Reducing requests using probabilistic data structures

Techniques are disclosed relating to providing and using probabilistic data structures to at least reduce requests between database nodes. In various embodiments, a first database node processes a database transaction that involves writing a set of database records to an in-memory cache of the first database node. As part of processing the database transaction, the first database node may insert, in a set of probabilistic data structures, a set of database keys that correspond to the set of database records. The first database node may send, to a second database node, the set of probabilistic data structures to enable the second database node to determine whether to request, from the first database node, a database record associated with a database key.

BACKGROUND

Technical Field

This disclosure relates generally to database systems and, more specifically, to reducing calls/requests between database nodes using probabilistic data structures.

Description of the Related Art

Modern database systems routinely implement management systems that enable users to store a collection of information in an organized manner that can be efficiently accessed and manipulated. In some cases, these management systems maintain a log-structured merge-tree (LSM tree) having multiple levels that each store information as key-value pairs. An LSM tree usually includes two high-level components: an in-memory cache and a persistent storage. In operation, a database system initially writes database records into the in-memory cache before later flushing them to the persistent storage.

The term “configured to” is not intended to mean “configurable to.” An unprogrammed FPGA, for example, would not be considered to be “configured to” perform some specific function, although it may be “configurable to” perform that function and may be “configured to” perform the function after programming.

As used herein, the terms “first,” “second,” etc. are used as labels for nouns that they precede, and do not imply any type of ordering (e.g., spatial, temporal, logical, etc.) unless specifically stated. For example, in a processor having eight processing cores, the terms “first” and “second” processing cores can be used to refer to any two of the eight processing cores. In other words, the first and second processing cores are not limited to processing cores 0 and 1, for example.

DETAILED DESCRIPTION

In some implementations, a database system maintaining a LSM tree writes records into an in-memory cache of the LSM tree before writing those records into a persistent storage that is associated with the LSM tree. In some approaches, the database system includes a single database node that is responsible for writing records into the LSM tree. In other approaches, the database system includes multiple database nodes that write records into the LSM tree while also reading records from the LSM tree. These database nodes may share a common persistent storage, but each have their own in-memory cache. In this scenario, records that are written by a database node into its in-memory cache, however, are not visible to other database nodes until those records are flushed to the common persistent storage. The present inventors have recognized that this arrangements causes certain inefficiencies. Consider a first database node that is processing a transaction that involves accessing the latest version of a certain record. This record may be stored in the in-memory cache of a second database node and thus is not visible to the first database node. As a result, the first database node has to issue a request to the second database node in order to determine whether the second database node has the latest version of that record.

In many cases, the size of the in-memory cache of a database node can be quite small (e.g., 2 GB or 10 GB) and as such, can store only a limited number of records at any point in time. As a result, even though many record requests are generated by database nodes, many if not most of these requests do not result in a record being return. Consequently, although the requested record is often not present in the in-memory cache of the second database node, the first database node still has to make a request to the second database node to see if the record is there. The present inventors have recognized that this slows down the overall operation of the database system because the database nodes spend an extensive amount of time issuing record requests to one another, even though these requests often do not result in a record being returned. This disclosure addresses this technical problem of too many resources being consumed as a result of too many requests being sent between database nodes for records that are usually not present at the other database node.

This disclosure describes techniques for implementing probabilistic data structures that enable database nodes to determine whether to request a database record from another database node. As used herein, the term “probabilistic data structure” refers to a data structure that stores information indicating that a particular item either does not exist or might exist at a particular location within a system. For example, a probabilistic data structure can store information that indicates that a database record, for a particular database key, does not exist or might exist at an in-memory cache of a certain database node. Bloom filters, cuckoo filters, hyperloglog-related structures, and surf tries are examples of probabilistic data structures.

In various embodiments that are described below, a system includes multiple database nodes that are capable of writing database records to their own local in-memory cache before flushing those database records to a persistent storage shared by those database nodes. When writing a database record into an in-memory cache, in various embodiments, a database node inserts a database key of the database record into a probabilistic data structure. As used herein, the phrase “inserting a database key into a probabilistic data structure” broadly refers to causing a modification to information in the probabilistic data structure based on the database key. The database key itself does not have to be stored in the probabilistic data structure. For example, a set of hash functions may be applied to the database key to derive a set of hash values. Those hash values can be used to set bits in the probabilistic data structure.

To insert a database key into a probabilistic data structure, in various embodiments, a database node applies a set of hash functions to derive a set of corresponding hash values. One of the hash values may be used to select a portion or “cache line” within the probabilistic data structure. The remaining hash values may be used to set bits within the cache line to represent the database key. During operation, a database node may insert various database keys into one or more probabilistic data structures. In some embodiments, the database node inserts database keys into a probabilistic data structure until a threshold number of keys have been inserted into the probabilistic data structure. (This threshold may correspond to some maximum size for the data structure; this could be a system design choice or a configuration setting in various embodiments.) The database node may then create another probabilistic data structure and begin inserting database keys into it. As a result, in various cases, a database node may create a stack of probabilistic data structures, each being associated with a different set of database keys.

The database node may provide probabilistic data structures from the stack to a second database node. In some embodiments, the database node provides probabilistic data structures from the stack as part of a response to a request from the second database node for a database record associated with a specified database key. In some embodiments, the database node may provide, to that second database node, only those probabilistic data structures that been created or changed since the second database node last received probabilistic data structures. For example, when the second database node initially communicates with the first database node, the first database node may provide all the probabilistic data structures from its stack. Afterwards, the first database node may add a new probabilistic data structure to the stack. When the second database nodes sends a request to the first database node for a database record, the first database node may provide, as part of a response to the request, the new probabilistic data structure, but not other ones from the stack.

