7 ms·

A distributed key value store in under 1000 lines

187 points by Triv888 6y ago

xuejie 6y ago
Reminds me of the first version of Redis in tcl: https://gist.github.com/antirez/6ca04dd191bdb82aad9fb241013e88a8 https://gist.github.com/antirez/6ca04dd191bdb82aad9fb241013e...
- greatNespresso 6y ago
  Man, that's so cool thanks for sharing !
- maxekman 6y ago
  That is really cool to read! I love seeing the early seeds of big projects!
alexchamberlain 6y ago
1000 lines... + nginx. This looks really interesting, but I think I'd sell it as "using nginx as a key-value store" rather than a key value store in less than 1000 lines.
- tuxone 6y ago
  Yet the number of loc to be maintained is less than 1k. Following this logic we should then add standard libraries and the whole os into account.
  - bostik 6y ago
    > Following this logic we should then add standard libraries and the whole os into account. I realise you're being snarky but systems and verification schemas like that do exist. The terms I most often associate with them is "high-assurance" or "critical supply chain" software. There's bound to be many others. These requirements crop up in stuff like the firmware for ATM keypad. Or Google's source code (they vendor everything in their own trees). Or Vegas slot machines. In an amusing twist, software supply chain assurance is such a massive problem that large security consultancies offer code escrow services. If you, as a software seller, can't guarantee that you'll be around 20 years down the line, the buyer can require you to submit your code to such a third-party service. Should you go out of business, the source code will remain accessible to the buyer for their future development needs.
  - vzcx 6y ago
    I honestly wish people did do this for these sorts of posts because it opens up a lot of solution space and would lead to interesting optimizations along the entire stack. The boundaries between all levels fade, the pieces ready for creative recombination. All that other code needs maintainers. Is it really that interesting to say "look how much I can punt to others?" It's not as if anyone except the authors will use these micro libs, we might as well encourage metrics that produce interesting ones.
  - alexchamberlain 6y ago
    I wasn't so much disagreeing with the number, as much as it being the tag line. Excluding ansible/chef recipe to manage the machine, I could deploy Redis and have no lines of code to maintain.
- ivoras 6y ago
  Go does include a reasonably capable HTTP server, so they could have done it in Go... but would you add the Go's HTTP server LOC to the count? :)
  - tutfbhuf 6y ago
    If Go's HTTP server would be a standalone binary and you have to take care of it separately from the main code base, then yes.
  - devjam 6y ago
    Go's HTTP server is typically imported as a package, just like `math/rand`, `time` or `fmt`. The resultant compiled binary would then be larger than if it had not been imported, but the package itself doesn't contribute to LOC. FWIW, the app does import and run Go's HTTP server for "server" commands: https://github.com/geohot/minikeyvalue/blob/master/src/main.go#L108 https://github.com/geohot/minikeyvalue/blob/master/src/main....
judofyr 6y ago
I looked a bit into this code and here's a short summary: - The API supports GET/PUT/DELETE (no range queries). - It uses 1 master server and N volume servers. - The master server keeps track of all keys and all requests need to go through this server. The values are stored in one or more volume servers using rendezvous hashing. - The volume servers are just Nginx + DAV which stores data on disk. - There's no live support for rebalancing. If you change the backend volumes, then you need to take the master server down, run a re-balancing job and then bring it up again. - Objects are locked in the master server during modification. This means that while a server is processing PUT/DELETE all GET requests for that key will be blocked. - There's no handling of errors from the volume servers. E.g. if one volume server fails to store data, then it won't rollback the changes done to the other volume servers nor do anything in the master server. - The benchmarking tool (thrasher.go) does "10000 write/read/delete" in 16 threads/goroutines. This means that it generates 10k random keys (i.e. no contention at all), and for each key it does a PUT, then a GET and then a DELETE. Their result show that it's capable of handling 3815.40 keys/sec (i.e. multiply this by 3 to get the request count).
- rakoo 6y ago
  Looking quickly at the code myself: > - The API supports GET/PUT/DELETE (no range queries). There are range query on keys: # list keys starting with "we" curl -v -L localhost:3000/we?list > - There's no handling of errors from the volume servers If a GET/PUT/DELETE fails it is communicated to the master server, who doesn't write anything in its own database All in all I believe it does quite a lot for less than 1000 lines already. Knowing its limitations I'm curious to see how well it handles production usage
  - codefined 6y ago
    > There are range query on keys I took it to mean the webserver doesn't support "HTTP range requests"[0], as opposed to ranges of keys. [0] https://developer.mozilla.org/en-US/docs/Web/HTTP/Range_requests https://developer.mozilla.org/en-US/docs/Web/HTTP/Range_requ...
  - judofyr 6y ago
