×

Distributed system and method for replicated storage of structured data records

  • US 8,996,482 B1
  • Filed: 02/10/2006
  • Issued: 03/31/2015
  • Est. Priority Date: 02/10/2006
  • Status: Active Grant
First Claim
Patent Images

1. A system, comprising:

  • one or more computing devices configured to implement a network-based data storage service configured to store data tables for a plurality of distinct clients, wherein the network-based data storage service comprises;

    a plurality of storage hosts each configured to store and retrieve structured data records; and

    a data store manager configured to, for each of the plurality of distinct clients;

    receive a request from the distinct client to store a structured data record within a table;

    in response to receiving said request;

    map said structured data record to a block, wherein to map said structured data record to a block, the data store manager is configured to;

    apply a hash function to a value of a partition key field of said structured data record to compute a hash value for said structured data record,based on the hash value and an identifier of the table, identify a block to which said structured data record is to be mapped, such that a block identifier corresponding to said block is determined,map said structured data record to said block, andmap said block to a subset of storage hosts, wherein to map said block to a subset of storage hosts, the data store manager is configured to;

    compute a set of hash values including a respective hash value for each of the plurality of storage hosts, wherein each respective hash value of the set of hash values is distinct from the hash value for said structured data record and is based on the hash value for said structured data record and a respective storage host identifier, wherein each respective hash value of the set of hash values is a result of applying a hash function to a concatenation of said block identifier and an identifier of a respective one of a plurality of data centers,apply a selection criterion to the set of hash values to select a subset of storage hosts of the plurality of storage hosts, wherein said subset of storage hosts comprises at least two of said plurality of storage hosts, andmap said block directly to each of the subset of storage hosts of said plurality of storage hosts, wherein to map said block to said subset of storage hosts, said data store manager is further configured to map said block to two or more of said plurality of data centers, wherein members of said subset of storage hosts are distributed among said two or more data centers; and

    upon successful storage of said structured data record to said block within said subset of storage hosts, return to said distinct client an indication that said request is complete.

View all claims
  • 1 Assignment
Timeline View
Assignment View
    ×
    ×