Hash Table Design for RDMA:Challenges and Opportunities

Hash Table Design for RDMA: Challenges and Opportunities

arXiv:2606.24073v1 [cs.DC] 23 Jun 2026

Shuchen She, Haipeng Dai∗ Nanjing University [email protected] Abstract Hash tables complete the insertion, lookup, and deletion of a single key in constant time on average, and they are widely used in databases, key-value stores, and network systems. In the Internet of Things (IoT), the number of devices and the volume of sensed data keep growing, so the hash tables that store or index these data consume more and more memory. When a single server runs out of memory, the system can place part of the data in the memory of other nodes. One-sided operations in Remote Direct Memory Access (RDMA) let one machine read and write the memory of another machine directly, with low latency and high bandwidth, and are therefore widely used to build disaggregated memory systems. Deploying a hash table on RDMA-based remote memory exploits the memory of other nodes and thus relieves the capacity limit of a single server. However, this deployment raises three problems. First, one logical hash-table access may translate into one or more remote network accesses, and collision handling and probing further increase the number of RDMA requests. Second, because the remote CPU is bypassed, traditional concurrency control that relies on remote threads no longer applies directly. Third, the limited resources of RDMA network interface cards, such as queues, caches, memory registration, and atomic operations, impose new constraints on hash table structures. This paper focuses on hash table design for RDMA. We review existing work, distill the key challenges, and discuss promising optimization directions and coping strategies, aiming to provide a reference for designing remote hash tables in IoT big-data scenarios.

Keywords: hash table; remote direct memory access; memory disaggregation; concurrency control; Internet of Things

1

Introduction

A hash table maps each key to a storage location through a hash function, and it completes the insertion, lookup, and deletion of a single key in constant time on average. Thanks to this fast key-value access and point-query capability, hash tables are widely used in databases, key-value stores, network systems, and machine learning [1, 2, 3, 4, 5, 6, 7]. First, distributed key-value stores often use hash tables for fast key lookups, for example to manage Internet of Things (IoT) data such as device states and sensor readings [1, 2]. Second, in packet forwarding and flow-table management, hash tables serve exact-match lookups that quickly locate the matching flow entry or forwarding rule [3, 4]. Third, for deduplication, frequent-item detection, and complex event recognition over IoT data streams, structures such as hash tables, filters, and bitmap indexes record the occurrences of data items, narrow the set of candidate events, and reduce unnecessary scans; these capabilities support duplicate detection, hot-item identification, and complex pattern matching [8, 9, 10, 11, 12, 13]. Because hash tables play a central role in so many systems, researchers have proposed a variety of designs that optimize lookup throughput, insertion efficiency, space utilization, concurrent access, and cache friendliness [14, 15, 16, 17, 18]. 1

As IoT deployments scale up, the amount of data that systems must store and index grows rapidly. Sensor data streams are produced continuously and keep accumulating, and the associated metadata, key-value mappings, and query indexes expand with them. In such systems, hash tables typically support the fast location of device identifiers, sensor readings, or metadata, so their capacity requirement grows with both the data volume and the index size. Meanwhile, data-intensive applications already report processing demands at the level of hundreds of terabytes [19]. When the data volume exceeds the memory capacity of a single server, the system can adopt a disaggregated memory architecture and place part of the data and index structures in the memory of other nodes, thereby breaking the single-server capacity limit. How to use the memory of other nodes efficiently to extend the capacity of hash tables and related index structures has therefore become a practical problem in IoT data infrastructure. To access the memory of other nodes efficiently, modern datacenters increasingly adopt Remote Direct Memory Access (RDMA). After memory registration and connection setup, RDMA allows an application to read and write registered remote memory regions directly through the network interface card, bypassing the kernel network stack and the remote CPU on the data path [20, 21]. Compared with traditional TCP/IP-based networking, RDMA usually offers lower access latency, higher throughput, and lower CPU usage [22]. On top of RDMA and other high-speed networks, datacenters have further developed the disaggregated memory architecture [23, 24]. This architecture separates compute resources and memory resources into a compute pool and a memory pool. The compute pool has strong computing power but limited local memory. The memory pool provides abundant memory but weak computing power, and it is generally unsuitable for complex operations [24]. The compute pool accesses the remote memory in the memory pool through RDMA. Under this architecture, the data region of a hash table and its related index structures can reside in the memory pool and be accessed by the compute pool through RDMA. However, directly porting a hash table from a single server to RDMA-based remote memory causes significant performance problems. First, the random accesses of a single-server hash table mostly hit local memory. On remote memory, the same accesses become remote operations such as RDMA READ, RDMA WRITE, or atomic operations, and each remote operation pays a network round trip. The repeated random probing, collision handling, and resizing inside a hash table therefore become much more expensive. Second, RDMA provides only low-level communication primitives. It offers no hash-table-level semantics for lookup, insertion, deletion, migration, or consistency, so the clients must build the remote data layout, the concurrency control scheme, and the consistency mechanisms by themselves. Third, the hardware resources of the RDMA network interface card (RNIC), including queues, caches, address translation, and atomic operations, are limited; these limits constrain the data layout, the access granularity, and the concurrency control of a hash table. This paper studies hash table design for RDMA. We review the design ideas of existing remote index structures and distill the key problems they face on remote memory. Our contributions are threefold. First, we organize existing studies around remote access overhead, concurrency and consistency, and dynamic resizing, and we discuss how filter structures can help optimize remote index lookups. To the best of our knowledge, a systematic survey dedicated to hash table design for RDMA is still missing. Second, we identify several open problems that RDMA hash tables have not fully solved: the high round-trip cost of remote accesses, the network amplification caused by collision handling, the complexity of maintaining consistency once the remote CPU is bypassed, and the difficulty of dynamically resizing large index structures. Third, for these problems we summarize the corresponding optimization directions and propose design principles, including reducing the number of remote accesses, improving data locality, lowering concurrency synchronization overhead, and supporting efficient resizing, as a reference for future research. The rest of this paper is organized as follows. Section 2 introduces the background on RDMA and memory disaggregation, and reviews existing work on hash tables and filters. Section 3 analyzes the main problems in hash table design for RDMA and the corresponding solutions. Section 4 concludes the paper and outlines future research directions. 2

