std::atomic from bottom up

std::atomic combines read-modify-write atomic instructions, memory barriers in hardware and memory order concept in C++ altogether. It's commonly used for lock-free programming, which often looks like, if (futex.compare_exchange_strong(expected, 1, memory_order_acquire)) { // lock acquired } Multiple Caches Data race doesn't exist until we had computers with…

Read-Write Transaction API

There are multiple ways you can approach a Read-Write transaction API. MySQL's transaction API is fully conversational that comes with great flexibility and power. However it can be easily abused causing long lock duration, especially in an OLTP workload. Most of the choices related to transactions boil down to pessimistic…

Synchronized Multi-Append

Hybrid Logical Clock is a nice primitive for keeping ordering. Many databases nowadays use HLC to version incoming writes (appends to binlog/WAL/redo-log). It's usually one monotonically increasing HLC per shard/database. When dealing with cross shard transactions, it would be very nice if we can have the same…

Linear scalable read-write lock

The basic concept of a read-write lock is simple. It allows multiple readers to access the resource simultaneously, but at most one thread can have exclusive ownership of the lock (a.k.a write lock). It's supposed to be an optimization, comparing to simple mutex (e.g. std::mutex). As…

Global Data Locality – Why and How

Why In folly, Facebook's open source c++ library, you often see code like the following: #define FOLLY_SETTING_DEFINE(_project, _name, _Type, _def, _desc) \ /* Fastpath optimization, see notes in FOLLY_SETTINGS_DEFINE_LOCAL_FUNC__. \ Aggregate all off these together in a single section for better TLB \ and cache locality. */ \ __attribute_…

My Ben Eater 8-bit breadboard build

I started working on it on and off, since July 2019. Burnt a few chips and stripped hundreds feet of wires. The following is a video of the computer running a program on the right. It ran a loop that keeps adding 10, until it overflowed and halted the clock.…

2 + 2 can be 22

I recently found this well-made short film, Alternative Math, https://www.youtube.com/watch?v=Zh3Yz3PiXZw. It became again after the University of Carlifornia decided to stop using ACT/SAT. I am a father of two young children, and I think everyone, including the teacher in the film, can do…

API for Assigning Timestamp

This is a follow-up post of my previous one about Spanner. There I talked about how Spanner uses TrueTime API to achieve external consistency at global scale and hide sharding and replication from users. In this post, I want to discuss different options of assigning timestamps and their usefulness to…

Notes on the Google Spanner Paper

This is my notes on the paper: Spanner: Google’s Globally-Distributed Database. I will first summarize the paper and try to explain how it works. At the end, I will list my opinion and questions about Spanner. What is Spanner It's a globally replicated database that hides sharding and replication.…