REPLACING KEY-VALUE PAIR SETS WITH NEW KEY-VALUE PAIR SETS
In some implementations, a memory device may determine, from a list of key-value pair sets, a key-value pair set. The memory device may identify, from the key-value pair set selected from the list of key-value pair sets, a first key that is included in at least one other key-value pair set from the list of key-value pair sets. The memory device may identify, from the key-value pair set selected from the list of key-value pair sets, a second key that is not included in at least one other key-value pair set from the list of key-value pair sets. The memory device may form a new key-value pair set that excludes the first key and includes the second key. The memory device may replace the key-value pair set selected from the list of key-value pair sets with the new key-value pair set.
1 . A method, comprising:
selecting a first list of key-value pair sets and a second list of key-value pair sets;
providing the first list of key-value pair sets and the second list of key-value pair sets to a merge loop process;
obtaining a first key-value pair and a second key-value pair from the merge loop process;
forming a new key-value pair set that excludes the first key-value pair and includes the second key-value pair in accordance with a set of rules; and
replacing the second list of key-value pair sets with the new key-value pair set.
2 . The method of claim 1 , further comprising:
performing a garbage collection on a plurality of key-value pair sets to remove duplicate keys from the plurality of key-value pair sets, wherein the second list of key-value pair sets comprises garbage key-value pair sets replaced during the garbage collection.
3 . The method of claim 1 , wherein key-value pair sets in the first list of key-value pair sets are newer than key-value pair sets in the second list of key-value pair sets.
4 . The method of claim 1 , wherein the new key-value pair set excludes the first key-value pair in accordance with the set of rules based on the first key-value pair being included in the first list of key-value pair sets.
5 . The method of claim 1 , wherein the new key-value pair set includes the second key-value pair in accordance with the set of rules based on the second key-value pair being included in the second list of key-value pair sets.
6 . The method of claim 1 , wherein the first list of key-value pair sets and the second list of key-value pair sets are associated with a log structured merge (LSM) tree of an LSM key-value database.
7 . The method of claim 1 , wherein:
the first key-value pair is associated with a duplicate key and is able to be discarded when forming the new key-value pair set; and
the second key-value pair is kept when forming the new key-value pair set.
8 . The method of claim 1 , wherein the first list of key-value pair sets includes sparse key-value pair sets that are ordered by age, and wherein the sparse key-value pair sets include key-value pair sets that are newer than key-value pair sets in the second list of key-value pair sets.
9 . The method of claim 1 , further comprising:
regenerating an index of sorted keys for the first list of key-value pair sets based on the second list of key-value pair sets being replaced with the new key-value pair set.
10 . The method of claim 1 , wherein the new key-value pair set inherits value data from the first list of key-value pair sets and creates new value data for the second list of key-value pair sets.
11 . The method of claim 1 , further comprising:
determining a first amount of key-value data from the second list of key-value pair sets that is used to form the new key-value pair set;
determining a second amount of key data from the first list of key-value pair sets that is used to form the new key-value pair set; and
determining a third amount of duplicate key-value data from the second list of key-value pair sets,
wherein the first list of key-value pair sets and the second list of key-value pair sets are selected based on the first amount, the second amount, and the third amount.
12 . A memory device, comprising:
one or more components configured to:
select a first list of key-value pair sets and a second list of key-value pair sets;
provide the first list of key-value pair sets and the second list of key-value pair sets to a merge loop process;
obtain a first key-value pair and a second key-value pair from the merge loop process;
form a new key-value pair set that excludes the first key-value pair and includes the second key-value pair in accordance with a set of rules; and
replace the second list of key-value pair sets with the new key-value pair set.
13 . The memory device of claim 12 , wherein the one or more components are further configured to:
perform a garbage collection on a plurality of key-value pair sets to remove duplicate keys from the plurality of key-value pair sets, wherein the second list of key-value pair sets comprises garbage key-value pair sets replaced during the garbage collection.
14 . The memory device of claim 12 , wherein key-value pair sets in the first list of key-value pair sets are newer than key-value pair sets in the second list of key-value pair sets.
15 . The memory device of claim 12 , wherein the new key-value pair set excludes the first key-value pair in accordance with the set of rules based on the first key-value pair being included in the first list of key-value pair sets.
16 . The memory device of claim 12 , wherein the new key-value pair set includes the second key-value pair in accordance with the set of rules based on the second key-value pair being included in the second list of key-value pair sets.
17 . The memory device of claim 12 , wherein the first list of key-value pair sets and the second list of key-value pair sets are associated with a log structured merge (LSM) tree of an LSM key-value database.
18 . The memory device of claim 12 , wherein:
the first key-value pair is associated with a duplicate key and is able to be discarded when forming the new key-value pair set; and
the second key-value pair is kept when forming the new key-value pair set.
19 . The memory device of claim 12 , wherein the first list of key-value pair sets includes sparse key-value pair sets that are ordered by age, and wherein the sparse key-value pair sets include key-value pair sets that are newer than key-value pair sets in the second list of key-value pair sets.
20 . A system, comprising:
memory; and
a controller configured to:
select a first list of key-value pair sets and a second list of key-value pair sets;
provide the first list of key-value pair sets and the second list of key-value pair sets to a merge loop process;
obtain a first key-value pair and a second key-value pair from the merge loop process;
form a new key-value pair set that excludes the first key-value pair and includes the second key-value pair in accordance with a set of rules; and
replace the second list of key-value pair sets with the new key-value pair set.