Fig. 1: Illustration of RDMA one-sided operations.

2

Background and Related Work

To set the stage for hash table design for RDMA, this section first introduces the RDMA operation model and the disaggregated memory architecture. It then reviews hash tables for persistent memory, hash tables for RDMA, and related filter studies, highlighting the limitations of existing work that motivate the key challenges discussed in this paper.

2.1

RDMA Operation Model and Disaggregated Memory Architecture

RDMA data transfers are executed mainly by the RNIC, which supports two common classes of operations [25]. The first class is two-sided operations, namely send and receive. Two-sided operations require the receiver to post receive requests in advance; after a message arrives, the remote application usually still has to handle the completion event and run the corresponding application logic. The second class is one-sided operations, including remote read, remote write, and atomic operations. Among the atomic operations, compare-and-swap (CAS) is commonly used for concurrent insertions into RDMA hash tables. A CAS first checks whether the current value at a remote memory location equals an expected (old) value; if so, it replaces the value with a new one. Take SepHash as an example [25]: each entry in a CurSegment is 8 bytes, and clients use RDMA CAS to compete for an empty entry, which guarantees that no two clients can both succeed in writing the same location. One-sided operations need no active participation of the remote CPU; the initiator accesses the registered remote memory region directly through its local RNIC. As shown in Fig. 1, the request of a one-sided operation travels from the local RNIC to the remote RNIC, the remote RNIC accesses the remote memory and returns the result or a completion acknowledgment, and the whole data access bypasses the remote CPU. In an RDMA network, one remote access usually takes microseconds, whereas one local memory access takes nanoseconds; the two differ by a factor of tens to more than a thousand. Reducing the number of remote accesses and the request submission overhead is therefore a primary goal of RDMA data structure design. Because this operation model bypasses the remote CPU and accesses remote memory directly, RDMA has become a key building block of disaggregated memory architectures. Memory disaggregation is a datacenter architecture that deploys compute resources and memory resources separately [23]. The system consists of a compute pool and a memory pool, connected by a high-speed network such as RDMA. The compute pool

3

consists of compute nodes with strong computing power; each node has CPUs and some local memory, but this local memory is relatively small and mainly holds caches, runtime state, and temporary data [26]. The memory pool provides a large amount of remotely accessible memory but has weak computing power; it mainly performs lightweight tasks such as network communication, memory management, and metadata maintenance [27]. Separating compute from memory alleviates the resource waste caused by the fixed coupling of CPU and memory in traditional servers, improves resource utilization, and makes the system more elastic under resource expansion and load changes [26]. Under the disaggregated memory architecture, the compute pool accesses the remote memory in the memory pool through RDMA. The lookup, insertion, and deletion logic of the hash table runs entirely in the compute pool, which performs all accesses through RDMA. The hash table can then exploit the scalability of remote memory and overcome the memory shortage of a single server. To reduce the local overhead of submitting several consecutive RDMA operations, RDMA supports doorbell batching. With this mechanism, the application hands all requests to the RNIC at once, which reduces the number of doorbell writes and the local submission overhead. In addition, when RDMA accesses remote memory, the RNIC must validate and translate the target address according to the address mappings of the registered memory regions. The RNIC caches part of the address translation information internally, which removes most of the translation overhead from each access. When the hash table is large and spans many remote memory pages, the number of address mappings grows accordingly. Once the mappings exceed the capacity of the RNIC’s address-translation cache, the RNIC has to fetch the mapping information again, which increases access latency and degrades overall performance. Beyond RDMA-based memory disaggregation, emerging interconnects such as Compute Express Link (CXL) are also advancing remote and expanded memory. A recent study revisits hash table design for CXL memory and shows that, on a memory medium with higher access latency, different bandwidth characteristics, and coherence overhead, traditional hash tables face new challenges in access granularity, metadata organization, concurrency control, and update mechanisms [28]. This finding indicates that hash table design cannot rely only on the cost model of local memory; it must be re-optimized for the underlying memory interconnect and the characteristics of remote access.

2.2

Hash Tables for Persistent Memory

Before analyzing remote hash tables for RDMA, we briefly review hash table research on persistent memory. Persistent memory is a large-capacity, byte-addressable memory that retains data across power failures. Understanding how hash tables are adapted to its access characteristics helps explain why hash tables must be redesigned again for RDMA. Existing studies improve persistent memory hash tables mainly in terms of resizing, concurrency, recovery, and performance stability. First, researchers have proposed various structures to reduce the data movement caused by resizing. The most straightforward resizing method is full-table rehashing, which remaps all existing items into a new, larger table; this incurs heavy data movement and high tail latency. To address this problem, Level hashing adopts a two-level structure and moves only one level of data during a resize, which reduces the amount of data moved per resize [16]. CCEH borrows the idea of extendible hashing [18, 29] and manages buckets or segments through a directory, so resizing can be performed locally instead of rebuilding the whole table; this lowers the impact of resizing on normal accesses. Second, researchers have also improved persistent memory hash tables from the perspectives of concurrent access and crash recovery. Clevel extends Level hashing with a lock-free concurrent design, which reduces the overhead caused by lock contention [30]. Dash optimizes the crash recovery time and uses lazy recovery to shorten the time before the hash table becomes available again [17]. Halo identifies the write amplification caused by the mismatch between the write granularity of persistent memory and the actual update granularity [31]. Pea hash makes an adaptive trade-off between throughput and space overhead [32]. 4

