# MementoHash: A Stateful, Minimal Memory, Best Performing Consistent Hash
Algorithm

Massimo Coluzzi, Amos Brocco, Alessandro Antonucci, Tiziano Leidi
Department of Innovative Technologies,
University of Applied Sciences and Arts of Southern Switzerland, Lugano,
Switzerland
Email:
<EMAIL_ADDRESS>
###### Abstract

Consistent hashing is used in distributed systems and networking applications
to spread data evenly and efficiently across a cluster of nodes. In this
paper, we present _MementoHash_ , a novel consistent hashing algorithm that
eliminates known limitations of state-of-the-art algorithms while keeping
optimal performance and minimal memory usage. We describe the algorithm in
detail, provide a pseudo-code implementation, and formally establish its solid
theoretical guarantees. To measure the efficacy of _MementoHash_ , we compare
its performance, in terms of memory usage and lookup time, to that of state-
of-the-art algorithms, namely, _AnchorHash_ , _DxHash_ , and _JumpHash_.
Unlike _JumpHash_ , _MementoHash_ can handle random failures. Moreover,
_MementoHash_ does not require fixing the overall capacity of the cluster (as
_AnchorHash_ and _DxHash_ do), allowing it to scale indefinitely. The number
of removed nodes affects the performance of all the considered algorithms.
Therefore, we conduct experiments considering three different scenarios:
stable (no removed nodes), one-shot removals (90% of the nodes removed at
once), and incremental removals. We report experimental results that averaged
a varying number of nodes from ten to one million. Results indicate that our
algorithm shows optimal lookup performance and minimal memory usage in its
best-case scenario. It behaves better than _AnchorHash_ and _DxHash_ in its
average-case scenario and at least as well as those two algorithms in its
worst-case scenario.

###### Index Terms:

Consistent hashing, load balancing, scalability.

##  I Introduction

A distributed system consists of multiple nodes that manage different kind of
data, such as files for distributed storage, records for distributed
databases, or requests for load balancers. An even distribution of these data
units among the nodes is necessary to prevent specific nodes from being
overloaded. Consistent hashing is widely known for its ability to evenly
allocate the load across the system and minimize the number of data units that
need to be remapped during cluster scaling [1]. After the introduction of
cloud infrastructures, _elasticity_ , namely the ability to scale quickly and
efficiently, has become a concept of paramount importance. Elasticity demands
efficient and high-performing consistent hashing algorithms because data units
must be redistributed to maintain balance as nodes are added or removed. Each
data unit is uniquely identified by a key, and each node is mapped to a
sequential integer called a bucket. In the considered scenario, each node in a
cluster of size $n$ is mapped to a unique value in the range $[0,n\\!-\\!1]$.
The lookup operation maps each key to a bucket in a deterministic way,
therefore invoking the lookup operation on the same key must return the same
bucket as long as such a bucket is available. The challenge is to efficiently
map keys to buckets, knowing that each key represents a data unit and each
bucket represents a node in a distributed system. The scientific literature
proposes several algorithms that strive to obtain the best balance between
desirable properties, algorithmic complexity, and real-world performance. Our
contribution, named _MementoHash_ , represents a novel consistent hashing
algorithm that eliminates known limitations of state-of-the-art algorithms
while keeping optimal performance and minimal memory usage.

##  II Related work

Consistent hashing algorithms are not a novel concept: the first example in
the literature can be dated back to $1996$, when Thaler and Ravishankar
proposed Rendezvous [2][3], while the term was first used by Karger and co-
authors in $1997$ [4]. Other consistent hashing algorithms for non peer-to-
peer environments followed. Overall, the most prominent ones, published
between $1996$ and $2021$, are:

  1. -

Rendezvous: published by Thaler and Ravishankar in 1996 [2][3].

  2. -

Consistent Hashing Ring: published by Karger et al. in 1997 [4][5].

  3. -

JumpHash: published by Lamping and Veach in 2014 [6].

  4. -

Multi-probe: published by Appleton and O’Reilly in 2015 [7].

  5. -

Maglev: published by Eisenbud in 2016 [8].

  6. -

AnchorHash: published by Mendelson et al. in 2020 [9].

  7. -

DxHash: published by Dong and Wang in 2021 [10].

For the sake of conciseness, in the following we omit the hash suffix from the
names of the aforementioned algorithms (e.g., Memento instead of MementoHash).

In a previous work [11][12], we implemented all the above algorithms in Java
together with a benchmark tool specifically designed for consistent hashing
algorithms [13]. We compared them against the following metrics:

  * -

memory usage: the amount of memory used to store the internal data structure.

  * -

initialization time: the time needed to initialize the internal data
structure.

  * -

lookup time: the time needed to map a given key to its related bucket.

  * -

resize time: the time to change the internal data structure when adding or
removing buckets.

  * -

balance: the ability to spread the keys evenly among the buckets.

  * -

resize balance: the ability to spread the keys evenly among the buckets after
resizing the cluster.

  * -

monotonicity: the ability to move only the keys involved in the resizing.

We found that Anchor, Dx, and Jump outmatch the other algorithms in all the
considered metrics. In particular, Jump was shown to be the best-performing
algorithm since it does not use any internal data structure. It uses minimal
memory and is the fastest in any time metric because it does not access memory
and runs at CPU speed. Jump allows only the last inserted bucket to be
removed, meaning that it is not able to handle the failure of a random node in
the cluster. In practical settings, any computational resource, whether
hardware or software-based, has the potential to experience failures. Even in
failure-transparent architectures, where every node is guaranteed to be highly
available, network failures can make one or more nodes unreachable. Therefore,
despite its excellent performance, Jump is an impractical solution for
production environments. Anchor and Dx address this limitation by using an
internal data structure to keep track of all the cluster nodes (both working
and not working) which causes them to use much more memory than Jump and to be
slower in all the time metrics. Moreover, those two algorithms require the
overall capacity of the cluster to be defined during initialization. The
capacity cannot change during execution, forcing an upper bound to the
scalability of the cluster. We argue that it is unnecessary to maintain a
record of all potential nodes, even those that are not operational. While
conducting our comparative analysis, we pondered whether it would be feasible
to harness the outstanding capabilities of _Jump_ by incorporating a minimal
data structure that only remembers the nodes that have failed. This line of
thinking led us to the creation of _MementoHash_ , which overcomes the
limitations of _Jump_ while maintaining nearly identical performance.

##  III Preliminaries

As previously mentioned, we consider the problem of distributing data units,
which are uniquely identified by keys, to buckets. In this context we commonly
turn our attention to hashing algorithms, which are deterministic functions
that take an arbitrary amount of data as input and produce a fixed length
output called hash value or digest. The digest, usually a number, can be
mapped to a value in the interval $[0,n\\!-\\!1]$ using modular algebra.
Hashing algorithms serve the purpose of evenly distributing keys among
buckets, ensuring a balanced load distribution across all buckets.
Additionally, they facilitate efficient determination of the mapping between
keys and buckets. However, when the number of buckets is altered, a simple
approach based on hash functions and modular algebra will result in a
significant remapping of keys to different buckets. Consequently, a
distributed system experiences the relocation of nearly all its data units
across nodes each time a node joins or departs from the cluster. To address
this problem, consistent hashing solutions have been devised. It is a class of
distributed hashing algorithms that provide the following properties:

  * balance: keys are evenly distributed among buckets. Given $k$ keys and $n$ buckets, ideally, $\frac{k}{n}$ keys are mapped to each bucket.

  * minimal disruption: the same key is always mapped to the same bucket as long as such a bucket is available. When a bucket leaves the cluster, only the keys mapped to such a bucket will move to other buckets, while keys previously mapped to the other buckets will not move.

  * monotonicity: when a new bucket is added, keys only move from an existing bucket to the new one, but not from an existing one to another. Given $k$ keys and $n$ buckets, ideally, only $\frac{k}{n+1}$ keys should move to the new bucket.

Since many consistent hashing algorithms rely on non-consistent hashing
functions we deem important to introduce the following assumption.

######  Note. III.1.

(Uniform hash functions) We assume the hash functions used inside the
consistent hashing algorithms to produce a uniform distribution of the keys.

###  III-A Notation

As stated in previous sections, we can map each node of a distributed system
to an integer in the range $[0,n\\!-\\!1]$ called a _bucket_. Therefore, we
can represent a cluster as an array of buckets.

######  Def. III.2 (b-array).

With the term _b-array_ we refer to the array of buckets representing a
cluster of nodes in a distributed system. A _b-array_ $\mathcal{N}$ of size
$n$ is an array of integers where every position contains a value in the range
$[0,n\\!-\\!1]$

######  Def. III.3 (working bucket).

With the term working bucket we identify a bucket related to a working node.

Moving forward, this paper will adhere to the following notation:

######  Def. III.4 (notation).

We will use $\subset$ to denote a strict inclusion and $\subseteq$ to denote a
non-strict inclusion.
Given a b-array:

  * -

$\mathcal{N}:=[0,\dots,n\\!-\\!1]$ is the content of the b-array and
$n:=|\mathcal{N}|$ is its size.

  * -

$\mathcal{W}\subseteq\mathcal{N}$ is the set of working buckets.

  * -

$\mathcal{W}_{b}:=\mathcal{W}\backslash\\{b\\}$ is the set of working buckets
after removing bucket $b$.

  * -

$\langle b\rightarrow c,p\rangle$ represents the replacement of the failing
bucket $b$ with the bucket $c$ (more details in Sec. V).

  * -

$\mathcal{R}:=\\{\langle b\rightarrow
c,p\rangle|b,c\\!\in\\!\mathcal{N},p\\!\leq\\!n\\}$ is the set of replacements
and $r:=|\mathcal{R}|$ is the number of replacements.

##  IV State of the art

In this section, we will briefly introduce the Jump, Anchor, and Dx
algorithms. We will discuss their strengths and weaknesses to allow a better
understanding of the improvements introduced by Memento.

###  IV-A The Jump algorithm

By representing a cluster as a b-array, Jump [6] assumes every bucket to be
working and the b-array to be sorted.

$0$$1$$2$$3$$\ldots$$n\\!-\\!2$$n\\!-\\!1$ Figure 1: Jump’s representation of
a cluster

