Building of tries over sorted keys

Techniques are disclosed relating to building an in-memory multi-level data structure useable to determine presence or absence of key ranges in files consisting of database records. In various embodiments, a computer system operates a database, including maintaining a set of records having a set of corresponding keys that are accessible in key-sorted order and generates a multi-level data structure that facilitates key range lookups against the set of records. The generating may include accessing ones of the set of keys in key-sorted order and determining, for a particular accessed key that includes a set of characters, an intermediate level within the multi-level data structure and a subset of the characters of the particular accessed key for insertion. The computer system may insert, starting at the intermediate level, information that identifies the subset of characters, with the inserting being performed without traversing any levels before the intermediate level.

BACKGROUND

Technical Field

This disclosure relates generally to database systems and, more specifically, to building multi-level data structures that can store information indicative of database keys.

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 database systems maintain a log-structured merge-tree (LSM tree) having multiple levels that each store information in database records as key-value pairs. An LSM tree normally includes two high-level components: an in-memory buffer and a persistent storage. During operation, a database system initially writes database records into the in-memory buffer before later flushing them to the persistent storage. As a part of flushing database records, the database system writes the database records into new files in which the database records are ordered according to their keys.

DETAILED DESCRIPTION

As mentioned, a database system often operates a database that is built around an LSM tree in which database records are stored in files written to persistent storage, with the database records being stored in key-sorted order. Thus, a file written to persistent storage contains a set of database records that associate that file with a particular key range. During operation, the database system processes transaction requests that may involve accessing databases records from files stored at the persistent storage for database keys specified in the transaction requests. If a transaction request involves searching files for database records whose keys fall within a particular key range instead of an individual key, then a particular type of probabilistic data structure, referred to as a “trie” or “trie data structure,” can be used to reduce the number of files fetched from the persistent storage. Tries can also be used to determine if a particular database node includes, in its in-memory buffer, database records whose database keys fall within a specified key range.

When the database system is writing out database records to a file on persistence storage, the database system may build and store a trie in the file (or along with the file) that can be used for key range lookups on those database records. Prior approaches for building tries, however, are deficient. For example, traditional tries are implemented as tree structures and thus building a trie involves traversing the branches of the trie's tree structure to navigate to the correct location for inserting a set of nodes corresponding to a new key being inserted into the trie. Having to traverse down potentially multiple levels from a root node for each key being inserted is costly, especially when thousands of keys are inserted into the trie. Furthermore, prior approaches for building tries do not impose a tight memory bound on the size of the trie when it is being built. The present disclosure addresses, among other things, these technical problems of costly trie traversals and a lack of a tight memory bound being imposed when building a trie.

More specifically, the present disclosure recognizes that, at the point when database records are being written to persistent storage, the keys of those records are available in key-sorted order. Accordingly, the present disclosure utilizes this availability of the sorted keys to build a multi-level data structure (e.g., a trie) in system memory in an efficient manner by avoiding unnecessary level traversals when inserting keys into the multi-level data structure. Since the preceding key and the succeeding key to a current key are available to the database system, the database system may compare the current key with both the preceding key and the succeeding key to determine 1) at which level in the multi-level data structure to start adding nodes corresponding to the current key and 2) how many nodes of the current key need to be added to the multi-level data structure during the insertion of the current key.

In particular, when adding a current key, in various embodiments, the database system determines at which level to start adding nodes for the current key by comparing the current key with the preceding key to determine their overlap. The nodes that overlap between these two keys have already been inserted when the preceding key was added to the multi-level data structure and thus that prefix portion (i.e., the overlap) of the current key does not have to be added again. As a result, when adding the current key, the database system can skip traversing the levels associated with those already added nodes, thus saving time. The database system may instead begin inserting nodes for the current key at the determined starting level. Hence, the techniques of this disclosure provide an advantage of avoiding unnecessary level traversal while inserting keys into the multi-level data structure.

After determining a starting level for inserting nodes, in various embodiments, the database system compares the current key to the succeeding key to determine the number of nodes to insert in order to differentiate the current key from other keys that are inserted in the multi-level data structure. Since a key may be very lengthy, it may be desirable to not insert the entire key. Thus, the database system may identify a set of nodes to insert based on the starting level and an overlap between the current key and the succeeding key. In some embodiments, the database system then adds one additional node to the set of nodes, where the additional node corresponds to the character of the current key that occurs sequentially after the overlap between those two keys. The additional node may be the smallest amount of information capable of providing a minimum differentiation from the succeeding key to be inserted into the multi-level data structure. This may result in smaller multi-level data structures, thus providing an advantage of keeping the size of the multi-level data structures manageable.

As noted, in various embodiments, the database system is able to determine the number of nodes to insert for the current key. Thus, another advantage of building a multi-level data structure using the techniques of the present disclosure is that it is possible to determine whether the insertion of the current key will cause a predetermined memory allocation for the multi-level data structure to be exceeded. Yet another advantage is that there is no need to provide buffering for the keys before insertion into the multi-level data structure, since the keys are inserted into the multi-level data structure as their corresponding database records are being written into persistent storage. 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 database node120that interacts with database110. As further shown, database110includes files115that are a repository of database records. Also as illustrated, database node120includes a ML management module130and a system memory140. In some embodiments, system100may be implemented differently than shown. For example, system100may include multiple database nodes120that interact with each other and database110.

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 node120to carry out operations (e.g., accessing, storing, etc.) on information that is stored at database110. In some embodiments, database110is implemented by a single or multiple storage devices connected together on a network (e.g., a storage attached network (SAN)) and configured to redundantly store information to prevent data loss. The storage devices may store data persistently and thus database110may serve as a persistent storage. In various embodiments, database110is shared between multiple database nodes120such that database records150written into files115by one database node120are accessible by other database nodes120. Files115may be stored as part of an LSM tree that is implemented at database110.