A database node that receives probabilistic data structures may use those probabilistic data structures to determine whether to request a database record from another database node (e.g., the owner of those probabilistic data structures). During operation, a database node may receive a request to process a database transaction that involves accessing a database record for a specified database key. The specified database key, however, may fall within a key space that is managed by a second database node. As such, the former database node (a first database node) may check probabilistic data structures associated with the second database node to determine if it should request a database record from the second database node. In order to check a probabilistic data structure, in some embodiments, the first database node applies, to the specified database key, the same set of hash functions that was used by the second database node for inserting database keys into that probabilistic data structure. If the hash values derived for the specified database key match bits set in the probabilistic data structure, then the first database node may determine that a database record might exist at the second database node for the specified database key; otherwise, the first database node determines that there is no database record for that key at the second database node.

These techniques may be advantageous over prior approaches as these techniques allow for database nodes to communicate in a more effective manner that involves reducing the number of database record requests sent between database nodes. In prior approaches, a database node would issue a request to another database node for database record if the database key for that record fell within the key space of that other database node. By using probabilistic data structures discussed in the present disclosure, a database node can determine whether to issue a request to another database node for a database record. If a probabilistic data structure does not have information set that indicates a particular database key, then the database node knows that a database record for that particular database key does not exist at the other database node and thus does not have to make a request to that other database node.

These techniques may also provide additional advantages. In various cases, a database system may have multiple processors that are interacting with cache lines that may correspond to probabilistic data structures. When inserting a database key into a probabilistic data structure in a non-single-cache-line approach, multiple hash values of that key may map to different cache lines. Updating the bits of probabilistic data structures may happen by atomic compare and swap operations that need the processor to take ownership of a cache line, preventing other processors from updating the cache line in the meantime. As a result, when the key hash values map to multiple cache lines, the processor has to fight for ownership of those cache lines a greater number of times in a concurrent system. This can cause more processor stalls (waiting for ownership of cache line) and reduce the insert performance of keys into probabilistic data structures. In a single-cache-line approach, all the key hash values map to the same hardware cache line. This allows for a processor to seek ownership of only a single cache line instead of multiple cache liens. Thus, the processor may spend less time waiting for the ability to insert a database key. An exemplary application of these techniques will now be discussed, starting with reference toFIG.1.

Turning now toFIG.1, a block diagram of a system100is shown. System100includes a set of components that may be implemented via hardware or a combination of hardware and software routines. In the illustrated embodiment, system100includes a database110and a set of database nodes120A-C. As further illustrated, database nodes120A-C each include an in-memory cache130(which stores respective database records135A-C) and a set of probabilistic data structures140. In some embodiments, system100may be implemented differently than illustrated. For example, system100may include more or less database nodes120.

System100, in various embodiments, implements a platform service that allows users of that service to develop, run, and manage applications. As an example, system100may be a multi-tenant system that provides various functionality to a plurality of users/tenants hosted by the multi-tenant system. Accordingly, system100may execute software routines from various, different users (e.g., providers and tenants of system100) as well as provide code, web pages, and other data to users, databases (e.g., database110), and other entities associated with system100. As depicted, system100includes database nodes120A-C that interact with database110to store and access data for users that are associated with system100.

Database110, in various embodiments, is a collection of information that is organized in a manner that allows for access, storage, and manipulation of that information. Accordingly, database110may include supporting software that allows for database nodes120to carry out operations (e.g., accessing, storing, etc.) on information in database110. As depicted, database110is shared between database nodes120A-C such that database records135that are written by one database node120are accessible by other database nodes120. In some embodiments, database110is implemented by a single or multiple storage devices that are connected together on a network (e.g., a storage attached network (SAN)) and are configured to redundantly store information in order to prevent data loss. These storage devices may store data persistently and thus database110may serve as a persistent storage.

In various embodiments, database110implements a part of a log-structured merge-tree (LSM tree) having multiple levels of database records135. As previously mentioned, an LSM tree may include two high-level portions: an in-memory portion and an on-disk portion. One or more levels of the LSM tree may comprise database records135that are written to an in-memory cache130. The remaining levels of the LSM tree may comprise database records135that are written to database110. Accordingly, in-memory caches130A-C may facilitate the in-memory portion of an LSM tree while database110facilitates the on-disk portion of that LSM tree.

Database nodes120, in various embodiments, are hardware, software, or a combination thereof capable of providing database services, such as data storage, data retrieval, and data manipulation. These database services may be provided to other components within system100or to components external to system100. As shown, database node120B receives a database transaction request105—this request might be received from an application server (not shown) that is attempting to access a set of database records135. As an example, database transaction request105may specify an SQL SELECT command that selects one or more rows from one or more database tables. The contents of a row may be defined in a database record135and thus a database node120may return one or more database records135that correspond to the selected one or more table rows. In some cases, a database transaction request105may instruct a database node120to write one or more database records135for the LSM tree. A database node120, in various embodiments, initially writes database records135to its in-memory cache130before flushing those database records to database110.

