Help wanted: implement an ARENA based lock-free skiplist

Hi guys, I am trying to implement an ARENA based lock-free skiplist, which is porting Dgraph's badger/skl at master · dgraph-io/badger · GitHub implementation. However, I meet some problems and want some helps and instructions on my code.

In original Go implementation, because Go has garbage collection, it is very simple to implement a growable lock-free ARENA (directly replace the buffer with a new one), but in Rust, it becomes extremely difficult and I have to use a Mutex.

func (s *Arena) allocate(sz uint32) uint32 {
	offset := atomic.AddUint32(&s.n, sz)
	if !s.shouldGrow {
		y.AssertTrue(int(offset) <= len(s.buf))
		return offset - sz

	// We are keeping extra bytes in the end so that the checkptr doesn't fail. We apply some
	// intelligence to reduce the size of the node by only keeping towers upto valid height and not
	// maxHeight. This reduces the node's size, but checkptr doesn't know about its reduced size.
	// checkptr tries to verify that the node of size MaxNodeSize resides on a single heap
	// allocation which causes this error: checkptr:converted pointer straddles multiple allocations
	if int(offset) > len(s.buf)-MaxNodeSize {
		growBy := uint32(len(s.buf))
		if growBy > 1<<30 {
			growBy = 1 << 30
		if growBy < sz {
			growBy = sz
		newBuf := make([]byte, len(s.buf)+int(growBy))
		y.AssertTrue(len(s.buf) == copy(newBuf, s.buf))
		s.buf = newBuf
	return offset - sz

The Go version, lock-free growable ARENA source code is here:

The Rust version lock-free(not lock-free in current implementation) growable ARENA source code is here:

I am a real newbie for writing lock-free data structure in Rust, really want someone can help me to complete this feature, or give me some instructions.

The repo is: GitHub - al8n/skl-rs: A lock-free thread-safe arena based Skiplist impelementation for building memtable.

Thank you very much!

I gave a look at the Go arena, but I don't see how it is thread safe. Consider this situation:

  • thread 1 tries to allocate, sees it should reallocate and creates newBuf (newBuf := ...)
  • thread 2 tries to allocate, sees it should reallocate and creates newBuf (newBuf := ...)
  • thread 1 updates s.buf
  • thread 1 writes to the updated s.buf
  • thread 2 updates s.buf
  • now thread 1 write has been lost

Not to mention that getNode/getKey might return data that refers to the old buffer. While this may not be a memory safety problem thanks to the GC it could still be a logic problem because it means any writes to them would be lost.

What you'd probably want is the buffer to be a linked list of buffers, so then to extend the buffer, you can do a CAS to link the next one on without risk of losing data or having locks.

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.