Building a Networked Key-Value-Store on an FPGA

https://adamwalker.github.io/Building-FPGA-KVS/

by todsacerdoti • 3 years ago

169 39 3 years ago

adamwalker.github.io

atoav• 3 years ago

Okay, this is really cool. Basically a 10G network connected ultra low latency key-value-store that you talk to using a set of custom UDP commands (of course as a proof of concept).

I really like the idea of stripping away essentially everything that is not needed and being left with what is.

If this is done all the way, it would be an incredibly sturdy and reliable (but a bit small) key-value-store.

_zoltan_• 3 years ago

this isn't 10Gbit.

adam_walker7• 3 years ago

Yes, but it would be if implemented on an FPGA with 10G capable transceivers. The hashtable is capable of looking up a key every clock cycle so it is actually capable of a fair bit more than 10G for lookups.

pjc503• 3 years ago

This is the 100Mbit PoC for an idea that clearly scales to 10G if you buy an expensive enough FPGA.

synthos• 3 years ago

To really optimize for latency, perform read lookup (and maybe write slot resolving) before the entire UDP packet is fully buffered and checksum verified.

jojobas• 3 years ago

Very neat. Looks like you could also have many of these in parallel, simply splitting the hash space between the addresses.

adam_walker7• 3 years ago

Yup, and you can partition a FPGA in this way to scale the design to bigger chips.

offmycloud• 3 years ago

Something like this would be great for fast cluster consensus or locking, reminds me of the Coupling Facility hardware used in IBM Parallel Sysplex.

klysm• 3 years ago

This is crazy cool. I’ve been thinking of doing this for a simplified http server for a while now

avidphantasm• 3 years ago

Very cool. I have been wondering about using high-level languages to program FPGAs recently.

Also, I hadn’t heard of cuckoo hashing before, it sounds neat. I briefly looked at the Wikipedia page about cuckoo hashing that the OP linked to, but didn’t find an answer, so I’ll ask this here:

What happens when the load factor of a set of tables gets “too high”, can you just create a new table and prepend it to the list of tables and call it a day, or do you still need to rehash the existing tables?

pjc503• 3 years ago

I have been wondering about using high-level languages to program FPGAs recently.

In general this is a bad idea. It's a very tempting idea, but it leans heavily on "sufficiently smart compiler" that's inevitably not that smart and also not well supported since it's one guy's research project. Even the vendor supported ones aren't that great.

You'd be better off with a higher-level or more modern HDL that compiles to Verilog/VHDL. "Chisel" is one such.

The need to control state vs time and manage pipelining makes most higher level software languages unhelpful when trying to get efficient FPGA performance. Not only that, higher level software languages tend to encourage recursion, which maps really badly to FPGA architecture.

adam_walker7• 3 years ago

You'd be better off with a higher-level or more modern HDL that compiles to Verilog/VHDL. "Chisel" is one such.

As is Clash, the language this project was written in :) https://clash-lang.org/

j-pb• 3 years ago

This paper is a great intro to cuckoo hash tables: http://www.ru.is/faculty/ulfar/CuckooHash.pdf

Since you have multiple hash functions in use at the same time you can simply increase the number of hash functions when you grow a table to include ones that also cover the new table space.

You can then lazily hash keys with the new functions whenever they are cuckooed out of the current position, and perform lookup with all of them.

If you keep track of how many elements are using each function, you can then start deprecating the old ones once all of their keys have been hashed with the new range.

eatonphil2• 3 years ago

A key-value-store (KVS), aka hashtable, is a database used for storing and retrieving data associated with a key. They are frequently used to cache data. Sometimes they run on the same machine as the client application. Sometimes they are accessed over the network. Software examples include Memcached and Redis.

Just to clarify there, many key value stores are not hash tables but btrees or LSM trees. One reason not to use hashtables is that you can't do efficient prefix scans since hashtables aren't sorted. Though it's possible redis and memcached do use a hashtable. Rocksdb/Leveldb, and pebble use LSM trees. Berkeleydb allows you to use a btree or hashtable.

