[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)