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?
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.
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.
Sure it may be weird, but my company utilized rsync for almost everything, and we were transferring files that were 100+Gb on the regular so this was actually a great tool to compare against since we were already using it for large file transfers.
Hey, you can already do this. It is designed to be portable and usage is described in the cmd folder in separate markdown file. Can be used in docker as well, with server and client usage described.
Hey man, had no reason to work on the code further, was a one man experimentation with no incentive to work on it further. The use of MD5 was not meant for security guarantees but instead as a way to ensure the integrity of content. There would be no reason to use SHA-256 in this case, not worried about security since that would be handled through use of SSL/TLS between server and client, which is already available.