Bug 1286798 - Part 38: Cache items in an array; r=asuth draft
authorJan Varga <jan.varga@gmail.com>
Wed, 24 Oct 2018 06:59:07 +0200
changeset 481716 91604e07a92350fdb5898fcabbcafa15bf97a5f5
parent 481715 88337fbca5231155430229d21838990be3718ea5
child 481717 e6484c48d5ae8152fbb7b183c9f6e6a349c19b3a
push id10
push userbugmail@asutherland.org
push dateSun, 18 Nov 2018 18:57:42 +0000
reviewersasuth
bugs1286798
milestone65.0a1
Bug 1286798 - Part 38: Cache items in an array; r=asuth Items are now cached also in an array (besides a hashtable). This gives us very fast snapshot initizilization for datastores that fit into the prefill limit. String buffers are reference counted, so memory footprint is only affected by the size of nsString. This patch also introduces a WriteOptimizer which is an abstraction for collecting, coalescing and applying write operations.
dom/localstorage/ActorsParent.cpp
--- a/dom/localstorage/ActorsParent.cpp
+++ b/dom/localstorage/ActorsParent.cpp
@@ -864,16 +864,138 @@ DetachShadowDatabase(mozIStorageConnecti
 
   return NS_OK;
 }
 
 /*******************************************************************************
  * Non-actor class declarations
  ******************************************************************************/
 
+class WriteOptimizer final
+{
+  class WriteInfo;
+  class AddItemInfo;
+  class UpdateItemInfo;
+  class RemoveItemInfo;
+
+  nsClassHashtable<nsStringHashKey, WriteInfo> mWriteInfos;
+  bool mClearedWriteInfos;
+
+public:
+  WriteOptimizer()
+    : mClearedWriteInfos(false)
+  { }
+
+  void
+  AddItem(const nsString& aKey,
+          const nsString& aValue);
+
+  void
+  UpdateItem(const nsString& aKey,
+             const nsString& aValue);
+
+  void
+  RemoveItem(const nsString& aKey);
+
+  void
+  Clear();
+
+  void
+  ApplyWrites(nsTArray<LSItemInfo>& aOrderedItems);
+};
+
+class WriteOptimizer::WriteInfo
+{
+public:
+  enum Type {
+    AddItem = 0,
+    UpdateItem,
+    RemoveItem
+  };
+
+  virtual Type
+  GetType() = 0;
+
+  virtual ~WriteInfo() = default;
+};
+
+class WriteOptimizer::AddItemInfo
+  : public WriteInfo
+{
+  nsString mKey;
+  nsString mValue;
+
+public:
+  AddItemInfo(const nsAString& aKey,
+              const nsAString& aValue)
+    : mKey(aKey)
+    , mValue(aValue)
+  { }
+
+  const nsAString&
+  GetKey() const
+  {
+    return mKey;
+  }
+
+  const nsAString&
+  GetValue() const
+  {
+    return mValue;
+  }
+
+private:
+  Type
+  GetType() override
+  {
+    return AddItem;
+  }
+};
+
+class WriteOptimizer::UpdateItemInfo final
+  : public AddItemInfo
+{
+public:
+  UpdateItemInfo(const nsAString& aKey,
+                 const nsAString& aValue)
+    : AddItemInfo(aKey, aValue)
+  { }
+
+private:
+  Type
+  GetType() override
+  {
+    return UpdateItem;
+  }
+};
+
+class WriteOptimizer::RemoveItemInfo final
+  : public WriteInfo
+{
+  nsString mKey;
+
+public:
+  explicit RemoveItemInfo(const nsAString& aKey)
+    : mKey(aKey)
+  { }
+
+  const nsAString&
+  GetKey() const
+  {
+    return mKey;
+  }
+
+private:
+  Type
+  GetType() override
+  {
+    return RemoveItem;
+  }
+};
+
 class DatastoreOperationBase
   : public Runnable
 {
   nsCOMPtr<nsIEventTarget> mOwningEventTarget;
   nsresult mResultCode;
   Atomic<bool> mMayProceedOnNonOwningThread;
   bool mMayProceed;
 
@@ -1273,41 +1395,42 @@ class Datastore final
   RefPtr<Connection> mConnection;
   RefPtr<QuotaObject> mQuotaObject;
   nsCOMPtr<nsIRunnable> mCompleteCallback;
   nsTHashtable<nsPtrHashKey<PrepareDatastoreOp>> mPrepareDatastoreOps;
   nsTHashtable<nsPtrHashKey<PreparedDatastore>> mPreparedDatastores;
   nsTHashtable<nsPtrHashKey<Database>> mDatabases;
   nsTHashtable<nsPtrHashKey<Database>> mActiveDatabases;
   nsDataHashtable<nsStringHashKey, nsString> mValues;
-  nsDataHashtable<nsStringHashKey, uint32_t> mUpdateBatchRemovals;
-  nsTArray<nsString> mUpdateBatchAppends;
-  nsTArray<nsString> mKeys;
+  nsTArray<LSItemInfo> mOrderedItems;
   nsTArray<int64_t> mPendingUsageDeltas;
+  WriteOptimizer mWriteOptimizer;
   const nsCString mOrigin;
   const uint32_t mPrivateBrowsingId;
   int64_t mUsage;
   int64_t mUpdateBatchUsage;
   int64_t mSizeOfKeys;
+  int64_t mSizeOfItems;
   bool mClosed;
 #ifdef DEBUG
   bool mInUpdateBatch;
 #endif
 
 public:
   // Created by PrepareDatastoreOp.
   Datastore(const nsACString& aOrigin,
             uint32_t aPrivateBrowsingId,
             int64_t aUsage,
             int64_t aSizeOfKeys,
+            int64_t aSizeOfItems,
             already_AddRefed<DirectoryLock>&& aDirectoryLock,
             already_AddRefed<Connection>&& aConnection,
             already_AddRefed<QuotaObject>&& aQuotaObject,
             nsDataHashtable<nsStringHashKey, nsString>& aValues,
-            nsTArray<nsString>& aKeys);
+            nsTArray<LSItemInfo>& aOrderedItems);
 
   const nsCString&
   Origin() const
   {
     return mOrigin;
   }
 
   uint32_t
