The performance of today's inmemory indexes is bottlenecked by the memory latency/bandwidth wall. Processinginmemory (PIM) is an emerging approach that potentially mitigates this bottleneck, by enabling lowlatency memory access whose aggregate memory bandwidth scales with the number of PIM nodes. There is an inherent tension, however, between minimizing internode communication and achieving load balance in PIM systems, in the presence of workload skew. This paper presents PIMtree , an ordered index for PIM systems that achieves both low communication and high load balance, regardless of the degree of skew in data and queries. Our skewresistant index is based on a novel division of labor between the host CPU and PIM nodes, which leverages the strengths of each. We introduce pushpull search , which dynamically decides whether to push queries to a PIMtree node or pull the node's keys back to the CPU based on workload skew. Combined with other PIMfriendly optimizations ( shadow subtrees and chunked skip lists ), our PIMtree provides highthroughput, (guaranteed) low communication, and (guaranteed) high load balance, for batches of point queries, updates, and range scans. We implement PIMtree, in addition to prior proposed PIM indexes, on the latest PIM system from UPMEM, with 32 CPUmore »
Wormhole: A Fast Ordered Index for Inmemory Data Management
Inmemory data management systems, such as keyvalue stores, have become an essential infrastructure in today's bigdata processing and cloud computing. They rely on efficient index structures to access data. While unordered indexes, such as hash tables, can perform point search with O(1) time, they cannot be used in many scenarios where range queries must be supported. Many ordered indexes, such as B+ tree and skip list, have a O(log N) lookup cost, where N is number of keys in an index. For an ordered index hosting billions of keys, it may take more than 30 keycomparisons in a lookup, which is an order of magnitude more expensive than that on a hash table. With availability of large memory and fast network in today's data centers, this O(log N) time is taking a heavy toll on applications that rely on ordered indexes.
In this paper we introduce a new ordered index structure, named Wormhole, that takes O(log L) worstcase time for looking up a key with a length of L. The low cost is achieved by simultaneously leveraging strengths of three indexing structures, namely hash table, prefix tree, and B+ tree, to orchestrate a single fast ordered index. Wormhole's range operations can more »
 Award ID(s):
 1815303
 Publication Date:
 NSFPAR ID:
 10119147
 Journal Name:
 EuroSys '19 Proceedings of the Fourteenth EuroSys Conference 2019
 Page Range or eLocationID:
 1 to 16
 Sponsoring Org:
 National Science Foundation
More Like this


Dictionaries remain the most well studied class of data structures. A dictionary supports insertions, deletions, membership queries, and usually successor, predecessor, and extractmin. In a RAM, all such operations take O(log n) time on n elements. Dictionaries are often crossreferenced as follows. Consider a set of tuples {〈ai,bi,ci…〉}. A database might include more than one dictionary on such a set, for example, one indexed on the a ‘s, another on the b‘s, and so on. Once again, in a RAM, inserting into a set of L crossreferenced dictionaries takes O(L log n) time, as does deleting. The situation is more interesting in external memory. On a Disk Access Machine (DAM), Btrees achieve O(logB N) I/Os for insertions and deletions on a single dictionary and Kelement range queries take optimal O(logB N + K/B) I/Os. These bounds are also achievable by a Btree on crossreferenced dictionaries, with a slowdown of an L factor on insertion and deletions. In recent years, both the theory and practice of external memory dictionaries has been revolutionized by write optimization techniques. A dictionary is write optimized if it is close to a Btree for query time while beating Btrees on insertions. The best (and optimal) dictionariesmore »

Keyvalue (KV) software has proven useful to a wide variety of applications including analytics, timeseries databases, and distributed file systems. To satisfy the requirements of diverse workloads, KV stores have been carefully tailored to best match the performance characteristics of underlying solidstate block devices. Emerging KV storage device is a promising technology for both simplifying the KV software stack and improving the performance of persistent storagebased applications. However, while providing fast, predictable put and get operations, existing KV storage devices don’t natively support range queries which are critical to all three types of applications described above. In this paper, we present KVRangeDB, a software layer that enables processing range queries for existing hashbased KV solidstate disks (KVSSDs). As an effort to adapt to the performance characteristics of emerging KVSSDs, KVRangeDB implements logstructured merge tree key index that reduces compaction I/O, merges keys when possible, and provides separate caches for indexes and values. We evaluated the KVRangeDB under a set of representative workloads, and compared its performance with two existing database solutions: a Rocksdb variant ported to work with the KVSSD, and Wisckey, a keyvalue database that is carefully tuned for conventional block devices. On filesystem aging workloads, KVRangeDB outperforms Wisckeymore »

For nearly six decades, the central open question in the study of hash tables has been to determine the optimal achievable tradeoff curve between time and space. Stateoftheart hash tables offer the following guarantee: If keys/values are Θ(logn) bits each, then it is possible to achieve constanttime insertions/deletions/queries while wasting only O(loglogn) bits of space per key when compared to the informationtheoretic optimum. Even prior to this bound being achieved, the target of O(log log n) wasted bits per key was known to be a natural end goal, and was proven to be optimal for a number of closely related problems (e.g., stable hashing, dynamic retrieval, and dynamicallyresized filters). This paper shows that O(log log n) wasted bits per key is not the end of the line for hashing. In fact, for any k ∈ [log∗ n], it is possible to achieve O(k)time insertions/deletions, O(1)time queries, and O(log(k) n) = Ologlog···logn k wasted bits per key (all with high probability in n). This means that, each time we increase inser tion/deletion time by an additive constant, we reduce the wasted bits per key exponentially. We further show that this tradeoff curve is the best achievable by anymore »

Memory hard functions (MHFs) are an important cryptographic primitive that are used to design egalitarian proofs of work and in the construction of moderately expensive keyderivation functions resistant to bruteforce attacks. Broadly speaking, MHFs can be divided into two categories: datadependent memory hard functions (dMHFs) and dataindependent memory hard functions (iMHFs). iMHFs are resistant to certain sidechannel attacks as the memory access pattern induced by the honest evaluation algorithm is independent of the potentially sensitive input e.g., password. While dMHFs are potentially vulnerable to sidechannel attacks (the induced memory access pattern might leak useful information to a bruteforce attacker), they can achieve higher cumulative memory complexity (CMC) in comparison than an iMHF. In particular, any iMHF that can be evaluated in N steps on a sequential machine has CMC at most 𝒪((N^2 log log N)/log N). By contrast, the dMHF scrypt achieves maximal CMC Ω(N^2)  though the CMC of scrypt would be reduced to just 𝒪(N) after a sidechannel attack. In this paper, we introduce the notion of computationally dataindependent memory hard functions (ciMHFs). Intuitively, we require that memory access pattern induced by the (randomized) ciMHF evaluation algorithm appears to be independent from the standpoint of a computationally boundedmore »