Help wanted: implement an ARENA based lock-free skiplist

help
1

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!

2

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.

3

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.

4

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.