SEPH targets stable throughput and fine-grained resizing [33]. However, these hash tables are built for local persistent memory and cannot be applied directly to RDMA scenarios. We next introduce hash table designs built on RDMA remote memory.

2.3

Hash Tables for RDMA

Persistent memory hash tables mainly tackle the costs of writes, recovery, and resizing on a locally addressable medium. RDMA instead places hash table accesses on the network path, so each bucket access turns into one or more remote network round trips. A hash table for RDMA must therefore consider not only its own space utilization and concurrency efficiency, but also the number of remote accesses, the access granularity, the semantics of one-sided operations, and the limited computing power of the memory pool. Some RDMA hash tables and key-value systems focus on the remote access efficiency of the lookup path: FaRM, Pilaf, and DrTM organize their tables with hopscotch hashing, cuckoo hashing, and cluster chaining, respectively [20, 21, 34]. Among them, Pilaf mainly uses one-sided RDMA READs to accelerate lookups and reduce remote CPU involvement during lookups, but writes, deletions, and updates still rely on the server CPU or more complex remote coordination. DrTM supports reading and writing remote key-value pairs with one-sided RDMA operations, but its design depends on a transaction system and specific concurrency control mechanisms. In other words, these systems are not designed for a disaggregated memory architecture whose memory pool has almost no computing power. On disaggregated memory, the memory pool only provides remote memory; its weak computing power cannot carry the complex logic of hash table updates, collision handling, and concurrency control. The insertion, deletion, and update logic of a traditional hash structure must therefore move entirely to the clients, and remote modifications must rely on one-sided RDMA operations alone. As a consequence, collision handling, item migration, and consistency maintenance may generate many remote round trips. For example, cuckoo hashing may repeatedly migrate items under high load factors, and each migration may involve remote reads, remote writes, and concurrency checks. In cluster chaining or chained hashing, the location of the next bucket on a collision chain usually depends on the result of the previous read, so the reads can hardly be batched in advance. RACE is an early RDMA hash table designed specifically for disaggregated memory. Its goal is to complete lookup, insertion, update, and resizing with one-sided RDMA operations only, without relying on any computing resources in the memory pool [26]. RACE adopts extendible hashing and organizes the table as one directory plus multiple subtables. Each key maps to two candidate main buckets in a subtable, and two adjacent main buckets share one overflow bucket that holds the items the main buckets cannot accommodate. A main bucket and its shared overflow bucket together form a combined bucket, so a lookup can examine the candidate slots in the main bucket and the shared overflow bucket at once. RACE further uses doorbell batching to submit the related RDMA READs back to back, which reduces the local submission overhead and lets a lookup usually finish within a short remote access path. To cut the remote data transfer during lookups, RACE stores in each bucket a fingerprint derived from the hash value of each key. A client first reads the bucket and compares the fingerprints. If a fingerprint does not match, the client rules out that key directly; only when the fingerprint matches does the client read the full key-value data for an exact comparison. This avoids a large number of unnecessary remote reads. For concurrency, RACE adopts lock-free remote concurrency control, so ordinary lookups and updates run concurrently without acquiring remote locks. Because reads and writes may interleave, a client may observe an intermediate state of an ongoing update; RACE therefore embeds checksums in the key-value data so that the client itself can verify whether a read result is complete and consistent. For resizing, RACE resizes locally: it extends only the subtable that overflows instead of rebuilding the whole table. To avoid extra round trips for directory accesses, RACE caches the directory at the clients. To handle directory caches that become stale after a resize, RACE records metadata in each bucket header for validating the directory mapping. After reading a bucket, the client uses this metadata to 5

check whether the bucket still belongs to the target subtable; if the cached directory turns out to be stale, the client refreshes its local cache and locates the bucket again. RACE may still suffer from resize-induced data movement and remote concurrency control overhead under write-intensive or resize-heavy workloads. To address this problem, SepHash proposes a writeoptimized hash table for disaggregated memory [25]. SepHash observes a bandwidth–latency trade-off in the RDMA access granularity. Small accesses transfer little data per request but inflate the number of requests and the protocol overhead, which lowers bandwidth utilization. Large accesses improve bandwidth utilization but increase the data volume and the latency of each access. Based on this observation, SepHash designs a two-level separate segment structure that migrates entries in batches during a resize instead of one at a time, which reduces the data movement and write amplification during resizing and saves bandwidth. For concurrent writes, SepHash adopts an append-based strategy. An insertion does not overwrite the old entry in place; it appends the new version to an empty entry in the currently writable segment. Multiple versions of the same key are laid out in write order, and newer versions occupy later visible positions. This avoids complex in-place updates and remote lock contention, and it lowers the synchronization overhead of concurrent insertions. On the lookup side, a client identifies the valid result from the state, version, or depth information in the entries, which reduces the re-reads and extra round trips caused by concurrent writes. For lookup optimization, SepHash also uses fingerprints, and it combines filters with client-side caching to cut unnecessary remote accesses, so it keeps good lookup performance while optimizing writes. More recently, several studies further optimize remote index structures from the perspective of key-value systems on disaggregated memory. Outback designs a communication-efficient index for key-value stores on disaggregated memory, focusing on reducing the remote communication during index accesses [35]. FUSEE takes the view of a complete key-value store and studies how to organize the index, the caches, and the data access path when memory is fully disaggregated [36]. These studies do not always propose a new hash table structure, but they further show that on RDMA, a hash table must be co-designed with the system’s access paths, caching mechanisms, and remote communication costs. Besides hash tables, tree-based indexes also exist on disaggregated memory; one example is Sherman, a write-optimized distributed B+ -tree [37]. Tree-based indexes support ordered access and range queries, whereas hash tables fit exact-match point queries. In the broader indexing literature, multi-dimensional indexes include the R-tree, the KD-tree, the Quadtree, and newer structures designed for modern hardware [38]. CHIME further proposes a hybrid index for disaggregated memory that combines the strengths of different index structures to improve cache efficiency and remote access performance [39]. Fig. 2 outlines how typical index structures have evolved from hash tables in local memory, to hash tables on persistent memory, and then to hash tables and filters for RDMA. As the underlying storage medium and access path change, the optimization goals shift accordingly: from purely reducing algorithmic complexity, to reducing the number of remote accesses, controlling the access granularity, lowering the data movement cost, and adapting to hardware resource limits.