@@ -1925,26 +2048,27 @@ class PrepareDatastoreOp
   nsCOMPtr<nsIEventTarget> mMainEventTarget;
   RefPtr<PrepareDatastoreOp> mDelayedOp;
   RefPtr<DirectoryLock> mDirectoryLock;
   RefPtr<Connection> mConnection;
   RefPtr<Datastore> mDatastore;
   nsAutoPtr<ArchivedOriginInfo> mArchivedOriginInfo;
   LoadDataOp* mLoadDataOp;
   nsDataHashtable<nsStringHashKey, nsString> mValues;
-  nsTArray<nsString> mKeys;
+  nsTArray<LSItemInfo> mOrderedItems;
   const LSRequestPrepareDatastoreParams mParams;
   nsCString mSuffix;
   nsCString mGroup;
   nsCString mMainThreadOrigin;
   nsCString mOrigin;
   nsString mDatabaseFilePath;
   uint32_t mPrivateBrowsingId;
   int64_t mUsage;
   int64_t mSizeOfKeys;
+  int64_t mSizeOfItems;
   NestedState mNestedState;
   bool mDatabaseNotAvailable;
   bool mRequestedDirectoryLock;
   bool mInvalidated;
 
 #ifdef DEBUG
   int64_t mDEBUGUsage;
 #endif
