Sign in

FoundationDB is a very impressive database. Its paper won the best industry paper award in SIGMOD’21. In this post, I will explain, in detail, how FDB works and discuss a few very interesting design choices they made. It’s a dense paper packed with neat ideas. Many details (sometimes even proof of correctness) are not included in the paper. I added the proof wherever necessary.

What is FoundationDB?

It’s a non-sharded, strict serializable, fault tolerant, key-value store that supports point writes, reads and range reads. Notice that it provides a key-value API (not SQL). It’s also not sharded, meaning the entire key space is…

Paxos, is the famous synonym for consistency in the context of distributed system. Unfortunately, consistency alone, is such an overloaded term, it’s often practically meaningless. In this post, I will explain the difference between Paxos-consistency vs. quorum-consistency.

I assume you know what Paxos is and what problem it solves. If you need a quick refresher, or you are in the mood of trying to read about a new way of explaining how Paxos works, click this link.

When I say quorum-based consistency, I mean systems like Dynamo, Cassandra, etc. that claim to support “strong” consistency when you read and write…

Memoization is an old technique. It’s basically caching outputs for giving inputs (usually in a map). But a map lookup itself is not free. How can we memoize map lookups?

I learned from my coworker this nifty trick recently. Let’s say we have a map (e.g. std::unordered_map<K,V>, for which the associations (key -> value mapping) don't change during the lifetime of the program. This is fairly common for things like settings and counters. Now every time you look up a certain key, you have to paid the lookup cost (more instructions, cacheline misses, memory accesses, you name it). …

Lamport proposed Paxos Commit algorithm as an alternative to 2PC for achieving Transaction Commit. It’s a very natural application of the Paxos algorithm (if you have read this post, where I pointed out Paxos is effectively itself a read-modify-write transaction protocol.)

There’s one subtle difference between 2PC and Paxos Commit that is not addressed in Lamport’s paper or anywhere I can find. It’s about how it enforces constraints. Taking databases for example, values are sometimes associated with constraints (e.g. y can never to less than 0, x can never be greater than 1, etc.). When you are running transactions that…

C++ language include an operator called typeid (

Queries information of a type.
Used where the dynamic type of a polymorphic object must be known and for static type identification.

It gives you information about the type of an object, as long as it’s available.

int a = 0; 
std::string tname = typeid(a).name(); // tname == "i"

How it works?

Static Type

For static types, like the example above, compiler has all the information to know the evaluation result of typeid(a). Let's take at look at the assembly.

call 0x555555555160 <_ZNKSt9type_info4nameEv> is where it calls the name() member function of the…

When going through the folly code base, sometimes, you see definitions like

class FOLLY_EXPORT OptionalEmptyException : public std::runtime_error { ...

FOLLY_EXPORT is defined as

#define FOLLY_EXPORT __attribute__((__visibility__("default")))

It sets the visibility attribute of symbol OptionalEmptyException to "default". What does it do exactly, and how it works?

Static Library

We will start with a very simply example. We have a file foo.cpp,

int foo(int x) { return x*x; }

And a simple main.cpp that calls foo. If we compile main.cpp and foo.cpp and inspect the object files,

clang++ -c main.cpp foo.cpp nm -C main.o 0000000000000000 T main U foo(int) nm -C foo.o …

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 in theory, multiple readers do not contend. Naively, read performance should scale linearly. However, this is not the case in practice for most read-write locks, due to cacheline pingpong-ing.

Let’s say N threads are running on N cores, all trying to get shared ownership of the mutex (read lock). Because we need to keep…

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.

Because I burnt the 74LS138 demux, I decided to run the computer without it. So each instruction takes full 8 clock cycles unnecessarily. So you would see a lot of the time when the computer is not doing anything.

I highly recommend Ben Eater’s YouTube channel.

Tags: breadboard

Originally published at on June 6, 2020.

This is the first post of a series of posts I plan to make about TLA+.

What is a computer

First, let’s take a look at a very philosophical question — “what is a computer?”. I am writing this post on my computer, which has 32 GB of RAM and 8 2.4 GHz cores. Most likely you are reading this post on your computer as well (or smartphone, which is also a computer). We are surrounded by computers nowadays (smart phones, laptops, game consoles, smart speaker, smart home devices, etc.). But what is a computer?

Is computer the thing on your desk right now…

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. So as a customer of Spanner, it feels as if all your reads and writes are sent to a single running database instance. And even better, it’s fault tolerant, so the service is still available under failures. …

Lu Pan

Software Engineer at Facebook working on cache infrastructure

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store