Files115, in various embodiments, include sets of database records150. A database record150, in various embodiments, includes a key-value pair that comprises data and a corresponding key155that is usable to look up that database record150. For example, a database record150may correspond to a data row in a database table where the database record150specifies values for one or more attributes (or columns) associated with the database table. In various embodiments, a file115is associated with one or more database key ranges defined by the keys155of the database records150that are included in that file115. Consider an example in which a file115stores three database records150associated with keys155“AA,” “AAB,” and “AC,” respectively. Those three keys155span a database key range of AA→AC and thus that file115may be associated with a database key range of AA→AC.

Database node120, in various embodiments, is hardware, software, or a combination thereof capable of providing database services, such as data storage, data retrieval, and/or data manipulation. Such database services may be provided to other components within system100and/or to components external to system100. As an example, database node120may receive a database transaction request from an application server (not shown) that is requesting data to be written to and/or read from database110. The database transaction request may specify an SQL SELECT command to select one or more rows from one or more database tables. The contents of a row may be defined in a database record150and thus database node120may locate and return one or more database records150that correspond to the selected one or more table rows. In some cases, the database transaction request may instruct database node120to write one or more database records150to database110. In various embodiments, database node120initially writes database records150to system memory140before flushing those database records150to database110as files115.

System memory140, in various embodiments, is a volatile memory (e.g., dynamic random-access memory) or a non-volatile memory (e.g., NAND flash memory). System memory140may serve as a repository that temporarily stores records150that are written for database transactions being processed by database node120. After a threshold number of records150have been written to system memory140, in various embodiments, database node120flushes a set of those records150out to database110as part of new files115. In some embodiments, database node120flushes records150after set intervals of time. System memory140also serves as a repository that stores in-memory multi-level data structures160.

A multi-level (ML) data structure160, in various embodiments, is a data structure that includes a vector structure (or simply “vector”) having a set of level vectors that respectively correspond to different levels of the ML data structure160. Each level vector may store a set of nodes that identify character values of keys155that have been inserted into the ML data structure160. Accordingly, as more keys155are increasingly inserted into the ML data structure160, the number of nodes of a given level vector may increase to accommodate the additional characters inserted as a result of the insertion of those keys155. An example of an ML data structure160is shown inFIG.4.

In various cases, an ML data structure160may be a probabilistic data structure that can provide an indication of the database key ranges associated with one or more files115. As used herein, the term “probabilistic data structure” refers to a data structure that maintains information indicating that a particular item either does not exist or might exist at a particular location within a system. As an example, a probabilistic data structure can store information that indicates that a database record150does not exist or might exist within a file115. In various embodiments, an ML data structure160has a reasonably smaller memory footprint than the corresponding file115. Consequently, database node120may more quickly and efficiently access ML data structures160than accessing the corresponding files115. As a result, using an ML data structure160to check for whether a certain database record150may be included in a given file115instead of directly accessing the given file115to check for the database record150can provide a substantial performance boost to system100. The efficient building of an ML data structure160is described in the rest of the disclosure.

ML management module130, in various embodiments, is a set of software routines executable to generate an ML data structure160. As noted, at the time of flushing records150stored in system memory140to persistent storage (e.g., to files115), the records150may be written out in a sorted order according to their keys155. Since records150are written out in key-sorted order, in various embodiments, knowledge about the ordering of those keys155is available to ML management module130. Accordingly, ML management module130may access a particular key155(which can be referred to as the “current” key155) along with the preceding and succeeding keys155to that current key155. ML management module130may then perform a set of comparisons involving those keys155as part of inserting the current key155into an ML data structure160. As alluded to previously, on the basis of two comparisons, in various embodiments, ML management module130determines the exact number of nodes to insert into an ML data structure160in order to represent the current key155. The process of determining the number of nodes to insert and the level in an ML data structure160at which to begin inserting them (without traversing any of the preceding levels of the ML data structure160) is further discussed with reference toFIGS.2-4.

As explained more fully with reference to the following figures, ML management module130provides an advantage over prior approaches of building tries by avoiding traversals of levels in an ML data structure160prior to the level at which the insertion of nodes is determined to begin while inserting nodes corresponding to a key into the ML data structure160. Furthermore, the building of an ML data structure160provides another advantage over prior approaches in that the building of the ML data structure160is performed without the need to buffer keys155, since the insertion of a key155takes place at the same time that the key's corresponding record150is being written to files115at persistent storage. A specific example to explain how ML management module130determines how many nodes to add to an ML data structure160in the context of inserting a particular key155among a set of sorted keys155is provided next with reference toFIG.2.

Turning now toFIG.2, an example200of a set of three example keys155is depicted including a current key155B that is being inserted into an ML data structure160.FIG.2provides an illustration about how the comparisons of current key155B with both a preceding key155A and a succeeding key155C (according to key-sorted order) provide an advantage of being able to figure out the least number of nodes (corresponding to characters of current key155B) to be inserted into an ML data structure160that is able to provide a differentiation of current key155B from both preceding key155A and succeeding key155C.

