Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Cmapv2: A high performance, concurrent map

github.com

Post reply on HN
Print view View original

21–28 of 28 posts

Re: Cmapv2: A high performance, concurrent map

#21

Post by sirgallo »

kiitos wrote: post #12
kiitos wrote: post #11

This repo is completely unsound, code like [1] is pervasive and demonstrates a total misunderstanding of what guarantees are provided -- or, really, not provided -- by "atomic" reads of unsafe.Pointer values. Data races everywhere! Not safe, do not pass go, do not collect $200, absolutely do not use. [1] https://github.com/sirgallo/cmapv2/blob/280e3017ae4ba212f6f8...

Be more specific? OK --- CopyNode broken `CopyNode` duplicates only the parent; every child pointer is still shared nodeCopy.setChildren(make([]*node, len(n.children))) copy(nodeCopy.children, n.children) // pointers reused https://github.com/sirgallo/cmapv2/blob/main/node.go#L11-L17 Any later mutation (for example `setValue`) writes through those shared pointers, so readers and historical snapshots are modified conc…

Hi, thank you for the in depth response. I really needed to hear these things. I have gone ahead and addressed almost all of the issues that you pointed out. I updated the root to be the only point for compare and swap and on mutations I do a clone instead of mutating the shared pointer. I updated set bit from xor to set and have an explicit clearbit fn for deletions. I also updated k/v aliasing to copy slices on write so that old copies do not share ref to same slice. The node pool has been removed completely for the time being as well. I added in additional tests to test for these cases and added in more concurrent tests as well. this was huge feedback and I really appreciate it.

Re: Cmapv2: A high performance, concurrent map

#22

Post by sapiogram »

johnisgood wrote: post #20
sapiogram wrote: post #19

Earlier quoted context omitted.

> You must clone the slice on both write and read, right? I haven't looked at the code, but that doesn't make sense to me. If you can't read the slice safely, you also can't clone it safely.

So, what are the solutions if they are indeed not safe to do read / write concurrently? Like okay, I read "both []byte slices, which are not safe for concurrent r/w access", but then, what is the solution? If the claim is indeed true.

Some options:

- Make sure no one mutates the slice ever, making it safe to read

- Guarding the slice behind a mutex, requiring anyone who reads or writes it to lock the mutex first

- Using some kind of thread-safe slice implementation

Re: Cmapv2: A high performance, concurrent map

#23

Post by sirgallo »

sapiogram wrote: post #22
johnisgood wrote: post #20

Earlier quoted context omitted.

So, what are the solutions if they are indeed not safe to do read / write concurrently? Like okay, I read "both []byte slices, which are not safe for concurrent r/w access", but then, what is the solution? If the claim is indeed true.

Some options: - Make sure no one mutates the slice ever, making it safe to read - Guarding the slice behind a mutex, requiring anyone who reads or writes it to lock the mutex first - Using some kind of thread-safe slice implementation

I went with option 1.

On a mutation, I do a complete node copy where I also copy the key/value slices. When I set a child node for the first time or update a child, I create a branch new leaf node with a copy of the key/value. This way previous nodes maintain the original copy.

Re: Cmapv2: A high performance, concurrent map

#24

Post by kiitos »

sirgallo wrote: post #21
kiitos wrote: post #12

Earlier quoted context omitted.

Be more specific? OK --- CopyNode broken `CopyNode` duplicates only the parent; every child pointer is still shared nodeCopy.setChildren(make([]*node, len(n.children))) copy(nodeCopy.children, n.children) // pointers reused https://github.com/sirgallo/cmapv2/blob/main/node.go#L11-L17 Any later mutation (for example `setValue`) writes through those shared pointers, so readers and historical snapshots are modified conc…

Hi, thank you for the in depth response. I really needed to hear these things. I have gone ahead and addressed almost all of the issues that you pointed out. I updated the root to be the only point for compare and swap and on mutations I do a clone instead of mutating the shared pointer. I updated set bit from xor to set and have an explicit clearbit fn for deletions. I also updated k/v aliasing to copy slices on wri…

The point of enumerating all of those specific issues, wasn't to say "here are some bugs" and if you fix them you're good. It was to say "here are some examples of the much more fundamental problem", which seemed to be a fundamental misunderstanding of the language memory model and the guarantees offered by assignments, atomic.CompareAndSwap, etc., and those operations' interactions with package unsafe.

For example this code

https://github.com/sirgallo/cmapv2/blob/6bcaa0253b1b0b261e8a...

and in particular its use of this code

https://github.com/sirgallo/cmapv2/blob/6bcaa0253b1b0b261e8a...

