BACKGROUND

Write-optimized databases (e.g., Cassandra, LevelDB, RocksDB, TokuDB, Big Table, Hbase, etc.) are a type of database capable of performing fast updates to entries (e.g., records) in the database. For example, write-optimized databases can work by buffering updates to entries in the database to a first portion (e.g., fast, temporary, etc.) of a data structure of the database (e.g., a data structure may be the format (e.g., table, array, record, tree (e.g., Bε-tree, LSM-tree, etc.), etc.) in which data is organized and stored in the database), and then later merging the buffered updates (e.g., in batches, individually, etc.) into a main data structure of the database. Such write-optimized databases may be able to perform random write operations more quickly than regular B+-tree operations.

One of the more common operations performed in a database to update (e.g., modify) an entry is a read-modify-write, where a value of an entry in the database is read, the value is modified (e.g., perform an operation on the value), and the modified value is written back to the entry. However, such a read-modify-write (i.e., query-modify-insert) operation includes a read operation for reading an entry from the database, which may not be optimized and therefore the overall operation may not be performed quickly. In addition, when a page corresponding to a number of entries stored in memory is written out while only very few entries in the page are dirty, a large portion of disk write bandwidth may be consumed unnecessarily (e.g., referred to as Write Amplification), thereby decreasing system performance. Updates in write-optimized databases may be designed to be “blind-updates” where no read is performed in the update, and those updates are instead later merged to the rest of the key-value store. Accordingly, data structures in write-optimized databases may support an update procedure that may be referred to as a merge update (also referred to as a message update or upsert) where an entry is modified without needing to perform a read operation at the time up the update.

For example, a database may be implemented as a key-value store where an entry in the database is stored as a key-value pair. The key portion of the entry may include a key (e.g., an identifier, type information, etc.) associated with the entry. The value portion of the entry may be the actual data accessed using the key. The database may be configured so that different operations can be performed on the database using the key. For example, operations include querying for a value associated with a key, inserting (e.g., replacing) a value associated with a key, and deleting a value associated with a key. The database may include a main data structure or portion that stores the key-value pairs for the database.

The database may further support performing a merge update to entries in the database. For example, to perform a merge update to a key-value pair a message is created in a portion of the database that may be separate from the main data structure. The message includes the same key as the key-value pair. However, the message may not include a value in the same way that a key-value pair stored in the database includes a value corresponding to actual data accessed using the key. Rather, the message includes a payload indicating a delta (e.g., an operation or function such as delete, multiply, sum, replace, etc.) to apply to a value of a key-value pair with the same key as the message. For example, if a key-value pair includes a key of “A” and a value of “10”, and a message includes the same key of “A” and a delta of “add 3”, then the message would indicate to add “3” to the value “10” resulting in an updated value “13” being associated with key “A” in the database.

However, when the message is created, the delta indicated in the payload of the message may not be immediately applied to the key-value pair with the same key. Rather, the message can be written to the database without querying or reading the key-value pair. Therefore, the result of applying the delta to the value in the key-value pair may not be known at the time the message is created. In a write-optimized database, this can reduce the latency associated with a read-modify-write operation, by removing the need to perform the read in order to update an entry in the database. The delta in the message may be applied at a later time to the value of the key-value pair with the same key as the message. Application of the delta of the message to the value may be referred to as a merge or compaction of the message with the key-value pair. For example, many messages may be created with the same key and/or different keys for application to the same and/or different key-value pairs, respectively. The messages may be merged with the key-value pairs (e.g., individually or in batches) in any suitable order (e.g., last in first out, first in first out, etc.). In some cases, the order of operations in which messages are merged may matter, and so messages are merged with the key-value pairs in a particular order (e.g., a multiplication operation may need to be performed before an addition operation). Further, messages may be merged with each other into a single message (e.g., two multiplication operations may be merged into a single multiplication operation), which may be later merged with another message or the key-value pair. The merging of messages may occur along a path or pipeline for processing messages.

If a query operation is performed with respect to a key for which messages are stored in the database that are not yet merged with the corresponding key-value pair, the query operation may identify all the messages with the key, and apply the deltas of the messages to the key-value pair and return the resulting value. In a query operation, the delta message remains in the database, unlike a compaction, where the delta message is removed from the database after it is merged with the corresponding key-value pair.

Accordingly, write-optimized databases implementing merge update procedures may be used to implement efficient databases. Therefore, techniques for improving such write-optimized databases may be desirable.

