pub struct SkipList<K: Eq + Hash, V> { /* private fields */ }Expand description
A concurrent, multi-version, transactional skiplist.
SkipList is the core data structure that stores key-value pairs. It supports
highly concurrent reads and writes using Multi-Version Concurrency Control (MVCC)
and Serializable Snapshot Isolation (SSI).
Implementations§
Source§impl<K, V> SkipList<K, V>
impl<K, V> SkipList<K, V>
Sourcepub async fn vacuum(&self) -> Result<(usize, usize), ()>
pub async fn vacuum(&self) -> Result<(usize, usize), ()>
Scans the database and removes dead data versions to reclaim space.
This function performs two main tasks:
-
Version Pruning: It iterates through every key’s version chain and removes any version that is considered “dead”. A version is dead if it was expired by a transaction that has since committed, and that transaction is older than any currently active transaction (i.e., it’s before the “vacuum horizon”).
-
Node Pruning: If, after pruning versions, a key’s version chain becomes empty, the node itself is logically marked as deleted. A subsequent traversal of the skiplist will then physically unlink and reclaim the memory for this node.
Finally, it updates the TransactionManager to allow it to prune its own
historical transaction status records, further saving memory.
§Returns
A Result containing a tuple of (versions_removed, keys_removed).
Source§impl<K, V> SkipList<K, V>
impl<K, V> SkipList<K, V>
Sourcepub fn with_max_level(max_level: usize) -> Self
pub fn with_max_level(max_level: usize) -> Self
Creates a new, empty SkipList with a specified max level.
Sourcepub fn with_max_level_and_p(max_level: usize, p: f64) -> Self
pub fn with_max_level_and_p(max_level: usize, p: f64) -> Self
Creates a new, empty SkipList with a specified max level and probability factor.
Sourcepub fn transaction_manager(&self) -> &Arc<TransactionManager<K, V>>
pub fn transaction_manager(&self) -> &Arc<TransactionManager<K, V>>
Returns a reference to the associated TransactionManager.
Sourcepub fn len(&self) -> usize
pub fn len(&self) -> usize
Returns the approximate number of keys in the skiplist.
This is an approximation because it may not reflect in-flight additions or removals.
Sourcepub fn get(&self, key: &K, transaction: &Transaction<K, V>) -> Option<Arc<V>>
pub fn get(&self, key: &K, transaction: &Transaction<K, V>) -> Option<Arc<V>>
Retrieves the value associated with key that is visible to the given transaction.
This method traverses the skiplist to find the node for the given key. It then
walks the version chain for that node to find the most recent version that is
visible according to the transaction’s Snapshot.
As part of the SSI protocol, this operation adds the key to the transaction’s read set.
Sourcepub fn contains_key(&self, key: &K, transaction: &Transaction<K, V>) -> bool
pub fn contains_key(&self, key: &K, transaction: &Transaction<K, V>) -> bool
Checks if a key exists and is visible to the given transaction.
Sourcepub async fn insert(
&self,
key: K,
value: Arc<V>,
transaction: &Transaction<K, V>,
)
pub async fn insert( &self, key: K, value: Arc<V>, transaction: &Transaction<K, V>, )
Inserts a key-value pair as part of a transaction.
If the key already exists, this prepends a new version to its version chain.
If the key does not exist, this creates a new Node and links it into the skiplist.
This operation adds the key to the transaction’s write set for SSI conflict detection.
Sourcepub async fn remove(
&self,
key: &K,
transaction: &Transaction<K, V>,
) -> Option<Arc<V>>
pub async fn remove( &self, key: &K, transaction: &Transaction<K, V>, ) -> Option<Arc<V>>
Logically removes a key as part of a transaction.
This finds the latest visible version of the key and atomically sets its
expirer_txid to the current transaction’s ID. The actual data is not
removed until the vacuum process runs.
This operation adds the key to the transaction’s write set.
§Returns
Returns the value that was removed if a visible version was found, otherwise None.