diff --git a/packages/NetworkStack/AndroidManifestBase.xml b/packages/NetworkStack/AndroidManifestBase.xml
index 69a4da4..d00a551 100644
--- a/packages/NetworkStack/AndroidManifestBase.xml
+++ b/packages/NetworkStack/AndroidManifestBase.xml
@@ -25,5 +25,9 @@
         android:defaultToDeviceProtectedStorage="true"
         android:directBootAware="true"
         android:usesCleartextTraffic="true">
+
+        <service android:name="com.android.server.connectivity.ipmemorystore.RegularMaintenanceJobService"
+                 android:permission="android.permission.BIND_JOB_SERVICE" >
+        </service>
     </application>
 </manifest>
diff --git a/packages/NetworkStack/src/com/android/server/connectivity/ipmemorystore/IpMemoryStoreDatabase.java b/packages/NetworkStack/src/com/android/server/connectivity/ipmemorystore/IpMemoryStoreDatabase.java
index b4eeefd..764e2d0 100644
--- a/packages/NetworkStack/src/com/android/server/connectivity/ipmemorystore/IpMemoryStoreDatabase.java
+++ b/packages/NetworkStack/src/com/android/server/connectivity/ipmemorystore/IpMemoryStoreDatabase.java
@@ -139,8 +139,9 @@
     /** The SQLite DB helper */
     public static class DbHelper extends SQLiteOpenHelper {
         // Update this whenever changing the schema.
-        private static final int SCHEMA_VERSION = 3;
+        private static final int SCHEMA_VERSION = 4;
         private static final String DATABASE_FILENAME = "IpMemoryStore.db";
+        private static final String TRIGGER_NAME = "delete_cascade_to_private";
 
         public DbHelper(@NonNull final Context context) {
             super(context, DATABASE_FILENAME, null, SCHEMA_VERSION);
@@ -152,6 +153,7 @@
         public void onCreate(@NonNull final SQLiteDatabase db) {
             db.execSQL(NetworkAttributesContract.CREATE_TABLE);
             db.execSQL(PrivateDataContract.CREATE_TABLE);
+            createTrigger(db);
         }
 
         /** Called when the database is upgraded */
@@ -172,6 +174,10 @@
                             + " " + NetworkAttributesContract.COLTYPE_ASSIGNEDV4ADDRESSEXPIRY;
                     db.execSQL(sqlUpgradeAddressExpiry);
                 }
+
+                if (oldVersion < 4) {
+                    createTrigger(db);
+                }
             } catch (SQLiteException e) {
                 Log.e(TAG, "Could not upgrade to the new version", e);
                 // create database with new version
@@ -188,8 +194,20 @@
             // Downgrades always nuke all data and recreate an empty table.
             db.execSQL(NetworkAttributesContract.DROP_TABLE);
             db.execSQL(PrivateDataContract.DROP_TABLE);
+            db.execSQL("DROP TRIGGER " + TRIGGER_NAME);
             onCreate(db);
         }
+
+        private void createTrigger(@NonNull final SQLiteDatabase db) {
+            final String createTrigger = "CREATE TRIGGER " + TRIGGER_NAME
+                    + " DELETE ON " + NetworkAttributesContract.TABLENAME
+                    + " BEGIN"
+                    + " DELETE FROM " + PrivateDataContract.TABLENAME + " WHERE OLD."
+                    + NetworkAttributesContract.COLNAME_L2KEY
+                    + "=" + PrivateDataContract.COLNAME_L2KEY
+                    + "; END;";
+            db.execSQL(createTrigger);
+        }
     }
 
     @NonNull
@@ -336,7 +354,7 @@
     }
 
     // If the attributes are null, this will only write the expiry.
-    // Returns an int out of Status.{SUCCESS,ERROR_*}
+    // Returns an int out of Status.{SUCCESS, ERROR_*}
     static int storeNetworkAttributes(@NonNull final SQLiteDatabase db, @NonNull final String key,
             final long expiry, @Nullable final NetworkAttributes attributes) {
         final ContentValues cv = toContentValues(key, attributes, expiry);
@@ -361,7 +379,7 @@
         return Status.ERROR_STORAGE;
     }
 