In-memory caches130, in various embodiments, are buffers that store data in memory (e.g., random access memory (RAM)) of database nodes120. HBase™ Memstore may be an example of an in-memory cache130. As mentioned, a database node120may initially write a database record135(e.g., in the form of a key-value pair) in its in-memory cache130. In some cases, the latest/newest version of a row in a database table may be found in a database record135that is stored in an in-memory cache130. Database records135, however, that are written to a database node120's in-memory cache130are not visible to other database nodes120in various embodiments. That is, those other database nodes120do not know, without asking, what information is stored within the in-memory cache130of that database node120. In order to determine whether an in-memory cache130is storing a database record135associated with a particular key, in some cases, a database node120may issue a database record request122to the database node120of the in-memory cache130. Such a database record request122may include the particular key and the database node120may return a database record135if there is one that corresponds to the particular key.

In many instances, one database node120may return a database record response124to another database node120where that response does not include a database record135. This may be because, in various embodiments, in-memory cache130is relatively small in size and thus the chance of a database record135corresponding to a particular key being in in-memory cache130may be relatively low. Accordingly, in various embodiments, a database node120uses probabilistic data structure140to reduce the amount of database record requests122that it issues to another database node120that provided those particular probabilistic data structure140.

Probabilistic data structures140, in various embodiments, are data structures that store information that is indicative of a probability that a database record135exists in an in-memory cache130for a corresponding database key. As mentioned, a database node120can receive a database transaction request105that may involve writing one or more database records135to its in-memory cache130. When writing a database record135to its in-memory cache130, in some embodiments, the database node120inserts a database key corresponding to the database record135into a probabilistic data structure140. To insert the database key into a probabilistic data structure140, in various embodiments, the database node120performs one or more hash functions on the database key to derive a set of hash values. These hash values may be used to select a portion of the probabilistic data structure140and to set bits of information within the portion.

A database node120that receives a probabilistic data structure140may perform the same one or more hash functions on a certain database key to determine if the appropriate bits have been set for that database key. If the appropriate bits have been set for that database key, then the database node120may determine that a database record135for the database key may exist at the in-memory cache130of the database node120that provided the probabilistic data structure140. If the appropriate bits have not been set for that database key, then the database node120may determine that a database record135for the database key does not exist at the in-memory cache130of that other database node120. If a database record135might exist, in various embodiments, the database node120sends a database record request122to the other database node120for the potential database record135.

Turning now toFIG.2A, a block diagram of an example probabilistic data structure140is shown. In the illustrated embodiment, probabilistic data structure140includes a cache line structure210, a key range220, a number of keys value230, an active transaction count240, an oldest transaction commit number250, a latest transaction commit number260, a state270, and an identifier value275. In some embodiments, probabilistic data structure140may be implemented differently than illustrated. As an example, probabilistic data structure140may include an identifier value. When one database node120purges a probabilistic data structure140, it may provide the identifier value of that probabilistic data structure140to another database node120so that the other database node120may purge its own copy of that probabilistic data structure140.

Cache line structure210, in various embodiments, is a data structure capable of storing information that indicates, for a database key, one of two data points: 1) that a database record for that database key is not stored at an in-memory cache130associated with probabilistic data structure140or 2) a database record for that database key might be stored at that in-memory cache130. In various embodiments, cache line structure210includes a plurality of cache lines, each of which may be series of bits that can be set based on database keys that are inserted into cache line structure210. Based on what bits have been set in a particular cache line, a database node120may determine whether a database record for a particular database key may be stored at another database node120's in-memory cache130. An example of cache line structure210is discussed in more detail with respect toFIG.2B.

Key range220, in various embodiments, is a set of data values that define the range of database keys that have been inserted into probabilistic data structure140. Key range220may be used by a database node120to determine whether to check probabilistic data structure140to learn whether there might be a database record135at another database node120for a certain database key. Consider an example in which database node120B receives three probabilistic data structures140from database node120A. Database node120B may desire to determine if there is a database record135in in-memory cache130A for a particular database key identified in a database transaction being processed by database node120B. Accordingly, database node120B may check key range220for each of the three probabilistic data structures140in order to determine if the particular database key falls within key range220. This may allow database node120B to save processing resources and time by not checking the cache line structure210of a probabilistic data structure140if key range220does not include the particular database key. In some embodiments, multiple probabilistic data structures140may have overlapping key ranges220.

Number of keys value230, in various embodiments, is a data value that is indicative of the number of database keys that have been inserted into probabilistic data structure140. In some cases, number of keys value230may approximate the number of database keys that have been inserted. This may result from value230being incremented without any synchronization and thus some increments might be lost due to no synchronization. In various embodiments, probabilistic data structure140is capped after a specified number of database keys have been inserted. By capping the number of database keys that can be inserted, the false positive rate (i.e., the rate at which probabilistic data structure140indicates that a database record135is at an in-memory cache130, but that database record is not actually there—hence, the database record135“may” be at that in-memory cache130) for probabilistic data structure140may be kept at a target rate (e.g., 1%) since the insertion of a database key can incrementally increase the false positive rate. As such, number of keys value230may be used to determine whether the specified number of database keys have been inserted. After number of keys value230identifies a value that matches or exceeds the specified number of database keys, database node120may prevent additional database keys from being inserted and may generate another probabilistic data structure140for database key insertions.

