Module flat_chain_store

Available on crate feature flat-chainstore only.

A fast database for the chainstore

In its infancy, floresta-chain used kv as database, since kv is a small and efficient embedded database that doesn’t require any runtime dependency. However, floresta-chain uses the database in a very unusual way: it downloads a bunch of small chunks of data that needs to be indexed and retrieved, all at once (~800k for mainnet at the time of writing). If we simply keep everything in memory, and then make one big batch, most embedded databases will see a big spike in heap usage. This would be OK for regular desktops, but floresta aims to run in small, lower-power devices too, so we can’t just assume we have two gigs of RAM to spare. We could make these writes more commonly, but then we reach an I/O bottleneck in those lower-power systems, where usually we won’t see high-quality SSDs that can make billions of transfers per second.

This chainstore was designed to reduce the over-usage of both. We do rely on any extra RAM as kernel buffers, but we also do a decent level of I/O. We get a better performance by using an ad-hock storage that exploits the fact that the data we keep is canonical and monotonically increasing, so we keep all headers in a simple flat file, one after the other. So pos(h) = h * size_of(DiskBlockHeader), with an overhead factor of 1. We also need a way to map block hashes into the given header, we do this by keeping a persistent, open-addressing hash map that map block hashes -> heights. Then from the height we can work out the block header in the headers file.

Calculations

We want to keep the load factor for the hash map as low as possible, while also avoiding re-hashing. So we pick a fairly big initial space to it, say 10 million buckets. Each bucket is 4 bytes long, so we have 40 MiB of map. Each [HashedDiskHeader] is 124 bytes long (80 bytes for header + 4 for height + 32 for hash + 8 for the accumulator size and pos), so the maximum size for it, assuming 2.5 million headers (good for the next ~30 years), is 310 MiB. The smallest device I know that can run floresta has ~250 MiB of RAM, so we could fit almost everything in memory. Given that newer blocks are more likely to be accessed, the OS will keep those in RAM.

The longest chain we have right now is testnet, with about 3 million blocks. That yields a load factor of 0.3. With that load factor, there’s a ~1/3 probability of collision, we are expected to have a worst-case search ~2. So we’ll need to fetch two nodes to find the one we want. Since each node is a u32, most of the time we’ll pull the second node too (64 bits machines can’t pull 32 bits values from memory). But to avoid going into the map every time, we keep a LRU cache of the last n blocks we’ve touched.

We also keep the accumulators for every block in a separate file, so we can load them in case of a reorg. They are stored in a regular file, and we keep the position and length of each one. The forest for mainnet has about 2^31 leaves, if we assume a Hamming weight of 1/2, we have 16 hashes per block, plus a 8-bytes leaves count. At the time of writing, we are approaching 900k blocks on mainnet. So we would have 32 * 16 + 8 = 520 bytes per accumulator. 520 * 900k = 468 MiB. This is the absolute worst case for the almost two decades that Bitcoin existed. However, although this is a pretty manageable number, we can safely get rid of some older roots, only storing the latest ones, and a few old ones for very deep reorgs. This is, however, a TODO.

Good to know

A load factor of a hashmap is the relation between empty buckets and buckets that are being used. The load factor is used to express the chance of hash collisions which decreases performance.

Buckets are the slots of a hashmap.

For more detailed information please refer to [Hash Table] (https://en.wikipedia.org/wiki/Hash_table) from wikipedia.

Safety

This is completely reckless and bare-bones, so it needs some safety precautions: (i): we must make sure that the map and flat file are initialized correctly (ii): we must make sure that the map won’t give us any height greater than the size of the flat file (iii): we must make sure that the load factor never reaches one i and ii will cause a segfault, iii will turn the addition (or search for non-existent values) an infinite loop. If we are about to reach the map’s capacity, we should re-hash with a new capacity.

Structs

DbCheckSum

The current checksum of our database

FlatChainStore

The main struct that holds all the context for our flat chain store

FlatChainStoreConfig

Configuration for our flat chain store. See each field for more information

Enums

FlatChainstoreError

An error that can happen when we’re dealing with our flat chain store