CN111373389B - Data storage system and method for providing data storage system - Google Patents

Abstract

The present invention provides a data storage system 100, which has a data storage 104 and a data controller 101, which is used to implement a prefix tree 600 with multiple nodes, wherein the data controller 101 is used to initiate in the prefix tree 600 Write operation; the data controller 101 is used to provide a lock for a single symbol among multiple symbols at nodes 602 and 603 under the write operation.

Description

Data storage system and method for providing data storage system

Technical field

The present invention relates to a data storage system and a method for providing a data storage system. More specifically, the present invention relates to a data storage system and method for improving the scalability of write operations among multiple writers.

Background technique

Data lookup is essential for all computer programs including information databases and storage systems. Programs need to quickly locate data for subsequent retrieval or calculations. Typically, such lookup capabilities are provided through index data structures that contain the corresponding locations or addresses of stored data organized by certain data attributes. Therefore, instead of traversing the entire stored data set, the corresponding index record is found. Common Index is a stand-alone tool with an efficient interface for quickly retrieving data locations by requested attributes.

In the presence of concurrency, several participants perform index modifications at the same time, and the overall operation efficiency depends largely on the method of concurrent synchronization. Typically, writers modify index structure records exclusively or in separate node replicas. Therefore, the index structure represents the complete and correct state of the stored data set. Synchronization of tree-based data structures is often considered a bottleneck.

Different tree-based index structures have been known for decades. Despite their different natures, many of them share certain characteristics, such as a single root node, internal nodes that are connected to each other to form the tree, and the final level of nodes, called leaves. Typically, the payload data is kept inside the leaves, and the internal nodes store some different attribute values that are selected during the traversal lookup.

Prefix trees are a special case of tree-based index data structures. Rather than storing attribute values within internal nodes, this information is stored within node interconnections. Therefore, during prefix tree traversal, there is no need to look at the child nodes one by one and compare the searched attribute values, but only select the child node corresponding to the attribute value index when it exists. Despite their apparent simplicity and concise traversal algorithm, such trees are not widely used in general-purpose database or storage system index structures due to their high memory overhead. In practice, each prefix tree node needs to hold the entire range of possible attribute values, even if only few such child nodes actually exist. The above implies that memory consumption increases exponentially.

In recent years, prefix trees have come into use for general purposes. The most important modification is to provide variable-sized nodes. This means that there are internal nodes of different capacities and a specific number of child nodes are selected during tree modification based on the number of child nodes required. This method is often called horizontal compression. Another valuable improvement consists in skipping all internal nodes with only a single child node, thereby requiring the common attributes to be saved inside the intermediate nodes and the search attributes to be stored within the corresponding leaves. This method is often called vertical compression or key-order skipping. Both improvements directly lead to more precise and modest memory consumption.

Another important issue with known prefix trees is the method of concurrent access or synchronization. Traditionally, synchronization techniques concatenate writers so that they simultaneously try to modify the same tree node, even if they change different parts of the node. Such solutions are simple but difficult to scale. More advanced techniques allow several writers to modify a tree node in parallel. However, they require complex data structures and are generally more complex to implement. An alternative that could be considered is to use hardware transactional memory, but there are still some obstacles in presenting proper hardware support when writing.

Typically, primitive prefix tree designs require large amounts of memory, so the use of such trees is very limited. The so-called Adaptive Radix Tree (ART) is an advanced design highly optimized for memory usage prefix trees. ART combines all known prefix tree compression techniques: instead of just one symbol per internal node, each internal node can contain several symbols, called co-prefixes, and key ordering is applied if the rest of the key is unique Skip to reduce the number of internal nodes. Additionally, each internal node has an adaptive size and increases or decreases based on the number of child nodes. Typically, in a prefix tree, modifications affect at most two nodes: the node where the change was made and possibly its parent. Therefore, there are generally several known concurrency control mechanisms that can be effectively applied to ART or prefix trees.

Lock coupling is a standard method for synchronizing B-trees and can be easily applied to prefix trees. The idea is to hold at most two locks at a time during tree traversal. Starting from the root node, each time you go down one level in the prefix tree, the lock on the child node is acquired, thereby releasing the parent lock. This method allows simultaneous modification of different prefix tree nodes when they have different parents. Lock coupling algorithms have the problem of high contention on the first level of the tree. Each participant starts at the root node, so there is high contention on level zero of the tree, and also high contention probability on level one.

Another approach is optimistic lock coupling. It is an enhanced lock coupling method with better performance. Rather than acquiring a lock at each step to prevent modifications to the node, each participant assumes that there will be no concurrent modifications. Detect modifications after using a version counter, and restart the operation if modifications are detected. Otherwise, up to two locks are required to perform modifications (for the node and parent). Optimistic lock coupling shows better performance because locks are acquired on demand and the total contention among tree nodes is not high. However, its main problem is coarse-grained locking. The coarse-grained lock blocks multiple tree nodes that are not actually performing any modifications. For example, if one actor locks a tree node, another actor cannot lock its child nodes because he also needs to lock the parent node.