-    // Returns an int out of Status.{SUCCESS,ERROR_*}
+    // Returns an int out of Status.{SUCCESS, ERROR_*}
     static int storeBlob(@NonNull final SQLiteDatabase db, @NonNull final String key,
             @NonNull final String clientId, @NonNull final String name,
             @NonNull final byte[] data) {
@@ -524,6 +542,93 @@
         return bestKey;
     }
 
+    // Drops all records that are expired. Relevance has decayed to zero of these records. Returns
+    // an int out of Status.{SUCCESS, ERROR_*}
+    static int dropAllExpiredRecords(@NonNull final SQLiteDatabase db) {
+        db.beginTransaction();
+        try {
+            // Deletes NetworkAttributes that have expired.
+            db.delete(NetworkAttributesContract.TABLENAME,
+                    NetworkAttributesContract.COLNAME_EXPIRYDATE + " < ?",
+                    new String[]{Long.toString(System.currentTimeMillis())});
+            db.setTransactionSuccessful();
+        } catch (SQLiteException e) {
+            Log.e(TAG, "Could not delete data from memory store", e);
+            return Status.ERROR_STORAGE;
+        } finally {
+            db.endTransaction();
+        }
+
+        // Execute vacuuming here if above operation has no exception. If above operation got
+        // exception, vacuuming can be ignored for reducing unnecessary consumption.
+        try {
+            db.execSQL("VACUUM");
+        } catch (SQLiteException e) {
+            // Do nothing.
+        }
+        return Status.SUCCESS;
+    }
+
+    // Drops number of records that start from the lowest expiryDate. Returns an int out of
+    // Status.{SUCCESS, ERROR_*}
+    static int dropNumberOfRecords(@NonNull final SQLiteDatabase db, int number) {
+        if (number <= 0) {
+            return Status.ERROR_ILLEGAL_ARGUMENT;
+        }
+
+        // Queries number of NetworkAttributes that start from the lowest expiryDate.
+        final Cursor cursor = db.query(NetworkAttributesContract.TABLENAME,
+                new String[] {NetworkAttributesContract.COLNAME_EXPIRYDATE}, // columns
+                null, // selection
+                null, // selectionArgs
+                null, // groupBy
+                null, // having
+                NetworkAttributesContract.COLNAME_EXPIRYDATE, // orderBy
+                Integer.toString(number)); // limit
+        if (cursor == null || cursor.getCount() <= 0) return Status.ERROR_GENERIC;
+        cursor.moveToLast();
+
+        //Get the expiryDate from last record.
+        final long expiryDate = getLong(cursor, NetworkAttributesContract.COLNAME_EXPIRYDATE, 0);
+        cursor.close();
+
+        db.beginTransaction();
+        try {
+            // Deletes NetworkAttributes that expiryDate are lower than given value.
+            db.delete(NetworkAttributesContract.TABLENAME,
+                    NetworkAttributesContract.COLNAME_EXPIRYDATE + " <= ?",
+                    new String[]{Long.toString(expiryDate)});
+            db.setTransactionSuccessful();
+        } catch (SQLiteException e) {
+            Log.e(TAG, "Could not delete data from memory store", e);
+            return Status.ERROR_STORAGE;
+        } finally {
+            db.endTransaction();
+        }
+
+        // Execute vacuuming here if above operation has no exception. If above operation got
+        // exception, vacuuming can be ignored for reducing unnecessary consumption.
+        try {
+            db.execSQL("VACUUM");
+        } catch (SQLiteException e) {
+            // Do nothing.
+        }
+        return Status.SUCCESS;
+    }
+
+    static int getTotalRecordNumber(@NonNull final SQLiteDatabase db) {
+        // Query the total number of NetworkAttributes
+        final Cursor cursor = db.query(NetworkAttributesContract.TABLENAME,
+                new String[] {"COUNT(*)"}, // columns
+                null, // selection
+                null, // selectionArgs
+                null, // groupBy
+                null, // having
+                null); // orderBy
+        cursor.moveToFirst();
+        return cursor == null ? 0 : cursor.getInt(0);
+    }
+
     // Helper methods
     private static String getString(final Cursor cursor, final String columnName) {
         final int columnIndex = cursor.getColumnIndex(columnName);
diff --git a/packages/NetworkStack/src/com/android/server/connectivity/ipmemorystore/IpMemoryStoreService.java b/packages/NetworkStack/src/com/android/server/connectivity/ipmemorystore/IpMemoryStoreService.java
index f801b35..5650f21 100644
--- a/packages/NetworkStack/src/com/android/server/connectivity/ipmemorystore/IpMemoryStoreService.java
+++ b/packages/NetworkStack/src/com/android/server/connectivity/ipmemorystore/IpMemoryStoreService.java
@@ -22,6 +22,7 @@
 import static android.net.ipmemorystore.Status.SUCCESS;
 
 import static com.android.server.connectivity.ipmemorystore.IpMemoryStoreDatabase.EXPIRY_ERROR;
+import static com.android.server.connectivity.ipmemorystore.RegularMaintenanceJobService.InterruptMaintenance;
 
 import android.annotation.NonNull;
 import android.annotation.Nullable;
@@ -43,6 +44,9 @@
 import android.os.RemoteException;
 import android.util.Log;
 
+import com.android.internal.annotations.VisibleForTesting;
+
+import java.io.File;
 import java.util.concurrent.ExecutorService;
 import java.util.concurrent.Executors;
 
@@ -57,8 +61,17 @@
 public class IpMemoryStoreService extends IIpMemoryStore.Stub {
     private static final String TAG = IpMemoryStoreService.class.getSimpleName();
     private static final int MAX_CONCURRENT_THREADS = 4;
+    private static final int DATABASE_SIZE_THRESHOLD = 10 * 1024 * 1024; //10MB
+    private static final int MAX_DROP_RECORD_TIMES = 500;
+    private static final int MIN_DELETE_NUM = 5;
     private static final boolean DBG = true;
 
+    // Error codes below are internal and used for notifying status beteween IpMemoryStore modules.
+    static final int ERROR_INTERNAL_BASE = -1_000_000_000;
+    // This error code is used for maintenance only to notify RegularMaintenanceJobService that
+    // full maintenance job has been interrupted.
+    static final int ERROR_INTERNAL_INTERRUPTED = ERROR_INTERNAL_BASE - 1;
+
     @NonNull
     final Context mContext;
     @Nullable
@@ -111,6 +124,7 @@
         // with judicious subclassing of ThreadPoolExecutor, but that's a lot of dangerous
         // complexity for little benefit in this case.
         mExecutor = Executors.newWorkStealingPool(MAX_CONCURRENT_THREADS);
+        RegularMaintenanceJobService.schedule(mContext, this);
     }
 
     /**
@@ -125,6 +139,7 @@
         // guarantee the threads can be terminated in any given amount of time.
         mExecutor.shutdownNow();
         if (mDb != null) mDb.close();
+        RegularMaintenanceJobService.unschedule(mContext);
     }
 
     /** Helper function to make a status object */
@@ -394,4 +409,89 @@
             }
         });
     }