@@ -2877,16 +3001,132 @@ CreateQuotaClient()
 
   RefPtr<QuotaClient> client = new QuotaClient();
   return client.forget();
 }
 
 } // namespace localstorage
 
 /*******************************************************************************
+ * WriteOptimizer
+ ******************************************************************************/
+
+void
+WriteOptimizer::AddItem(const nsString& aKey,
+                        const nsString& aValue)
+{
+  AssertIsOnBackgroundThread();
+
+  WriteInfo* existingWriteInfo;
+  nsAutoPtr<WriteInfo> newWriteInfo;
+  if (mWriteInfos.Get(aKey, &existingWriteInfo) &&
+      existingWriteInfo->GetType() == WriteInfo::RemoveItem) {
+    newWriteInfo = new UpdateItemInfo(aKey, aValue);
+  } else {
+    newWriteInfo = new AddItemInfo(aKey, aValue);
+  }
+  mWriteInfos.Put(aKey, newWriteInfo.forget());
+}
+
+void
+WriteOptimizer::UpdateItem(const nsString& aKey,
+                           const nsString& aValue)
+{
+  AssertIsOnBackgroundThread();
+
+  WriteInfo* existingWriteInfo;
+  nsAutoPtr<WriteInfo> newWriteInfo;
+  if (mWriteInfos.Get(aKey, &existingWriteInfo) &&
+      existingWriteInfo->GetType() == WriteInfo::AddItem) {
+    newWriteInfo = new AddItemInfo(aKey, aValue);
+  } else {
+    newWriteInfo = new UpdateItemInfo(aKey, aValue);
+  }
+  mWriteInfos.Put(aKey, newWriteInfo.forget());
+}
+
+void
+WriteOptimizer::RemoveItem(const nsString& aKey)
+{
+  AssertIsOnBackgroundThread();
+
+  WriteInfo* existingWriteInfo;
+  if (mWriteInfos.Get(aKey, &existingWriteInfo) &&
+      existingWriteInfo->GetType() == WriteInfo::AddItem) {
+    mWriteInfos.Remove(aKey);
+    return;
+  }
+
+  nsAutoPtr<WriteInfo> newWriteInfo(new RemoveItemInfo(aKey));
+  mWriteInfos.Put(aKey, newWriteInfo.forget());
+}
+
+void
+WriteOptimizer::Clear()
+{
+  AssertIsOnBackgroundThread();
+
+  mWriteInfos.Clear();
+  mClearedWriteInfos = true;
+}
+
+void
+WriteOptimizer::ApplyWrites(nsTArray<LSItemInfo>& aOrderedItems)
+{
+  if (mClearedWriteInfos) {
+    aOrderedItems.Clear();
+    mClearedWriteInfos = false;
+  }
+
+  for (int32_t index = aOrderedItems.Length() - 1;
+       index >= 0;
+       index--) {
+    LSItemInfo& item = aOrderedItems[index];
+
+    if (auto entry = mWriteInfos.Lookup(item.key())) {
+      WriteInfo* writeInfo = entry.Data();
+
+      switch (writeInfo->GetType()) {
+        case WriteInfo::RemoveItem:
+          aOrderedItems.RemoveElementAt(index);
+          entry.Remove();
+          break;
+
+        case WriteInfo::UpdateItem: {
+          auto updateItemInfo = static_cast<UpdateItemInfo*>(writeInfo);
+          item.value() = updateItemInfo->GetValue();
+          entry.Remove();
+          break;
+        }
+
+        case WriteInfo::AddItem:
+          break;
+
+        default:
+          MOZ_CRASH("Bad type!");
+      }
+    }
+  }
+
+  for (auto iter = mWriteInfos.ConstIter(); !iter.Done(); iter.Next()) {
+    WriteInfo* writeInfo = iter.Data();
+
+    MOZ_ASSERT(writeInfo->GetType() == WriteInfo::AddItem);
+
+    auto addItemInfo = static_cast<AddItemInfo*>(writeInfo);
+
+    LSItemInfo* itemInfo = aOrderedItems.AppendElement();
+    itemInfo->key() = addItemInfo->GetKey();
+    itemInfo->value() = addItemInfo->GetValue();
+  }
+
+  mWriteInfos.Clear();
+}
+
+/*******************************************************************************
  * DatastoreOperationBase
  ******************************************************************************/
 
 /*******************************************************************************
  * ConnectionDatastoreOperationBase
  ******************************************************************************/
 
 ConnectionDatastoreOperationBase::ConnectionDatastoreOperationBase(
@@ -3526,38 +3766,40 @@ ConnectionThread::Shutdown()
 /*******************************************************************************
  * Datastore
  ******************************************************************************/
 
 Datastore::Datastore(const nsACString& aOrigin,
                      uint32_t aPrivateBrowsingId,
                      int64_t aUsage,
                      int64_t aSizeOfKeys,
+                     int64_t aSizeOfItems,
                      already_AddRefed<DirectoryLock>&& aDirectoryLock,
                      already_AddRefed<Connection>&& aConnection,
                      already_AddRefed<QuotaObject>&& aQuotaObject,
                      nsDataHashtable<nsStringHashKey, nsString>& aValues,
-                     nsTArray<nsString>& aKeys)
+                     nsTArray<LSItemInfo>& aOrderedItems)
   : mDirectoryLock(std::move(aDirectoryLock))
   , mConnection(std::move(aConnection))
   , mQuotaObject(std::move(aQuotaObject))
   , mOrigin(aOrigin)
   , mPrivateBrowsingId(aPrivateBrowsingId)
   , mUsage(aUsage)
   , mUpdateBatchUsage(-1)
   , mSizeOfKeys(aSizeOfKeys)
