MAINTAINING I/O TRANSACTION METADATA IN LOG-WITH-INDEX STRUCTURE

Abstract

An information handling system maintains a log-with-index (LWI) structure that includes a log for inserting and deleting records, each of which includes a key, and a binary index for maintaining an index of log records. The log may be stored to disk for persistence. Insertions of new records into the log may occur sequentially to ensure adequate performance. The index tree may be maintained in memory for performance. When the log is full, log records may be written in key-sorted order to a new tablet in a tablet library. Two tablets may be merged from time to time. Merging may include iteratively performing a plurality of atomic merges for each of a plurality of atomic portions. During atomic merges, tablet index data may be modified in copy-on-write fashion to preserve existing data until the atomic merge completes.

Claims

1. An information handling system, comprising: a processor; and a memory, accessible to the processor, including processor-executable program instructions for causing the processor to perform operations comprising: maintaining a log-with-index (LWI) structure, comprising: a log for inserting and deleting records, each record including a key; and an index tree for: maintaining an index of records in the log; and in accordance with a log full signal, performing log clear operations comprising: committing the records, ordered in accordance with the index, to a new tablet in a tablet library comprising at least one previous tablet; and clearing the log and the index tree of the records; maintaining a tablet index for accessing records in the tablet library; and in accordance with a merge tablet signal, merging a first tablet in the tablet library with a second tablet in the tablet library to produce a merged tablet; wherein merging the first tablet and the second tablet comprises iteratively performing a plurality of atomic merges for each of a plurality of atomic portions, each atomic merge comprising: merging an atomic portion of the first tablet with an atomic portion of the second tablet to form an atomic portion of the merged tablet; and updating a portion of the tablet index corresponding to the atomic portion.

2. The information handling system of claim 1, wherein each record is associated with a key-value pair comprising a key field indicating a key and a value field.

3. The information handling system of claim 1, wherein: each record includes: a presence bit for distinguishing between insertion transactions and deletion transactions; and a sequence field storing a sequence value common to each record in the log; and clearing the log includes incrementing the sequence number.

4. The information handling system of claim 1, wherein the index tree comprises a binary tree.

5. The information handling system of claim 1, wherein maintaining the LWI structure comprises, maintaining the log structure in persistent storage and maintaining the index tree in memory.

6. The information handling system of claim 5, wherein inserting records comprises inserting records in the next sequential record.

7. The information handling system of claim 6, wherein the atomic portion comprises a tablet portion corresponding to a particular range of the keys.

8. The information handling system of claim 7, wherein the atomic portion comprises a plurality of fixed-size pages and wherein atomic portions comprise a particular number of tablet pages.

9. The information handling system of claim 1, further comprising: maintaining nodes of the tablet index as copy-on-write data wherein said updating of the tablet index preserves node data until the atomic merge is committed to the merged tablet and the atomic portions of the first and second tablets are released.

10. The information handling system of claim 9, wherein the tablet index includes a super root node comprising a parent node of root nodes for the first, second, and merged tablets, wherein said updating of the nodes preserves node data until the atomic merge is committed to the merged tablet and the atomic portions of the first and second tablets are released.

11. The information handling system of claim 1, wherein the log full signal is asserted responsive to utilization of the log exceeding a threshold selected from: a percentage utilization threshold; a record count threshold; and a byte size threshold.

12. A data storage method, comprising: maintaining a log-with-index (LWI) structure, comprising: a log for inserting and deleting records, each record including a key; and an index tree for: maintaining an index of records in the log; and in accordance with a log full signal, performing log clear operations comprising: committing the records, ordered in accordance with the index, to a newest tablet in a tablet library comprising at least one previous tablet; and clearing the log and the index tree of the records; maintaining a tablet index for accessing records in the tablet library; and in accordance with a merge tablet signal, merging a first tablet in the tablet library with a second tablet in the tablet library to produce a merged tablet; wherein merging the first tablet and the second tablet comprises iteratively performing a plurality of atomic merges for each of a plurality of atomic portions, each atomic merge comprising: merging an atomic portion of the first tablet with an atomic portion of the second tablet to form an atomic portion of the merged tablet; and updating a portion of the tablet index corresponding to the atomic portion.