+
+    /** Get db size threshold. */
+    @VisibleForTesting
+    protected int getDbSizeThreshold() {
+        return DATABASE_SIZE_THRESHOLD;
+    }
+
+    private long getDbSize() {
+        final File dbFile = new File(mDb.getPath());
+        try {
+            return dbFile.length();
+        } catch (final SecurityException e) {
+            if (DBG) Log.e(TAG, "Read db size access deny.", e);
+            // Return zero value if can't get disk usage exactly.
+            return 0;
+        }
+    }
+
+    /** Check if db size is over the threshold. */
+    @VisibleForTesting
+    boolean isDbSizeOverThreshold() {
+        return getDbSize() > getDbSizeThreshold();
+    }
+
+    /**
+     * Full maintenance.
+     *
+     * @param listener A listener to inform of the completion of this call.
+     */
+    void fullMaintenance(@NonNull final IOnStatusListener listener,
+            @NonNull final InterruptMaintenance interrupt) {
+        mExecutor.execute(() -> {
+            try {
+                if (null == mDb) {
+                    listener.onComplete(makeStatus(ERROR_DATABASE_CANNOT_BE_OPENED));
+                    return;
+                }
+
+                // Interrupt maintenance because the scheduling job has been canceled.
+                if (checkForInterrupt(listener, interrupt)) return;
+
+                int result = SUCCESS;
+                // Drop all records whose relevance has decayed to zero.
+                // This is the first step to decrease memory store size.
+                result = IpMemoryStoreDatabase.dropAllExpiredRecords(mDb);
+
+                if (checkForInterrupt(listener, interrupt)) return;
+
+                // Aggregate historical data in passes
+                // TODO : Waiting for historical data implement.
+
+                // Check if db size meets the storage goal(10MB). If not, keep dropping records and
+                // aggregate historical data until the storage goal is met. Use for loop with 500
+                // times restriction to prevent infinite loop (Deleting records always fail and db
+                // size is still over the threshold)
+                for (int i = 0; isDbSizeOverThreshold() && i < MAX_DROP_RECORD_TIMES; i++) {
+                    if (checkForInterrupt(listener, interrupt)) return;
+
+                    final int totalNumber = IpMemoryStoreDatabase.getTotalRecordNumber(mDb);
+                    final long dbSize = getDbSize();
+                    final float decreaseRate = (dbSize == 0)
+                            ? 0 : (float) (dbSize - getDbSizeThreshold()) / (float) dbSize;
+                    final int deleteNumber = Math.max(
+                            (int) (totalNumber * decreaseRate), MIN_DELETE_NUM);
+
+                    result = IpMemoryStoreDatabase.dropNumberOfRecords(mDb, deleteNumber);
+
+                    if (checkForInterrupt(listener, interrupt)) return;
+
+                    // Aggregate historical data
+                    // TODO : Waiting for historical data implement.
+                }
+                listener.onComplete(makeStatus(result));
+            } catch (final RemoteException e) {
+                // Client at the other end died
+            }
+        });
+    }
+
+    private boolean checkForInterrupt(@NonNull final IOnStatusListener listener,
+            @NonNull final InterruptMaintenance interrupt) throws RemoteException {
+        if (!interrupt.isInterrupted()) return false;
+        listener.onComplete(makeStatus(ERROR_INTERNAL_INTERRUPTED));
+        return true;
+    }
 }
