Chronologically ordered out-of-place update key-value storage system

One embodiment provides a method including storing a key-value store in a memory. Out-of-place operations are performed to maintain chronological ordering of the operations by enforcing ordering of the operations on a storage layer in presence of a garbage collection transaction without an explicit secondary index.

BACKGROUND

Typical log-structured storage systems store record data in temporal order in a “log.” These typical systems allow basic primitive operations, such as insert, update, delete, read. Each update of data results in a new record being inserted at the tail of the “log.” Each delete results in a tombstone object being inserted at the tail of the log. Additionally, background garbage collection process compacts the data reclaiming space that does not contain valid data.

SUMMARY

Embodiments relate to chronologically ordered out-of-place updates in a key-value storage system. One embodiment provides a method including storing a key-value store in a memory. Out-of-place operations are performed to maintain chronological ordering of the operations by enforcing ordering of the operations on a storage layer in presence of garbage collection transactional processing without an explicit secondary index.

DETAILED DESCRIPTION

One or more embodiments relate to chronologically ordered out-of-place updates in a key-value storage system. One embodiment provides a method including storing a key-value store in a memory. Out-of-place operations are performed to maintain chronological ordering of the operations by enforcing ordering of the operations on a storage layer in presence of GC transactional processing without an explicit secondary index.

Characteristics are as follows:

On-demand self-service: a cloud consumer can unilaterally provision computing capabilities, such as server time and network storage, as needed and automatically, without requiring human interaction with the service's provider.

Service Models are as follows:

Deployment Models are as follows:

A cloud computing environment is a service oriented with a focus on statelessness, low coupling, modularity, and semantic interoperability. At the heart of cloud computing is an infrastructure comprising a network of interconnected nodes.

Workloads layer90provides examples of functionality for which the cloud computing environment may be utilized. Examples of workloads and functions which may be provided from this layer include: mapping and navigation91; software development and lifecycle management92; virtual classroom education delivery93; data analytics processing94; transaction processing95; and chronologically ordered out-of-place updates in a key-value storage system processing96. As mentioned above, all of the foregoing examples described with respect toFIG. 2are illustrative only, and the invention is not limited to these examples.

It is understood all functions of one or more embodiments as described herein may be typically performed by the processing system300(FIG. 3) or the autonomous cloud environment410(FIG. 4), which can be tangibly embodied as hardware processors and with modules of program code. However, this need not be the case for non-real-time processing. Rather, for non-real-time processing the functionality recited herein could be carried out/implemented and/or enabled by any of the layers60,70,80and90shown inFIG. 2.

It is reiterated that although this disclosure includes a detailed description on cloud computing, implementation of the teachings recited herein are not limited to a cloud computing environment. Rather, the embodiments of the present invention may be implemented with any type of clustered computing environment now known or later developed.

FIG. 3illustrates a network architecture300, in accordance with one embodiment. As shown inFIG. 3, a plurality of remote networks302are provided, including a first remote network304and a second remote network306. A gateway301may be coupled between the remote networks302and a proximate network308. In the context of the present network architecture300, the networks304,306may each take any form including, but not limited to, a LAN, a WAN, such as the Internet, public switched telephone network (PSTN), internal telephone network, etc.

In use, the gateway301serves as an entrance point from the remote networks302to the proximate network308. As such, the gateway301may function as a router, which is capable of directing a given packet of data that arrives at the gateway301, and a switch, which furnishes the actual path in and out of the gateway301for a given packet.

Further included is at least one data server314coupled to the proximate network308, which is accessible from the remote networks302via the gateway301. It should be noted that the data server(s)314may include any type of computing device/groupware. Coupled to each data server314is a plurality of user devices316. Such user devices316may include a desktop computer, laptop computer, handheld computer, printer, and/or any other type of logic-containing device. It should be noted that a user device311may also be directly coupled to any of the networks in some embodiments.

A peripheral320or series of peripherals320, e.g., facsimile machines, printers, scanners, hard disk drives, networked and/or local storage units or systems, etc., may be coupled to one or more of the networks304,306,308. It should be noted that databases and/or additional components may be utilized with, or integrated into, any type of network element coupled to the networks304,306,308. In the context of the present description, a network element may refer to any component of a network.

According to some approaches, methods and systems described herein may be implemented with and/or on virtual systems and/or systems, which emulate one or more other systems, such as a UNIX system that emulates an IBM z/OS environment, a UNIX system that virtually hosts a MICROSOFT WINDOWS environment, a MICROSOFT WINDOWS system that emulates an IBM z/OS environment, etc. This virtualization and/or emulation may be implemented through the use of VMWARE software in some embodiments.