Read-Optimized Write Exclusion (ROWEX) method shows better performance. Each internal node is extended with a layer field that indicates the total length of the key sequence at the node's layer. Through atomic modification of the prefix and prefix length, and atomic modification of the node pointer, the reader can work without any hindrance (locking, retries, etc.). Writers work similarly to writers in optimistic locking coupling, but perform additional actions to support readers in correctly reading the prefix tree in the state. For writers, ROWEX uses a locking method similar to optimistic lock coupling. Each writer has two exclusive locks on the tree node that needs to be modified and its parent node. The main difference is that the writer performs additional actions to allow the reader to work without locks. Most of these extra actions come from atomic updates to tree node fields that are important for the reader to read the tree correctly.

The Copy on Write (COW) method is usually used in lock-free algorithms. The key idea is to make a hidden copy of the modified node, then perform all changes on that copy and make it visible. Traditional locking, comparison and swap operations as well as node versioning can be used to implement COW. The COW method is suitable for read-oriented workloads, for example, a workload with 95% read operations and 5% write operations. The writer detects changes during preparation for tree node replication, restarts the operation, and redoes the copy. This type of additional memory copying and allocation can also lead to poor write performance. COW, on the other hand, can be used with locks to avoid restarts. In this case, the scalability of write operations is quite low. Also, for non-volatile memory, which is slower to write but has read speeds close to DRAM, the extra copy takes more time, so fine-grained locking may actually be faster.

Hardware Transactional Memory (HTM) is a hardware mechanism used to detect conflicts and undo any changes made to shared data. The goal of this hardware is to transparently support regions of code marked as transactions by enforcing atomicity, consistency, and isolation. In this scenario, all participants always observe a consistent state of the tree nodes because modifications are only performed within a transaction and are therefore visible to all participants only after a successful commit. When the commit operation fails, the modification needs to be restarted because the nodes have been changed at the same time. HTM is a very specialized piece of hardware that is not well supported yet, and there are not many opportunities to use it in production today.

Software Transactional Memory (STM) is a simulation of HTM on the machine without HTM support. However, optimally implementing STM requires a large number of compare-and-swap instructions to support (e.g., DCAS) operations, otherwise implementation of this approach is complex and extremely slow. Unfortunately, DCAS operations are only supported by the latest processors and are not widely available. Furthermore, in practice, the performance of STM systems suffers compared to systems based on fine-grained locks, mainly due to the overhead associated with maintaining logs and the time spent committing transactions.

Concurrent implementation of radix trees is complex because key compression can cause an indeterminate state to persist for a period of time until the tree transformation is complete. Simultaneous access to nodes by readers and writers needs to be handled appropriately to avoid an indeterminate state of the tree.

Due to key compression, it is necessary for a write operation to decompress part of the key in the current node and fork another path. This is the most complex situation and results in changes in the structure of the tree. For example, for adaptive radix trees, node extensions may need to be reallocated. Such operations are complex and typically require one writer to wait in a wait state until the other writer completes its write operation.

Contents of the invention

In view of the above problems and shortcomings, the present invention aims to improve the performance of prefix trees. Therefore, it is an object of the present invention to improve the scalability of write operations between multiple writers.

The object of the invention is achieved by the solution provided in the appended independent claims. Advantageous embodiments of the invention are further defined in the dependent claims.

Specifically, the present invention proposes a data storage system that includes a memory-efficient index data structure and a unique concurrency control method for synchronizing several writers, thereby providing high scalability when writing.

In databases and storage systems, the performance of the index data structure is very important and has a significant impact on the final performance. To support simultaneous access by data users, the index data structure is equipped with a concurrency control mechanism. Due to the extra overhead caused by known complex concurrency control mechanisms, the above concurrency control mechanisms become bottlenecks in the system. Even serialization of parallel access can sometimes have detrimental effects, limiting the scalability of the system on multi-core hardware. The present invention solves the scalability problem of the index data structure by improving the concurrency control mechanism of write operations.

The present invention can be regarded as a fine-grained locking method and is suitable for use as a concurrency control mechanism for prefix trees used as index data structures in databases and storage systems. The prefix tree can also apply vertical and horizontal compression, key order skipping, variable size nodes, and advanced synchronization between writers and readers. The tree operates within a uniform search domain of all words in a finite alphabet or string. The branching factor of a tree node is defined by the base of the alphabet. It can also include concepts such as variable node sizes, common node prefixes, and node locks, extending node locks with multi-symbol semantics. Variable node size technology allows the actual branching factor for a specific node to be determined based on actual needs. Common node prefixes enable vertical compression of radix trees in situations where child nodes share multiple symbols or prefixes within their keys.

Multi-symbol locks allow obtaining an exclusive lock on an entire node or a selective lock on a specific symbol of the alphabet within that node. The alphabet-specific symbol lock provides the facility to lock only one corresponding child node, while the exclusive locks all child nodes. The writer is then able to make simultaneous modifications to different child nodes of the same parent node. Furthermore, if these writers work for different symbols of the alphabet, insertions or deletions can be made in the same node at the same time. In more complex cases (which usually occur rarely), such as when the co-prefix needs to be changed or the variable node size should be expanded or reduced, the writer is still able to acquire an exclusive lock. The envisaged optimistic relaxed lock coupling synchronization method is an enhancement of the optimistic lock coupling scheme, which uses at most two exclusive locks for tree modifications of multi-symbol locks. This approach enables better scalability and better performance in concurrent environments.