greatNespresso 6y ago
For those interested, here is the youtube video of geohot building it: https://www.youtube.com/watch?v=cAFjZ1gXBxc https://www.youtube.com/watch?v=cAFjZ1gXBxc
- nucatus 6y ago
  What is coded in that video is the python version of it. The actual version is written in Go.
  - greatNespresso 6y ago
    Wow good catch indeed, thanks for pointing out
PostThisTooFast 6y ago
Just remember: It’s “key/value” store.
mxmxnxor 6y ago
Does it support consistent replication and automatic failover? (you need implement raft or paxos-like replication algorithm for this)
nasretdinov 6y ago
Shameless plug: I have a small YouTube series about developing a very similar distributed key-value database in Go. The sources for the database itself are at https://github.com/YuriyNasretdinov/distribkv https://github.com/YuriyNasretdinov/distribkv . The database uses static sharding using powers of 2 and also requires downtime to increase the number of shards.
nucatus 6y ago
To avoid some confusion, this is only the "distributed" part. The actual store is handled by the https://github.com/google/leveldb https://github.com/google/leveldb library.
EugeneOZ 6y ago
As usual, a tiny wrapper and huge beasts behind it, but let's count just this wrapper's code, lol. nginx and levelDb - who cares about them? :)
- deleted 6y ago
  [deleted]
- Triv888 6y ago
  Do you count Python too while you're at it...
ZephyrBlu 6y ago
This seems more like a _sharded_ KV-store than a distributed one, no? A truly distributed KV-store would use a consensus algorithm to prevent the master server being a single point of failure. For instance, CockroachDB uses Raft [0]. [0] https://www.infoq.com/presentations/cockroachdb-distributed-sql/ https://www.infoq.com/presentations/cockroachdb-distributed-...
- tmotwu 6y ago
  If we go by most definitions of a distributed system, say Lamport’s, it still is. It’s networked, asynchronous, has group membership and replication. Provides liveness guarantees with a coordinator for requests and locks. GFS/NFS predates many modern data stores, had SPOF, and are considered important contributions in distributed computing.
lexicality 6y ago
Maybe I'm just jaded by now, but these days whenever I see someone bragging about how much smaller their codebase is vs thing they want to replace, I start to wonder what edge cases they decided don't exist. Like you try running this in production and 3 months later find out it instantly dies if there's more than 4% packet loss between you and the DNS server or something
- vzcx 6y ago
  It needs to become commonplace to include your OS, external dependencies, and any language runtime code in this count. Otherwise it's just not going to evolve into a proper demoscene.
