IP Library Granted Patent US 10,884,629
Granted Patent B1
US 10,884,629 · App. 16/287,181 · Granted Jan 5, 2021

Shard rebalancing based on over-provisioning

Inventors: Navneeth Kankani (Fremont, CA); Mrinmoy Ghosh (Milpitas, CA)
Assignee: Facebook, Inc.
G06F3/0611G06F3/067G06F3/0631G06F3/0647G06F3/0653
View Patent ↗
Loading inventors, assignments & file history…
Monitor This Case
Get email alerts when status or documents change.
Order Certified Copies
Most orders are placed with the USPTO same day — all within 24 business hours.
Order via The Patent Place →
Pre-filled with this patent's details
Quick Facts
Patent No.
US 10,884,629
App. No.
16/287,181
Granted
Jan 5, 2021
Kind
B1
Abstract

A performance metric of a data shard stored in a first storage portion is monitored. It is determined that the performance metric of the data shard exceeds a threshold. In response to the determination that the performance metric exceeds the threshold, the data shard is reassigned to a second storage portion selected based on an over-provisioning bias of the second storage portion that is different than an over-provisioning bias of the first storage portion or the over-provisioning bias of the first storage portion is increased.

Claims (36)

1. A method comprising:

monitoring a performance metric of a data shard including a plurality of files stored in a first storage portion;

determining that the performance metric of the data shard including the plurality of files exceeds a threshold;

in response to at least the determination that the performance metric exceeds the threshold, increasing the over-provisioning bias of a first storage portion storing a plurality of data shards each storing a plurality of files; and

in response to a determination that a cumulative value the over-provisioning bias associated with an amount of buffer space allocated to the first storage portion meets a cumulative over-provisioning bias limit, rebalancing the plurality of data shards of the first storage portion including by reassigning the data shard to a second storage portion selected based on an over-provisioning bias of the second storage portion that is different than the over-provisioning bias of the first storage portion.

2. The method of claim 1 , wherein the performance metric that is monitored is associated with a frequency of access of the data shard over a specified period of time.

3. The method of claim 1 , wherein the performance metric that is monitored includes one or more of the following: read queries per unit of time, write queries per unit of time, read bandwidth, write bandwidth, read latency, or write latency.

4. The method of claim 1 , wherein at least one of the first storage portion and the second storage portion is a solid-state drive or a portion of a solid-state drive.

5. The method of claim 1 , wherein at least one of the first storage portion and the second storage portion is a Non-Volatile Memory Express set.

6. The method of claim 1 , wherein determining that the performance metric of the data shard exceeds the threshold includes determining that a number of times the data shard has been accessed during a specified period of time is greater than or equal to a specified value.

7. The method of claim 1 , wherein the data shard was reassigned to the second storage portion based on a determination that a specified limit on how many data shards for which the performance metric exceeds the threshold can be reassigned has not been reached.

8. The method of claim 1 , wherein the data shard was reassigned to the second storage portion based on a determination that a cumulative over-provisioning bias limit with respect to a collection of storage portions, of which the first storage portion and the second storage portion are a part, has not been reached.

9. The method of claim 1 , wherein reassigning the data shard to the second storage portion includes issuing a Non-Volatile Memory Express command.

10. The method of claim 1 , wherein the over-provisioning bias of the second storage portion is higher than the over-provisioning bias of the first storage portion.

11. The method of claim 1 , further comprising:

determining that the performance metric as applied to each of a plurality of additional data shards exceeds the threshold; and

separating the plurality of additional data shards within a storage system.

12. The method of claim 11 , wherein separating the plurality of additional data shards within the storage system includes assigning the plurality of additional data shards to different storage portions such that the different storage portions are accessed at a substantially similar frequency.

13. The method of claim 11 , wherein separating the plurality of additional data shards within the storage system includes mixing the plurality of additional data shards with another plurality of data shards for which the performance metric does not exceed the threshold for each member of that plurality of data shards.

14. The method of claim 1 , wherein the data shard includes data flushed from a volatile memory source.

15. The method of claim 1 , wherein the second storage portion includes one or more other data shards for which the performance metric exceeds the threshold that form a stream with the data shard.

16. The method of claim 1 , wherein reassigning the data shard to the second storage portion includes copying the plurality of files comprising the data shard to the second storage portion and deleting the copied plurality of files comprising the data shard from the first storage portion.

17. The method of claim 1 , wherein at least one file in the plurality of files comprising the data shard is combined with another file to form a new file in the second storage portion.

18. The method of claim 17 , wherein the another file did not reside in the first storage portion.

19. A system comprising:

a processor configured to:

monitor a performance metric of a data shard including a plurality of files stored in a first storage portion;

determine that the performance metric of the data shard including the plurality of files exceeds a threshold;

in response to at least the determination that the performance metric exceeds the threshold, increase the over-provisioning bias of a first storage portion storing a plurality of data shards each storing a plurality of files; and

in response to a determination that a cumulative value the over-provisioning bias associated with an amount of buffer space allocated to the first storage portion meets a cumulative over-provisioning bias limit, rebalance the plurality of data shards of the first storage portion including by reassigning the data shard to a second storage portion selected based on an over-provisioning bias of the second storage portion that is different than the over-provisioning bias of the first storage portion; and

a memory coupled to the processor and configured to provide the processor with instructions.

20. A computer program product, the computer program product being embodied in a non-transitory computer readable storage medium and comprising computer instructions for:

monitoring a performance metric of a data shard including a plurality of files stored in a first storage portion;

determining that the performance metric of the data shard including the plurality of files exceeds a threshold; and

in response to at least the determination that the performance metric exceeds the threshold, increasing the over-provisioning bias of a first storage portion storing a plurality of data shards each storing a plurality of files; and

in response to a determination that a cumulative value the over-provisioning bias associated with an amount of buffer space allocated to the first storage portion meets a cumulative over-provisioning bias limit, rebalancing the plurality of data shards of the first storage portion including by reassigning the data shard to a second storage portion selected based on an over-provisioning bias of the second storage portion that is different than the over-provisioning bias of the first storage portion.

Assignments (2)
CHANGE OF NAME Recorded Nov 19, 2021
From: FACEBOOK, INC.
To: META PLATFORMS, INC.
Reel/Frame 058214/0351 →
ASSIGNMENT OF ASSIGNOR'S INTEREST Recorded May 2, 2019
From: KANKANI, NAVNEETH; GHOSH, MRINMOY
To: FACEBOOK, INC.
Reel/Frame 049066/0833 →
Cited By (3)
US 12,210,765 US 12,524,309 US 12,579,007