table of contents
| SDS Copy on Write B+Tree(3) | dirsrv | SDS Copy on Write B+Tree(3) |
NAME¶
SDS Copy on Write B+Tree -
Data Structures¶
struct sds_bptree_node_list
struct sds_bptree_transaction
struct sds_bptree_cow_instance
Enumerations¶
enum sds_txn_state { SDS_TXN_READ = 0,
SDS_TXN_WRITE = 1 }
Functions¶
sds_result sds_bptree_cow_init
(sds_bptree_cow_instance **binst_ptr, uint16_t checksumming,
int64_t(*key_cmp_fn)(void *a, void *b), void(*value_free_fn)(void *value),
void *(*value_dup_fn)(void *key), void(*key_free_fn)(void *key), void
*(*key_dup_fn)(void *key))
sds_result sds_bptree_cow_destroy
(sds_bptree_cow_instance *binst)
sds_result sds_bptree_cow_verify (sds_bptree_cow_instance
*binst)
sds_result sds_bptree_cow_rotxn_begin
(sds_bptree_cow_instance *binst, sds_bptree_transaction
**btxn)
sds_result sds_bptree_cow_rotxn_close
(sds_bptree_transaction **btxn)
sds_result sds_bptree_cow_wrtxn_begin
(sds_bptree_cow_instance *binst, sds_bptree_transaction
**btxn)
sds_result sds_bptree_cow_wrtxn_abort
(sds_bptree_transaction **btxn)
sds_result sds_bptree_cow_wrtxn_commit
(sds_bptree_transaction **btxn)
sds_result sds_bptree_cow_search (sds_bptree_transaction
*btxn, void *key)
sds_result sds_bptree_cow_retrieve
(sds_bptree_transaction *btxn, void *key, void **target)
sds_result sds_bptree_cow_delete (sds_bptree_transaction
*btxn, void *key)
sds_result sds_bptree_cow_insert (sds_bptree_transaction
*btxn, void *key, void *value)
sds_result sds_bptree_cow_update (sds_bptree_transaction
*btxn, void *key, void *value)
sds_result sds_bptree_cow_search_atomic
(sds_bptree_cow_instance *binst, void *key)
sds_result sds_bptree_cow_retrieve_atomic
(sds_bptree_cow_instance *binst, void *key, void **target)
sds_result sds_bptree_cow_delete_atomic
(sds_bptree_cow_instance *binst, void *key)
sds_result sds_bptree_cow_insert_atomic
(sds_bptree_cow_instance *binst, void *key, void *value)
Detailed Description¶
Thread safe Copy of Write B+Tree. Supports parallel read transactions and serialised writes with ref counted members.
This is a very important structure, and is the primary reason to consume this library. There are a number of important properties that this tree provides.
A key concept of this structure is that all values and keys contained have their lifetimes bound to the life of the tree and it's nodes. This is due to the transactional nature of the structure. Consider a value that has been inserted into the tree. We take a read transaction of the tree in thread A. Thread B now deletes the value that was inserted. Because A still refers to the value, it is not freed until thread A closes it's read transaction. This guarantees that all read transactions are always valid, while also maintaining that memory can be freed correctly. This has many applications including the Directory Server plugin subsystem. We can use this property to guarantee a plugin exists for the life of an operation, and we only free it once all consumers have completed their operations with it.
Another key aspect of this tree is that write transactions do not block read transactions. Reads can be completed in parallel to writes with complete safety. Write operations are serialised in this structure. This makes the structure extremely effective for long read operations with many queries, without interrupting other threads.
Along with the value and key ownership properties, we can guarantee that the content of the tree within a read transaction will not be removed or added and will be consistent within the tree (however, we can't guarantee a user doesn't change the value.)
As a comparison, the single thread tree is on paper, much faster than the COW version due to less memory operations. However in a multi thread use case, the COW version is signifigantly faster and safer than a mutex protected single thread tree.
This tree can be used as a form of object manager for C, as well as a way to allow async operations between threads while maintaining, thread safety across an application. This assumes that the operations are largely parallel and batch read oriented over write heavy small transactions.
Enumeration Type Documentation¶
enum sds_txn_state¶
sds_txt_state lists the possible states of a transaction.
Enumerator
- SDS_TXN_READ
- SDS_TXN_READ 0 This is a read only transaction. Not mutable actions may be taken.
- SDS_TXN_WRITE
- SDS_TXN_WRITE 1 This is a read and write transaction. You may perform all read operations, and also all write operations.
Function Documentation¶
sds_result sds_bptree_cow_delete (sds_bptree_transaction *btxn, void *key)¶
Delete key and the associated data from the tree. This operates only on a valid write transaction, and changes made are not reflected until a commit is made. existing reads will never see this change til they close and open new transactions.
Parameters:
key The key to delete, along with associated data. If you have called retrieve on this key, the key and value must not be accessed after this point within this transactions lifetime as the values may be invalidated.
Return values:
sds_result sds_bptree_cow_delete_atomic (sds_bptree_cow_instance *binst, void *key)¶
Delete atomic functions as delete, but implise a single short livied write transaction, and commit phase.
If you have multiple searches to make, it is better to use a write transaction due to the memory design of the transaction. Multiple atomics may cause contention on certain parts of the transaction code.
Parameters:
key The key to delete. This removes the associated value.
Return values:
sds_result sds_bptree_cow_destroy (sds_bptree_cow_instance *binst)¶
Destroy an instance. This will destroy all open transactions and free all tree elements.
Parameters:
Return values:
sds_result sds_bptree_cow_init (sds_bptree_cow_instance **binst_ptr, uint16_tchecksumming, int64_t(*)(void *a, void *b)key_cmp_fn, void(*)(void *value)value_free_fn, void *(*)(void *key)value_dup_fn, void(*)(void *key)key_free_fn, void *(*)(void *key)key_dup_fn)¶
Initialise an sds cow b+tree for usage. This allocates space for the tree and bootstraps the initial blank transaction.
Parameters:
checksumming During DEBUG, this flag enables tree content checksumming.
key_cmp_fn Comparison function for keys in the tree.
value_free_fn During operation, the values assigned to this tree are owned by the instance. This allows us to free the values when required.
value_dup_fn During a copy on write operation, we need to be able to copy the values in the tree.
key_free_fn Free the key value
key_dup_fn Duplicate a key value
Return values:
sds_result sds_bptree_cow_insert (sds_bptree_transaction *btxn, void *key, void *value)¶
Insert a key and associated value to the tree via a valid write transaction. values and keys inserted to the tree now completely belong to the tree, and may be duplicated or freed at any time. After you have given a key and value to the tree, you must only access them via the retrieve interface in valid scenarios.
Parameters:
key The key to insert. If a duplicate key is detected, and error is returned.
value The value to insert. May be NULL.
Return values:
sds_result sds_bptree_cow_insert_atomic (sds_bptree_cow_instance *binst, void *key, void *value)¶
Insert atomic functions as insert, but implies a single short lived write transaction and commit phase.
If you have multiple searches to make, it is better to use a write transaction due to the memory design of the transaction. Multiple atomics may cause contention on certain parts of the transaction code.
Parameters:
key The key to insert.
value The value to insert associated with key.
Return values:
sds_result sds_bptree_cow_retrieve (sds_bptree_transaction *btxn, void *key, void **target)¶
Search a tree with a valid transaction reference. This returns KEY_PRESENT or KEY_NOT_PRESENT if the search suceeds or not. Additionally, the value attached to key is placed into the pointer for target. Search may operation on a valid uncommited write transaction, or a read transaction.
Parameters:
key The key to search for.
target The pointer where value will be placed on sucessful search. NULL is a valid value, so be sure to check the result.
Return values:
sds_result sds_bptree_cow_retrieve_atomic (sds_bptree_cow_instance *binst, void *key, void **target)¶
Retrieve atomic functions as retrieve, but implies a single short lived read transaction. Calling this implies that you must free tha value returned to you.
If you have multiple searches to make, it is better to use a read transaction due to the memory design of the transaction. Multiple atomics may cause contention on certain parts of the transaction code.
Parameters:
key The key to search for.
target The value retrieved. You must free this after use, with the same free function as the binst holds.
Return values:
sds_result sds_bptree_cow_rotxn_begin (sds_bptree_cow_instance *binst, sds_bptree_transaction **btxn)¶
Begin a read only transaction on the tree. This guarantees the memory consistency of all values in the tree for the duration of the operation.
Parameters:
btxn The pointer to a transaction to be allocated.
Return values:
sds_result sds_bptree_cow_rotxn_close (sds_bptree_transaction **btxn)¶
Complete a read only transaction. After you have closed the transaction, it may not be used again. This may trigger a garbage collection. After you close the transaction, you may NOT reference any elements you viewed in the tree. Given that there is no penalty to holding this open, just keep the transaction open til you are sure you do not need the values any longer.
Parameters:
Return values:
sds_result sds_bptree_cow_search (sds_bptree_transaction *btxn, void *key)¶
Search a tree with a valid transaction reference. This returns KEY_PRESENT or KEY_NOT_PRESENT if the search suceeds or not. Search may operation on a valid uncommited write transaction, or a read transaction.
Parameters:
key The key to search for.
Return values:
sds_result sds_bptree_cow_search_atomic (sds_bptree_cow_instance *binst, void *key)¶
Search atomic functions as search, but implies a single short lived read transaction.
If you have multiple searches to make, it is better to use a read transaction due to the memory design of the transaction. Multiple atomics may cause contention on certain parts of the transaction code.
Parameters:
key The key to search for.
Return values:
sds_result sds_bptree_cow_update (sds_bptree_transaction *btxn, void *key, void *value)¶
Update a key to have a new associated value within a valid write transaction. This is more efficient than delete -> insert, so for updates it's preferred. This is needed in the case that you have previous read transactions, and want to alter a value, without affecting the read. You would use this by calling retrieve, copying the value, then calling update on the b+tree.
Parameters:
key The key to update. If the key does not exist, fall back to insert.
value The value to update. May be NULL.
Return values:
sds_result sds_bptree_cow_verify (sds_bptree_cow_instance *binst)¶
Verify an instance holds under a number of properties. This should only be used in debbuging issues. If you find an issue, add it to the test cases!
Parameters:
Return values:
sds_result sds_bptree_cow_wrtxn_abort (sds_bptree_transaction **btxn)¶
Abort and roll back the changes made during a write transaction. This operation is guaranteed safe to all other transactions, including future writes. After the abort function is called, you must NOT access this transaction again.
Parameters:
Return values:
sds_result sds_bptree_cow_wrtxn_begin (sds_bptree_cow_instance *binst, sds_bptree_transaction **btxn)¶
Begin a write transaction. This allows you to alter the content of the tree. Due to the exclusive nature of this transaction, it is best if you are able to keep this transaction for the 'minimal' time possible as it is serialised. Changes made in a write transaction are guaranteed to have no impact on any types currently in a read transaction.
Parameters:
btxn The pointer to a location for the transaction to be created into.
Return values:
sds_result sds_bptree_cow_wrtxn_commit (sds_bptree_transaction **btxn)¶
Commit the transaction. After this operation, the transaction must not be accessed again. All changes to the tree are now visible after this call is made, and new read transactions will have this view. Commit does not affect pre-existing read transactions data.
Parameters:
Return values:
Author¶
Generated automatically by Doxygen for dirsrv from the source code.
| Tue Jun 4 2024 | Version 1.3.11.12 |