13. The method of claim 12, wherein each record is associated with a key-value pair comprising a key field indicating a key and a value field.

14. The method of claim 12, wherein: each record includes: a presence bit for distinguishing between insertion transactions and deletion transactions; and a sequence field storing a sequence value common to each record in the log; and clearing the log includes incrementing the sequence number.

15. The method of claim 12, wherein the index tree comprises a binary tree.

16. The method of claim 12, wherein maintaining the LWI structure comprises, maintaining the log structure in persistent storage and maintaining the index tree in memory.

17. The method of claim 16, wherein inserting records comprises inserting records in the next sequential record.

18. The method of claim 17, wherein the atomic portion comprises a tablet portion corresponding to a particular range of the keys.

19. The method of claim 18, wherein the atomic portion comprises a plurality of fixed-size pages and wherein atomic portions comprise a particular number of tablet pages.

20. The method of claim 19, further comprising: maintaining the tablet index as copy-on-write data wherein said updating of the tablet index preserves node data until the atomic merge is committed to the merged tablet and the atomic portions of the first and second tablets are released.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

[0028] The description of the illustrative embodiments can be read in conjunction with the accompanying FIGUREs. It will be appreciated that, for simplicity and clarity of illustration, elements illustrated in the FIGUREs have not necessarily been drawn to scale. For example, the dimensions of some of the elements may be exaggerated relative to other elements. Embodiments incorporating teachings of the present disclosure are shown and described with respect to the FIGUREs presented herein, in which:

[0029] FIG. 1 illustrates an example information handling platform including a storage system;

[0030] FIG. 2A illustrates a block diagram of logical elements of the storage system of FIG. 1;

[0031] FIG. 2B illustrates a block diagram of structural and functional elements of the storage system of FIG. 1;

[0032] FIG. 3 illustrates a block diagram of a data structure suitable for generating and maintaining metadata for a dataset;

[0033] FIG. 4 illustrates a flow diagram of a data storage method;

[0034] FIG. 5 illustrates a flow diagram of an atomic merge of two storage tablets;

[0035] FIG. 6 illustrates a block diagram of a tablet index suitable for a disclosed tablet library; and

[0036] FIG. 7 illustrates a generation of keys suitable for use in a data deduplication application.

DETAILED DESCRIPTION

[0037] In the following detailed description, specific exemplary embodiments in which disclosed subject matter may be practiced are described in sufficient detail to enable those skilled in the art to practice the disclosed embodiments. For example, details such as specific method orders, structures, elements, and connections have been presented herein. However, it is to be understood that the specific details presented need not be utilized to practice embodiments of disclosed subject matter. It is also to be understood that other embodiments may be utilized and that logical, architectural, programmatic, mechanical, electrical and other changes may be made within the scope of the disclosed subject matter. The following detailed description is, therefore, not to be taken as limiting the scope of the appended claims and equivalents thereof.

[0038] References within the specification to “one embodiment,” “an embodiment,” “at least one embodiment”, or “some embodiments” and the like indicate that a particular feature, structure, or characteristic described in connection with the embodiment is included in at least one embodiment of the present disclosure. The appearance of such phrases in various places within the specification are not necessarily all referring to the same embodiment, nor are separate or alternative embodiments mutually exclusive of other embodiments. Further, various features may be described which may be exhibited by some embodiments and not by others. Similarly, various requirements may be described which may be requirements for some embodiments but not for other embodiments.

[0039] It is understood that the use of specific component, device, and/or parameter names and/or corresponding acronyms thereof, such as those of the executing utility, logic, and/or firmware described herein, are for example only and not meant to imply any limitations on the described embodiments. The embodiments may thus be described with different nomenclature and/or terminology utilized to describe the components, devices, parameters, methods and/or functions herein, without limitation. References to any specific protocol or proprietary name in describing one or more elements, features or concepts of the embodiments are provided solely as examples of one implementation, and such references do not limit the extension of the claimed embodiments to embodiments in which different elements, features, protocols, or concept names are utilized. Thus, each term utilized herein is to be given its broadest interpretation given the context in which that term is utilized.