In the example ofFIG.2, preceding key155A corresponds to a record150that is written to database110before the database record(s)150of current key155B while succeeding key155C corresponds to a record150that is to be written after the writing of the database record(s) of current key155B. As shown, preceding key155A comprises four nodes “R”, “O”, “C”, and “K”; current key155B comprises four nodes “R”, “O”, “O”, and “F”; and succeeding key155C comprises five nodes “R”, “O”, “O”, “T”, and “S”. The availability of both preceding key155A and succeeding key155C allows for an ML data structure160to be built in an efficient manner, as explained below.

Regarding the building of an ML data structure160efficiently, in various embodiments, ML management module130performs a comparison between preceding key155A and current key155B to determine the number of nodes that are shared between the two keys155. In the specific example depicted inFIG.2, there are 2 nodes (“RO”) shared between preceding key155A (“ROCK”) and current key155B (“ROOF”)—this shared overlap is shown as preceding key prefix overlap210. Based on preceding key prefix overlap210, in various embodiments, ML management module130determines a level at which to start inserting information about current key155B into an ML data structure160. This is because nodes that are shared between preceding key155A and current key155B have already been inserted when preceding key155A was added and thus that prefix portion of current key155B does not need to be added again. Consequently, ML management module130may determine an intermediate level of ML data structure160that occurs after those levels that include the nodes for the shared portion between preceding key155A and current key155B. As a result, when adding current key155B, ML management module130can skip traversing the levels associated with those already added nodes, thus saving time.

In various embodiments, ML management module130also performs a comparison between current key155B and succeeding key155C to determine succeeding key prefix overlap220, i.e., the number of nodes that are shared between those two keys155. As shown inFIG.2, there are 3 nodes (“ROO”) shared between current key155B (“ROOF”) and succeeding key155C (“ROOTS”). Based on this comparison and the one mentioned above, ML management module130may calculates a number of prefix nodes to insert in an ML data structure160as 1) the difference between the number of shared nodes between current key155B with succeeding key155C and the number of shared nodes between current key155B with preceding key155A and 2) one distinguishing suffix node230. In the specific example, ML management module130determines the number of prefix nodes to be (3−2)=1 prefix node (i.e., the node “O”).

Subsequently, ML management module130determines a distinguishing suffix node230as the one node that distinguishes current key155B from succeeding key155C, that being the node “F” in the example ofFIG.2. Finally, ML management module130determines insertion nodes240to represent the minimum number of nodes that would distinguish current key155B from both preceding key155A and succeeding key155C. As noted, a minimum 1 prefix node and 1 suffix node are to be inserted into the ML data structure for current key155B to be distinguishable. In other words, in various embodiments, only the minimum nodes that distinguish the current key155B are inserted into an ML data structure160, and not necessarily all the nodes of current key155B. In the specific example shown inFIG.2, these nodes are prefix node “O”, and suffix node “F”.

By following the steps described above, ML management module130determines the minimum number of nodes from current key155B to insert into an ML data structure160. Thus, the size of ML data structure160is kept to a minimum in system memory140. Also, being able to precisely determine the size of ML data structure160at the stage of insertion of each current key155B by determining the number of prefix nodes and one suffix node prior to the insertion of the nodes into an ML data structure160, ML management module130provides an advantage of being able to prevent the size of an ML data structure160from exceeding a predetermined memory budget. In some embodiments, if the memory budget is about to be exceeded, then the insertion of current key155B may be skipped. An example illustration of an ML data structure160is shown with reference toFIG.3Anext as a vector comprising multiple levels. Each vector represents a vector of nodes at a particular level of an ML data structure160.

Turning now toFIGS.3A and3B,FIG.3Adepicts a general example of an ML data structure160andFIG.3Billustrates an example embodiment of a node320included in an ML data structure160. In the example ofFIG.3A, level vector310A includes node320A, which serves as the root node at level 0 in the illustrated ML data structure160. As noted, each level of the ML data structure160may be a vector of nodes. At level 0 in the ML data structure160, only a root character may be inserted that does not represent a node in any key155, but rather includes metadata for interpreting the ML data structure160(e.g., the metadata may indicate the number of keys155inserted into the ML data structure160). Level vector310B represents nodes at level 1 in the ML data structure160, where the first node of each key155that is unique from the preceding keys155is inserted into the ML data structure160at level 1. In the illustrated embodiment, level vector310B is shown to include nodes320B,320C,320D, and320E. Level vector310C represents nodes320at level 2. The insertion of nodes320based on a current key155begins at level 2 if the current key155shares exactly one node with the preceding key155. In the illustrated embodiment, level vector310C includes a vector of nodes320F,320G,320H,320I. Similarly, level vector310D represents nodes at level 3. The insertion of nodes from a current key155begins at level 3 if the current key155shares exactly two nodes with the preceding key155. In the illustrated embodiment, level vector310D includes a vector of nodes320J,320K,320L,320M. Finally, level vector310E represents nodes at level “n”. The insertion of nodes from a current key155begins at level “n” if the current key155shares exactly “n” nodes with the preceding key155. In the illustrated embodiment, level vector310E includes a vector of nodes320N,320O,320P,320Q.

In the example ofFIG.3B, the contents of a node320that is inserted into a level vector310of an ML data structure160is depicted. In some embodiments, a node320of the ML data structure160includes a character value330that represents the node/character from the key155that is being inserted into the level vector310. Furthermore, a node320may include a suffix indicator340to indicate whether the node is a suffix node. In various cases, suffix indicator340may be a bit. As such, if suffix indicator340is set to 1, then the node is a suffix node, otherwise, it is a prefix node). If a node320is a suffix node, then ML management module130may determine that it has reached the end of a key155. A node320may also include a first child node indicator350that indicates whether the node is a first child node.