FIG. 4shows a representative hardware system400environment associated with a user device416and/or server314ofFIG. 3, in accordance with one embodiment. In one example, a hardware configuration includes a workstation having a central processing unit410, such as a microprocessor, and a number of other units interconnected via a system bus412. The workstation shown inFIG. 4may include a Random Access Memory (RAM)414, Read Only Memory (ROM)416, an I/O adapter418for connecting peripheral devices, such as disk storage units420to the bus412, a user interface adapter422for connecting a keyboard424, a mouse426, a speaker428, a microphone432, and/or other user interface devices, such as a touch screen, a digital camera (not shown), etc., to the bus412, communication adapter434for connecting the workstation to a communication network435(e.g., a data processing network) and a display adapter436for connecting the bus412to a display device438.

In one example, the workstation may have resident thereon an operating system, such as the MICROSOFT WINDOWS Operating System (OS), a MAC OS, a UNIX OS, etc. In one embodiment, the system400employs a POSIX® based file system. It will be appreciated that other examples may also be implemented on platforms and operating systems other than those mentioned. Such other examples may include operating systems written using JAVA, XML, C, and/or C++ language, or other programming languages, along with an object oriented programming methodology. Object oriented programming (OOP), which has become increasingly used to develop complex applications, may also be used.

FIG. 5illustrates an example key-value storage system500for chronologically ordered out-of-place updates, according to an embodiment. The term “garbage collection” (GC) refers to reclaiming “disk space” occupied by stale entries in the log. For example, when a record is inserted, an entry is added to the tail of the log. When the same record is deleted, a tombstone entry is added to the tail of the log. The tombstone entry refers to the original location of the data on disk as created by the insert. The disk space occupied by the original inserted record may be garbage collected (provided the system is not maintaining older versions). Stale data may be the result of records that have been deleted or updated. Updates result in stale data because older versions of the data that are maintained in the log are no longer needed. Note that in a log-structured store, every insert, update or delete operation results in a record being inserted at the tail of the log.

For log structured storage systems for small objects (e.g., a log structured key-value store), update operations are treated as new writes (append-only). Application programming interfaces (APIs) include: PUT, GET and DELETE. The PUT API returns back the address to the caller. The DELETE API results in insertion of a tombstone. Space occupied by deleted objects is reclaimed by the GC process. The object size is small (typically, 10s or 100s of bytes). GC granularity is large (MBs or GBs).

