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. …

Paxos in one hand is very concise. It fits in a single slide.

On the other hand, Paxos is notoriously hard to apprehend. In this post, I will explain Paxos as a read-modify-write transaction, which is much more intuitive in my opinion.


Paxos is essentially a read-modify-write transaction. It’s as simple as:

  1. Read from the majority of Acceptors to find out if a value is already chosen and which value is it.
  2. Modify the proposal to the potential chosen value.
  3. Write/propose the value to Acceptors.

Ballot number (a.k.a proposal id), is used to resolve the read-modify-write race when there are…

These two are very different concepts but can be confusing. re-entrant is used to describe a function in a single-threaded environment, thread-safe in multi-threaded environment on the other hand. A function can be both re-entrant and thread-safe, either re-entrant or thread-safe, or neither.

A function is re-entrant, if it can be interrupted in the middle of an execution, and it’s safe to call the same function again in the same thread. The second execution of the function can finish after the first one. Notice how this differs from recursing a function, as in recursion, the latter execution always finishes before…

Two Phase Commit, a.k.a 2pc, is a very well-known and intuitive algorithm, often used for coordinating transactions. Paxos is a well-known consensus algorithm, often used for replication on a stateful service. Paxos is less intuitive and harder to grasp.

Atomic commit is a classic 2pc use case. E.g. you want to commit a transaction touching different MySQL shards. You do it by locking all the rows in the first phase and committing the transaction in the second phase.

Leader election is a classic use case of Paxos. E.g. you want all replicas to agree on which host is the leader…

Lu Pan

Software Engineer at Facebook working on cache infrastructure

Get the Medium app
