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 ( https://en.cppreference.com/w/cpp/language/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 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…