diff --git a/bin/ledger/testing/data_generator.cc b/bin/ledger/testing/data_generator.cc
index e282d32..82d1b98 100644
--- a/bin/ledger/testing/data_generator.cc
+++ b/bin/ledger/testing/data_generator.cc
@@ -15,6 +15,11 @@
 #include "peridot/lib/convert/convert.h"
 
 namespace ledger {
+namespace {
+
+constexpr fxl::StringView kKeyIdSeparator = "-";
+
+}  // namespace
 
 DataGenerator::DataGenerator(rng::Random* random)
     : generator_(random->NewBitGenerator<uint64_t>()) {}
@@ -23,11 +28,11 @@
 
 std::vector<uint8_t> DataGenerator::MakeKey(int i, size_t size) {
   std::string i_str = std::to_string(i);
-  FXL_DCHECK(i_str.size() + 1 <= size);
-  auto rand_bytes = MakeValue(size - i_str.size() - 1);
+  FXL_DCHECK(i_str.size() + kKeyIdSeparator.size() <= size);
+  auto rand_bytes = MakeValue(size - i_str.size() - kKeyIdSeparator.size());
 
-  return convert::ToArray(
-      fxl::Concatenate({i_str, "-", convert::ExtendedStringView(rand_bytes)}));
+  return convert::ToArray(fxl::Concatenate(
+      {convert::ExtendedStringView(rand_bytes), kKeyIdSeparator, i_str}));
 }
 
 PageId DataGenerator::MakePageId() {
@@ -55,4 +60,12 @@
   return keys;
 }
 
+size_t DataGenerator::GetKeyId(const std::vector<uint8_t>& key) {
+  std::string key_str = convert::ToString(key);
+  size_t split_index = key_str.find_last_of(kKeyIdSeparator.ToString());
+  FXL_CHECK(split_index != std::string::npos &&
+            split_index + kKeyIdSeparator.size() < key_str.size());
+  return std::stoul(key_str.substr(split_index + kKeyIdSeparator.size()));
+}
+
 }  // namespace ledger
diff --git a/bin/ledger/testing/data_generator.h b/bin/ledger/testing/data_generator.h
index 47cbf57..8dbf326 100644
--- a/bin/ledger/testing/data_generator.h
+++ b/bin/ledger/testing/data_generator.h
@@ -22,9 +22,8 @@
 
   ~DataGenerator();
 
-  // Builds a key of the given length as "<the given int>-<random data>", so
-  // that deterministic ordering of entries can be ensured by using a different
-  // |i| value each time, but the resulting B-tree nodes are always distinct.
+  // Builds a key of the given |size| as "<random data>-<i>". The id (|i|) of
+  // the result can be retrieved by calling |GetKeyId|.
   std::vector<uint8_t> MakeKey(int i, size_t size);
 
   // Builds a random value that can be used as a page id.
@@ -35,9 +34,12 @@
 
   // Builds a vector of length |key_count| containing keys of size |key_size|,
   // |unique_key_count| of which are unique.
-  std::vector<std::vector<uint8_t>> MakeKeys(size_t key_count,
-                                                 size_t key_size,
-                                                 size_t unique_key_count);
+  std::vector<std::vector<uint8_t>> MakeKeys(size_t key_count, size_t key_size,
+                                             size_t unique_key_count);
+
+  // Returns the id of |key|. |key| is assumed to have been created by this
+  // DataGenerator, using either |MakeKey| or |MakeKeys|.
+  size_t GetKeyId(const std::vector<uint8_t>& key);
 
  private:
   std::independent_bits_engine<rng::Random::BitGenerator<uint64_t>, CHAR_BIT,
diff --git a/bin/ledger/tests/benchmark/put/put.cc b/bin/ledger/tests/benchmark/put/put.cc
index b55d54a..55847d1 100644
--- a/bin/ledger/tests/benchmark/put/put.cc
+++ b/bin/ledger/tests/benchmark/put/put.cc
@@ -162,22 +162,21 @@
         }
         page_ = std::move(page);
 