is still completely unsound.

Looking at *only this code path* -- and there are *many more* --

---

Put

- Snapshots the current root pointer with atomic.LoadPointer

- Makes an updated root pointer via putRecursive, given the snapshotted root pointer

- Spins on a CAS of the root ptr and the updated ptr with runtime.Gosched() between attempts

---

atomic.LoadPointer isn't a real snapshot

- It's atomic only over the root ptr, not any interior field

- Those interior fields are mutated in-place via e.g. setBitmap, setChild, etc.

- Any goroutine can see partial data, violating the memory model, etc.

---

putRecursive is unsound

- copyNode performs a shallow copy, child pointers are shared, subsequent setChild, extendTable, etc. mutate nodes other goroutines can still hold -- this is a fundamental bug that seems to remain un-addressed from the previous review

- Those mutations use plain writes (no atomics/locks/etc.) -- data race, memory model violation, etc.

- Get later returns the internal []byte slice directly -- data race, memory model violation, etc.

- Newly created nodes are cast to unsafe.Pointer without an atomic store, bypassing the write barrier required by the GC

---

That compareAndSwap is unsound

- It compares only the root pointer, a shallow copy

- After a successful CAS other writers can still mutate any shared children (see above), so readers following any shared path see data races, memory model violations, etc.

- The retry loop can livelock, details elided

---

The implementation still seems to confuse "atomic pointer swap" with "atomic update of a complex, shared value", misunderstands the requirements of the Go memory model, and consistently mis-uses unsafe.Pointer.

tl;dr here is probably to just stop using package unsafe altogether, until you have some time to properly understand its semantics, requirements, and limitations...

Re: Cmapv2: A high performance, concurrent map

#25

Post by sirgallo »

kiitos wrote: post #24
sirgallo wrote: post #21

Earlier quoted context omitted.

Hi, thank you for the in depth response. I really needed to hear these things. I have gone ahead and addressed almost all of the issues that you pointed out. I updated the root to be the only point for compare and swap and on mutations I do a clone instead of mutating the shared pointer. I updated set bit from xor to set and have an explicit clearbit fn for deletions. I also updated k/v aliasing to copy slices on wri…

The point of enumerating all of those specific issues, wasn't to say "here are some bugs" and if you fix them you're good. It was to say "here are some examples of the much more fundamental problem", which seemed to be a fundamental misunderstanding of the language memory model and the guarantees offered by assignments, atomic.CompareAndSwap, etc., and those operations' interactions with package unsafe. For example t…

Understood, and again, thank you for picking apart my code. I will take some time to fully understand Go mem model and unsafe package before trying to tackle this problem again. In the meantime, do you have any resources I could take a look at to better my understanding?

Re: Cmapv2: A high performance, concurrent map

#26

Post by sirgallo »

kiitos wrote: post #24
sirgallo wrote: post #21

Earlier quoted context omitted.

Hi, thank you for the in depth response. I really needed to hear these things. I have gone ahead and addressed almost all of the issues that you pointed out. I updated the root to be the only point for compare and swap and on mutations I do a clone instead of mutating the shared pointer. I updated set bit from xor to set and have an explicit clearbit fn for deletions. I also updated k/v aliasing to copy slices on wri…

The point of enumerating all of those specific issues, wasn't to say "here are some bugs" and if you fix them you're good. It was to say "here are some examples of the much more fundamental problem", which seemed to be a fundamental misunderstanding of the language memory model and the guarantees offered by assignments, atomic.CompareAndSwap, etc., and those operations' interactions with package unsafe. For example t…

Hey, this is going to sound crazy, but I have been looking for someone to critique my code with as much care as you have and give real genuine feedback. I am going to take your input as learning experience.

Re: Cmapv2: A high performance, concurrent map

#27

Post by jbn »

ecshafer wrote: post #17
sapiogram wrote: post #13

Earlier quoted context omitted.

Thank you for debunking it so I didn't have to. I don't think I've ever seen someone post a low-level/concurrent data structure in Go that wasn't wildly unsound, so I assumed this was too.

Go is made by Google. Do they not have someone writing an equivalent of Java.util.concurrent.ConcurrentHashMap?

or a port of the lock-free hash map from https://preshing.com/20130605/the-worlds-simplest-lock-free-...

But really, the premise of using a shared map with concurrent readers and writers seems like a good generator of hard-to-reproduce bugs. IMHO shared-nothing (when feasible) is much easier to reason about, and possibly do periodic merging of thread-local updates, but I would avoid concurrent updates entirely (in particular if 2 threads race to update the same key... that goes to deeper design issues in the application).

Post reply on HN