+  , mSizeOfItems(aSizeOfItems)
   , mClosed(false)
 #ifdef DEBUG
   , mInUpdateBatch(false)
 #endif
 {
   AssertIsOnBackgroundThread();
 
   mValues.SwapElements(aValues);
-  mKeys.SwapElements(aKeys);
+  mOrderedItems.SwapElements(aOrderedItems);
 }
 
 Datastore::~Datastore()
 {
   AssertIsOnBackgroundThread();
   MOZ_ASSERT(mClosed);
 }
 
@@ -3753,53 +3995,57 @@ Datastore::GetSnapshotInitInfo(nsTHashta
                                nsTArray<LSItemInfo>& aItemInfos,
                                uint32_t& aTotalLength,
                                int64_t& aInitialUsage,
                                int64_t& aPeakUsage,
                                LSSnapshot::LoadState& aLoadState)
 {
   AssertIsOnBackgroundThread();
   MOZ_ASSERT(!mClosed);
+  MOZ_ASSERT(!mInUpdateBatch);
 
 #ifdef DEBUG
   int64_t sizeOfKeys = 0;
-  for (auto key : mKeys) {
-    sizeOfKeys += static_cast<int64_t>(key.Length());
+  int64_t sizeOfItems = 0;
+  for (auto item : mOrderedItems) {
+    int64_t sizeOfKey = static_cast<int64_t>(item.key().Length());
+    sizeOfKeys += sizeOfKey;
+    sizeOfItems += sizeOfKey + static_cast<int64_t>(item.value().Length());
   }
   MOZ_ASSERT(mSizeOfKeys == sizeOfKeys);
+  MOZ_ASSERT(mSizeOfItems == sizeOfItems);
 #endif
 
   int64_t size = 0;
   if (mSizeOfKeys <= gSnapshotPrefill) {
-    nsString value;
-    for (auto key : mKeys) {
-      if (!value.IsVoid()) {
-        DebugOnly<bool> hasValue = mValues.Get(key, &value);
-        MOZ_ASSERT(hasValue);
-
-        size += static_cast<int64_t>(key.Length()) +
-                static_cast<int64_t>(value.Length());
-
-        if (size > gSnapshotPrefill) {
-          value.SetIsVoid(true);
-        } else {
-          aLoadedItems.PutEntry(key);
+    if (mSizeOfItems <= gSnapshotPrefill) {
+      aItemInfos.AppendElements(mOrderedItems);
+      aLoadState = LSSnapshot::LoadState::AllOrderedItems;
+    } else {
+      nsString value;
+      for (auto item : mOrderedItems) {
+        if (!value.IsVoid()) {
+          value = item.value();
+
+          size += static_cast<int64_t>(item.key().Length()) +
+                  static_cast<int64_t>(value.Length());
+
+          if (size <= gSnapshotPrefill) {
+            aLoadedItems.PutEntry(item.key());
+          } else {
+            value.SetIsVoid(true);
+          }
         }
+
+        LSItemInfo* itemInfo = aItemInfos.AppendElement();
+        itemInfo->key() = item.key();
+        itemInfo->value() = value;
       }
 
-      LSItemInfo* itemInfo = aItemInfos.AppendElement();
-      itemInfo->key() = key;
-      itemInfo->value() = value;
-    }
-
-    if (value.IsVoid()) {
       aLoadState = LSSnapshot::LoadState::AllOrderedKeys;
-    } else {
-      aLoadedItems.Clear();
-      aLoadState = LSSnapshot::LoadState::AllOrderedItems;
     }
   } else {
     for (auto iter = mValues.ConstIter(); !iter.Done(); iter.Next()) {
       const nsAString& key = iter.Key();
       const nsString& value = iter.Data();
 
       size += static_cast<int64_t>(key.Length()) +
               static_cast<int64_t>(value.Length());
@@ -3810,17 +4056,17 @@ Datastore::GetSnapshotInitInfo(nsTHashta
 
       aLoadedItems.PutEntry(key);
 
       LSItemInfo* itemInfo = aItemInfos.AppendElement();
       itemInfo->key() = iter.Key();
       itemInfo->value() = iter.Data();
     }
 
-    MOZ_ASSERT(aItemInfos.Length() < mKeys.Length());
+    MOZ_ASSERT(aItemInfos.Length() < mOrderedItems.Length());
     aLoadState = LSSnapshot::LoadState::Partial;
   }
 
   aTotalLength = mValues.Count();
 
   aInitialUsage = mUsage;
   aPeakUsage = aInitialUsage;
 }
@@ -3837,17 +4083,19 @@ Datastore::GetItem(const nsString& aKey,
 }
 
 void
 Datastore::GetKeys(nsTArray<nsString>& aKeys) const
 {
   AssertIsOnBackgroundThread();
   MOZ_ASSERT(!mClosed);
 
-  aKeys.AppendElements(mKeys);
+  for (auto item : mOrderedItems) {
+    aKeys.AppendElement(item.key());
+  }
 }
 
 void
 Datastore::SetItem(Database* aDatabase,
                    const nsString& aDocumentURI,
                    const nsString& aKey,
                    const nsString& aOldValue,
                    const nsString& aValue)
@@ -3863,25 +4111,34 @@ Datastore::SetItem(Database* aDatabase,
   if (oldValue != aValue || oldValue.IsVoid() != aValue.IsVoid()) {
     bool isNewItem = oldValue.IsVoid();
 
     NotifySnapshots(aDatabase, aKey, oldValue, /* affectsOrder */ isNewItem);
 
     mValues.Put(aKey, aValue);
 
     if (isNewItem) {
-      mUpdateBatchAppends.AppendElement(aKey);
-
-      mUpdateBatchUsage += static_cast<int64_t>(aKey.Length()) +
-                           static_cast<int64_t>(aValue.Length());
-
-      mSizeOfKeys += static_cast<int64_t>(aKey.Length());
+      mWriteOptimizer.AddItem(aKey, aValue);
+
+      int64_t sizeOfKey = static_cast<int64_t>(aKey.Length());
+      int64_t sizeOfItem = sizeOfKey + static_cast<int64_t>(aValue.Length());
+
+      mUpdateBatchUsage += sizeOfItem;
+
+      mSizeOfKeys += sizeOfKey;
+      mSizeOfItems += sizeOfItem;
     } else {
-      mUpdateBatchUsage += static_cast<int64_t>(aValue.Length()) -
-                           static_cast<int64_t>(oldValue.Length());
+      mWriteOptimizer.UpdateItem(aKey, aValue);
+
+      int64_t delta = static_cast<int64_t>(aValue.Length()) -
+                      static_cast<int64_t>(oldValue.Length());
+
+      mUpdateBatchUsage += delta;
+
+      mSizeOfItems += delta;
     }
 
     if (IsPersistent()) {
       mConnection->SetItem(aKey, aValue);
     }
   }
 
   NotifyObservers(aDatabase, aDocumentURI, aKey, aOldValue, aValue);
@@ -3901,27 +4158,25 @@ Datastore::RemoveItem(Database* aDatabas
   nsString oldValue;
   GetItem(aKey, oldValue);
 
   if (!oldValue.IsVoid()) {
     NotifySnapshots(aDatabase, aKey, oldValue, /* aAffectsOrder */ true);
 
     mValues.Remove(aKey);
 
-    auto entry = mUpdateBatchRemovals.LookupForAdd(aKey);
-    if (entry) {
-      entry.Data()++;
-    } else {
-      entry.OrInsert([]() { return 1; });
-    }
-
-    mUpdateBatchUsage -= (static_cast<int64_t>(aKey.Length()) +
-                          static_cast<int64_t>(oldValue.Length()));
-
-    mSizeOfKeys -= static_cast<int64_t>(aKey.Length());
+    mWriteOptimizer.RemoveItem(aKey);
+
+    int64_t sizeOfKey = static_cast<int64_t>(aKey.Length());
+    int64_t sizeOfItem = sizeOfKey + static_cast<int64_t>(oldValue.Length());
+
+    mUpdateBatchUsage -= sizeOfItem;
+
+    mSizeOfKeys -= sizeOfKey;
+    mSizeOfItems -= sizeOfItem;
 
     if (IsPersistent()) {
       mConnection->RemoveItem(aKey);
     }
   }
 
   NotifyObservers(aDatabase, aDocumentURI, aKey, aOldValue, VoidString());
 }
@@ -3944,24 +4199,22 @@ Datastore::Clear(Database* aDatabase,
       updateBatchUsage -= (static_cast<int64_t>(key.Length()) +
                            static_cast<int64_t>(value.Length()));
 
       NotifySnapshots(aDatabase, key, value, /* aAffectsOrder */ true);
     }
 
     mValues.Clear();
 
-    mUpdateBatchRemovals.Clear();
-    mUpdateBatchAppends.Clear();
-
-    mKeys.Clear();
+    mWriteOptimizer.Clear();
 
     mUpdateBatchUsage = updateBatchUsage;
 
     mSizeOfKeys = 0;
+    mSizeOfItems = 0;
 
     if (IsPersistent()) {
       mConnection->Clear();
     }
   }
 
   NotifyObservers(aDatabase,
                   aDocumentURI,
@@ -3978,19 +4231,20 @@ Datastore::PrivateBrowsingClear()
   MOZ_ASSERT(!mClosed);
 
   if (mValues.Count()) {
     DebugOnly<bool> ok = UpdateUsage(-mUsage);
     MOZ_ASSERT(ok);
 
     mValues.Clear();
 
-    mKeys.Clear();
+    mOrderedItems.Clear();
 
     mSizeOfKeys = 0;
+    mSizeOfItems = 0;
   }
 }
 
 void
 Datastore::BeginUpdateBatch(int64_t aSnapshotInitialUsage)
 {
   AssertIsOnBackgroundThread();
   MOZ_ASSERT(aSnapshotInitialUsage >= 0);
@@ -4012,36 +4266,17 @@ Datastore::BeginUpdateBatch(int64_t aSna
 void
 Datastore::EndUpdateBatch(int64_t aSnapshotPeakUsage)
 {
   AssertIsOnBackgroundThread();
   MOZ_ASSERT(aSnapshotPeakUsage >= 0);
   MOZ_ASSERT(!mClosed);
   MOZ_ASSERT(mInUpdateBatch);
 
-  if (mUpdateBatchAppends.Length()) {
-    mKeys.AppendElements(std::move(mUpdateBatchAppends));
-  }
-
-  if (mUpdateBatchRemovals.Count()) {
-    RefPtr<Datastore> self = this;
-
-    mKeys.RemoveElementsBy([self](const nsString& aKey) {
-      if (auto entry = self->mUpdateBatchRemovals.Lookup(aKey)) {
-        if (--entry.Data() == 0) {
-          entry.Remove();
-        }
-        return true;
-      }
-      return false;
-    });
-  }
-
-  MOZ_ASSERT(mUpdateBatchAppends.Length() == 0);
-  MOZ_ASSERT(mUpdateBatchRemovals.Count() == 0);
+  mWriteOptimizer.ApplyWrites(mOrderedItems);
 
   int64_t delta = mUpdateBatchUsage - aSnapshotPeakUsage;
 
   if (mActiveDatabases.Count()) {
     // We can't apply deltas while other databases are still active.
     // The final delta must be zero or negative, but individual deltas can be
     // positive. A positive delta can't be applied asynchronously since there's
     // no way to fire the quota exceeded error event.
@@ -5071,16 +5306,17 @@ PrepareDatastoreOp::PrepareDatastoreOp(n
                                        const LSRequestParams& aParams)
   : LSRequestBase(aMainEventTarget)
   , mMainEventTarget(aMainEventTarget)
   , mLoadDataOp(nullptr)
   , mParams(aParams.get_LSRequestPrepareDatastoreParams())
   , mPrivateBrowsingId(0)
   , mUsage(0)
   , mSizeOfKeys(0)
+  , mSizeOfItems(0)
   , mNestedState(NestedState::BeforeNesting)
   , mDatabaseNotAvailable(false)
   , mRequestedDirectoryLock(false)
   , mInvalidated(false)
 #ifdef DEBUG
   , mDEBUGUsage(0)
 #endif
 {
@@ -5882,21 +6118,22 @@ PrepareDatastoreOp::GetResponse(LSReques
       quotaObject = GetQuotaObject();
       MOZ_ASSERT(quotaObject);
     }
 
     mDatastore = new Datastore(mOrigin,
                                mPrivateBrowsingId,
                                mUsage,
                                mSizeOfKeys,
+                               mSizeOfItems,
                                mDirectoryLock.forget(),
                                mConnection.forget(),
                                quotaObject.forget(),
                                mValues,
-                               mKeys);
+                               mOrderedItems);
 
     mDatastore->NoteLivePrepareDatastoreOp(this);
 
     if (!gDatastores) {
       gDatastores = new DatastoreHashtable();
     }
 
     MOZ_ASSERT(!gDatastores->Get(mOrigin));
@@ -6096,18 +6333,21 @@ LoadDataOp::DoDatastoreWork()
 
     nsString value;
     rv = stmt->GetString(1, value);
     if (NS_WARN_IF(NS_FAILED(rv))) {
       return rv;
     }
 
     mPrepareDatastoreOp->mValues.Put(key, value);
-    mPrepareDatastoreOp->mKeys.AppendElement(key);
+    auto item = mPrepareDatastoreOp->mOrderedItems.AppendElement();
+    item->key() = key;
+    item->value() = value;
     mPrepareDatastoreOp->mSizeOfKeys += key.Length();
+    mPrepareDatastoreOp->mSizeOfItems += key.Length() + value.Length();
 #ifdef DEBUG
     mPrepareDatastoreOp->mDEBUGUsage += key.Length() + value.Length();
 #endif
   }
   if (NS_WARN_IF(NS_FAILED(rv))) {
     return rv;
   }