Decoupled data stream and access structures

• US 7,930,559 B1
• Filed: 06/30/2006
• Issued: 04/19/2011
• Est. Priority Date: 06/30/2006
• Status: Active Grant

• Current Assignee: Emc IP Holding Company LLC (Dell Technologies Inc.)
• Original Assignee: EMC Corporation (Dell Technologies Inc.)
• Inventors: Yang, Bin, Pocas, Jamie, Beaverson, Arthur
• Primary Examiner(s): Truong; Thanhnga B
• Assistant Examiner(s): Mehrmanesh; Amir
• Application Number:
  US11/480,346
• Time in Patent Office: 1,754 Days
• Field of Search: None
• US Class Current: 713/193
• CPC Class Codes: G06F 11/1448 Management of the data involved in backup or backup restore
• CPC Class Codes: G06F 11/1453 using de-duplication of the data
• CPC Class Codes: G06F 11/1456 Hardware arrangements for backup
• CPC Class Codes: G06F 11/1458 Management of the backup or restore process
• CPC Class Codes: G06F 11/1461 Backup scheduling policy
• CPC Class Codes: G06F 16/2358 Change logging, detection, and notification replication G06F16/27

Abstract

Described are techniques for storing data. A plurality of data portions and a corresponding token for each of the data portions are received. Each of said plurality of data portions is to be stored by one of a plurality of processes and each token has a corresponding token value. Each of the data portions is stored at a storage location on a device allocated for use by one of said plurality of processes. An entry is written in a log file in accordance with said storing of the data portion. The log file is a private log file of one of the plurality processes. An access structure used to access stored data portions is updated. The access structure is indexed by token values of the stored data portions. The updating of the access structure is performed in accordance with log entries from private log files of the plurality of processes.

Claims

1. A method of storing data comprising:

receiving a plurality of data portions and a corresponding token for each of the data portions, wherein each of said plurality of data portions is stored by one of a plurality of processes, each token having a corresponding token value;

storing, by said plurality of processes, each of the data portions to storage locations on devices included in a storage pool of a plurality of devices, wherein each of the plurality of processes is allocated a portion of the plurality of storage devices of the storage pool for exclusive use by said each process;

writing an entry in a log file in accordance with said storing of each data portion by one of the plurality of processes, said log file being a private log file of said one of the plurality processes, wherein said private log file contains a plurality of entries recording write operations performed only by said one process, each entry in said private log file corresponding to one of the write operations and a different point in time at which said one process performs said one write operation and stores one of the data portions on one of the plurality of devices allocated for exclusive use by said one process;

updating an access structure used to access stored data portions in the storage pool, wherein the access structure is indexed by token values of the stored data portions, said updating being performed in accordance with log entries from private log files of the plurality of processes, said access structure including an entry corresponding to each unique data portion stored in the storage pool, the entry including a field identifying a location in the storage pool at which said each unique data portion is stored;

wherein the access structure is partitioned into “

M”

index structure portions, each of said M index structure portions being associated with a range of token values for data portions, and wherein each of said plurality of processes has “

M”

private log files, one corresponding to each index structure portion; and

wherein a first of said “

M”

private log files corresponding to a first of said M index structure portions contains a record of write operations performed only by said each process for writing data portions having token values included in the range of token values associated with said first index structure portion, each entry in one of said “

M”

private log files corresponding to a different point in time at which said each process stores one of the data portions on one of the plurality of devices allocated for exclusive use by said each process.

2. The method of claim 1, wherein said storage pool includes only a single copy of each unique data portion, and wherein each entry of the access structure associated with a unique data portion includes a reference count indicating a number of times the unique data portion associated therewith is referenced in one or more data segments stored in one or more data storage systems including said storage pool.

3. The method of claim 1, further comprising:

merging private log files of each of said plurality of processes associated with a same index structure portion producing “

M”

merged log files, and performing said updating using said merged log files.

4. The method of claim 3, wherein said merging includes merging log entries for data portions having a same token value and sorting said merged log files in accordance with a token value of each entry in the merged log files.

5. The method of claim 2, further comprising, for each data portion of said plurality of data portions:

determining if an entry exists in said access structure for said each data portion by searching for an entry in said access structure having a same token value as said each data portion.