2.4

Filters

Besides optimizing the hash table itself, reducing unnecessary accesses to the remote hash table is another important optimization for RDMA. Like hash tables, filters are hash-based data structures, but a filter only answers approximate membership queries and stores no complete key-value data. In practice, a filter usually serves as a pre-check before hash table accesses. When the filter reports that a key does not exist, the client skips the remote hash table entirely; when the filter reports that the key may exist, the client then queries the hash table for an exact answer. Filters are therefore closely related to the lookup optimization of remote hash tables. Common filters include the Bloom filter and the cuckoo filter [40, 41]. A filter keeps no complete raw data; it keeps only bits or fingerprints computed from the keys, so its space cost is far smaller than storing the full key set [42]. The price of this space efficiency is false positives: for a key that does not exist, the 6

Fig. 2: Illustration of the evolution of index structures across different hardware environments.

filter may still report that it exists. In many systems, however, a false positive only causes one extra lookup and never affects the correctness of the result. Filters are therefore commonly used as a pre-check before the actual lookup to cut unnecessary accesses. In IoT, filters are often used to reduce storage and communication costs. For example, in wireless sensor networks, filters assist authentication, membership checking, and duplicate detection; in vehicular networks, filters support content-cache checks to reduce unnecessary cache queries [43, 44]. Some studies build filters specifically for persistent memory. Wormhole filters target the access overhead of filters on persistent memory and reorganize the hash and fingerprint information to reduce that overhead [45, 46]. Beyond optimizing a specific filter structure, other work improves the accuracy of approximate membership queries through encoding. The variable-length encoding framework assigns codes of different lengths to different items, which increases the expressiveness of a filter and lowers its false positive rate [47]. These methods show that filter performance depends not only on the bucket layout and the hash access pattern, but also on how the fingerprints or codes are organized. Filters are especially useful for RDMA hash tables. Because one remote RDMA access costs far more than one local memory access, a client can cache the filter locally and check it before touching the remote hash table. If the filter reports absence, the client ends the lookup immediately and saves one remote RDMA access. If the filter reports possible presence, the client still queries the remote hash table for confirmation. False positives let a few nonexistent keys still trigger remote accesses, but compared with always accessing the remote hash table, a filter sharply reduces the remote round trips spent on unnecessary lookups. For the capacity adjustment of filters and caches under dynamic workloads, the Bamboo filter improves the adaptivity and stability of filter resizing through smooth reconstruction [48, 49], and a lightweight working set size estimation method shows, from the angle of online cache capacity optimization, the importance of adjusting data structure capacity according to the access workload [50].

3

Challenges and Opportunities

This section analyzes the main problems in hash table design for RDMA. For each challenge, we first describe the problem, then show through existing work that the problem exists, and finally discuss possible solutions.

7

3.1

Number of Remote Accesses and Round-Trip Overhead

In local memory, one hash table lookup usually touches only a few buckets or slots, so the access cost is low. When the hash table moves to RDMA remote memory, those local memory accesses become remote network accesses. If one hash operation reads several buckets, it issues several RDMA READs, which increases the lookup latency. The problem is worst in chained hashing and other pointer-linked structures: the address of the next access becomes known only after the previous remote read returns, so the accesses are serial, and the round trips stack up directly on the critical path of the operation. Existing collision-handling schemes all suffer from this remote access amplification under RDMA. Chained hashing reads the nodes along the chain one by one and cannot issue the reads in parallel. Open addressing probes several consecutive slots. Cuckoo hashing can compute its candidate locations in advance, but a triggered eviction may still cause several remote reads. Hash table design for RDMA therefore cannot focus on time complexity alone; it must also account for the number of remote accesses one operation actually issues, and for whether those accesses can run in parallel. Existing RDMA hash tables reduce the remote access overhead by limiting the number of candidate buckets or by batching request submission. These methods, however, still leave the serial access problem unsolved. Future research can explore more predictable access paths, so that the remote locations needed by a lookup or an update are determined as much as possible before the operation starts. It can also study load-aware bucket layouts and collision-handling mechanisms that keep probe sequences short even under high load. The goal is to shrink the data volume of each access, reduce the number of remote accesses, and turn unparallelizable accesses into accesses that are predictable, batchable, or parallel.

3.2

Trade-off Between One-Sided and Two-Sided Operations

RDMA offers two classes of access: one-sided operations and two-sided operations. With one-sided operations, the client reads and writes remote memory directly, which suits remote nodes with weak computing power; however, the client must know the remote data layout and implement the lookup, insertion, deletion, and consistency-check logic by itself. Two-sided operations let the remote CPU take part in hash table operations, which simplifies the client design and eases complex collision handling and concurrency control; however, they consume remote computing resources, and with many clients the server becomes the bottleneck of the whole system. A hash table for RDMA therefore has to choose between the two according to the concrete conditions, such as the available remote computing power. One-sided operations lower the remote CPU overhead and improve scalability. Relying on them exclusively, however, creates new problems: the clients must implement all complex update logic, coordination among multiple clients becomes harder, and some operations need several remote reads and writes to complete. We believe the opportunity for future research lies in more flexible hybrid access mechanisms. Simple lookups and routine updates can keep using one-sided operations to minimize remote involvement. Resizing, collision handling on hot buckets, bulk migration, and complex consistency maintenance can instead use lightweight remote assistance or offloading to data processing units (DPUs) and SmartNICs. This keeps the low CPU overhead of one-sided operations while avoiding pushing all the complex logic onto the clients, and it strikes a better balance among performance, scalability, and implementation complexity.

