6 ms·

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

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/ https://docs.rs/left-right/latest/left_right/

loeg 3y ago
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).
jerrinot 3y ago
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.
- the_svd_doctor 3y ago
  >> I thought I came up with something novel - it turns out it was just my ignorance:) The first 3 years of my PhD summarized in one sentence.
- dikei 3y ago
  > 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. I think you can't even do a new publish if all readers haven't finished switching to a new epoch after a previous publish. Otherwise, you risk corrupting readers that are still on the original epoch.
colonelxc 3y ago
I agree, it is a great pattern if you can spare the memory.
sa46 3y ago
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
bombela 3y ago
Interesting, I have always called this double buffering.
- cjbgkagh 3y ago
  I think the difference is that with double buffering the stale data is thrown away but here they maintain a list of operations to repeat on the stale data to bring it into sync.

loeg 3y ago

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

jerrinot 3y ago

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.

the_svd_doctor 3y ago
>> I thought I came up with something novel - it turns out it was just my ignorance:) The first 3 years of my PhD summarized in one sentence.
dikei 3y ago
> 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. I think you can't even do a new publish if all readers haven't finished switching to a new epoch after a previous publish. Otherwise, you risk corrupting readers that are still on the original epoch.

colonelxc 3y ago

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

sa46 3y ago

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

bombela 3y ago

Interesting, I have always called this double buffering.

cjbgkagh 3y ago
I think the difference is that with double buffering the stale data is thrown away but here they maintain a list of operations to repeat on the stale data to bring it into sync.