[0040] Disclosed subject matter includes a storage controller with an LWI structure that supports sequential inserts of new transactions into a non-volatile log structure that is backed by a RAM-speed index tree analogous to a log structured merge tree. The LWI structure combines a memory-based index for fast searching and sorting with an NVM-based or HDD-based, sequentially accessed log structure to provide persistence and adequate insert performance. Disclosed LWI structures are tailored for use in one or more data storage and storage system applications including one or more data deduplication applications.

[0041] FIG. 1 illustrates an information handling platform 80 including a workload application 90 communicating I/O operations 92 to a storage system 100 that supports metadata and/or deduplication features in accordance with subject matter described herein. While workload application 90 is representative of substantially any application that generates I/O, the metadata and/or data deduplication features disclosed herein may be most useful with respect to workload applications that manage or otherwise interact with large, e.g., terabyte or petabyte, databases and generate a high volume of insert and other transactions.

[0042] Storage system 100 is an information handling system that receives and processes I/O operations 92. The storage system 100 of FIG. 1 encompasses hardware, firmware, drivers, and other resources for translating I/O operations 92 into read and write operations targeting one or more types of storage media. Storage system 100 may further include features or resources for maintaining and accessing metadata associated with a corresponding dataset to achieve one or more objectives including, as non-limiting examples, providing a database index structure for faster access and providing data deduplication resources to support data deduplication features.

[0043] Although storage system 100 encompasses any one or more suitable types of storage media, the storage media types emphasized in the description of the following figures include hard disk drive (HDD) storage, any of various nonvolatile semiconductor-based storage media including, as non-limiting examples, a solid state drive (SSD), and traditional random access memory (RAM). An SSD generally includes a flash memory array and a storage drive interface integrated within a single device. In at least one embodiment, storage system 100 supports nonvolatile memory (NVM) express (NVMe) SSDs, in which the storage interface is a peripheral component interconnect express (PCIe) interface.

[0044] FIG. 2A illustrates logical elements of the storage system 100 of FIG. 1. The storage system 100 illustrated in FIG. 2A includes a storage controller 120, a metadata module 125, a dataset 140, and metadata 145. The storage controller 120 receives and processes I/O operations 92 and communicates read/write operations 121 with dataset 140. The storage controller 120 of FIG. 2A interfaces with metadata module 125 to communicate transactions 128 with metadata 145.

[0045] The metadata 145 may include substantially any information descriptive of, derived from, or otherwise associated with dataset 140. The metadata 145, illustrated in more detail in FIG. 3 and subsequent figures, may include an LWI structure that includes a sequentially accessed transaction log backed by an index tree to support the generation of key-sorted transaction log tablets. In embodiments that support data deduplication, the key itself may be indicative of or otherwise in accordance with a mapping or other relationship between a data reference and a deduplication data pattern.

[0046] As depicted in FIG. 2B, storage controller 120 may be implemented as a special purpose information handling system that includes a central processing unit (CPU) 101 coupled to a memory 110 and a chip set 102. The chip set 102 of FIG. 2B includes a plurality of I/O adapters 103, any one or more of which may support a suitable high-speed serial communication protocol including, as non-limiting examples: PCIe, universal serial bus (USB), IEEE 802.3 (Ethernet), serial AT attachment (SATA), and small computer system interface (SCSI).

[0047] The chip set 102 illustrated in FIG. 2B includes a first I/O adapter 103-1 supporting an I/O bus connection to an HDD array 130, a second I/O interface adapter 103-2 supporting an I/O bus connection to an SSD 108, and a third I/O adapter 103-3 supporting an I/O bus connection to a host system (not depicted).