Jump assumes buckets are sorted from $0$ to $n\\!-\\!1$ and cannot change
their position. Therefore, it only needs to store the size of the b-array
(see, e.g., Fig. 1). When the cluster scales up, Jump increases the buckets
count, assuming new buckets to be added to the tail of the b-array with values
$n$, $n\\!+\\!1$, $\ldots$ (see, e.g., Fig. 2).

$0$$1$$2$$3$$\ldots$$n\\!-\\!2$$n\\!-\\!1$$n$$n\\!+\\!1$ Figure 2: Jump Hash:
Adding two buckets

When the cluster scales down, Jump reduces the buckets count, assuming buckets
to be removed from the tail, first $n\\!-\\!1$, then $n\\!-\\!2$, … (see,
e.g., Fig. 3)

$0$$1$$2$$3$$\ldots$$n\\!-\\!2$$n\\!-\\!1$ Figure 3: Jump Hash: Removing two
buckets

The algorithm takes a key and the size of the b-array as input parameters and
returns the bucket such a key belongs (e.g., $jump(key,n)\rightarrow
b\in\mathcal{N}$). Its output depends only on the provided parameters. Jump
holds the properties of balance, monotonicity, and minimal disruption. As an
example, let us assume $jump(key,10)\rightarrow 5$, then also
$jump(key,9)\rightarrow 5$, $jump(key,8)\rightarrow 5$, $\ldots$,
$jump(key,6)\rightarrow 5$. The bucket returned by Jump will change only when
$5$ is no more a working bucket (e.g., $jump(key,5)\rightarrow 2$ ). Each key
is always mapped to the same bucket until such a bucket is removed. This
behavior describes the property of minimal disruption. Jump operates without
an internal state and does not perform any memory access, allowing it to run
at CPU speed. In spite of its slower theoretical growth rate, this
characteristic makes Jump the fastest algorithm in practical terms [11][12].
In an ideal scenario where failures are absent, it would be possible to scale
our cluster by adding and removing buckets in a _Last-In-First-Out_ (LIFO)
order. In such a case, Jump would be the most effective consistent-hashing
algorithm available. However, in real-world environments, any node can fail at
any time. Furthermore, we could need to shut down for maintenance the node
mapped to the bucket $0$. Jump does not allow you to do that unless you shut
down the entire cluster. This limitation makes Jump impractical for real-world
environments.

###  IV-B The Anchor algorithm

To address the limitations of Jump, Anchor [9] represents all the possible
buckets up to the maximum size reachable by the cluster. This choice allows
Anchor to mark which buckets are working and which are not, allowing it to
handle random failures (see, e.g., Fig. 4). Let us call $W_{b}$, the set of
working buckets remaining after removing $b$. When a bucket fails, the
algorithm maps $\mathcal{W}_{b}$ to $b$. Every removed bucket $b$ is mapped to
the set of buckets that were working after the removal of $b$. The basic idea
behind Anchor is to use a hash function to map a key to one of the buckets $b$
in the cluster. If $b$ is working, the algorithm is done. Otherwise, the key
is mapped to a bucket $c$ in the subset of buckets $\mathcal{W}_{b}$ that were
working when $b$ was removed. The algorithm iterates the same logic on $c$. If
$c$ is working, the algorithm is done. Otherwise, the key is mapped to a
bucket $d$ in the subset of buckets $\mathcal{W}_{c}$ that worked when $c$ was
removed. Since $c\in\mathcal{W}_{b}$, $c$ worked when $b$ was removed.
Therefore, calling $\mathcal{W}$ the set of working buckets, we have that
$\mathcal{W}\subset\mathcal{W}_{c}\subset\mathcal{W}_{b}$. Every iteration
will work on a smaller set, and a working bucket will eventually be found.

$0$$1$$2$$3$$4$$5$$\ldots$$n\\!-\\!2$$n\\!-\\!1$$n$$n\\!+\\!1$$\ldots$$a\\!-\\!2$$a\\!-\\!1$
Figure 4: Cluster representation for Anchor

The described solution takes $O(ln(\frac{a}{w}))$ iterations to look up a key,
where $a$ is the overall capacity of the cluster (working and nonworking
buckets). Still, it uses a considerable amount of memory. To overcome this
issue, the authors of Anchor suggest an in-place solution that leverages four
arrays of integers to store the required information. The in-place solution
uses less memory but takes $O([ln(\frac{a}{w})]^{2})$ steps to perform a
lookup. Both versions rely on the assumption of keeping track of all the
available nodes in the cluster. The size of the internal data structure cannot
change to ensure monotonicity and minimal disruption. Therefore, from start
the arrays must be big enough to contain any possible buckets. Foreseeing from
the early beginning the maximum size reachable by the cluster is not a trivial
task. Capacity can be ensured by instantiating large arrays, but
overestimating will consume resources and slow down performance.

###  IV-C The Dx algorithm

Dx [10] reduces the memory consumption by using a bit-array to mark the
availability of the buckets. It is a remarkable improvement compared to the
four integer arrays used by Anchor. Still, it uses an amount of memory
proportional to the overall capacity of the cluster. In order to compute a
position in the range $[0,a\\!-\\!1]$, Dx uses a pseudo-random function $R$
initialized with the key as the seed. Accordingly, a sequence of buckets in
the form $R(k),R(R(k)),R(R(R(k)))...$ can be generated, and the first working
bucket is chosen (see, e.g., Fig. 5). Dx trades the improvement in memory
consumption in terms of lookup time. It takes $O(\frac{a}{w})$ steps to
perform a lookup while suffering from the same limitations of Anchor (i.e.,
upper bound in the overall capacity of the cluster).

$0$$1$$2$$3$$4$$5$$\ldots$$n\\!-\\!2$$n\\!-\\!1$$n$$n\\!+\\!1$$\ldots$$a\\!-\\!2$$a\\!-\\!1$
Figure 5: Lookup process of Dx

##  V MementoHash

The basic idea behind the Memento algorithm is to use memory just to remember
the removed buckets. It starts with an empty data structure and relies on Jump
as its core engine. When all the buckets are working, or when buckets are
removed in LIFO order, Memento works exactly like Jump. If a random bucket is
removed (i.e., the related node fails) Memento stores this information in its
internal data structure and redistributes the keys among the remaining
buckets.

###  V-A Dense b-arrays

When we initially set up a new cluster, we associate each node to a sequential
bucket. We can represent the cluster as a b-array where each bucket represents
a working node and is positioned at the corresponding index. Jump assumes the
b-array always to be in this configuration (see, e.g., Fig. 6).

IndexBucket$0$$1$$2$$3$$4$$5$$6$$7$$8$$9$$0$$1$$2$$3$$4$$5$$6$$7$$8$$9$ Figure
6: Initial state of a b-array of size 10

######  Note. V.1.

For clarity in the upcoming explanations, remember that a b-array
$\mathcal{N}$ is always accessed by index (or position), just like any regular
array. When we use the term bucket we refer to the identifier of the
corresponding resource, while when using position or index we refer to a
location within the b-array. In a b-array of size $n$, each bucket $b$ has a
value within the range $[0,n\\!-\\!1]$. As a result, $b$ can also serve as an
index for accessing the value $\mathcal{N}[b]$. Initially, each bucket is
located at its corresponding index, i.e., $\mathcal{N}[b]=b\ \forall b$ (refer
to Fig. 6). When a bucket $b$ is removed, it gets replaced by a bucket $c$.
Therefore, $\mathcal{N}[b]=c$.

######  Def. V.2 (dense b-array).

Given a b-array $\mathcal{N}$ of size $n$ and a value $w\leq n$. We define the
b-array as _dense_ up to $w$, $D_{w}(\mathcal{N})$ if every index between $0$
and $w\\!-\\!1$ contains a working bucket.

The b-array representing the initial configuration of a cluster of size
$n=w=|\mathcal{N}|$ is dense (i.e., $D_{n}(\mathcal{N})$ holds), and the
buckets are sorted from $0$ to $n\\!-\\!1$. If we remove the last bucket,
$w=|\mathcal{N}|-1$, hence $D_{n-1}(\mathcal{N})$ holds. It is the working
condition for Jump. On the other hand, if we remove a random bucket other than
the last (i.e., the related node fails), we create a gap, and neither
$D_{n}(\mathcal{N})$ nor $D_{n-1}(\mathcal{N})$ hold.

###  V-B Maintaining a dense b-array

In the general sense, random node removals prevent us from using Jump. In the
following we thus present the basic idea that enables us to keep the b-array
dense. Let us assume to have a b-array $\mathcal{N}_{0}$ of size $10$ (Fig.
7), $D_{10}(\mathcal{N}_{0})$ holds. If we remove bucket $9$, the condition
$D_{9}(\mathcal{N}_{1})$ holds. Subsequently, if we remove bucket $5$, we
create a gap, and neither $D_{9}(\mathcal{N}_{1})$ nor
$D_{8}(\mathcal{N}_{1})$ would hold. Accordingly, to fill the gap, we can copy
bucket $8$ in position $5$ to obtain $\mathcal{N}_{2}$, where
$D_{8}(\mathcal{N}_{2})$ and $D_{9}(\mathcal{N}_{2})$ hold again.

$\mathcal{N}_{0}$$\mathcal{N}_{1}$$\mathcal{N}_{2}$ Initial state Removal of
node 9 Replace bucket 5 with 8
$0$$1$$2$$3$$4$$5$$6$$7$$8$$9$$0$$1$$2$$3$$4$$5$$6$$7$$8$$9$$n=10$,
$w=10$$0$$1$$2$$3$$4$$5$$6$$7$$8$$9$$n=9$,
$w=9$$0$$1$$2$$3$$4$$\mathbf{8}$$6$$7$$8$$9$$n=9$, $w=8$ Figure 7: Removing a
bucket: the last (9) or any other than the last (5)

Since we removed bucket $5$, the new size of our cluster is $w=8$. So, we will
consider only the buckets in the positions from $0$ to $7$. After removing
bucket $5$ the working buckets are $[0,8]\backslash\\{5\\}$, which are
precisely the buckets available from position $0$ to $7$. If we remove another
bucket, for example, bucket $1$, we fill the gap by copying bucket $7$ in
position $1$ to obtain $\mathcal{N}_{3}$ (Fig. 8). The working buckets are now
$[0,8]\backslash\\{1,5\\}$, and the size of the cluster becomes $7$.