3.3

Concurrent Access and Data Consistency

In a remote RDMA hash table, multiple clients may run lookups and insertions at the same time, so data consistency under concurrent access must be guaranteed. Unlike the local case, the remote CPU on disaggregated memory usually does not participate, so the clients can hardly rely on remote threads for locking or complex coordination. If remote locks are built on RDMA CAS, every lock and unlock costs a remote round trip, and heavy contention further causes waiting and retries, which greatly increases latency. 8

Moreover, one-sided reads may interleave with concurrent writes, so a client may read a bucket or key-value data that is in the middle of an update; concurrent insertions of the same key may also cause duplicate writes or version conflicts. How to guarantee data consistency is therefore a central problem in RDMA hash table design. Beyond concurrency, a remote hash table on disaggregated memory also has to consider failure recovery and fault tolerance. Aceso studies efficient fault tolerance for key-value stores on disaggregated memory [51], showing that in real systems, remote data structures must also be co-designed with recovery protocols, metadata consistency, and failure handling. Existing studies lower the remote synchronization overhead to some extent through lock-free access, self-verifying fields such as checksums, version information, and atomic updates. These methods, however, still cannot cover all complex concurrency scenarios. Future research can explore lightweight consistency protocols for RDMA, for example based on version numbers, checksums, epochs, or leases, so that a client can decide at low cost whether the remote data is in a stable state. Research can also pursue contention reduction for hot buckets, using write spreading, batched submission, append-based updates, or multi-version management to reduce CAS contention. For concurrent access during resizing, clearer mechanisms are needed for directory cache invalidation, migration state marking, and read/write forwarding, so that correctness is preserved while the remote synchronization and retry costs drop.

3.4

RNIC Address Translation and Remote Memory Layout Constraints

Before RDMA accesses remote memory, the RNIC must validate and translate the target address according to the mappings of the registered memory regions. To lower this cost, the RNIC caches part of the address translation information, but the cache capacity is limited. When the hash table is large and spans many remote memory pages, the RNIC’s address-translation cache misses more often, which increases the access latency. On RDMA remote memory, hash table performance therefore depends on the memory registration method, the page granularity, the address contiguity, and the access locality. Existing work usually mitigates this problem with huge-page registration, contiguous memory layouts, and compact bucket designs. Huge pages reduce the number of pages for the same capacity and thus the number of address mappings. Contiguous layouts reduce random accesses across regions. Compact buckets let a client read a whole bucket in one access and compare multiple slots locally. These methods reduce the address translation and request submission overhead, but they mainly fit relatively static layouts and fixed access patterns. Future work should pursue remote memory layouts that are friendlier to the RNIC. On the one hand, hot buckets, directory entries, and frequently used metadata can be placed together to raise the hit rate of the RNIC’s address-translation cache. On the other hand, hot and cold data can be separated by access frequency to reduce the pressure that large-scale random accesses put on the RNIC cache. Overall, the address translation limits show that RDMA hash table design cannot focus on hash collisions alone; it must include the RNIC hardware resources and the remote memory layout in its optimization objectives.

3.5

Remote Resizing and Elastic Scaling

A hash table usually needs resizing once its load factor rises, and on RDMA remote memory, resizing is more complex than in local memory. First, resizing moves data over the network; with full-table rehashing, it consumes a large amount of RDMA bandwidth and sharply increases the tail latency. Second, multiple clients may have cached old directories, bucket addresses, or capacity information; after a resize these caches may become stale and cause wrong accesses or extra retries. Finally, resizing usually runs concurrently with normal lookups, insertions, and updates, and the system must keep the access results correct while the migration is still in progress. Remote resizing is therefore not only a capacity adjustment problem, but also a problem of data migration, cache consistency, and concurrency control. 9

Existing work eases the cost of full-table rebuilding through local resizing, segment-by-segment migration, and client-side validation, but elastic scaling under high concurrency and dynamic workloads remains hard to solve completely. Future research can explore finer-grained incremental resizing, so that a resize affects only a few hot buckets or subtables while normal requests run in parallel with the migration. Clearer migration state marking and directory cache update mechanisms are also needed, so that a client can tell whether a data item is at the old location, at the new location, or in migration. For workloads with strong load variation, a remote hash table should further support load-aware scaling and reorganization of hot and cold data, limiting the bandwidth consumption while reducing the impact of resizing on throughput and tail latency.

4

Conclusion

In this paper, we surveyed hash table design for RDMA-based remote memory. Starting from the large-scale storage and fast lookup demands created by ever-growing IoT data, we explained why it makes sense to deploy hash tables on RDMA remote memory when the memory capacity and scalability of a single server fall short. On this basis, we reviewed hash table research for RDMA remote memory and discussed how filters reduce unnecessary lookups. We then distilled five key challenges: the number of remote accesses and round-trip overhead, the trade-off between one-sided and two-sided operations, concurrent access and data consistency, RNIC address translation and remote memory layout constraints, and remote resizing and elastic scaling. Future work can study dedicated hash table structures for RDMA remote memory and explore how to balance fewer remote round trips, lower RNIC address translation overhead, lock-free concurrent access, and localized resizing, so as to exploit the high bandwidth and low latency of RDMA more fully.