Active transaction count240, in various embodiments, is a data value that is indicative of the number of transactions that are each still active after inserting at least one database key into probabilistic data structure140. For example, a database node120may receive a database transaction request105to perform a database transaction. As part of processing that database transaction, the database node120may insert a database key into probabilistic data structure140. In response to inserting the database key, in various embodiments, the database node120increments active transaction count240. Continuing the example, the database node120may receive another database transaction request105to perform a second database transaction. As part of processing the second database transaction, the database node120may insert a database key into probabilistic data structure140. In response to inserting the database key, the database node120may increment active transaction count240to indicate two active transactions that have inserted at least one key into probabilistic data structure140. In response to committing the first database transaction, in various embodiments, the database node120then decrements active transaction count240. The database node120may again decrement active transaction count240when the second database transaction commits. In various embodiments, a database transaction can be committed in which a database node120acknowledges that the database transaction is complete. As a result of committing the transaction, the database records135associated with the committed transaction may become available to other database nodes120via record requests122. Active transaction count240may also be decremented when a database transaction aborts.

While active transaction count240identifies a value that is greater than zero, in various embodiments, probabilistic data structure140cannot be purged. That is, a purger engine may reclaim probabilistic data structure140only after there are no active database transactions that are associated with probabilistic data structure140.

Oldest transaction commit number250, in various embodiments, is a data value that is indicative of the oldest committed transaction (in time) that inserted at least one database key into probabilistic data structure140. That is, when a transaction is committed by database node120, the transaction may be assigned a transaction commit number that may be based on when the transaction was committed. As a result, a transaction that is committed earlier in time than another transaction has a lesser/lower transaction commit number. Oldest transaction commit number250, in various embodiments, is used by a database node120to determine whether to check probabilistic data structure140for a database key. For example, if a database node120is handling a transaction snapshot with a value less than the oldest transaction commit number250, then that database node120may not check the corresponding probabilistic data structure140.

Latest transaction commit number260, in various embodiments, is a data value that is indicative of the latest committed transaction (in time) that inserted at least one database key into probabilistic data structure140. Latest transaction commit number260may be used by a first database node120to determine which probabilistic data structures140to send to a second database node120. For example, when that second database node120sends a request to that first database node120for a database record, the request may identify a transaction commit number. The transaction commit number may correspond to the latest transaction commit number260of the probabilistic data structures140that the second database node120received previously from the first database node120. The first database node120may send a response that includes probabilistic data structures140having a latest transaction commit number260that is greater than the transaction commit number specified in the second database node120's request.

State270, in various embodiments, is a data value indicative of what stage probabilistic data structure140is at in its lifecycle. In various embodiments, there are three different stages to the lifecycle of probabilistic data structure140: open, closed, and unused. Probabilistic data structure140may initially start in the “open” stage of its lifecycle and thus have a state270of “open.” While in the “open” stage of its lifecycle, probabilistic data structure140may be used for database key insertions that result from currently running database transactions. In various embodiments, after a specified number of database keys have been inserted into probabilistic data structure140, its state270is updated to “closed.” While in the “closed” stage, probabilistic data structure140may continue to be used by database nodes120, but no more database keys may be inserted into it. As a result, currently running database transactions may proceed with inserts into a new probabilistic data structure140.

Identifier value275, in various embodiments, is a value that identifies probabilistic data structure140from other probabilistic data structures140. In various cases, identifier value275may enable a database node120to refresh a stale copy of probabilistic data structure140since probabilistic data structure140may be updated and shared multiple times over the course of its existence. As an example, a transaction might continue to insert keys into probabilistic data structure140after probabilistic data structure140has been provided to another database node120. If the updated probabilistic data structure140is again shared with the other database node120, the other database120may use identifier value275in order to identify the older version of probabilistic data structure140so that it can be replaced with the updated version. In some embodiments, a database node120may include identifier value275as part of a database record request122so that the receiving database node120may determine whether the corresponding probabilistic data structure140has been updated and should be returned as a part of a database record response124.

In some embodiments, after probabilistic data structure140's latest transaction commit number260passes beyond a flusher transaction commit number (which may identify the latest transaction flushed to database110), a purger engine executing on the corresponding database node120begins a procedure to retire probabilistic data structure140. The purger engine may transition probabilistic data structure140to an “unused” state. Accordingly, state270may be updated to reflect that probabilistic data structure140is in an unused state.

Turning now toFIG.2B, a block diagram of an example cache line structure210is shown. In the illustrated embodiment, cache line structure210includes cache lines280A-D, each having respective cache line sections285. In some embodiments, cache line structure210may be implemented differently than illustrated. While cache lines280A-D are depicted as not being connected, in some embodiments, cache lines280A-D are part of a continuous segment of memory in which a given cache line280may be identified by a offset value and may span a set number of bytes in that segment.

Cache lines280, in various embodiments, are each a collection of bits that may be set as part of inserting a database key into a probabilistic data structure140. Accordingly, a cache line section285may be a bit value. In various embodiments, a cache line280is a hardware construct; yet in other embodiments, a cache line280may be implemented in software. As shown, there are five cache line sections285(i.e., five bits) per cache line280, although the amount of bits per cache line280can be different in other embodiments. In some cases, the amount of bits per cache line280may be based on a desired size of cache line structure210and a desired false positive rate. As discussed in more detail with respect toFIG.3, an initial hash function may be performed to generate a hash value that is usable to select a cache line280(e.g., cache line280A) and then a set of hash functions may be performed to generate hash values that are usable to set bits of that cache line280(e.g., set bits of sections285A and285C). The number of bits that are set may be based on a property of system100. For example, system100may provide an instruction that permits simultaneous loading from 8 different locations. Accordingly, 8 bits may be set within a cache line280for a given database key in order to benefit from the property of that instruction.

