PLACEMENT POLICY

• US 20140188825A1
• Filed: 12/31/2012
• Published: 07/03/2014
• Est. Priority Date: 12/31/2012
• Status: Active Grant

• Current Assignee: Meta Platforms, Inc. (f/k/a Facebook, Inc.)
• Original Assignee: Meta Platforms, Inc. (f/k/a Facebook, Inc.)
• Inventors: Muthukkaruppan, Kannan, Ranganathan, Karthik, Tang, Liyin
• Granted Patent: US 9,268,808 B2
• Time in Patent Office: Days
• US Class Current: 707/694
• CPC Class Codes: G06F 16/134 Distributed indices
• CPC Class Codes: G06F 16/1752 based on file chunks
• CPC Class Codes: G06F 16/178 Techniques for file synchronisation in file systems
• CPC Class Codes: G06F 16/183 Provision of network file services by network file servers, e.g. by using NFS, CIFS network file access protocols H04L67/1097
• CPC Class Codes: G06F 16/185 Hierarchical storage management [HSM] systems, e.g. file migration or policies thereof details of archiving G06F16/11
• CPC Class Codes: G06F 16/22 Indexing; Data structures therefor; Storage structures
• CPC Class Codes: G06F 16/2282 Tablespace storage structures; Management thereof

Abstract

A region-based placement policy that can be used to achieve a better distribution of data in a clustered storage system is disclosed herein. The clustered storage system includes a master module to implement the region-based placement policy for storing one or more copies of a received data across many data nodes of the clustered storage system. When implementing the region-based placement policy, the master module splits the received data into one or more regions, where each region includes a contiguous portion of the received data. Further, for each of the plurality of regions, the master module stores complete copies of the region in a subset of the data nodes.

Claims

1. A clustered storage system comprising:

a plurality of data nodes for receiving and storing data associated with the clustered storage system, the data received from one or more client systems serviced by the clustered storage system; and

a master module in communication with one or more of the plurality of data nodes and for facilitating storage of data in the plurality of data nodes, the master module configured to;

receive client data from a client system of the one or more client systems;

split the client data into a plurality of regions, each region including a contiguous portion of the client data;

for each of the plurality of regions, store a complete replica of the region in a single storage node of the plurality of storage nodes.

2. The clustered storage system of claim 1, wherein the placement of the plurality of replicas associated with each region is directed according to a placement policy maintained in association with the master module.

3. The clustered storage system of claim 1, wherein the received client data is a data table, the data table comprising a plurality of rows and columns.

4. The clustered storage system of claim 3, wherein one or more rows of the data table constitutes a different region of the data table.

5. The clustered storage system of claim 4, wherein the data associated with a region is divided into one or more data files, wherein each of the one or more data files is associated with a column of data of the data table.

6. The clustered storage system of claim 5, wherein storing a replica associated with the region includes:

processing, by the master module, a plurality of write requests, each write request corresponding to one or more of the data files associated with the region.

7. The clustered storage system of claim 5, wherein the data associated with a data file is stored as one or more data blocks in an associated data node.

8. The clustered storage system of claim 1, wherein the plurality of data nodes constitute at least a portion of a Hadoop clustered storage system.

9. The clustered storage system of claim 1, wherein the master module constitutes at least a portion of a HBase database layer.

10. A computer-implemented method for storing data in a clustered storage system, the clustered storage system including a plurality of storage nodes operable to store the data associated with the clustered storage system, the method comprising:

receiving, by a master module associated with the clustered storage system, client data to be stored in the clustered storage system, the client data received from one or more client systems serviced by the clustered storage system;

splitting, by the master module, the client data into a plurality of regions, each region including a contiguous portion of the client data;

for each of the plurality of regions, storing a replica of the region, in its entirety, in multiple storage nodes of the plurality of storage nodes.

11. The method of claim 10, wherein the client data is in the form of a data table, the data table comprising a plurality of rows and columns.

12. The method of claim 11, wherein one or more rows of the data table constitutes a region of the plurality of regions.

13. The method of claim 12, wherein the each replica of a region includes one or more data files, wherein each of the one or more data files constitutes a column of data from the plurality of columns of the data table.

14. The method of claim 13, wherein the storing of each replica includes processing a plurality of sub-write requests, each sub-write request associated with storage corresponding to the one or more of the data files.

15. The method of claim 12, wherein the data associated with a data file is stored as one or more data blocks in a storage node.

16. A computer-implemented method for storing data in a clustered storage system, the method comprising:

receiving, by a storage server associated with the clustered storage system, data to be stored in the clustered storage system, the clustered storage system including a plurality of storage nodes for storing the data;

splitting, by the storage server, the data into one or more regions, each region constituting a contiguous portion of the received data;

assigning, by the storage server, each region to one of a plurality of region servers, wherein each region server manages data access on behalf of the region;

for each region of the one or more regions, determining, by the storage server, multiple storage nodes of the plurality of storage nodes to store the region in, wherein a complete replica of the region is stored in each of the multiple storage nodes; and

for each region of the one or more regions, requesting, by the storage server, a region server corresponding to the region to execute a write request, execution of the write request by the region server causing each replica of the region to be stored in corresponding nodes of the multiple storage nodes.

17. The method of claim 16, further comprising:

receiving, by the storage server, a status report indicating the success of storing the one or more regions in their corresponding storage nodes.

18. The method of claim 17, wherein the stored data is a data table, the data table comprising a plurality of rows and columns.

19. The method of claim 18, wherein one or more rows of the data table constitutes a different region of the data table for the purpose of generating replicas.

20. The method of claim 19, wherein the data associated with a region includes one or more data files, wherein each of the one or more data files is associated with a column of data of the data table.

21. The method of claim 20, wherein storing a replica associated with the region includes:

processing, by the master module, a plurality of write requests, each write request corresponding to one or more of the data files associated with the region.

22. The method of claim 21, wherein the data associated with a data file is stored as one or more data blocks in a storage node.

23. The method of claim 16, wherein the plurality of storage nodes constitutes at least a portion of a Hadoop clustered storage.

24. The method of claim 16, wherein the storage server constitutes at least a portion of a HBase database layer.

25. The method of claim 16, wherein the clustered storage system is a HBase-Hadoop storage system.

26. The clustered storage system of claim 16, wherein multiple storage nodes constitutes a subset of the plurality of storage nodes.

27. A storage server system comprising:

a processor;

a network interface through which to communicate, over a network, with a plurality of storage nodes associated with a clustered storage system;

a memory storing code which, when executed by the processor, causes the storage server system to perform a plurality of operations, including;

receiving client data to be stored in the clustered storage system, the client data received from one or more client systems serviced by the clustered storage system;

splitting the client data into a plurality of regions, each region including a contiguous portion of the client data;

splitting, by the master module, the client data into a plurality of regions, each region including a contiguous portion of the client data;

for each of the plurality of regions, storing a complete replica of the region in a single storage node of the plurality of storage nodes.