diff --git a/apex/blobstore/service/java/com/android/server/blob/BlobMetadata.java b/apex/blobstore/service/java/com/android/server/blob/BlobMetadata.java
index 8b640ca..8edfab1 100644
--- a/apex/blobstore/service/java/com/android/server/blob/BlobMetadata.java
+++ b/apex/blobstore/service/java/com/android/server/blob/BlobMetadata.java
@@ -32,6 +32,7 @@
 import static com.android.server.blob.BlobStoreConfig.TAG;
 import static com.android.server.blob.BlobStoreConfig.XML_VERSION_ADD_DESC_RES_NAME;
 import static com.android.server.blob.BlobStoreConfig.XML_VERSION_ADD_STRING_DESC;
+import static com.android.server.blob.BlobStoreConfig.hasLeaseWaitTimeElapsed;
 import static com.android.server.blob.BlobStoreUtils.getDescriptionResourceId;
 import static com.android.server.blob.BlobStoreUtils.getPackageResources;
 
@@ -227,6 +228,35 @@
         return false;
     }
 
+    boolean isACommitter(@NonNull String packageName, int uid) {
+        synchronized (mMetadataLock) {
+            return isAnAccessor(mCommitters, packageName, uid);
+        }
+    }
+
+    boolean isALeasee(@Nullable String packageName, int uid) {
+        synchronized (mMetadataLock) {
+            return isAnAccessor(mLeasees, packageName, uid);
+        }
+    }
+
+    private static <T extends Accessor> boolean isAnAccessor(@NonNull ArraySet<T> accessors,
+            @Nullable String packageName, int uid) {
+        // Check if the package is an accessor of the data blob.
+        for (int i = 0, size = accessors.size(); i < size; ++i) {
+            final Accessor accessor = accessors.valueAt(i);
+            if (packageName != null && uid != INVALID_UID
+                    && accessor.equals(packageName, uid)) {
+                return true;
+            } else if (packageName != null && accessor.packageName.equals(packageName)) {
+                return true;
+            } else if (uid != INVALID_UID && accessor.uid == uid) {
+                return true;
+            }
+        }
+        return false;
+    }
+
     boolean isALeasee(@NonNull String packageName) {
         return isALeasee(packageName, INVALID_UID);
     }
@@ -243,24 +273,6 @@
         return hasOtherLeasees(null, uid);
     }
 