diff --git a/packages/NetworkStack/src/com/android/server/connectivity/ipmemorystore/RegularMaintenanceJobService.java b/packages/NetworkStack/src/com/android/server/connectivity/ipmemorystore/RegularMaintenanceJobService.java
new file mode 100644
index 0000000..2775fde
--- /dev/null
+++ b/packages/NetworkStack/src/com/android/server/connectivity/ipmemorystore/RegularMaintenanceJobService.java
@@ -0,0 +1,140 @@
+/*
+ * Copyright (C) 2019 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.android.server.connectivity.ipmemorystore;
+
+import android.app.job.JobInfo;
+import android.app.job.JobParameters;
+import android.app.job.JobScheduler;
+import android.app.job.JobService;
+import android.content.ComponentName;
+import android.content.Context;
+import android.net.ipmemorystore.IOnStatusListener;
+import android.net.ipmemorystore.Status;
+import android.net.ipmemorystore.StatusParcelable;
+import android.os.IBinder;
+import android.os.RemoteException;
+import android.util.Log;
+
+import java.util.ArrayList;
+import java.util.concurrent.TimeUnit;
+
+/**
+ * Regular maintenance job service.
+ * @hide
+ */
+public final class RegularMaintenanceJobService extends JobService {
+    // Must be unique within the system server uid.
+    public static final int REGULAR_MAINTENANCE_ID = 3345678;
+
+    /**
+     * Class for interrupt check of maintenance job.
+     */
+    public static final class InterruptMaintenance {
+        private volatile boolean mIsInterrupted;
+        private final int mJobId;
+
+        public InterruptMaintenance(int jobId) {
+            mJobId = jobId;
+            mIsInterrupted = false;
+        }
+
+        public int getJobId() {
+            return mJobId;
+        }
+
+        public void setInterrupted(boolean interrupt) {
+            mIsInterrupted = interrupt;
+        }
+
+        public boolean isInterrupted() {
+            return mIsInterrupted;
+        }
+    }
+
+    private static final ArrayList<InterruptMaintenance> sInterruptList = new ArrayList<>();
+    private static IpMemoryStoreService sIpMemoryStoreService;
+
+    @Override
+    public boolean onStartJob(JobParameters params) {
+        if (sIpMemoryStoreService == null) {
+            Log.wtf("RegularMaintenanceJobService",
+                    "Can not start job because sIpMemoryStoreService is null.");
+            return false;
+        }
+        final InterruptMaintenance im = new InterruptMaintenance(params.getJobId());
+        sInterruptList.add(im);
+
+        sIpMemoryStoreService.fullMaintenance(new IOnStatusListener() {
+            @Override
+            public void onComplete(final StatusParcelable statusParcelable) throws RemoteException {
+                final Status result = new Status(statusParcelable);
+                if (!result.isSuccess()) {
+                    Log.e("RegularMaintenanceJobService", "Regular maintenance failed."
+                            + " Error is " + result.resultCode);
+                }
+                sInterruptList.remove(im);
+                jobFinished(params, !result.isSuccess());
+            }
+
+            @Override
+            public IBinder asBinder() {
+                return null;
+            }
+        }, im);
+        return true;
+    }
+
+    @Override
+    public boolean onStopJob(JobParameters params) {
+        final int jobId = params.getJobId();
+        for (InterruptMaintenance im : sInterruptList) {
+            if (im.getJobId() == jobId) {
+                im.setInterrupted(true);
+            }
+        }
+        return true;
+    }
+
+    /** Schedule regular maintenance job */
+    static void schedule(Context context, IpMemoryStoreService ipMemoryStoreService) {
+        final JobScheduler jobScheduler =
+                (JobScheduler) context.getSystemService(Context.JOB_SCHEDULER_SERVICE);
+
+        final ComponentName maintenanceJobName =
+                new ComponentName(context, RegularMaintenanceJobService.class);
+
+        // Regular maintenance is scheduled for when the device is idle with access power and a
+        // minimum interval of one day.
+        final JobInfo regularMaintenanceJob =
+                new JobInfo.Builder(REGULAR_MAINTENANCE_ID, maintenanceJobName)
+                        .setRequiresDeviceIdle(true)
+                        .setRequiresCharging(true)
+                        .setRequiresBatteryNotLow(true)
+                        .setPeriodic(TimeUnit.HOURS.toMillis(24)).build();
+
+        jobScheduler.schedule(regularMaintenanceJob);
+        sIpMemoryStoreService = ipMemoryStoreService;
+    }
+
+    /** Unschedule regular maintenance job */
+    static void unschedule(Context context) {
+        final JobScheduler jobScheduler =
+                (JobScheduler) context.getSystemService(Context.JOB_SCHEDULER_SERVICE);
+        jobScheduler.cancel(REGULAR_MAINTENANCE_ID);
+        sIpMemoryStoreService = null;
+    }
+}
diff --git a/packages/NetworkStack/tests/src/com/android/server/connectivity/ipmemorystore/IpMemoryStoreServiceTest.java b/packages/NetworkStack/tests/src/com/android/server/connectivity/ipmemorystore/IpMemoryStoreServiceTest.java
index 071ff26..94cc589 100644
--- a/packages/NetworkStack/tests/src/com/android/server/connectivity/ipmemorystore/IpMemoryStoreServiceTest.java
+++ b/packages/NetworkStack/tests/src/com/android/server/connectivity/ipmemorystore/IpMemoryStoreServiceTest.java
@@ -16,6 +16,8 @@
 
 package com.android.server.connectivity.ipmemorystore;
 
