[0001] This application claims the benefit of United States Provisional Patent Application
No. 63/094,328, filed October 20, 2020, and United States Provisional Patent Application No
63/094,797, filed October 21,2020, each of which is hereby incorporated by reference herein
in its entirety.
Background
[0002] In-memory data structures (e.g., REDIS) are widely used to store data that needs to
be quickly accessed for applications such as gaming, advertising, financial services,
healthcare, and many other applications. In many instances, in-memory data structures can be
applied in distributed systems.
[0003] Conflict-free replicated data types (CRDTs) are data structures that can be
replicated across multiple nodes in a distributed system network to achieve strong eventual
consistency without requiring consensus and introducing the delay and reduced availability
consensus involves.
[0004] It is therefore desirable to implement CRDTs in in-memory data structures.
Summary
[0005] In accordance with some embodiments, systems, methods, and media for
implementing conflict-free replicated data types in in-memory data structures are provided.
[0006] In some embodiments, systems for implementing conflict-free replicated data
types in in-memory data structures are provided, the systems comprising: a memory; and at
least one hardware processor coupled to the memory and collectively configured to: mark a
first key of a conflict-free replicated data type as to be deleted; send an update message
reflecting that the first key is to be deleted to a first replica of an in-memory data structure;
receive a plurality of messages each acknowledging that the first key is to be deleted;
determine that the plurality of messages includes a message for each of a plurality of shards of
the first replica; and in response to determining that the plurality of messages includes a
message for each of the plurality of shards of the first replica, delete the first key.
1
[0007] In some of these embodiments, the at least one hardware processor is further
configured to: maintain a counter wherein the counter tracks an interval value and logical
clock for a plurality of intervals.
[0008] In some of these embodiments, the at least one hardware processor is further
configured to: determine a second replica that most recently updated a second key and setting
the second replica as an eviction owner of the second key; determine that a memory usage of
the second replica exceeds a threshold; determine that the second key is at least one of a least
frequently used key and a least recently used key of a plurality of keys stored by the second
replica; and delete the second key in response to determining that the memory usage of the
second replica exceeding the threshold and determining that the second key is at least one of a
least frequently used key and a least recently used key of the plurality of keys stored by the
second replica.
[0009] In some of these embodiments, the at least one hardware processor is further
configured to: associate a third key with an expiration data owner; determine that the third key
has expired; and determine that the third key is associated with the expiration data owner; and
in response to determining that the third key has expired and determining that the third key is
associated with the expiration data owner, delete the third key by the expiration data owner.
[0010] In some of these embodiments, the at least one hardware processor is further
configured to: by each of a plurality of replicas: create a stream of append-only updates for
updates to the each of the plurality of replicas; and replicate the stream to each other of the
plurality of replicas.
[0011] In some of these embodiments, the at least one hardware processor is further
configured to: identify a fourth key created by a fourth replica as having a first value and a
first type; identify a fifth key created by a fifth replica as having a second value that is
different from the first value and a second type that is different from the first type; and apply a
precedence to the fourth key and the fifth key based on the first type and the second type so
that the fourth key is assigned the second value.
[0012] In some of embodiments, methods for implementing conflict-free replicated data
types in in-memory data structures are provided, the methods comprising: marking a first key
of a conflict-free replicated data type as to be deleted; sending an update message reflecting
that the first key is to be deleted to a first replica of an in-memory data structure; receiving a
plurality of messages each acknowledging that the first key is to be deleted; determining that
2
the plurality of messages includes a message for each of a plurality of shards of the first
replica; and in response to determining that the plurality of messages includes a message for
each of the plurality of shards of the first replica, deleting the first key.
[0013] In some of these embodiments, the method further comprises: maintaining a
counter wherein the counter tracks an interval value and logical clock for a plurality of
intervals.
[0014] In some of these embodiments, the method further comprises: determining a
second replica that most recently updated a second key and setting the second replica as an
eviction owner of the second key; determining that a memory usage of the second replica
exceeds a threshold; determining that the second key is at least one of a least frequently used
key and a least recently used key of a plurality of keys stored by the second replica; and
deleting the second key in response to determining that the memory usage of the second
replica exceeding the threshold and determining that the second key is at least one of a least
frequently used key and a least recently used key of the plurality of keys stored by the second
replica.
[0015] In some of these embodiments, the method further comprises: associating a third
key with an expiration data owner; determining that the third key has expired; and
determining that the third key is associated with the expiration data owner; and in response to
determining that the third key has expired and determining that the third key is associated
with the expiration data owner, deleting the third key by the expiration data owner.
[0016] In some of these embodiments, the method further comprises: by each of a
plurality of replicas: creating a stream of append-only updates for updates to the each of the
plurality of replicas; and replicating the stream to each other of the plurality of replicas.
[0017] In some of these embodiments, the method further comprises: identifying a fourth
key created by a fourth replica as having a first value and a first type; identifying a fifth key
created by a fifth replica as having a second value that is different from the first value and a
second type that is different from the first type; and applying a precedence to the fourth key
and the fifth key based on the first type and the second type so that the fourth key is assigned
the second value.
[0018] In some of embodiments, non-transitory computer-readable medium containing
computer executable instructions that, when executed by a processor, cause the processor to
perform a method for implementing conflict-free replicated data types in in-memory data
3
structures are provided, the method comprising: marking a first key of a conflict-free
replicated data type as to be deleted; sending an update message reflecting that the first key is
to be deleted to a first replica of an in-memory data structure; receiving a plurality of
messages each acknowledging that the first key is to be deleted; determining that the plurality
of messages includes a message for each of a plurality of shards of the first replica; and in
response to determining that the plurality of messages includes a message for each of the
plurality of shards of the first replica, deleting the first key.
[0019] In some of these embodiments, the method further comprises: maintaining a
counter wherein the counter tracks an interval value and logical clock for a plurality of
intervals.
[0020] In some of these embodiments, the method further comprises: determining a second
replica that most recently updated a second key and setting the second replica as an eviction
owner of the second key; determining that a memory usage of the second replica exceeds a
threshold; determining that the second key is at least one of a least frequently used key and a
least recently used key of a plurality of keys stored by the second replica; and deleting the
second key in response to determining that the memory usage of the second replica exceeding
the threshold and determining that the second key is at least one of a least frequently used key
and a least recently used key of the plurality of keys stored by the second replica.
[0021] In some of these embodiments, the method further comprises: associating a third
key with an expiration data owner; determining that the third key has expired; and
determining that the third key is associated with the expiration data owner; and in response to
determining that the third key has expired and determining that the third key is associated
with the expiration data owner, deleting the third key by the expiration data owner.
[0022] In some of these embodiments, the method further comprises: by each of a
plurality of replicas: creating a stream of append-only updates for updates to the each of the
plurality of replicas; and replicating the stream to each other of the plurality of replicas.
[0023] In some of these embodiments, the method further comprises: identifying a fourth
key created by a fourth replica as having a first value and a first type; identifying a fifth key
created by a fifth replica as having a second value that is different from the first value and a
second type that is different from the first type; and applying a precedence to the fourth key
and the fifth key based on the first type and the second type so that the fourth key is assigned
the second value.
4
Brief Description of the Drawings
[0024] FIG. 1 is an example flow diagram of a process for deleting a key in accordance
with some embodiments.
[0025] FIG. 2 is an example block diagram of system in accordance with some
embodiments.
[0026] FIG. 3 is an example block diagram of hardware in accordance with some
embodiments.
Detailed Description
[0027] In accordance with some embodiments, mechanism, including systems, methods,
and media, for implementing conflict-free replicated data types (CRDTs) in in-memory data
structures are provided.
[0028] In some embodiments, these mechanisms provide several enhancements on top of
well-known, academic-proven CRDTs and allow in-memory data structures (e.g., REDIS) to
be deployed in an active-active deployment with minimal changes to APis of the in-memory
data structures (e.g., REDIS) and the known behavior of the in-memory data structures (e.g.,
RED IS).
[0029] In some embodiments, a unique property of the mechanisms described herein is
that that they apply CRDT semantics to pre-existing systems of in-memory data structure
(e.g., REDIS) data types and commands to create an eventually consistent, distributed system
that exhibits application and user experiences that are very similar to those exhibited by a
non-distributed in-memory data structures.
[0030] Sharding is a well-known and common method of distributing data between nodes
(referred to as "shards") in a system in order to achieve scale, e.g., store more data or process
transactions faster. When sharding is used, it may be necessary for a system to store
configuration information about the sharding topology, e.g., the mapping between data
elements and the node that stores and handles them. Because such a system is dynamic in
nature, this configuration information can change; for example, if a new node is added to a
system and some data should migrate to the new node, the configuration information for the
system should be updated. This process is called re-sharding.

