Granted Patent B2

US 12,493,587 · App. 17/506,162 · Granted Dec 9, 2025

Inventors: Yuval Inbar (Giva'ataim, IL); Yossi Gottlieb (Clil, IL)

Assignee: Redis, Ltd.

G06F16/1844G06F16/162G06F16/172G06F16/178G06F16/1805

Abstract

Claims (80)

1 . A system for implementing conflict-free replicated data types in in-memory data structures within a distributed system, 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 implemented in an in-memory data structure to be deleted;

send an update message to a first replica of the in-memory data structure, wherein the update message is associated with the first key to be deleted from the first replica of the in-memory data structure, wherein the first replica of the in-memory data structure includes a plurality of shards;

receive a plurality of messages from the first replica of the in-memory data structure, wherein the plurality of message is in a vector clock structure and wherein each message of the plurality of messages corresponds to its corresponding shard of the plurality of shards, wherein the each message of the plurality of messages is an acknowledgement by the corresponding shard that the first key is to be deleted, wherein at least one message of the plurality of messages identifies a number of other shards in the plurality of shards, and wherein at least one shard of the plurality of shards does not hold the first key;

and

in response to receiving the plurality of messages, 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 , 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 frequently used key and a least recently used key of the plurality of keys stored by the second replica.

4 . The system of claim 1 , 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 claim 1 , 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 claim 1 , 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 . The system of claim 1 , wherein the first key marked to be deleted becomes invisible to a user without being deleted.

8 . The system of claim 1 , wherein the at least one message of the plurality of messages includes data associated with sharding topology of the plurality of shards.

9 . A method for implementing conflict-free replicated data types in in-memory data structures within a distributed system, comprising:

marking a first key of a conflict-free replicated data type implemented in an in-memory data structure to be deleted;

sending an update message to a first replica of the in-memory data structure, wherein the update message is associated with the first key to be deleted from the first replica of the in-memory data structure, wherein the first replica of the in-memory data structure includes a plurality of shards;

receiving a plurality of messages from the first replica of the in-memory data structure, wherein the plurality of message is in a vector clock structure and wherein each message of the plurality of messages corresponds to its corresponding ea shard of the plurality of shards, wherein the each message of the plurality of messages is an acknowledgement by the corresponding shard that the first key is to be deleted, wherein at least one message of the plurality of messages identifies a number of other shards in the plurality of shards, and wherein at least one of the plurality of shards does not hold the first key;

and

in response to receiving the plurality of messages, deleting the first key.

10 . The method of claim 9 , further comprising:

maintaining a counter wherein the counter tracks an interval value and logical clock for a plurality of intervals.

11 . The method of claim 9 , 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.

12 . The method of claim 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.

13 . The method of claim 9 , 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.

14 . The method of claim 9 , 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.

15 . 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 within a distributed system, the method comprising:

marking a first key of a conflict-free replicated data type implemented in an in-memory data structure to be deleted;

sending an update message to a first replica of the in-memory data structure, wherein the update message is associated with the first key to be deleted from the first replica of the in-memory data structure, wherein the first replica of the in-memory data structure includes a plurality of shards;

receiving a plurality of messages from the first replica of the in-memory data structure, wherein the plurality of message is in a vector clock structure and wherein each message of the plurality of messages corresponds to its corresponding shard of the plurality of shards, wherein the each message of the plurality of messages is an acknowledgement by the corresponding shard that the first key is to be deleted, wherein at least one message of the plurality of messages identifies a number of other shards in the plurality of shards, and wherein at least one of the plurality of shards does not hold the first key;

and

in response to receiving the plurality of messages, deleting the first key.

16 . The non-transitory computer-readable medium of claim 15 , wherein the method further comprises:

maintaining a counter wherein the counter tracks an interval value and logical clock for a plurality of intervals.

17 . The non-transitory computer-readable medium of claim 15 , 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.

18 . The non-transitory computer-readable medium of claim 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.

19 . The non-transitory computer-readable medium of claim 15 , 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.

20 . The non-transitory computer-readable medium of claim 15 , 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.

Assignments (2)

Continuity (3)

References Cited (19)