Turning now toFIG.3, a block diagram of an example transaction engine310is shown. In the illustrated embodiment, transaction engine310includes hash functions315. As further depicted, transaction engine310interacts with in-memory cache130and cache line structure210. In some embodiments, transaction engine310may be implemented different than shown.

Transaction engine310, in various embodiments, is a set of software routines that are executable to process database transactions, which can include inserting database records135into in-memory cache130and corresponding database keys320into cache line structures210of probabilistic data structures140. As discussed in more detail with respect toFIG.4, as part of processing a database transaction, transaction engine310may issue database record requests122to other transaction engines310at other database nodes120in order to potentially receive database records135from the other in-memory caches130.

As depicted, transaction engine310can receive a database transaction request105. In various cases, processing a database transaction request105may involve writing one or more database records135to in-memory cache130. When a database record135is written into in-memory cache130, in various embodiments, transaction engine310inserts the corresponding database key320into cache line structure210. In some embodiments, transaction engine310may perform a bulk insertion of database keys320of that transaction into probabilistic data structure140followed by initiating a transaction commit—in some cases, the bulk insertion is performed as part of a pre-commit phase in which a database node120performs a set of actions before finally committing the transaction.

In order to insert database key320into cache line structure210, transaction engine310may perform a set of hash function315on database key320to derive a set of hash values. A hash function315, in various embodiments, is a function that is performable to map data (e.g., database key320) of arbitrary size to fixed-size values. Hash functions315may, for example, correspond to hash functions found in the MurmurHash family. When inserting database key320into cache line structure210, transaction engine310may initially perform a hash function315on database key320to derive a hash value usable to select a cache line280. As illustrated, transaction engine310performs hash function315A on database key320to derive hash value330A. Hash value330A is used to select cache line280C. As a result, transaction engine310may set bits within cache line280C. In order to determine which bits to set, transaction engine310may perform additional hash functions315to derive additional hash values used to set bits in a cache line280. As illustrated, transaction engine310performs hash functions315B and315C on database key320to derive hash values330B and330C, respectively. Hash values330B and330C are used to set bits within cache line280C.

In some embodiments, information indicative of a database key range may be inserted into a cache line structure210. Transaction engine310may perform the procedure discussed above on a prefix portion shared between database keys in the database key range. As a result, the prefix portion may be inserted into a cache line structure210. A database node120further may determine whether to request database records associated with a key range from another database node120by checking for insertion of the prefix portion in probabilistic data structures140received from that other database node120.

Turning now toFIG.4, a block diagram of example database nodes120A and120B is shown. In the illustrated embodiment, database nodes120A and120B include an in-memory cache130, probabilistic data structures140A-C, and a transaction engine310. As illustrated, probabilistic data structures140A and140B are local to database node120A in that they were generated by database node120A while probabilistic data structure140C is local to database node120B in that it was generated by database node120B. The illustrated embodiment may be implemented differently than shown—e.g., database nodes120A and120B may include a purger engine.

As mentioned previously, database nodes120may provide database services (e.g., data storage) to tenants (e.g., an organization) of system100. A tenant's data may define a keyspace that is associated with that tenant. In some embodiments, a keyspace may be split into multiple keyspace partitions that are each assigned to a respective database node120. Consequently, a database node120may write only database records that fall within its assigned keyspace to its in-memory cache130. As a result, the probabilistic data structures140produced by a database node120may correspond to its assigned keyspace. Accordingly, as an example, probabilistic data structures140A and140B correspond to database node120A's keyspace and probabilistic data structure140C corresponds to database node120B's keyspace.

When a database node120wishes to access a database record135, it may determine which keyspace that the database record135belongs to based on its corresponding database key320. If that database record135belongs to the database node120's own keyspace, then it may checks its own in-memory cache130for the database record135and then proceed to database110if the record135is not in its own in-memory cache130. If that database record135belongs to another database node120's keyspace (e.g., belongs to database node120A), then the former database node120(e.g., database node120B) may determine whether it has probabilistic data structures140that can be checked for information indicative of the database record's database key320.

Initially, database node120B may not have any probabilistic data structures140from database node120A. Database node120B may thus issue a database record request122that identifies a particular database key320for a database record135. In various embodiments, as a side effect of the database record lookup, database node120A can return probabilistic data structures140to database node120B as part of a database record response124. Probabilistic data structures140may be returned even if there is no database record135found at database node120A's in-memory cache130. In some embodiments, database node120B is capable of issuing a probabilistic-data-structure-specific request to database node120A for probabilistic data structures140. Database node120A may have initially generated only probabilistic data structure140A and, as such, may return it to database node120B as part of the database record response124for the database record request122.

Afterwards, database node120B may wish to access another database record135that belongs to the keyspace assigned to database node120A. In some embodiments, database node120B checks probabilistic data structure140A (which it previously received) if that database record's database key320falls within the key range220of probabilistic data structure140A and if the transaction snapshot associated with that database record135occurs earlier than the oldest transaction commit that is associated with probabilistic data structure140A, which may be identified by oldest transaction commit number250. In various cases, database node120B may check one or the other or additional parameters to determine whether a probabilistic data structure140should be checked.

