Hybrid object placement in a distributed storage system

• US 20070027916A1
• Filed: 07/29/2005
• Published: 02/01/2007
• Est. Priority Date: 07/29/2005
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Zhang, Zheng, Lin, Shiding, Chen, Yu, Chen, Wei, Lian, Qiao, Teodosiu, Dan, Jin, Chao
• Granted Patent: US 7,536,426 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 11/1662 the resynchronized component or unit being a persistent storage device re-synchronization of failed mirror storage G06F11/2082; rebuild or reconstruction of parity RAID storage G06F11/1008

Abstract

Described is the differentiation of replicas in a large distributed object store as either being smoothing replicas based on an amount of load on storage nodes (bricks), or as spreading replicas based on a substantially random distribution among the system'"'"'s bricks. The smoothing replicas are placed among the lowest usage bricks, while the spreading replicas are placed randomly throughout other bricks in the system independent of load. As a result, fast, primarily parallel data repair is facilitated by selecting a spreading replica when repair is needed, while load balancing is facilitated by placing a smoothing replica on a low-usage brick when a new replica is checked in, and selecting a smoothing replica when load balancing is triggered by overloading of a brick and/or addition of a new brick. Check-in, data repair and load balancing policies specify how to use smoothing replicas and spreading replicas.

Claims

1. At least one computer-readable medium having computer-executable instructions, which when executed perform steps, comprising:

placing a first replica in a distributed object store as a smoothing replica based on an amount of load of a set of bricks; and

placing a second replica that has contents identical to the first replica in the distributed object store as a spreading replica based on a substantially random distribution among another set of bricks.

2. The computer-readable medium of claim 1 wherein placing the first replica as the smoothing replica comprises randomly selecting a selected brick from among a set of lowest usage bricks, and placing the smoothing replica on the selected brick.

3. The computer-readable medium of claim 1 wherein placing the first and second replicas is based on a check-in policy.

4. The computer-readable medium of claim 3 wherein the check-in policy places at least two replicas as spreading replicas and at least one other replica as a smoothing replica.

5. The computer-readable medium of claim 1 having further computer-executable instructions comprising copying a replica from one brick to another brick based on a data repair policy.

6. The computer-readable medium of claim 5 wherein the data repair policy specifies selecting a spreading replica for copying if at least one spreading replica is available.

7. The computer-readable medium of claim 1 having further computer-executable instructions comprising moving a replica from one brick to another brick based on a load balancing policy.

8. The computer-readable medium of claim 7 wherein the load balancing policy is triggered by at least one of adding at least one new brick to a system of bricks, or deleting objects and causing a load imbalance among the bricks.

9. The computer-readable medium of claim 7 wherein the load balancing policy specifies selecting a smoothing replica for moving if at least one smoothing replica is available.

10. The computer-readable medium of claim 1 having further computer-executable instructions comprising maintaining at least one index having information therein that indicates that the first replica comprises a smoothing replica and the second replica comprises a spreading replica.

11. At least one computer-readable medium having computer-executable instructions, which when executed perform steps, comprising:

determining that a replica needs to be stored on at least one brick in a distributed system of bricks; and

evaluating policy to establish whether to store the replica as a smoothing replica based on load, as a spreading replica based on distribution, or store at least one smoothing replica and at least one spreading replica.

12. The computer readable medium of claim 11 wherein determining that the replica needs to be stored on at least one brick is based on a newly checked-in object, wherein evaluating the policy comprises evaluating a check-in policy, and wherein the check-in policy establishes that at least one copy of the replica is to be stored as a spreading replica and at least one copy of the replica is to be stored as a smoothing replica.

13. The computer-readable medium of claim 11 wherein determining that the replica needs to be stored on at least one brick is based on at least one of failure of another brick or a load imbalance among the bricks, wherein evaluating the policy comprises evaluating a repair policy, and wherein the repair policy establishes that a spreading replica is to be selected for copying.

14. The computer-readable medium of claim 11 wherein determining that the replica needs to be stored on at least one brick is based on load balancing, wherein evaluating the policy comprises evaluating a load balancing policy, and wherein the load balancing policy establishes that a smoothing replica is to be selected for moving from one brick to another brick.

15. In a computing environment in which objects are replicated among bricks of a distributed object store, a method comprising:

storing a copy of an object as a first replica on one brick;

storing another copy of an object as a second replica on another brick; and

maintaining information that indicates that the first replica is a smoothing replica and the second replica is a spreading replica.

16. The method of claim 15 further comprising, copying the spreading replica to a different brick based on a need for an additional copy of the replica in the distributed object store.

17. The method of claim 16 wherein the need for then additional copy of the replica in the distributed object store is based on at least one of failure of part of at least one brick or a load imbalance among the bricks.

18. The method of claim 15 further comprising, moving the spreading from the other brick to a different brick based on relative loading among bricks.

19. The method of claim 15 wherein maintaining the information comprises maintaining at least one index that correlates replicas to bricks, wherein the at least one index includes data that indicates that the first replica is a smoothing replica and the second replica is a spreading replica.

20. The method of claim 15 wherein storing a copy of an object as a first replica on one brick and storing another copy of an object as a second replica on another brick comprises evaluating a check-in policy.