In system500, an object indexing service (OIS)510performs PUT, GET and DELETE operations. In one embodiment, the format of the PUT operation is: PUT (key, value, <previous address>, which returns address. In one embodiment, the format of the GET operation is: GET (Address), which returns Key-value record. In one embodiment, the format of the DELETE operation is: DELETE (address). The output or returned value from the OIS510is input into the object storage service (OSS)520, which is used for a GC process530. In one embodiment, the OIS510and the OSS520may or may not be collocated. The OIS510and the OSS520, even if co-located may be part of different processes. In one example embodiment, a key is exposed to the OSS520.

In one embodiment, the GC process530is performed as a transaction. Transaction processing divides information processing into individual, indivisible operations known as transactions. Each transaction must succeed or fail as a complete unit, and can never be only partially complete.

FIG. 6illustrates an example600of GC object granularity, according to an embodiment. Ad-hoc deletion results in fragmentation of space and poor utilization. GC process530(FIG. 5) granularity>>object granularity. GC process530of a slot requires live objects to be relocated.

Returning toFIG. 5, the system500retains chronological order of operations as follows. In one embodiment, chronological ordering provides for the ability to iterate the key-value store in the order in which the keys are inserted/updated in the store without an explicit secondary index. Since the store is out-of-place updated, all writes/updates may be performed in the chronological order. Chronological ordering of data is important in order to efficiently support functionality such as “change capture feed.” For example, to support queries such as “list all valid changes since.” Such a query should list only valid (i.e., not deleted records) but should list them in chronological order. Retaining chronological order is also useful for failure recovery if the append-only data store is being treated as a log. Chronological order is difficult to maintain while supporting delete/update operations and performing GC process530to retain valid records. In one example, a problem is that conventional GC processing of invalid key-value pairs will re-order the data, breaking chronological order. In one embodiment, system500provides a mechanism to maintain chronological order of keys in the presence of GC process530without maintaining a secondary index.

In one embodiment, system500provides for chronological ordering without secondary index by implementing the following. System500performs writes, updates and deletes in the order in which operations are issued by the upper layer. In one embodiment, system500maintains this information implicitly by performing the operations in a logically increasing order at the storage layer (e.g., in a log-structured order). Typical GC processing will break this implicit ordering.

FIG. 7illustrates an example700of a GC break of chronological order, according to an embodiment. As shown, the example700includes index710, on disk layout720(showing log position), on disk layout730with holes marked, and log position740after chronological out-of-order GC. The out-of-order GC includes garbage collecting the first slot (0-4) and writing the valid content at position1after position11leads to non-chronological ordering. This results in the log position740having positions10,11and12with keys5,6and1(out of chronological order).

FIG. 8illustrates an example800of a chronological in-order GC, according to an embodiment. As shown, using the system500(FIG. 5), after processing chronological in-order-GC, the log position840shows the results for log positions0,1, and2including the in-order of keys1,5and6. The in-order-GC includes garbage collecting the first slot (0-4) and writing the valid content at position1to maintain the ordering. Internal ordering includes maintaining relative ordering of keys copied from the victim slot as before GC. External ordering includes maintaining relative ordering of keys copied from the victim slot the same as compared to the rest of the keys in other slots as before GC.

FIG. 9Aillustrates an example900of slots including a GC victim slot930(slot2), according to an embodiment. The example900includes slot0910, slot1920and slot2930, which is the GC victim slot.FIG. 9Bshows example900including a GC target slot (slot51940), according to an embodiment. In this example900, the GC victim (slot2930) where live data is moved to the GC target slot (slot51940). In the approach showed by example900, a tombstone record has the format of: <TOMBSTONE, key, prior address>. The prior address refers to the last valid address for the key. A data record has the format of: “Address x”: <DATA, key, value, prior address (“Address x−n”)>, where x and n are positive integers. When a data record is moved, the following new records are inserted:<DATA, key, value, “Address x”>, <TOMBSTONE, key, “Address x−n”>.

FIG. 10Aillustrates an example1000initial state of a target slot (slot511030) and a victim slot (slot31040) prior to GC, according to an embodiment. The example1000shows slot11020, slot511030(target slot), slot31040(victim slot) and key-value index1010. Also shown is a back-pointer1050shown from slot31040position1(K8) to slot11020position4(k8).FIG. 10Billustrates the example1000state of the target slot (slot511030) after GC, according to an embodiment. As shown, the key-value index1010is modified to key-value index1015, which shows the modification of K8, K9and K10to slot51:6, slot51:8and slot51:9, respectively. Slot511030now includes the target slot at position7(K8) that points to the victim slot (slot31040, which now does not exist; which is the same for positions7,8and9). Additionally, cleanup is required after GC failure (e.g., incomplete transaction). The back-pointer (points to previous address)1055points from position7of slot511030to position4of slot11020.

In one embodiment, in-order chronological GC processing includes the following. (1) The system500(FIG. 5) selects a victim slot (e.g., slot31040). In one embodiment, victim slot selection is based on system “cost-benefit” (i.e., processing time, bandwidth, memory usage, etc.) analysis, sequential slot selection, etc. Next, (2) the system500estimates the amount of live data in the victim slot. (3) The target slot(s) (e.g., slot511030) are then identified. If a prior slot has free capacity, the target slot is identified as the prior slot of the victim slot. Otherwise, if more valid content needs to be copied, system500selects a free slot as a target slot (assign next logical slot identifier (ID)) and insert it before the victim slot in the slot chain. (4) System500then records the beginning of the GC transaction in the recovery log. (5) The valid content is then copied from the victim slot to the target slot. This includes placing a tombstone if the record being copied is an update (needed so that the original insert remains invalid and does not show up), where the tombstone points to where the update back-pointer is pointing to in the victim slot. The back-pointer for entries in the GC target slot should point to the victim slot. The valid content includes “live data records” and “live tombstones.” (6) Next, system500updates the in-memory index (e.g., a b+ tree-based index) to record the new position of the key in the target slot. (7) If more valid content needs to be copied, system500selects a free slot and inserts it before the victim slot in the slot chain and proceed back to (3). (8) System500records the end of the GC transaction in the recovery log.

One or more embodiments provides chronological ordering of the data by explicitly ensuring that a garbage collector does not re-order the relative location of the data. Therefore, system500stores the data in chronological order without reordering during GC. One or more embodiments have the advantage over conventional systems in that secondary indexing is not needed, and that GC does not need to be turned off, which provides for improving the effective use of available storage capacity.

FIG. 11illustrates a block diagram for a process1100for chronologically ordered out-of-place updates in a key-value storage system, according to one embodiment. In one embodiment, block1110in process1100includes storing a key-value store in a memory. Out-of-place operations are performed by a processor to maintain chronological ordering of the operations by enforcing ordering of the operations on a storage layer in presence of GC transactional processing without an explicit secondary index.

In one embodiment, in process1100the out-of-place operations include update, delete and insert operations. In one embodiment, process1100may further include performing a GC transaction to maintain the chronological ordering of the operations by keeping a same relative order of keys copied out of a victim slot as in at least one target slot before the GC transaction.

In one embodiment, process1100may include performing a GC transaction to maintain a same relative order of keys copied out of a victim slot as compared to keys in other slots before GC transaction processing. In one embodiment, process1100may further include estimating amount of live data in a victim slot, identifying at least one target slot, recording a beginning of a GC transaction in a recovery log, copying valid content from the victim slot to the at least one target slot, placing a tombstone if a record being copied is an update, and updating an in-memory index to record a new position of a key in the target slot. In one embodiment, in process1100the tombstone points to where an update back-pointer is pointing to in the victim slot, a back-pointer for entries in the target slot points to the victim slot, and valid content includes live data records and live tombstones.

In one embodiment, process1100may further include recording an end of the GC transaction in the recovery log.