node-simdb is a binding of SimDB that consist of a key value store that uses arbitrary byte data (of arbitrary length) as both the key and the value. It additionally uses shared memory, which allows processes to communicate with each other quickly. It is lock free and scales well with multiple threads writing, reading, and deleting concurrently.
This package is a wrapper around the simdb C library.
SimDB is a key value store that uses arbitrary byte data (of arbitrary length) as both the key and the value. It additionally uses shared memory, which allows processes to communicate with each other quickly. It is lock free and scales well with multiple threads writing, reading, and deleting concurrently.
SimDB contains the user facing interface. It contains the ConcurrentHash
,
ConcurentStore
, and SharedMem
classes as members. These data structures are
made to be an interface over the contiguous memory given to them using a single
address. They do not allocate any heap memory themselves, but do have a few class
members that will be on the stack. At the time of this writing it is 176 bytes on
the stack.
SharedMem
: Interface to OS specific shared memory functions. Also handles
an initial alignment.ConcurrentHash
: Hash map that uses atomic operations on an array of VerIdx
structs. It uses 64 bit atomic operations to compare-exchange one VerIdx at a
time (VerIdx is two unsigned 32 bit integers, a version and an index). This makes
sure that reading, writing and deleting is lock free. Writing is lock free since
a VerIdx is already fully created and written to before putting it in the VerIdx
array (m_vis) and the put operation here is a single 64 bit compare and swap.
Deletion is lock free since the index in VerIdx is only freed from the CncrLst
after setting the VerIdx here to DELETED. Actually deletion means 1. setting the
VerIdx to DELETED 2. decrementing the readers of the blocklist that idx points
to 3. If the readers variable of that blocklist is decremented below its initial
value then the thread that took it below its initial value is the one to free it.
Get is lock free since it can read an index from a VerIdx, increment readers,
compare its key to the key in the list of blocks, read the value in the blocks to
the output buffer and finally decrement the readers variable. Just like deletion,
if a thread decrements readers below its initial value, it needs to free the block
list. This means the last one out cleans up.ConcurrentStore
: Keeps track of block lists. This primarily uses an array of
BlkLst structs (which are 24 bytes each). The BlkLst lava_vec is used to make
linked lists of block indices. The idea of a block list ends up being a starting
index (from the VerIdx struct in the concurrent hash). The BlkLst struct at the
starting index contains an index of the next BlkLst struct and so on until
reaching a BlkLst that has an index of LIST_END. This means that one array
contains multiple linked lists (using indices and not pointers of course). This
exposes an alloc() function and a free() function. alloc() gets the index of the
next block from CncrLst (concurrent list). The BlkLst struct keeps the total
length and the key length / value offset since it does not have to be atomic and
is only initialized and used when one thread allocates and only destroyed when
one thread frees, just like the actual data blocks.ConcurrentList
:
The concurrent list is an array integers. The number of elements (like all the arrays)
is the number of blocks.There is one integer per block with the integer at a
given index representing the next slot in the list. The end of the list will have
value LIST_END. On initialization the array's values would be |1|2|3|4| ... LIST_END,
which makes a list from the start to the end. This means s_lv[0] would return 1....
...
...
...
...
https://www.npmjs.com/~nicknaso
https://www.npmjs.com/~mauro-d
https://twitter.com/maurodoganieri
https://twitter.com/pierluigiiannar
Thank you to all people that encourage me every day.
Licensed under Apache license V2