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 a count of the number of active readers (to exclude writers), each lock_shared() call needs to mutate the mutex state. …


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

Image for post
Image for post

Originally published at https://blog.the-pans.com 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 with billions of transistors? Well, that describes the computer on your desk, or more generally a class of computers of this kind. But this certainly doesn’t describe all computers. If I just throw a billion transistors in a trash can, the trash can is not a computer. …


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.

Image for post
Image for post

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.

TL;DR

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


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 the former execution. …


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, that should be taking writes. …


Almost all stateful services (data store, cache, etc.) have versions stored along with each piece of data. The version can be in the form of a timestamp, version (a.k.a logical clock), or even better — Hybrid Logical Clock.

If it’s a data store, HLC is almost always better than timestamp or version. Because HCL is strictly more powerful than either timestamp or version and data stores are usually OK with sparing a few extra bytes to store it.

But there are legitimate cases that one might prefer versions. E.g. you might want to store a small version (2 bytes) in cache instead of HLC. Because a cache service is most likely memory-bound and spending a few extra bytes for every piece of data in cache can be very expensive. …


This is my notes on the paper: Amazon Aurora: Design Considerations for High Throughput Cloud-Native Relational Databases.

What’s Amazon Aurora

Functionally speaking, an instance of Aurora is same as an instance of MySQL. The differences are Aurora decouples compute from storage and it’s fault-tolerant. It supports all ANSI isolation levels and Snapshot Isolation (or consistent read).

High Level Design

Image for post
Image for post

The main idea behind Aurora is that the database is the log. It disaggregates the storage, calling SQL engine and log the database, caching and storage the storage. On writes, the database replicates its log. And the application of updates from the redo log to storage is asynchronous. …

About

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