A first aspect of the present invention provides a data storage system having a data memory and a data controller for implementing a prefix tree with a plurality of nodes, wherein the data controller is used to initiate a write operation in the prefix tree ; The data controller is used to provide a lock for a single symbol among multiple symbols at a node under a write operation.

One advantage of the invention is that, in addition to obtaining a fully exclusive lock, it is also possible to obtain a relaxed lock for only one symbol. For prefix trees, this means that even if multiple child nodes have the same parent, they can still be modified at the same time because their prefixes are actually different. Other advantages are that the present invention scales better than optimistic lock coupling using exclusive locks, achieving an average throughput gain of 30%, as tested on the benchmark model. Another advantage of the inventive method compared to the copy-on-write method is persistent memory.

The data storage system according to the present invention can bring several positive effects to concurrent databases and storage systems and other applications that rely heavily on index data structures, such as higher throughput, reduced operation latency, improved system scalability, and reduced CPU load.

In an implementation of the first aspect, the data controller is used to initiate the insertion or deletion of a specific node; the data controller is used to provide a lock for the specific node; to provide a parent node for the specific node. The lock is provided by a single symbol among multiple symbols that represents the particular node. This operation allows locking the child nodes under the operation, while only locking a single node at the parent node. Therefore, more than one child node of a single parent node can be modified simultaneously.

In another implementation of the first aspect, the data controller is configured to initiate a change to a single symbol among a plurality of symbols of a specific node; and provide a lock for the single symbol. This single-symbol lock allows multi-symbol operations at a single node because only the corresponding symbol is locked, rather than the entire node. Additionally, the parent node does not need to be locked.

In another implementation of the first aspect, the data controller is configured to provide a lock structure with a bit length of 0 to n-1 for a node, where n is a branching factor of the prefix tree, and where The data controller is configured to provide a lock for at least one bit of the lock structure. This lock structure allows full-scope locking of all symbols with resolution of a single symbol. This approach may increase memory usage. However, the integration complexity and execution time are approximately the same as the standard program.

In another implementation of the first aspect, the data controller is configured to provide a lock structure for a node, wherein the lock structure includes: a symbol segment, including a length of 0 to k-1 and used to store symbols. an array; the lock mask segment, the bit length is 0 to k–1; where, k<n, n is the branching factor of the prefix tree, wherein the data controller is used to provide the lock mask segment At least one bit of provides the lock. This lock structure allows the use of compact locks that can be used as a drop-in replacement for traditional locks. Although integration complexity may be higher, memory usage and execution time are approximately the same as the standard program.

In another implementation of the first aspect, the data controller is configured to: initiate a first write operation on a first node in the prefix tree; provide a lock for the first node; and provide a lock for the first node. A single symbol representing the first node at the parent node of a node provides a lock; wherein the data controller is used to initiate a second write to a second node in the prefix tree that has the same parent node as the first node. operate. Two parallel write operations can be performed on two child nodes of a common parent node. Start two writers to write simultaneously, allowing multiple wait-free write operations to occur at one point in time.

In another implementation of the first aspect, the data controller is configured to provide a lock for the second node; provide a lock for a single symbol at the parent node that represents the second node. The locking operation on the second symbol at the parent node is optional, for example, when there are only two concurrent write operations, the locking operation is not required. For more than two concurrent write operations, the corresponding symbol at the parent node is locked.

In another implementation of the first aspect, the data controller is configured to initiate a first write operation on a first symbol of a node in the prefix tree, wherein the first symbol represents a a first child node; providing a lock for the first symbol; wherein the data controller is configured to initiate a second write operation on a second symbol in the node, where the second symbol represents the node's first Two child nodes. Two concurrent writes can be made to two symbols at a node. Start two writers to modify multiple symbols at a node simultaneously, allowing multiple wait-free writes to occur at a single point in time.

In another implementation of the first aspect, the data controller is configured to provide a lock for the second symbol. The locking operation on the second symbol at the parent node is optional, for example, when there are only two concurrent write operations, the locking operation is not required. For more than two concurrent write operations, the corresponding symbol at the parent node is locked.

In another implementation of the first aspect, the data controller is configured to: provide a lock for a child node under a write operation; and represent a corresponding child node at all parent nodes of the child node under the write operation. A single symbol provides a lock such that only a single path to the child node under the write operation is locked. This definition of a single path to a single-symbol lock causes minimal damage to single-node modifications or writes to the tree. It leaves plenty of room for more concurrent write operations. In the existing technology, all subtrees need to be locked.

In another implementation of the first aspect, the data controller is configured to release a lock of a symbol and/or a node after completing the write operation. Once the modification is terminated, the release gives the opportunity for further writes to that particular node or symbol.

In another implementation of the first aspect, the data controller is configured to provide an exclusive lock for a particular node by locking the plurality of symbols at the particular node. The lock concept of this application still allows the use of exclusive locks, that is, locks of all symbols at the node.