- notretarded 6y ago
  It's George hotz, literally all edge cases are left to be considered as "an exercise for the reader"
  - lexicality 6y ago
    And he founded a self driving vehicle startup? Oh dear...
    - jonathanstrange 6y ago
      Well, if I remember correctly his original suggestion was to use the mobile phone to steer the car, nothing could go wrong with that...
      - boogies 6y ago
        > nothing could go wrong with that... https://comma.ai/ https://comma.ai/ says it’s been driven 30 million miles (over years), has anything gone wrong?
        quineoa 6y ago
        Also, unlike Elon tweets (from https://github.com/commaai/openpilot/blob/devel/README.md#supported-cars https://github.com/commaai/openpilot/blob/devel/README.md#su...): > openpilot ALC and openpilot LDW do not automatically drive the vehicle or reduce the amount of attention that must be paid to operate your vehicle. The driver must always keep control of the steering wheel and be ready to correct the openpilot ALC action at all times. While changing lanes, openpilot is not capable of looking next to you or checking your blind spot. Only nudge the wheel to initiate a lane change after you have confirmed it's safe to do so. Many factors can impact the performance of openpilot ALC and openpilot LDW, causing them to be unable to function as intended. These include, but are not limited to: Poor visibility (heavy rain, snow, fog, etc.) or weather conditions that may interfere with sensor operation. The road facing camera is obstructed, covered or damaged by mud, ice, snow, etc. Obstruction caused by applying excessive paint or adhesive products (such as wraps, stickers, rubber coating, etc.) onto the vehicle. The device is mounted incorrectly. When in sharp curves, like on-off ramps, intersections etc...; openpilot is designed to be limited in the amount of steering torque it can produce. In the presence of restricted lanes or construction zones. When driving on highly banked roads or in presence of strong cross-wind. Extremely hot or cold temperatures. Bright light (due to oncoming headlights, direct sunlight, etc.). Driving on hills, narrow, or winding roads. The list above does not represent an exhaustive list of situations that may interfere with proper operation of openpilot components. It is the driver's responsibility to be in control of the vehicle at all times.
ryanar 6y ago
A distributed key/value stored backed by nginx and leveldb. Though it is impressive that these two technologies are being combined to create the store in under 1k lines. If you have the time to go through the codebase, it was an interesting read. Nothing too surprising, but cool to see how it all comes together.
thom 6y ago
Dunno if anyone else has the same gut reaction, but Jepsen tests feel like table stakes at this point.
bufferoverflow 6y ago
1000 lines + Nginx + LevelDB This is basically a front-end with key balancing.
chrismarlow9 6y ago
Writing an s3 terraform resource is also under 1000 lines of code.
oli5679 6y ago
He also made a short gradient descent library, tinygrad. https://github.com/geohot/tinygrad https://github.com/geohot/tinygrad
SergeAx 6y ago
> go get github.com/syndtr/goleveldb/leveldb Okay.
chrislusf 6y ago
I am working on SeaweedFS, which this simple key value store project is inspired by. This minikeyvalue is a nice simplification for George's own use case. SeaweedFS has filePath -> fileIds -> locateVolumeServers -> lookupOnVolumeServerByFileIds. These levels of indrection give the system more control of the data management and placement. For example, one file can be mapped to multiple file ids. minikeyvalue has key -> locateVolumeServer(by nginx) -> lookupOnVolumeServerByKey. This removed the file id indirection level. This means the data is placed on statically organized volume servers. And the whole value needs to be on one volume server. So the value can not be too large. Obviously this large value is not a requirement. There are no need to over-engineer anything. If this is what is needed, no need to add more levels of indirection. And no need of being critical about this project. It is efficient and it works. It is a piece of code that the author can easily fix if any problem happens. The code and the language are just tools to get the job done. His goal is autonomous driving, not a general-purpose key value store.

187 points by Triv888 6y ago

Reminds me of the first version of Redis in tcl: https://gist.github.com/antirez/6ca04dd191bdb82aad9fb241013e88a8 https://gist.github.com/antirez/6ca04dd191bdb82aad9fb241013e...

greatNespresso 6y ago
Man, that's so cool thanks for sharing !
maxekman 6y ago
That is really cool to read! I love seeing the early seeds of big projects!

alexchamberlain 6y ago

1000 lines... + nginx. This looks really interesting, but I think I'd sell it as "using nginx as a key-value store" rather than a key value store in less than 1000 lines.

tuxone 6y ago
Yet the number of loc to be maintained is less than 1k. Following this logic we should then add standard libraries and the whole os into account.
- bostik 6y ago
  > Following this logic we should then add standard libraries and the whole os into account. I realise you're being snarky but systems and verification schemas like that do exist. The terms I most often associate with them is "high-assurance" or "critical supply chain" software. There's bound to be many others. These requirements crop up in stuff like the firmware for ATM keypad. Or Google's source code (they vendor everything in their own trees). Or Vegas slot machines. In an amusing twist, software supply chain assurance is such a massive problem that large security consultancies offer code escrow services. If you, as a software seller, can't guarantee that you'll be around 20 years down the line, the buyer can require you to submit your code to such a third-party service. Should you go out of business, the source code will remain accessible to the buyer for their future development needs.
- vzcx 6y ago
  I honestly wish people did do this for these sorts of posts because it opens up a lot of solution space and would lead to interesting optimizations along the entire stack. The boundaries between all levels fade, the pieces ready for creative recombination. All that other code needs maintainers. Is it really that interesting to say "look how much I can punt to others?" It's not as if anyone except the authors will use these micro libs, we might as well encourage metrics that produce interesting ones.
- alexchamberlain 6y ago
  I wasn't so much disagreeing with the number, as much as it being the tag line. Excluding ansible/chef recipe to manage the machine, I could deploy Redis and have no lines of code to maintain.
ivoras 6y ago
Go does include a reasonably capable HTTP server, so they could have done it in Go... but would you add the Go's HTTP server LOC to the count? :)
- tutfbhuf 6y ago
  If Go's HTTP server would be a standalone binary and you have to take care of it separately from the main code base, then yes.
- devjam 6y ago
  Go's HTTP server is typically imported as a package, just like `math/rand`, `time` or `fmt`. The resultant compiled binary would then be larger than if it had not been imported, but the package itself doesn't contribute to LOC. FWIW, the app does import and run Go's HTTP server for "server" commands: https://github.com/geohot/minikeyvalue/blob/master/src/main.go#L108 https://github.com/geohot/minikeyvalue/blob/master/src/main....

judofyr 6y ago

I looked a bit into this code and here's a short summary: - The API supports GET/PUT/DELETE (no range queries). - It uses 1 master server and N volume servers. - The master server keeps track of all keys and all requests need to go through this server. The values are stored in one or more volume servers using rendezvous hashing. - The volume servers are just Nginx + DAV which stores data on disk. - There's no live support for rebalancing. If you change the backend volumes, then you need to take the master server down, run a re-balancing job and then bring it up again. - Objects are locked in the master server during modification. This means that while a server is processing PUT/DELETE all GET requests for that key will be blocked. - There's no handling of errors from the volume servers. E.g. if one volume server fails to store data, then it won't rollback the changes done to the other volume servers nor do anything in the master server. - The benchmarking tool (thrasher.go) does "10000 write/read/delete" in 16 threads/goroutines. This means that it generates 10k random keys (i.e. no contention at all), and for each key it does a PUT, then a GET and then a DELETE. Their result show that it's capable of handling 3815.40 keys/sec (i.e. multiply this by 3 to get the request count).

rakoo 6y ago
Looking quickly at the code myself: > - The API supports GET/PUT/DELETE (no range queries). There are range query on keys: # list keys starting with "we" curl -v -L localhost:3000/we?list > - There's no handling of errors from the volume servers If a GET/PUT/DELETE fails it is communicated to the master server, who doesn't write anything in its own database All in all I believe it does quite a lot for less than 1000 lines already. Knowing its limitations I'm curious to see how well it handles production usage
- codefined 6y ago
  > There are range query on keys I took it to mean the webserver doesn't support "HTTP range requests"[0], as opposed to ranges of keys. [0] https://developer.mozilla.org/en-US/docs/Web/HTTP/Range_requests https://developer.mozilla.org/en-US/docs/Web/HTTP/Range_requ...
- judofyr 6y ago

greatNespresso 6y ago

For those interested, here is the youtube video of geohot building it: https://www.youtube.com/watch?v=cAFjZ1gXBxc https://www.youtube.com/watch?v=cAFjZ1gXBxc

nucatus 6y ago
What is coded in that video is the python version of it. The actual version is written in Go.
- greatNespresso 6y ago
  Wow good catch indeed, thanks for pointing out

PostThisTooFast 6y ago

Just remember: It’s “key/value” store.

mxmxnxor 6y ago

Does it support consistent replication and automatic failover? (you need implement raft or paxos-like replication algorithm for this)

nasretdinov 6y ago

Shameless plug: I have a small YouTube series about developing a very similar distributed key-value database in Go. The sources for the database itself are at https://github.com/YuriyNasretdinov/distribkv https://github.com/YuriyNasretdinov/distribkv . The database uses static sharding using powers of 2 and also requires downtime to increase the number of shards.

nucatus 6y ago

To avoid some confusion, this is only the "distributed" part. The actual store is handled by the https://github.com/google/leveldb https://github.com/google/leveldb library.

EugeneOZ 6y ago

As usual, a tiny wrapper and huge beasts behind it, but let's count just this wrapper's code, lol. nginx and levelDb - who cares about them? :)