+import static com.android.server.connectivity.ipmemorystore.RegularMaintenanceJobService.InterruptMaintenance;
+
 import static org.junit.Assert.assertEquals;
 import static org.junit.Assert.assertFalse;
 import static org.junit.Assert.assertNull;
@@ -24,6 +26,7 @@
 import static org.mockito.ArgumentMatchers.anyString;
 import static org.mockito.Mockito.doReturn;
 
+import android.app.job.JobScheduler;
 import android.content.Context;
 import android.net.ipmemorystore.Blob;
 import android.net.ipmemorystore.IOnBlobRetrievedListener;
@@ -37,6 +40,7 @@
 import android.net.ipmemorystore.SameL3NetworkResponseParcelable;
 import android.net.ipmemorystore.Status;
 import android.net.ipmemorystore.StatusParcelable;
+import android.os.ConditionVariable;
 import android.os.IBinder;
 import android.os.RemoteException;
 
@@ -69,6 +73,9 @@
     private static final String TEST_CLIENT_ID = "testClientId";
     private static final String TEST_DATA_NAME = "testData";
 
+    private static final int TEST_DATABASE_SIZE_THRESHOLD = 100 * 1024; //100KB
+    private static final int DEFAULT_TIMEOUT_MS = 5000;
+    private static final int LONG_TIMEOUT_MS = 30000;
     private static final int FAKE_KEY_COUNT = 20;
     private static final String[] FAKE_KEYS;
     static {
@@ -80,6 +87,8 @@
 
     @Mock
     private Context mMockContext;
+    @Mock
+    private JobScheduler mMockJobScheduler;
     private File mDbFile;
 
     private IpMemoryStoreService mService;
@@ -91,7 +100,22 @@
         final File dir = context.getFilesDir();
         mDbFile = new File(dir, "test.db");
         doReturn(mDbFile).when(mMockContext).getDatabasePath(anyString());
-        mService = new IpMemoryStoreService(mMockContext);
+        doReturn(mMockJobScheduler).when(mMockContext)
+                .getSystemService(Context.JOB_SCHEDULER_SERVICE);
+        mService = new IpMemoryStoreService(mMockContext) {
+            @Override
+            protected int getDbSizeThreshold() {
+                return TEST_DATABASE_SIZE_THRESHOLD;
+            }
+
+            @Override
+            boolean isDbSizeOverThreshold() {
+                // Add a 100ms delay here for pausing maintenance job a while. Interrupted flag can
+                // be set at this time.
+                waitForMs(100);
+                return super.isDbSizeOverThreshold();
+            }
+        };
     }
 
     @After
