IP Library Granted Patent US 11,422,721
Granted Patent B2
US 11,422,721 · App. 16/839,605 · Granted Aug 23, 2022

Data storage scheme switching in a distributed data storage system

Inventors: Michael Loh (El Cerrito, CA); Daniel R. Horn (Mountain View, CA); Andraz Kavalar (San Francisco, CA); David Lichtenberg (San Francisco, CA); Austin Sung (San Francisco, CA); Shi Feng (Millbrae, CA); Jongmin Baek (Foster City, CA)
Assignee: DROPBOX, INC.
G06F3/0634G06F3/067G06F3/0611G06F3/0653G06N7/005G06N20/00H03M13/154
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 11,422,721
App. No.
16/839,605
Granted
Aug 23, 2022
Kind
B2
Abstract

Systems and methods for dynamic and automatic data storage scheme switching in a distributed data storage system. A machine learning-based policy for computing probable future content item access patterns based on historical content item access patterns is employed to dynamically and automatically switch the storage of content items (e.g., files, digital data, photos, text, audio, video, streaming content, cloud documents, etc.) between different data storage schemes. The different data storage schemes may have different data storage cost and different data access cost characteristics. For example, the different data storage schemes may encompass different types of data storage devices, different data compression schemes, and/or different data redundancy schemes.

Claims (71)

1. A computing system comprising:

one or more processors;

a non-transitory computer-readable storage medium comprising instructions which, when executed by the one or more processors, cause the computing system to:

store, at an initial time, a content item according to a first data storage scheme;

use, at a first time, a first trained machine learning model to compute, based on a first set of one or more historical accesses to the content item between the initial time and the first time, a first probability that the content item will be accessed in the future;

maintain, based on the first probability, storage of the content item according to the first data storage scheme;

use, at a second time after the first time, a second trained machine learning model different from the first trained machine learning model to compute, based on a second set of one or more historical accesses to the content item between, a second probability that the content item will be accessed in the future relative to a second reference time that is after the second set of one or more historical accesses have occurred, the second trained machine learning model trained to compute probabilities on the basis of a different time horizon from a time horizon on which the first trained machine learning model is trained;

switch, based on the second probability, the content item from being stored according to the first data storage scheme to being stored according to a second data storage scheme, wherein the first machine learning model is again used at a third time after the second time in connection with determining whether to switch the content item from being stored in the second data storage scheme to a different data storage scheme.

2. The computing system of claim 1 , wherein the second data storage scheme is a colder storage relative to the first data storage scheme.

3. The computing system of claim 1 , wherein the initial time corresponds to when a content management system takes a content management action on the content item.

4. The computer system of claim 1 , further comprising instructions which, when executed by one or more of the one or more processors, cause the computing system to:

collect a set of one or more access predictors for the content item;

generate a set of one or more feature values for the content item based on the set of one or more access predictors; and

use, at the first time, the first trained machine learning model to compute, based on the set of one or more feature values, the first probability.

5. The computing system of claim 4 , wherein the set of one or more access predictors for the content item include at least one or more of:

a content type of the content item,

access timing information for the first set of one or more historical accesses,

a size of the content item,

a filename of the content item,

a file path of the content item,

a number of the first set of one or more historical accesses by a particular user, or

a type of end-user computing device using a historical access of the first set of one or more historical accesses.

6. A computer-implemented method comprising:

storing a first content item in a distributed data storage system according to a first data storage scheme;

using two or more trained machine learning models to compute, based on a first set of one or more historical accesses to the first content item in the distributed data storage system while the first content item is stored in the distributed data storage system according to the first data storage scheme, a first probability that the first content item will be accessed in the distributed data storage system during a first period of time and a second probability that the first content item will be accessed in the distributed data storage system during a second period of time, the two or more trained machine learning models trained using training data corresponding to different time horizons with respect to one another, the one or more historical accesses occurring prior to a reference time that precedes the first and second periods of time; and

based on one or more of the first probability and the second probability, storing the first content item in the distributed data storage system according to a second data storage scheme, wherein a first machine learning model of the two or more trained machine learning models trained using a shorter time horizon than one or more other time horizons of the different time horizons is again used in connection with determining whether to switch the content item from being stored in the second data storage scheme to a different data storage scheme.

7. The method of claim 6 , wherein:

the first data storage scheme has a first data storage cost, the first data storage cost associated with a storage of the first content item in the distributed data storage system according to the first data storage scheme;

the first data storage scheme has a first data access cost, the first data access cost associated with an access to the first content item in the distributed data storage system while the first content item is stored in the distributed data storage system according to the first data storage scheme;

the second data storage scheme has a second data storage cost, the second data storage cost associated with a storage of the first content item in the distributed data storage system according to the second data storage scheme;

the second data storage scheme has a second data access cost, the second data access cost associated with an access to the first content item in the distributed data storage system while the first content item is stored in the distributed data storage system according to the second data storage scheme;

the first data storage cost is different than the second data storage cost; and

the first data access cost is different than the second data access cost.

8. The method of claim 7 , wherein:

the first data storage cost is greater than the second data storage cost; and

the first data access cost is less than the second data access cost.

9. The method of claim 7 , wherein:

the first data storage cost is less than the second data storage cost; and

the first data access cost is greater than the second data access cost.

10. The method of claim 6 , further comprising:

using one or more machine learning models to compute, based on a second set one or more historical accesses to the first content item in the distributed data storage system while the first content item is stored in the distributed data storage system according to the second data storage scheme, a second probability that the first content item will be accessed in the distributed data storage system during a second period of time that is after the first period of time; and

based on the second probability, storing the first content item in the distributed data storage system according to the first data storage scheme.