######  Prop. V.3.

The new size of the cluster always corresponds to the index of the bucket we
use to fill the gap.

$\mathcal{N}_{3}$ Replace bucket 1 with 7
$0$$\mathbf{7}$$2$$3$$4$$\mathbf{8}$$6$$7$$8$$9$$n=9$, $w=7$ Figure 8: Filling
the gap after removal of bucket 1

If we compare the b-array versions $\mathcal{N}_{1}$, $\mathcal{N}_{2}$, and
$\mathcal{N}_{3}$ we can notice that they are identical except for the
positions of the removed buckets. Therefore, instead of representing the whole
b-array, we can represent only the differences between the initial and the
current state of the b-array (Fig. 9).

$\mathcal{N}_{1}$$\mathcal{N}_{2}$$\mathcal{N}_{3}$$0$$1$$2$$3$$4$$5$$6$$7$$8$$0$$1$$2$$3$$4$$5$$6$$7$$8$$0$$1$$2$$3$$4$$\mathbf{8}$$6$$7$$8$$0$$\mathbf{7}$$2$$3$$4$$\mathbf{8}$$6$$7$$8$
Figure 9: Comparing versions $\mathcal{N}_{1}$, $\mathcal{N}_{2}$, and
$\mathcal{N}_{3}$

Each bucket corresponds to its position in the initial state
$\mathcal{N}_{0}$, so we do not need to represent it; we just need the size of
the b-array. Removing the last bucket just reduces the size of the b-array.
Also in this case, we just need to update its size ($n\leftarrow n\\!-\\!1$).
For every removed bucket $b$, other than the last one, we remember its
replacement in the form $b\rightarrow c$ where $c$ is the replacing bucket. As
we will discuss later, when we restore the buckets, we should do it in reverse
order, from the last removed bucket backward. This approach preserves the
properties of balance and minimal disruption of the algorithm. Therefore, when
a bucket $b$ is removed, we store the replacement $b\rightarrow c$ together
with the previously removed bucket $p$.

######  Def. V.4 (replacement).

A replacement is defined by a tuple $\langle b\rightarrow c,p\rangle$ where
$b$ is the removed bucket, $c$ is the replacing one, and $p$ is the previously
removed bucket.

######  Def. V.5 (replacement set).

The replacement set $\mathcal{R}$ is the data structure used to store the
replacements $\langle b\rightarrow c,p\rangle$ for all the removed buckets. We
are only interested in knowing if there exists a replacement for a given
bucket $b$. Therefore, we can implement $\mathcal{R}$ using a hash table that
takes $b$ as the key and returns $\langle c,p\rangle$ as the value. This
allows us to add a replacement for bucket $b$ into $\mathcal{R}$, remove the
replacement for bucket $b$ from $\mathcal{R}$, and check if a replacement for
the bucket $b$ exists in constant time.

Given a cluster with $n$ initial nodes, all the buckets are working and are in
the range $[0,n\\!-\\!1]$. When the first bucket $b$ is removed, we set $p=n$
in the replacement. This way, when the first removed bucket gets restored, the
next node added to the cluster will be mapped to the bucket $n$ as expected.

######  Prop. V.6.

The number of working buckets $w=n-r$ is given by the difference between the
size of the b-array $n=|\mathcal{N}|$ and the number of replacements
$r=|\mathcal{R}|$ (i.e., the number of removed buckets).