@@ -200,10 +224,15 @@
 
     // Helper method to factorize some boilerplate
     private void doLatched(final String timeoutMessage, final Consumer<CountDownLatch> functor) {
+        doLatched(timeoutMessage, functor, DEFAULT_TIMEOUT_MS);
+    }
+
+    private void doLatched(final String timeoutMessage, final Consumer<CountDownLatch> functor,
+            final int timeout) {
         final CountDownLatch latch = new CountDownLatch(1);
         functor.accept(latch);
         try {
-            if (!latch.await(5000, TimeUnit.MILLISECONDS)) {
+            if (!latch.await(timeout, TimeUnit.MILLISECONDS)) {
                 fail(timeoutMessage);
             }
         } catch (InterruptedException e) {
@@ -224,6 +253,46 @@
                 })));
     }
 
+    /** Insert large data that db size will be over threshold for maintenance test usage. */
+    private void insertFakeDataAndOverThreshold() {
+        try {
+            final NetworkAttributes.Builder na = new NetworkAttributes.Builder();
+            na.setAssignedV4Address((Inet4Address) Inet4Address.getByName("1.2.3.4"));
+            na.setGroupHint("hint1");
+            na.setMtu(219);
+            na.setDnsAddresses(Arrays.asList(Inet6Address.getByName("0A1C:2E40:480A::1CA6")));
+            final byte[] data = new byte[]{-3, 6, 8, -9, 12, -128, 0, 89, 112, 91, -34};
+            final long time = System.currentTimeMillis() - 1;
+            for (int i = 0; i < 1000; i++) {
+                int errorCode = IpMemoryStoreDatabase.storeNetworkAttributes(
+                        mService.mDb,
+                        "fakeKey" + i,
+                        // Let first 100 records get expiry.
+                        i < 100 ? time : time + TimeUnit.HOURS.toMillis(i),
+                        na.build());
+                assertEquals(errorCode, Status.SUCCESS);
+
+                errorCode = IpMemoryStoreDatabase.storeBlob(
+                        mService.mDb, "fakeKey" + i, TEST_CLIENT_ID, TEST_DATA_NAME, data);
+                assertEquals(errorCode, Status.SUCCESS);
+            }
+
+            // After added 5000 records, db size is larger than fake threshold(100KB).
+            assertTrue(mService.isDbSizeOverThreshold());
+        } catch (final UnknownHostException e) {
+            fail("Insert fake data fail");
+        }
+    }
+
+    /** Wait for assigned time. */
+    private void waitForMs(long ms) {
+        try {
+            Thread.sleep(ms);
+        } catch (final InterruptedException e) {
+            fail("Thread was interrupted");
+        }
+    }
+
     @Test
     public void testNetworkAttributes() throws UnknownHostException {
         final NetworkAttributes.Builder na = new NetworkAttributes.Builder();
@@ -344,7 +413,7 @@
                                     status.isSuccess());
                             assertEquals(l2Key, key);
                             assertEquals(name, TEST_DATA_NAME);