In another implementation of the first aspect, the prefix tree is a radix tree or an adaptive radix tree. The lock concept of this application is very suitable for this kind of tree, because for radix trees, each node can represent several symbols.

A second aspect of the present invention provides a method for providing a data storage system for implementing a prefix tree having a plurality of nodes, the method comprising: initiating a write operation in the prefix tree; Provides a lock on a single symbol among multiple symbols at the node under write operation. The same modifications and advantages as above apply.

A third aspect of the invention provides a computer program having program code for performing a method as described above when the computer program is run on a computer or a data storage system as described above. The same modifications and advantages as above apply.

It should be noted that all devices, elements, units and structures described in this application may be implemented in software or hardware elements or any kind of combination thereof. All steps described in this application as being performed by various entities and functions described as being performed by the various entities are intended to indicate that the respective entities are suitable or useful for performing the respective steps and functions. Although in the following description of specific embodiments, specific functions or steps performed by an external entity are not reflected in the description of specific elements of the entity that perform the specific steps or functions, it should be clear to the skilled person that these methods and functions may be performed in implemented in their respective hardware or software components or any combination thereof.

Description of the drawings

In conjunction with the accompanying drawings, the following description of specific embodiments will illustrate various aspects of the invention and its implementation, wherein:

Figure 1 shows the system architecture diagram of a data storage system with an index structure.

Figure 2 shows a diagram of the full range lock structure.

Figure 3 shows an example of a 256-bit full range lock structure.

Figure 4 shows a diagram of the compact lock structure.

Figure 5 shows an example of a compact lock structure of 64-bit size.

Figure 6 shows an index tree with two concurrent write operations.

Figure 7 shows a flow chart of the key insertion algorithm.

Figure 8 shows a flow chart of the multi-symbol lock algorithm.

Figure 9 shows a flow chart of the full range lock algorithm.

Figure 10 shows a flow chart of the compact lock algorithm.

Figure 11 illustrates a method for providing a data storage system.

Detailed ways

Figure 1 shows a data storage system 100 including a data controller 101. The data controller 101 includes a concurrency control mechanism 102 for a prefix tree or radix tree with vertical compression and key order skipping used as the index data structure 103 . Data storage system 100 also includes data storage 104 . The data controller 101 can be implemented in the main memory using a dynamic random access memory (Dynamic Random Access Memory, DRAM), etc. The data memory 104 usually includes a large-capacity memory, such as a hard disk, a solid-state disk (Solid-State-Disk, SSD), etc. .

According to claim 1 of the present invention, the data storage system 100 includes a data controller 101 and a data memory 104.

Therefore, in order to quickly locate data, only the index corresponding to the requested index record in the index data structure 103 needs to be searched. Typically, index data structures organize raw data into logical units and retain the direct address of each unit on the storage medium, thereby minimizing interaction with the storage medium during data lookup.

Data users 111 may interact with the database or storage system via the network or the Internet and low-level device protocols, or may run on the same machine. Each data user can function as a writer 112 for adding and modifying data, or a reader 113 for finding and retrieving stored data 104 . In the presence of concurrency, when several participants 111 perform data lookups and modifications simultaneously, the overall operational efficiency depends largely on the method of concurrency synchronization or control 102 that aims to keep the stored data in a consistent state.

The data storage system 100 can be viewed as a variant of advanced synchronization between multiple writers 112, which is applicable as a concurrency control mechanism for the index or prefix tree used as the index data structure 103 in the data storage system 100 and information database. 102. This prefix tree based index data structure 103 can also be equipped with vertical compression, horizontal compression, key order skipping and advanced synchronization between the writer 112 and the reader 113.

The present invention provides a new prefix tree node locking tool: multi-symbol lock and its implementation: compact lock and full-range lock. For any alphabet, the maximum branching factor of a prefix tree node is actually equal to the alphabet base. However, tree modifications are mostly performed on a child node in the tree node. Therefore, in most cases, the mechanism of locking only a single child node is quite advantageous. Multi-symbol locks are designed for this purpose.

Figure 2 shows a full range lock structure 200. This full-range lock structure 200 has n bits, where n is the number of symbols in a given alphabet. For example, for C-style byte strings, use four 64-bit unsigned integers. The full range lock structure 200 may be in the form of an array with a bit length of 0 to n-1, where n is the branching factor of the prefix tree.

Figure 3 shows an example of a full-range lock structure 200 for a 256-bit C string. For better explanation, an ASCII table is provided on the right side of Figure 3. In the first example, full range lock structure 200a is unlocked. Therefore, all bits from 0 to 255 are set to 0. In the second example, full range lock structure 200b is locked exclusively. Therefore, all bits from 0 to 255 are set to 1. In a third example, in full range lock structure 200c, symbol d is locked. Therefore, all bits from 0 to 255 are set to 0 except bit 100 (representing the symbol d, see the ASCII table) which is set to 1. In a fourth example, in full range lock structure 200d, symbols d and K are locked. Therefore, all bits from 0 to 255 are set to 0 except bit 100 (representing the symbol d, see the ASCII table) and bit 75 (representing the symbol K, see the ASCII table), which are set to 1.

