My skiplist.h code had a bug capable of causing data races at higher throughput.
Initially, when I ran my test harness with just two threads, each with one insert function, it compiled and ran successfully. I then increased the number to 10000 insertions per thread to see its performance, attempting to witness a potential hardware collision. And I did. It gave me a long output, the summary of which was:
SUMMARY: ThreadSanitizer: data race src/skiplist.h:37 in SkipList<int, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > >::Insert(int const&, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > const&)
==================
ThreadSanitizer: reported 4 warnings
I checked line 37 and eventually understood what the problem was—candidate.value not being an atomic variable meant it was capable of being written to simultaneously by two distinct writing threads.
The fix is to make the value variable atomic.
About the author
- Low-level C++ engineer specializing in database storage architectures. Currently deconstructing analytical query engines and implementing LSM write paths under strict ASan, TSan, and memory-ordering constraints.
Comments
Join the discussionNo comments yet. Be the first to comment.
Building the LSM-tree Storage Engine
This series details the structural evolution of a Log-Structured Merge (LSM) tree storage engine in C++. The architecture is developed sequentially from volatile memory primitives to persistent disk storage. The implementation begins with a MemTable backed by a custom Arena allocator for localized memory control. Concurrency is established via a lock-free SkipList. Data durability is enforced through Write-Ahead Logging (WAL) protocols. The system finalizes by flushing volatile data structures to immutable Sorted String Table (SSTable) blocks on disk. The documentation traces the exact engineering progression required to assemble high-throughput database internals from the ground up.