References [1] Josiah L. Carlson. Redis in action. Manning Publications Co., 2013. URL https://www.oreilly. com/library/view/redis-in-action/9781617290855/. [2] Miguel Ángel Arévalo-Gómez, Eduardo Carrillo Zambrano, Luis Felipe Herrera-Quintero, and Jaime Chavarriaga. Water wells monitoring solution in rural zones using IoT approaches and cloud-based real-time databases. In Proceedings of the Euro American Conference on Telematics and Information Systems, pages 1–5, 2018. URL https://doi.org/10.1145/3293614.3293650. [3] Tianlong Li, Tian Song, and Yating Yang. iStack: A general and stateful name-based protocol stack for named data networking. In Proceedings of the 21st USENIX Symposium on Networked Systems Design and Implementation, pages 267–280, 2024. URL https://www.usenix.org/conference/nsdi24/ presentation/li-tianlong. [4] Sylvia Ratnasamy, Andrey Ermolinskiy, and Scott Shenker. Revisiting IP multicast. In Proceedings of the Conference on Applications, Technologies, Architectures, and Protocols for Computer Communications, pages 15–26, 2006. URL https://doi.org/10.1145/1159913.1159917. [5] Shuang Yu, Xiongfei Li, Siru Sun, Hancheng Wang, Xiaoli Zhang, and Shiping Chen. IBMvSVM: An instance-based multi-view SVM algorithm for classification. Applied Intelligence, 52(1):14739–14755, 2022. URL https://doi.org/10.1007/s10489-021-03101-y. [6] Shuang Yu, Xiongfei Li, Hancheng Wang, Xiaoli Zhang, and Shiping Chen. BIDI: A classification algorithm with instance difficulty invariance. Expert Systems with Applications, 165(1):1–13, 2021. URL https://doi.org/10.1016/j.eswa.2020.113920.

10

[7] Zeyu Wang, Xiongfei Li, Haoran Duan, Xiaoli Zhang, and Hancheng Wang. Multifocus image fusion using convolutional neural networks in the discrete wavelet transform domain. Multimedia Tools and Applications, 78(24):34483–34512, 2019. URL https://doi.org/10.1007/s11042-019-08070-6. [8] Haipeng Dai, Muhammad Shahzad, Alex X. Liu, and Yuankun Zhong. Finding persistent items in data streams. Proceedings of the VLDB Endowment, 10(4):289–300, 2016. URL https://doi.org/10. 14778/3025111.3025114. [9] Shizhe Liu, Haipeng Dai, Shaoxu Song, Meng Li, Jingsong Dai, Rong Gu, and Guihai Chen. ACER: Accelerating complex event recognition via two-phase filtering under range bitmap-based indexes. In Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pages 1933–1943, 2024. URL https://doi.org/10.1145/3637528.3671814. [10] Jiaqian Liu, Haipeng Dai, Rui Xia, Meng Li, Ran Ben Basat, Rui Li, and Guihai Chen. DUET: A generic framework for finding special quadratic elements in data streams. In Proceedings of the ACM Web Conference, pages 2989–2997, 2022. URL https://doi.org/10.1145/3485447.3512019. [11] Shizhe Liu, Haipeng Dai, Shaoxu Song, Meng Li, Jingsong Dai, Rong Gu, and Guihai Chen. Accelerating complex event recognition via range bitmap-based indexes with window-wise filtering. IEEE Transactions on Knowledge and Data Engineering, 38(6):3385–3400, 2026. URL https://doi.org/10.1109/TKDE.2026.3679736. [12] Shuang Yu, Xiongfei Li, Hancheng Wang, Xiaoli Zhang, and Shiping Chen. C_CART: An instance confidence-based decision tree algorithm for classification. Intelligent Data Analysis, 25(4):929–948, 2021. URL https://doi.org/10.3233/IDA-205361. [13] Shuang Yu, Xiongfei Li, Xiaoli Zhang, and Hancheng Wang. The OCS-SVM: An objective-costsensitive SVM with sample-based misclassification cost invariance. IEEE Access, 7(1):118931–118942, 2019. URL https://doi.org/10.1109/ACCESS.2019.2933437. [14] Witold Litwin. Linear hashing: A new tool for file and table addressing. In Proceedings of the International Conference on Very Large Data Bases, pages 212–223, 1980. URL https://doi.org/ 10.5555/1286887.1286911. [15] Maurice Herlihy, Nir Shavit, and Moran Tzafrir. Hopscotch hashing. In Proceedings of the International Symposium on Distributed Computing, pages 350–364, 2008. URL https://doi.org/10.1007/ 978-3-540-87779-0_24. [16] Pengfei Zuo, Yu Hua, and Jie Wu. Write-optimized and high-performance hashing index scheme for persistent memory. In Proceedings of the 13th USENIX Symposium on Operating Systems Design and Implementation, pages 461–476, 2018. URL https://www.usenix.org/conference/osdi18/ presentation/zuo. [17] Baotong Lu, Xiangpeng Hao, Tianzheng Wang, and Eric Lo. Dash: Scalable hashing on persistent memory. Proceedings of the VLDB Endowment, 13(8):1147–1161, 2020. URL https://doi.org/10. 14778/3389133.3389134. [18] Moohyeon Nam, Hokeun Cha, Young ri Choi, Sam H. Noh, and Beomseok Nam. Write-optimized dynamic hashing for persistent memory. In Proceedings of the 17th USENIX Conference on File and Storage Technologies, pages 31–44, 2019. URL https://www.usenix.org/conference/fast19/ presentation/nam.

11

