5 ms·

Cuckoo++ – High-Performance Hash Tables for Networking Applications (2017)

75 points by jsnell 6y ago

aeontech 6y ago
A neat interactive visualization http://www.lkozma.net/cuckoo_hashing_visualization/ http://www.lkozma.net/cuckoo_hashing_visualization/ Edit: as child comment points out, this is a visualization of normal cuckoo hashing, not cuckoo++ that this paper describes.
- abainbridge 6y ago
  Just to be clear, the paper is about an extension to Cuckoo hashing, while the link to the visualization is about standard Cuckoo hashing. From the paper: "we describe algorithmical changes to cuckoo hash tables allowing a more efficient implementation. More precisely, our hash table adds a bloom filter in each bucket that allows to prune unnecessary lookups to the secondary bucket."
  - aeontech 6y ago
    Yes, I should have been clearer
  - ryanmarsh 6y ago
    So we’re back to trading time for space again? I thought the whole point of a ... oh nevermind.
  - scaramanga 6y ago
    Also, when the paper says "cuckoo hashing" they mean "bucketized cuckoo hashing" which is different enough from the academic description of cuckoo hashing, which is what is described in GP's link, as to be a bit confusing!
alexhutcheson 6y ago
It would be interesting to see this benchmarked against absl::flat_hash_map[1] and folly::f14:F14FastMap[2]. [1] https://abseil.io/about/design/swisstables https://abseil.io/about/design/swisstables [2] https://github.com/facebook/folly/blob/master/folly/container/F14.md https://github.com/facebook/folly/blob/master/folly/containe...
- scaramanga 6y ago
  The point of cuckoo++ is to handle timers and expiry efficiently so neither of those hash tables is comparable. It would have to be "swisstables + heap" or "+ timer wheel" or some other timer management algorithm.
  - alexhutcheson 6y ago
    Interesting, thanks for pointing that out - it wasn't obvious to me from skimming the paper. In their "Conclusion" section, they write: "We thus propose Cuckoo++ which adds a bloom filter in the primary bucket, allowing to prune unnecessary accesses to the secondary bucket without requiring expensive computation. Cuckoo++ hash tables have a uniformly good performance when compared to both pessimistic and optimistic implementation, and an improved performance over DPDK and Horton tables for all cases. We also describe a variant of Cuckoo++ that integrate support for entry expiration directly in the hash table, avoiding the need for external management of timers and the associated overheads. This relies on a new memory layout more compact than DPDK’s original one, and on the use of 16-bit timestamp." That seems to imply that the timer/expiration feature is an optional added bonus, rather than a core feature of Cuckoo++.
    - scaramanga 6y ago
      Sure, I read it more the other way around, the bloom filter thing is part of an ongoing thrust (like horton) to reduce the number of memory accesses for bucketized cuckoo (2 on failure, 1.5 on success) down closer to 1. But in the case of flow-tracking, many more memory accesses would be needed to organise a heap or timer wheel, so that's where the main win is, compared to an incremental improvement on bucketized cuckoo / horton.
    - scaramanga 6y ago
      So yeah, you're right, comparison would be possible if you subtract all the timer stuff. But as I recall of the offered implementation there wasn't actually an easy way to do that...
skyde 6y ago
so is that thread-safe ?
- scaramanga 6y ago
  It's for networking apps where scaling is typically achieved by shared-nothing multi-threading making use of the receive-side-scaling feature of NICs. Incoming packets are hashed by their 5-tuple and divided among CPUs and a thread is capturing traffic on each CPU and works independently of the others. Edit: so the answer is that the question if thread safety isn't addressed, since it doesn't arise in the intended use-case. But I'm sure it could be added with per-bucket locking since it is based on cuckoo hash.
  - jsnell 6y ago
    Specifically, here's the system the hash table was developed for: https://www.usenix.org/conference/atc18/presentation/andre https://www.usenix.org/conference/atc18/presentation/andre So yes, very much a system architecture with no locking or sharing.
doctorsher 6y ago
The submitted link is a pre-publication draft of this conference paper published at the 2018 Symposium on Architectures for Networking and Communication Systems (ANCS): https://dl.acm.org/doi/10.1145/3230718.3232629 https://dl.acm.org/doi/10.1145/3230718.3232629
rurban 6y ago
The size of a cache line must be fixed in the preprint. He assumes a cacheline is 64 bit, whilst it is 64 byte, 8 words not just one. This affects the timestamp chapter mostly.

