[storage] Introduce `store` #1327

clabby · 2025-07-27T23:59:27Z

Overview

Introduces a new store module that contains a simple, unauthenticated Store K/V DB.

patrick-ogrady · 2025-07-28T00:00:13Z

👀 👀 👀

storage/src/store/operation.rs

patrick-ogrady

My original ambition with this issue (#1206) was to actually create a totally unrelated implementation to adb (with variable-sized operations)...something like archive but "mutable" (and where each key wasn't associated with some "index").

This PR has made me second guess that original effort given how straightforward your abstraction seems to integrate into the adbs (especially because it is a "known useful" pattern rather than just something I thought may be useful).

The code you've provided looks pretty solid (I just left comments primarily around how it is presented).

Thanks for putting this up! We'll get back to you tomorrow with direction on what route we prefer 👍

storage/src/store/mod.rs

storage/src/store/base.rs

roberto-bayardo · 2025-07-28T15:21:57Z

If decoupled from ADB, we don't need to support by-index lookups, and could therefore support variable length items without the additional log structure used by adb::immutable.

I'm leaning towards keeping this "non authenticated" store independent of ADB and giving it variable-length record capability to make it more flexible?

patrick-ogrady · 2025-07-28T16:09:10Z

If decoupled from ADB, we don't need to support by-index lookups, and could therefore support variable length items without the additional log structure used by adb::immutable.

I'm leaning towards keeping this "non authenticated" store independent of ADB and giving it variable-length record capability to make it more flexible?

Agreed. Let's keep store as a standalone thing for now (at least until we get further along the adb optimization path). We should support variable length as well (you can look at archive::prunable for an example of how this is done with journal::variable and Index).

clabby · 2025-07-29T01:06:37Z

Sounds good - thanks y'all 😄

I should have some time mid-week to revisit.

clabby · 2025-08-02T20:40:00Z

Rewrote + simplified the store - now allows for variable-length values and is more separate from the adb in functionality.

patrick-ogrady

Your "historical functionality" introduced some unintended behavior (based on a smal misunderstanding of how Index works).

If you revert those, I think it should be pretty close!

Adding some sort of historical query pattern is an interesting idea (and as you are likely well-aware is commonly used to power archive state stores these days) but have typically found that to require some sort of "range query" functionality that isn't present in any of our DBs (so far 😉 ).

storage/src/store/mod.rs

clabby · 2025-08-03T02:41:52Z

Thanks @patrick-ogrady - good catch! I fooled myself on the underlying behavior of Index here with test_store_historical_access; The test only works out as-is due to using the same key, but "the "nth" version of some key is really the nth version of some super set of keys with the same prefix" (#1327 (comment)) bears its teeth when you assign a few values to a key that shares a prefix with the one used to saturate values as you suggested.

If you revert those, I think it should be pretty close!

The code for the historical retrieval + allowing the index to expand with the number of ops was added in 5be4491, and prior to that change (a3a3e55), the store does handle conflicts within the cursor correctly (as suggested in #1327 (comment).)

The downside to that version is that it does not support a form of pruning inactive operations in the log, which I attempted to give purpose to in 5be4491 by adding the option to access historical values that the key has taken on.

Would you prefer to keep it simple, and just revert to a3a3e55, or is there more functionality you'd like to see here (i.e. pruning)?

patrick-ogrady · 2025-08-03T13:41:41Z

Thanks @patrick-ogrady - good catch! I fooled myself on the underlying behavior of Index here with test_store_historical_access; The test only works out as-is due to using the same key, but "the "nth" version of some key is really the nth version of some super set of keys with the same prefix" (#1327 (comment)) bears its teeth when you assign a few values to a key that shares a prefix with the one used to saturate values as you suggested.

👍

The code for the historical retrieval + allowing the index to expand with the number of ops was added in 5be4491, and prior to that change (a3a3e55), the store does handle conflicts within the cursor correctly (as suggested in #1327 (comment)). The downside to that version is that it does not support a form of pruning inactive operations in the log, which I attempted to give purpose to in 5be4491 by adding the option to access historical values that the key has taken on. Would you prefer to keep it simple, and just revert to a3a3e55, or is there more functionality you'd like to see here (i.e. pruning)?

Like with adb::any, we should maintain an "inactivity floor" and rewrite keys to the tip of the log (reading from the base of the log at the rate new keys are added to bound the "junk" on disk):

monorepo/storage/src/adb/any/mod.rs

Lines 744 to 793 in 65ee8a7

    
               /// Raise the inactivity floor by exactly `max_steps` steps, followed by applying a commit 
        
               /// operation. Each step either advances over an inactive operation, or re-applies an active 
        
               /// operation to the tip and then advances over it. 
        
               /// 
        
               /// This method does not change the state of the db's snapshot, but it always changes the root 
        
               /// since it applies at least one operation. 
        
               pub(super) async fn raise_inactivity_floor(&mut self, max_steps: u64) -> Result<(), Error> { 
        
                   for _ in 0..max_steps { 
        
                       if self.inactivity_floor_loc == self.op_count() { 
        
                           break; 
        
                       } 
        
                       let op = self.log.read(self.inactivity_floor_loc).await?; 
        
                       self.move_op_if_active(op, self.inactivity_floor_loc) 
        
                           .await?; 
        
                       self.inactivity_floor_loc += 1; 
        
                   } 
        
                   self.apply_op(Fixed::Commit(self.inactivity_floor_loc)) 
        
                       .await?; 
        
                   Ok(()) 
        
               } 
        
               /// Prune historical operations that are > `pruning_delay` steps behind the inactivity floor. 
        
               /// This does not affect the db's root or current snapshot. 
        
               pub(super) async fn prune_inactive(&mut self) -> Result<(), Error> { 
        
                   let Some(oldest_retained_loc) = self.log.oldest_retained_pos().await? else { 
        
                       return Ok(()); 
        
                   }; 
        
                   // Calculate the target pruning position: inactivity_floor_loc - pruning_delay 
        
                   let target_prune_loc = self.inactivity_floor_loc.saturating_sub(self.pruning_delay); 
        
                   let ops_to_prune = target_prune_loc.saturating_sub(oldest_retained_loc); 
        
                   if ops_to_prune == 0 { 
        
                       return Ok(()); 
        
                   } 
        
                   debug!(ops_to_prune, target_prune_loc, "pruning inactive ops"); 
        
                   // Prune the MMR, whose pruning boundary serves as the "source of truth" for proving. 
        
                   let prune_to_pos = leaf_num_to_pos(target_prune_loc); 
        
                   self.ops 
        
                       .prune_to_pos(&mut self.hasher, prune_to_pos) 
        
                       .await?; 
        
                   // Because the log's pruning boundary will be blob-size aligned, we cannot use it as a 
        
                   // source of truth for the min provable element. 
        
                   self.log.prune(target_prune_loc).await?; 
        
                   Ok(()) 
        
               }

You may definitely feel you are duplicating a good bit of logic and (as discussed previously) I'm ok with that for this early phase. We are planning to do a "deduplication effort" once the core storage primitives are complete (and prefer keeping them un-entangled for faster experimentation).

Hope that helps!

clabby · 2025-08-04T19:48:33Z

Reverted the changes in 5be4491, and added pruning logic to the store akin to adb::any's.

storage/src/store/mod.rs

clabby

Added deletion support + fixed an issue with conflicting keys in the snapshot building process, one last todo.

storage/src/store/mod.rs

Introduces a new module in `commonware-storage` that provides an unauthenticated key-value store, supporting variable-sized values.

storage/src/store/mod.rs

patrick-ogrady

~5 minutes away from merge!

storage/src/store/mod.rs

storage/src/store/operation.rs

storage/src/store/mod.rs

patrick-ogrady · 2025-08-06T18:36:42Z

🚀 🚀 🚀

codecov · 2025-08-06T20:17:58Z

Codecov Report

❌ Patch coverage is 96.86347% with 17 lines in your changes missing coverage. Please review.
✅ Project coverage is 91.32%. Comparing base (18e6449) to head (84af2f4).
⚠️ Report is 5 commits behind head on main.

Files with missing lines	Patch %	Lines
storage/src/store/mod.rs	95.96%	17 Missing ⚠️

@@            Coverage Diff             @@
##             main    #1327      +/-   ##
==========================================
+ Coverage   91.24%   91.32%   +0.08%     
==========================================
  Files         262      265       +3     
  Lines       65310    66018     +708     
==========================================
+ Hits        59590    60291     +701     
- Misses       5720     5727       +7

Files with missing lines	Coverage Δ
storage/src/adb/any/mod.rs	`98.90% <ø> (ø)`
storage/src/adb/operation.rs	`88.06% <ø> (ø)`
storage/src/store/operation.rs	`100.00% <100.00%> (ø)`
storage/src/store/mod.rs	`95.96% <95.96%> (ø)`

... and 6 files with indirect coverage changes

Continue to review full report in Codecov by Sentry.

Legend - Click here to learn more
Δ = absolute <relative> (impact), ø = not affected, ? = missing data
Powered by Codecov. Last update 18e6449...84af2f4. Read the comment docs.

🚀 New features to boost your workflow:

❄️ Test Analytics: Detect flaky tests, report on failures, and find test suite problems.

patrick-ogrady requested a review from roberto-bayardo July 28, 2025 00:01

clabby marked this pull request as draft July 28, 2025 00:05

patrick-ogrady requested a review from danlaine July 28, 2025 00:08

clabby force-pushed the cl/store branch 2 times, most recently from e742649 to 0022902 Compare July 28, 2025 00:09

clabby commented Jul 28, 2025

View reviewed changes

storage/src/store/operation.rs Show resolved Hide resolved

clabby marked this pull request as ready for review July 28, 2025 00:11

patrick-ogrady reviewed Jul 28, 2025

View reviewed changes

clabby force-pushed the cl/store branch from b790e0a to 6567000 Compare August 2, 2025 20:31

clabby force-pushed the cl/store branch from 6567000 to 5be4491 Compare August 2, 2025 20:43

clabby requested a review from patrick-ogrady August 2, 2025 20:53

patrick-ogrady requested changes Aug 2, 2025

View reviewed changes

storage/src/store/mod.rs Outdated Show resolved Hide resolved

storage/src/store/mod.rs Outdated Show resolved Hide resolved

storage/src/store/mod.rs Outdated Show resolved Hide resolved

clabby force-pushed the cl/store branch from 5be4491 to db316e5 Compare August 4, 2025 19:42

clabby requested a review from patrick-ogrady August 4, 2025 19:47

clabby force-pushed the cl/store branch 2 times, most recently from 71ac6a6 to aa42c41 Compare August 4, 2025 19:53

patrick-ogrady reviewed Aug 4, 2025

View reviewed changes

storage/src/store/mod.rs Outdated Show resolved Hide resolved

clabby commented Aug 5, 2025

View reviewed changes

storage/src/store/mod.rs Show resolved Hide resolved

clabby added 4 commits August 5, 2025 11:01

[storage] Introduce store

42009b7

Introduces a new module in `commonware-storage` that provides an unauthenticated key-value store, supporting variable-sized values.

feat: Use secondary journal for variable journal offsets

f767025

Support pruning

781a1c3

Support deletions

ad5fecc

clabby added 2 commits August 5, 2025 11:01

Optimize snapshot building memory footprint

71e59e9

cover Operation::Delete

3b31166

clabby force-pushed the cl/store branch from 313fc88 to 3b31166 Compare August 5, 2025 15:01

clabby requested a review from patrick-ogrady August 5, 2025 15:02

clabby commented Aug 5, 2025

View reviewed changes

storage/src/store/mod.rs Outdated Show resolved Hide resolved

clean, optimize update

f1fb018

patrick-ogrady requested changes Aug 6, 2025

View reviewed changes

patrick's review

cd43a82

clabby requested a review from patrick-ogrady August 6, 2025 18:22

nit

3bb397a

patrick-ogrady previously approved these changes Aug 6, 2025

View reviewed changes

nit

27f8138

patrick-ogrady dismissed their stale review via 27f8138 August 6, 2025 18:38

patrick-ogrady previously approved these changes Aug 6, 2025

View reviewed changes

cleanup benchmark

a20de87

patrick-ogrady dismissed their stale review via a20de87 August 6, 2025 18:55

patrick-ogrady added 2 commits August 6, 2025 11:55

remove logs

908dcfc

nit

84af2f4

patrick-ogrady merged commit 1d7dc6b into commonwarexyz:main Aug 6, 2025
32 checks passed

[storage] Introduce store #1327

[storage] Introduce store #1327

Uh oh!

Conversation

clabby commented Jul 27, 2025 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Overview

Uh oh!

patrick-ogrady commented Jul 28, 2025

Uh oh!

Uh oh!

patrick-ogrady left a comment • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

roberto-bayardo commented Jul 28, 2025

Uh oh!

patrick-ogrady commented Jul 28, 2025

Uh oh!

clabby commented Jul 29, 2025

Uh oh!

clabby commented Aug 2, 2025

Uh oh!

patrick-ogrady left a comment • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

Uh oh!

clabby commented Aug 3, 2025 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

patrick-ogrady commented Aug 3, 2025

Uh oh!

clabby commented Aug 4, 2025

Uh oh!

Uh oh!

clabby left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

patrick-ogrady left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

patrick-ogrady commented Aug 6, 2025

Uh oh!

Uh oh!

codecov bot commented Aug 6, 2025

Codecov Report

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

3 participants

[storage] Introduce `store` #1327

[storage] Introduce `store` #1327

clabby commented Jul 27, 2025 •

edited

Loading

patrick-ogrady left a comment •

edited

Loading

patrick-ogrady left a comment •

edited

Loading

clabby commented Aug 3, 2025 •

edited

Loading