Expand description
A persistent index that maps sparse indices to commonware_utils::Arrays.
Ordinal is a collection of commonware_runtime::Blobs containing ordered records of fixed size. Because records are fixed size, file position corresponds directly to index. Unlike crate::journal::fixed::Journal, Ordinal supports out-of-order insertion.
§Design
Ordinal is a collection of commonware_runtime::Blobs where:
- Each record:
[V][crc32(V)]where V is an commonware_utils::Array - Index N is at file offset:
N * RECORD_SIZE - A crate::rmap::RMap tracks which indices have been written (and which are missing)
§File Organization
Records are grouped into blobs to avoid having too many files:
Blob 0: indices 0-999
Blob 1: indices 1000-1999
...§Format
Ordinal stores values in the following format:
+---+---+---+---+---+---+---+---+---+---+---+---+---+
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |10 |11 |12 |
+---+---+---+---+---+---+---+---+---+---+---+---+---+
| Value (Fixed Size) | CRC32 |
+---+---+---+---+---+---+---+---+---+---+---+---+---+§Performance Characteristics
- Writes: O(1) - direct offset calculation
- Reads: O(1) - direct offset calculation
- Has: O(1) - in-memory lookup (via crate::rmap::RMap)
- Next Gap: O(log n) - in-memory range query (via crate::rmap::RMap)
- Restart: O(n) where n is the number of existing records (to rebuild crate::rmap::RMap)
§Atomicity
Ordinal eagerly writes all new data to commonware_runtime::Blobs. New data, however, is not synced until Ordinal::sync is called. As a result, data is not guaranteed to be atomically persisted (i.e. shutdown before Ordinal::sync may lead to some writes being lost).
If you want atomicity for sparse writes, pair commonware_utils::BitVec and crate::metadata::Metadata with Ordinal (use bits to indicate which items have been atomically written).
§Recovery
On restart, Ordinal validates all records using their CRC32 and rebuilds the in-memory crate::rmap::RMap. Invalid records (corrupted or empty) are excluded from the rebuilt index.
§Example
use commonware_runtime::{Spawner, Runner, deterministic};
use commonware_storage::ordinal::{Ordinal, Config};
use commonware_utils::{sequence::FixedBytes, NZUsize, NZU64};
let executor = deterministic::Runner::default();
executor.start(|context| async move {
// Create a store for 32-byte values
let cfg = Config {
partition: "ordinal_store".into(),
items_per_blob: NZU64!(10000),
write_buffer: NZUsize!(4096),
replay_buffer: NZUsize!(1024 * 1024),
};
let mut store = Ordinal::<_, FixedBytes<32>>::init(context, cfg).await.unwrap();
// Put values at specific indices
let value1 = FixedBytes::new([1u8; 32]);
let value2 = FixedBytes::new([2u8; 32]);
store.put(0, value1).await.unwrap();
store.put(5, value2).await.unwrap();
// Sync to disk
store.sync().await.unwrap();
// Check for gaps
let (current_end, next_start) = store.next_gap(0);
assert_eq!(current_end, Some(0));
assert_eq!(next_start, Some(5));
// Close the store
store.close().await.unwrap();
});