If applicable, database node120B may check probabilistic data structure140A in order to determine if there is a possibility that a database record135associated with the particular database key320is present at database node120A's in-memory cache130. If there is a chance, then database node120B may send a database record request122to database node120A. In some embodiments, a database record request122specifies a latest transaction commit number260. Database node120A may use commit number260to determine if any new probabilistic data structures140have been created since database node120B last issued a database record request122. If there are new probabilistic data structures140(e.g., database node120A may have created probabilistic data structure140B), then those probabilistic data structures140can be returned via a database record response124.

As mentioned, a database node120may initially write database records135to its in-memory cache130before flushing those records to database110. A database node120may flush database records135up to a particular transaction commit number or epoch. In various embodiments, when flushing database records135to database110, a database node120may purge probabilistic data structures140whose latest transaction commit number260is less than the purge transaction commit number. For example, probabilistic data structure140A may only be associated with a transaction “A.” Accordingly, when all database records135associated with transaction A are flushed to database110, database node120A may purge probabilistic data structure140A such that probabilistic data structure140A is no longer provided to other database node120. In some embodiments, a database node120notifies other database nodes120about purged probabilistic data structures140so that those other database nodes120no longer use those probabilistic data structures140if they previously received copies of those probabilistic data structures140. In yet various embodiments, when database records135are flushed to database110, an indication of the purge transaction commit number may be written to a catalog accessible to all database nodes120. As such, database nodes120may read from the catalog to determine not to use certain probabilistic data structures140as they have been purged—the purging database node120does not have to communicate with the other database nodes120directly to let them know about purged probabilistic data structures140. A database node120may remove stale probabilistic data structures140from its storage.

Turning now toFIG.5, a block diagram of a transaction engine310that interacts with example probabilistic data structures140A-C is shown. The illustrated embodiment may be implemented differently than shown—e.g., there may be more probabilistic data structures140than shown.

In some embodiments, database nodes120handle long-running transactions differently than non-long-running transactions. As mentioned, when a database node120initially inserts a database key320for a transaction into a probabilistic data structure140, that database node120may register the transaction with that probabilistic data structure140by incrementing the active transaction count240of the probabilistic data structure140. While the active transaction count240is non-zero, that probabilistic data structure140may not be purged from the database node120. This can result in issues where long-running transactions prevent probabilistic data structures140from being purged and a database node120runs out of allocated space to create new probabilistic data structures140. In particular, a long-running transaction (e.g., one that lasts over 2 hours) may write into a plurality of probabilistic data structures140that cannot be purged while the long-running transaction has not committed. In some instances, there may be multiple long-running transactions that prevent thousands of probabilistic data structures140from being purged for hours, for example. Accordingly, because database node120may not be able to purge those probabilistic data structures140for some time, it may not have sufficient space to allocate new probabilistic data structures140. Thus, in some embodiments, database nodes120handle long-running transactions differently than non-long-running transactions.

Upon beginning processing of a database transaction, a database node120may initially insert database keys320for the database transaction into probabilistic data structures140. As depicted for example, transaction engine310inserts database keys320into probabilistic data structure140A. If, however, the database node120determines that the database transaction should be classified as a long-running database transaction, then the database node120may halt database key insertion for that database transaction until a pre-commit phase. To determine if the database transaction should be classified as a long-running transaction, the database node120may use various criteria. In various embodiments, if a database transaction last longer than (or exceeds) a specified amount of time, than that database transaction may be classified as a long-running transaction. For example, if a database node120has been processing a database transaction for 120 seconds, then the database transaction may be classified as a long-running transaction. In some embodiments, if a database transaction has inserted keys into a specified number of probabilistic data structures140, than that database transaction may be classified as a long-running transaction. As an example, if in processing a database transaction, a database node120has inserted database keys320into 10 different probabilistic data structures140, then the database transaction may be classified as a long-running transaction.

Once a database node120has determined that a database transaction is a long-running database transaction, in various embodiments, the database node120unregisters the database transaction from probabilistic data structure140that it has touched. To unregister the database transaction from a given probabilistic data structure140, the database node120may decrement the active transaction count240for that given probabilistic data structure140. This may allow the given probabilistic data structure140to be purged sooner than waiting for the long-running database transaction to commit. After determining that a database transaction is a long-running transaction, the database node120may stop inserting database keys320into probabilistic data structures140for the transaction until a pre-commit phase has been initiated by database node120for that transaction. In various embodiments, a transaction is committed by database node120after writing all database records135into its in-memory cache130for that transaction—the commit may made in relation to its in-memory cache130. In some embodiments, instead of stopping key insertion for a long-running database transaction, database node120may begin writing database keys320into a single probabilistic data structure140. Database node120may allow that probabilistic data structure140to exceed a threshold number of keys than it otherwise would be permitted—that is, database node120may allow that probabilistic data structure140overflow instead of creating a new probabilistic data structure140.

Before a database node120commits a long-running database transaction, in various embodiments, the database node120performs a bulk insertion of all database keys320that are associated with the transaction into a new set of probabilistic data structures140. The database node120may then provide the new set of probabilistic data structures140to another database node120as part of a response to a database transaction request105as discussed earlier. In some embodiments, a database node120may resume inserting database keys320for the database transaction instead of restarting the insertion of all database keys320for that database transaction.