Let $l$, with $0\leq l\leq n$, be the last removed bucket. Accordingly, the
aforementioned removals lead to the following updates:

  * Initialization: $n=10$, $R_{\mathcal{N}_{0}}=\\{\\}$, $l=10$

  * Removing bucket 9: $n=9$, $R_{\mathcal{N}_{1}}=\\{\\}$, $l=9$

  * Removing bucket 5: $n=9$, $R_{\mathcal{N}_{2}}=\\{\langle 5\rightarrow 8,9\rangle$, $l=5$

  * Removing bucket 1: $n=9$, $R_{\mathcal{N}_{3}}=\\{\langle 5\rightarrow 8,9\rangle,\langle 1\rightarrow 7,5\rangle\\}$, $l=1$

This replacement strategy works well in all situations. However, in the
following sections, we will discuss two edge cases we can get while removing
buckets.

###  V-C Removing a replacing bucket

In the previous example, we removed bucket $5$, replacing it with $8$, and
then we removed bucket $1$, replacing it with $7$. We will now show what
happens if we remove bucket $8$ from $\mathcal{N}_{3}$. Following the same
logic, we will copy bucket $6$ in position $8$. The remaining working buckets
are $6$ namely: $\mathcal{N}_{4}=\\{0,2,3,4,6,7\\}$ (Fig. 10).

$\mathcal{N}_{4}$$0$$1$$2$$3$$4$$5$$6$$7$$8$$9$$0$$7$$2$$3$$4$$8$$6$$7$$\mathbf{6}$$9$$n=9$,
$w=6$ Figure 10: Removing a replacing bucket

At this point, to find the actual replacement of bucket $5$, we need to apply
the substitution two times $5\rightarrow 8\rightarrow 6$. In Fig. 11, we can
see how substitutions can be chained to obtain a proper replacement.

Step I$0$$1$$2$$3$$4$$5$$6$$7$$8$$9$$0$$7$$2$$3$$4$$8$$6$$7$$6$$9$Step
II$0$$1$$2$$3$$4$$5$$6$$7$$8$$9$$0$$7$$2$$3$$4$$8$$6$$7$$6$$9$ Figure 11:
Removing a replacing bucket - lookup steps

The proper bucket positions (containing the working buckets) are in the range
$[0,5]$. Therefore, positions $6$, $7$, or $8$ cannot be directly reached. The
only way to hit one of the related buckets is through redirection.

The same concept holds in the opposite situation where the replacing bucket
was removed in a previous iteration. In this case we fill the gap with an
already replaced bucket. Therefore, to find the working bucket we need to
follow the chain of replacements.

###  V-D Replacing a bucket with itself

Suppose we remove bucket $5$ from the b-array $\mathcal{N}_{4}$. Applying the
same logic, bucket $5$ must be copied in position $5$ to obtain
$\mathcal{N}_{5}$ (Fig. 12). Bucket $5$ is replaced by itself. However, this
is not an issue since, after removing bucket $5$, the size of the cluster
becomes $5$. Therefore, the proper bucket positions are in the range $[0,4]$,
representing the set of working buckets $\\{0,2,3,4,7\\}$. Position $5$ cannot
be hit directly, and bucket $5$ cannot be reached via redirection.

$\mathcal{N}_{5}$$0$$1$$2$$3$$4$$5$$6$$7$$8$$9$$0$$7$$2$$3$$4$$\mathbf{5}$$6$$7$$6$$9$$n=9$,
$w=5$ Figure 12: Replacing a bucket with itself

##  VI Explanation of the algorithm

As described in the previous sections, Memento relies entirely on Jump as its
core engine. The latter ensures balance, monotonicity when adding new buckets,
and minimal disruption when removing buckets from the tail. However, since
Memento allows for removing arbitrary buckets, additional state information
needs to be stored.

######  Def. VI.1 (state).

The algorithm state information $S$, which comprises all relevant information
required by Memento, is defined as $\mathcal{S}$ := $\langle
n,\mathcal{R},l\rangle$ where:

  * $n$ is the size of the b-array

  * $\mathcal{R}$ is the set of replacements

  * $l$, with $0\leq l\leq n$, is the last removed bucket.

In the following, the underlying details of the algorithm will be discussed.

###  VI-A Initialization

When we set up a new cluster of size $n$, all the initial buckets are working
($\mathcal{W}=\mathcal{N}$ and $\mathcal{R}=\emptyset$). Memento initializes
its state by storing the initial number of buckets and creating an empty set
of replacements (Alg. 1). The last removed bucket $l$ gets initialized to the
value of $n$, since the b-array would grow starting from this index.

Algorithm 1 Init Memento

$initial\\_node\\_count>0$

function INIT($initial\\_node\\_count$)

$n\leftarrow initial\\_node\\_count$

$l\leftarrow n$ $\triangleright$ l = last removed bucket

$\mathcal{R}\leftarrow\emptyset$

end function

###  VI-B Removing a bucket

If all the buckets work and we remove a bucket from the tail, it reduces the
b-array’s size. Otherwise, if there are already removed buckets or when
removing a bucket $b$ other than the last, Memento creates a new replacement
$\langle b\rightarrow w\\!-\\!1,l\rangle$ and puts it into $\mathcal{R}$. The
bucket $b$ becomes the new last removed $l\leftarrow b$. The removal procedure
is described in Alg. 2.

Algorithm 2 Remove a bucket

$0\leq b<n$

function REM($b$)

if $b=n-1$ and $\mathcal{R}=\emptyset$ then

$n\leftarrow n-1$ $\triangleright$ Size is reduced by 1

else

$w\leftarrow n-|\mathcal{R}|$

$\mathcal{R}\leftarrow\mathcal{R}\cup\langle b\rightarrow w\\!-\\!1,l\rangle$

end if

$l\leftarrow b$ $\triangleright$ The last removed bucket

end function

###  VI-C Adding a bucket

If all the buckets are working, a new bucket will be added to the tail of the
array, increasing the number of buckets by one. Otherwise, we will restore the
last removed bucket (Alg. 3).

Algorithm 3 Add a bucket

$0\leq b\leq n$

function ADD()

if $\mathcal{R}=\emptyset$ then $\triangleright$ Adds a bucket to the tail

$b\leftarrow n$

$l\leftarrow n\leftarrow n+1$

else

$b\leftarrow l$ $\triangleright$ Get the last removed bucket

$\mathcal{R}\leftarrow\mathcal{R}\backslash\langle b\rightarrow c,p\rangle$
$\triangleright$ Remove the replacement

$l\leftarrow p$ $\triangleright$ Updates the last removed bucket

end if

return $b$

end function

As described in Sec. V-C, there are edge cases where removing buckets may
create chains of replacements. By always restoring the last removed bucket, we
guarantee to properly untie the chains of replacements.

###  VI-D Lookup

The explanation of the lookup function is the following. We start hitting a
position in the b-array. If the related bucket $b$ works, we are done.
Otherwise, we hit a new position in the portion of b-array $\mathcal{W}_{b}$
containing the working buckets when $b$ was removed. We hit a new bucket,
$c\in\mathcal{W}_{b}$. If it works, we are done. Otherwise, we search in the
portion of b-array $\mathcal{W}_{c}$ containing the working buckets when $c$
was removed. This second portion is smaller than $\mathcal{W}_{b}$ (i.e.,
$\mathcal{W}\subseteq\mathcal{W}_{c}\subset\mathcal{W}_{b}$). Therefore,
eventually, we will reach the portion of the b-array $\mathcal{W}$ containing
only working buckets.

More specifically, when performing a lookup, Memento starts by invoking Jump
to get a bucket $b$ in the range $[0,n\\!-\\!1]$ (Alg. 4 line 2). If the
bucket is working, the lookup is done. Otherwise, there must be a replacement
in the form $\langle b\rightarrow c,p\rangle\in\mathcal{R}$ for some
$c,p\in\mathcal{N}$.

When we start a new cluster, all the buckets are working. Jump is balanced and
evenly maps the keys among the buckets. When we remove a bucket $b$ other than
the last, all the keys originally mapped to $b$ need to be evenly distributed
among the remaining buckets.

As stated in Prop. V.3, the value $c$ corresponds also to the remaining number
of working buckets after the removal of $b$ (Alg. 4 line 4). Therefore, the
working buckets can be found only in range $[0,c\\!-\\!1]$.

We hash the key again to get a new mapping in the range $[0,c\\!-\\!1]$ (Alg.
4 lines 5 and 6). This time we do not need the hashing algorithm to be
consistent. So, we can reduce complexity by using an uniform hash function as
described in Note III.1 that works in $O(1)$ (assuming keys to be of fixed
size).

Algorithm 4 Lookup

1:$0\leq b<n$

2:function LOOKUP($key$)

3: $b\leftarrow jump(key,n)$

4: while $\exists\langle b\rightarrow c,p\rangle\in\mathcal{R}$ do

5: $w_{b}\leftarrow c$ $\triangleright$ Working buckets after b was removed

6: $h\leftarrow hash(key,b)$ $\triangleright$ Traditional hash function

7: $d\leftarrow h$ mod $w_{b}$ $\triangleright$ New bucket in
$[0,w_{b}\\!-\\!1]$

8: while $\exists\langle d\rightarrow u,q\rangle\in\mathcal{R}$ and $u\geq
w_{b}$ do

9: $d\leftarrow u$ $\triangleright$ Follow substitutions

10: end while

11: $b\leftarrow d$

12: end while

13: return $b$

14:end function

At this step, if we hit a working bucket, the algorithm is done. Otherwise, we
follow the replacements chain until either we find a working bucket, or we
find a bucket $d$ removed after $b$ (Alg. 4 lines 7 and 8). It is worth noting
that the condition $u\geq w_{b}$ of the inner loop contributes in guaranteeing
the balance. Since, without such a condition, the inner loop would always
follow the replacement chain until the end resulting in an unbalanced
distribution. Suppose, for instance, to have a b-array of size 6 and remove
buckets 0, 3, and 5 in order (Fig. 13, the three steps denote the removal
order and the corresponding replacement). The replacement set is
$\mathcal{R}=\\{\langle 0\rightarrow 5,6\rangle,\langle 3\rightarrow
4,0\rangle\,\langle 5\rightarrow 3,3\rangle\\}$.

$Step\ I$$\langle 0\rightarrow
5,6\rangle$$0$$1$$2$$3$$4$$5$$\mathbf{5}$$1$$2$$4$$4$$5$$Step\ II$$\langle
3\rightarrow 4,0\rangle$$0$$1$$2$$3$$4$$5$$5$$1$$2$$\mathbf{4}$$4$$5$$Step\
III$$\langle 5\rightarrow
3,3\rangle$$0$$1$$2$$3$$4$$5$$5$$1$$2$$4$$4$$\mathbf{3}$ Figure 13: Removing
bucket 0, 3, and 5 in order

The first operation of the lookup $jump(key,6)$ returns $3$. Bucket $3$ was
removed (i.e., $\langle 3\rightarrow 4,0\rangle\in\mathcal{R}$, see step II in
Fig. 13), so we rehash the key to get an index in the range $[0,4\\!-\\!1]$
(Alg. 4 lines 3 to 6. Fig. 14).

$\mathcal{N}$$0$$1$$2$$3$$4$$5$$\mathbf{5}$$1$$2$$\mathbf{4}$$4$$3$new lookup
range $[0,4\\!-\\!1]$ Figure 14: First lookup step ($jump(key,6)\rightarrow
3$)

We assume to use a uniform hash function, so every index has the same
probability of being selected. Buckets $0$ and $3$ are removed, and both
redirect to bucket $4$ ($3\rightarrow 4$ and $0\rightarrow 5\rightarrow
3\rightarrow 4$). Therefore, buckets $1$ and $2$ have $\frac{1}{4}$
probability of being selected, while the probability of selecting bucket $4$
(which is at the end of the replacement chain) is $\frac{1}{2}$. Thanks to the
condition $u\geq w_{b}$ of the internal loop, this balance issue is avoided.
If the first rehash returns $1$ or $2$, we find a working bucket, and the loop
exits. If it returns $3$, we follow the redirect hitting bucket $4$ that is
also working, and the loop exits. Finally, if it returns $0$, the internal
loop follows the first redirect $\langle 0\rightarrow
5,3\rangle\in\mathcal{R}$, hitting $5$. Bucket $5$ was removed after bucket
$3$ (i.e., $\langle 5\rightarrow 3,0\rangle\in\mathcal{R}$, see step III in
Fig. 13), but the condition $u\geq w_{b}$ does not hold because
$u(=3)<w_{b}(=4)$. Therefore, the internal loop stops, $b$ is set to $5$ (Alg.
4 line 10), $w_{b}$ is set to $3$ (Alg. 4 line 4), and we rehash the key again
to get an index in the interval $[0,3\\!-\\!1]$ (Fig. 15).

$\mathcal{N}$$0$$1$$2$$3$$4$$5$$\mathbf{5}$$1$$2$$\mathbf{4}$$4$$\mathbf{3}$new
lookup range $[0,3\\!-\\!1]$ Figure 15: Second lookup step when $d=0$

Again, the indexes $0$, $1$, and $2$ have the same probability of being
selected. This time, $w_{b}=3$ so, if we hit $0$ again, the internal loop
keeps following the substitution chain ($0\rightarrow 5\rightarrow
3\rightarrow 4$) until hitting bucket $4$. This allows keys to be distributed
evenly among the working buckets. Keys returning the indexes $1$, $2$, or $3$
end the external loop in one iteration, while keys returning the index $0$ do
an additional iteration that distributes the keys evenly among the working
buckets, as shown in Fig 16. Kindly observe that during each cycle of the
external loop, we either identify a working bucket or the lookup range
diminishes.

$b\leftarrow$jump(key,6)pt$\langle 3\rightarrow
4,0\rangle\in\mathcal{R}$$d\leftarrow$hash(key,3) mod $4$ pt$0\rightarrow
5$(Internal loop) pt$\langle 5\rightarrow
3,3\rangle\in\mathcal{R}$$d\leftarrow$hash(key,5) mod $3$ pt$0\rightarrow
5\rightarrow 3\rightarrow 4$(Internal loop) ptreturn $4$$P=\frac{1}{12}$
$d=4$$d=0$ptreturn $1$$P=\frac{1}{12}$ $d=1$ptreturn $2$$P=\frac{1}{12}$
$d=2$$d=5$$d=0$ptreturn $1$$P=\frac{1}{4}$ $d=1$ptreturn $2$$P=\frac{1}{4}$
$d=2$pt$3\rightarrow 4$(Internal loop) ptreturn $4$$P=\frac{1}{4}$
$d=4$$d=3$$b=3$ptJump stepptLoop iteration #1ptLoop iteration #2 Figure 16:
External loop iterations and output probabilities

######  Prop. VI.2.

The lookup function always ends.

###### Proof.

To prove the termination of the lookup function, we must prove that the two
nested loops always perform a bounded number of iterations. We will start
proving the termination of the internal loop.
In section V, it is explained that when a bucket is removed, a substitution in
the form $\langle b\rightarrow c,p\rangle$ is added to $\mathcal{R}$, where
$b$ is the removed bucket, $c$ is the replacing bucket, and $p$ is the bucket
previously removed. By construction, either $c$ is working, or there must
exist a substitution $\langle c\rightarrow u,q\rangle\in\mathcal{R}$. This
ensures that a chain of substitutions always ends with a working bucket. In
Algorithm 4, the internal loop (lines 7 to 9) follows this substitution chain
until it either reaches a working bucket (the end of the chain) or encounters
a bucket $d$ that was removed after $b$ (i.e., a bucket that was working when
$b$ was removed). This guarantees the termination of the internal loop.
The external loop (lines 3 to 11) begins by selecting a bucket $d$ from the
range $[0,n\\!-\\!1]$. For each iteration of the external loop, the internal
loop will return either $d$ if it is working or a bucket $u$ that was working
when $d$ was removed (and can still be working). If the internal loop returns
$d$ or $u$ as working, the external loop terminates. If not, the external loop
selects a new $d$ from the range $[0,u\\!-\\!1]$. Proposition V.3 emphasizes
that the value $u$ represents both the replacing bucket and the count of
working buckets after the removal of $d$. Hence, $u$ is strictly less than
$n$. Considering these factors, it becomes evident that, in each iteration, we
either discover a working bucket or reduce the range $[0,u\\!-\\!1]$ to
$[0,u\\!-\\!\delta]$, with $\delta>1$. Ultimately, this range contracts to
$[0,w\\!-\\!1]$, where each position leads to a working bucket. Therefore, the
external loop is guaranteed to terminate. ∎

######  Prop. VI.3.

Minimal disruption holds for Memento.

###### Proof.

When we remove a bucket $b$, only the keys previously mapped to $b$ should
move to a new location. We will prove this property by induction on $r$ (the
number of removed buckets).

  * •

r = 1: If we remove the bucket from the tail, minimal disruption is guaranteed
by Jump. Otherwise, let us assume to remove a bucket $b$ other than the last.
First, we invoke Jump. if it returns an index other than $b$ the algorithm
ends. The position of the keys previously mapped to a bucket other than $b$
does not change. If Jump returns $b$ the key is rehashed and mapped to an
index in the range [0,n-2]. If it hits $b$ again, it will be redirected to
$c\neq b$. Only keys previously mapped to $b$ will move to another bucket.

  * •

r: we assume the property to hold for $r\geq 1$.

  * •

r+1: by hypothesis all the keys were consistently moved to the $n-r$ working
buckets. After we remove a new bucket $b$, the lookup algorithm stops if a key
hits a working bucket. Keys on working buckets do not move. Keys hitting a
previously removed bucket will not move by hypothesis. Finally, if a key hits
$b$ (the last removed bucket), it will be rehashed and mapped to an index in
the range $[0,n\\!-\\!r\\!-\\!2]$ that contains only working buckets.
Therefore, only keys mapped to $b$ will move to a working bucket.

∎

######  Prop. VI.4.

Balance holds for Memento

###### Proof.

We prove the balance by induction on the number of removed buckets $r$.

  * •

r = 0: balance is guaranteed by Jump.

  * •

r = 1: first we invoke Jump, evenly distributing keys among all the buckets.
Every bucket gets $\frac{k}{n}$ keys. The keys mapped on the only removed
bucket $b$ are rehashed and mapped to an index in the range $[0,n\\!-\\!2]$.
The hash function is assumed to be uniform, so every index gets
$\frac{\frac{k}{n}}{n-1}$ keys. The keys that hit $b$ again are remapped to
$c$. Therefore, all the buckets except $b$ will end up having
$\frac{k}{n}+\frac{\frac{k}{n}}{n-1}=\frac{k}{n}+\frac{k}{n(n-1)}=\frac{k(n-1)+k}{n(n-1)}=\frac{kn}{n(n-1)}=\frac{k}{n-1}$
keys.

  * •

r: we assume the property to hold for $r\geq 0$.

  * •

r+1: we assume the keys to be evenly distributed after removing $r$ buckets.
Every working bucket has $\frac{k}{n-r}$ keys. When we remove a new bucket
$b$, all the keys previously mapped to other buckets will not be affected
(minimal disruption). The keys previously mapped to $b$ will be rehashed and
mapped to an index in the range $[0,n-r-2]$. Since we use a uniform hash
function, every index in $[0,n\\!-\\!r\\!-\\!2]$ gets
$\frac{1}{n\\!-\\!r\\!-\\!1}$ of the rehashed keys. After the removal of $b$
every working bucket will have
$\frac{k}{n-r}+\frac{\frac{k}{n-r}}{n-r-1}=\frac{k}{n-r}+\frac{k}{(n-r-1)(n-r)}=\frac{k(n-r)}{(n-r)(n-r-1)}=\frac{k}{n-r-1}$
keys.

∎

######  Prop. VI.5.

Monotonicity holds for Memento.

###### Proof.

When a new bucket is added, keys only move from an existing bucket to the new
one, but not between existing ones. We will prove this property by induction
on the number of removed buckets $r$.

  * •

r = 0: there are no removed buckets. The new bucket is added to the tail and
monotonicity is guaranteed by Jump.

  * •

r = 1: we have only one removed bucket $b$. Keys that are sent to $b$ by Jump
in the first place are evenly remapped to the remaining buckets. As proven in
VI.4, every bucket other than $b$ gets $\frac{1}{n-1}$ of the keys previously
mapped to $b$. When we add a new node to the cluster, Memento will assign to
such a node the bucket $b$. Keys previously mapped to $b$ will move to $b$
again, so from every node other than $b$, $\frac{k}{n(n-1)}$ keys will move to
$b$. A total of $\frac{k}{n}$ keys will move to $b$. Keys mapped by Jump to
buckets other than $b$ are not affected by this operation and, therefore, will
not move.

  * •

r: we assume the property to hold for $r\geq 1$.

  * •

r+1: by hypothesis monotonicity holds when up to $r$ buckets are removed. We
assume to have $r+1$ removed buckets and add a new node to the cluster.
Memento restores the last removed bucket. As discussed in VI.3, keys were
remapped to the working buckets when the last bucket $b$ was removed. Each
working bucket got $\frac{1}{n-r-1}$ of the keys previously mapped to $b$.
When $b$ gets restored, keys are not remapped anymore. Therefore, any working
bucket other than $b$ will send $\frac{k}{(n-r)(n-r-1)}$ keys back to $b$. A
total of $\frac{k}{n-r}$ keys will move to $b$, and no keys will move to any
other node.

∎

##  VII Computational complexity

In this section, we explore the computational complexity of the functions
described earlier. The complexity related to initializing the data structure,
adding and removing buckets is considered negligible, thus requiring only a
brief explanation. For the lookup function we provide instead a formal
characterisation to elaborate on its intricate nature.

###  VII-A Initialization

During the initialization phase, we assume all nodes to be working and each
bucket to match its own position. The set of replacements is initialized as an
empty set (or hash table) and the size of the b-array is stored in the
algorithm state. The initialization takes therefore $O(1)$ and uses minimal
memory.

###  VII-B Removing a bucket

If $b=n-1$ and $\mathcal{R}=\emptyset$ the algorithm just updates the size of
the b-array which takes $O(1)$. Otherwise, a new replacement is created and
added to the replacement set. The replacement is a tuple and can be created in
constant time. The replacement can be added in constant time by using a hash
table to represent $\mathcal{R}$. So, the overall complexity of removing a
bucket is $O(1)$.

###  VII-C Adding a bucket

If $\mathcal{R}=\emptyset$ (no previously removed buckets), we assume the
bucket to be added to the tail of the b-array. In this case, the algorithm
stores such information by increasing the size of the b-array, which takes
$O(1)$. Otherwise, the algorithm restores the last removed bucket. A
replacement can be removed in constant time by using a hash table to represent
$\mathcal{R}$. So, the overall complexity of adding a bucket is $O(1)$.

###  VII-D Lookup

In this section, we derive an upper bound to the average number of operations
needed to lookup a key. The algorithm starts invoking $b\leftarrow
jump(key,n)$ which takes $O(\ln(n))$ [6]. If the first step hits a working
bucket the algorithm is done. Otherwise there are two nested loops. We will
start by giving an upper bound to the number of iterations of the external
loop (Alg. 4 lines 3-11).

######  Prop. VII.1 (External loop computational complexity).

Let $\tau$ denote the number of iterations of the external loop in Alg. 4
given a b-array of size $n$ with $w\leq n$ working buckets and a given key.
Due to the stochastic nature of the underlying process, $\tau$ is a random
variable and we have that:

  * (i)

the expectation of $\tau$ is upper-bounded by $ln(\frac{n}{w})$; and

  * (ii)

the standard deviation of $\tau$ is upper-bounded by $\sqrt{ln(\frac{n}{w})}$.

###### Proof.

We prove the proposition by deriving a closed-form expression for the _moment
generating function_ (MGF, [14]) of $\tau$, that is defined as:

$\phi_{\tau}(s):=\mathbb{E}[e^{s\tau}]\,,$ (1)

with $\mathbb{E}$ denoting the expectation of its argument computed w.r.t. the
distribution $\mathbb{P}(\tau)$. It is a straightforward exercise to check
that the expectation and the variance of $\tau$ can be expressed by means of
the first two derivatives of the MGF computed for $s=0$:

$\displaystyle\mathbb{E}[\tau]$ $\displaystyle=$
$\displaystyle\phi^{\prime}_{\tau}(0)\,,$ (2) $\displaystyle\mathbb{V}(\tau)$
$\displaystyle=$
$\displaystyle\phi_{\tau}^{\prime\prime}(0)-(\phi_{\tau}^{\prime}(0))^{2}\,.$
(3)

Remember that $\mathcal{W}_{b}$ denotes the set of working buckets after $b$
was removed. When the first step (i.e., $jump(key,n)$) hits a removed bucket
$b$, there must exist a replacement tuple $\langle b\rightarrow
c,p\rangle\in\mathcal{R}$ such that $c\in\mathcal{W}_{b}$ represents both the
replacing bucket (see Prop. V.3) and the number of working buckets after $b$
was removed (i.e., $c=|\mathcal{W}_{b}|$). The existence of such a tuple is
the entering condition for the external loop. The key is consequently rehashed
to an index in the interval $[0,c\\!-\\!1]$ with uniform probability, and $b$
is replaced by either a working bucket or a bucket removed after $b$. The
interval $[0,c\\!-\\!1]$ becomes smaller after each iteration, and the loop
terminates when we reach the interval containing only working buckets.

Consider a fixed sequence of removed buckets
$r_{n-w-1}\rightarrow\dots\rightarrow r_{0}$ where $r_{n-w-1}$ is the first
removed bucket and $r_{0}$ the last one. Denote as $\mathcal{W}_{r_{i}}$ the
set of working buckets after the removal of $r_{i}$ (hence,
$\mathcal{W}_{r_{0}}=\mathcal{W}$). We might regard the working buckets as
buckets that have not been already removed, and extend the sequence by adding
working buckets with negative indexes to the tail, i.e.,
$r_{n-w-1}\rightarrow\dots\rightarrow r_{0}\rightarrow
r_{-1}\rightarrow\dots\rightarrow r_{-w}$. In this way, every bucket $b$ is
equal to $r_{i}$ for some $i$, being working iff $i<0$. In particular, if
$b=jump(key,n)$ is the bucket returned by the first instruction of the
algorithm (line 2) there is a $i$ such that $b=r_{i}$. If $b\in\mathcal{W}$
(i.e., $i<0$) the loop exits and $\tau=1$. If this is not the case, we call
$\tau_{i}$ the number of iterations of the loop when $i\geq 0$.

When the algorithm enters the loop, a new bucket $d\in\mathcal{W}_{b}$ is
picked with uniform probability. Let us consider a discrete random variable
$j$ defined as the index (smaller than $i$ by construction) such that
$d=r_{j}$. If $j<0$, we have that $d$ is working, the loop ends and
$\tau_{i}=1$. Otherwise, if $0\leq j<i$, by the uniform hashing assumption
(see Note III.1), $\tau_{i}=1+\tau_{j}$. Finally, notice that, since
$\mathcal{W}_{r_{0}}=\mathcal{W}$, $\tau_{0}=1$.

Consider the MGF of $\tau_{i}$, which, with a small abuse of notation, is
denoted as:

$\phi_{i}(s):=\mathbb{E}[e^{s\tau_{i}}]\,.$ (4)

This allows us to apply the law of total expectation to $\phi_{i}(s)$ by
conditioning w.r.t. $j$, i.e.,

$\begin{split}\phi_{i}(s)=&\mathbb{P}(j<0)\cdot\mathbb{E}[e^{s\tau_{i}}|j<0]\\\
&+\sum_{k=0}^{i-1}\mathbb{P}(j=k)\cdot\mathbb{E}[e^{s\tau_{i}}|j=k]\,.\end{split}$
(5)

Distribution $\mathbb{P}(j)$ is uniform over its $w+i$ integer values. We can
therefore rewrite Eq. (5) as:

$\begin{split}\phi_{i}(s)=&\frac{w}{w+i}\cdot\mathbb{E}[e^{s\tau_{i}}|j<0]\\\
&+\frac{1}{w+i}\sum_{k=0}^{i-1}\mathbb{E}[e^{s\tau_{i}}|j=k]\,.\end{split}$
(6)

For $j<0$ (i.e., $d\in\mathcal{W}$), as the loop ends after one iteration and
a single hash calculation is done, we have $\tau_{i}=1$ and hence:

$\mathbb{E}[e^{s\tau_{i}}|j<0]=e^{s}\,.$ (7)

For each $j=k$ with $0\leq k<i$, we already proved that $\tau_{i}=1+\tau_{k}$
and hence:

$\mathbb{E}[e^{s\tau_{i}}|j=k]=\mathbb{E}[e^{s(1+\tau_{k})}]=e^{s}\mathbb{E}[e^{s\tau_{k}}]\,.$
(8)

Overall, by Eqs. (7) and (8) and the definition in Eq. (4), we can rewrite Eq.
(6) as follows:

$\phi_{i}(s)=\frac{we^{s}}{w+i}+\frac{e^{s}}{w+i}\sum_{k=0}^{i-1}\phi_{k}(s)\,,$
(9)

and hence, by simple algebra:

$\frac{w+i}{e^{s}}\phi_{i}(s)=w+\sum_{k=0}^{i-1}\phi_{k}(s)\,,$ (10)

and finally, by putting in evidence $\phi_{i-1}(s)$:

$\frac{w+i}{e^{s}}\phi_{i}(s)=w+\sum_{k=0}^{i-2}\phi_{k}(s)+\phi_{i-1}(s)\,.$
(11)

If we rewrite Eq. (10) with $i-1$ instead of $i$, we obtain on the r.h.s. the
first two terms of the r.h.s. of Eq. (11). The latter equation might therefore
rewrite as:

$\frac{w+i}{e^{s}}\phi_{i}(s)=\frac{w+i-1}{e^{s}}\phi_{i-1}(s)+\phi_{i-1}(s)\,,$
(12)

and hence, by simple algebra, as the following recursion:

$\phi_{i}(s)=\frac{w+i-1+e^{s}}{w+i}\phi_{i-1}(s)\,.$ (13)

As $\phi_{0}(s)=e^{s}$, for each $i>0$ we obtain the following closed-form
expression for Eq. (13):

$\phi_{i}(s)=e^{s}\prod_{k=1}^{i}\frac{w+k-1+e^{s}}{w+k}\,,$ (14)

and hence, by taking the logarithm on both sides:

$\ln(\phi_{i}(s))=s+\sum_{j=1}^{i}\ln\left(\frac{w+j-1+e^{s}}{w+j}\right)\,,$
(15)

and finally, by taking the derivative on both sides:

$\frac{\phi_{i}^{\prime}(s)}{\phi_{i}(s)}=1+\sum_{k=1}^{i}\frac{e^{s}}{w+k-1+e^{s}}\,.$
(16)

By the MGF definition, we trivially have $\phi_{i}(0)=1$. Thus, from Eqs. (2)
and (16):

$\mathbb{E}[\tau_{i}]=\phi_{i}^{\prime}(0)=1+\sum_{k=1}^{i}\frac{1}{w+k}\,.$
(17)

Note that the number $\tau$ of iterations for the external loop is
stochastically larger when $b=r_{n-w}$ is the first removed bucket. Therefore,
we can upper-bound the expectation of $\tau$ and, by Eq. (17), write:

$\mathbb{E}[\tau]\leq\mathbb{E}[\tau_{n-w}]=\phi^{\prime}_{n-w}(0)=1+\sum_{k=1}^{n-w}\frac{1}{w+k}\,.$
(18)

The proof of (i) finally follows from the fact that the sum in the r.h.s. of
Eq. (17) is equal to the difference between the $n$-th and th $w$-th _harmonic
numbers_ being therefore dominated by the difference of the corresponding
natural logarithms, i.e.,111If $H_{k}$ is the $k$-th harmonic number, then
$H_{k}=\ln k+\gamma_{k}$, where $\gamma_{k}$ is a monotonic function of $k$
[15].

$1+\sum_{k=1}^{n-w}\frac{1}{w+k}\leq 1+\ln\left(\frac{n}{w}\right)\,.$ (19)

We similarly upper-bound the variance (and then the standard deviation), by
first taking the derivative of Eq. (16):

$\frac{\phi^{\prime\prime}_{i}(s)\phi_{i}(s)-(\phi^{\prime}_{i}(s))^{2}}{(\phi_{i}(s))^{2}}=\sum_{k=1}^{i}\frac{e^{s}(w+k-1+e^{s})-e^{2s}}{(w+k-1+e^{s})^{2}}\,.$
(20)

Evaluating Eq. (20) for $s=0$ and noting that $\phi_{i}(0)=1$ we obtain on the
l.h.s. the variance of $\tau_{i}$ as in Eq. (3) and hence:

$\mathbb{V}(\tau_{i})=\sum_{k=1}^{i}\frac{w+k-1}{(w+k)^{2}}\,.$ (21)

As for the expected value the variance of $\tau$ is stochastically dominated
by the worst-case value in $b=r_{n-w}$, thus:

$\mathbb{V}(\tau)\leq\mathbb{V}(\tau_{n-w})=\sum_{k=1}^{n-w}\frac{w+k-1}{(w+k)^{2}}\,,$
(22)

and hence:

$\sum_{k=1}^{n-w}\frac{w+k-1}{(w+k)^{2}}\leq\sum_{k=1}^{n-w}\frac{w+k}{(w+k)^{2}}\leq\ln{(\frac{n}{w})}\,,$
(23)

where the first inequality follows by simple algebra and the second is because
of Eq. (19). As the standard deviation is the square root of the variance, it
is upper-bounded by $\sqrt{\ln(\frac{n}{w})}$. Note that the bounds do not
depend on the removal sequence. ∎

Let us similarly characterise the worst-case complexity of the internal loop
of the algorithm by the following result.

######  Prop. VII.2 (Internal loop computational complexity).

Let $\sigma$ denote the number of iterations of the internal loop in Alg. 4
given a b-array of size $n$ with $w\leq n$ working buckets and a given key.
Due to the stochastic nature of the underlying process, $\sigma$ is a random
variable and we have that:

  * •

the expectation of $\sigma$ is upper-bounded by $ln(\frac{n}{w})$; and

  * •

the standard deviation of $\sigma$ is upper-bounded by
$\sqrt{ln(\frac{n}{w})}$.

###### Proof.

The proof is very similar to that of Prop. VII.1. As in the other proof, let
us extend the sequence of removals by adding the working buckets to the tail
with negative indexes: $r_{n-w-1}\rightarrow\dots\rightarrow r_{0}\rightarrow
r_{-1}\rightarrow\dots\rightarrow r_{-w}$.

The first step of the algorithm returns a random bucket $b\leftarrow
jump(key,n)$ with uniform probability. But, if we enter the external loop,
then $b$ is a removed bucket. Let us consider a discrete random variable $x$
defined as the index such that $b=r_{x}$. As $b$ is a removed bucket, we have
$x\geq 0$. In this case, the algorithm generates a new bucket $d=r_{i}$ for
some $i$. The condition to enter also the internal loop is $\exists\langle
d\rightarrow u,q\rangle\in\mathcal{R}$ and $u\geq w_{b}$ can be translated as
follows:

> _The loop ends if $d$ is a working bucket or if $d$ was removed after $b$,
> i.e., if $b=r_{x}$, $d=r_{i}$, and $i<x$. The loop executes instead a new
> iteration if $i\geq x$._

Let $\sigma_{i}$ denote the number of iterations of the internal loop when
$d=r_{i}$. If $d$ is working or was removed after $b$ (i.e., $i<x$), the loop
ends immediately and $\sigma_{i}=1$. Otherwise, $d$ is replaced by $u$ (Alg. 4
line 8) with $u=r_{j}$ for some $j<i$. Since the sequence of removed buckets
can be any, also the substitutions $d\rightarrow u$ are randomly defined.
Therefore, when $i>x$ the distribution of $\sigma_{i}$ follows the same
distribution as $1+\sigma_{j}$. We can therefore proceed as in Eq. (5) and
write the MGF of $\sigma_{i}$ as:

$\begin{split}\mathbb{E}[e^{t\sigma_{i}}]=&\mathbb{P}(j<x)\cdot\mathbb{E}[e^{t\sigma_{i}}|j<x]\\\
+&\sum_{k=x}^{i-1}\mathbb{P}(j=k)\cdot\mathbb{E}[e^{t\sigma_{i}}|j=k]\,.\end{split}$
(24)

The number of iterations of the internal loop is stochastically larger when
$b=r_{0}$ is the last removed bucket (i.e., $x=0$). In this case, all the
other buckets were removed before $b$. Thus, replacing $x$ with $0$ in Eq.
(24) holds:

$\begin{split}\mathbb{E}[e^{t\sigma_{i}}]\leq&\mathbb{P}(j<0)\cdot\mathbb{E}[e^{t\sigma_{i}}|j<0]\\\
&+\sum_{k=0}^{i-1}\mathbb{P}(j=k)\cdot\mathbb{E}[e^{t\sigma_{i}}|j=k]\,,\end{split}$
(25)

and finally:

$\begin{split}\mathbb{E}[e^{t\sigma_{i}}]&\leq\frac{w}{w+i}\cdot\mathbb{E}[e^{t\sigma_{i}}|j<0]\\\
&+\frac{1}{w+i}\sum_{k=0}^{i-1}\mathbb{E}[e^{t\sigma_{i}}|j=k]\,.\end{split}$
(26)

Since the r.h.s. of Eq. (26) is the same as in Eq. (6) and the same conditions
hold, we can apply the same steps as for the external loop to obtain the proof
of the proposition. ∎

Finally, we can provide an upper bound to the overall complexity of the two
nested loops.

######  Prop. VII.3 (Nested loops computational complexity).

Let $\omega$ denote the overall number of iterations executed by the nested
loops in Alg. 4. Due to the stochastic nature of the underlying process,
$\omega$ is a random variable and we have that:

  * (i)

the expectation of $\omega$ is upper-bounded by
$\left[ln(\frac{n}{w})\right]^{2}$; and

  * (ii)

the standard deviation of $\omega$ is upper-bounded by
$\left[ln(\frac{n}{w})\right]^{\frac{3}{2}}$.

###### Proof.

Since the two loops are nested, the total number of iterations is given by the
product of the iterations of the individual loops. Hence,
$\omega=\tau\cdot\sigma$. As those two random variables are independent the
expected values factorise, i.e.,

$\mathbb{E}[\tau\cdot\sigma]=\mathbb{E}[\tau]\cdot\mathbb{E}[\sigma]\,,$ (27)

and (i) easily follow from the results about the expectations in the two
previous propositions.

Finally, to characterise the standard deviation, we first consider a classical
characterisation of the variance of the product of two independent variables
such as $\tau$ and $\sigma$:

$\mathbb{V}(\tau\cdot\sigma)=\mathbb{V}(\tau)\cdot\mathbb{V}(\sigma)+\mathbb{V}(\tau)\cdot\mathbb{E}[\sigma]^{2}+\mathbb{E}[\tau]^{2}\cdot\mathbb{V}(\sigma)\,,$
(28)

and hence, by considerations analogous to those provided for the expectations:

$\mathbb{V}(\tau\cdot\sigma)\leq\left[\ln\left(\frac{n}{w}\right)\right]^{3}\,,$
(29)

and thence the upper bound in (ii) for the standard deviation. ∎

The overall complexity of the _lookup_ function is given by summing the
complexity of Jump, invoked as the first instruction, and the complexity of
the nested loops, resulting in $O(ln(n)+[ln(\frac{n}{w})]^{2})$. The following
table summarizes the asymptotic complexity in time and space of Memento and
the other algorithms considered in the paper.

TABLE I: Asymptotic complexity

| Memento | Jump
---|---|---
Memory usage | $\Theta(r)$ | $\Theta(1)$
Lookup time | $O(ln(n)+[ln(\frac{n}{w})]^{2})$ | $O(ln(w))$
Init time | $\Theta(1)$ | $\Theta(1)$
Resize time | $\Theta(1)$ | $\Theta(1)$
| Anchor | Dx
Memory usage | $\Theta(a)$ | $\Theta(a)$
Lookup time | $O([ln(\frac{a}{w})]^{2})$ | $O(\frac{a}{w})$
Init time | $\Theta(a)$ | $\Theta(a)$
Resize time | $\Theta(1)$ | $\Theta(1)$

  * w = number of working buckets

  * r = number of removed buckets

  * a = overall capacity of the cluster

  * n = size of the b-array

##  VIII Benchmarks

We conducted a benchmark comparing the performance of Memento with Jump, Dx,
and the in-place version of Anchor in terms of lookup time and memory usage.
The implementations of these algorithms, together with the benchmarking tool,
can be found on GitHub [13]. Our findings indicate that Memento performs
similarly to Jump in the best-case scenario and better than Anchor and Dx in
the worst-case scenario (up to $65\%$ of removed nodes). As mentioned in Sec.
III, Anchor and Dx require setting an upper bound for the cluster’s overall
capacity (referred to as the value $a$ in Tab. I). This value impacts both
time and memory complexity. Determining the appropriate overall capacity is
not a straightforward task. Setting the overall capacity to the initial
cluster size (i.e., $a=w$), or merely doubling the initial cluster size (i.e.,
$a=2*w$) is unrealistic because real-world scenarios often involve scaling
clusters up to tens or hundreds of times the initial size, such as in
distributed storage systems. Therefore, we believe that the overall capacity
of the cluster should be much bigger than the initial cluster size (i.e.,
$a>>w$). However, using a significantly larger overall capacity would
negatively affect the performance of these algorithms. Hence, we decided to
settle for a reasonable compromise that reflects a real-world setup without
excessively penalizing performance, setting the overall capacity to be ten
times the initial capacity (i.e., $a=10*w$). In Sec. VIII-E we provide a
sensitivity analysis with respect to ratio $\frac{a}{w}$.

###  VIII-A Evaluation scenarios

We propose a comprehensive set of empiric evaluation scenarios to determine
the behavior of our algorithm. The considered metrics are lookup time (i.e.,
the time required for resolving the bucket which stores a particular key), and
memory usage. We experimented with three main scenarios:

  * •

Stable: in this scenarios the nodes (buckets) of the network are stable and no
additions or removals are performed (the size of the cluster remains $w$
throughout the experiment);

  * •

One-shot removals: given an initial size (number of nodes), we remove $90\%$
of the initial nodes ($w$);

  * •

Incremental removals: starting from an initial size of one million nodes
($w=10^{6}$), a growing number of nodes (buckets) is removed from the network.
The amount of nodes removed will be expressed as a percentage of the initial
size ($w$).

For every benchmark, we always initialize Anchor and Dx with $a=10*w$. When
the network is constructed we assume that nodes are inserted, one at a time,
into a corresponding data structure in a known order. This ordering influences
the performance of the algorithms, therefore concerning removals, we evaluated
two different strategies: for the best case, removals follow a Last-In-First-
Out (LIFO) order (i.e. the first node to be removed is the last node added to
the network), whereas for the worst case we remove the nodes in random order.
Since Jump only supports removals in LIFO order, the worst case results for
that algorithm will also refer to a LIFO removal order.

Figure 17: Stable scenario - Lookup time Figure 18: Stable scenario - Memory
usage

###  VIII-B Stable scenario

In the first evaluation scenario we consider stable networks of different
sizes (from ten to one million nodes). Concerning the lookup time, as shown in
Fig. 17, Memento performs similarly to Jump, and noticeably better than both
Anchor and Dx. Regarding memory usage, Jump does clearly benefit from the
absence of an internal data structure, which results in the lowest requirement
(as shown in Fig. 18 and 20). With a constant memory usage, Memento is on par
with Jump, whereas Anchor (which has to keep track of the working buckets) and
Dx (which optimizes memory usage by using a bit-array to mark available
buckets) are the worst performers.

Figure 19: One-shot removals - Memory usage (best case) Figure 20: One-shot
removals - Memory usage (worst case)

###  VIII-C One-shot removals

When nodes are removed, all algorithms apart from Jump need to store
additional information into their data structure. This behavior is reflected
in an increased memory usage. As shown in Fig. 19, in the best case (namely
when nodes are removed in a LIFO order), both Memento and Jump use very little
memory and exhibit constant requirements regardless of the size of the
network. On the contrary, Dx and Anchor actively keep track of removed nodes,
therefore increasing their memory usage. In the worst-case scenario (nodes
removed randomly), Memento also needs to update its state and consumed memory
increases (Fig. 20). To notice that, even in its worst case scenario, Memento
needs less memory than Anchor and Dx.

Figure 21: One-shot Removals - Lookup time (best case) Figure 22: One-shot
Removals - Lookup time (worst case)

Concerning lookup-time, both Memento and Jump perform significantly better
than Dx and display better results also compared to Anchor in the best-case
scenario (Fig. 21). The advantage of Memento over Anchor disappears in the
worst-case scenario, where the latter algorithm performs slightly better on
average (Fig. 22). While Dx remains the slowest of the pack. As mentioned
before, Jump does not support random removals. Therefore the reported
measurement still concerns the LIFO ordering.

###  VIII-D Incremental removals

In the last scenario, we simulate the incremental removal up to $90\%$ of the
nodes. Fig. 23 and Fig. 24 report the lookup time in the best case and in the
worst case, respectively. In the best case, and in contrast to the previous
scenario, Dx is by far the worst performer: this result can be explained by
the fact that several additional resolution steps are introduced by that
algorithm when removing nodes. Memento and Jump perform similarly, as the
logic for both of them is similar. In the worst case, Anchor is the worst
performer, up until the removal of $65\%$ of the nodes. After that threshold,
Memento and Dx become the slowest ones. Losing more than $65\%$ of nodes is
not a common situation. During the regular life cycle of a cluster, the number
of failing nodes is likely never to exceed the threshold of $20\%$, which is
the optimal performance range for Memento.

Figure 23: Incremental removals - Lookup time (best case) Figure 24:
Incremental removals - Lookup time (worst case)

Regarding memory usage, LIFO removals do not affect neither Jump nor Memento,
as no additional information is required to keep track of removed nodes (Fig.
25). In the worst case, analogously to the One-shot removals scenario, Memento
exhibits similar results as Dx, whereas Anchor has the highest memory
consumption.

Figure 25: Incremental removals - Memory usage (best case) Figure 26:
Incremental removals - Memory usage (worst case)

###  VIII-E Sensitivity to the $\frac{a}{w}$ ratio in Anchor and Dx

As stated at the beginning of Sec. VIII, both Anchor and Dx require setting an
upper bound for the cluster’s overall capacity. We argued that this value
affects both time and memory complexity, and decided to perform our benchmarks
using $\frac{a}{w}=10$, which we consider a sensible option. To corroborate
our choice, we present here a sensitivity analysis to determine how different
ratios affect the performance of those algorithms.

A sensitivity analysis was conducted by keeping the number of working nodes
$w$ fixed and by varying the overall capacity $a$. More specifically, we
conducted experiments on the following scenarios:

  * •

Stable: we consider a cluster of one million working nodes ($w=10^{6}$);

  * •

One-shot removal of 20% of the nodes: from an initial size of one million
working nodes ($w=10^{6}$), we randomly remove $20\%$ of the nodes
(effectively resulting in a scenario where only $800\ 000$ nodes are operative
during lookup);

  * •

One-shot removal of 65% of the nodes: from an initial size of one million
working nodes ($w=10^{6}$), we randomly remove $65\%$ of the nodes
(effectively resulting in a scenario where only $350\ 000$ nodes are operative
during lookup).

The considered $\frac{a}{w}$ ratios are $5$, $10$, $20$, $50$, and $100$
(where $w$ is always the initial size of $10^{6}$ nodes). Both lookup time and
memory usage where measured. Beside the stable scenario, we choose to study
one-shot removals of $20\%$ and $65\%$ of the nodes. The former can be
considered as a realistic worst-case threshold for the number of failing nodes
during the regular life cycle of a cluster, whereas the latter was chosen
because it exhibits similar lookup performance between Memento, Anchor, and Dx
(as shown in Sec. VIII-D). The results also report the values for Memento as a
baseline.

Figure 27: Sensitivity to $\frac{a}{w}$ \- Lookup time (Stable) Figure 28:
Sensitivity to $\frac{a}{w}$ \- Memory usage (Stable)

In the Stable scenario, the performance of Dx is heavily affected by large
over-provisioning ratios, with the lookup time growing linearly (as shown in
Fig. 27). On the contrary, Anchor continues to perform well, although showing
a logarithmic growth as the ratio increases (as expected from the asymptotic
complexity). With respect to memory usage, both Anchor and Dx suffer
considerably from large ratios, as shown in Fig. 28. In practice, the need for
preallocating data structures based on the expected overall capacity, and the
penalties incurred when overestimating the maximum scale of the system could
represent a significant hindrance when deploying solutions based on Anchor or
Dx. On the contrary, Memento does not limit the overall capacity of the
cluster and always maintains minimal memory usage and optimal time
performance.

Figure 29: Sensitivity to $\frac{a}{w}$ \- Lookup time (20% removals) Figure
30: Sensitivity to $\frac{a}{w}$ \- Memory usage (20% removals)

As expected, the performance of all the considered algorithms worsens as nodes
are removed from the system. In both evaluation scenarios with one-shot
removal of a percentage of the nodes, it is possible to observe a linear
growth of the lookup time for Dx, and a logarithmic growth for Anchor as the
ratio $\frac{a}{w}$ increases (Figs. 29 and 31). It is also worth noting that
with $\frac{a}{w}=10$ and $65\%$ of the nodes removed, the lookup performance
of all three considered algorithms is almost equal. Meanwhile, with only
$20\%$ of the nodes removed Anchors is the worst performer.

Figure 31: Sensitivity to $\frac{a}{w}$ \- Lookup time (65% removals) Figure
32: Sensitivity to $\frac{a}{w}$ \- Memory usage (65% removals)

Concerning memory usage, it comes at no surprise that both Anchor and Dx show
similar results in all scenarios (Figs. 30 and 32). The slight differences
which can be observed as the number of removals increases (from no removals,
up to 65%) can be explained by the need for storing the order of the removals.

###  VIII-F Discussion

Memento shows to be asymptotically slower than the other considered
algorithms. However, as shown in this section, it is faster in practice. The
asymptotic complexity is given by two parts:

  1. 1.

$O(ln(n))$ which is given by the initial execution of Jump (Alg. 4 line $2$),
and

  2. 2.

$O([ln(\frac{n}{w})]^{2})$ which is given by the two nested loops (Alg. 4
lines $3$ to $11$).

As discussed in Sec. IV-A, Jump achieves high speed by avoiding memory
accesses and operating at CPU speed. This is evident from the comparison shown
in Figs. 23 and 24, where Jump consistently outperforms all other algorithms.
The Memento algorithm incorporates Jump as its initial instruction and enters
the nested loops only if the bucket returned by Jump is not working. When all
buckets are working, Memento performs similarly to Jump. However, as buckets
are removed, the latter part of the complexity becomes increasingly
significant. Nonetheless, Memento exhibits better performance than Anchor and
Dx until approximately $65\%$ of the buckets are removed. In real-world
production environments, significant efforts are made to prevent failures,
resulting in a low probability of concurrent failures. Additionally, if more
than $20\%$ of the nodes fail simultaneously, the performance or memory
consumption of the consistent hashing algorithm becomes a secondary concern.
On the whole, we argue that Memento has an edge over Anchor and Dx by not
requiring an upper limit on the cluster size: as shown in our sensitivity
analysis, it is evident how larger upper bounds have a significant impact on
the memory requirements of Anchor and on the lookup performance of Dx. The
recommended usage pattern for Memento involves scaling the cluster by adding
and removing buckets in a LIFO order, utilizing replacements exclusively for
failures. This approach ensures that the internal structure remains empty,
resulting in optimal performance and minimal memory usage.

##  IX Conclusion

In this paper, we presented a novel consistent hashing algorithm named
MementoHash, which improves upon state-of-the-art algorithms such as JumpHash,
AnchorHash, and DxHash. We provided implementation details and theoretical
guarantees. MementoHash is an advancement of JumpHash, capable of handling
random failures while maintaining minimal memory usage and optimal time
performance. Unlike AnchorHash and DxHash, it does not require fixing the
overall capacity of the cluster, thus allowing for indefinite scalability. The
recommended usage pattern for Memento involves scaling the cluster by adding
and removing buckets in a Last-In-First-Out order, utilizing replacements
exclusively for failures. This approach ensures that the internal structure
remains empty, resulting in optimal performance and minimal memory usage. By
means of an experimental evaluation, we measured and compared the behavior of
those algorithms concerning lookup time and memory usage. Results show that
the lookup time of MementoHash is on par with JumpHash and considerably better
than both AnchorHash and DxHash. In terms of memory usage, MementoHash ranks
second only to JumpHash. However, JumpHash does not allow random removals, and
only the last added node can be removed. To address this limitation,
AnchorHash and DxHash keep track of all the nodes of the cluster (working and
not working). To ensure balance and minimal disruption, those algorithms force
an upper bound to the overall capacity of the cluster, leading to reduced
scalability. MementoHash overcomes the limitations of JumpHash without
limiting the overall capacity of the cluster. Compared to AnchorHash and
DxHash, our approach exhibits similar memory usage in the worst-case scenario
and performs significantly better in the best-case scenario.

##  X Future work

In order to further expand the scope of application of MementoHash and
facilitate its implementation in existing or novel distributed solutions,
several avenues of future work can be explored. First and foremost, it is
worth investigating the feasibility of extending MementoHash to maintain full
consistency when nodes may not unanimously agree on the removal order.
Furthermore, we aim at investigating the applicability of our solution to a
scenario with bounded loads [16].

## References

  * [1] S. Priyamvada, “Analysis of various hash function,” _International Journal of Innovative Science and Research Technology_ , vol. 3, 2018.
  * [2] D. Thaler and C. V. Ravishankar, “A name-based mapping scheme for rendezvous,” in _Technical Report CSE-TR-316-96, University of Michigan_. University of Michigan, 1996\.
  * [3] D. G. Thaler and C. V. Ravishankar, “Using name-based mappings to increase hit rates,” _IEEE/ACM Transactions on networking_ , vol. 6, no. 1, pp. 1–14, 1998.
  * [4] D. Karger, E. Lehman, T. Leighton, R. Panigrahy, M. Levine, and D. Lewin, “Consistent hashing and random trees: Distributed caching protocols for relieving hot spots on the world wide web,” in _Proceedings of the twenty-ninth annual ACM symposium on Theory of computing_ , 1997, pp. 654–663.
  * [5] D. Karger, A. Sherman, A. Berkheimer, B. Bogstad, R. Dhanidina, K. Iwamoto, B. Kim, L. Matkins, and Y. Yerushalmi, “Web caching with consistent hashing,” _Comput. Netw._ , vol. 31, no. 11–16, p. 1203–1213, may 1999\.
  * [6] J. Lamping and E. Veach, “A fast, minimal memory, consistent hash algorithm,” _arXiv preprint arXiv:1406.2294_ , 2014.
  * [7] B. Appleton and M. O’Reilly, “Multi-probe consistent hashing,” _arXiv preprint arXiv:1505.00062_ , 2015.
  * [8] D. E. Eisenbud, C. Yi, C. Contavalli, C. Smith, R. Kononov, E. Mann-Hielscher, A. Cilingiroglu, B. Cheyney, W. Shang, and J. D. Hosein, “Maglev: A fast and reliable software network load balancer,” in _13th $\\{$USENIX$\\}$ Symposium on Networked Systems Design and Implementation ($\\{$NSDI$\\}$ 16)_, 2016, pp. 523–535.
  * [9] G. Mendelson, S. Vargaftik, K. Barabash, D. H. Lorenz, I. Keslassy, and A. Orda, “Anchorhash: A scalable consistent hash,” _IEEE/ACM Transactions on Networking_ , vol. 29, no. 2, pp. 517–528, 2020.
  * [10] C. Dong and F. Wang, “Dxhash: A scalable consistent hash based on the pseudo-random sequence,” _arXiv preprint arXiv:2107.07930_ , 2021.
  * [11] M. Coluzzi, A. Brocco, P. Contu, and T. Leidi, “A survey and comparison of consistent hashing algorithms,” in _2023 IEEE International Symposium on Performance Analysis of Systems and Software_ , April 2023.
  * [12] M. Coluzzi, A. Brocco, and T. Leidi, “Consistently faster: A survey and fair comparison of consistent hashing algorithms,” in _Proceedings of SEBD 2023: 31st Symposium on Advanced Database System, July 02–05, 2023, Galzignano Terme, Padua, Italy_ , ser. CEUR Workshop Proceedings, 2023.
  * [13] Institute of Information Systems and Networking at SUPSI. java-consistent-hashing-algorithms. [Online]. Available: https://github.com/SUPSI-DTI-ISIN/java-consistent-hashing-algorithms
  * [14] N. Cressie and M. Borkent, “The moment generating function has its moments,” _Journal of Statistical Planning and Inference_ , vol. 13, pp. 337–344, 1986\.
  * [15] Z.-W. Sun, “Arithmetic theory of harmonic numbers,” _Proceedings of the American Mathematical Society_ , vol. 140, no. 2, pp. 415–428, 2012.
  * [16] V. Mirrokni, M. Thorup, and M. Zadimoghaddam, “Consistent hashing with bounded loads,” 2016. [Online]. Available: https://arxiv.org/abs/1608.01350