75 points by jsnell 6y ago

A neat interactive visualization http://www.lkozma.net/cuckoo_hashing_visualization/ http://www.lkozma.net/cuckoo_hashing_visualization/ Edit: as child comment points out, this is a visualization of normal cuckoo hashing, not cuckoo++ that this paper describes.

abainbridge 6y ago
Just to be clear, the paper is about an extension to Cuckoo hashing, while the link to the visualization is about standard Cuckoo hashing. From the paper: "we describe algorithmical changes to cuckoo hash tables allowing a more efficient implementation. More precisely, our hash table adds a bloom filter in each bucket that allows to prune unnecessary lookups to the secondary bucket."
- aeontech 6y ago
  Yes, I should have been clearer
- ryanmarsh 6y ago
  So we’re back to trading time for space again? I thought the whole point of a ... oh nevermind.
- scaramanga 6y ago
  Also, when the paper says "cuckoo hashing" they mean "bucketized cuckoo hashing" which is different enough from the academic description of cuckoo hashing, which is what is described in GP's link, as to be a bit confusing!

alexhutcheson 6y ago

It would be interesting to see this benchmarked against absl::flat_hash_map[1] and folly::f14:F14FastMap[2]. [1] https://abseil.io/about/design/swisstables https://abseil.io/about/design/swisstables [2] https://github.com/facebook/folly/blob/master/folly/container/F14.md https://github.com/facebook/folly/blob/master/folly/containe...

scaramanga 6y ago
The point of cuckoo++ is to handle timers and expiry efficiently so neither of those hash tables is comparable. It would have to be "swisstables + heap" or "+ timer wheel" or some other timer management algorithm.
- alexhutcheson 6y ago
  Interesting, thanks for pointing that out - it wasn't obvious to me from skimming the paper. In their "Conclusion" section, they write: "We thus propose Cuckoo++ which adds a bloom filter in the primary bucket, allowing to prune unnecessary accesses to the secondary bucket without requiring expensive computation. Cuckoo++ hash tables have a uniformly good performance when compared to both pessimistic and optimistic implementation, and an improved performance over DPDK and Horton tables for all cases. We also describe a variant of Cuckoo++ that integrate support for entry expiration directly in the hash table, avoiding the need for external management of timers and the associated overheads. This relies on a new memory layout more compact than DPDK’s original one, and on the use of 16-bit timestamp." That seems to imply that the timer/expiration feature is an optional added bonus, rather than a core feature of Cuckoo++.
  - scaramanga 6y ago
    Sure, I read it more the other way around, the bloom filter thing is part of an ongoing thrust (like horton) to reduce the number of memory accesses for bucketized cuckoo (2 on failure, 1.5 on success) down closer to 1. But in the case of flow-tracking, many more memory accesses would be needed to organise a heap or timer wheel, so that's where the main win is, compared to an incremental improvement on bucketized cuckoo / horton.
  - scaramanga 6y ago
    So yeah, you're right, comparison would be possible if you subtract all the timer stuff. But as I recall of the offered implementation there wasn't actually an easy way to do that...

skyde 6y ago

so is that thread-safe ?

scaramanga 6y ago
It's for networking apps where scaling is typically achieved by shared-nothing multi-threading making use of the receive-side-scaling feature of NICs. Incoming packets are hashed by their 5-tuple and divided among CPUs and a thread is capturing traffic on each CPU and works independently of the others. Edit: so the answer is that the question if thread safety isn't addressed, since it doesn't arise in the intended use-case. But I'm sure it could be added with per-bucket locking since it is based on cuckoo hash.
- jsnell 6y ago
  Specifically, here's the system the hash table was developed for: https://www.usenix.org/conference/atc18/presentation/andre https://www.usenix.org/conference/atc18/presentation/andre So yes, very much a system architecture with no locking or sharing.

doctorsher 6y ago

The submitted link is a pre-publication draft of this conference paper published at the 2018 Symposium on Architectures for Networking and Communication Systems (ANCS): https://dl.acm.org/doi/10.1145/3230718.3232629 https://dl.acm.org/doi/10.1145/3230718.3232629

rurban 6y ago

The size of a cache line must be fixed in the preprint. He assumes a cacheline is 64 bit, whilst it is 64 byte, 8 words not just one. This affects the timestamp chapter mostly.