Together,FIGS.3Aand B illustrate an organization of an ML data structure160as a vector consisting of multiple levels. Such an organization of an ML data structure160makes it possible to determine the level at which to start the insertion of nodes320in the ML data structure160without traversing any of the preceding levels in the ML data structure160. This represents an advantage provided by the present disclosure about building a ML data structure160efficiently in system memory140.

Turning now toFIG.4, a block diagram400of an example embodiment of ML management module130is depicted. In the illustrated embodiment, ML management module130includes a key comparator module410and a node inserter module420. The steps of an algorithm for inserting a particular key155in a ML data structure160are described next. In some embodiments, the steps described below are implemented by ML management module130.

For adding a particular key155, ML management module130may first determine:

b) Shared bytes with succeeding key: SBn+1, n

Next, ML management module130may determine a number of prefix nodes “p” to be inserted into the MIL data structure, as follows.

As noted, one (1) suffix node may be added to an ML data structure160for a minimum differentiation of the particular key155with the succeeding key155to be added. Since the size of (p+1) nodes are known, the size requirement of adding the particular key155is known prior to adding the nodes for the particular key155. If there is not enough space in the ML data structure160to add the nodes (according to a predefined size limit of the ML data structure160), then the nodes may not be added. This provides an advantage of enforcing a tight memory bound on the size of the ML data structure160. Before adding a key155to the ML data structure160, the last entry in the vector at level=SBn, n−1may be read. This is the last byte that is shared between the preceding key155and the current, particular key155. The addition of the nodes for the particular key155may be performed by adding a new branch from the next level in the ML data structure160. If the first child node indicator350is set in the last entry, then the first child node indicator350in the node at the next level may not be set, and vice versa. In various embodiments, the algorithm loops through all levels from [SBn, n−1+1, SBn, n−1+p] and for each level, a node is appended to the level vector310at the level, if the level vector310exists. If the level vector310does not exist at that level, then the node320is added after creating a new level vector310at the level. Finally, as alluded to previously, one (1) suffix node320is appended at level SBn, n−1+p+1.

Key comparator module410, in various embodiments, is a set of software routines executable to perform a comparison of current, preceding, and succeeding keys155to determine the number of nodes320to insert into an ML data structure160. These comparisons may allow key comparator module410to determine the number of prefix nodes320and one suffix node320to be inserted into an ML data structure160corresponding to the insertion of the current key155into the ML data structure160. In various embodiments, key comparator module410implements the steps of the algorithm that relate to comparison of keys155. As noted, key comparator module410compares a current key155with both a preceding key155and a succeeding key155in order to determine the number of nodes320to insert into an ML data structure160. As alluded to previously, key comparator module410may also determine the level at which to start inserting the determined number nodes320through the comparison of the current key155with the preceding key155.

Node inserter module420, in various embodiments, is a set of software routines executable to perform an insertion of the determined number of nodes320into an ML data structure160. Node inserter module420interfaces with key comparator module410to obtain information about what nodes320to insert into an ML data structure160. Key comparator module410may also inform node inserter module420about the starting level from which to start inserting the nodes320for the current key155. For each node320inserted into the ML data structure160, in various embodiments, node inserter module420inserts a character value330representing that node320of the key155being inserted. Further, node inserter module420may determine whether to set the suffix indicator340and/or the first child node indicator350for the node320. Thus, node inserter module420may be responsible for ensuring that each node320added to the ML data structure160is inserted at the appropriate level, and that the suffix indicator340and the first child node indicator350are set to correct values for each node320. The setting of the suffix indicator340and the first child node indicator350enable proper read-back of the keys155based on the nodes320inserted in the ML data structure160. It may be noted that not all characters of each key155are inserted into the ML data structure160, since for managing the overall size of the ML data structure160, node inserter module420may insert only the minimum number of nodes320that provides a differentiation of a current key155from both the preceding and succeeding keys155. In some embodiments, node inserter module420may provide the flexibility of appending the nodes in parallel to each relevant level vector310of the ML data structure160, thus further accentuating the advantage of not having to traverse the ML data structure for inserting nodes. A specific example of the insertion of a particular set of keys155into an ML data structure160is depicted next with reference toFIG.5.

Turning now toFIG.5, an example of the state of an ML data structure160is illustrated after the insertion of example keys155“ROCK”, “ROOF”, and “ROOTS”. As shown inFIG.5, level vector310A is the root level of the illustrated ML data structure160(designated as “Root”) and does not represent a node320belonging to any of the keys155being inserted. Starting with the insertion of key155“ROCK”, it may not be first compared with a preceding key155as it is the first key155inserted. Hence, there is no preceding key prefix overlap210and thus SBn, n−1=0. The key155“ROCK” may then be compared to the succeeding key155“ROOF”. There are 2 characters in common (“RO”) and thus SBn+1, n=2. Hence, the number of prefix nodes320is determined as p=2 that are designated as prefix nodes320, and those are inserted starting at level 1. Thus, a node320“R” is inserted in level vector310B at level 1, and a node320“O” is inserted in level vector310C at level 2. For each of those nodes320, the suffix indicator340is set to 0, to indicate that the nodes320are prefix nodes320. One suffix node320is then added to level vector310D as the character “C”, since that represents the one character that provides a minimum differentiation of the current key155“ROCK” with the succeeding key “ROOF”. The suffix indicator340for that node320added at level 3 is set to 1, to indicate that the node320is a suffix node. The first child node indicator350may be set to 1 for the nodes added at each level of the ML data structure, since these nodes are the first child at each level.

