BW-Tree

Traditional B-Tree has a few noticeable downsides e.g. heavy disk IO (for in-place update), and low space utilization (as B-Tree leaves a lot of space on the table to avoid frequent splits and merges). BW-Tree(https://www.microsoft.com/en-us/research/publication/the-bw-tree-a-b-tree-for-new-hardware/) is a B-Tree variant proposed by…

GNU Visibility Attribute

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

Fix visual artifact on Linux running AMD 3400G

I did a mini-itx build with AMD 3400G. It works great except occasionaly visual artifacts which affected Firefox the most when watching videos. The problem is solved by disabling IOMMU. I verfied that setting kernel parameter iommu=pt also works. https://en.wikipedia.org/wiki/Input%E2%80%93output_memory_…

Compile `folly` from source on Arch Linux

You first need to install all the dependencies as documented on the folly github page, fmt googletest, boost gflag glog These are pretty straightforward, as you can build them just fine by following the github page for each project respectively. However I ran into some issues when building folly from…

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