-    boolean isALeasee(@Nullable String packageName, int uid) {
-        synchronized (mMetadataLock) {
-            // Check if the package is a leasee of the data blob.
-            for (int i = 0, size = mLeasees.size(); i < size; ++i) {
-                final Leasee leasee = mLeasees.valueAt(i);
-                if (packageName != null && uid != INVALID_UID
-                        && leasee.equals(packageName, uid)) {
-                    return true;
-                } else if (packageName != null && leasee.packageName.equals(packageName)) {
-                    return true;
-                } else if (uid != INVALID_UID && leasee.uid == uid) {
-                    return true;
-                }
-            }
-        }
-        return false;
-    }
-
     private boolean hasOtherLeasees(@Nullable String packageName, int uid) {
         synchronized (mMetadataLock) {
             if (mCommitters.size() > 1 || mLeasees.size() > 1) {
@@ -352,6 +364,22 @@
         return revocableFd.getRevocableFileDescriptor();
     }
 
+    boolean shouldBeDeleted(boolean respectLeaseWaitTime) {
+        // Expired data blobs
+        if (getBlobHandle().isExpired()) {
+            return true;
+        }
+
+        // Blobs with no active leases
+        // TODO: Track commit time instead of using last modified time.
+        if ((!respectLeaseWaitTime || hasLeaseWaitTimeElapsed(getBlobFile().lastModified()))
+                && !hasLeases()) {
+            return true;
+        }
+
+        return false;
+    }
+
     void dump(IndentingPrintWriter fout, DumpArgs dumpArgs) {
         fout.println("blobHandle:");
         fout.increaseIndent();
diff --git a/apex/blobstore/service/java/com/android/server/blob/BlobStoreConfig.java b/apex/blobstore/service/java/com/android/server/blob/BlobStoreConfig.java
index 5e8ea7a..f2c1586 100644
--- a/apex/blobstore/service/java/com/android/server/blob/BlobStoreConfig.java
+++ b/apex/blobstore/service/java/com/android/server/blob/BlobStoreConfig.java
@@ -29,6 +29,7 @@
 import android.util.DataUnit;
 import android.util.Log;
 import android.util.Slog;
+import android.util.TimeUtils;
 
 import com.android.internal.util.IndentingPrintWriter;
 
@@ -88,6 +89,17 @@
         public static float TOTAL_BYTES_PER_APP_LIMIT_FRACTION =
                 DEFAULT_TOTAL_BYTES_PER_APP_LIMIT_FRACTION;
 
+        /**
+         * Denotes the duration from the time a blob is committed that we wait for a lease to
+         * be acquired before deciding to delete the blob for having no leases.
+         */
+        public static final String KEY_LEASE_ACQUISITION_WAIT_DURATION_MS =
+                "lease_acquisition_wait_time_ms";
+        public static final long DEFAULT_LEASE_ACQUISITION_WAIT_DURATION_MS =
+                TimeUnit.HOURS.toMillis(6);
+        public static long LEASE_ACQUISITION_WAIT_DURATION_MS =
+                DEFAULT_LEASE_ACQUISITION_WAIT_DURATION_MS;
+
         static void refresh(Properties properties) {
             if (!NAMESPACE_BLOBSTORE.equals(properties.getNamespace())) {
                 return;
@@ -102,6 +114,10 @@
                         TOTAL_BYTES_PER_APP_LIMIT_FRACTION = properties.getFloat(key,
                                 DEFAULT_TOTAL_BYTES_PER_APP_LIMIT_FRACTION);
                         break;
+                    case KEY_LEASE_ACQUISITION_WAIT_DURATION_MS:
+                        LEASE_ACQUISITION_WAIT_DURATION_MS = properties.getLong(key,
+                                DEFAULT_LEASE_ACQUISITION_WAIT_DURATION_MS);
+                        break;
                     default:
                         Slog.wtf(TAG, "Unknown key in device config properties: " + key);
                 }
@@ -117,6 +133,9 @@
             fout.println(String.format(dumpFormat, KEY_TOTAL_BYTES_PER_APP_LIMIT_FRACTION,
                     TOTAL_BYTES_PER_APP_LIMIT_FRACTION,
                     DEFAULT_TOTAL_BYTES_PER_APP_LIMIT_FRACTION));
+            fout.println(String.format(dumpFormat, KEY_LEASE_ACQUISITION_WAIT_DURATION_MS,
+                    TimeUtils.formatDuration(LEASE_ACQUISITION_WAIT_DURATION_MS),
+                    TimeUtils.formatDuration(DEFAULT_LEASE_ACQUISITION_WAIT_DURATION_MS)));
         }
     }
 
@@ -136,6 +155,14 @@
         return Math.max(DeviceConfigProperties.TOTAL_BYTES_PER_APP_LIMIT_FLOOR, totalBytesLimit);
     }
 
+    /**
+     * Returns whether the wait time for lease acquisition for a blob has elapsed.
+     */
+    public static boolean hasLeaseWaitTimeElapsed(long commitTimeMs) {
+        return commitTimeMs + DeviceConfigProperties.LEASE_ACQUISITION_WAIT_DURATION_MS
+                < System.currentTimeMillis();
+    }
+
     @Nullable
     public static File prepareBlobFile(long sessionId) {
         final File blobsDir = prepareBlobsDir();
diff --git a/apex/blobstore/service/java/com/android/server/blob/BlobStoreManagerService.java b/apex/blobstore/service/java/com/android/server/blob/BlobStoreManagerService.java
index f4b8f0f..15c069f 100644
--- a/apex/blobstore/service/java/com/android/server/blob/BlobStoreManagerService.java
+++ b/apex/blobstore/service/java/com/android/server/blob/BlobStoreManagerService.java
@@ -424,8 +424,9 @@
     private void releaseLeaseInternal(BlobHandle blobHandle, int callingUid,
             String callingPackage) {
         synchronized (mBlobsLock) {
-            final BlobMetadata blobMetadata = getUserBlobsLocked(UserHandle.getUserId(callingUid))
-                    .get(blobHandle);
+            final ArrayMap<BlobHandle, BlobMetadata> userBlobs =
+                    getUserBlobsLocked(UserHandle.getUserId(callingUid));
+            final BlobMetadata blobMetadata = userBlobs.get(blobHandle);
             if (blobMetadata == null || !blobMetadata.isAccessAllowedForCaller(
                     callingPackage, callingUid)) {
                 throw new SecurityException("Caller not allowed to access " + blobHandle
@@ -436,6 +437,10 @@
                 Slog.v(TAG, "Released lease on " + blobHandle
                         + "; callingUid=" + callingUid + ", callingPackage=" + callingPackage);
             }
+            if (blobMetadata.shouldBeDeleted(true /* respectLeaseWaitTime */)) {
+                deleteBlobLocked(blobMetadata);
+                userBlobs.remove(blobHandle);
+            }
             writeBlobsInfoAsync();
         }
     }
@@ -863,12 +868,15 @@
                     getUserBlobsLocked(UserHandle.getUserId(uid));
             userBlobs.entrySet().removeIf(entry -> {
                 final BlobMetadata blobMetadata = entry.getValue();
-                blobMetadata.removeCommitter(packageName, uid);
+                final boolean isACommitter = blobMetadata.isACommitter(packageName, uid);
+                if (isACommitter) {
+                    blobMetadata.removeCommitter(packageName, uid);
+                }
                 blobMetadata.removeLeasee(packageName, uid);
-                // Delete the blob if it doesn't have any active leases.
-                if (!blobMetadata.hasLeases()) {
-                    blobMetadata.getBlobFile().delete();
-                    mActiveBlobIds.remove(blobMetadata.getBlobId());
+                // Regardless of when the blob is committed, we need to delete
+                // it if it was from the deleted package to ensure we delete all traces of it.
+                if (blobMetadata.shouldBeDeleted(isACommitter /* respectLeaseWaitTime */)) {
+                    deleteBlobLocked(blobMetadata);
                     return true;
                 }
                 return false;
@@ -899,8 +907,7 @@
             if (userBlobs != null) {
                 for (int i = 0, count = userBlobs.size(); i < count; ++i) {
                     final BlobMetadata blobMetadata = userBlobs.valueAt(i);
-                    blobMetadata.getBlobFile().delete();
-                    mActiveBlobIds.remove(blobMetadata.getBlobId());
+                    deleteBlobLocked(blobMetadata);
                 }
             }
             if (LOGV) {
@@ -938,27 +945,14 @@
         for (int i = 0, userCount = mBlobsMap.size(); i < userCount; ++i) {
             final ArrayMap<BlobHandle, BlobMetadata> userBlobs = mBlobsMap.valueAt(i);
             userBlobs.entrySet().removeIf(entry -> {
-                final BlobHandle blobHandle = entry.getKey();
                 final BlobMetadata blobMetadata = entry.getValue();
-                boolean shouldRemove = false;
 
-                // Cleanup expired data blobs.
-                if (blobHandle.isExpired()) {
-                    shouldRemove = true;
-                }
-
-                // Cleanup blobs with no active leases.
-                // TODO: Exclude blobs which were just committed.
-                if (!blobMetadata.hasLeases()) {
-                    shouldRemove = true;
-                }
-
-                if (shouldRemove) {
-                    blobMetadata.getBlobFile().delete();
-                    mActiveBlobIds.remove(blobMetadata.getBlobId());
+                if (blobMetadata.shouldBeDeleted(true /* respectLeaseWaitTime */)) {
+                    deleteBlobLocked(blobMetadata);
                     deletedBlobIds.add(blobMetadata.getBlobId());
+                    return true;
                 }
-                return shouldRemove;
+                return false;
             });
         }
         writeBlobsInfoAsync();
@@ -995,6 +989,12 @@
         writeBlobSessionsAsync();
     }
 
+    @GuardedBy("mBlobsLock")
+    private void deleteBlobLocked(BlobMetadata blobMetadata) {
+        blobMetadata.getBlobFile().delete();
+        mActiveBlobIds.remove(blobMetadata.getBlobId());
+    }
+
     void runClearAllSessions(@UserIdInt int userId) {
         synchronized (mBlobsLock) {
             if (userId == UserHandle.USER_ALL) {
@@ -1024,9 +1024,8 @@
             if (blobMetadata == null) {
                 return;
             }
-            blobMetadata.getBlobFile().delete();
+            deleteBlobLocked(blobMetadata);
             userBlobs.remove(blobHandle);
-            mActiveBlobIds.remove(blobMetadata.getBlobId());
             writeBlobsInfoAsync();
         }
     }
diff --git a/services/tests/mockingservicestests/src/com/android/server/blob/BlobStoreManagerServiceTest.java b/services/tests/mockingservicestests/src/com/android/server/blob/BlobStoreManagerServiceTest.java
index cd39144..f4d7b8b 100644
--- a/services/tests/mockingservicestests/src/com/android/server/blob/BlobStoreManagerServiceTest.java
+++ b/services/tests/mockingservicestests/src/com/android/server/blob/BlobStoreManagerServiceTest.java
@@ -15,6 +15,7 @@
  */
 package com.android.server.blob;
 
+import static com.android.dx.mockito.inline.extended.ExtendedMockito.doCallRealMethod;
 import static com.android.dx.mockito.inline.extended.ExtendedMockito.doReturn;
 import static com.android.dx.mockito.inline.extended.ExtendedMockito.mock;
 import static com.android.dx.mockito.inline.extended.ExtendedMockito.mockitoSession;
@@ -22,6 +23,8 @@
 
 import static com.google.common.truth.Truth.assertThat;
 
+import static org.mockito.ArgumentMatchers.anyBoolean;
+import static org.mockito.ArgumentMatchers.anyLong;
 import static org.mockito.Mockito.never;
 import static org.mockito.Mockito.verify;
 
@@ -89,6 +92,7 @@
         doReturn(mBlobsDir).when(() -> BlobStoreConfig.getBlobsDir());
         doReturn(true).when(mBlobsDir).exists();
         doReturn(new File[0]).when(mBlobsDir).listFiles();
+        doReturn(true).when(() -> BlobStoreConfig.hasLeaseWaitTimeElapsed(anyLong()));
 
         mContext = InstrumentationRegistry.getTargetContext();
         mHandler = new TestHandler(Looper.getMainLooper());
@@ -138,19 +142,32 @@
         final long blobId1 = 978;
         final File blobFile1 = mock(File.class);
         final BlobHandle blobHandle1 = BlobHandle.createWithSha256("digest1".getBytes(),
-                "label1", System.currentTimeMillis(), "tag1");
-        final BlobMetadata blobMetadata1 = createBlobMetadataMock(blobId1, blobFile1, true);
+                "label1", System.currentTimeMillis() + 10000, "tag1");
+        final BlobMetadata blobMetadata1 = createBlobMetadataMock(blobId1, blobFile1,
+                blobHandle1, true /* hasLeases */);
+        doReturn(true).when(blobMetadata1).isACommitter(TEST_PKG1, TEST_UID1);
         mUserBlobs.put(blobHandle1, blobMetadata1);
 
         final long blobId2 = 347;
         final File blobFile2 = mock(File.class);
         final BlobHandle blobHandle2 = BlobHandle.createWithSha256("digest2".getBytes(),
-                "label2", System.currentTimeMillis(), "tag2");
-        final BlobMetadata blobMetadata2 = createBlobMetadataMock(blobId2, blobFile2, false);
+                "label2", System.currentTimeMillis() + 20000, "tag2");
+        final BlobMetadata blobMetadata2 = createBlobMetadataMock(blobId2, blobFile2,
+                blobHandle2, false /* hasLeases */);
+        doReturn(false).when(blobMetadata2).isACommitter(TEST_PKG1, TEST_UID1);
         mUserBlobs.put(blobHandle2, blobMetadata2);
 
+        final long blobId3 = 49875;
+        final File blobFile3 = mock(File.class);
+        final BlobHandle blobHandle3 = BlobHandle.createWithSha256("digest3".getBytes(),
+                "label3", System.currentTimeMillis() - 1000, "tag3");
+        final BlobMetadata blobMetadata3 = createBlobMetadataMock(blobId3, blobFile3,
+                blobHandle3, true /* hasLeases */);
+        doReturn(true).when(blobMetadata3).isACommitter(TEST_PKG1, TEST_UID1);
+        mUserBlobs.put(blobHandle3, blobMetadata3);
+
         mService.addActiveIdsForTest(sessionId1, sessionId2, sessionId3, sessionId4,
-                blobId1, blobId2);
+                blobId1, blobId2, blobId3);
 
         // Invoke test method
         mService.handlePackageRemoved(TEST_PKG1, TEST_UID1);
@@ -170,20 +187,24 @@
         // Verify blobs are removed
         verify(blobMetadata1).removeCommitter(TEST_PKG1, TEST_UID1);
         verify(blobMetadata1).removeLeasee(TEST_PKG1, TEST_UID1);
-        verify(blobMetadata2).removeCommitter(TEST_PKG1, TEST_UID1);
+        verify(blobMetadata2, never()).removeCommitter(TEST_PKG1, TEST_UID1);
         verify(blobMetadata2).removeLeasee(TEST_PKG1, TEST_UID1);
+        verify(blobMetadata3).removeCommitter(TEST_PKG1, TEST_UID1);
+        verify(blobMetadata3).removeLeasee(TEST_PKG1, TEST_UID1);
 
         verify(blobFile1, never()).delete();
         verify(blobFile2).delete();
+        verify(blobFile3).delete();
 
         assertThat(mUserBlobs.size()).isEqualTo(1);
         assertThat(mUserBlobs.get(blobHandle1)).isNotNull();
         assertThat(mUserBlobs.get(blobHandle2)).isNull();
+        assertThat(mUserBlobs.get(blobHandle3)).isNull();
 
         assertThat(mService.getActiveIdsForTest()).containsExactly(
                 sessionId2, sessionId3, blobId1);
         assertThat(mService.getKnownIdsForTest()).containsExactly(
-                sessionId1, sessionId2, sessionId3, sessionId4, blobId1, blobId2);
+                sessionId1, sessionId2, sessionId3, sessionId4, blobId1, blobId2, blobId3);
     }
 
     @Test
@@ -269,21 +290,24 @@
         final File blobFile1 = mock(File.class);
         final BlobHandle blobHandle1 = BlobHandle.createWithSha256("digest1".getBytes(),
                 "label1", System.currentTimeMillis() - 2000, "tag1");
-        final BlobMetadata blobMetadata1 = createBlobMetadataMock(blobId1, blobFile1, true);
+        final BlobMetadata blobMetadata1 = createBlobMetadataMock(blobId1, blobFile1, blobHandle1,
+                true /* hasLeases */);
         mUserBlobs.put(blobHandle1, blobMetadata1);
 
         final long blobId2 = 78974;
         final File blobFile2 = mock(File.class);
         final BlobHandle blobHandle2 = BlobHandle.createWithSha256("digest2".getBytes(),
                 "label2", System.currentTimeMillis() + 30000, "tag2");
-        final BlobMetadata blobMetadata2 = createBlobMetadataMock(blobId2, blobFile2, true);
+        final BlobMetadata blobMetadata2 = createBlobMetadataMock(blobId2, blobFile2, blobHandle2,
+                true /* hasLeases */);
         mUserBlobs.put(blobHandle2, blobMetadata2);
 
         final long blobId3 = 97;
         final File blobFile3 = mock(File.class);
         final BlobHandle blobHandle3 = BlobHandle.createWithSha256("digest3".getBytes(),
                 "label3", System.currentTimeMillis() + 4400000, "tag3");
-        final BlobMetadata blobMetadata3 = createBlobMetadataMock(blobId3, blobFile3, false);
+        final BlobMetadata blobMetadata3 = createBlobMetadataMock(blobId3, blobFile3, blobHandle3,
+                false /* hasLeases */);
         mUserBlobs.put(blobHandle3, blobMetadata3);
 
         mService.addActiveIdsForTest(blobId1, blobId2, blobId3);
@@ -350,11 +374,14 @@
         return session;
     }
 
-    private BlobMetadata createBlobMetadataMock(long blobId, File blobFile, boolean hasLeases) {
+    private BlobMetadata createBlobMetadataMock(long blobId, File blobFile,
+            BlobHandle blobHandle, boolean hasLeases) {
         final BlobMetadata blobMetadata = mock(BlobMetadata.class);
         doReturn(blobId).when(blobMetadata).getBlobId();
         doReturn(blobFile).when(blobMetadata).getBlobFile();
         doReturn(hasLeases).when(blobMetadata).hasLeases();
+        doReturn(blobHandle).when(blobMetadata).getBlobHandle();
+        doCallRealMethod().when(blobMetadata).shouldBeDeleted(anyBoolean());
         return blobMetadata;
     }
 
diff --git a/tests/BlobStoreTestUtils/src/com/android/utils/blob/DummyBlobData.java b/tests/BlobStoreTestUtils/src/com/android/utils/blob/DummyBlobData.java
index b805744..42908be 100644
--- a/tests/BlobStoreTestUtils/src/com/android/utils/blob/DummyBlobData.java
+++ b/tests/BlobStoreTestUtils/src/com/android/utils/blob/DummyBlobData.java
@@ -46,7 +46,7 @@
     byte[] mFileDigest;
     long mExpiryTimeMs;
 
-    public DummyBlobData(Builder builder) {
+    private DummyBlobData(Builder builder) {
         mRandom = new Random(builder.getRandomSeed());
         mFile = new File(builder.getContext().getFilesDir(), builder.getFileName());
         mFileSize = builder.getFileSize();
diff --git a/tests/BlobStoreTestUtils/src/com/android/utils/blob/Utils.java b/tests/BlobStoreTestUtils/src/com/android/utils/blob/Utils.java
index 654c1e2..482b23f 100644
--- a/tests/BlobStoreTestUtils/src/com/android/utils/blob/Utils.java
+++ b/tests/BlobStoreTestUtils/src/com/android/utils/blob/Utils.java
@@ -124,7 +124,11 @@
         final BlobStoreManager blobStoreManager = (BlobStoreManager) context.getSystemService(
                 Context.BLOB_STORE_SERVICE);
         blobStoreManager.releaseLease(blobHandle);
-        assertThat(blobStoreManager.getLeaseInfo(blobHandle)).isNull();
+        try {
+            assertThat(blobStoreManager.getLeaseInfo(blobHandle)).isNull();
+        } catch (SecurityException e) {
+            // Expected, ignore
+        }
     }
 
     private static void assertLeaseInfo(LeaseInfo leaseInfo, String packageName,