chen--orange / nbds

non-blocking hash table, lock-free skiplist and other non-blocking data structures

nbds

non-blocking hash table, lock-free skiplist and other non-blocking data structures

Lock-Free Transactional Map Lock-free transactional key-value store. The transactional semantics follow database-style snapshot isolation using multi-version concurrency control.

With snapshot isolation updates are versioned. Transactions are isolated from changes after they begin. They always see a consistent view of the structure. Conversely, a transaction's updates are invisible to all other transactions until it commits. When a transaction tries to commit its writes are checked for conflicts against any committed concurrent transactions. If the system detects a conflict then the committing transaction rolls back. Otherwise its updates become visible to future transactions.

Lock-Free Skiplist The lock-free skiplist data structure created by Maurice Herlihy, Yossi Lev, and Nir Shavit. See Herlihy's and Shavit's book "The Art of Multiprocessor Programming" and Kir Fraser's dissertation "Practical Lock Freedom"

http://www.amazon.com/Art-Multiprocessor-Programming-Maurice-Herlihy/dp/0123705916/ http://www.cl.cam.ac.uk/techreports/UCAM-CL-TR-579.pdf I've generalized the data structure to support update operations like set() and CAS() in addition to the normal add() and remove() operations, while preserving the lock-free property and linearizability.

Lock-Free Hashtable Cliff Click's lock-free hash table from

http://www.azulsystems.com/events/javaone_2008/2008_CodingNonBlock.pdf http://sourceforge.net/projects/high-scale-lib

nbds's Issues

Invalid length used in nstring compare

What steps will reproduce the problem?
1. ns1 = "12";
2. ns2 = "123";
3. Call int ns_cmp (const nstring_t *ns1, const nstring_t *ns2);

What is the expected output? What do you see instead?
Expected response: -1
Instead: 0, due to bug in ns_cmp using ns1->len for the compare

What version of the product are you using? On what operating system?
nbds-0.4.3

Please provide any additional information below.

Original issue reported on code.google.com by [email protected] on 3 Jan 2013 at 5:54

warning: 'alloc_size' attribute directive ignored

What steps will reproduce the problem?
1. make test
2.
3.

What is the expected output? What do you see instead?


What version of the product are you using? On what operating system?
There is only one version. Redhat el5


Please provide any additional information below.

Original issue reported on code.google.com by [email protected] on 14 Jun 2011 at 9:57

It doesn't compile in 32 bits

It doesn't compile in 32 bits (Debian 6.0).

First error:
runtime/runtime.c:27: error: ‘MaxThreadId’ undeclared (first use in this 
function)

The problem is in the previous line:
static int ThreadIndex
The line doesn't terminate with ';'

if ';' is added at the end of the line, still doesn't compile:

runtime/runtime.c:14: error: ‘ThreadIndex’ defined but not used

Solution: remove the line:
static int ThreadIndex


Second error:
test/perf_test.c:70: error: cast to pointer from integer of different size

The problem is in the line:
uint64_t ops = 0;

just substitute that line by:
#ifdef NBD32
    uint32_t ops = 0;
#else
    uint64_t ops = 0;
#endif

and then it compiles.

Original issue reported on code.google.com by [email protected] on 15 Jun 2013 at 1:34