# US 2014/0156618 A1 · Distributed, Transactional Key-Value Store > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 2014/0156618 A1 - Document ID: US20140156618A1 - Status: Published application - Kind: A1 - Application number: 13/692,777 - Filed: 2012-12-03 - Published: 2014-06-05 - Earliest claimed: 2012-12-03 - Assignees: VMware, Inc. - Applicants: Vmware, Inc. - Inventors: Luca Castellano - Web page: https://patentgrep.com/patent/US20140156618A1 ## CPC - G06F 16/2358: {Change logging, detection, and notification (replication G06F16/27)} - G06F 16/13: File access structures, e.g. distributed indices (arrangements of input from, or output to, record carriers G06F3/06) - G06F 16/148: {File search processing} - G06F 16/1756: {based on delta files} - G06F 16/1865: {Transactional file systems} - G06F 16/2272: {Management thereof} - G06F 16/2308: {Concurrency control (transaction processing G06F9/466)} - G06F 16/2329: {using versioning} - G06F 16/2365: {Ensuring data consistency and integrity} - G06F 16/28: Databases characterised by their database models, e.g. relational or object models - G06F 16/128: {Details of file system snapshots on the file-level, e.g. snapshot creation, administration, deletion (error detection or correction of the data by redundancy in operations or in hardware G06F11/14, G06F11/16)} - G06F 16/185: Hierarchical storage management [HSM] systems, e.g. file migration or policies thereof (details of archiving G06F16/11) - G06F 2201/84: Using snapshots, i.e. a logical point-in-time copy of the data - Y10S 707/99933: Query processing, i.e. searching - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) - Y10S: TECHNICAL SUBJECTS COVERED BY FORMER USPC CROSS-REFERENCE ART COLLECTIONS [XRACs] AND DIGESTS ## Abstract In one embodiment, a system for implementing a distributed, transactional key-value store is provided. The system includes a set of nodes, where each node is communicatively coupled with one or more storage devices storing a set of data log files, and where each data log file including key-value pairs for a key namespace. Each node is configured to execute, using a transaction log file specific to the node, transactions for modifying or retrieving key-value pairs in the set of data log files, where the transaction log file includes state information for the transactions. The transactions are executed in a manner that ensures the atomicity and durability of each transaction. ## Claims ### Claim 1 A system for implementing a distributed, transactional key-value store, the system comprising: a set of nodes, wherein each node is communicatively coupled with one or more storage devices storing a set of data log files, each data log file including key-value pairs for a key namespace, wherein each node is configured to execute, using a transaction log file specific to the node, transactions for modifying or retrieving key-value pairs in the set of data log files, the transaction log file including state information for the transactions, and wherein the transactions are executed in a manner that ensures atomicity and durability of each transaction. ### Claim 2 (depends on 1) The system of claim 1 wherein the transaction log file specific to each node is stored on a local storage device of the node. ### Claim 3 (depends on 1) The system of claim 1 wherein the transaction log file specific to each node indicates whether each transaction has been initiated, committed, or aborted by the node. ### Claim 4 (depends on 1) The system of claim 1 wherein the transaction log file specific to each node is readable and writable by the node, but is only readable by other nodes in the set of nodes. ### Claim 5 (depends on 1) The system of claim 1 wherein each node is configured to execute the transactions in a manner that further ensures per-node-snapshot isolation of each transaction. ### Claim 6 (depends on 1) The system of claim 1 wherein each node is further configured to search the set of data log files in response to a search operation that includes a search expression and a target key namespace, the searching comprising: identifying a data log file in the set of data log files that includes key-value pairs for the target key namespace; and searching the data log file for key-value pairs that satisfy the search expression. ### Claim 7 (depends on 1) The system of claim 1 wherein each node is configured to execute a transaction that modifies one or more key-value pairs in the set of data log files by: determining a data log snapshot, wherein the data log snapshot identifies one or more data log files in the set data log files that the node will access due to the transaction, and wherein the data log snapshot includes, for each of the one or more data log files, a version number and size; and determining one or more key-value subsets, wherein each key-value subset includes key-value pairs from an associated data log file in the one or more data log files that the node will attempt to modify due to the transaction. ### Claim 8 (depends on 7) The system of claim 7 wherein the node is configured to execute the transaction by further: determining a transaction identifier for the transaction; writing a first transaction log entry to the transaction log file specific to the node, the first transaction log entry including the transaction identifier and indicating that the modifier transaction has been initiated; and for each key-value subset in the one or more key-value subsets, attempting to append one or more data log entries to the key-value subset's associated data log file, each data log entry identifying a modification to a key-value pair in the key-value subset's associated data log file. ### Claim 9 (depends on 8) The system of claim 8 wherein attempting to append the one or more data log entries to the key-value subset's associated data log file comprises: retrieving the version number of the key-value subset's associated data log file from the data log snapshot; and invoking an append operation that takes the version number as an input parameter, wherein the append operation succeeds if the version number matches a current version number of the key-value subset's associated data log file, and wherein the append operation fails if the version number does not match the current version number. ### Claim 10 (depends on 9) The system of claim 9 wherein the node is configured to execute the transaction by further: if the append operation succeeds for each key-value subset in the one or more key-value subsets, writing a second transaction log entry to the transaction log file specific to the node, the second transaction log entry including the transaction identifier and indicating that the modifier transaction has been committed. ### Claim 11 (depends on 9) The system of claim 9 wherein the node is configured to execute the transaction by further: if the append operation fails for any key-value subset in the one or more key-value subsets, writing a second transaction log entry to the transaction log file specific to the node, the second transaction log entry including the transaction identifier and indicating that the modifier transaction has been aborted. ### Claim 12 (depends on 9) The system of claim 9 wherein the append operation is implemented by a distributed file system (DFS) component running on the node, and wherein the append operation is guaranteed by the distributed file system to be atomic. ### Claim 13 (depends on 9) The system of claim 9 wherein attempting to append the one or more data log entries to the key-value subset's associated data log file further comprises: if the append operation fails: retrieving the length of the key-value subset's associated data log file from the data log snapshot; reading the key-value subset's associated data log file backwards from the end of the file to the retrieved length; as the key-value subset's associated data log file is read, determining whether any keys in the key-value subset's associated data log file match keys in the key-value subset; if a match is found, determining that the transaction should be aborted; and if a match is not found: updating the data log snapshot to include a current version number and a current length of the key-value subset's associated data log file; and re-invoking the append operation by passing in the current version number. ### Claim 14 (depends on 1) The system of claim 1 wherein each node is configured to execute a transaction that retrieves one or more key-value pairs in the set of data log files by: for each key-value pair in the one or more key-value pairs: identifying a data log file in the set of data log files that includes the key-value pair; saving a length of the data log file; and processing the data log file by: determining a data log entry in the data log file that represents the most recent modification of the key-value pair, the determining being based on the saved length of the data log file; identifying a source node and a source transaction associated with the data log entry; retrieving a transaction log file specific to the source node; determining a transaction log entry in the transaction log file specific to the source node that represents a current state of the source transaction; if the transaction log entry indicates that the source transaction has been committed, returning the key-value pair as identified in the data log entry; and if the transaction log entry does not indicate that the source transaction has been committed: adjusting the saved length of the data log file to skip the data log entry; and re-processing the data log file based on the adjusted saved length. ### Claim 15 (depends on 14) The system of claim 14 wherein the node is configured to execute the transaction by further: prior to determining the transaction log entry, retrieving a length of the transaction log file from a progressive transaction log snapshot, the progressive transaction log snapshot identifying transaction log files accessed by the node during the transaction and their corresponding lengths at the time of access, wherein determining the transaction log entry is based on the retrieved length. ### Claim 16 (depends on 1) The system of claim 1 wherein each data log file and transaction log file is compacted at predetermined time intervals or upon reaching a predetermined size. ### Claim 17 A method performed by a node in a set of nodes, the node being communicatively coupled with one or more storage devices storing a set of data log files, each data log file including key-value pairs for a key namespace, the method comprising: executing, by the node using a transaction log file that is specific to the node, transactions for modifying or retrieving key-value pairs in the set of data log files, the transaction log file including state information for the transactions, wherein the transactions are executed in a manner that ensures atomicity and durability of each transaction. ### Claim 18 (depends on 17) The method of claim 17 wherein the transactions are executed in a manner that further ensures per-node-snapshot isolation of each transaction. ### Claim 19 A non-transitory computer readable medium embodying computer software, the computer software being executable by a node in a set of nodes, the node being communicatively coupled with one or more storage devices storing a set of data log files, each data log file including key-value pairs for a key namespace, the computer software causing the node to perform a method comprising: executing, using a transaction log file that is specific to the node, transactions for modifying or retrieving key-value pairs in the set of data log files, the transaction log file including state information for the transactions, wherein the transactions are executed in a manner that ensures atomicity and durability of each transaction. ### Claim 20 (depends on 19) The non-transitory computer readable medium of claim 19 wherein the transactions are executed in a manner that further ensures per-node-snapshot isolation of each transaction.