Figure 4 shows a compact lock structure 400. This compact lock structure 400 includes a symbol interval or segment 401 of nodes and a lock mask 402 . Symbol segment 401 may include an array of length 0 to k-1 for storing symbols, where n is the number of symbols in a given alphabet or the branching factor of a prefix tree. The bit length of the lock mask segment or lock mask 402 may be from 0 to k – 1, where k is a number less than n since there is a small possibility that all symbols need to be locked at once. When k equals n, the compact lock becomes the full-range lock because for each symbol there is a corresponding bit in the lock mask and no symbol gap segment is required. For the special case, that is, when lock mask 402 is used up, another write operation occurs, and the write operation must wait. The compact lock structure 400 requires a k-bit mask and k value intervals, each of which represents a symbol. It is a shortened version of the full range lock described. For example, for C-style byte strings, the most reasonable k values are 7 and 14. For k equal to 7, you can use a 64-bit unsigned integer, where the first byte is used as the bit and the other bytes are used as the value. Similarly, for k equal to 14, the compact lock can be represented using a 128-bit unsigned integer, where the first two bytes are used as bits and the other bytes are used as values.

The data controller 101 is configured to provide a lock for at least one bit of the lock mask segment 402.

Figure 5 shows an example of a compact lock structure 400 for a 64-bit size C string. In the first example, compact lock structure 400a is unlocked. Therefore, all bits from 0 to 6 are set to 0. In a second example, compact lock structure 400b is locked exclusively. Therefore, all bits from 0 to 6 are set to 1. In a third example, in compact lock structure 400c, symbol d is locked. Therefore, all bits from 0 to 6 are set to 0 except bit 1 (representing the symbol d) which is set to 1. The first bit of the lock mask 402 corresponds to the first interval of the symbol segment 401. In a fourth example, in compact lock structure 400d, symbols d and K are locked. Therefore, all bits from 0 to 6 are set to 0 except bit 1 (representing the symbol d) and bit 4 (representing the symbol K) which are set to 1.

For the detailed example of the multi-symbol lock implementation given above, the alphabet used in the example is a single-byte character set, each symbol is represented in 8 bits, and the entire alphabet base is 256 symbols. All symbols are used to form the input key string, the 255 non-zero bytes are the symbols used to encode the information, and the zero byte symbol indicates the end of the string. This approach is called C-style strings or null-terminated strings.

The prefix tree can apply key order skipping and vertical compression techniques. In this case, the inner nodes are extended with common prefix fields, while the leaf nodes store all keys. During tree traversal, if certain symbols are skipped, additional comparisons are required to ensure that a specific leaf node corresponds to the expected key. Additionally, internal nodes may be split or merged when the common prefix changes after an insertion or deletion. Adaptive branching factors are often applied to significantly reduce memory consumption. Internal nodes are updated with variable size intervals for child nodes, which can, for example, expand or contract to sizes 4, 16, 48, and 256 as needed. All memory optimization techniques make internal nodes complex, and it is not possible to automatically update all fields of an internal node on general purpose hardware. Therefore, an advanced synchronization mechanism is needed to build multi-threaded prefix trees.

Figure 6 shows a radix tree 600 with a root node 601, two internal nodes 602 and 603, and a leaf node 604. Combined with radix tree 600, the advantages of multi-symbol locking are explained. Instead of acquiring a fully exclusive lock, it is possible for a multi-symbol lock to acquire only a relaxed lock of one symbol. For prefix trees, this means that several child nodes can be modified simultaneously even if they have the same parent. Actually only their prefixes need to be different. A compact lock variant of the multi-symbol lock is used here.

Assume that first writer 605 and second writer 606 modify radix tree 600 simultaneously. On the left, actions are shown for a multi-symbol lock. For comparison, the functionality of a traditional fully exclusive lock is shown on the right.

First writer 605 modifies internal node 602. According to the present invention, the first writer 605 locks bit 607 at the root node 601, ie sets its value to 1. This bit 607 corresponds to symbol c (interval 608), which represents the symbol of node 602 under write operation. In addition, the first writer 605 exclusively locks all symbols of the node 602 under the write operation as indicated by all bits in the lock mask segment 402 that are set to 1.

At parent node 601, only one bit 607 is set. Therefore, the second writer 606 is able to perform a concurrent second write operation to another internal node 603 . Therefore, the second writer 606 locks bit 609 at the root node 601, ie, sets its value to 1. This bit 609 corresponds to the symbol r (interval 610), which represents the symbol of the node 603 under the second write operation. In addition, the second writer 606 exclusively locks all symbols of the node 603 under the write operation as indicated by all bits in the lock mask segment 402 that are set to 1.

The situation with the fully exclusive lock shown on the right is completely different. Among them, the second writer 606 that writes first completely locks the root node 601 and the internal node 603. Therefore, the first writer 605 needs to wait for the second writer 606 to complete the operation. In contrast, the present invention allows parallel write operations by writers 605 and 606.

