IcebergHT High Performance PMEM Hash Tables Through Stability and Low Associativity

2025-04-22 0 0 780.83KB 15 页 10玖币

侵权投诉

IcebergHT: High Performance PMEM Hash Tables

Through Stability and Low Associativity

Prashant Pandey

pandey@cs.utah.edu

University of Utah

Michael A. Bender

bender@cs.stonybrook.edu

Stony Brook University

Alex Conway

aconway@vmware.com

VMware Research

Martín Farach-Colton

farach@rutgers.edu

Rutgers University

William Kuszmaul

kuszmaul@mit.edu

MIT

Guido Tagliavini

guido.tag@rutgers.edu

Rutgers University

Rob Johnson

robj@vmware.com

VMware Research

ABSTRACT

Modern hash table designs strive to minimize space while maxi-

mizing speed. The most important factor in speed is the number of

cache lines accessed during updates and queries. This is especially

important on PMEM, which is slower than DRAM and in which

writes are more expensive than reads.

This paper proposes two stronger design objectives: stability

and low-associativity. A stable hash table doesn’t move items

around, and a hash table has low associativity if there are only

a few locations where an item can be stored. Low associativity

ensures that queries need to examine only a few memory locations,

and stability ensures that insertions write to very few cache lines.

Stability also simplies scaling and crash safety.

We present IcebergHT, a fast, crash-safe, concurrent, and

space-ecient hash table for PMEM based on the design principles

of stability and low associativity. IcebergHTcombines in-memory

metadata with a new hashing technique, iceberg hashing, that

is (1) space ecient, (2) stable, and (3) supports low associativity.

In contrast, existing hash-tables either modify numerous cache

lines during insertions (e.g. cuckoo hashing), access numerous

cache lines during queries (e.g. linear probing), or waste space

(e.g. chaining). Moreover, the combination of (1)-(3) yields several

emergent benets: IcebergHT scales better than other hash tables,

supports crash-safety, and has excellent performance on PMEM

(where writes are particularly expensive).

In our benchmarks, IcebergHT inserts are 50% to 3

faster than

state-of-the-art PMEM hash tables Dash and CLHT and queries

are 20% to 2

faster. IcebergHT space overhead is 17%, whereas

Dash and CLHT have space overheads of 2

and 3

, respectively.

IcebergHT also exhibits linear scaling and is crash safe. In DRAM,

IcebergHT outperforms state-of-the-art hash tables libcuckoo

and CLHT by almost 2

on insertions while oering good query

throughput and much better space eciency.

ACM Reference Format:

Prashant Pandey, Michael A. Bender, Alex Conway, Martín Farach-Colton,

William Kuszmaul, Guido Tagliavini, and Rob Johnson. 2022. IcebergHT:

Permission to make digital or hard copies of part or all of this work for personal or

classroom use is granted without fee provided that copies are not made or distributed

for prot or commercial advantage and that copies bear this notice and the full citation

on the rst page. Copyrights for third-party components of this work must be honored.

For all other uses, contact the owner/author(s).

Conference’17, July 2017, Washington, DC, USA

ACM ISBN 978-x-xxxx-xxxx-x/YY/MM.

https://doi.org/10.1145/nnnnnnn.nnnnnnn

High Performance PMEM Hash Tables Through Stability and Low

Associativity. In Proceedings of ACM Conference (Conference’17). ACM, New

York, NY, USA, 15 pages. https://doi.org/10.1145/nnnnnnn.nnnnnnn

1 INTRODUCTION

Hash tables are a core data structure in many applications, including

key-value stores, databases, and big-data-analysis engines, and are

included in most standard libraries. Hash-table performance can

be a substantial bottleneck for many applications [14, 31, 36].

With the advent of persistent-memory (PMEM) hardware, such

as Intel Optane, designing PMEM hash tables has become an active

eld of research [

–

]. Optane is cheaper

than DRAM, enabling larger data sets, but it is slower, with write

bandwidth being roughy 2

−

