[HN Gopher] Designing a new concurrent data structure ___________________________________________________________________ Designing a new concurrent data structure Author : goodroot Score : 41 points Date : 2023-08-28 14:56 UTC (8 hours ago) (HTM) web link (questdb.io) (TXT) w3m dump (questdb.io) | cafxx wrote: | Why not just allocating the blobs off-heap? (That is something | you probably want to do anyway if it's cryptographic material, to | avoid being at the mercy of the GC leaving copies around) | | ByteBuffer.allocateDirect should do that IIRC. This allows you to | use the standard ConcurrentHashMap while being able to get a | stable pointer for use by the rust logic. | jerrinot wrote: | 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. | singron wrote: | You could also check out hazard pointers. This is basically the | example used in https://melodiessim.netlify.app/intro-hazard- | ptrs/ | jerrinot wrote: | Hello, the author here. It feels great to see my blog on HN! | | It was quite a journey, at first I thought I invented a novel | concurrency schema. However, it turns out that it was simply a | mix of my ignorance and hubris! :-) | | Still, I had a lot of fun while designing this data structure and | I believe it made a nice story. Ask me anything! | motoboi wrote: | Hi. You missed the opportunity to implement the reader as an | AutoCloseable and do the get as a Reader method. | | That way, classe users will be warned by the IDE that they should | use a try-with-resources when acquiring a Reader. | | For the sake of completeness here, Java compiler will warn about | it, but that warning is disabled by default. | jerrinot wrote: | 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. | IndoorPatio wrote: | In my experience Left-Write is the clear place to start. It's | general purpose and fast for reads. Only if that is unsuitable | (eg memory usage) does one design a custom data structure. | There's a Rust lib implementation with links to more resources: | | https://docs.rs/left-right/latest/left_right/ | jerrinot wrote: | 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. | colonelxc wrote: | I agree, it is a great pattern if you can spare the memory. | audnaun252 wrote: | seems like a lot of effort - could you have moved the map state | to rust instead? to invoke the AuthCrypto.verifySignature with | just the key? | jerrinot wrote: | 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! ___________________________________________________________________ (page generated 2023-08-28 23:00 UTC)