Continuing with the insertion of key155“ROOF”, it may first be compared to the preceding key155“ROCK”. For this example, SBn, n−1=2, since characters R and O are shared between the current key155“ROOF” and the preceding key155“ROCK”. Also, SBn+1, n=3, since characters “R”, “O”, and “O” are shared between the current key155and the succeeding key155“ROOTS”. Hence, p=3−2=1. Thus, one prefix node320, the character “O”, may be inserted into the MIL data structure160. The level at which the prefix node320will be inserted is at level 3, since the characters at the first two levels of the ML data structure160have already been inserted while adding the preceding key155“ROCK”. Thus, a node320“O” is inserted in level vector310D at level 3 with the suffix indicator340being set to 0, to indicate that the node320is a prefix node320. The first child node indicator350for the node230added to level vector310D may be set to 0 since it is not the first child node320at that level. One suffix node may then be added to level vector310E as the character “F”, since that represents the one character that provides a minimum differentiation of the current key155“ROOF” with the succeeding key155“ROOTS”. For the node added to level vector310D, the suffix indicator340may be set to 1 (to indicate that it is a suffix node), and the first child node indicator350is set to 1 (to indicate that it is the first child node for level vector310D).

Finally, with regards to the insertion of the key155“ROOTS”, it may first be compared to the preceding key155“ROOF”. For this example, SBn, n−1=3, since characters “R” and “O” are shared between the current key155and the preceding key155. Also, SBn+1, n=0, since there is no succeeding key155for comparison with the current key155. Hence, p=0, and thus no prefix nodes may be inserted in the ML data structure160for this current key155. Since SBn, n−1=3, hence, the level to add one suffix node320to the ML data structure160is level 4. The character to add as a suffix node320is “T” in level vector310E, since that represents the one character that provides a minimum differentiation of the current key155“ROOTS” with the preceding key155“ROOF”. Note that the determination of the suffix character may be done by comparing with the preceding key155in case there is no succeeding key to compare the current key with. For the node320added to level vector310E, the suffix indicator340is set to 1 (to indicate that it is a suffix node320), and the first child node indicator350is set to 1 (to indicate that it is the first child node320for level vector310E). This completes the description of the insertion of the example keys155“ROCK”, “ROOF”, and “ROOTS” into the ML data structure160. The example illustrates the advantages of avoidance of traversal of prior levels while inserting nodes, and of being able to respect a predetermined limit of a memory budget for the ML data structure. With the description of the algorithm and specific example of insertion of particular set of keys into a ML data structure having been provided with respect toFIGS.4and5, a couple of example methods for building the ML data structure in an efficient manner is provided next.

Turning now toFIG.6, a flowchart of an example method600implemented by a database node is shown. In the illustrated embodiment, at step610, a computer system (e.g., database node120) operates a database, including maintaining a set of records having a set of corresponding keys that are accessible in key-sorted order. In some embodiments, the set of records in the database is maintained as a LSM tree data structure; however, the records may be initially written to a memory of the computer system (e.g., records150in system memory140). When the size of the records exceeds a particular threshold, the set of records are written to persistence storage (e.g., to files115) in a sorted order of the keys of the records.

At step620, the computer system generates a multi-level data structure (e.g., an ML data structure160) that facilitates key range lookups against the set of records. In some embodiments, the generation of the ML data structure takes place at the time when database records are being written from memory to persistence storage. Details about the steps for generating an example ML data structure have been discussed with reference toFIGS.2-5. Note that when the ML data structure is used for key range lookups, it is able to correctly determine with accuracy whether a key (or a range of keys) is not present in the ML data structure. But the ML data structure may not always indicate that a particular key is present in a corresponding file comprising a set of database records. The reason for this is that only a minimum set of characters from a particular key is stored in the ML data structure that provides a minimum distinguishing of the particular key from a preceding and a succeeding key. Thus, if the ML data structure includes a key prefix of ROOF, and a key with characters ROOFER is searched, then the ML data structure may indicate that the searched key is possibly present in the corresponding file of database records. In such cases, an actual search of the file with database records would truly reveal the presence or absence of the searched key in the set of database records.

At step622, the computer system continues with the generation of the multi-level data structure whereby the generating includes accessing ones of set of keys in key-sorted order. For example, the accessed key is designated as a current key155inFIGS.2-5.

At step624, the computer system continues with the generation of the multi-level data structure whereby the generating further includes, for particular accessed key that comprises set of characters, determining intermediate level within multi-level data structure at which to start inserting information about particular accessed key, and determining a subset of characters of particular accessed key for insertion. In some embodiments, as described above with reference toFIGS.4and5, the determination of the intermediate level at which to start inserting nodes from the particular accessed key involves the comparison of the particular key with a preceding and a succeeding key in the sorted order of the keys.

At step626, the computer system further continues with the generation of the multi-level data structure whereby the generating includes inserting, starting at intermediate level, information that identifies subset of characters. In some embodiments, the comparison of the particular key with a preceding and a succeeding key not only determines the level at which to start inserting nodes into the ML data structure but also identifies the subset of characters that minimally distinguish the particular key from all other keys in the set of database records in memory.

Turning now toFIG.7, a flowchart of an example method700implemented by a database node is shown. Method700has similarities and overlap to method600described with respect toFIG.6. At step710, a computer system (e.g., database node120) operates a database that includes plurality of key-value pair data records. As noted, when writing the data records from memory to persistent storage, the records are written in a sorted order of the keys.