slower than read bandwidth [

Hash tables must be specically designed for PMEM in order to

achieve both high performance and crash safety.

Despite several years of research on PMEM hash tables, state-of-

the-art PMEM hash tables—such as Dash [

] and CLHT [

]—utilize

less than 35% of PMEM’s raw throughput for at least one of

insertions and queries (see Figure 4) Furthermore, Dash and CLHT

have space overheads of 2-3×(see Table 3).

In this paper, we introduce a new hash table,

IcebergHT

, that

is able to achieve over 60-70% of the PMEM hardware throughput on

both insertions and queries, scales easily with additional threads, is

crash safe, and has space eciency of over 85% (i.e. space overhead

is less than 1

≈

17%). IcebergHT also integrates easily with

existing PMEM software infrastructure without requiring custom

allocators or PMDK implementations, whereas CLHT requires

custom support libraries.

The design of PMEM (and other) hash tables typically involves de-

veloping a hash table algorithm that minimizes read and write ampli-

cation.

In this paper, we argue that two stricter criteria, referential

stability and low associativity should be optimized to yield high per-

formance on PMEM. As we will see, these two goals seem to be at odds

with each other, and part of the innovation of our hash table design is

that it simultaneously achieves both. Naturally, the third design goal

for a high-performance hash table is compactness, but compactness

also seems at odds with referential stability and low associativity.

A hash table is said to be

stable

if the position where an element

is stored is guaranteed not to change until either the element is

The

write amplication

is the amount of data written to PMEM per insert/delete

divided by the amount of data inserted/deleted. Similarly, the

read amplication

the amount of data read from PMEM per query divided by the amount of data output

by the query.

arXiv:2210.04068v2 [cs.DS] 11 Oct 2022

IcebergHT Dash CLHT

Insertion Deletion

Throughput(M/s)

Pos Query Neg Query

Figure 1: Throughput for insertions, deletions, and queries

(positive and negative) using 16 threads for PMEM hash

tables. The throughput is computed by inserting

𝑁

keys-value pairs where 𝑁is the initial capacity of the hash

table. (Throughput is Million ops/second)

deleted or the table is resized [

]. Stability oers a number

of desirable properties. For example, stability enables simpler

concurrency-control mechanisms and thus reduces the performance

impact of locking. Moreover, since elements are not moved, writing

is minimized, which improves PMEM performance.

The

associativity

of a hash table is the number of locations

where an element is allowed to be stored.

The best known

low-associative (DRAM) hash table is the cuckoo hash table [

In the original design, each element has exactly two locations

in the table where it is allowed to be stored, meaning that the

associativity is two. Low associativity yields a dierent set of

desirable properties—most importantly, it helps search costs. For

example, searching for an element in a cuckoo hash table is fast

because there are only two locations in the table to check. In

addition, low associativity can enable us to further improve query

performance by keeping a small amount of metadata; see Section 2.

In combination, stability can be used to achieve high insertion

throughput in PMEM, where writes are expensive, and low associa-

tivity can be use to achieve high query performance. Furthermore,

we also show how stability enables locking and concurrency-control

mechanisms to be simplied, leading to better multithreaded scaling

and simpler designs for crash consistency.

Unfortunately, there is a tension between stability and low

associativity. If a hash table has associativity

𝛼

, and elements

cannot move once they are inserted, then an unlucky choice of

𝛼

locations for

𝛼

elements can block a

(𝛼+

)

st element from being

inserted. As

𝛼

decreases, the probability of such an unlucky event

increases. Cuckoo hashing reduces the probability of these bad

events by giving up stability via kickout chains, which are chains

of elements that displace each other from one location to another.

Practical implementations [

] generally increase the number

of elements that can be stored in a given location—and thus the

associativity—to reduce the kickout-chain length and increase the

maximum-allowed

load factor

, i.e, the ratio of the total number

of keys in the table to the overall capacity of the table.

Similarly, there is a three-way tension between space eciency,

associativity, and stability. For example, cuckoo hash tables can

be made stable if they are overprovisioned so much that the

Associativity is often associated with caches that restrict the locations an item may

be stored in. Here we refer to data structural associativity, which is a restriction on

how many locations a data structure may choose from to put an item in, even on fully

associative hardware.

kickout-chain length reaches 0. Such overprovisioning directly

decreases space eciency, but it also increases associativity. Linear

probing hash tables are stable (assuming they use tombstones to

implement delete) but, as the load factor approaches 1, the average

probe length for queries goes up, increasing associativity. Other

open-addressing hash tables have a similar space/associativity

trade-o. Chaining hash tables are stable, but they have large

associativity and signicant space overheads. CLHT [

] improves

query performance despite high associativity by storing multiple

items in each node, but this further reduces space eciency.

IcebergHT is based on a new type of hash table, which we call

iceberg hashing

. Iceberg hash tables are the rst to simultaneously

achieve low associativity and stability, and they also have small

space consumption. To date, hash tables have had to choose between

stability (e.g., chaining), low associativity (e.g., cuckoo) or neither

(e.g., Robin Hood [

]). The techniques introduced in this paper

also have ramications to the theoretical study of hash tables—we

present a detailed study of these implications, including closing

various theoretical open problems, in a companion manuscript [

We describe Iceberg hash tables in Section 2.

Results.

In this paper, we introduce Iceberg hashing and its

implementation, IcebergHT. We prove that Iceberg hashing

simultaneously achieves stability and low associativity. Iceberg

hashing is the rst hash-table design to achieve both properties.

These guarantees give IcebergHT excellent performance on PMEM,

as well as on DRAM, and for workloads ranging from read-heavy to

write-heavy. Specically, IcebergHT accesses very few cache lines,

both for queries and insertions, has low CPU cost, and has high

load factor (and thus small space), with high probability. Stability

and low associativity enable simpler concurrency mechanisms, so

that IcebergHT achieves nearly linear scaling with the number of

threads, and it is crash safe on PMEM.

In building IcebergHT, based on our Iceberg hash table, we oer

the following design contributions:

(1)

We show how to achieve an ecient, practical metadata

scheme that is adapted to practical hardware constraints.

The metadata scheme is small enough that the metadata for a

bucket ts in a cache line, improving query performance and

enabling nearly lock-free concurrency, i.e., locks are needed

only for resizing.

(2)

A highly concurrent and thread-safe implementation of

Iceberg hashing. IcebergHT can scale almost linearly with

increasing threads in PMEM, as well as DRAM, experiments.

(3) Fenceless crash safety on PMEM. Achieving crash-safety on

PMEM often requires controlling the order in which cache

lines get ushed to persistent storage, e.g., to ensure that

an undo-log entry gets persisted before the changes to the

hash table get persisted. Since insertions in our hash table

modify only a single cache line, we can achieve crash safety

by simply persisting that cache line.

(4)

A simple, high-performance and concurrent technique

for eciently resizing Iceberg hash tables in a lazy online

manner, thus reducing the worst-case latency of insertions.

Performance.

We evaluated IcebergHT on a system with Intel

Optane memory. We nd that:

(1) Inserts and deletions:

IcebergHT insertions and deletions

are roughly 50% faster than Dash and 2

−

faster than CLHT.

(2) Queries:

IcebergHT positive queries are as fast as CLHT

and negative queries are about 20% faster. IcebergHT queries

are 1.5−2×faster than Dash.

(3) Space:

IcebergHT achieves a space eciency of 85%,

whereas Dash and CLHT have space eciencies of 45% and

33%, respectively.

(4) Scalability:

IcebergHT throughput scales nearly linearly

in all our benchmarks. CLHT also scales roughly linearly to

8 threads but scales slightly less eciently than IcebergHT

from 8 to 16 threads. Dash hits a wall at 8 threads in several

benchmarks.

(5) YCSB:

IcebergHT is anywhere from 1

to 8

faster than

Dash and CLHT in our YCSB benchmarks.

Although IcebergHT is designed for PMEM, we also compare

it to libcuckoo [

], CLHT [

], and TBB [

] in DRAM. We nd

that IcebergHT outperforms these other state-of-the-art DRAM

hash tables on insertions and oers good but not-quite-best query

performance. For example, IcebergHT is almost twice as fast as the

next fastest hash table on insertions in DRAM, and it nearly matches

the fastest hash table on positive queries, but it is only about 75%

as fast as the fastest hash table on negative queries and roughly

60% as fast on deletions. We believe this insertion optimization at

the cost of queries reects the fact that IcebergHT is optimized

to minimize writes, which are expensive in PMEM, resulting in

stellar insertion performance. Thus, IcebergHT is a strong choice

for insertion-heavy workloads in DRAM.

Roadmap.

In the rest of the paper, we discuss the various hash

table designs in and we give an overview of Iceberg hashing and

theoretical guarantees Section 2. In Sections 3 to 6, we present our

implementation of IcebergHT in DRAM and PMEM. Section 7

evaluates IcebergHT and compares it with other hash tables. We

discuss related work in Section 8.

2 ICEBERG HASHING

In this section, we begin by introducing Iceberg Hashing, a new,

stable, low-associativity hash-table design. We then give the

theoretical basis for Iceberg hashing, proving the theorems that

establish its correctness. In subsequent sections, we show how to

exploit Iceberg hashing’s low associativity to implement an ecient

metadata scheme, explain how to make the hashtable concurrent,

how to handle resizes, and how to ensure crash safety.

The goal of this section is to establish the theoretical basis for

the high performance we demonstrate in Section 7. Of particular

note for PMEM is that IcebergHT enables an unmanaged backyard

that results in stability, which we will show is important for both

high performance and crash safety on PMEM. These theoretical

guarantees hold even in the presence of deletes. Previous hash-table

designs have weak or no theoretical guarantees in the presence of

deletes, e.g., cuckoo hashing. An important technical challenge is to

guarantee stability and low associativity, which we simultaneously

achieve in a hash table for the rst time.

Ave ll =ℎMax ll =𝑏Space Eciency =𝑏/ℎ

𝑂(1)𝑂(log 𝑛/log log 𝑛)Θ(log 𝑛/log log 𝑛) ≫ Θ(1)

log 𝑛 𝑂 (log 𝑛)Θ(1)

≫log 𝑛 ℎ +𝑂(√ℎ)1+𝑜(1)

Table 1: The relationship between the average ll, 𝒃, and

the maximum ll, 𝒉, in a balls-and-bins system is well

understood [4, 32].

2.1 From Load Balancing to Iceberg hashing

In this section, we have an overview of the design and design

principles of IcebergHT.IcebergHT is a three-level hash table,

where most items are hashed into a very ecient rst level, some

items are hashed into a less ecient second level, and a few residual

items are hashed into an overow third level. The rst level is

called the front yard and the second and third levels are called the

backyard

. In the remainder of the section, we describe how each

level is designed, and we give theorems to show that IcebergHT

is correct and fast. Interestingly, the bounds in our main theorems

are so tight that we are able to make all parameter choices in our

implementation based on these theorems, as we describe below.

Consider a one-level hash table (which will correspond to the rst

level of IcebergHT). One way to design a hash table is to take an

array and logically break it into

𝑚

buckets of size

𝑏

. As items are

inserted, they are hashed to a random bucket and placed in any free

spot of the bucket. After inserting

𝑛

items, the expected number of

items in each bucket will be

ℎ=𝑛/𝑚

and the

space eciency

the table will be

𝑏𝑚/𝑛=𝑏𝑚/ℎ𝑚 =𝑏/ℎ

. Thus, in order to optimize

space eciency, we want to minimize

𝑏/ℎ

. But

𝑏

is a function of

ℎ

so the choices are not independent, as show in Table 1. Note that in

a balls-and-bins game,

𝑏

is the maximum ll of a bucket, because in

our hash table, each bucket must be congured to be big enough to

handle all insertions into that bucket.

The second observation is that, by using a backyard, we don’t need

to get the number of overows to 0. Specically, we congure the

front yard so that the number of overows will be

𝑂(𝑛/polylog(𝑛))

Then we can use any hash table for the back yard as long as it has

Θ(

)

space eciency. In section 2.2, we show that the overall space

eciency of the hash table will be a remarkable 1+𝑂(1/log 𝑛).

We conclude that

ℎ

should be somewhat greater than

log 𝑛

, so we

set the bucket size to be 64. This bucket size is bigger than a cache line

but IcebergHT does not read the whole bucket. Rather it will keep

metadata to index the bucket. IcebergHT nds itself in a sweet spot

because, as will show below, buckets of size 64 are small enough that

the metadata needed to index the items in a bucket ts in a cache line.

A smaller bucket size oers a poorer choice. Smaller buckets

would either decrease the space eciency, by increasing the number

of buckets needed to prevent overows, or increase the number of

items that land in the less ecient backyard. On the other hand, a

larger bucket size does not decrease overows but the metadata for

bigger buckets no longer ts in a cache line.

2.2 Bounding the Overows

In this section, we describe the theoretical basis for Iceberg hash

tables. The primary theorem we need is a bound on the number of

items that will be placed in the backyard.

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

10 玖币 0人已下载

立即下载

摘要：

IcebergHT:HighPerformancePMEMHashTablesThroughStabilityandLowAssociativityPrashantPandeypandey@cs.utah.eduUniversityofUtahMichaelA.Benderbender@cs.stonybrook.eduStonyBrookUniversityAlexConwayaconway@vmware.comVMwareResearchMartínFarach-Coltonfarach@rutgers.eduRutgersUniversityWilliamKuszmaulkuszmaul...

展开>> 收起<<

IcebergHT High Performance PMEM Hash Tables Through Stability and Low Associativity.pdf

共15页,预览3页

还剩页未读，继续阅读

声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！

IcebergHT High Performance PMEM Hash Tables Through Stability and Low Associativity

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: