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.
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.
The SRAM clock and the Ethernet clock can be independent. The SRAM clock rate is what determines the rate of lookups for a single cuckoo hashtable.
On a modern FPGA, the SRAM clock can run up to about 500MHz. So, if you pipeline things, you can get 500 million lookups per second in the FPGA fabric. The maximum packet rate in 10G Ethernet is around 15 million/sec. So, no matter how you design the protocol you use to communicate with the FPGA, if you only request a single lookup per packet, you will be well below the maximum rate the RAMs can support.
Of course, I haven't actually built any of this. The clock rates in the blog post are much lower, and the chip is much smaller. So, this is all an educated guess.
For sure! 10G can be done on FPGA's at 312.5 Mhz using 32-bit words. BlockRAM on higher ended chips reaches 450Mhz+. If you wanted to it could even run at 156.25 Mhz with 64-bit words. This way it is even doable on lower ended FPGA's.
This write up seems to only refer to on fpga ram which is fast, but very limited. In fact the author seems to completely ignore using any ram external to the fpga. Certainly fpga have capacity to interface with DDR ram of various types, and the more expensive fpga the better, but that also impacts the performance quiet a lot, making performance more in line with a normal non specialized device; beacause memory access time dominates.
> making performance more in line with a normal non specialized device; because memory access time dominates.
Well, yes. With a short enough piece of network cable it's probably lower latency to query a different one of these devices a short way away than wait for DRAM to very slowly charge up a row.
Yes, this is about building a small hashtable in the RAMs internal to the FPGA. As you pointed out, things would slow down a bit if you had to go to external RAM.
However, if you are building a hashtable in external RAM that is accessed via Ethernet, I think there are still some performance gains to be had with an FPGA compared to a non-specialized device.
For one, you get to skip the PCIe bus with an FPGA, reducing latency, since the Ethernet transceivers go straight into the FPGA fabric. Also, while I don't know a lot about power consumption, I expect it would be a fair bit lower on a dedicated FPGA compared to a server performing the same work.
To really optimize for latency, perform read lookup (and maybe write slot resolving) before the entire UDP packet is fully buffered and checksum verified.
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?
> 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.
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.
> 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.
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.
I suspect it's that if you have a CAM/TCAM, the layout of the data in this memory is less dependent on algorithms meant for fast lookups. As in, if I search all the memory in a single cycle for a match anyways, it's other properties of the memory layout that become far more important.
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.
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.
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.
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.
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.
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.
The article has everything to with an FPGA accelerated NIC connected service though. Did you perhaps misunderstand what's going on? Because your comments make it sound like you've missed the point.
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.
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.
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.
40 comments
[ 2.8 ms ] story [ 91.0 ms ] threadI 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.
Does the SRAM latency still allow for single-cycle reads at 10G?
The SRAM clock and the Ethernet clock can be independent. The SRAM clock rate is what determines the rate of lookups for a single cuckoo hashtable.
On a modern FPGA, the SRAM clock can run up to about 500MHz. So, if you pipeline things, you can get 500 million lookups per second in the FPGA fabric. The maximum packet rate in 10G Ethernet is around 15 million/sec. So, no matter how you design the protocol you use to communicate with the FPGA, if you only request a single lookup per packet, you will be well below the maximum rate the RAMs can support.
Of course, I haven't actually built any of this. The clock rates in the blog post are much lower, and the chip is much smaller. So, this is all an educated guess.
Well, yes. With a short enough piece of network cable it's probably lower latency to query a different one of these devices a short way away than wait for DRAM to very slowly charge up a row.
However, if you are building a hashtable in external RAM that is accessed via Ethernet, I think there are still some performance gains to be had with an FPGA compared to a non-specialized device.
For one, you get to skip the PCIe bus with an FPGA, reducing latency, since the Ethernet transceivers go straight into the FPGA fabric. Also, while I don't know a lot about power consumption, I expect it would be a fair bit lower on a dedicated FPGA compared to a server performing the same work.
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?
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.
As is Clash, the language this project was written in :) https://clash-lang.org/
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.
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.
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-...
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.
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.
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.
This is a big reason why chatgpt is useful. Because some people are not better than a keyword search.