Figure 7 depicts a flow chart of optimistically relaxed lock-coupling concurrency control for prefix tree insertion operations. To perform modifications, the writer initially follows the synchronization scheme chosen for the reader to traverse the tree and find the required key or location to insert a new node. To perform an insertion or deletion, the writer requires at most two locks: one for the node that has stopped traversing, and one for that node's parent. If necessary, the writer will always acquire a single-symbol lock on the corresponding symbol on the parent node. Therefore, other writers can modify different child nodes of the same parent node. Single-symbol locks on shared fields should also be used when child nodes can be inserted or deleted without affecting that node, for example, to add a new cotyledon node.

To apply the optimistically relaxed lock coupling approach to prefix trees, all internal nodes are expanded with multi-symbol locks. It can be one of the proposed implementations: compact lock or full-range lock. In general, the idea is to enhance optimistic locking coupling algorithms that exploit relaxed locks. That is, whenever possible, only lock a single symbol, rather than locking exclusively. This algorithm requires synchronization between concurrent writers to maintain the consistency of the prefix tree. To synchronize concurrent writers and readers, any known method can be used, such as node versioning based on atomic operations or a lock-free approach. Additionally, readers can apply classic lock coupling algorithms, where it is more reasonable to use single-symbol locks instead of exclusive ones.

In step 700, the process begins and proceeds to step 702, where the reader looks up the key and thereby acts as a reader. In step 703, it is determined whether the key is found. If found, the corresponding value is updated in step 704. Subsequently, the routine is terminated in exit step 705.

If the key is not found in step 703, the current node is selected for insertion in step 706. Then, in step 707, the corresponding single symbol in the parent node is locked. In step 708, it is determined whether the current node at the locked symbol is still a direct child of the parent node. If not, in step 709, a new node is inserted and the symbol in the parent node is unlocked, and in step 702, the procedure is restarted.

The routine branches from node 708 to node 710 when the current node is still a direct child of the parent node at the locked symbol. Among them, determine whether node conversion is required. If necessary, the complete active node is locked in step 711 since the entire node is affected by the modification. If not required, only the symbol in the current node is locked in step 712, since only this symbol is affected by the modification. In both cases, the corresponding insertion is performed in step 713. Before exiting the program in step 705, all acquired locks are unlocked in step 714.

Figure 8 depicts four flowcharts of the multi-symbol lock algorithm supporting four main operations. The multi-symbol lock algorithm can be implemented by a full-range lock algorithm (explained later in conjunction with Figure 9) or a compact lock algorithm (explained later in conjunction with Figure 10).

According to the first algorithm starting from step 800, an exclusive lock is acquired. In step 801, the lock status is obtained or observed. In step 802, it is determined whether any locks have been held, ie, whether some kind of lock has been set. If so, the operation returns to step 801, thereby forming a loop for observing the lock status. If not, the exclusive lock is set in step 803, as described above. Finally, in step 804, the routine is exited with the exclusive lock set at the corresponding node.

According to the second algorithm starting at step 810, the exclusive lock is released. In step 810, it is described how to release the set exclusive lock. In step 811, the exclusive lock is released. How this operation is actually performed depends on the algorithm used. Either the full-range locking algorithm or the compact locking algorithm can be used. Finally, in step 812, the routine is exited with the lock released at the corresponding node.

According to the third algorithm starting from step 820, a single symbol lock is acquired. In step 821, the lock status is obtained or observed. In step 822, it is determined whether the exclusive lock has been held. If so, the operation returns to step 821, forming a loop that observes the lock status of the node. If not, go to step 823. In step 823, it is determined whether the current symbol has been locked. If so, the operation returns to step 821, forming a loop that observes the lock state of the symbol. If not, the single symbol lock is set in step 824, as described above. Finally, in step 825, the routine is exited with the single symbol lock set at the corresponding node.

According to the fourth algorithm starting at step 830, the single symbol lock is released. In step 831, the single symbol lock is released. How this operation is actually performed depends on the algorithm used. Either the full-range locking algorithm or the compact locking algorithm can be used. Finally, in step 832, the routine is exited with the lock released at the corresponding node.

Figure 9 shows five full-range locking algorithms. A full-range lock is physically represented as a memory block of length n bits, as shown in Figure 2. Each bit i (i is 0 to n–1) corresponds to a symbol of the alphabet with code i. The full-scope lock is a precise solution that provides maximum scalability, but may consume more memory than traditional locks.

According to the first algorithm starting from step 900, an exclusive lock is acquired. In step 901, the lock value is read, and in step 902, it is determined whether the lock value is equal to 0. If not, the operation returns to step 901, thereby forming a loop for reading the lock value. If so, in step 903, all n bits are set to the lock value 1, thereby setting or acquiring the exclusive lock. Finally, in step 904, the routine is exited with the exclusive lock set at the corresponding node.

According to the second algorithm starting from step 910, the exclusive lock is actively acquired. This algorithm will not allow other participants to acquire a single-symbol lock when a participant attempts to acquire an exclusive lock, that is, an exclusive lock has a higher priority than a single-symbol lock. In step 911, the n-bit local variable remainder mask is initialized by setting all n bits to 1. The remaining mask bits represent the bits of the lock that still need to be acquired. In step 912, the lock value is read, and in step 913, the remaining mask bits are updated bitwise by performing an AND operation using the lock value. In step 914, all bits are set to the lock value of 1. In step 915, it is determined whether the remaining mask value is equal to 0, indicating that all bits of the lock are held. If not, the operation returns to step 912 to restart updating of the remaining mask bits. If so, in step 916, the routine is exited with the exclusive lock set at the corresponding node.