[0048] The memory 110 illustrated in FIG. 2B includes CPU-executable program instructions and associated data structures. The program instructions illustrated in FIG. 2B include program instructions that, when executed by CPU 101, provide functionality for an operating system 111 and one or more driver stack(s) 112 for processing I/O operations to/from an application layer program (not depicted in FIG. 2B) and read/write operations to/from storage devices including HDD array 130 and/or SSD 108. Storage driver stack 112 may include, as non-limiting examples, an I/O driver, a file system driver, a volume driver, a device driver, and a RAID driver.

[0049] In conjunction with metadata transaction functionality supported by storage controller 100, the memory 110 illustrated in FIG. 2B comprises metadata module instructions 115 for providing the metadata module 125 of FIG. 2A, including query processor instructions 114 and insertion/deletion (I/D) module instructions 116 for maintaining and querying an LWI structure 150 (illustrated in FIG. 3) as well as index tree instructions 117 to maintain a transaction index 154 (illustrated in FIG. 3).

[0050] Query processor functionality corresponding to query processor instructions 114 may support commands including: INSERT k.fwdarw.v (insert the mapping k.fwdarw.v into the transaction log), DELETE(k) (remove or invalidate an existing k.fwdarw.v mapping from the transaction log), and QUERY(k), (return the value v associated with a key k if k is present). In addition, disclosed embodiments may support extended metadata commands including, as non-limiting examples, RANGE (k1, k2), which may retrieve all keys in dataset 140 between k1 and k2 inclusive, and SUMMARIZE (k1, k2, c, m) for determining key counts including, for example, the count of all keys, as masked by m, from k1 to k2, to a maximum of c.

[0051] FIG. 3 illustrates example metadata 145 including the metadata module 125, an LWI structure 150, and a tablet library 170. Metadata module 125 may include I/D module 126, for inserting records into LWI structure 150 and deleting existing records from LWI structure 150, query processor module 124 for querying records in LWI structure 150 and/or tablet library 170, and index tree module 127 for maintaining transaction index 154.

[0052] The LWI structure 150 illustrated in FIG. 3 includes a transaction log 152 and a transaction index 154. The illustrated transaction log 152 includes a plurality of rows or records 160, each of which includes one or more columns or attributes. Each record 160 illustrated in FIG. 3 includes a key attribute 162 for storing a key, a value attribute 164 for storing a value, a presence attribute 166 for storing a presence indicator, and a sequence attribute 168 for storing a sequence value. The presence attribute 166 may indicate whether the corresponding record 160 is valid. For example, storage system 100 may perform a delete transaction by setting the presence attribute 166 of the applicable record.

[0053] In at least one embodiment, the transaction log 152 of FIG. 3 is a persistent data record maintained in an accessible HDD or SSD. The transaction log 152 illustrated in

[0054] FIG. 3 is a sequential log structure in which metadata transactions 128 arriving from metadata module 125 are processed in chronological order. FIG. 3 illustrates an example of a particular set of transactions 128 T.sub.1 through T.sub.5 occurring in a chronological order, indicated by the subscript, and transaction log 152 is shown reflecting the sequential processing of transactions 128 T.sub.1 through T.sub.3 with T.sub.4 and T.sub.5 still unprocessed. The transactions 128 illustrated in FIG. 3 include insertion transactions, indicated by a mapping symbol (.fwdarw.), each of which includes a key 163, a value 165.

[0055] FIG. 3 further illustrates LWI structure 150 including a transaction index 154 configured to provide a key-sorted index of the records 160 in transaction log 152. In at least one embodiment, transaction index 154 is maintained in RAM or SSD to achieve a desirable access performance. The transaction index 154 illustrated in FIG. 3 comprises a tree index and, more specifically, a binary tree index.

[0056] The metadata 145 of FIG. 3 includes a tablet library 170 comprising a tablet index 171 and a plurality of two or more tablets 172, 172-1 through 172-N. Whenever transaction log 152 becomes full or nearly full, storage system 100 may generate a log full signal and LWI structure 150 may respond by writing the records 160 in transaction log 152 to persistent storage in tablet library 170. In at least one embodiment, each tablet 172 originates when transaction log 152 is cleared from time to time. In conjunction with transaction index 154, at least some embodiments may write transaction log 152 out to HDD in key-sorted order. The key sorted order is conveyed in FIG. 3 by the “A” to “Z” markings under tablet 172-1 and tablet 172-N.

