×

Methods and systems for key sharding of objects stored in distributed storage system

  • US 9,767,130 B2
  • Filed: 08/08/2015
  • Issued: 09/19/2017
  • Est. Priority Date: 12/31/2014
  • Status: Active Grant
First Claim
Patent Images

1. A method of performing a delta edit of a named object stored in a distributed storage system, the method comprising:

  • storing, in the distributed storage system, a payload of the named object in key shards that are defined by key-shard chunk references, wherein the payload for the named object comprises a collection of key-value records, and wherein referenced chunks identified by the key shards each stores a subset of the collection of the key-value records, where the key-value records in the subset have key hashes that have a range of matching bits in common;

    receiving, by a gateway server, a request for a set of delta edits to be applied to the named object, wherein each delta edit specifies addition or deletion of at least one key-value record;

    determining, by the gateway server, relevant key shards to which the delta edits apply; and

    updating the relevant key shards, while not updating other key shards for the named object,wherein updating the relevant key shards comprises;

    obtaining a name hash identifying token for the named object;

    generating a plurality of key hash identifying tokens corresponding to the plurality of key-value records;

    determining negotiating groups for the relevant key shards using the name hash identifying token and the plurality of key hash identifying tokens;

    multicasting, by the gateway server, put requests to the negotiating groups for the relevant key shards, wherein the multicast put request specifies a cryptographic hash of a referenced chunk that is to be used as a base for a new chunk to be created;

    collecting, by the gateway server, responses from the negotiating groups;

    selecting rendezvous groups based on the responses from the negotiating groups;

    initiating rendezvous transfers to the rendezvous groups; and

    each addressed target server in a rendezvous group applying a delta edit to a copy of the referenced chunk to create a new chunk and calculating a content hash identifying token for the new chunk.

View all claims
  • 4 Assignments
Timeline View
Assignment View
    ×
    ×