According to the third algorithm starting at step 920, the exclusive lock is released. In step 921, the lock is released. To release the exclusive lock, n bits are all set to 0. Finally, in step 922, the routine is exited with the lock released at the corresponding node.

According to the fourth algorithm starting from step 930, a single symbol lock is acquired. In step 931, local variable i is set to the symbol code, thereby selecting the corresponding symbol. In step 932, the lock value is read. In step 933, it is determined whether the i bit is found. If so, the operation returns to step 932, forming a loop that reads the lock value. If not, in step 934, the i bit is set to the lock value 1, thereby setting or acquiring the single symbol lock. Finally, in step 935, the routine is exited with the single symbol lock set at the corresponding node.

According to the fifth algorithm starting at step 940, the single symbol lock is released. In step 941, local variable i is set to the symbol code, thereby selecting the corresponding symbol. In step 942, the i bit is set to a lock value of 0, thereby releasing the single symbol lock. Finally, in step 943, the routine is exited with the single symbol lock released at the corresponding node.

Figure 10 shows five compact locking algorithms. Compact locks are optimized for memory consumption, but may result in slightly less scalability. The compact locks can utilize the same amount of memory as traditional locks, serving as their drop-in replacement. Figure 4 shows the representation of a compact lock in memory as several intervals of symbols and bit masks. The number of intervals k is also the number of bits in the mask, where k < n. Each interval represents the storage of a single locked symbol and must be large enough to represent the symbols of the alphabet. Each bit in the mask indicates whether the corresponding signed interval is locked.

According to the first algorithm starting from step 1000, an exclusive lock is acquired. In step 1001, the lock mask is read, and in step 1002, it is determined whether the lock mask is equal to 0. If not, the operation returns to step 1001, thereby forming a loop for reading the lock mask. If so, in step 1003, all n bits of the lock mask are set to 1, thereby setting or acquiring the exclusive lock. During the setting of all k bits in the mask, the part of the gap that holds the symbol is ignored. Finally, in step 1004, the routine is exited with the exclusive lock set at the corresponding node.

According to the second algorithm starting from step 1010, the exclusive lock is actively acquired. This algorithm will not allow other participants to acquire a single-symbol lock when a participant attempts to acquire an exclusive lock, that is, an exclusive lock has a higher priority than a single-symbol lock. In step 1011, the k-bit local variable remainder mask is initialized by setting all k bits to 1. The remaining mask bits represent the bits of the lock mask that still need to be acquired. In step 1012, the lock mask is read, and in step 1013, the remaining mask bits are updated bitwise by performing an AND operation using the lock mask. In step 1014, all bits of the lock mask are set to a lock value of 1. During the setting of all k bits in the mask, the part of the gap that holds the symbol is ignored. In step 1015, it is determined whether the remaining mask value is equal to 0, indicating that all bits of the lock mask are maintained. If not, the operation returns to step 1012 to restart the updating of the remaining mask bits. If so, in step 1016, the routine is exited with the exclusive lock set at the corresponding node.

According to the third algorithm starting from step 1020, the exclusive lock is released. In step 1021, the lock mask is set to 0 by zeroing out all k bits in the mask, thereby ignoring the portion of the gap that holds the symbol. Finally, in step 1022, the routine is exited with the exclusive lock released at the corresponding node.

According to the fourth algorithm starting from step 1030, a single symbol lock is acquired. In step 1031, local variable i is set to the symbol code, thereby selecting the corresponding symbol.

In step 1032, the lock mask is read, and in step 1033, each bit in the lock mask is iterated until there are more bits. In steps 1034 and 1035, if the current bit in the lock mask is set (step 1034) and the corresponding symbol interval value is equal to i (step 1035), the operation returns to step 1032 to form the read The loop of the lock mask, otherwise, the operation returns to step 1033 and continues to the next bit in the lock mask. If there are no more bits (step 1033), operation proceeds to step 1036. In step 1036, it is determined whether there are any unset j bits in the lock mask. If not, the compact lock is full and operation returns to step 1032 to retry the lock. Optionally, the operation in step 1036 may search for unset bits in the lock mask starting from a random index or starting from the symbol code mod k to reduce what may happen when several writers try to occupy the first available zero bit number of conflicts.

Therefore, all intervals that have the corresponding bit set in the lock mask are scanned to ensure that the symbol has not been locked. Accordingly, look for any bit j that is not set in the lock mask, j being 0 to k–1.

If it is determined in step 1036 that there are j bits that are not set, the operation proceeds further to step 1037, where the j bits in the lock mask are set and the symbol interval j is set to i. In other words, bit j in the lock mask is set and the symbol is stored in interval j. In optional step 1038, a j value is returned, which can be used to later release the single symbol lock. Finally, in step 1039, the routine is exited with the single symbol lock set at the corresponding node.

