Designing a new concurrent data structure (opens in new tab)

I only learned about the left-right schema after finishing my design. I thought I came up with something novel - it turns out it was just my ignorance:)

Still, I think the left-right crate could benefit from one optimization I came up with. This is what the lib says in the docs:

> When WriteHandle::publish is called, the writer, atomically swaps the reader pointer to point to the other T. It then waits for the epochs of all current readers to change, and then replays the operational log to bring the stale copy up to date.

I think the lib could postpone the log replaying until the next publish. Chances are all readers will have the new epoch by than = the writer thread won't have to wait at all.

Interesting, I have always called this double buffering.

Oh neat, that’s what that’s called. I did something similar in ignorance. I needed a histogram metric with multiple lock-free writers and a single reader.

- create two ring buffers (left/right; I called them hot/cold)

- store the hot ring buffer in an atomic pointer

- single reader swaps hot and cold and waits for writers to finish

If you're ok with single writer as a constraint, hazard pointers get you similar read availability at the cost of maybe more expensive writes (and similar 2x memory overhead so long as the read sections are relatively short).

I agree, it is a great pattern if you can spare the memory.

If the keys are strings and you can use Rust, have you considered fst [0]? If the keys have prefixes in common, it is very compact. There's a blog post about it [1]

[0] https://github.com/BurntSushi/fst

[1] https://blog.burntsushi.net/transducers/

The main limitation of it is that it doesn't support removal, but if removals are infrequent you can workaround that with another fst with removed items (and periodically rebuild the whole thing)

How do you learn stuff like this? Especially the JNI and off-heap memory parts.

That's actually exactly what I did! I removed this part from the article as I felt it was not relevant for the concurrent protocol design and it was adding mental load for readers not that fluent in Java.

> Did you consider just making an array of HashMap, say 512 of them, and locking only one of them based on your key's hash?

A disadvantage of that approach is that even without any lock contention you would still have two writes to memory for every lock acquisition.

I could use DirectByteBuffer instances as CHM values. But Java deallocates the backing memory of DirectByteBuffers during object finalization. If there is no on-heap memory pressure then there is no GC and thus no finalization. So it would leak offheap memory. I could also use Unsafe to hack into DirectByteBuffer and call the Cleaner explicitly. Many libraries do that anyway. But then I would still need some kind of reference counting to make sure I won't deallocate a buffer with active readers.

Is this the equivalent of directly asking the os for more pages, or does it work via some other heap-like mechanism that simply isn't garbage collected?

That's indeed a very good question! There are 2 sets of reasons:

1. Technical

The contract is given - I'm receiving usernames as CharSequence(String). I could change that, but that would likely require changes in the SQL parser - not simple at all. Alternatively, I could pass the whole CharSequence to Rust - but passing objects over the JNI boundary comes with perf. penalty (when compared to passing primitive) and we avoid that whenever possible. Or I could encode CharSequence content to a temporary offheap buffer and pass just the pointer to Rust. But this brings back some of the questions from the article - like who owns the buffer?

2. Other reasons

I realized this was a possibility only when I was nearly done with the design (this whole endeavor took less than one day) and I felt the urge to finish it. Also: This article wouldn't have been created!