Pseudorandom data storage

• US 20040003173A1
• Filed: 01/24/2003
• Published: 01/01/2004
• Est. Priority Date: 01/25/2002
• Status: Active Grant

• Current Assignee: University of Southern California
• Original Assignee: University of Southern California
• Inventors: Shahabi, Cyrus, Zimmermann, Roger, Yao, Shu-Yuen Didi
• Granted Patent: US 7,096,328 B2
• Time in Patent Office: Days
• US Class Current: 711/114
• CPC Class Codes: G06F 3/061 Improving I/O performance
• CPC Class Codes: G06F 3/064 Management of blocks
• CPC Class Codes: G06F 3/067 Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS]

Abstract

Systems and techniques to pseudorandomly place and redistribute data blocks in a storage system. In general, in one implementation, the techniques include: distributing data blocks over multiple storage devices according to a reproducible pseudorandom sequence that provides load balancing across the storage devices, and determining current storage locations of the data blocks by reproducing the pseudorandom sequence. The techniques may also include: distributing data blocks over multiple storage devices according to a reproducible pseudorandom sequence, in response to initiation of a storage scaling operation, pseudorandomly redistributing a selected subset of the data blocks and saving information describing the storage scaling operation, determining current storage locations based on the pseudorandom sequence and the saved scaling operation information, and accessing the data blocks according to the determined current storage locations.

Claims

1. A method comprising:

distributing data blocks over multiple storage devices according to a reproducible pseudorandom sequence that provides load balancing across the storage devices; and

determining current storage locations of the data blocks by reproducing the pseudorandom sequence.

2. The method of claim 1, further comprising, in response to initiation of a storage scaling operation, redistributing a selected subset of the data blocks and saving information describing the storage scaling operation, wherein said determining current storage locations comprises computing the current storage locations of the data blocks based on the reproduced pseudorandom sequence and the saved scaling operation information.

3. The method of claim 2, further comprising accessing the data blocks according to the determined current storage locations.

4. The method of claim 2, wherein the storage scaling operation comprises addition of one or more storage devices, and redistributing the selected subset of the data blocks comprises:

determining new storage locations for the data blocks based on the addition of the one or more storage devices; and

moving the selected subset of the data blocks that have determined new storage locations on the one or more added storage devices.

5. The method of claim 2, wherein the storage scaling operation comprises removal of one or more storage devices, and said redistributing the selected subset of the data blocks comprises:

determining new storage locations for the selected subset of the data blocks that reside on the one or more storage devices based on the removal of the one or more storage devices; and

moving the selected subset of the data blocks based on the determined new storage locations.

6. The method of claim 2, further comprising transmitting data comprising at least one of the data blocks being accessed according to the determined current storage locations, wherein said redistributing the selected subset of the data blocks comprises, during said transmitting:

copying the selected subset of the data blocks to newly determined storage locations on a new set of storage devices comprising at least one of the multiple storage devices;

switching to the new set of storage devices; and

deleting unused data blocks during idle times of said transmitting.

7. The method of claim 2, wherein said redistributing the selected subset of the data blocks comprises determining new storage locations based on the pseudorandom sequence used as input to a pseudorandom number generator.

8. The method of claim 7, wherein the pseudorandom number generator is used to generate the pseudorandom sequence.

9. The method of claim 8, further comprising generating the pseudorandom sequence by seeding the pseudorandom number generator with a number derived from an object name corresponding to the data blocks.

10. The method of claim 7, further comprising providing continuous media data to clients.

11. A machine-readable medium embodying information indicative of instructions for causing one or more machines to perform operations comprising:

distributing data blocks over multiple storage devices according to a reproducible pseudorandom sequence that provides load balancing across the storage devices; and

determining current storage locations of the data blocks by reproducing the pseudorandom sequence.

12. The machine-readable medium of claim 11, wherein the operations further comprise, in response to initiation of a storage scaling operation, redistributing a selected subset of the data blocks and saving information describing the storage scaling operation, and wherein said determining current storage locations comprises computing the current storage locations of the data blocks based on the reproduced pseudorandom sequence and the saved scaling operation information.

13. The machine-readable medium of claim 12, wherein the operations further comprise accessing the data blocks according to the determined current storage locations.

14. The machine-readable medium of claim 12, wherein the storage scaling operation comprises addition of one or more storage devices, and redistributing the selected subset of the data blocks comprises:

determining new storage locations for the data blocks based on the addition of the one or more storage devices; and

moving the selected subset of the data blocks that have determined new storage locations on the one or more added storage devices.

15. The machine-readable medium of claim 12, wherein the storage scaling operation comprises removal of one or more storage devices, and said redistributing the selected subset of the data blocks comprises:

determining new storage locations for the selected subset of the data blocks that reside on the one or more storage devices based on the removal of the one or more storage devices; and

moving the selected subset of the data blocks based on the determined new storage locations.

16. The machine-readable medium of claim 12, wherein the operations further comprise transmitting data comprising at least one of the data blocks being accessed according to the determined current storage locations, and wherein said redistributing the selected subset of the data blocks comprises, during said transmitting:

copying the selected subset of the data blocks to newly determined storage locations on a new set of storage devices comprising at least one of the multiple storage devices;

switching to the new set of storage devices; and

deleting unused data blocks during idle times of said transmitting.

17. The machine-readable medium of claim 12, wherein said redistributing the selected subset of the data blocks comprises determining new storage locations based on the pseudorandom sequence used as input to a pseudorandom number generator.