11. The method of claim 6 , wherein:

the first content item stored in the distributed data storage system according to the first data storage scheme is a first compressed version of the first content item, the first compressed version of the first content item compressed according to a first data compression algorithm; and

the first content item stored in the distributed data storage system according to the second data storage scheme is a second compressed version of the first content item, the second compressed version of the first content item compressed according to a second data compression algorithm.

12. The method of claim 11 , wherein:

the first compressed version of the first content item stored in the distributed data storage system according to the first data storage scheme has a higher data storage cost than the second compression version of the first content item stored in the distributed data storage system according to the second data storage scheme; and

the first compressed version of the first content item stored in the distributed data storage system according to the first data storage scheme has a lower data access cost than the second compressed version of the first content item stored in the distributed data storage system according to the second data storage scheme.

13. The method of claim 6 , wherein:

wherein the first content item stored in the distributed data storage system according to the first data storage scheme is a first redundant version of the first content item made redundant according to a first data redundancy scheme; and

wherein the first content item stored in the distributed data storage system according to the second data storage scheme is a second redundant version of the first content item made redundant according to a second data redundancy scheme.

14. The method of claim 13 , wherein:

the first redundant version of the first content item comprises a plurality of copies of the first content item stored in the distributed data storage system according to the first data redundancy scheme; and

the second redundant version of the first content item comprises an erasure-coding of the first content item stored in the distributed data storage system according to the second data redundancy scheme.

15. The method of claim 13 , wherein the second redundant version of the first content item stored in the distributed data storage system according to the second data redundancy scheme consumes less data storage space of the distributed data storage system than the first redundant version of the first content item stored in the distributed data storage system according to the first data redundancy scheme.

16. The method of claim 13 , wherein:

the first redundant version of the first content item stored according to the first data redundancy scheme comprises a content item block of which the first content item is stored in at least two different geographic regions of the distributed data storage system; and

the second redundant version of the first content item stored the distributed data storage system according to the second data redundancy scheme comprises a first fragment of the content item block stored in a first geographic region of the distributed data storage system, a second fragment of the content item block stored in a second geographic region of the distributed data storage system, and a parity fragment stored in a third geographic region of the distributed data storage system.

17. The method of claim 6 , wherein:

the first content item stored in the distributed data storage system according to the first data storage scheme is stored on one or more data storage devices of a first type of data storage device; and

the first content item stored in the distributed data storage system according to the second data storage scheme is stored on one or more data storage devices of a second type of data storage device.

18. The method of claim 6 , wherein:

the first probability is a probability that the first content item stored in the distributed data storage system according to the first data storage scheme will be accessed during the first period of time only during off-peak time periods; and

the second data storage scheme is a colder storage relative to the first data storage scheme.

19. The method of claim 6 , further comprising:

before using one or more trained machine learning models to compute the first probability, using one or more trained machine learning models to compute, based on a second set of one or more historical accesses to the first content item in the distributed data storage system when stored according to the first data storage scheme, a second probability that the first content item stored according to the first data storage scheme will be accessed during a second period of time that is prior to the first period of time; and

based on the second probability, maintaining storage of the first content item according to the first data storage scheme.

20. A non-transitory computer-readable media comprising instructions which, when executed by a computing system, causes the computing system to perform:

storing a plurality of content items in a distributed data storage system according to a first data storage scheme;

using two or more trained machine learning models to compute, for each content item of the plurality of content items, based on a respective set of one or more historical accesses to the content item in the distributed data storage system when stored according to the first data storage scheme, a respective probability that the content item stored according to the first data storage scheme will be accessed subsequent to a reference time, the one or more historical accesses occurring prior to the reference time, the two or more trained machine learning models trained using training data corresponding to different time horizons with respect to one another; and

based on the respective probability computed for each content item of the plurality of content items, maintaining storage of the respective content item according to the first data storage scheme or switching the respective content item to a second data storage scheme, wherein a first machine learning model of the two or more trained machine learning models trained using a shorter time horizon than one or more other time horizons of the different time horizons is again used in connection with determining whether to switch the content item from being stored in the first data storage scheme to a different data storage scheme.

Assignments (5)
RELEASE OF SECURITY INTEREST Recorded Dec 13, 2024
From: JPMORGAN CHASE BANK, N.A., AS COLLATERAL AGENT
To: DROPBOX, INC.
Reel/Frame 069635/0332 →
SECURITY INTEREST Recorded Dec 12, 2024
From: DROPBOX, INC.
To: WILMINGTON TRUST, NATIONAL ASSOCIATION, AS COLLATERAL AGENT
Reel/Frame 069604/0611 →
PATENT SECURITY AGREEMENT Recorded Mar 10, 2021
From: DROPBOX, INC.
To: JPMORGAN CHASE BANK, N.A., AS COLLATERAL AGENT
Reel/Frame 055670/0219 →
ASSIGNMENT OF ASSIGNOR'S INTEREST Recorded Apr 20, 2020
From: LOH, MICHAEL; HORN, DANIEL R.; KAVALAR, ANDRAZ; LICHTENBERG, DAVID; SUNG, AUSTIN; FENG, SHI; BAEK, JONGMIN
To: DROPBOX, INC.
Reel/Frame 052446/0267 →
ASSIGNMENT OF ASSIGNOR'S INTEREST Recorded Apr 3, 2020
From: LOH, MICHAEL; HORN, DANIEL R.; KAVALAR, ANDRAZ; LICHTENBERG, DAVID; SUNG, AUSTIN; BAEK, JONGMIN
To: DROPBOX, INC.
Reel/Frame 052306/0982 →