Storing data across a plurality of storage nodes

• US 9,250,830 B2
• Filed: 06/02/2014
• Issued: 02/02/2016
• Est. Priority Date: 01/20/2011
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Kadatch, Andrew, Greenfield, Lawrence E.
• Primary Examiner(s): KROFCHECK, MICHAEL C
• Application Number:
  US14/293,330
• Publication Number:
  US 20140281233A1
• Time in Patent Office: 610 Days
• US Class Current: 1/1
• CPC Class Codes: G06F 11/1044 with specific ECC/EDC distribution
• CPC Class Codes: G06F 11/1076 Parity data used in redundant arrays of independent storages, e.g. in RAID systems
• CPC Class Codes: G06F 2211/1009 Cache, i.e. caches used in RAID system with parity
• CPC Class Codes: G06F 2211/1028 Distributed, i.e. distributed RAID systems with parity
• CPC Class Codes: G06F 3/0613 in relation to throughput
• CPC Class Codes: G06F 3/0619 in relation to data integrity, e.g. data losses, bit errors
• CPC Class Codes: G06F 3/0643 Management of files
• CPC Class Codes: G06F 3/0656 Data buffering arrangements
• CPC Class Codes: G06F 3/0665 at area level, e.g. provisioning of virtual or logical volumes
• CPC Class Codes: G06F 3/067 Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS]
• CPC Class Codes: G06F 3/0685 Hybrid storage combining heterogeneous device types, e.g. hierarchical storage, hybrid arrays

Abstract

Methods, systems, and apparatus, including computer programs encoded on a computer storage medium, for storing data on storage nodes. In one aspect, a method includes receiving a file to be stored across a plurality of storage nodes each including a cache. The is stored by storing portions of the file each on a different storage node. A first portion is written to a first storage node'"'"'s cache until determining that the first storage node'"'"'s cache is full. A different second storage node is selected in response to determining that the first storage node'"'"'s cache is full. For each portion of the file, a location of the portion is recorded, the location indicating at least a storage node storing the portion.

Claims

1. A method performed by data processing apparatus, the method comprising:

receiving a file to be stored across a plurality of storage nodes each including a cache;

storing the file by storing a plurality of portions of the file each on a different storage node, including writing a first portion to a first storage node'"'"'s cache;

copying the first portion from the first storage node'"'"'s cache to slower storage of the first storage node, the slower storage of the first storage node being slower than the first storage node'"'"'s cache;

recording, within a log, data specifying the slower storage of the first storage node, the log also specifying a plurality of additional corresponding slower storages of a plurality of storage nodes;

determining that the first storage node'"'"'s cache is full and in response, selecting a different second storage node, wherein selecting the second storage node comprises;

examining the log, and

selecting the second storage node as the storage node having a corresponding write time in the log that is the furthest in the past of the write times in the log.

2. The method of claim 1, wherein determining that the first storage node'"'"'s cache is full comprises determining that a data storage rate for writing the first portion has dropped.

3. The method of claim 1, wherein determining that the first storage node'"'"'s cache is full comprises comparing an amount of the first portion to a known size of the first storage node'"'"'s cache and determining that the amount is equal to or exceeds the known size.

4. The method of claim 1, further comprising selecting a third storage node in response to determining that the second storage node'"'"'s cache is full, and assigning a weight to each of the plurality of storage nodes, and wherein selecting the third storage node includes using the weights.

5. The method of claim 4, wherein each storage node'"'"'s weight is based on a performance characteristic of the storage node.

6. The method of claim 1, further comprising selecting a third storage node in response to determining that the second storage node'"'"'s cache is full, and wherein selecting the third storage node is based on one or more of:

a performance characteristic of the third storage node, usage history of the third storage node, and a past performance record for the third storage node.

7. The method of claim 1, further comprising selecting a third storage node in response to determining that the second storage node'"'"'s cache is full, and wherein selecting the third storage node is based on an amount of data stored by the third storage node relative to a capacity of the third storage node.

8. The method of claim 1, wherein storing the file comprises writing a second portion to the second storage node.

9. The method of claim 8, wherein writing the second portion to the second storage node comprises writing the second portion to the second storage node'"'"'s cache until determining that second storage node'"'"'s cache is full.

10. The method of claim 1, wherein storing the file comprises continuing to write portions of the file to various storage nodes until the file is completely stored in the plurality of storage nodes.

11. The method of claim 1, further comprising:

receiving a request for the file;

reading the first portion from the first storage node; and

reading the second portion from the second storage node.

12. A system comprising one or more data processing apparatus configured to perform operations comprising:

receiving a file to be stored across a plurality of storage nodes each including a cache;

storing the file by storing a plurality of portions of the file each on a different storage node, including writing a first portion to a first storage node'"'"'s cache;

copying the first portion from the first storage node'"'"'s cache to slower storage of the first storage node, the slower storage of the first storage node being slower than the first storage node'"'"'s cache;

recording, within a log, data specifying the slower storage of the first storage node, the log also specifying a plurality of additional corresponding slower storages of a plurality of storage nodes;

determining that the first storage node'"'"'s cache is full and in response, selecting a different second storage node, wherein selecting the second storage node comprises;

examining the log; and

selecting the second storage node as the storage node having a corresponding write time in the log that is the furthest in the past of the write times in the log.

13. The system of claim 12, wherein determining that the first storage node'"'"'s cache is full comprises determining that a data storage rate for writing the first portion has dropped.

14. The system of claim 12, wherein determining that the first storage node'"'"'s cache is full comprises comparing an amount of the first portion to a known size of the first storage node'"'"'s cache and determining that the amount is equal to or exceeds the known size.

15. The system of claim 12, wherein storing the file comprises writing a second portion to the second storage node.

16. The system of claim 15, wherein writing the second portion to the second storage node comprises writing the second portion to the second storage node'"'"'s cache until determining that second storage node'"'"'s cache is full.

17. The system of claim 12, wherein storing the file comprises continuing to write portions of the file to various storage nodes until the file is completely stored in the plurality of storage nodes.

18. The system of claim 12, the operations further comprising:

receiving a request for the file;

reading the first portion from the first storage node; and

reading the second portion from the second storage node.