[0057] Referring now to FIG. 4, a flow diagram of a metadata method 400, performed by storage system 100 or a resource of storage system 100, for employing a LWI structure to maintain and query metadata associated with a dataset is illustrated.

[0058] In the metadata method 400 of FIG. 4 the applicable system or resource monitors(operation 402) for an I/O metadata transaction, an example of which is the metadata transaction 128 illustrated in FIG. 2. When a metadata transaction is detected (operation 404), the transaction is inserted or otherwise incorporated (operation 406) into the transaction log, e.g., the transaction log 152 of FIG. 2, and the index tree is updated (operation 410) to reflect the newly inserted transaction.

[0059] In at least some embodiments, the transaction log is maintained in nonvolatile storage and transactions are incorporated into the transaction log sequentially, to insure adequate insert/delete performance. The index tree may be maintained in RAM or in an SSD and is used to maintain an index of the keys stored in the transaction log.

[0060] The metadata method 400 of FIG. 4 continues to monitor for transactions and to incorporate any transactions detected until a log full signal is detected (operation 412). The storage system 100 may generate a log full signal based upon any of various criteria determined based, at least in part, on the number of transactions stored in the transaction log, the amount of time since the last assertion of the log full signal, or a combination of both. In at least one embodiment, the transaction log is a fixed-size data structure and the log full signal is asserted based solely or partially on the number of records in the transaction log, e.g., log full signal is asserted upon detecting that the transaction log is filled to capacity or that the number of records stored in the transaction log exceeds a threshold value. In some embodiments, the log full signal may be periodically or non-periodically asserted even if the number of transaction log records does not exceed the applicable threshold.

[0061] When a log full signal is generated, the metadata method 400 of FIG. 4 creates (operation 420) a new tablet, stores (operation 422) the transaction log records to the new tablet, and clears (operation 424) the transaction log. In conjunction with the transaction index 154, the transaction log records are stored to the tablet in key-sorted order, e.g., from lowest key to highest key or vice versa. The clearing of the transaction log may include deleting or otherwise releasing all transaction log records and all node data in the index tree. In embodiments that employ a transaction log sequence number, the transaction log sequence number may be incremented (operation 426) in response to all or some assertions of the log full signal.

[0062] The metadata method 400 illustrated in FIG. 4 monitors (operation 430) for a tablet merge signal and performs a tablet merge (operation 432) in response to assertions of the tablet merge signal. The tablet merge 432 may include the creation of a storage space for a merged tablet followed by the merging of two or more existing tablets. In at least some embodiments, tablets are generally treated as read-only data structures once created. However, because the tablets represent a chronological sequence of key-sorted transaction log snap shots and because keys can be deleted or overwritten, tablet data may become stale over time. To maintain the relevance of the records in the tablet library and prevent an index that includes an ever-increasing number of decreasingly significant tablet layers, two or more tablets may be merged, with any conflicting entries being resolved in favor of the newer tablet.

[0063] Tablet merges may occur periodically or based upon one or more other or additional criteria. The size of a tablet resulting from the merging of two existing tablets can range from a minimum size, equal to the size of the more recent tablet, to a maximum size, equal to the sum of the two tablets. Assuming that any two newly created tablets are of approximately the same size and a tablet merge occurs between two existing tablets each time a new tablet is created, i.e., whenever the number of tablets equals three the two oldest tablets are merged, it can be seen that the size of the merged tablet may grow monotonically over time.

[0064] To prevent an unchecked drift of tablet size over time, any one of various suitable operations may be included within metadata method 400. For example, if the size of the tablet library, excluding the oldest tablet, exceeds a particular threshold, merge operations are performed. In another example, a time stamp may be associated with each tablet. If the age of the oldest tablet exceeds a particular threshold, merge operations are performed.