-                            Arrays.equals(b.data, data);
+                            assertTrue(Arrays.equals(b.data, data));
                             latch.countDown();
                         })));
 
@@ -506,4 +575,64 @@
                     latch.countDown();
                 })));
     }
+
+
+    @Test
+    public void testFullMaintenance() {
+        insertFakeDataAndOverThreshold();
+
+        final InterruptMaintenance im = new InterruptMaintenance(0/* Fake JobId */);
+        // Do full maintenance and then db size should go down and meet the threshold.
+        doLatched("Maintenance unexpectedly completed successfully", latch ->
+                mService.fullMaintenance(onStatus((status) -> {
+                    assertTrue("Execute full maintenance failed: "
+                            + status.resultCode, status.isSuccess());
+                    latch.countDown();
+                }), im), LONG_TIMEOUT_MS);
+
+        // Assume that maintenance is successful, db size shall meet the threshold.
+        assertFalse(mService.isDbSizeOverThreshold());
+    }
+
+    @Test
+    public void testInterruptMaintenance() {
+        insertFakeDataAndOverThreshold();
+
+        final InterruptMaintenance im = new InterruptMaintenance(0/* Fake JobId */);
+
+        // Test interruption immediately.
+        im.setInterrupted(true);
+        // Do full maintenance and the expectation is not completed by interruption.
+        doLatched("Maintenance unexpectedly completed successfully", latch ->
+                mService.fullMaintenance(onStatus((status) -> {
+                    assertFalse(status.isSuccess());
+                    latch.countDown();
+                }), im), LONG_TIMEOUT_MS);
+
+        // Assume that no data are removed, db size shall be over the threshold.
+        assertTrue(mService.isDbSizeOverThreshold());
+
+        // Reset the flag and test interruption during maintenance.
+        im.setInterrupted(false);
+
+        final ConditionVariable latch = new ConditionVariable();
+        // Do full maintenance and the expectation is not completed by interruption.
+        mService.fullMaintenance(onStatus((status) -> {
+            assertFalse(status.isSuccess());
+            latch.open();
+        }), im);
+
+        // Give a little bit of time for maintenance to start up for realism
+        waitForMs(50);
+        // Interrupt maintenance job.
+        im.setInterrupted(true);
+
+        if (!latch.block(LONG_TIMEOUT_MS)) {
+            fail("Maintenance unexpectedly completed successfully");
+        }
+
+        // Assume that only do dropAllExpiredRecords method in previous maintenance, db size shall
+        // still be over the threshold.
+        assertTrue(mService.isDbSizeOverThreshold());
+    }
 }