I ntroducon to MemSQL Lock-Free data structures Tradional databases use locks (latches and enqueues) to manage serializaon and they run into issues such as deadlocks or priority inversion, when processes block each other as they complete execuon. This results in performance and scalability issues with increasing volumes of concurrent read and write operaons. Lock-free data structures that enable beer scalability and performance are at the core of MemSQL’s engine. Every component of the engine is built using lock-free data structures including queues, stacks, hash tables, skip lists, and linked lists. For superior memory management and efficiently managing transacon state, lock-free queues and stacks are used throughout the system. In the area of code generaon, lock-free hash tables are used to map query shapes to the compiled plans in the plan cache. MemSQL also implements lock-free skip lists and hash tables that are kept in memory for fast, random access to data. Lock-free skip lists are the primary index-backing data structure in MemSQL. Compared to B-trees for disk-based databases, skip lists perform extremely well in-memory and under high concurrency, thereby delivering beer scalability. Figure 4. Skiplist index 9