Hashing, Load Balancing and Multiple Choice

摘要

Many tasks in computer systems could be abstracted as distributingitems into buckets, so that the allocation of items across buckets is asbalanced as possible, and furthermore, given an item’s identifier it ispossible to determine quickly to which bucket it was assigned. A canonicalexample is a dictionary data structure, where ‘items’ stands forkey-value pairs and ‘buckets’ for memory locations. Another exampleis a distributed key-value store, where the buckets represent locationsin disk or even whole servers. A third example may be a distributedexecution engine where items represent processes and buckets computedevices, and so on. A common technique in this domain is the use ofa hash-function that maps an item into a relatively short fixed lengthstring. The hash function is then used in some way to associate theitem to its bucket. The use of a hash function is typically the first stepin the solution and additional algorithmic ideas are required to dealwith collisions and the imbalance of hash values. In this monograph wesurvey some of these techniques. We focus on multiple choice schemeswhere items are placed into buckets via the use of several independenthash functions, and typically an item is placed at the least loadedbucket at the time of placement. We analyze the distributions obtainedin detail, and show how these ideas could be used to design basic datastructures. With respect to data structures we focus on dictionaries,presenting linear probing, cuckoo hashing and many of their variants.