Expand description
An immutable key-value store optimized for minimal memory usage and write amplification.
Freezer is a key-value store designed for permanent storage where data is written once and never modified. Meant for resource-constrained environments, Freezer exclusively employs disk-resident data structures to serve queries and avoids ever rewriting (i.e. compacting) inserted data.
As a byproduct of the mechanisms used to satisfy these constraints, Freezer consistently provides low latency access to recently added data (regardless of how much data has been stored) at the expense of a logarithmic increase in latency for old data (increasing with the number of items stored).
§Format
The Freezer uses a three-level architecture:
- An extendible hash table (written in a single commonware_runtime::Blob) that maps keys to locations
- A key index journal (crate::journal::segmented::fixed) that stores keys and collision chain pointers
- A value journal (crate::journal::segmented::glob) that stores the actual values
These journals are combined via crate::journal::segmented::oversized, which coordinates crash recovery between them.
+-----------------------------------------------------------------+
| Hash Table |
| +---------+---------+---------+---------+---------+---------+ |
| | Entry 0 | Entry 1 | Entry 2 | Entry 3 | Entry 4 | ... | |
| +----+----+----+----+----+----+----+----+----+----+---------+ |
+-------|---------|---------|---------|---------|---------|-------+
| | | | | |
v v v v v v
+-----------------------------------------------------------------+
| Key Index Journal |
| Section 0: [Entry 0][Entry 1][Entry 2]... |
| Section 1: [Entry 10][Entry 11][Entry 12]... |
| Section N: [Entry 100][Entry 101][Entry 102]... |
+-------|---------|---------|---------|---------|---------|-------+
| | | | | |
v v v v v v
+-----------------------------------------------------------------+
| Value Journal |
| Section 0: [Value 0][Value 1][Value 2]... |
| Section 1: [Value 10][Value 11][Value 12]... |
| Section N: [Value 100][Value 101][Value 102]... |
+-----------------------------------------------------------------+The table uses two fixed-size slots per entry to ensure consistency during updates. Each slot contains an epoch number that monotonically increases with each sync operation. During reads, the slot with the higher epoch is selected (provided it’s not greater than the last committed epoch), ensuring consistency even if the system crashed during a write.
+-------------------------------------+
| Hash Table Entry |
+-------------------------------------+
| Slot 0 | Slot 1 |
+-----------------+-------------------+
| epoch: u64 | epoch: u64 |
| section: u64 | section: u64 |
| offset: u32 | offset: u32 |
| added: u8 | added: u8 |
+-----------------+-------------------+
| CRC32: u32 | CRC32: u32 |
+-----------------+-------------------+The key index journal stores fixed-size entries containing a key, a pointer to the value in the value journal, and an optional pointer to the next entry in the collision chain (for keys that hash to the same table index).
+-------------------------------------+
| Key Index Entry |
+-------------------------------------+
| Key: Array |
| Value Offset: u64 |
| Value Size: u32 |
| Next: Option<(u64, u32)> |
+-------------------------------------+The value journal stores the actual encoded values at the offsets referenced by the key index entries.
§Traversing Conflicts
When multiple keys hash to the same table index, they form a linked list within the key index journal. Each key index entry points to its value in the value journal:
Hash Table:
[Index 42] +-------------------+
| section: 2 |
| offset: 768 |
+---------+---------+
|
Key Index Journal: v
[Section 2] +-----------------------+
| Key: "foo" |
| ValOff: 100 |
| ValSize: 20 |
| Next: (1, 512) -------+---+
+-----------------------+ |
v
[Section 1] +-----------------------+
| Key: "bar" |
| ValOff: 50 |
| ValSize: 20 |
| Next: (0, 256) -------+---+
+-----------------------+ |
v
[Section 0] +-----------------------+
| Key: "baz" |
| ValOff: 0 |
| ValSize: 20 |
| Next: None |
+-----------------------+
Value Journal:
[Section 0] [Value: 126 @ offset 0 ]
[Section 1] [Value: 84 @ offset 50]
[Section 2] [Value: 42 @ offset 100]New entries are prepended to the chain, becoming the new head. During lookup, the chain
is traversed until a matching key is found. The added field in the table entry tracks
insertions since the last resize, triggering table growth when 50% of entries have had
table_resize_frequency items added (since the last resize).
§Extendible Hashing
The Freezer uses bit-based indexing to grow the on-disk hash table without rehashing existing entries:
Initial state (table_size=4, using 2 bits of hash):
Hash: 0b...00 -> Index 0
Hash: 0b...01 -> Index 1
Hash: 0b...10 -> Index 2
Hash: 0b...11 -> Index 3
After resize (table_size=8, using 3 bits of hash):
Hash: 0b...000 -> Index 0 -+
... |
Hash: 0b...100 -> Index 4 -+- Both map to old Index 0
Hash: 0b...001 -> Index 1 -+
... |
Hash: 0b...101 -> Index 5 -+- Both map to old Index 1When the table doubles in size:
- Each entry at index
isplits into two entries:iandi + old_size - The existing chain head is copied to both locations with
added=0 - Future insertions will naturally distribute between the two entries based on their hash
This approach ensures that entries inserted before a resize remain discoverable after the resize, as the lookup algorithm checks the appropriate entry based on the current table size. As more and more items are added (and resizes occur), the latency for fetching old data will increase logarithmically (with the number of items stored).
To prevent a “stall” during a single resize, the table is resized incrementally across multiple sync calls.
Each sync will process up to table_resize_chunk_size entries until the resize is complete. If there is
an ongoing resize when closing the Freezer, the resize will be completed before closing.
§Example
use commonware_runtime::{Spawner, Runner, deterministic, buffer::paged::CacheRef};
use commonware_storage::freezer::{Freezer, Config, Identifier};
use commonware_utils::{sequence::FixedBytes, NZUsize, NZU16};
let executor = deterministic::Runner::default();
executor.start(|context| async move {
// Create a freezer
let cfg = Config {
key_partition: "freezer-key-index".into(),
key_write_buffer: NZUsize!(1024 * 1024), // 1MB
key_page_cache: CacheRef::from_pooler(&context, NZU16!(1024), NZUsize!(10)),
value_partition: "freezer-value-journal".into(),
value_compression: Some(3),
value_write_buffer: NZUsize!(1024 * 1024), // 1MB
value_target_size: 100 * 1024 * 1024, // 100MB
table_partition: "freezer-table".into(),
table_initial_size: 65_536, // ~3MB initial table size
table_resize_frequency: 4, // Force resize once 4 writes to the same entry occur
table_resize_chunk_size: 16_384, // ~1MB of table entries rewritten per sync
table_replay_buffer: NZUsize!(1024 * 1024), // 1MB
codec_config: (),
};
let mut freezer = Freezer::<_, FixedBytes<32>, i32>::init(context, cfg).await.unwrap();
// Put a key-value pair
let key = FixedBytes::new([1u8; 32]);
freezer.put(key.clone(), 42).await.unwrap();
// Sync to disk
freezer.sync().await.unwrap();
// Get the value
let value = freezer.get(Identifier::Key(&key)).await.unwrap().unwrap();
assert_eq!(value, 42);
// Close the freezer
freezer.close().await.unwrap();
});Structs§
- Checkpoint
- Marker of Freezer progress.
- Config
- Configuration for Freezer.
- Cursor
- Location of an item in the Freezer.
- Freezer
- Implementation of Freezer.
Enums§
- Error
- Errors that can occur when interacting with the Freezer.
- Identifier
- Subject of a Freezer::get operation.