[0065] FIG. 5 illustrates an example of the tablet merge operation 432 of FIG. 4. The tablet merge operation 432 of FIG. 5 addresses a concern particularly applicable in the context of massive datasets, where tablet sizes of terabytes or petabytes may be common. Merging two or more very large HDD tablets can require a massive number of compute cycles. As the amount of time required to convert a data set from one state to another state increases, the cost associated with a failure occurring during the transition increases.

[0066] To reduce the risk associated with losing a potentially enormous amount of computational “work-in-progress” during a tablet merge, the tablet merge operation 432 depicted in FIG. 5 comprises a series of atomic merges, i.e., merges of atomic portions of two or more tablets. By performing the tablet merge as a series of atomic merges, the risk associated with a power failure or other fatal disruption is limited to the computational risk associated with each atomic merge. Thus, the risk can be controlled by adjusting the atom size, i.e., the portion of a tablet merged during any given atomic merge.

[0067] Atom sizes may be chosen in accordance with any one or more of various suitable parameters. For example, because the tablets contain records arranged in key sorted order, the atomicity of each merge may be defined according to a range of keys. Alternatively, if the tablets are formatted into fixed-size pages when stored, atomicity might be defined in terms of physical pages, e.g., each atomic merge merges N physical pages. Defining atomicity in terms of physical pages may, however, result in some duplicate entries in the merged tablet since page ranges and key ranges are not inherently aligned.

[0068] The tablet merge operation 432 illustrated in FIG. 5 includes identifying (block 502) the first or next successive atomic portion (ATP) to be merged, whether based on key ranges, physical page ranges, a combination of both, or otherwise.

[0069] Whenever the distribution of keys within a tablet is non-uniform, a key-defined atomicity may result in some atomic merges that process more records than others. Similarly, if the distribution of keys in a first tablet differs from the distribution of keys in a second tablet, an atomic merge may require more time to complete since fewer keys in the older tablet can be discarded due to the presence of the same key in the newer tablet. Some embodiments may impose page-based or other size-based constraints on the size of an atom to achieve a more uniform atomic risk, i.e., the risk of re-performing an atomic merge. Once the first or next successive ATP is defined, the tablet merge operation 432 of FIG. 5 allocates (operation 504) storage space for the ATP of the merged tablet.

[0070] As described below with respect to FIG. 6 below, storage system 100 may maintain an index for the tablet library to improve query performance. To accommodate atomic merging as described herein, the nodes of this tablet index may be implemented as copy-on-write nodes, in which an attempt to write node data stores the write value in a different storage location, thereby preserving the original data. In this manner, the tablet index nodes may be modified, e.g., to index records in the merged tablet rather than records in the source tablets, while an atomic merge is in progress without committing the original node data. If a failure occurs while an atomic merge is in progress, the pre-failure stat of the tablet index can be restored. Accordingly, the tablet merge operation 432 illustrated in FIG. 5 includes a copy-on-write operation(operation 506) in which source tablet index nodes associated with the current ATP are duplicated and modified.

[0071] The source tablet ATPs are then merged (operation 510) into the ATP of the merged tablet. The basic merge operation may comprise a prioritized union of the source ATPs in which duplicate records are discarded and any conflicting records are resolved in favor of the more recent record. In this manner, the merged tablet contains all the records included in the newer tablet plus any record in the older tablet for a key not found in the newer tablet. After the entire ATP of the source tablets has been merged into the corresponding ATP of the merged tablet, the tablet index nodes that were previously stored to copy-on-write storage locations can be committed (operation 512) to the tablet index and the original data can be released.

[0072] The tablet merge operation 432 illustrated in FIG. 5 determines (operation 520) whether any ATPs remain and, if so, returns to the identification of the next ATP in operation 502. When all ATPs have been processed, the tablet index nodes of the source tablets and the source tablets themselves can be released (operation 522) in their entirety, at which point the merged tablet is fully committed.

[0073] FIG. 6 illustrates a tablet index 171 suitable for performing the atomic merging described with respect to FIG. 5. The tablet index 171 illustrated in FIG. 6, which illustrates the merging of two source tablets, includes three multi-tiered node trees 602, including node trees 602-1 and 602-2 corresponding to the first and second source tablets and a node tree 602-3 for the merged tablet. Each node tree 602 includes a root node 604 and two or more generations of descendant nodes terminating in a set of leaf nodes 610.

