sirgallo

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.

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?

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.

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.

sounds good, they are a bit hidden right now. also am most likely going to update the other docs.

definitely, I can expand my comparisons and benchmarks

yes I can take a look, thanks for passing that along

Performance comparisons are made against go sync.Map, with cmapv2 on par or sometimes exceeding is on different workloads. It is both lock-free and thread safe, using atomic operations. It also supports sharding out of the box. cmapv2 with 10m k/v pairs where keys and values are 64bytes was able to achieve 1.5m w/s and 3m r/s.

MariV2 is an exploration of using an ordered array mapped trie as a database engine over traditional B+/LSM trees. Written purely in Go, it incorporates a version of MVCC and lock free atomic operations to achieve both high read and writes, while maintaining high durability. Tests show that it achieves writes of around 40,000 per second and reads of upwards of 250,000 per second. Ordered ranges and iterations achieves 1million+ reads a second. It is also fully transactional and has a simple to use api similar to BoltDB.

This project is also completely open source, so do with it as you wish. I have not seen any other implementations of concurrent, persistent array mapped tries, this was meant to be an exploration into beautiful data structures.

mariv2 looks to be a direct competitor to bbolt db. Also implemented in go, it utilizes a concurrent ordered array mapped trie as the storage engine, unlike most databases which utilize a B+ or LSM tree. The design is inspired by Phil Bagwell’s Ideal Hash Tree whitepaper. The design is lock free and utilizes a version of mvcc and occ.

Hey, not sure how this came up but I’m the original author of the repository…thanks for taking a look at my code and thinking it was cool enough to post on here. If you have any questions let me know, or create an issue on the repository and I’ll try to take a look at it.