Turning now toFIG.6, a flow diagram of a method600is shown. Method600is one embodiment of a method that is performed by a first database node (e.g., database node120A) in order to provide a second database node (e.g., database node120B) with probabilistic data structures (e.g., probabilistic data structures140). Method600may be performed by executing a set of program instructions stored on a non-transitory computer-readable medium. In some embodiments, method600may include more or less steps. As an example, method600may include a step in which the first database node writes one or more of a set of database records (e.g., database records135) from its in-memory cache (e.g., in-memory cache130A) to a persistent storage (e.g., database110) shared between the first and second database nodes. The first database node may determine whether to purge one or more probabilistic data structures in response to writing those database records to the persistent storage.

Method600begins in step610with the first database node processing a database transaction that involves writing a set of database records to the in-memory cache of the first database node. The processing may include inserting, in a set of probabilistic data structures, a set of database keys (e.g., database keys320) that correspond to the set of database records. In some embodiments, inserting a given database key into a given probabilistic data structure includes applying a hash function (e.g., a hash function315) to the given database key to derive a hash value (e.g., a hash value330) that corresponds to particular one of a plurality of cache lines (e.g., a cache line280) included in the given probabilistic data structure. Accordingly, the first database node may insert the given database key in the particular cache line. Inserting the given database key in the particular cache line may include applying a set of hash functions (e.g., hash functions315) to the given database key to derive a set of hash values and setting a set of bits (e.g., a bit of a cache line section285) of the particular cache line based on the set of hash values.

The first database node may insert ones of the set of database keys in a first one of the set of probabilistic data structures. In some instances, in response to the first probabilistic data structure including a defined threshold number of database keys (e.g., 20,000 keys), the first database node may insert remaining ones of the set of database keys in a second, different one of the set of probabilistic data structures. In some cases, at least one of the set of probabilistic data structures may be associated with database keys from a plurality of different transactions.

In step620, the first database node sends, to the second database node, the set of probabilistic data structures to enable the second database node to determine whether to request, from the first database node, a database record associated with a database key. After sending the set of probabilistic data structures to the second database node, the first database node may add one or more additional probabilistic data structures to the set of probabilistic data structures. The first database node may then receive, from the second database node, a database record request (e.g., a database record request122) for a most recent version of a database record associated with a particular database key. The first database node may include, in a response (e.g., database record response124) to the database record request, the one or more additional probabilistic data structures.

In some embodiments, a given probabilistic data structure is associated with metadata (e.g., latest transaction commit number260) that indicates a latest transaction commit that corresponds to the given probabilistic data structure. In some cases, prior to including the one or more additional probabilistic data structures in the response, the first database node may determine to include the one or more additional probabilistic data structures based on each of the one or more additional probabilistic data structures being associated with a respective end latest transaction commit that corresponds to a later point in time than a particular transaction commit specified in the database record request.

In some embodiments, a given probabilistic data structure is associated with metadata (e.g., active transaction count240) that indicates a number of active transactions for which database keys have been inserted in the given probabilistic data structure. The first database node may determine whether the given probabilistic data structure can be purged based on whether the number of active transactions indicates that there are active transactions for the given probabilistic data structure. In some cases, at least two of the set of probabilistic data structures may each include a respective database key inserted as part of processing the database transaction. As such, in response to committing the database transaction in relation to the in-memory cache, the first database node may decrement, for each of the at least two probabilistic data structures, the number of active transactions associated with that probabilistic data structure.

Turning now toFIG.7, a flow diagram of a method700is shown. Method700is one embodiment of a method that is performed by a first database node (e.g., database node120A) in order to determine whether to request a database record (e.g., a database record135) from a second database node (e.g., database node120B). Method700may be performed by executing a set of program instructions stored on a non-transitory computer-readable medium. In some embodiments, method700may include more or less steps. As an example, method700may include a step in which the first database node provides a database record (received from the second database node) to an application system as part of processing a transaction request (e.g., database transaction request105) received from the application system.

Method700begins in step710with the first database node receiving, from the second database node, a set of probabilistic data structures (e.g., probabilistic data structures140) that is usable to determine whether a given database record is not stored within an in-memory cache (e.g., in-memory cache130B) of the second database node. In step720, the first database node receives a request (e.g., database transaction request105) to process a database transaction that involves a particular database key (e.g., database key320).

In step730, the first database node determines, based on the set of probabilistic data structures, whether to request, from the second database node, a most recent version of a database record that is associated with the particular database key. In some embodiments, a given probabilistic data structure includes a plurality of cache lines. As such, the first database node may apply a hash function (e.g., a hash function315) to the particular database key to derive a hash value (e.g., hash value330). Based on the hash value, the first database node may select one of the plurality of cache lines of the given probabilistic data structure. The first database node may then determine whether information stored in the cache line is indicative of the particular database key.

In response to determining that the information stored in the cache line is not indicative of the particular database key, the first database node may request the most recent version of the database record from a persistent storage (e.g., database110) shared by the first and second database nodes. In response to determining that the information stored in the cache line is indicative of the particular database key, the first database node may send a request (e.g., database record request122) to the second database node for the most recent version of the database record. Accordingly, the first database node may receive a response (e.g., database record response124) from the second database node. In some cases, the request to the second database node may identify a latest transaction commit that is associated with the set of probabilistic data structures. As such, the response may include a set of additional probabilistic data structures, each of which is associated with a transaction commit occurring later than the latest transaction commit identified by the request.

