Perfect(ing) hashing in NetBSD

Jörg Sonnenberger

joerg@NetBSD.org

Tokyo, March 16, 2013

AsiaBSDCon 2013

Overview

  • What are Perfect Hash Functions (PHF)?
  • Why should you care?
  • Characteristics
  • History of perfect hash functions
  • Excursion I: Randomized hash functions
  • Excursion II: Random graphs
  • CHM
  • BPZ
  • nbperf
  • NetBSD's cdb
  • The future: route lookup

What are Perfect Hash Functions (PHF)?

  • Hash functions: map a set of keys to a set of integers
  • ...used to implement associative arrays
  • Perfect: injective, i.e. distinct keys are mapped to distinct values
  • A.k.a.: collision-free
  • Minimal: if the value range is [0..n-1] for n keys

Why should you care?

  • Algorithmic attacks try to force high collision rates as DoS
  • Deterministic timing
  • Compact, even if keys don't fit into memory
  • It's the S in CS
  • Because they are used in NetBSD

Route lookup in the BSD network stack

  • Problem with CIDR: find best matching prefix (BMP)
  • Implementation: radix tree
  • Very complex code
  • Solves more generic problem: non-continous netmasks
  • Kitchen-sink approach in the network stack
  • Mixes policy and implementation details
  • David Young started separation in NetBSD with thin wrapper layer

Multi-level hashing

  • Find BMP using binary search on the possible prefix lengths
  • Needs markers if a longer prefix exists and the search starts at a shorter prefix
  • References to the covered prefix in the marker avoid backtracking

Multi-level hashing example

Destination network Gateway
0/0 192.168.0.10
127/8 127.0.0.1
192.168/16 R: 0/0
192.168.0/24 192.168.0.2
192.168.1/24 192.168.0.1
10/8 192.168.0.1
10.0/16 R: 10/8
10.0.10/24 192.168.0.5
10.192/12 192.168.0.6
11/8 R: 10/8
11.192/12 192.168.0.7
  • 192.168.0.5: 192.168/16 -> 192.168.0/16 done
  • 10.0.9.8: 10.0/16 -> 10.0.9/24 done

Multi-level performance

  • Perfect hashing: deterministic cost (memory accesses!)
  • BPZ with 2-graph and no post-filter: 50% usage, 2 bit per key
  • Separate tables for larger prefixes
  • IPv4: 64bit per entry (32bit network, 32bit next-hop ID)
  • IPv6: from 64bit to 160bit
  • Fits into L3 cache even with 100,000 entries
  • Question: construction time
  • Dynamic branching: less than 2 lookups on average

Summary

  • Modern algorithms like CHM, BPZ and CHD are fast and practical
  • Useful for performance sensitive read-mostly data structures
  • Useful for compact on-disk databases
  • Available in NetBSD 6

Q&A

Questions?