Abstract
Consistent hashing is a central building block in many networking applications, such as maintaining connection affinity of TCP flows. However, current consistent hashing solutions do not ensure full consistency under arbitrary changes or scale poorly in terms of memory footprint, update time and key lookup complexity. We present AnchorHash, a scalable and fully-consistent hashing algorithm. AnchorHash achieves high key lookup rate, low memory footprint and low update time. We formally establish its strong theoretical guarantees, and present an advanced implementation with a memory footprint of only a few bytes per resource. Moreover, evaluations indicate that AnchorHash scales on a single core to 100 million resources while still achieving a key lookup rate of more than 15 million keys per second.