Turning now toFIG.8, a flow diagram of a method800is shown. Method800is one embodiment of a method that is performed by a database node (e.g., a database node120) to handle a long-running database transaction. Method800may be performed by executing a set of program instructions stored on a non-transitory computer-readable medium. In some embodiments, method800may include more or less steps. As an example, method800may include a step in which the database node sends, to another database node, a set of probabilistic data structures (e.g., probabilistic data structures140) to enable the other database node to determine whether to request, from the database node, a database record (e.g., a database record135) associated with a particular database key (e.g., a database key320).

Method800begins in step810with a database node receiving a request (e.g., database transaction request105) to perform a database transaction that involves writing a set of database records (e.g., database records135) to an in-memory cache (e.g., in-memory cache130) of the database node and inserting a corresponding set of database keys (e.g., database keys320) into probabilistic data structures. In step820, the database node performs the database transaction

In step822, as part of performing the database transaction, for each probabilistic data structure in which at least one database key is inserted for the database transaction, the database node registers the database transaction with that probabilistic data structure. In various cases, the registering is performed to prevent that probabilistic data structure from being deleted while the database transaction is registered. In some embodiments, a particular one of the probabilistic data structures includes metadata (e.g., active transaction count240) that specifies a number of active transactions for which database keys have been inserted in the particular probabilistic data structure. While the number of active transactions indicates that there is at least one active transaction, the particular probabilistic data structure may be prevented from being deleted. In some cases, performing the database transaction includes inserting at least one database key in the particular probabilistic data structure. As such, the database node may register the database transaction with the particular probabilistic data structure includes updating the metadata to increment the number of active transactions.

In step824, as part of performing the database transaction, the database node determines that a duration of the database transaction exceeds a specified amount of time (e.g., 30 seconds). In some embodiments, the database node determines that a specified number (e.g., 10) of probabilistic data structures have been written to as a part of performing the database transaction.

In step826, as part of performing the database transaction, in response to the determining, the database node unregisters the database transaction from each probabilistic data structure for which the database transaction was previously registered. Unregistering the database transaction from the particular probabilistic data structure may include updating the metadata to decrement the number of active transactions. The decrementing may cause the number of active transactions to be zero. As such, after determining that unregistering the database transaction from a probabilistic data structure has caused the metadata to be updated to reflect that there are no active transaction, the database node may delete the particular probabilistic data structure.

In response to the determining, the database node may delay insertion of database keys for the database transaction into probabilistic data structures until a pre-commit phase for the database transaction has been initiated by the database node. In some cases, in response to initiating the pre-commit phase for the database transaction, the database node may restart insertion of the set of database keys of the database transaction into a set of probabilistic data structures. In some cases, in response to initiating the pre-commit phase for the database transaction, the database node may resume insertion of the set of database keys of the database transaction into a set of probabilistic data structures. Before committing the database transaction, the database node may delete at least one of the probabilistic data structures from which the database transaction was unregistered. In some embodiments, in response to the determining, the database node inserts remaining database keys of the set of database keys into a single probabilistic data structure.

Exemplary Computer System

Turning now toFIG.9, a block diagram of an exemplary computer system900, which may implement system100, database110, and/or a database node120, is depicted. Computer system900includes a processor subsystem980that is coupled to a system memory920and I/O interfaces(s)940via an interconnect960(e.g., a system bus). I/O interface(s)940is coupled to one or more I/O devices950. Computer system900may be any of various types of devices, including, but not limited to, a server system, personal computer system, desktop computer, laptop or notebook computer, mainframe computer system, tablet computer, handheld computer, workstation, network computer, a consumer device such as a mobile phone, music player, or personal data assistant (PDA). Although a single computer system900is shown inFIG.9for convenience, system900may also be implemented as two or more computer systems operating together.

Processor subsystem980may include one or more processors or processing units. In various embodiments of computer system900, multiple instances of processor subsystem980may be coupled to interconnect960. In various embodiments, processor subsystem980(or each processor unit within980) may contain a cache or other form of on-board memory.

System memory920is usable store program instructions executable by processor subsystem980to cause system900perform various operations described herein. System memory920may be implemented using different physical memory media, such as hard disk storage, floppy disk storage, removable disk storage, flash memory, random access memory (RAM—SRAM, EDO RAM, SDRAM, DDR SDRAM, RAMBUS RAM, etc.), read only memory (PROM, EEPROM, etc.), and so on. Memory in computer system900is not limited to primary storage such as memory920. Rather, computer system900may also include other forms of storage such as cache memory in processor subsystem980and secondary storage on I/O Devices950(e.g., a hard drive, storage array, etc.). In some embodiments, these other forms of storage may also store program instructions executable by processor subsystem980. In some embodiments, program instructions that when executed implement a database110, a database node120, an in-memory cache130, and a probabilistic data structure140may be included/stored within system memory920.

I/O interfaces940may be any of various types of interfaces configured to couple to and communicate with other devices, according to various embodiments. In one embodiment, I/O interface940is a bridge chip (e.g., Southbridge) from a front-side to one or more back-side buses. I/O interfaces940may be coupled to one or more I/O devices950via one or more corresponding buses or other interfaces. Examples of I/O devices950include storage devices (hard drive, optical drive, removable flash drive, storage array, SAN, or their associated controller), network interface devices (e.g., to a local or wide-area network), or other devices (e.g., graphics, user interface devices, etc.). In one embodiment, computer system900is coupled to a network via a network interface device950(e.g., configured to communicate over WiFi, Bluetooth, Ethernet, etc.).