6. The method of claim 5, wherein, for said each data portion, if there is an existing entry in said access structure having the same token value as said each data portion, updating a reference count of the existing entry and invalidating a copy of said each data portion as stored in said storing step.

7. The method of claim 5, wherein, for said each data portion, if there is no existing entry in said access structure having the same token value as said each data portion, allocating a new entry in said access structure, wherein said new entry is initialized to specify said storage location of said storing step in said field of the new entry identifying the location in the storage pool of said single copy.

8. The method of claim 2, further comprising:

reading from persistent storage into memory a current copy of said access structure;

updating said current copy of said access structure in accordance with said log entries producing an updated copy of said access structure; and

writing said updated copy of said access structure to persistent storage.

9. The method of claim 8, further comprising:

reading said current copy of said access structure;

storing memory addresses of valid nodes of said access structure into cache lines of a cache, each cache line including one of said memory addresses; and

generating a mapping table including an entry for each cache line at which one of said memory addresses is stored, said entry identifying a cache line including one of said memory addresses of a valid node and a corresponding index number of said valid node in said access structure.

10. The method of claim 9, wherein said mapping table is sorted by token values, each of said token values being associated with an entry of the mapping table.

11. The method of claim 10, wherein said writing traverses said mapping table in an order in accordance with sorted token values of entries in said mapping table.

12. A non-transitory computer readable medium comprising code stored thereon for storing data, the computer readable medium comprising code for:

receiving a plurality of data portions and a corresponding token for each of the data portions, wherein each of said plurality of data portions is stored by one of a plurality of processes, each token having a corresponding token value;

storing, by said plurality of processes, each of the data portions to storage locations on devices included in a storage pool of a plurality of devices, wherein each of the plurality of processes is allocated a portion of the plurality of storage devices of the storage pool for exclusive use by said each process;

writing an entry in a log file in accordance with said storing of each data portion by one of the plurality of processes, said log file being a private log file of said one of the plurality processes, wherein said private log file contains a plurality of entries recording write operations performed only by said one process, each entry in said private log file corresponding to one of the write operations and a different point in time at which said one process performs said one write operation and stores one of the data portions on one of the plurality of devices allocated for exclusive use by said one process;

updating an access structure used to access stored data portions in the storage pool, wherein the access structure is indexed by token values of the stored data portions, said updating being performed in accordance with log entries from private log files of the plurality of processes, said access structure including an entry corresponding to each unique data portion stored in the storage pool, the entry including a field identifying a location in the storage pool at which said each unique data portion is stored;

wherein the access structure is partitioned into “

M”

index structure portions, each of said M index structure portions being associated with a range of token values for data portions, and wherein each of said plurality of processes has “

M”

private log files, one corresponding to each index structure portion; and

wherein a first of said “

M”

private log files corresponding to a first of said M index structure portions contains a record of write operations performed only by said each process for writing data portions having token values included in the range of token values associated with said first index structure portion, each entry in one of said “

M”

private log files corresponding to a different point in time at which said each process stores one of the data portions on one of the plurality of devices allocated for exclusive use by said each process.

13. The non-transitory computer readable medium of claim 12, wherein said storage pool includes only a single copy of each unique data portion, and wherein each entry of the access structure associated with a unique data portion includes a reference count indicating a number of times the unique data portion associated therewith is referenced in one or more data segments stored in one or more data storage systems including said storage pool.

14. The non-transitory computer readable medium of claim 12, further comprising code stored thereon for:

merging private log files of each of said plurality of processes associated with a same index structure portion producing “

M”

merged log files, and performing said updating using said merged log files, wherein said merging includes merging log entries for data portions having a same token value and sorting said merged log files in accordance with a token value of each entry in the merged log files.

15. The non-transitory computer readable medium of claim 13, further comprising code stored thereon which, for each data portion of said plurality of data portions:

determines if an entry exists in said access structure for said each data portion by searching for an entry in said access structure having a same token value as said each data portion; and

wherein, for said each data portion, if there is an existing entry in said access structure having the same token value as said each data portion, updates a reference count of the existing entry and invalidates a copy of the data portion as stored in said storing step.