[0074] The tablet index 171 of FIG. 6 includes a super node 601 that has each of the three root nodes 604 as its child nodes. In this manner, super node 601 provides a single point of synchronization for the tablet index, encompassing the source nodes as well as the target node. In addition, as described above each individual tablet index node 611 is a copy-on-write data structure that includes a committed block 612 and a modified block 613. Either of the blocks may serve as the committed block and the node may include additional metadata not illustrated in FIG. 6 to indicate at any given time which of the two blocks contains committed data. During an atomic merge operation, the storage system 100 may index the tablet library using the data in the modified block of the applicable tablet index node until the entire ATP is merged, at which point the copy-on-write data can be committed all the way up the node tree to super node 601. Once modified data has been committed through to the super nodes 601, the previously committed data may be released.

[0075] FIG. 7 illustrates a key generation feature suitable for use with a data deduplication application of the log and tree structure analogous to the metadata 145 illustrated in FIG. 3. The key generation technique illustrated in FIG. 7 generates data deduplication keys 720 that beneficially indicate an association between a data reference and its corresponding data pattern.

[0076] Data deduplication keys 720 may be beneficially used in storage systems 100 that support data deduplication. Data deduplication support may include elements (not depicted in FIG. 7) for performing a hashing algorithm on arriving data blocks and maintaining a library of the hash values. The hash value of each newly arriving data block can be queried against the library hash values. If a match is detected and verified, a reference to the existing data block is stored instead of storing a second copy of the data block itself. An exemplary data deduplication technique is more fully described in R. Brosch, Data Deduplication with Augmented Cuckoo Filters, U.S. patent application Ser. No. 15/431,938, filed Feb. 11, 2016, incorporated by referenced herein.

[0077] FIG. 7 illustrates a group of data blocks 702, including data blocks 702-1, 702-2, and 702-3. Each data block 702 may represent a fixed-size or variable-sized block of data, referred to herein as the data block's pattern, which may comprise the data block itself or a hash of the data block depending upon how the data deduplication is implemented. FIG. 7 further illustrates set of references 712 to the illustrated data pattern addresses 704. In particular, FIG. 7 illustrates a data reference memory 710 that includes a set of data deduplication references 712, each of which includes a data reference value 711 and a corresponding data reference address 714.

[0078] FIG. 7 illustrates an example configuration that employs, for the sake of simplicity, an 8-bit data pattern address and an 8-bit data reference address. The number of bits used for either of these two addresses is an implementation detail and other embodiments may use other values. FIG. 7 further illustrates the use of 4 KB data patterns 702, but other embodiments may use smaller or larger data blocks.

[0079] FIG. 7 illustrates four data deduplication references 712, including three data deduplication references 712-1, 712-2, and 712-3, containing references to data pattern 1 702-1, and a single data deduplication reference 712-4 containing a reference to data pattern address 704-3. Specifically, data reference addresses 0x05, 0x11, and 0x15 of data reference memory 710 are each associated with data pattern address 0x01, where data pattern address 0x01 corresponds to the first data pattern 702-1. Data reference address 0x02 is associated with data pattern address 0x03, where data pattern address 0x03 corresponds to third data pattern 702-3.

[0080] For at least some purposes useful in maintaining data deduplication metadata, it may be beneficial to configure a key that, when sorted, readily reveals the number of data deduplication references 712 to any particular data pattern 702. The data deduplication keys 720-1 through 720-4 corresponding to data deduplication references 712-1 through 712-4 respectively are produced or obtained by concatenating the applicable data reference address 714 and the applicable data pattern address 704 with the data pattern address 704 stored in the most significant bits and the data reference address 714 stored in the least significant bits. Other embodiments may produce or obtain data deduplication keys 720 differently.

