HyperDB
a scalable distributed database
@mafintosh
👩 ↩️
👩 ↩️
👨 ↩️ 🖥️
👩 ↩️
👨 ↩️
👩 ↩️
👩 ↩️
👨 ↩️ 🖥️
👩 ↩️
👨 ↩️
👩 ↩️
👩 ↩️
👨 ↩️ 💀
👩 ↩️
👨 ↩️
Solution: Use more than one server
👩 ↩️
👩 ↩️
👨 ↩️ 🖥️+🖥️+🖥️
👩 ↩️
👨 ↩️
Each server is a clone of the other ones
I.e. they all contain the same data
Problem: What happens when new data is written?
👨 key=foo ➡️ 🖥️
👩 key=bar ➡️ 🖥️
Inconsistency!
Solution: Pick a leader server, and always write to that one
You can keep reading from any other one
Leader replicates changes out to all other clones
Since the leader gets all writes it knows which value is the "latest" one
Consistency!
Leader election can be done using raft or paxos
LOTS of databases rely on leader election
mySQL, Postgres, MongoDB, ...
Leader election scales well in a data center
Leader is ~always online and you have ~low latency
And you trust the computers in the data center to do the right thing
If you want to write a P2P database for the web it has issues
The web has high latency, unpredictable topologies, no implied trust
Append only logs!
Using append only logs we can design a database where multiple servers can write at the same time
🖥️
#0: key=value
db.key=value
🖥️
#0: key=value
#1: key=other-value
db.key=other-value
🖥️
#0: key=value
#1: key=other-value
#2: key=other-other-value
db.key=other-other-value
npm install hypercore
a secure, p2p, append-only log
npm install hypercore
a secure, p2p, append-only log
Using one log per server we can order events locally
🖥️ 🖥️
#0: key=foo
db.key=foo
🖥️ 🖥️
#0: key=foo
(the servers synchronize)
db.key=foo
🖥️ 🖥️
#0: key=foo
#0: key=bar
db.key=bar
What happens if two servers write at the same time?
🖥️ 🖥️
#0: key=foo
db.key=foo
🖥️ 🖥️
#0: key=foo #0: key=bar
db.key=[foo, bar]
Returns both foo and bar to the user.
User picks the "right" one
User can merge by doing a new write
🖥️ 🖥️
#0: key=foo #0: key=bar
db.key=[foo, bar]
🖥️ 🖥️
#0: key=foo #0: key=bar
(the servers synchronize)
db.key=[foo, bar]
🖥️ 🖥️
#0: key=foo #0: key=bar
#1: key=baz
db.key=baz
(demo)
How it works
The only storage we have is an append-only log...
So all keys are incrementing numbers...
We want to use string keys
Solution: Hash array mapped tries
Hash the key using a fast hash function
siphash(key) ➡️ 0xdeadbeef
Convert the hash to a lower base (we use 4)
siphash(key) ➡️ 031312320...
Find the latest values in the append-only log that shares a prefix of the hash
siphash(key) ➡️ 031312320...
siphash(key) ➡️ 031312320...
nodes1 = shares_prefix(0)
siphash(key) ➡️ 031312320...
nodes1 = shares_prefix(0)
nodes2 = shares_prefix(03)
siphash(key) ➡️ 031312320...
nodes1 = shares_prefix(0)
nodes2 = shares_prefix(03)
nodes3 = shares_prefix(031)
Remove duplicates
For each remaining node, store the log sequence number and how much of the prefix it shares
We call these nodes links.
To lookup a key:
0. hash = siphash(lookup-key)
1. Get latest node in the append-only log.
2. Check if node.key === key. If so we are done.
3. Look at the nodes it links,
and pick the one with the longest shared hash prefix
4. If no shared prefix, the key does not exist.
5. Else, get the node from the log and go to 2.
(demo)
TL;DR Store a little bit of information and lookup
any key in log(n) disk round trips