[19] Gaurav Gupta, Minghao Yan, Benjamin Coleman, Bryce Kille, R. A. Leo Elworth, Tharun Medini, Todd Treangen, and Anshumali Shrivastava. Fast processing and querying of 170TB of genomics data via a repeated and merged Bloom filter (RAMBO). In Proceedings of the International Conference on Management of Data, pages 2226–2234, 2021. URL https://doi.org/10.1145/3448016. 3457333. [20] Aleksandar Dragojević, Dushyanth Narayanan, Miguel Castro, and Orion Hodson. FaRM: Fast remote memory. In Proceedings of the 11th USENIX Conference on Networked Systems Design and Implementation, pages 401–414, 2014. URL https://www.usenix.org/conference/nsdi14/ technical-sessions/dragojevi%C4%87. [21] Christopher Mitchell, Yifeng Geng, and Jinyang Li. Using one-sided RDMA reads to build a fast, CPU-efficient key-value store. In Proceedings of the USENIX Annual Technical Conference, pages 103–114, 2013. URL https://www.usenix.org/conference/atc13/technical-sessions/ presentation/mitchell. [22] Anuj Kalia, Michael Kaminsky, and David G. Andersen. Design guidelines for high performance RDMA systems. In Proceedings of the USENIX Annual Technical Conference, pages 437–450, 2016. URL https://www.usenix.org/conference/atc16/technical-sessions/presentation/kalia. [23] Peter Xiang Gao, Akshay Narayan, Sagar Karandikar, João Carreira, Sangjin Han, Rachit Agarwal, Sylvia Ratnasamy, and Scott Shenker. Network requirements for resource disaggregation. In Proceedings of the 12th USENIX Symposium on Operating Systems Design and Implementation, pages 249–264, 2016. URL https://www.usenix.org/conference/osdi16/technical-sessions/ presentation/gao. [24] Hasan Al Maruf and Mosharaf Chowdhury. Memory disaggregation: Advances and open challenges. ACM SIGOPS Operating Systems Review, 57(1):29–37, 2023. URL https://doi.org/10.1145/ 3606557.3606562. [25] Xinhao Min, Kai Lu, Pengyu Liu, Jiguang Wan, Changsheng Xie, Daohui Wang, Ting Yao, and Huatao Wu. SepHash: A write-optimized hash index on disaggregated memory via separate segment structure. Proceedings of the VLDB Endowment, 17(5):1091–1104, 2024. URL https://doi.org/10.14778/ 3641204.3641218. [26] Pengfei Zuo, Jiazhao Sun, Liu Yang, Shuangwu Zhang, and Yu Hua. One-sided RDMA-conscious extendible hashing for disaggregated memory. In Proceedings of the USENIX Annual Technical Conference, pages 15–29, 2021. URL https://www.usenix.org/conference/atc21/presentation/ zuo. [27] Shizhe Liu, Haipeng Dai, Meng Li, Yuemeng Zhang, Shaoxu Song, Zhifeng Bao, Hancheng Wang, Xiaofeng Gao, and Guihai Chen. When complex event recognition meets cloud-native architectures. In Proceedings of the 42nd IEEE International Conference on Data Engineering, pages 2294–2307, 2026. URL https://josehokec.github.io/ICDE26_final.pdf. [28] Hancheng Wang, Haipeng Dai, Shusen Chen, and Guihai Chen. Rethinking hash tables: Challenges and opportunities with Compute Express Link (CXL). In Proceedings of the ACM Turing Award Celebration Conference, pages 23–27, 2024. URL https://doi.org/10.1145/3674399.3674418. [29] Ronald Fagin, Jürg Nievergelt, Nicholas Pippenger, and H. Raymond Strong. Extendible hashing—a fast access method for dynamic files. ACM Transactions on Database Systems, 4(3):315–344, 1979. URL https://doi.org/10.1145/320083.320092. 12

[30] Zhangyu Chen, Yu Hua, Bo Ding, and Pengfei Zuo. Lock-free concurrent level hashing for persistent memory. In Proceedings of the USENIX Annual Technical Conference, pages 799–812, 2020. URL https://www.usenix.org/conference/atc20/presentation/chen. [31] Daokun Hu, Zhiwen Chen, Wenkui Che, Jianhua Sun, and Hao Chen. Halo: A hybrid PMem-DRAM persistent hash index with fast recovery. In Proceedings of the International Conference on Management of Data, pages 1049–1063, 2022. URL https://doi.org/10.1145/3514221.3517884. [32] Zhuoxuan Liu and Shimin Chen. Pea hash: A performant extendible adaptive hashing index. Proceedings of the ACM on Management of Data, 1(1):1–25, 2023. URL https://doi.org/10.1145/ 3588962. [33] Chao Wang, Junliang Hu, Tsun-Yu Yang, Yuhong Liang, and Ming-Chang Yang. SEPH: Scalable, efficient, and predictable hashing on persistent memory. In Proceedings of the 17th USENIX Symposium on Operating Systems Design and Implementation, pages 479–495, 2023. URL https://www.usenix. org/conference/osdi23/presentation/wang-chao. [34] Xingda Wei, Jiaxin Shi, Yanzhe Chen, Rong Chen, and Haibo Chen. Fast in-memory transaction processing using RDMA and HTM. In Proceedings of the 25th Symposium on Operating Systems Principles, pages 87–104, 2015. URL https://doi.org/10.1145/2815400.2815419. [35] Yi Liu, Minghao Xie, Shouqian Shi, Yuanchao Xu, Heiner Litz, and Chen Qian. Outback: Fast and communication-efficient index for key-value store on disaggregated memory. Proceedings of the VLDB Endowment, 18(2):335–348, 2024. URL https://doi.org/10.14778/3705829.3705849. [36] Jiacheng Shen, Pengfei Zuo, Xuchuan Luo, Tianyi Yang, Yuxin Su, Yangfan Zhou, and Michael R. Lyu. FUSEE: A fully memory-disaggregated key-value store. In Proceedings of the 21st USENIX Conference on File and Storage Technologies, pages 81–97, 2023. URL https://www.usenix.org/ conference/fast23/presentation/shen. [37] Qing Wang, Youyou Lu, and Jiwu Shu. Sherman: A write-optimized distributed B+Tree index on disaggregated memory. In Proceedings of the International Conference on Management of Data, pages 1033–1048, 2022. URL https://doi.org/10.1145/3514221.3517824. [38] Mingxin Li, Hancheng Wang, Haipeng Dai, Meng Li, Chengliang Chai, Rong Gu, Feng Chen, Zhiyuan Chen, Shuaituan Li, Qizhi Liu, and Guihai Chen. A survey of multi-dimensional indexes: Past and future trends. IEEE Transactions on Knowledge and Data Engineering, 36(8):3635–3655, 2024. URL https://doi.org/10.1109/TKDE.2024.3364183. [39] Xuchuan Luo, Jiacheng Shen, Pengfei Zuo, Xin Wang, Michael R. Lyu, and Yangfan Zhou. CHIME: A cache-efficient and high-performance hybrid index on disaggregated memory. In Proceedings of the ACM SIGOPS 30th Symposium on Operating Systems Principles, pages 110–126, 2024. URL https://doi.org/10.1145/3694715.3695959. [40] Burton H. Bloom. Space/time trade-offs in hash coding with allowable errors. Communications of the ACM, 13(7):422–426, 1970. URL https://doi.org/10.1145/362686.362692. [41] Bin Fan, Dave G. Andersen, Michael Kaminsky, and Michael D. Mitzenmacher. Cuckoo filter: Practically better than Bloom. In Proceedings of the 10th ACM International Conference on Emerging Networking Experiments and Technologies, pages 75–88, 2014. URL https://doi.org/10.1145/ 2674005.2674994.

