Necklace: An Efficient Cuckoo Hashing Scheme for Cloud Storage Services

With the rapid growth of data, query performance is an important concern in cloud storage applications. To reduce the query response time, cuckoo hashing via $d$ hash functions has been adopted to achieve 0(1) query efficiency. However, in practice the cuckoo hashing consumes a large amount of system resources, since an item insertion may suffer from frequent “kick-out” operations or even endless loops. In order to address this problem, we propose an efficient loop-oblivious scheme, called Necklace, in the cloud. The idea behind Necklace is to minimize data migration among servers and alleviate the collisions in the insertion operation. We identify the shortest path via indexing the auxiliary table, without retrieving the actual storage contents or carrying out the tentative “kick-out” operations. We have implemented Necklace in a real cloud system and examined the performance by using a real-world trace. Extensive experimental results demonstrate the efficiency and efficacy of Necklace.