At step720, the computer system fetches a first key that belongs to particular key-value pair data record of plurality of key-value pair data records stored in database. In some embodiments, the availability of keys in a sorted order presents an opportunity to compare a particular key with a preceding and a succeeding key while the records corresponding to those keys are present in system memory. This allows those records to be accessed without cache misses.

At step730, the computer system, in response to comparing first key with preceding key belonging to immediately preceding key-value pair data record for which preceding key is different from first key and comparing first key with succeeding key belonging to immediately succeeding key-value pair data record for which succeeding key is different from first key, inserts a set of character nodes into multi-level tree data structure. In some embodiments, the ML data structure is implemented as vector of multiple levels of vectors. As alluded to previously with reference toFIGS.4and5, the comparison of a first key with a preceding and a succeeding key enables the determination of a level in the ML data structure at which to start inserting nodes from the first key into the ML data structure. Advantageously, the organization of the ML data structure as a vector of multiple levels of vectors allows the insertion to occur without traversing any of the previous levels of the ML data structure.

Exemplary Multi-Tenant Database System

Turning now toFIG.8, an exemplary multi-tenant database system (MTS)800in which various techniques of the present disclosure can be implemented is shown—e.g., system100may be MTS800. InFIG.8, MTS800includes a database platform810, an application platform820, and a network interface830connected to a network840. Also as shown, database platform810includes a data storage812and a set of database servers814A-N that interact with data storage812, and application platform820includes a set of application servers822A-N having respective environments824. In the illustrated embodiment, MTS800is connected to various user systems850A-N through network840. The disclosed multi-tenant system is included for illustrative purposes and is not intended to limit the scope of the present disclosure. In other embodiments, techniques of this disclosure are implemented in non-multi-tenant environments such as client/server environments, cloud computing environments, clustered computers, etc.