13

[42] Li Fan, Pei Cao, Jussara Almeida, and Andrei Z. Broder. Summary cache: A scalable wide-area web cache sharing protocol. IEEE/ACM Transactions on Networking, 8(3):281–293, 2000. URL https://doi.org/10.1109/90.851975. [43] Bacem Mbarek, Nabil Sahli, and Nafaâ Jabeur. BFAN: A Bloom filter-based authentication in wireless sensor networks. In Proceedings of the 14th International Wireless Communications & Mobile Computing Conference, pages 304–309, 2018. URL https://doi.org/10.1109/IWCMC.2018.8450292. [44] Amit Dua, Megha Shishodia, Nikhil Kumar, Gagangeet Singh Aujla, and Neeraj Kumar. Bloom filter based efficient caching scheme for content distribution in vehicular networks. In Proceedings of the IEEE International Conference on Communications Workshops, pages 1–6, 2019. URL https: //doi.org/10.1109/ICCW.2019.8756669. [45] Hancheng Wang, Haipeng Dai, Rong Gu, Youyou Lu, Jiaqi Zheng, Jingsong Dai, Shusen Chen, Zhiyuan Chen, Shuaituan Li, and Guihai Chen. Wormhole filters: Caching your hash on persistent memory. In Proceedings of the 19th European Conference on Computer Systems, pages 456–471, 2024. URL https://doi.org/10.1145/3627703.3629590. [46] Hancheng Wang, Haipeng Dai, Shusen Chen, Meng Li, Rong Gu, Youyou Lu, Chengxun Wu, Jiaqi Zheng, Lexi Xu, and Guihai Chen. Parallel wormhole filters: High-performance approximate membership query data structures for persistent memory. IEEE Transactions on Parallel and Distributed Systems, 36(11):2229–2246, 2025. URL https://doi.org/10.1109/TPDS.2025.3605780. [47] Haipeng Dai, Hancheng Wang, Zhipeng Chen, Jiaqi Zheng, Meng Li, Rong Gu, Chen Tian, and Wanchun Dou. Variable-length encoding framework: A generic framework for enhancing the accuracy of approximate membership queries. In Proceedings of the IEEE International Conference on Data Mining, pages 61–70, 2023. URL https://doi.org/10.1109/ICDM58522.2023.00015. [48] Hancheng Wang, Haipeng Dai, Shusen Chen, Meng Li, Rong Gu, Huayi Chai, Jiaqi Zheng, Zhiyuan Chen, Shuaituan Li, Xianjun Deng, and Guihai Chen. Bamboo filters: Make resizing smooth and adaptive. IEEE/ACM Transactions on Networking, 32(5):3776–3791, 2024. URL https://doi.org/ 10.1109/TNET.2024.3403997. [49] Hancheng Wang, Haipeng Dai, Meng Li, Jun Yu, Rong Gu, Jiaqi Zheng, and Guihai Chen. Bamboo filters: Make resizing smooth. In Proceedings of the 38th IEEE International Conference on Data Engineering, pages 979–991, 2022. URL https://doi.org/10.1109/ICDE53745.2022.00078. [50] Rong Gu, Simian Li, Haipeng Dai, Hancheng Wang, Yili Luo, Bin Fan, Ran Ben Basat, Ke Wang, Zhenyu Song, Shouwei Chen, Beinan Wang, Yihua Huang, and Guihai Chen. Adaptive online cache capacity optimization via lightweight working set size estimation at scale. In Proceedings of the USENIX Annual Technical Conference, pages 467–484, 2023. URL https://www.usenix.org/conference/ atc23/presentation/gu. [51] Zhisheng Hu, Pengfei Zuo, Yizou Chen, Chao Wang, Junliang Hu, and Ming-Chang Yang. Aceso: Achieving efficient fault tolerance in memory-disaggregated key-value stores. In Proceedings of the ACM SIGOPS 30th Symposium on Operating Systems Principles, pages 127–143, 2024. URL https://doi.org/10.1145/3694715.3695951.

14