[0081] In at least one embodiment, each data deduplication key 720 represents a key 162 in the log 152 of FIG. 3. Each of the data deduplication keys 720 illustrated in FIG. 7 thus contains a reference to the data pattern address 704 and a reference to the data reference address 714 for each data deduplication reference 712. Moreover, because the data pattern address 704 occupies the most significant bits of the applicable data deduplication key 720, a numerically-ordered sorting of the keys 162 facilitates reference counts and other data pattern based characterizations of the set of keys 162.

[0082] Accordingly, the data deduplication keys 720 illustrated in FIG. 7 in this manner beneficially support extended query operations that may be useful in data deduplication operations. For example, when a set of keys 162 generated in accordance with the data deduplication keys 720 is arranged in key-sorted order, the keys 162 readily reveal the number of references to any particular data pattern 702, i.e., deduplication reference counts, including data patterns 702 which are not referenced by any data reference value 711 in data reference memory 710. Similarly, a key-sorted list of keys 162 facilitates the process of identifying keys associated with an atomic tablet merge as described above. Every time another reference to a data pattern is detected in the dataset, the applicable reference count can be incremented. Whenever a reference to a data pattern is removed, the reference count may be decremented. When the reference count for a specific data pattern decrements to zero, this indicates that there is no reference to this pattern and the data pattern can therefore be released.

[0083] The data deduplication references 720 illustrated in FIG. 7 may be inserted into transaction log 152 of FIG. 3 and managed in conjunction with the transaction index 154 and the tablet library 170 illustrated in FIG. 3. In any such embodiment, the value attribute 164 illustrated in transaction log 152 of FIG. 3 may be omitted, ignored, or configured to reflect a null value because the data deduplication keys 720 have no corresponding value data, In other respects however, data deduplication keys 720 may be indexed in the transaction index 154 and written out to tablet library 170 as tablets, where the tablets may be merged from time to time as described above.

[0084] Any one or more processes or methods described above, including processes and methods associated with the FIG. 4 and FIG. 5 flow diagrams, may be embodied as a computer readable storage medium or, more simply, a computer readable medium including processor-executable program instructions, also referred to as program code or software, that, when executed by the processor, cause the processor to perform or otherwise result in the performance of the applicable operations.

[0085] A computer readable medium, which may also be referred to as computer readable memory or computer readable storage, encompasses volatile and non-volatile media, memory, and storage, whether programmable or not, whether randomly accessible or not, and whether implemented in a semiconductor, ferro-magnetic, optical, organic, or other suitable medium. Information handling systems may include two or more different types of computer readable medium and, in such systems, program code may be stored, in whole or in part, in two or more different types of computer readable medium.

[0086] Unless indicated otherwise, operational elements of illustrated or described methods may be combined, performed simultaneously, or performed in a different order than illustrated or described. In this regard, use of the terms first, second, etc. does not necessarily denote any order, importance, or preference, but may instead merely distinguish two or more distinct elements.

[0087] Program code for effecting described operations may be written in any appropriate combination of programming languages and encompasses human readable program code including source code as well as machine readable code including object code. Program code may be executed by a general purpose processor, a special purpose processor, including, as non-limiting examples, a graphics processor, a service processor, or an embedded processor or controller.

[0088] Disclosed subject matter may be implemented in any appropriate combination of software, firmware, and hardware. Terms including circuit(s), chip(s), processor(s), device(s), computer(s), desktop(s), laptop(s), system(s), and network(s) suggest at least some hardware or structural element(s), but may encompass non-transient intangible elements including program instruction(s) and one or more data structures including one or more databases.

[0089] While the disclosure has been described with reference to exemplary embodiments, it will be understood by those skilled in the art that the disclosure encompasses various changes and equivalents substituted for elements. Therefore, the disclosure is not limited to the particular embodiments expressly disclosed, but encompasses all embodiments falling within the scope of the appended claims.

[0090] As used herein, the singular forms “a”, “an” and “the” are intended to include the plural forms as well, unless the context clearly indicates otherwise. It will be further understood that the terms “comprises” and/or “comprising,” when used in this specification indicate the presence of stated features, operations, elements, and/or components, but does not preclude the presence or addition of one or more other features, operations, elements, components, and/or groups thereof.