-        InitializeKeys(
-            [this](std::vector<std::vector<uint8_t>> keys) mutable {
-              if (transaction_size_ > 0) {
-                page_->StartTransaction(
-                    [this, keys = std::move(keys)](Status status) mutable {
-                      if (QuitOnError(QuitLoopClosure(), status,
-                                      "Page::StartTransaction")) {
-                        return;
-                      }
-                      TRACE_ASYNC_BEGIN("benchmark", "transaction", 0);
-                      BindWatcher(std::move(keys));
-                    });
-              } else {
-                BindWatcher(std::move(keys));
-              }
-            });
+        InitializeKeys([this](std::vector<std::vector<uint8_t>> keys) mutable {
+          if (transaction_size_ > 0) {
+            page_->StartTransaction(
+                [this, keys = std::move(keys)](Status status) mutable {
+                  if (QuitOnError(QuitLoopClosure(), status,
+                                  "Page::StartTransaction")) {
+                    return;
+                  }
+                  TRACE_ASYNC_BEGIN("benchmark", "transaction", 0);
+                  BindWatcher(std::move(keys));
+                });
+          } else {
+            BindWatcher(std::move(keys));
+          }
+        });
       });
 }
 
@@ -185,7 +184,7 @@
                             ResultState /*result_state*/,
                             OnChangeCallback callback) {
   for (auto const& change : page_change.changed_entries) {
-    size_t key_number = std::stoul(convert::ToString(change.key));
+    size_t key_number = generator_.GetKeyId(change.key);
     if (keys_to_receive_.find(key_number) != keys_to_receive_.end()) {
       TRACE_ASYNC_END("benchmark", "local_change_notification", key_number);
       keys_to_receive_.erase(key_number);
@@ -206,11 +205,11 @@
     keys_cloned.push_back(keys[i]);
     if (transaction_size_ == 0 ||
         i % transaction_size_ == transaction_size_ - 1) {
-      keys_to_receive_.insert(std::stoul(convert::ToString(keys[i])));
+      keys_to_receive_.insert(generator_.GetKeyId(keys[i]));
     }
   }
   // Last key should always be recorded so the last transaction is not lost.
-  size_t last_key_number = std::stoul(convert::ToString(keys.back()));
+  size_t last_key_number = generator_.GetKeyId(keys.back());
   keys_to_receive_.insert(last_key_number);
   if (!update_) {
     on_done(std::move(keys));
@@ -242,15 +241,14 @@
       });
 }
 
-void PutBenchmark::RunSingle(int i,
-                             std::vector<std::vector<uint8_t>> keys) {
+void PutBenchmark::RunSingle(int i, std::vector<std::vector<uint8_t>> keys) {
   if (i == entry_count_) {
     // All sent, waiting for watcher notification before shutting down.
     return;
   }
 
   fidl::VectorPtr<uint8_t> value = generator_.MakeValue(value_size_);
-  size_t key_number = std::stoul(convert::ToString(keys[i]));
+  size_t key_number = generator_.GetKeyId(keys[i]);
   if (transaction_size_ == 0) {
     TRACE_ASYNC_BEGIN("benchmark", "local_change_notification", key_number);
   }
@@ -312,8 +310,8 @@
       });
 }
 
-void PutBenchmark::CommitAndRunNext(
-    int i, size_t key_number, std::vector<std::vector<uint8_t>> keys) {
+void PutBenchmark::CommitAndRunNext(int i, size_t key_number,
+                                    std::vector<std::vector<uint8_t>> keys) {
   TRACE_ASYNC_BEGIN("benchmark", "local_change_notification", key_number);
   TRACE_ASYNC_BEGIN("benchmark", "commit", i / transaction_size_);
   page_->Commit([this, i, keys = std::move(keys)](Status status) mutable {
diff --git a/bin/ledger/tests/benchmark/sync/sync.cc b/bin/ledger/tests/benchmark/sync/sync.cc
index 7f38b34..d0cc4df 100644
--- a/bin/ledger/tests/benchmark/sync/sync.cc
+++ b/bin/ledger/tests/benchmark/sync/sync.cc
@@ -210,8 +210,7 @@
 void SyncBenchmark::OnChange(PageChange page_change, ResultState result_state,
                              OnChangeCallback callback) {
   FXL_DCHECK(!page_change.changed_entries.empty());
-  size_t i =
-      std::stoul(convert::ToString(page_change.changed_entries.at(0).key));
+  size_t i = generator_.GetKeyId(page_change.changed_entries.at(0).key);
   changed_entries_received_ += page_change.changed_entries.size();
   if (result_state == ResultState::COMPLETED ||
       result_state == ResultState::PARTIAL_STARTED) {
@@ -233,7 +232,8 @@
 
   std::vector<std::vector<uint8_t>> keys(entries_per_change_);
   for (size_t i = 0; i < entries_per_change_; i++) {
-    // Keys are distinct, but have the common prefix <i>.
+    // Keys are distinct, but they all have the same id (|change_number|), which
+    // will be used to end the trace.
     keys[i] = generator_.MakeKey(change_number, kKeySize);
   }