MTS800, in various embodiments, is a set of computer systems that together provide various services to users (alternatively referred to as “tenants”) that interact with MTS800. In some embodiments, MTS800implements a customer relationship management (CRM) system that provides mechanism for tenants (e.g., companies, government bodies, etc.) to manage their relationships and interactions with customers and potential customers. For example, MTS800might enable tenants to store customer contact information (e.g., a customer's website, email address, telephone number, and social media data), identify sales opportunities, record service issues, and manage marketing campaigns. Furthermore, MTS800may enable those tenants to identify how customers have been communicated with, what the customers have bought, when the customers last purchased items, and what the customers paid. To provide the services of a CRM system and/or other services, as shown, MTS800includes a database platform810and an application platform820.

Database platform810, in various embodiments, is a combination of hardware elements and software routines that implement database services for storing and managing data of MTS800, including tenant data. As shown, database platform810includes data storage812. Data storage812, in various embodiments, includes a set of storage devices (e.g., solid state drives, hard disk drives, etc.) that are connected together on a network (e.g., a storage attached network (SAN)) and configured to redundantly store data to prevent data loss. In various embodiments, data storage812is used to implement a database (e.g., database110) comprising a collection of information that is organized in a way that allows for access, storage, and manipulation of the information. Data storage812may implement a single database, a distributed database, a collection of distributed databases, a database with redundant online or offline backups or other redundancies, etc. As part of implementing the database, data storage812may store files (e.g., files115) that include one or more database records having respective data payloads (e.g., values for fields of a database table) and metadata (e.g., a key value, timestamp, table identifier of the table associated with the record, tenant identifier of the tenant associated with the record, etc.).

In various embodiments, a database record may correspond to a row of a table. A table generally contains one or more data categories that are logically arranged as columns or fields in a viewable schema. Accordingly, each record of a table may contain an instance of data for each category defined by the fields. For example, a database may include a table that describes a customer with fields for basic contact information such as name, address, phone number, fax number, etc. A record therefore for that table may include a value for each of the fields (e.g., a name for the name field) in the table. Another table might describe a purchase order, including fields for information such as customer, product, sale price, date, etc. In various embodiments, standard entity tables are provided for use by all tenants, such as tables for account, contact, lead and opportunity data, each containing pre-defined fields. MTS800may store, in the same table, database records for one or more tenants—that is, tenants may share a table. Accordingly, database records, in various embodiments, include a tenant identifier that indicates the owner of a database record. As a result, the data of one tenant is kept secure and separate from that of other tenants so that that one tenant does not have access to another tenant's data, unless such data is expressly shared.

In some embodiments, the data stored at data storage812is organized as part of a log-structured merge-tree (LSM tree). An LSM tree normally includes two high-level components: an in-memory buffer and a persistent storage. In operation, a database server814may initially write database records into a local in-memory buffer before later flushing those records to the persistent storage (e.g., data storage812).

When a database server814wishes to access a database record for a particular key, the database server814may traverse the different levels of the LSM tree for files that potentially include a database record for that particular key. If the database server814determines that a file may include a relevant database record, the database server814may fetch the file from data storage812into a memory of the database server814. The database server814may then check the fetched file for a database record having the particular key.

Database servers814, in various embodiments, are hardware elements, software routines, or a combination thereof capable of providing database services, such as data storage, data retrieval, and/or data manipulation. A database server814may correspond to database node120. Such database services may be provided by database servers814to components (e.g., application servers822) within MTS800and to components external to MTS800. As an example, a database server814may receive a database transaction request from an application server822that is requesting data to be written to or read from data storage812. The database transaction request may specify an SQL SELECT command to select one or more rows from one or more database tables. The contents of a row may be defined in a database record and thus database server814may locate and return one or more database records that correspond to the selected one or more table rows. In various cases, the database transaction request may instruct database server814to write one or more database records for the LSM tree—database servers814maintain the LSM tree implemented on database platform810. In some embodiments, database servers814implement a relational database management system (RDMS) or object-oriented database management system (OODBMS) that facilitates storage and retrieval of information against data storage812. In various cases, database servers814may communicate with each other to facilitate the processing of transactions. For example, database server814A may communicate with database server814N to determine if database server814N has written a database record into its in-memory buffer for a particular key.

Application platform820, in various embodiments, is a combination of hardware elements and software routines that implement and execute CRM software applications as well as provide related data, code, forms, web pages and other information to and from user systems850and store related data, objects, web page content, and other tenant information via database platform810. In order to facilitate these services, in various embodiments, application platform820communicates with database platform810to store, access, and manipulate data. In some instances, application platform820may communicate with database platform810via different network connections. For example, one application server822may be coupled via a local area network and another application server822may be coupled via a direct network link. Transfer Control Protocol and Internet Protocol (TCP/IP) are exemplary protocols for communicating between application platform820and database platform810, however, it will be apparent to those skilled in the art that other transport protocols may be used depending on the network interconnect used.

Application servers822, in various embodiments, are hardware elements, software routines, or a combination thereof capable of providing services of application platform820, including processing requests received from tenants of MTS800. Application servers822, in various embodiments, can spawn environments824that are usable for various purposes, such as providing functionality for developers to develop, execute, and manage applications (e.g., business logic). Data may be transferred into an environment824from another environment824and/or from database platform810. In some cases, environments824cannot access data from other environments824unless such data is expressly shared. In some embodiments, multiple environments824can be associated with a single tenant.

Application platform820may provide user systems850access to multiple, different hosted (standard and/or custom) applications, including a CRM application and/or applications developed by tenants. In various embodiments, application platform820may manage creation of the applications, testing of the applications, storage of the applications into database objects at data storage812, execution of the applications in an environment824(e.g., a virtual machine of a process space), or any combination thereof. In some embodiments, application platform820may add and remove application servers822from a server pool at any time for any reason, there may be no server affinity for a user and/or organization to a specific application server822. In some embodiments, an interface system (not shown) implementing a load balancing function (e.g., an F5 Big-IP load balancer) is located between the application servers822and the user systems850and is configured to distribute requests to the application servers822. In some embodiments, the load balancer uses a least connections algorithm to route user requests to the application servers822. Other examples of load balancing algorithms, such as are round robin and observed response time, also can be used. For example, in certain embodiments, three consecutive requests from the same user could hit three different servers822, and three requests from different users could hit the same server822.

In some embodiments, MTS800provides security mechanisms, such as encryption, to keep each tenant's data separate unless the data is shared. If more than one server814or822is used, they may be located in close proximity to one another (e.g., in a server farm located in a single building or campus), or they may be distributed at locations remote from one another (e.g., one or more servers814located in city A and one or more servers822located in city B). Accordingly, MTS800may include one or more logically and/or physically connected servers distributed locally or across one or more geographic locations.

One or more users (e.g., via user systems850) may interact with MTS800via network840. User system850may correspond to, for example, a tenant of MTS800, a provider (e.g., an administrator) of MTS800, or a third party. Each user system850may be a desktop personal computer, workstation, laptop, PDA, cell phone, or any Wireless Access Protocol (WAP) enabled device or any other computing device capable of interfacing directly or indirectly to the Internet or other network connection. User system850may include dedicated hardware configured to interface with MTS800over network840. User system850may execute a graphical user interface (GUI) corresponding to MTS800, an HTTP client (e.g., a browsing program, such as Microsoft's Internet Explorer™ browser, Netscape's Navigator™ browser, Opera's browser, or a WAP-enabled browser in the case of a cell phone, PDA or other wireless device, or the like), or both, allowing a user (e.g., subscriber of a CRM system) of user system850to access, process, and view information and pages available to it from MTS800over network840. Each user system850may include one or more user interface devices, such as a keyboard, a mouse, touch screen, pen or the like, for interacting with a graphical user interface (GUI) provided by the browser on a display monitor screen, LCD display, etc. in conjunction with pages, forms and other information provided by MTS800or other systems or servers. As discussed above, disclosed embodiments are suitable for use with the Internet, which refers to a specific global internetwork of networks. It should be understood, however, that other networks may be used instead of the Internet, such as an intranet, an extranet, a virtual private network (VPN), a non-TCP/IP based network, any LAN or WAN or the like.

Because the users of user systems850may be users in differing capacities, the capacity of a particular user system850might be determined one or more permission levels associated with the current user. For example, when a salesperson is using a particular user system850to interact with MTS800, that user system850may have capacities (e.g., user privileges) allotted to that salesperson. But when an administrator is using the same user system850to interact with MTS800, the user system850may have capacities (e.g., administrative privileges) allotted to that administrator. In systems with a hierarchical role model, users at one permission level may have access to applications, data, and database information accessible by a lower permission level user, but may not have access to certain applications, database information, and data accessible by a user at a higher permission level. Thus, different users may have different capabilities with regard to accessing and modifying application and database information, depending on a user's security or permission level. There may also be some data structures managed by MTS800that are allocated at the tenant level while other data structures are managed at the user level.

In some embodiments, a user system850and its components are configurable using applications, such as a browser, that include computer code executable on one or more processing elements. Similarly, in some embodiments, MTS800(and additional instances of MTSs, where more than one is present) and their components are operator configurable using application(s) that include computer code executable on processing elements. Thus, various operations described herein may be performed by executing program instructions stored on a non-transitory computer-readable medium and executed by processing elements. The program instructions may be stored on a non-volatile medium such as a hard disk, or may be stored in any other volatile or non-volatile memory medium or device as is well known, such as a ROM or RAM, or provided on any media capable of staring program code, such as a compact disk (CD) medium, digital versatile disk (DVD) medium, a floppy disk, and the like. Additionally, the entire program code, or portions thereof, may be transmitted and downloaded from a software source, e.g., over the Internet, or from another server, as is well known, or transmitted over any other conventional network connection as is well known (e.g., extranet, VPN, LAN, etc.) using any communication medium and protocols (e.g., TCP/IP, HTTP, HTTPS, Ethernet, etc.) as are well known. It will also be appreciated that computer code for implementing aspects of the disclosed embodiments can be implemented in any programming language that can be executed on a server or server system such as, for example, in C, C+, HTML, Java, JavaScript, or any other scripting language, such as VBScript.

Network840may be a LAN (local area network), WAN (wide area network), wireless network, point-to-point network, star network, token ring network, hub network, or any other appropriate configuration. The global internetwork of networks, often referred to as the “Internet” with a capital “I,” is one example of a TCP/IP (Transfer Control Protocol and Internet Protocol) network. It should be understood, however, that the disclosed embodiments may utilize any of various other types of networks.

User systems850may communicate with MTS800using TCP/IP and, at a higher network level, use other common Internet protocols to communicate, such as HTTP, FTP, AFS, WAP, etc. For example, where HTTP is used, user system850might include an HTTP client commonly referred to as a “browser” for sending and receiving HTTP messages from an HTTP server at MTS800. Such a server might be implemented as the sole network interface between MTS800and network840, but other techniques might be used as well or instead. In some implementations, the interface between MTS800and network840includes load sharing functionality, such as round-robin HTTP request distributors to balance loads and distribute incoming HTTP requests evenly over a plurality of servers.

In various embodiments, user systems850communicate with application servers822to request and update system-level and tenant-level data from MTS800that may require one or more queries to data storage812. In some embodiments, MTS800automatically generates one or more SQL statements (the SQL query) designed to access the desired information. In some cases, user systems850may generate requests having a specific format corresponding to at least a portion of MTS800. As an example, user systems850may request to move data objects into a particular environment824using an object notation that describes an object relationship mapping (e.g., a JavaScript object notation mapping) of the specified plurality of objects.

Exemplary Computer System

Turning now toFIG.9, a block diagram of an exemplary computer system900, which may implement system100, database110, database node120, MTS800, and/or user system850, 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. 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 ML management module130may 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.).

The present disclosure includes references to “embodiments,” which are non-limiting implementations of the disclosed concepts. References to “an embodiment,” “one embodiment,” “a particular embodiment,” “some embodiments,” “various embodiments,” and the like do not necessarily refer to the same embodiment. A large number of possible embodiments are contemplated, including specific embodiments described in detail, as well as modifications or alternatives that fall within the spirit or scope of the disclosure. Not all embodiments will necessarily manifest any or all of the potential advantages described herein.

Unless stated otherwise, the specific embodiments are not intended to limit the scope of claims that are drafted based on this disclosure to the disclosed forms, even where only a single example is described with respect to a particular feature. The disclosed embodiments are thus intended to be illustrative rather than restrictive, absent any statements to the contrary. The application is intended to cover such alternatives, modifications, and equivalents that would be apparent to a person skilled in the art having the benefit of this disclosure.

Particular features, structures, or characteristics may be combined in any suitable manner consistent with this disclosure. The disclosure is thus intended to include any feature or combination of features disclosed herein (either explicitly or implicitly), or any generalization thereof. Accordingly, new claims may be formulated during prosecution of this application (or an application claiming priority thereto) to any such combination of features. In particular, with reference to the appended claims, features from dependent claims may be combined with those of the independent claims and features from respective independent claims may be combined in any appropriate manner and not merely in the specific combinations enumerated in the appended claims.

Where appropriate, it is also contemplated that claims drafted in one statutory type (e.g., apparatus) suggest corresponding claims of another statutory type (e.g., method).

References to the singular forms such “a,” “an,” and “the” are intended to mean “one or more” unless the context clearly dictates otherwise. Reference to “an item” in a claim thus does not preclude additional instances of the item.

When the term “or” is used in this disclosure with respect to a list of options, it will generally be understood to be used in the inclusive sense unless the context provides otherwise. Thus, a recitation of “x or y” is equivalent to “x or y, or both,” covering x but not y, y but not x, and both x and y. On the hand, a phrase such as “either x or y, but not both” makes clear that “or” is being used in the exclusive sense.

Various “labels” may proceed nouns in this disclosure. Unless context provides otherwise, different labels used for a feature (e.g., “first circuit,” “second circuit,” “particular circuit,” “given circuit,” etc.) refer to different instances of the feature. The labels “first,” “second,” and “third” when applied to a particular feature do not imply any type of ordering (e.g., spatial, temporal, logical, etc.), unless stated otherwise.

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. This unprogrammed FPGA may be “configurable to” perform that function, however.

Reciting in the appended claims that a structure is “configured to” perform one or more tasks is expressly intended not to invoke 35 U.S.C. § 112(f) for that claim element. Should Applicant wish to invoke Section 112(f) during prosecution, it will recite claim elements using the “means for” [performing a function] construct.

In this disclosure, various “modules” operable to perform designated functions are shown in the figures and described in detail above (e.g., ML management module130, key comparator module410, node inserter module420, etc.).