jakemoroni• 3 years ago

many key value stores are not hash tables

Yep. In fact, in an FPGA, you can even have true TCAM/CAMs (content addressable memory).

https://www.xilinx.com/products/intellectual-property/ef-di-...

luma• 3 years ago

CAM has always interested me, it’s used in network gear for fast MAC lookups and in modern CPUs for functions like the TLB. It feels like it could also be applied to some application logic if only it was accessible to the app layer.

eatonphil2• 3 years ago

I'm missing the connection you're making. What is the implication of content addressable memory here?

8192kjshad09-• 3 years ago

This is super cool but I was left feeling like it missed the most important part, benchmarks. I know it mentions "2 clock cycles", but what does the latency for this end up being when you try to query it. I would be super interested to see how much faster this ends up being e2e.

adam_walker7• 3 years ago

Yes, benchmarks are missing. When I wrote this almost two years ago, I just wanted to explain the design at a high level to make it easier for people to understand the code. I didn't have access to a higher end FPGAs capable of 10G+ line rates to do any serious benchmarking, nor did I have access to precise Ethernet timestamping equipment.

However, I do have a bit of experience designing low latency FPGA based networking firmware. <100 nanoseconds measured wire to wire at the Ethernet level should be possible with 10G Ethernet. That's actually quite a long time on an FPGA. But, when you have latencies on the order of packet (de)serialization times, you need to be very careful about what you are measuring.

Also, I haven't actually built what I'm describing, so take my estimates with a grain of salt.

plagiarist2• 3 years ago

Am I wrong that you actually cannot have multiple evictions going at once without sacrificing correctness?

If entry one hits a series of eviction locations A0, A1, A2... and entry two ends up going into AN with the same key as A(N-1) in a fewer number of steps than N, wouldn't that result in an earlier entry overwriting a later entry? Trying to wrap my head around how concurrency works when the steps are all on the same clock.

adam_walker7• 3 years ago

I'll have to think about that one. TBH, this stuff is pretty difficult to reason about.

However, I can say that I used a SMT solver as part of the wonderful SymbiYosys verification flow to verify that the design was good for around 20 cycles, no matter what the inputs are. That, and the randomised testing gives me quite a bit of confidence in the design.

plagiarist2• 3 years ago

I'd trust the SMT solver also! But if I read correctly you were only doing one insert at a time thus far? If you give it a try with multiple I hope you post again! This was a really neat project to read.

axman63• 3 years ago

I think you could definitely get into a loop where you have two values chasing each other around, offset by some number of cycles, where all their positions are full, and they keep evicting each other when they get to the array where they hash to the same index. It's certainly not an idea situation but you can limit the likelihood of it happening by keeping the load factor in check, and probabilistically all these chains should eventually terminate.

up2isomorphism2• 3 years ago

FPGA but via a network? Sounds a little bit like an oxymoron.

jovial_cavalier• 3 years ago

No? One of the hottest sectors of FPGA products currently are FPGA-accelerated NICs.

up2isomorphism2• 3 years ago

If you read the article to a certain extent you will know it has nothing to do with “FPGA accelerated NIC”.

This is a big reason why chatgpt is useful. Because some people are not better than a keyword search.

JohnMakin2• 3 years ago

Worked for a startup circa ~2017 that was working on essentially the same thing for these cards, and a connector/interface that plugged into C and then eventually Python. Got a pretty good buy offer for a startup of less than 10 people, but the CEO turned it down, and we went under shortly after.

pgwhalen• 3 years ago

What industry were you trying to sell to?

JohnMakin2• 3 years ago

fintech

0xbadcafebee• 3 years ago

This doesn't seem to have much application for general use cases. It sounds cool but in actuality a regular computer with fast k/v software will be better for almost everyone.

axman63• 3 years ago

That's not really the point, no one is claiming this is supposed to be for general purpose workloads. If you know you need this sort of relatively small, super low latency cache, then this is a great solution, but those usecases are very niche - though so are most applications where an FPGA is the appropriate solution.

Building a Networked Key-Value-Store on an FPGA

Related Stories