Thread by @jgarzik

Finally spent some time studying #Ethereum Merkle Patricia Tree github.com/ethereum/wiki/…
1. It is an elegant data structure for Eth, creating a cryptographically stable merkle root, no matter the data insertion order.
2. Oh boy, it really punishes your hard drive storage.

In my past life at Red Hat, I wrote the ATA (aka IDE) drivers for Linux, so I know a bit about data storage and hard drives.
Here is why Eth is so punishing on data storage, and why SSDs/NVMe are a field requirement for Eth:

Like Bitcoin, Eth has poor cache locality:
* Huge db, which means each Next Page is less likely to be in page/disk cache.
* Keys are hashes, which means each Next Query Key is uniformly random, and therefore equally unlikely to be “close” to any recent past query.

Merkle Patricia trees enhance the "huge hash db" pain:
- A single tree key/value tree query requires several backend DB queries. These lookups are uniformly random & therefore just as unlikely to be in disk cache.
- Worst case is ~63 DB queries for 1 tree lookup.

None of this matters if the working set is all in cache of course. en.wikipedia.org/wiki/Working_s…
Ethereum's full node working set - on geth 1.8.22 as of yesterday - is 400G and growing. Few machines have anywhere near 400G of RAM.

For more on cache locality, see en.wikipedia.org/wiki/Locality_… and examples such as this Cornell course: cs.cornell.edu/courses/cs3110…