Thread safe tree library?

[joseph.p...@gmail.com]

Is there a simple tree library that is thread safe? 

If I have to write one for myself, do I have to set locks on nodes as I walk the tree to 

prevent another thread from changing nodes that are 'above' me?

[K. Alex Mills]

That is the simplest and most conservative way go about it, but ultimately it depends on what you need out of your concurrency semantics.

If you're willing to settle for a linearizable execution, you can gain some performance improvements by only checking the lock for write operations. So long as two write operations do not pass each other in the tree, they will be linearizable based on which write passed the root node first. Read operations can pass one another (and other write operations) freely. We can always pick a linearization point for them with respect to the rest of the concurrent write operations in the tree.

You will also need to do hand-over-hand locking on your way down the tree to ensure no two writes can overtake one another.

An approach like this can yield significant performance gains and you can formally show that the results you get are correct with regard to some actual state the tree could be in depending on when you consider each concurrent write to "complete".

--
You received this message because you are subscribed to the Google Groups "golang-nuts" group.
To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/golang-nuts/6597198c-c439-4a1e-bff2-a2176204b272n%40googlegroups.com.

[Nathan Fisher]

Does write only locking provide read correctness? I would’ve thought based on the memory model it could cause issues?

https://golang.org/ref/mem#tmp_2

To view this discussion on the web visit https://groups.google.com/d/msgid/golang-nuts/CALJzkY-RSMPbObc-Dxhw985O9v_raMhGNwGcy03%3DKuWRTHeRmg%40mail.gmail.com.

[K. Alex Mills]

On Tue, Jan 5, 2021, 6:59 PM Nathan Fisher <nfi...@junctionbox.ca> wrote:

Does write only locking provide read correctness? I would’ve thought based on the memory model it could cause issues?

https://golang.org/ref/mem#tmp_2

It depends on your notion of "read correctness", specifically when you consider each read to have occurred with respect to its concurrent writes. Linearizability may be a weaker guarantee than you want, and that's okay.

Linearizability requires that, for each operation, you can pick some point between the start and end of an operation when it can be said to have "occurred". When you consider all the operations in that order, the results you see must be the same as a sequential execution.

In the case I have described, we can pick a linearization point for reads just before the last write which they passed on their way down the tree. The reads should then see all the writes which happened prior to this point.

This isn't the order the operations enter the root, but linearizability doesn't care. It doesn't have an opinion on when overlapping operations "occur" with respect to one another.

I don't think using a happens-before relation for the program order seen by each goroutine is going to cause a problem with respect to choosing these linearization points, but maybe I'm missing something.

Maybe also there is a standardized notion of read correctness that you're referring to which I am not aware of.

[joseph.p...@gmail.com]

Well, I think I only need to lock on writes, and it'll be easier if I just lock the entire tree on writes. Reads will be the majority of the operations by far. This is for a bit of caching before we go to a K/V database like REDIS, etc.

[Robert Engels]

I think you have to go a bit more and use a RW mutex to ensure memory consistency (for the simple solution). 

On Jan 5, 2021, at 8:52 PM, joseph.p...@gmail.com <joseph.p...@gmail.com> wrote:

Well, I think I only need to lock on writes, and it'll be easier if I just lock the entire tree on writes. Reads will be the majority of the operations by far. This is for a bit of caching before we go to a K/V database like REDIS, etc.

--

You received this message because you are subscribed to the Google Groups "golang-nuts" group.
To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts...@googlegroups.com.

To view this discussion on the web visit https://groups.google.com/d/msgid/golang-nuts/8d97ad06-f7e6-4fdd-8ec4-0803e0ad3dd1n%40googlegroups.com.

[ksbh...@gmail.com]

https://pkg.go.dev/lang.yottadb.com/go/yottadb gives you B*trees with a hierarchical key-value model that you can experiment with in a Docker container (or of course a virtual or real machine). When you get to needing persistence and concurrency control, you can also get ACID transactions (i.e., for linearization, it “occurs” at commit time).

Regards

– Bhaskar

[Robert Engels]

You can look at github.com/robaho/keydb and it’s LSM trees as an alternative method of concurrency. You can also take the low level tree.go and wrap it in a RW mutex. 

On Jan 6, 2021, at 9:28 AM, ksbh...@gmail.com <ksbh...@gmail.com> wrote:



To view this discussion on the web visit https://groups.google.com/d/msgid/golang-nuts/78177b5a-d1b9-49bd-a275-5bd2585f8b15n%40googlegroups.com.

[Nathan Fisher]

I was thinking of potential issues if you rebalance the tree as an example.

I’m not certain what issues could arise as I’ve never considered a concurrent data structure that lacks some kind of synchronisation for both read and writes unless it’s immutable copy-on-write or similar.

Do you happen to have references available for further research?

[Robert Engels]

I would review the source code of the Java concurrent package. It has links to the relevant academic research. 

On Jan 8, 2021, at 1:29 PM, Nathan Fisher <nfi...@junctionbox.ca> wrote:



--

You received this message because you are subscribed to the Google Groups "golang-nuts" group.
To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts...@googlegroups.com.

To view this discussion on the web visit https://groups.google.com/d/msgid/golang-nuts/CA%2Bc2dWexae8DOR4h4M9hgCFps%3D60F7bjr%3DKGPLS3OuvTL-NN7w%40mail.gmail.com.

[K. Alex Mills]

I was thinking of potential issues if you rebalance the tree as an example.

I’m not certain what issues could arise as I’ve never considered a concurrent data structure that lacks some kind of synchronisation for both read and writes unless it’s immutable copy-on-write or similar.

Do you happen to have references available for further research?

You do have to be careful when rebalancing. The goal is to make the rebalancing appear atomic to other reads as they go down the tree. IIRC a technique to do this involves recreating the nodes involved in the rebalance and completing the rebalance by updating a single edge at once. That sounds a lot to me like copy-on-write but IIRC it doesn't require copying the entire subtree.

You might also be interested in some of the below references, although they're all on lock-free and wait-free options. Disclaimer: They're all from my Ph.D advisor. I was working in his lab when most of this work was being done. Most of what I've posted here is based on my memory of their approach.

https://dl.acm.org/doi/10.1145/3391438  

https://dl.acm.org/doi/10.1145/3016078.2851173 

https://dl.acm.org/doi/10.1145/2688500.2688551

[joseph.p...@gmail.com]

Thanks! You all have given me much to look at.

-joe