18. The machine-readable medium of claim 17, wherein the pseudorandom number generator is used to generate the pseudorandom sequence.

19. The machine-readable medium of claim 18, wherein the operations further comprise generating the pseudorandom sequence by seeding the pseudorandom number generator with a number derived from an object name corresponding to the data blocks.

20. The machine-readable medium of claim 17, wherein the operations further comprise providing continuous media data to clients.

21. A method comprising:

distributing data blocks over multiple storage devices according to a reproducible pseudorandom sequence;

in response to initiation of a storage scaling operation, pseudorandomly redistributing a selected subset of the data blocks and saving information describing the storage scaling operation;

determining current storage locations based on the pseudorandom sequence and the saved scaling operation information; and

accessing the data blocks according to the determined current storage locations.

22. The method of claim 21, wherein said pseudorandomly redistributing comprises:

seeding a pseudorandom number generator, used to generate the pseudorandom sequence, with one or more numbers from the pseudorandom sequence; and

determining one or more new storage locations based on output of the pseudorandom number generator.

23. The method of claim 21, wherein pseudorandomly redistributing comprises pseudorandomly redistributing the selected subset of the data blocks while transmitting data comprising at least one of the data blocks being accessed according to the determined current storage locations.

24. The method of claim 21, wherein the storage scaling operation comprises addition of one or more storage devices, and pseudorandomly redistributing the selected subset of the data blocks comprises:

determining new storage locations for the data blocks based on the addition of the one or more storage devices and based on output of a pseudorandom number generator seeded with one or more numbers from the pseudorandom sequence; and

moving the selected subset of the data blocks that have determined new storage locations on the one or more added storage devices.

25. The method of claim 21, wherein the storage scaling operation comprises removal of one or more storage devices, and pseudorandomly redistributing the selected subset of the data blocks comprises:

determining new storage locations for the selected subset of the data blocks that reside on the one or more storage devices based on the removal of the one or more storage devices and based on output of a pseudorandom number generator seeded with one or more numbers from the pseudorandom sequence; and

moving the selected subset of the data blocks based on the determined new storage locations.

26. The method of claim 21, further comprising generating the pseudorandom sequence by seeding a pseudorandom number generator with a number derived from an object name corresponding to the data blocks.

27. The method of claim 21, further comprising providing continuous media data to clients, said providing continuous media data comprising said accessing the data blocks.

28. A machine-readable medium embodying information indicative of instructions for causing one or more machines to perform operations comprising:

distributing data blocks over multiple storage devices according to a reproducible pseudorandom sequence;

in response to initiation of a storage scaling operation, pseudorandomly redistributing a selected subset of the data blocks and saving information describing the storage scaling operation;

determining current storage locations based on the pseudorandom sequence and the saved scaling operation information; and

accessing the data blocks according to the determined current storage locations.

29. The machine-readable medium of claim 28, wherein said pseudorandomly redistributing comprises:

seeding a pseudorandom number generator, used to generate the pseudorandom sequence, with one or more numbers from the pseudorandom sequence; and

determining one or more new storage locations based on output of the pseudorandom number generator.

30. The machine-readable medium of claim 28, wherein pseudorandomly redistributing comprises pseudorandomly redistributing the selected subset of the data blocks while transmitting data comprising at least one of the data blocks being accessed according to the determined current storage locations.

31. The machine-readable medium of claim 28, wherein the storage scaling operation comprises addition of one or more storage devices, and pseudorandomly redistributing the selected subset of the data blocks comprises:

determining new storage locations for the data blocks based on the addition of the one or more storage devices and based on output of a pseudorandom number generator seeded with one or more numbers from the pseudorandom sequence; and

moving the selected subset of the data blocks that have determined new storage locations on the one or more added storage devices.

32. The machine-readable medium of claim 28, wherein the storage scaling operation comprises removal of one or more storage devices, and pseudorandomly redistributing the selected subset of the data blocks comprises:

determining new storage locations for the selected subset of the data blocks that reside on the one or more storage devices based on the removal of the one or more storage devices and based on output of a pseudorandom number generator seeded with one or more numbers from the pseudorandom sequence; and

moving the selected subset of the data blocks based on the determined new storage locations.

33. The machine-readable medium of claim 28, wherein the operations further comprise generating the pseudorandom sequence by seeding a pseudorandom number generator with a number derived from an object name corresponding to the data blocks.

34. The machine-readable medium of claim 28, wherein the operations further comprise providing continuous media data to clients, said providing continuous media data comprising said accessing the data blocks.

35. A system comprising:

one or more storage devices; and

one or more controllers configured to pseudorandomly place data blocks on the one or more storage devices, to perform pseudorandom scaling of the one or more storage devices, and to access the data blocks based on information describing prior pseudorandom scaling.

36. The system of claim 35, further comprising a continuous media server comprising the one or more controllers.

37. The system of claim 36, wherein the one or more storage devices comprise two or more hard drives.

38. A system comprising:

means for randomized storing of data blocks without maintaining a directory system identifying locations of all the data blocks; and

means for randomized redistributing of the data blocks such that block movement is minimized.

39. The system of claim 38, further comprising means for transmitting data comprising the data blocks, wherein said means for transmitting and said means for randomized redistributing operate simultaneously.

40. The system of claim 39, wherein the means for randomized storing and the means for randomized redistributing use a single pseudorandom number generator.