What is claimed is:
1. A system for implementing conflict-free replicated data types in in-memory data
structures, comprising:
a memory; and
at least one hardware processor coupled to the memory and collectively configured to:
mark a first key of a conflict-free replicated data type as to be deleted;
send an update message reflecting that the first key is to be deleted to a first replica of
an in-memory data structure;
receive a plurality of messages each acknowledging that the first key is to be deleted;
determine that the plurality of messages includes a message for each of a plurality of
shards of the first replica; and
in response to determining that the plurality of messages includes a message for each
of the plurality of shards of the first replica, delete the first key.
2. The system of claim 1, where the at least one hardware processor is further configured
to:
maintain a counter wherein the counter tracks an interval value and logical clock for a
plurality of intervals.
3. The system of claim 1 or 2, where the at least one hardware processor is further
configured to:
determine a second replica that most recently updated a second key and setting the
second replica as an eviction owner of the second key;
determine that a memory usage of the second replica exceeds a threshold;
determine that the second key is at least one of a least frequently used key and a least
recently used key of a plurality of keys stored by the second replica; and
delete the second key in response to determining that the memory usage of the second
replica exceeding the threshold and determining that the second key is at least one of a least
23
frequently used key and a least recently used key of the plurality of keys stored by the second
replica.
4. The system of any one of the preceding claims, where the at least one hardware
processor is further configured to:
associate a third key with an expiration data owner;
determine that the third key has expired; and
determine that the third key is associated with the expiration data owner; and
in response to determining that the third key has expired and determining that the third
key is associated with the expiration data owner, delete the third key by the expiration data
owner.
5. The system of any one of the preceding claims, where the at least one hardware
processor is further configured to:
by each of a plurality of replicas:
create a stream of append-only updates for updates to the each of the plurality
of replicas; and
replicate the stream to each other of the plurality of replicas.
6. The system of any one of the preceding claims, where the at least one hardware
processor is further configured to:
identify a fourth key created by a fourth replica as having a first value and a first type;
identify a fifth key created by a fifth replica as having a second value that is different
from the first value and a second type that is different from the first type; and
apply a precedence to the fourth key and the fifth key based on the first type and the
second type so that the fourth key is assigned the second value.
7. A method for implementing conflict-free replicated data types in in-memory data
structures, comprising:
marking a first key of a conflict-free replicated data type as to be deleted;
24
sending an update message reflecting that the first key is to be deleted to a first replica of an
in-memory data structure;
receiving a plurality of messages each acknowledging that the first key is to be deleted;
determining that the plurality of messages includes a message for each of a plurality of shards
of the first replica; and
in response to determining that the plurality of messages includes a message for each of the
plurality of shards of the first replica, deleting the first key.
8. The method of claim 7, further comprising:
maintaining a counter wherein the counter tracks an interval value and logical clock
for a plurality of intervals.
9. The method of claim 7 or 8, further comprising:
determining a second replica that most recently updated a second key and setting the
second replica as an eviction owner of the second key;
determining that a memory usage of the second replica exceeds a threshold;
determining that the second key is at least one of a least frequently used key and a
least recently used key of a plurality of keys stored by the second replica; and
deleting the second key in response to determining that the memory usage of the
second replica exceeding the threshold and determining that the second key is at least one of a
least frequently used key and a least recently used key of the plurality of keys stored by the
second replica.
10. The method of any one of claims 7 to 9, further comprising:
associating a third key with an expiration data owner;
determining that the third key has expired; and
determining that the third key is associated with the expiration data owner; and
in response to determining that the third key has expired and determining that the third
key is associated with the expiration data owner, deleting the third key by the expiration data
owner.
25
11. The method of any one of claims 7 to 10, further comprising:
by each of a plurality of replicas:
creating a stream of append-only updates for updates to the each of the
plurality of replicas; and
replicating the stream to each other of the plurality of replicas.
12. The method of any one of claims 7 to 11, further comprising:
identifying a fourth key created by a fourth replica as having a first value and a first
type;
identifying a fifth key created by a fifth replica as having a second value that is
different from the first value and a second type that is different from the first type; and
applying a precedence to the fourth key and the fifth key based on the first type and
the second type so that the fourth key is assigned the second value.
13. A non-transitory computer-readable medium containing computer executable
instructions that, when executed by a processor, cause the processor to perform a method for
implementing conflict-free replicated data types in in-memory data structures, the method
compnsmg:
marking a first key of a conflict-free replicated data type as to be deleted;
sending an update message reflecting that the first key is to be deleted to a first replica of an
in-memory data structure;
receiving a plurality of messages each acknowledging that the first key is to be deleted;
determining that the plurality of messages includes a message for each of a plurality of shards
of the first replica; and
in response to determining that the plurality of messages includes a message for each of the
plurality of shards of the first replica, deleting the first key.
14. The non-transitory computer-readable medium of claim 13, wherein the method
further comprises:
26
maintaining a counter wherein the counter tracks an interval value and logical clock
for a plurality of intervals.
15. The non-transitory computer-readable medium of claim 13 or 14, wherein the method
further comprises:
determining a second replica that most recently updated a second key and setting the
second replica as an eviction owner of the second key;
determining that a memory usage of the second replica exceeds a threshold;
determining that the second key is at least one of a least frequently used key and a
least recently used key of a plurality of keys stored by the second replica; and
deleting the second key in response to determining that the memory usage of the
second replica exceeding the threshold and determining that the second key is at least one of a
least frequently used key and a least recently used key of the plurality of keys stored by the
second replica.
16. The non-transitory computer-readable medium of any one of claims 13 to 15, wherein
the method further comprises:
associating a third key with an expiration data owner;
determining that the third key has expired; and
determining that the third key is associated with the expiration data owner; and
in response to determining that the third key has expired and determining that the third
key is associated with the expiration data owner, deleting the third key by the expiration data
owner.
17. The non-transitory computer-readable medium of any one of claims 13 to 16, wherein
the method further comprises:
by each of a plurality of replicas:
creating a stream of append-only updates for updates to the each of the
plurality of replicas; and
replicating the stream to each other of the plurality of replicas.18. The non-transitory computer-readable medium of any one of claims 13 to 17, wherein
the method further comprises:
identifying a fourth key created by a fourth replica as having a first value and a first
type;
identifying a fifth key created by a fifth replica as having a second value that is
different from the first value and a second type that is different from the first type; and
applying a precedence to the fourth key and the fifth key based on the first type and
the second type so that the fourth key is assigned the second value.