Providing a distributed and replicated data store in a heterogeneous cluster

A computer program product, the computer program product being embodied in a tangible non-transitory computer readable storage medium and comprising computer instructions for:

• providing a distributed and replicated data store associated with a storage system using a circular order for a portion of a plurality of logical storage segments that at least includes a first logical storage segment of a first storage node and a second logical storage segment of a second storage node, wherein the first logical storage segment of the first storage node and the second logical storage segment of the second storage node are adjacent to each other in the circular order, wherein a fault tolerance policy indicates a threshold number of adjacent logical storage segments of the plurality of logical storage segments needed to store a copy of a bucket, wherein the fault tolerance policy is at least in part satisfied by having the first logical storage segment of the first storage node store a first copy of a first bucket and the second logical storage segment of the second storage node store a second copy of the first bucket;
• adding a new storage node to the storage system;
• determining a number count of logical storage segments associated with the new storage node;
• adjusting the circular order associated with the storage system based on the determined number count of logical storage segments associated with the new storage node, wherein in the adjusted circular order associated with the storage system, a logical storage segment of the new storage node is located in between the first logical storage segment of the first storage node and the second logical storage segment of the second storage node;
• and
• rebalancing the distributed and replicated data store based on the adjusted circular order including by migrating the first copy of the first bucket from the first logical storage segment of the first storage node or the second copy of the first bucket from the second logical storage segment of the second storage node to the logical storage segment associated with the new storage node to satisfy the fault tolerance policy.

A system, comprising:

• a processor;
• and
• a memory coupled with the processor, wherein the memory is configured to provide the processor with instructions which when executed cause the processor to:
• provide a distributed and replicated data store associated with a storage system using a circular order for a portion of a plurality of logical storage segments that at least includes a first logical storage segment of a first storage node and a second logical storage segment of a second storage node, wherein the first logical storage segment of the first storage node and the second logical storage segment of the second storage node are adjacent to each other in the circular order, wherein a fault tolerance policy indicates a threshold number of adjacent logical storage segments of the plurality of logical storage segments needed to store a copy of a bucket, wherein the fault tolerance policy is at least in part satisfied by having the first logical storage segment of the first storage node store a first copy of a first bucket and the second logical storage segment of the second storage node store a second copy of the first bucket;
• add a new storage node to the storage system;
• determine a number count of logical storage segments associated with the new storage node;
• adjust the circular order associated with the storage system based on the determined number count of logical storage segments associated with the new storage node, wherein in the adjusted circular order associated with the storage system, a logical storage segment of the new storage node is located in between the first logical storage segment of the first storage node and the second logical storage segment of the second storage node;
• and
• rebalance the distributed and replicated data store based on the adjusted circular order including by migrating the first copy of the first bucket from the first logical storage segment of the first storage node or the second copy of the first bucket from the second logical storage segment of the second storage node to the logical storage segment associated with the new storage node to satisfy the fault tolerance policy.