Abortable transactions using versioned tuple cache

A transaction manager for handling operations on data in a storage system provides a system for executing transactions that uses a versioned tuple cache to achieve fast, abortable transactions using a redo-only log. The transaction manager updates an in-memory key-value store and also attaches a transaction identifier to the tuple as a minor key. Opportunistic locking can be accomplished due to the low cost of aborting transactions.

BACKGROUND

Storage systems often use transactions to get atomic updates of on-disk data structures. For example, an update operation on a bitmap data structure to indicate certain blocks are now allocated and a write operation of the underlying blocks are performed atomically to ensure consistency of the storage system. Otherwise, if the storage system should crash or fail mid-operation, the storage system (specifically the bitmap and underlying data blocks) would be left in an inconsistent state. Isolation is another characteristic of storage systems, which ensures that concurrent (e.g., in parallel) execution of transactions results in a system state that would be obtained if the transactions were executed serially. Database systems have typically used data structures such as undo-redo logs to achieve isolation characteristics in relational database systems. However, because of the overhead incurred by undo-redo logs, file and storage systems have conventionally used redo-only logs to get fast transactions which cannot be aborted.

DETAILED DESCRIPTION

Embodiments of the present disclosure provides a system for executing transactions that uses a versioned tuple cache to achieve fast, abortable transactions using a redo-only log. Embodiments include a transaction manager that updates an in-memory key-value store and also attach a transaction identifier to the tuple as a major key. Unless a transaction is aborted, the transaction manager executes searches on the key-value store that ignores all tuples modified by un-committed transactions. The transaction manager may use a hash table of committed transactions and a maximal committed transaction identifier to determine whether a particular transaction has been committed. Accordingly, embodiments of the present disclosure enable opportunistic locking to be performed because the cost of aborting transactions is low compared to other approaches.

FIG. 1is a block diagram that illustrates a computer system100according to one or more embodiments of the present disclosure. Computer system100includes one or more hosts102configured to provide a virtualization layer that abstracts processor, memory, storage, and networking resources of a hardware platform108into multiple virtual machines (VMs)116that run concurrently on the same host102. VMs116run on top of a software interface layer, referred to as a hypervisor106, that enables sharing of the hardware resources of host102by VMs116. One example of hypervisor106is a VMware ESXi hypervisor provided as part of the VMware vSphere solution made commercially available from VMware, Inc. In some embodiments, storage system104may be implemented as software-define storage such as VMware Virtual SAN that clusters together server-attached hard disks and/or solid state drives (HDDs and/or SSDs), to create a flash-optimized, highly resilient shared datastore designed for virtual environments.

While embodiments are described in relation to a virtualized system, embodiments of the present disclosure can also be applied and/or extended to general filesystems and storage system layers.

