Prefetching keys for garbage collection
Techniques are provided for implementing a garbage collection process and a prediction read ahead mechanism to prefetch keys into memory to improve the efficiency and speed of the garbage collection process. A log structured merge tree is used to store keys of key-value pairs within a key-value store. If a key is no longer referenced by any worker nodes of a distributed storage architecture, then the key can be freed to store other data. Accordingly, garbage collection is performed to identify and free unused keys. The speed and efficiency of garbage collection is improved by dynamically adjusting the amount and rate at which keys are prefetched from disk and cached into faster memory for processing by the garbage collection process.
1. A system, comprising:
a distributed storage architecture including a plurality of worker nodes managing distributed storage comprised of storage devices hosted by the plurality of worker nodes; and
a worker node of the distributed storage architecture owning key value pairs of a key value store hosted within the distributed storage, wherein the worker node:
performs garbage collection rounds of a garbage collection process, wherein during a first garbage collection ground, the worker node:
receives a first set of probabilistic structures from the plurality of worker nodes, wherein the first set of probabilistic structures provide indications of keys that are in-use by the plurality of worker nodes;
compares the first set of probabilistic structures to a first set of keys of the key value pairs owned by the worker node to identify unused keys within the first set of keys that are not indicated by at least one probabilistic structure; and
frees key value pairs associated with the unused keys within the first set of keys; and
predicts, using a predictive read ahead mechanism, a second set of keys that will be evaluated during a second garbage collection round subsequent the first garbage collection round, wherein the second set of keys are pre-fetched from the storage devices and are cached into memory for evaluation during the second garbage collection round.
2. The system of claim 1 , wherein during the second garbage collection round, the worker node:
receives a second set of probabilistic structures from the plurality of worker nodes, wherein the second set of probabilistic structures provide indications of keys that are in-use by the plurality of worker nodes at a point in time when the second set of probabilistic structures were created;
compares the second set of probabilistic structures to the second set of keys pre-fetched and cached within the memory to identify unused keys within the second set of keys that are not indicated by at least one probabilistic structure of the second set of probabilistic structures; and
frees key value pairs associated with the unused keys within the second set of keys.
3. The system of claim 1 , wherein the worker node:
monitors a rate at which probabilistic structures are being received by the garbage collection process; and
selects an amount of keys for inclusion within the second set of keys based upon the rate at which the probabilistic structures are being received by the garbage collection process.
4. The system of claim 1 , wherein the worker node:
monitors disk latency of the storage devices; and
selects an amount of keys for inclusion within the second set of keys based upon the disk latency of the storage devices.
5. The system of claim 1 , wherein the worker node:
implements a feedback loop to collect operational statistics associated with performing garbage collection of the key value store; and
compares the operational statistics to a rate of prefetching and caching keys into memory in order to select an amount of keys for inclusion within the second set of key.
6. The system of claim 5 , wherein the operational statistics correspond to at least one of an amount of unused keys being garbage collected, access patterns of the key value store, a fullness of the key value store, a timespan between garbage collection rounds, or a total time to complete a garbage collection round.
7. The system of claim 1 , wherein the worker node:
monitors a rate of delete operations being performed upon the key value store; and
selects an amount of keys for inclusion within the second set of keys based upon the rate of the delete operations being performed.
8. The system of claim 1 , wherein the worker node:
monitors a rate at which probabilistic structures are being validated by the garbage collection process; and
selects an amount of keys for inclusion within the second set of keys based upon the rate at which the probabilistic structures are being validated by the garbage collection process.
9. The system of claim 1 , wherein the worker node:
dynamically adjusts amounts of keys pre-fetched and cached within the memory based upon a rate of processing probabilistic structures.
10. The system of claim 1 , comprising:
a slice service generating probabilistic structures used to indicate in-use keys of the distributed storage that are used to store data, wherein a rate of the slice service sending the probabilistic structures to the garbage collection process is used by the predictive read ahead mechanism to determine a rate and amount of keys to pre-fetch.
11. The system of claim 1 , comprising:
a block service, hosted by the worker node, managing bins of keys owned by the worker node, wherein a rate of the block service receiving probabilistic structures from slice slices of other worker nodes is used by the predictive read ahead mechanism to determine a rate and amount of keys to pre-fetch.
12. The system of claim 1 , wherein the worker node:
in response to determining that a latency of accessing the storage devices exceed a threshold, selects an amount of keys as the second set of keys that is larger than an amount of keys of the first set of keys.
13. The system of claim 1 , wherein the worker node:
in response to determining that a rate at which probabilistic structures are being validated by the garbage collection process exceeds a threshold, selects an amount of keys as the second set of keys that is larger than an amount of keys of the first set of keys.
14. The system of claim 1 , wherein the worker node:
in response to determining that a rate at which delete operations are being processed and resulting in unused keys exceeds a threshold, selects an amount of keys as the second set of keys that is larger than an amount of keys of the first set of keys.
15. A method comprising:
implementing a feedback loop to collect operational statistics associated with performing garbage collection for a key value store hosted within distributed storage of a distributed storage architecture including a plurality of worker nodes managing the distributed storage comprised of storage devices hosted by the plurality of worker nodes;
comparing the operational statistics to a rate of prefetching and caching keys into memory in order to select an amount of keys to pre-fetch from the storage devices and cache within the memory for a next garbage collection round;
pre-fetching and caching the amount of keys as a set of keys within the memory; and
performing the next garbage collection round comprising:
receiving a set of probabilistic structures from the plurality of worker nodes, wherein the set of probabilistic structures provide indications of keys that are in-use by the plurality of worker nodes;
comparing the set of probabilistic structures to the set of keys cached within the memory to identify unused keys within the set of keys that are not indicated by at least one probabilistic structure; and
freeing key value pairs associated with the unused keys within the set of keys.
16. The method of claim 15 , comprising:
dynamically adjusting amounts of keys pre-fetched and cached within the memory for subsequent garbage collection rounds based upon a rate of processing probabilistic structures.
17. The method of claim 15 , comprising:
dynamically adjusting amounts of keys pre-fetched and cached within the memory for subsequent garbage collection rounds based upon a rate of delete operations being performed upon the key value store.
18. The method of claim 15 , comprising:
dynamically adjusting amounts of keys pre-fetched and cached within the memory for subsequent garbage collection rounds based upon disk latency of the storage devices.
19. A non-transitory machine readable medium comprising instructions, which when executed by a machine, causes the machine to:
evaluate operational statistics associated with performing garbage collection of a key value store hosted within distributed storage of a distributed storage architecture including a plurality of worker nodes managing the distributed storage comprised of storage devices hosted by the plurality of worker nodes to select an amount of keys to pre-fetch from the storage devices and cache within memory for a garbage collection round;
pre-fetch and caching the amount of keys as a set of keys within the memory; and
perform the garbage collection round comprising:
receiving a set of probabilistic structures from the plurality of worker nodes, wherein the set of probabilistic structures provide indications of keys that are in-use by the plurality of worker nodes;
comparing the set of probabilistic structures to the set of keys cached within the memory to identify unused keys within the set of keys that are not indicated by at least one probabilistic structure; and
freeing key value pairs associated with the unused keys within the set of keys.
20. The non-transitory machine readable medium of claim 19 , wherein the operational statistics correspond to at least one of an amount of unused keys being garbage collected, access patterns of the key value store, a fullness of the key value store, a timespan between garbage collection rounds, a total time to complete a garbage collection round.