According to the fifth algorithm starting at step 1040, the single symbol lock is released. In step 1041, it is determined whether optional parameter index j is provided. If not provided, in step 1042, the local variable i is set to the symbol code, thereby selecting the corresponding symbol. In step 1043, scan all intervals in which the corresponding bits are set in the mask to find j bits with a symbol interval j in which symbol i is present, i being a symbol code from 0 to n-1 . In step 1044, the j bits of the found lock mask are zeroed by setting them to zero, thereby ignoring the symbol gap. After determining in step 1041 that optional parameter index j is provided, the operation proceeds to step 1044. Finally, in step 1045, the routine is exited with the single symbol lock released at the corresponding node.

Figure 11 shows a method for providing a data storage system 100 according to claim 14.

According to a first step 1100, a data storage system 100 is provided for implementing a prefix tree with a plurality of nodes. In step 1101, a write operation is initiated in the prefix tree. In step 1102, a lock is provided for a single symbol of the plurality of symbols at the node under the write operation.

The invention has been described in connection with different embodiments and implementations as examples. However, other variations will be apparent to those skilled in the art in practicing the claimed invention, from a study of the drawings, the disclosure and the independent claims. In the claims and description, the word "comprising" does not exclude other elements or steps, and the indefinite article "a" or "an" does not exclude a plurality. A single element or other unit may fulfill the functions of several entities or items recited in a claim. The mere fact that certain measures are recited in mutually different dependent claims does not mean that a combination of these measures cannot be used to advantageous implementations.

Claims (13)

1. A data storage system (100), characterized by having a data memory (104) and a data controller (101) for implementing a prefix tree (600) with multiple nodes, wherein The data controller (101) is used to initiate a write operation in the prefix tree (600); The data controller (101) is configured to provide a lock for a single symbol among a plurality of symbols at a node (602, 603) under a write operation; The data controller (101) is specifically configured to: provide a lock structure with a bit length of 0 to n-1 for a node, where n is a branching factor of the prefix tree (600), and the lock structure includes: a symbol segment (401), including an array with a length of 0 to k–1 for storing symbols; a lock mask segment (402) with a bit length of 0 to k–1, where k<n, the data controller (101 ) is used to provide a lock for at least one bit of the lock mask segment (402). 2. The data storage system (100) according to claim 1, characterized in that The data controller (101) is used to initiate the insertion or deletion of a specific node; The data controller (101) is configured to provide a lock for the specific node; provide a lock for a single symbol representing the specific node among multiple symbols at a parent node of the specific node. 3. Data storage system (100) according to claim 1 or 2, characterized in that The data controller (101) is configured to initiate changes to a single symbol among multiple symbols of a specific node; and provide a lock for the single symbol. 4. Data storage system (100) according to any one of claims 1 to 3, characterized in that The data controller (101) is configured to: initiate a first write operation on the first node in the prefix tree (600); provide a lock for the first node; and represent the parent node of the first node. A single symbol of the first node provides the lock; where The data controller (101) is configured to initiate a second write operation on a second node in the prefix tree (600) that has the same parent node as the first node. 5. The data storage system (100) according to claim 4, characterized in that The data controller (101) is configured to provide a lock for the second node; provide a lock for a single symbol representing the second node at the parent node. 6. Data storage system (100) according to any one of claims 1 to 5, characterized in that The data controller (101) is configured to initiate a first write operation on the first symbol of a node in the prefix tree (600), where the first symbol represents the first child node of the node; for the The first symbol provides the lock; where The data controller (101) is configured to initiate a second write operation on a second symbol in the node, where the second symbol represents a second child node of the node. 7. Data storage system (100) according to claim 6, characterized in that The data controller (101) is configured to provide a lock for the second symbol. 8. Data storage system (100) according to any one of claims 1 to 7, characterized in that The data controller (101) is configured to: provide a lock for a child node under a write operation; provide a lock for a single symbol representing a corresponding child node at all parent nodes of the child node under the write operation, so that only locks to A single path to the child node under the write operation. 9. Data storage system (100) according to any one of claims 1 to 8, characterized in that The data controller (101) is configured to release the lock of the symbol and/or node after completing the write operation. 10. Data storage system (100) according to any one of claims 1 to 9, characterized in that The data controller (101) is configured to provide an exclusive lock for a specific node by locking multiple symbols at the specific node. 11. Data storage system (100) according to any one of claims 1 to 10, characterized in that The prefix tree (600) is a radix tree or an adaptive radix tree. 12. A method for providing a data storage system (100), characterized in that the data storage system (100) is used to implement a prefix tree (600) with a plurality of nodes, the method comprising: Initiate a write operation in the prefix tree (600); Provides a lock on a single symbol among multiple symbols at node (602, 603) under write operation; Providing a lock for a single symbol among multiple symbols at a node (602, 603) under a write operation includes: providing a lock structure with a bit length of 0 to n-1 for the node, where n is the prefix tree ( 600), the lock structure includes: a symbol segment (401), including an array with a length of 0 to k–1 and used to store symbols; a lock mask segment (402), with a bit length of 0 to k–1 , where k<n, the data controller (101) is used to provide a lock for at least one bit of the lock mask segment (402). 13. A computer-readable storage medium, characterized by storing a computer program for running on a computer or the data storage system (100) of any one of claims 1 to 11, The method of claim 12 is performed.