deleted 6y ago
[deleted]
Triv888 6y ago
Do you count Python too while you're at it...

ZephyrBlu 6y ago

This seems more like a _sharded_ KV-store than a distributed one, no? A truly distributed KV-store would use a consensus algorithm to prevent the master server being a single point of failure. For instance, CockroachDB uses Raft [0]. [0] https://www.infoq.com/presentations/cockroachdb-distributed-sql/ https://www.infoq.com/presentations/cockroachdb-distributed-...

tmotwu 6y ago
If we go by most definitions of a distributed system, say Lamport’s, it still is. It’s networked, asynchronous, has group membership and replication. Provides liveness guarantees with a coordinator for requests and locks. GFS/NFS predates many modern data stores, had SPOF, and are considered important contributions in distributed computing.

lexicality 6y ago

Maybe I'm just jaded by now, but these days whenever I see someone bragging about how much smaller their codebase is vs thing they want to replace, I start to wonder what edge cases they decided don't exist. Like you try running this in production and 3 months later find out it instantly dies if there's more than 4% packet loss between you and the DNS server or something

vzcx 6y ago
It needs to become commonplace to include your OS, external dependencies, and any language runtime code in this count. Otherwise it's just not going to evolve into a proper demoscene.
notretarded 6y ago
It's George hotz, literally all edge cases are left to be considered as "an exercise for the reader"
- lexicality 6y ago
  And he founded a self driving vehicle startup? Oh dear...
  - jonathanstrange 6y ago
    Well, if I remember correctly his original suggestion was to use the mobile phone to steer the car, nothing could go wrong with that...
    - boogies 6y ago
      > nothing could go wrong with that... https://comma.ai/ https://comma.ai/ says it’s been driven 30 million miles (over years), has anything gone wrong?
      - quineoa 6y ago
        Also, unlike Elon tweets (from https://github.com/commaai/openpilot/blob/devel/README.md#supported-cars https://github.com/commaai/openpilot/blob/devel/README.md#su...): > openpilot ALC and openpilot LDW do not automatically drive the vehicle or reduce the amount of attention that must be paid to operate your vehicle. The driver must always keep control of the steering wheel and be ready to correct the openpilot ALC action at all times. While changing lanes, openpilot is not capable of looking next to you or checking your blind spot. Only nudge the wheel to initiate a lane change after you have confirmed it's safe to do so. Many factors can impact the performance of openpilot ALC and openpilot LDW, causing them to be unable to function as intended. These include, but are not limited to: Poor visibility (heavy rain, snow, fog, etc.) or weather conditions that may interfere with sensor operation. The road facing camera is obstructed, covered or damaged by mud, ice, snow, etc. Obstruction caused by applying excessive paint or adhesive products (such as wraps, stickers, rubber coating, etc.) onto the vehicle. The device is mounted incorrectly. When in sharp curves, like on-off ramps, intersections etc...; openpilot is designed to be limited in the amount of steering torque it can produce. In the presence of restricted lanes or construction zones. When driving on highly banked roads or in presence of strong cross-wind. Extremely hot or cold temperatures. Bright light (due to oncoming headlights, direct sunlight, etc.). Driving on hills, narrow, or winding roads. The list above does not represent an exhaustive list of situations that may interfere with proper operation of openpilot components. It is the driver's responsibility to be in control of the vehicle at all times.

ryanar 6y ago

A distributed key/value stored backed by nginx and leveldb. Though it is impressive that these two technologies are being combined to create the store in under 1k lines. If you have the time to go through the codebase, it was an interesting read. Nothing too surprising, but cool to see how it all comes together.

thom 6y ago

Dunno if anyone else has the same gut reaction, but Jepsen tests feel like table stakes at this point.

bufferoverflow 6y ago

1000 lines + Nginx + LevelDB This is basically a front-end with key balancing.

chrismarlow9 6y ago

Writing an s3 terraform resource is also under 1000 lines of code.

oli5679 6y ago

He also made a short gradient descent library, tinygrad. https://github.com/geohot/tinygrad https://github.com/geohot/tinygrad

SergeAx 6y ago

> go get github.com/syndtr/goleveldb/leveldb Okay.

chrislusf 6y ago

I am working on SeaweedFS, which this simple key value store project is inspired by. This minikeyvalue is a nice simplification for George's own use case. SeaweedFS has filePath -> fileIds -> locateVolumeServers -> lookupOnVolumeServerByFileIds. These levels of indrection give the system more control of the data management and placement. For example, one file can be mapped to multiple file ids. minikeyvalue has key -> locateVolumeServer(by nginx) -> lookupOnVolumeServerByKey. This removed the file id indirection level. This means the data is placed on statically organized volume servers. And the whole value needs to be on one volume server. So the value can not be too large. Obviously this large value is not a requirement. There are no need to over-engineer anything. If this is what is needed, no need to add more levels of indirection. And no need of being critical about this project. It is efficient and it works. It is a piece of code that the author can easily fix if any problem happens. The code and the language are just tools to get the job done. His goal is autonomous driving, not a general-purpose key value store.