Host102may comprise a general purpose computer system having one or more virtual machines accessing data stored on a storage system104communicatively connected to host102. Host102may be constructed on a conventional, typically server-class, hardware platform108. Hardware platform108of host102may include conventional physical components of a computing device, such as a processor (CPU)110, a memory111, a disk interface112, and a network interface113card (NIC. Processor110is configured to execute instructions, for example, executable instructions that perform one or more operations described herein and may be stored in memory111. Memory111and storage system104are devices allowing information, such as executable instructions, cryptographic keys, virtual disks, configurations, and other data, to be stored and retrieved. Memory111may include, for example, one or more random access memory (RAM) modules. Storage system104may include one or more locally attached storage devices, for example, one or more hard disks, flash memory modules, solid state disks, and optical disks. In some embodiments, storage system104may include a shared storage system having one or more storage arrays of any type such as a network-attached storage (NAS) or a block-based device over a storage area network (SAN). Disk interface112, such as a host bus adapter (HBA), enables host102to communicate with a storage device, such as storage system104, to store “virtual disks” that are accessed by VMs116, as described later. Network interface113enables host102to communicate with another device via a communication medium, such as a communication network (not shown). An example of network interface113is a network adapter, also referred to as a Network Interface Card (NIC).

While storage system104is typically made up of a plurality of disks, other forms of storage, such as solid-state non-volatile storage devices, may be used, and the use of the term, “disk” herein, should therefore not be construed as limited only to rotating disk storage media, but may also be construed to encompass solid state disks, or “SSDs.” In some embodiments, storage system104may be comprised of high-density non-volatile memory. Furthermore, while storage system104is depicted as a separate, external component to host102, storage system104may be internal to host102, for example, a local storage device or locally attached storage.

As shown inFIG. 1, a hypervisor106is installed on top of hardware platform108and supports a virtual machine execution space114within which multiple virtual machines (VMs)1161-116Nmay be instantiated and executed. Each such virtual machine1161-116Nimplements a virtual hardware platform118that supports the installation of a guest operating system (OS)120which is capable of executing one or more applications (not shown). Examples of a guest OS120include any of the well-known commodity operating systems, such as Microsoft Windows, Linux, and the like. In each instance, guest OS120includes a native file system layer, for example, either an NTFS or an ext3 type file system layer. These file system layers interface with virtual hardware platforms118to access, from the perspective of guest operating systems120, a data storage HBA, which in reality, is virtual HBA122implemented by virtual hardware platform118that provides the appearance of disk storage support (in reality, virtual disks124A-124X) to enable execution of guest OS120transparent to the virtualization of the system hardware. A virtual disk124exposes the same abstraction as a real (physical) disk, that is, a linear list of sectors; however, a VMM may choose to implement virtual disks124as regular files on the host. Although, from the perspective of guest operating systems120, file system calls initiated by such guest operating systems120to implement file system-related data transfer and control operations appear to be routed to virtual disks124A-124Xfor final execution, in reality, such calls are processed and passed through virtual HBA122to adjunct virtual machine monitor (VMM) layers1261-126Nthat implement the virtual system support needed to coordinate operation with hypervisor106. In particular, a HBA emulator of each VMM126functionally enables the data transfer and control operations to be correctly handled by hypervisor106which ultimately passes such operations through its various layers to true hardware HBAs112or NIC113that connect to storage system104.

Hypervisor106includes a storage layer132configured to manage storage space persistently for VMs116via VMM layers1261to126N. In one embodiment, storage layer132may include numerous logical layers, such as an I/O virtualization layer, a file system driver, and a disk access layer. In some embodiments, the I/O virtualization layer receives a data transfer and control operation (in the form of I/O commands, for example, intended for a virtual disk) from VMM layers1261to126N, and converts the operations into file system operations that are understood by a virtual machine file system (VMFS) driver in order to access a file stored in underlying storage under the management of the VMFS driver that represents virtual disk124. The I/O virtualization layer then issues these file system operations to the VMFS driver. The VMFS driver, in general, manages creation, use, and deletion of files (e.g., such as .vmdk files representing virtual disks) stored on physical locations of, or in logical volumes or Logical Unit Numbers (LUNs) exposed by, storage system104. The VMFS driver converts the file system operations received from the I/O virtualization layer to raw SCSI operations, which are issued to a data access layer that applies command queuing and scheduling policies to the raw SCSI operations and ultimately sends the raw SCSI operations to components of physical hardware platform108. While storage layer132is depicted as part of a virtualized architecture, it should be recognized that embodiments of the present disclosure can be extended to other systems having a storage layer. For example, in an alternative embodiment, storage layer132may be a file system driver of an operating system that manages storage space persistently for locally attached storage.

It should be recognized that the various terms, layers and categorizations used to describe the virtualization components inFIG. 1may be referred to differently without departing from their functionality or the spirit or scope of the invention. For example, VMMs126may be considered separate virtualization components between VMs116and hypervisor106(which, in such a conception, may itself be considered a virtualization “kernel” component) since there exists a separate VMM for each instantiated VM. Alternatively, each VMM may be considered to be a component of its corresponding virtual machine since such VMM includes the hardware emulation components for the virtual machine. In such an alternative conception, for example, the conceptual layer described as virtual hardware platform118may be merged with and into VMM126such that virtual host bus adapter122is removed fromFIG. 1(i.e., since its functionality is effectuated by a host bus adapter emulator within VMM126).

Storage layer132maintains on-disk storage metadata134for facilitating the dynamic allocation of storage blocks136(sometimes referred to as disk blocks, disk sectors, or sectors) and other operations on storage system104. For example, storage layer132is configured to receive and/or execute space allocation requests for storage blocks136that can used to handle requests to write data to storage system104. In some embodiments, storage layer132uses storage metadata134for such tasks as remembering which storage blocks136are allocated and which storage blocks are free (e.g., bitmaps), or allowing quick random access to an arbitrary block in a particular file (e.g., b-trees).

Storage systems (e.g., storage system104) often use transactions to get atomic updates of on-disk data structures (e.g., metadata134, data blocks136). For example, an update operation on a bitmap data structure to indicate certain blocks are now taken and a write operation of the underlying blocks are performed atomically to ensure consistency of the storage system. Otherwise, should the storage system crash or fail mid-operation, the storage system (specifically the bitmap and underlying data blocks) would be left in an inconsistent state.

Isolation is another characteristic of storage systems, which ensures that concurrent (e.g., in parallel) execution of transactions results in a system state that would be obtained if the transactions were executed serially. Database systems have typically used data structures such as undo-redo logs to achieve isolation characteristics in relational database systems. However, because of the overhead incurred by undo-redo logs, file and storage systems have conventionally used redo-only logs to get fast transactions which cannot be aborted.

Accordingly, embodiments of the present disclosure provides a system for executing transactions that uses a versioned tuple cache to achieve fast, abortable transactions using a redo-only log. In one or more embodiments, storage system104includes a transaction manager140configured to maintains a plurality of data structures including a tuple cache142, a logical log144, a block cache146, and a physical log148for executing atomic, abortable transactions on data stored in storage system104.

In one or more embodiments, storage system104includes a transaction manager140configured to update an in-memory key-value store and also attach a transaction identifier to the tuple as a major key. Before a transaction is aborted, transaction manager140is configured to execute searches on the key-value store that ignores all tuples modified by un-committed transactions. Transaction manager140is further configured to use a hash table of committed transactions and a maximal committed transaction identifier to determine whether a particular transaction has been committed. Accordingly, embodiments of the present disclosure enable opportunistic locking to be performed because the cost of aborting transactions is low compared to other approaches.

In one or more embodiments, transaction manager140is configured to convert I/O commands into key-value pairs that are written into tuple cache142and logical log144as intentions to operate on data. In one embodiment, tuple cache142is a versioned key-value store configured to store values representing I/O operations with transaction identifiers as keys. In some embodiments, tuple cache142may be maintained in-memory for high-performance and low-latency of operations. Upon committing a transaction, transaction manager140is configured to retrieve entries in tuple cache142and logical log144to be “replayed” and actually perform the operations on the data, as described herein. From a software perspective, operations for initiating a transaction, writing intentions to operate, and committing the transaction are illustrated in the pseudo-code provided in Table 1 below.

In one embodiment, entries in logical log142include an operation specifying a particular I/O command, and one or more arguments specifying information needed to perform the I/O command. In one embodiment, entries in logical log142generally have the form of <transaction identifier>, <operation>, <argument(s)>, and may be variably-sized. Examples of I/O operations within logical log142are presented in Table 2 below. For example, logical log142may contain an entry indicating an insert operation for a <value> at a location <key> associated with the transaction identified by <txid>. In another example, logical log142may contain an entry indicating a delete operation for data stored at a location <key>, the operation being associated with the transaction identified by <txid>. In another example, logical log142may contain an entry specifying a space allocation (e.g., “alloc”) or de-allocation (e.g., “free”) operation for disk blocks.

In one embodiment, physical log148contains a real physical representation of the blocks on disk (e.g., data). In contrast to logical log144, physical log148has the property of idempotency such that operations in physical log148may be replayed repeatedly without changing the result beyond the intended state. Entries in physical log148may contain a transaction identifier, a physical log block number, actual data contents for the target block (e.g., to be written), and a logical log transaction identifier. The content of the target block may be arranged in a fixed size format (e.g., 4 kB, 8 kB). In one embodiment, entries in physical log148may have a form such as: <tx>, <plog-blkno>, <content of the block>, <llog-tx>.

FIG. 2is a flow diagram illustrating a method200for executing transactions, according to one embodiment of the present disclosure. While method200is described in conjunction with the system shown inFIG. 1, it should be recognized that other systems may be used to perform the described methods.

Method200begins at step202, where transaction manager140initializes a transaction on data stored in a storage device (e.g., storage system104). Unlike conventional transaction systems using redo-only logs, the transaction is abortable by transaction manager140, as described later. In some embodiments, transaction manager140initializes a transaction by generating a unique transaction identifier to be associated with any operations that are part of the new transaction. In one implementation, transaction manager140may initialize the transaction in response to a software call (e.g., txCreate( )).

After initializing the transaction, transaction manager140may receive one or more operations to be performed atomically as part of the transaction. For each operation, transaction manager140may, among other actions, insert into a versioned tuple cache142at least one key-value pair representing the operation. In some embodiments, the key-value pairs are indexed by a transaction identifier.

At step204, transaction manager140determines whether the received operation is a write operation. If so, at step206, responsive to a request to write data to storage system104, transaction manager140writes an entry containing an insert operation and associated arguments (i.e., <insOp, arg>) into logical log144. At step208, transaction manager140inserts the insert operation into versioned tuple cache142. In some embodiments, transaction manager140inserts a key-value pair where the key is the transaction identifier of the transaction and the value contains the insert operation and its associated arguments.

At step210, transaction manager140determines whether the received operation is a delete operation. If so, at step212, responsive to a request to delete data from storage system104, transaction manager140writes a delete operation into logical log144. In one implementation, transaction manager140writes an entry containing a delete operation and an argument indicating the location of the delete to be deleted (i.e., <delOp, arg>) into logical log144. At step214, transaction manager140inserts the delete operation into versioned tuple cache142. In some embodiments, transaction manager140inserts a key-value pair where the key is the transaction identifier of the transaction and the value contains the delete operation and its associated argument(s). The delete operation represents a negative record indicating the deleted data no longer exists, without deleting underlying blocks from storage. That is, if tuple cache142is later queried for that data before the changes have been committed, tuple cache142can still report that the data has been deleted. Should the transaction be aborted, the negative record in tuple cache142can be discarded and other concurrent transactions can still reach that data, thereby achieving isolation storage characteristics.

At step216, transaction manager140determines whether the received operation is a lookup operation. If so, at step218, responsive to a request to look up data from storage system104, transaction manager140first queries tuple cache142for the data. If found, at step220, transaction manager140retrieves data from tuple cache142and returns the data in a response. Transaction manager140queries tuple cache142for any tuples that match the (logical) address of the data and that match the transaction identifier associated with the current transaction. In some embodiments, any lookup within a given transaction searches for data within tuples associated with the given transaction in tuple cache142, ignoring tuples of other transactions, thereby providing isolation characteristic to the described technique. For example, a lookup for data block A in transaction X would ignore a tuple, which indicates the data block A has been deleted (i.e., negative record), stored in tuple cache142for a concurrent transaction Y. In effect, any lookup operation on tuple cache142will ignore all tuples modified by uncommitted transaction(s) of other thread(s).

Otherwise, at step222, responsive to determining that the data is not found in the versioned tuple cache, transaction manager140queries block cache146for the data. In some embodiments, transaction manager140subsequently inserts an entry into tuple cache142with the data retrieved from block cache146, so that tuple cache142can be used to retrieve that same data in subsequent lookup operations of the transaction.

At step224, transaction manager140determines whether the received operation is a commit operation. If so, transaction manager140retrieve the key-value pairs from the versioned tuple cache using the transaction identifier, and applies the operations of the key-value pairs to block cache146. In some embodiments, transaction manager140applies the operations of the key-value pairs to shadow pages of block cache146, and applies changes to the shadow pages of block cache146if no conflicts. The commit operation is described in further detail in conjunction withFIG. 3.

At step226, transaction manager140determines whether the received operation is an abort operation on the current transaction. If so, at step228, responsive to a request to abort the transaction, transaction manager140discards all key-value pairs associated with the transaction from versioned tuple cache142based on the transaction identifier.

FIG. 3is a flow diagram illustrating a method300for committing a transaction, according to one embodiment of the present disclosure. While method300is described in conjunction with the system shown inFIG. 1, it should be recognized that other systems may be used to perform the described methods.

Method300begins at step302, where transaction manager140locks block cache146. In some embodiments, transaction manager140locks the entirety of block cache146during method300. In other embodiments, transaction manager140locks a portion of block cache146that will be affected by tuple operations, for example, according to a “preflight” check. In such an embodiment, transaction manager140scans the operations of the overall transaction and uses a hash table to find which portions of block cache146need to be locked.

In the described method, transaction manager140generally attempts to commit every tuple in tuple cache142associated with a given transaction in a loop. As such, in a loop condition, at step304, transaction manager140determines whether there are more tuples of the particular transaction to be committed in tuple cache142. If so, at step306, transaction manager140retrieves a next tuple from tuple cache142of the particular transaction. In one implementation, transaction manager140can retrieve a next tuple using the transaction identifier associated with the transaction to be committed.

At step308, transaction manager140determines whether the operation in the retrieved tuple conflicts with the state of block cache146. The operation in the retrieved tuple is part of a current transaction might conflict with a prior and/or concurrent transaction. For example, the operation in the retrieved tuple may be a delete operation on a data block that has already been deleted by a prior transaction. In some embodiments, particularly embodiments where the transaction identifiers are generated as monotonically increasing, transaction manager140determines whether the current transaction conflicts with prior committed transactions according to a comparison of the transaction identifier. That is, transaction manager140can determine if the current transaction having a lower transaction identifier conflicts with a prior committed transaction having a higher transaction identifier. Such conflicts can arise in situations where one thread has a later-started but earlier-committed transaction than another concurrent thread. If so, at step310, responsive to detecting a conflict, transaction manager140discards all shadow pages of block cache146. Use of shadow pages are described further below. Subsequently, transaction manager140may reach an error state and abort the current transaction.

At step312, responsive to determining the operation in the retrieved tuple does not conflict with the state of block cache146, transaction manager140applies the operation to a shadow page of block cache146. Shadow pages provide a copy-on-write technique where, instead of applying the operation to a target page in block cache146itself, a shadow page corresponding to that target page is allocated and the operation is applied to the shadow page. For example, responsive to an update operation on block A, transaction manager140allocates a shadow page A′ and applies the update to shadow page A′. Use of the shadow pages permit the transaction manager140to discard any pending changes to block cache146in case of conflict or error (as in step310above) by simply discarding the shadow pages. At step312, transaction manager140removes the tuple from the tuple cache, and proceeds to repeat steps304to314.

Referring back to step304, responsive to determining that there are no more tuples of the particular transaction to be committed in tuple cache142(and assuming no conflict has been detected), transaction manager140applies all shadow pages to block cache146itself. Transaction manager140may atomically swap all those blocks of the shadow pages with the corresponding blocks in block cache146. That is, transaction manager140applies physical transactions onto the underlying data (e.g., B-tree data structure) itself. At such point, the particular transaction may be considered successfully committed and all operations of the transaction have been applied and persisted to storage system104.

There may be cases where storage system140may suffer a failure or other interruption to its operations. As mentioned above, in such cases, storage system140is configured to bootstrap and recover from such failures using tuple cache142and logical log144.FIG. 4is a flow diagram illustrating a method400for bootstrapping transaction manager140, according to one embodiment of the present disclosure. While method400is described in conjunction with the system shown inFIG. 1, it should be recognized that other systems may be used to perform the described methods.

Method400begins at step402, where transaction manager140replays every valid physical transaction found within physical log148into tuple cache142. In this context, a transaction is characterized as valid by having an entry with a “BEGIN” instruction and corresponding entry having a “COMMIT” instruction denoting the end of the transaction. An example physical log148is provided in Table 3 below. In this example, transaction manager140finds the BEGIN instruction having the transaction identifier “5” (i.e., “log_tx5”) and a corresponding COMMIT instruction having the same transaction identifier “5”. As such, transaction manager140determines that the transaction “5” is valid, and replays that transaction into tuple cache142by updating logical block10with content A. Further in this example, transaction manager140determines the second transaction having the transaction identifier “6” is also valid, and replays that transaction6by writing logical blog15with content B in tuple cache142. However, in the case of the transaction “7”, transaction manager140determines that this transaction is not valid because while there is a BEGIN instruction, there is no corresponding COMMIT instruction found in physical log148. Such a scenario may arise in cases where the system is interrupted or has failed in the middle of writing the transaction7to physical log148.

At step404, transaction manager140determines a latest transaction identifier found within physical log148and designates this transaction identifier the “current” transaction identifier. In some embodiments, transaction manager140keeps track of the latest transaction identifier encountered while iterating through log entries in physical log148during course of replaying transactions in step402. In the above example, the latest transaction identifier is transaction “6.” This state represents that transaction manager140has successfully replayed every valid transaction up to transaction6.

At step406, transaction manager140attempts to reads a next log entry from logical log144having a “next” transaction identifier that exceeds the current transaction identifier. Continuing the above example scenario, at the outset of the bootstrap procedure, logical log142contains log entries for transactions identified3to10. Transaction manager140attempts to read log entries in logical log144associated with transaction identifier “7” (i.e., 6+1). In this way, transaction manager140does not have to replay logical log entries for transactions3,4,5, and6.

At step408, transaction manager140determines whether a corresponding log entry having that next transaction identifier can be found within logical log144. If none found, transaction manager140may deem the bootstrap operation complete, and exit.

At step410, responsive to finding a corresponding log entry in logical log144, transaction manager140replays the operation contained in the corresponding log entry in logical log144into tuple cache142. For example, transaction manager140replays the operation by inserting a key-value pair into tuple cache142that represents the operation, as described in method200. At step412, transaction manager140determines whether the operation was successfully replayed. If so, at step414, transaction manager140increments the current transaction identifier and iterates to step406to read a next log entry from logical log144, if needed, and continue method400.