CN115114294A - Adaptive method, device and computer equipment for database storage mode - Google Patents

Abstract

The application relates to a database storage mode self-adaption method, a database storage mode self-adaption device, computer equipment, a storage medium and a computer program product. The method comprises the following steps: acquiring operating parameters of a workload and read-write operation performance parameters of each key value pair; the operation parameters comprise read-write operation proportion, query statements and data distribution; determining a first space size of a space occupied by the key value pair according to the read-write operation proportion and the read-write operation performance parameter; determining a partition mode of a storage area according to the semantic information of the query statement; determining data density under a candidate grouping range according to the data distribution; determining a storage mode of a data table in a database when the workload is running based on the partition mode, the candidate grouping range, the data density and the first space size. By adopting the method, the overall performance of the database system can be effectively improved.

Description

Adaptive method, device and computer equipment for database storage mode

technical field

The present application relates to the field of computer technology, and in particular, to an adaptive method, apparatus, computer device, storage medium and computer program product for a database storage mode.

Background technique

With the development of computer technology and Internet technology, data has become the core asset of an enterprise, and data protection is one of the effective means to protect enterprise assets. When storing data, row-based or column-based storage modes are usually used, so that these storage modes can improve the read-write (I/O) performance of the database when processing queries under certain workloads.

However, in the current adaptive mode of database storage mode, because the storage mode is limited by row storage and column storage, and parameter adjustment mostly depends on hardware configuration and query characteristics, it is impossible to adjust the underlying basic configuration such as storage mode. Therefore, it is easy to make the final selected storage mode often not optimal, which may cause relatively large storage overhead or even waste of space, resulting in poor overall performance of the database system.

SUMMARY OF THE INVENTION

Based on this, it is necessary to provide an adaptive method, apparatus, computer equipment, computer-readable storage medium and computer program product for the database storage mode, which can effectively improve the overall performance of the database system.

In a first aspect, the present application provides an adaptive method for a database storage mode. The method includes: obtaining operating parameters of the workload and read-write operation performance parameters of each key-value pair; the operating parameters include read-write operation ratio, query statement and data distribution; according to the read-write operation ratio and the read-write operation ratio Write operation performance parameters, determine the first space size of the space occupied by the key-value pair; determine the partition mode of the storage area according to the semantic information of the query statement; determine the data density in the candidate grouping range according to the data distribution; Based on the partition mode, the candidate grouping range, the data density, and the first space size, a storage mode of a data table in the database is determined when the workload is running.

In a second aspect, the present application also provides an adaptive device for a database storage mode. The device includes: an acquisition module for acquiring operating parameters of the workload and read-write operation performance parameters of each key-value pair; the operating parameters include read-write operation ratio, query statement and data distribution; a determination module, used for according to The read-write operation ratio and the read-write operation performance parameter determine the first space size of the space occupied by the key-value pair; determine the partition mode of the storage area according to the semantic information of the query statement; The distribution determines the data density under the candidate grouping range; based on the partition mode, the candidate grouping range, the data density and the first space size, determines the storage mode of the data table in the database when the workload is running.

In a third aspect, the present application also provides a computer device. The computer device includes a memory and a processor, the memory stores a computer program, and the processor implements the following steps when executing the computer program: acquiring the operating parameters of the workload and the read-write operation performance parameters of each key-value pair; The operating parameters include read-write operation ratio, query statement and data distribution; according to the read-write operation ratio and the read-write operation performance parameter, determine the first space size of the space occupied by the key-value pair; according to the The semantic information of the query statement is used to determine the partition mode of the storage area; the data density in the candidate grouping range is determined according to the data distribution; based on the partition mode, the candidate grouping range, the data density and the first space size , which determines the storage mode of the data tables in the database when running the workload.

In a fourth aspect, the present application also provides a computer-readable storage medium. The computer-readable storage medium has a computer program stored thereon, and when the computer program is executed by the processor, the following steps are implemented: obtaining the operating parameters of the workload and the read-write operation performance parameters of each key-value pair; the operating parameters Including read-write operation ratio, query statement and data distribution; according to the read-write operation ratio and the read-write operation performance parameter, determine the first space size of the space occupied by the key-value pair; according to the semantics of the query statement information, determine the partition mode of the storage area; determine the data density under the candidate grouping range according to the data distribution; The workload is the storage mode of the data table in the database.

In a fifth aspect, the present application also provides a computer program product. The computer program product includes a computer program, and when the computer program is executed by the processor, the following steps are implemented: obtaining the operation parameters of the workload and the read-write operation performance parameters of each key-value pair; the operation parameters include the read-write operation ratio, query statement and data distribution; determine the first space size of the space occupied by the key-value pair according to the read-write operation ratio and the read-write operation performance parameter; determine the size of the storage area according to the semantic information of the query statement Partitioning mode; determining the data density under the candidate grouping range according to the data distribution; determining the database when running the workload based on the partitioning mode, the candidate grouping range, the data density and the first space size The storage mode of the data table in .

The self-adaptive method, device, computer equipment, storage medium and computer program product of the above-mentioned database storage mode are obtained by obtaining the operation parameters of the workload and the read-write operation performance parameters of each key-value pair; the operation parameters include the read-write operation ratio, the query statement and data distribution; determine the first space size of the space occupied by key-value pairs according to the ratio of read and write operations and performance parameters of read and write operations; determine the partition mode of the storage area according to the semantic information of the query statement; determine the candidate grouping range according to the data distribution The data density under the data density; based on the partition method, the candidate grouping range, the data density and the first space size, determine the storage mode of the data table in the database when the workload is running. Since the read-write operation performance parameters of each key-value pair are obtained through pre-testing, the key-value pair can be determined based on the read-write operation ratio in the operating parameters of different workloads and the read-write operation performance parameters of each key-value pair obtained by the pre-test. The optimal value range of the space occupied by the value pair, so that the server can determine the database when running different workloads based on the partition mode, candidate grouping range, data density, and the optimal value range of the space occupied by the key-value pair. The optimal storage mode of the data table in the data table solves the problem that the traditional method cannot match the optimal storage mode according to different loads, and effectively improves the I/O efficiency of the system, thereby effectively improving the overall performance of the system.

Description of drawings

Fig. 1 is the application environment diagram of the adaptive method of database storage mode in one embodiment;

2 is a schematic flowchart of an adaptive method for a database storage mode in one embodiment;

Fig. 3 is the schematic diagram of the structure change of data table in one embodiment;

Fig. 4 is the conversion schematic diagram of the storage mode in one embodiment;

5 is a schematic diagram of a column segment memory mode in one embodiment;

6 is a schematic diagram of a column family segment storage mode in one embodiment;

FIG. 7 is a schematic diagram of the entire table storage mode in one embodiment;

Fig. 8 is the overall architecture diagram of the system in one embodiment;

9 is a schematic diagram of cell row storage in one embodiment;

10 is a schematic diagram of cell column storage in one embodiment;

11 is a schematic diagram of multi-line storage in one embodiment;

12 is a schematic diagram of a column family memory storage format in one embodiment;

13 is a schematic diagram of an encoding scheme of a diversified storage mode in one embodiment;

FIG. 14 is a flow diagram of storage mode adaptation processing in one embodiment;

15 is a structural block diagram of an apparatus for adapting a database storage mode in one embodiment;

Figure 16 is a diagram of the internal structure of a computer device in one embodiment.

Detailed ways

In order to make the purpose, technical solutions and advantages of the present application more clearly understood, the present application will be described in further detail below with reference to the accompanying drawings and embodiments. It should be understood that the specific embodiments described herein are only used to explain the present application, but not to limit the present application.

The adaptive method for the database storage mode provided by the embodiment of the present application can be applied to the application environment shown in FIG. 1 . The terminal 102 communicates with the server 104 through the network. The data storage system may store data that the server 104 needs to process. The data storage system can be integrated on the server 104, or it can be placed on the cloud or other servers. The server 104 can obtain the operating parameters of the workload and the read-write operation performance parameters of each key-value pair from the terminal 102, and the operating parameters include the read-write operation ratio, query statement and data distribution; the server 104 can obtain the read-write operation ratio and the read-write operation performance according to the parameter, determine the first space size of the space occupied by the key-value pair; the server 104 determines the partition mode of the storage area according to the semantic information of the query statement; further, the server 104 determines the data density under the candidate grouping range according to the data distribution, and based on The partition mode, candidate grouping range, data density, and first space size determine the storage mode of the data table in the database when the workload is running.

The terminal 102 can be, but is not limited to, various desktop computers, notebook computers, smart phones, tablet computers, IoT devices and portable wearable devices, and the IoT devices can be smart speakers, smart TVs, smart air conditioners, smart vehicle-mounted devices, etc. . The portable wearable device may be a smart watch, a smart bracelet, a head-mounted device, or the like. The server 104 can be implemented by an independent server or a server cluster composed of multiple servers.

It can be understood that the server 104 provided in the embodiment of the present application may also be a service node in a blockchain system, and each service node in the blockchain system forms a peer-to-peer (P2P, Peer To Peer) network, and the P2P protocol is An application layer protocol that runs on top of the Transmission Control Protocol (TCP, Transmission Control Protocol).

Cloud technology is a general term for network technology, information technology, integration technology, management platform technology, application technology, etc. based on the application of cloud computing business models. It can form a resource pool, which can be used on demand, flexible and convenient. Cloud computing technology will become an important support. Background services of technical network systems require a lot of computing and storage resources, such as video websites, picture websites and more portal websites. With the high development and application of the Internet industry, in the future, each item may have its own identification mark, which needs to be transmitted to the back-end system for logical processing. Data of different levels will be processed separately, and all kinds of industry data need to be strong. The system backing support can only be achieved through cloud computing.

Cloud computing is a computing model that distributes computing tasks on a resource pool composed of a large number of computers, enabling various application systems to obtain computing power, storage space and information services as needed. The network that provides the resources is called the "cloud". The resources in the "cloud" are infinitely expandable in the eyes of users, and can be obtained at any time, used on demand, expanded at any time, and paid for according to usage.

As a basic capability provider of cloud computing, it will establish a cloud computing resource pool (referred to as cloud platform, generally called IaaS (Infrastructure as a Service) platform, and deploy various types of virtual resources in the resource pool for External customers choose to use. The cloud computing resource pool mainly includes: computing devices (which are virtualized machines, including operating systems), storage devices, and network devices.

According to the division of logical functions, the PaaS (Platform as a Service) layer can be deployed on the IaaS (Infrastructure as a Service) layer, and the SaaS (Software as a Service) layer can be deployed on the PaaS layer. service) layer, or directly deploy SaaS on IaaS. PaaS is a platform on which software runs, such as databases and web containers. SaaS is a variety of business software, such as web portals, SMS group senders, etc. Generally speaking, SaaS and PaaS are upper layers relative to IaaS.

Cloud storage is a new concept extended and developed from the concept of cloud computing. Distributed cloud storage system (hereinafter referred to as storage system) refers to functions such as cluster application, grid technology and distributed storage file system. A storage system that integrates a large number of different types of storage devices (also called storage nodes) in the network through application software or application interfaces to work together to provide external data storage and service access functions.

At present, the storage method of the storage system is as follows: creating a logical volume, and when creating a logical volume, a physical storage space is allocated to each logical volume, and the physical storage space may be composed of a storage device or disks of several storage devices. The client stores data on a logical volume, that is, stores the data on the file system. The file system divides the data into many parts, each part is an object, and the object contains not only data but also data identification (ID, ID entity) and other additional information, the file system writes each object into the physical storage space of the logical volume, and the file system records the storage location information of each object, so that when the client requests to access data, the file system can The storage location information of the object allows the client to access the data.

The process of allocating physical storage space by the storage system to the logical volume, specifically: according to the capacity estimation of the objects stored in the logical volume (this estimation often has a large margin relative to the actual capacity of the objects to be stored) and independent redundant disks Array (RAID, Redundant Array of Independent Disk) group, which divides the physical storage space into stripes in advance, and a logical volume can be understood as a stripe, thereby allocating physical storage space for the logical volume.

With the research and progress of artificial intelligence technology, artificial intelligence technology has been researched and applied in many fields, such as common smart homes, smart wearable devices, virtual assistants, smart speakers, smart marketing, unmanned driving, autonomous driving, drones , robots, intelligent medical care, intelligent customer service, Internet of Vehicles, autonomous driving, intelligent transportation, etc. It is believed that with the development of technology, artificial intelligence technology will be applied in more fields and play an increasingly important value.

In one embodiment, as shown in FIG. 2, an adaptive method for a database storage mode is provided, and the method is applied to the server in FIG. 1 as an example to illustrate, including the following steps:

Step 202: Acquire operating parameters of the workload and performance parameters of read and write operations of each key-value pair; the operating parameters include the ratio of read and write operations, query statements, and data distribution.

The workload refers to each workload running on the database. The database in this application can be a relational database, the structure of each data table in the relational database is pre-configured, and the structure of the database can be a distributed database. The workloads in this application may include different types of workloads. For example, OLTP (On-Line Transaction Processing) type workloads have many write operations to data, and OLAP (On-Line Analytical Processing) operations generally have many range query operations. OLTP (On-Line Transaction Processing) is one of the ways to quickly respond to user operations. The basic feature is that the user data received by the front desk can be immediately sent to the computing center for processing, and the processing results can be given in a short time. OLAP (On-Line Analytical Processing) is a software mechanism for high-speed multi-dimensional analysis of large amounts of data from a data warehouse, data mart, or some other unified centralized data store.

The running parameters of the workload refer to the parameters when the workload runs normally on the database. For example, the running parameters can include the proportion of each I/O operation in the workload, all the query statements involved in the workload, and the data corresponding to the workload. Distribution.

Key-value refers to (Key-Value, abbreviated as KV). In this application, data is organized, indexed and stored in the form of key-value pairs, that is, in the storage engine, key-value pairs are used as the basic unit of storage.

The performance parameters of read and write operations refer to the performance parameters corresponding to each I/O operation. For example, for the check operation in the I/O operation, the delay time of a 16B KV pair is 0.01ms, and the delay of a 32B KV pair is 0.01ms. The time is 0.005ms, and the delay time is the performance parameter corresponding to the check operation.

The ratio of read and write operations refers to the ratio of each I/O operation in the workload. For example, the corresponding ratio of single-point query operations, update operations, insert operations, delete operations, and range query operations for workload A within a preset time period.

Query statements refer to all query statements involved in the workload. For example, the running parameters may include the proportion of query statements and the meta information involved in each query statement.

Data distribution refers to the distribution of data in the workload, for example, the range of primary keys and the corresponding proportions. Specifically, the server may acquire the running parameters of a certain workload within a preset period of time when it is running normally in the database, and the storage mode in the database at this time may be any storage mode. In general, the line memory mode can be selected as the benchmark mode for testing. In this step, the running parameters that need to be collected include the following three types: First, the proportion of each I/O operation in the workload, such as single-point query operations, update operations, insert operations, delete operations, and range query operations. The corresponding proportion; the second is the proportion of all query statements involved in the workload, and the meta information corresponding to the columns involved; the third is the data distribution in the workload, such as the range of primary keys and the corresponding proportion. Further, the server may obtain the read/write operation performance parameters of key-value pairs occupying different space sizes from the pre-established performance model. The performance parameter may include at least one of delay time, bandwidth, or IOPS (Input/Output Operations Per Second).

For example, assuming that the current workload A contains 1000 point query operations, 10 full table scan operations involving 100,000 rows, 1000 update operations, 1000 insert operations, and 10 delete operations, the server obtains the The running parameters of workload A include 1,000 point query operations, 10 full table scan operations involving 100,000 rows, 1,000 update operations, 1,000 insert operations, and 10 delete operations. Further, the server can obtain the performance of each size KV pair under different I/O operations from the pre-established performance model. For example, the server obtains a delay time of 0.01 for a 16B KV pair in the check operation. ms, the delay time of 32B size KV pair is 0.005ms, and the delay time of 48B size KV pair is 0.009ms.

Step 204: Determine the first space size of the space occupied by the key-value pair according to the read-write operation ratio and the read-write operation performance parameter.

The first space size refers to the value range of the space occupied by the key-value pair with the best overall performance of the selected workload. Therefore, it can be determined that the first space size of the space occupied by the key-value pair is 16B.

Specifically, after the server obtains the operating parameters of the workload and the read-write operation performance parameters of each key-value pair, the server can estimate the read-write operation ratio and the read-write operation performance parameters of each key-value pair contained in the operating parameters. The overall performance of the current workload under each KV pair size, and then the server can select the KV pair size with the highest overall performance from it, as the first space size of the space occupied by the key-value pair set by the system. Since the size of the space occupied by the key-value pair has a great impact on the performance of the storage system, it is necessary to estimate the most suitable KV pair size according to the proportion of each I/O operation in the current workload. Generally, KV pairs with large granularity are more suitable for processing full table scan operations, and KV pairs with small granularity are more suitable for processing single-point query, update, insert, delete and other operations.

For example, assuming that the current workload A contains 1000 point query operations, 10 full table scan operations involving 100,000 rows, 1000 update operations, 0 insert operations, and 0 delete operations, the server obtains the The running parameters of workload A include 1,000 point query operations, 10 full table scan operations involving 100,000 rows, 1,000 update operations, 0 insert operations, and 0 delete operations. Further, the server can obtain the performance of each size KV pair under different I/O operations from the pre-established performance model. For example, the server obtains a delay time of 0.01 for a 16B KV pair in the check operation. ms, the delay time of a 32B-sized KV pair is 0.005ms, and the 48B-sized KV pair’s delay time is 0.009ms, then the server can estimate the time-consuming of the 16B KV pair in the current workload A in the check operation. t _a1 is 1000*0.01ms, the time consuming t _a2 of the 32B KV pair in the enumeration operation is 1000*0.05ms, and the time consuming t _a3 of the 48B KV pair in the enumeration operation is 1000*0.09ms. By analogy, the server can estimate that the time-consuming of 16B KV pairs in the full table scan operation and the update operation are t _b1 and t _c1 respectively, and the server uses the 16B KV pair in the check operation, the full table scan operation and the update operation. The total time consumption T1=t _a1 +t _b1 +t _c1 is obtained by summing the time consumption in . Similarly, for KV pairs of other sizes, the server can also calculate an estimated total time-consuming. Assuming that the server sums the time-consuming of 32B KV pairs in the check operation, full table scan operation and update operation, the total time is calculated as the total time. Time-consuming T2=t _a2 +t _b2 +t _c2 . After the server sums up the time consuming of the 48B KV pair in the check operation, the full table scan operation and the update operation, the total time consuming is T3=t _a3 +t _b3 +t _c3 . Since T3<T1<T2, the server can select the KV pair size corresponding to T3 with the shortest estimated total time consumption, that is, 48B as the optimal KV pair size, that is, the server can select the ratio of each read and write operation in the current load A and the difference For the read and write operation performance parameters of the KV pair, determine the optimal value of the space occupied by the key-value pair of 48B.

Step 206: Determine the partition mode of the storage area according to the semantic information of the query statement.

The semantic information of the query statement refers to the semantic information in the query statement obtained by parsing the grammar in the query statement. For example, for each query, its grammar can be parsed to extract the column information involved from the projection clause and the WHERE conditional clause and save it.

The storage area refers to the area where data is stored in the data table. For example, if a data table with a structure of 5 rows*8 columns is pre-defined, the area of 5 rows*8 columns in the data table is the storage area.

Partition refers to dividing the attributes of a data table in the database into several groups. The partitioning method refers to the method of partitioning the data table in the vertical direction, that is, the method of dividing a data table into several subsets in the vertical direction. For example, the columns of the data table are partitioned to obtain the corresponding column partitioning scheme.

Specifically, after the server determines the first space size of the space occupied by the key-value pair according to the read-write operation ratio and the read-write operation performance parameters, the server can determine the partition mode of the storage area according to the semantic information of the query statement in the running parameters, that is, The server can extract relevant column information according to the semantic information of the query statement, so as to deduce the candidate scheme of column partitioning. In actual storage, after the server divides the attributes of a data table in the database into several groups according to the partition method, the server can store data according to these groups.

For example, as shown in FIG. 3 , it is a schematic diagram of the structure change of the data table. As shown in (1) in Figure 3, partitioning divides a data table into subsets in the vertical direction. First, the server can obtain all query statements and corresponding ratios involved in the data table. For each query statement, the server can parse its syntax, fetch and save the column information involved. Further, the server may sort each query statement according to the proportion of each query statement, and select the top n query statements with the highest proportion as the target query statement. The server can start from the target query statement with the highest proportion, and after partitioning according to the column information involved in the target query statement, the server takes out the target query statement with the second highest proportion, and repeats the partitioning operation until all attributes have been partitioned. .

Step 208: Determine the data density in the candidate grouping range according to the data distribution.

The candidate grouping range refers to a preset grouping range. For example, when a grouping range is predefined, in order to facilitate the implementation of the grouping algorithm and reduce the amount of calculation, a power of 2 can be taken as the grouping range, that is, the preset The candidate values for the candidate grouping range of are {2 ¹ , 2 ² and 2 ³ }. The grouping range refers to the grouping range of primary key values.

Data density refers to the average data density under each candidate grouping range. For example, when the candidate grouping range is set to 8, the data table can be divided into 8 groups, and the data density in each group is determined separately, and then 8 The average value P of the data densities in each grouping is taken as the data density in the candidate grouping range, that is, the data density when the candidate grouping range is 8 is P. Among them, when determining the data density corresponding to each group, it is assumed that the grouping range is set to 8, and the data with the primary key value of 1 to 7 in the data table does not exist, and only the data with the primary key value of 0 is assigned to this group. , therefore, the positions where the primary key values are 1 to 7 are vacated, and the data density in this group is 1/8 at this time.

Specifically, after the server determines the partition mode of the storage area according to the semantic information of the query statement, the server can determine the data density under each candidate grouping range according to the data distribution and a preset group of candidate grouping ranges. That is, the server can calculate the data density in each candidate grouping range according to the data distribution when the current workload is running. Grouping and aggregation can aggregate multiple rows of data into a KV pair, improving the efficiency of reading and writing data. The grouping strategy and grouping range need to be determined according to the data distribution of the current workload. As shown in (2) in Figure 3, grouping divides a data table into several subsets in the horizontal direction. The grouping strategy in this application may include hash grouping and sequential grouping. Hash grouping refers to storing data of the same hash value in the same data group through a certain hash function. Sequential grouping refers to storing a series of consecutively arriving data in the same data group according to the arrival order of the data. It can be understood that the grouping strategy in this application includes, but is not limited to, hash grouping and sequential grouping, and can also be other customized grouping strategies.

For example, it is assumed that the adopted grouping strategy is hash grouping, that is, the grouping function is set to a hash function, and a predefined group of candidate grouping ranges are {2 ¹ , 2 ² , 2 ⁴ }. Assume that the primary key of the first row of data in data table A is int type, the value is 32, and the primary key value of the second row of data is 31. At this time, the server is based on the hash function, that is, the divisibility function. When the candidate grouping range is 2 ⁴ , For the first row of data with key 32, its grouping sequence number=32 divisible by 16=2, it should be divided into the second group; for the second row of data with key 31, its grouping sequence number=31 divisible by 16=1, it should be in group 1. Assuming that the server divides the data table A into two groups, namely the first group and the second group, the server determines the data density in each group respectively, and then takes the mean value P of the data densities in the two groups as the candidate grouping range: The data density under 2 ⁴ , that is, the data density when the candidate grouping range is 16 is P

Step 210: Determine the storage mode of the data table in the database when the workload is running based on the partition mode, the candidate grouping range, the data density and the first space size.

The data table refers to different data tables in the database whose data table structure is pre-set.

Storage mode refers to the storage mode of data tables in the database. The storage modes in this application include row storage mode, column storage mode, cell storage mode, multi-row storage mode, column segment storage mode, column family storage mode, and column family segment. at least one of the storage mode or the whole table storage mode.

Specifically, after the server determines the data density in the candidate grouping range according to the data distribution, the server may determine the optimal storage mode of the data table in the database when running the workload based on the partition mode, the candidate grouping range, the data density and the first space size . That is, the server can estimate the second space size of the space occupied by the key-value pairs in each candidate grouping range according to the partitioning method, each candidate grouping range, and the data density in each candidate grouping range. The second space size of the space occupied by the key-value pair is compared with the first space size of the space occupied by the key-value pair determined in step 204. When the difference between the second space size and the first space size satisfies the preset When the difference condition is , the server obtains the partition mode and candidate grouping range corresponding to the second space size, and determines the data table in the database when running the current workload based on the partition mode and candidate grouping range corresponding to the second space size optimal storage mode.

In addition, after the server determines the optimal storage mode of the data table in the database when the current workload is running, when the server is in an idle state, the server can re-encode the data in the data table according to the encoding method corresponding to the optimal storage mode stored later.

In the above adaptive method of database storage mode, the operation parameters of the workload and the read and write operation performance parameters of each key-value pair are obtained; the operation parameters include the ratio of read and write operations, query statements and data distribution; Write operation performance parameters to determine the first space size of the space occupied by the key-value pair; determine the partition mode of the storage area according to the semantic information of the query statement; determine the data density in the candidate grouping range according to the data distribution; Scope, data density, and first space size, determine the storage pattern of data tables in the database when running the workload. Since the read-write operation performance parameters of each key-value pair are obtained through pre-testing, the key-value pair can be determined based on the read-write operation ratio in the operating parameters of different workloads and the read-write operation performance parameters of each key-value pair obtained by the pre-test. The optimal value range of the space occupied by the value pair, so that the server can determine the database when running different workloads based on the partition mode, candidate grouping range, data density, and the optimal value range of the space occupied by the key-value pair. The optimal storage mode of the data table in the data table solves the problem that the traditional method cannot match the optimal storage mode according to different loads, and effectively improves the I/O efficiency of the system, thereby effectively improving the overall performance of the system.

In one embodiment, before acquiring the operating parameters of the workload and the read/write operation performance parameters of each key-value pair, the method further includes:

Get the size of the space occupied by the key-value pair;

In the case of the size of the occupied space, determine the read and write operation performance parameters of the key-value pair;

Based on the performance parameters of read and write operations, establish a performance model of key-value pairs;

The obtaining of the operating parameters of the workload and the read-write operation performance parameters of each key-value pair includes:

Get the running parameters of the workload, and the read and write operation performance parameters of key-value pairs based on the performance model.

The size of the space occupied by the key-value pair refers to the size of the space occupied by the storage of the key-value pair. For example, a set of preset space sizes occupied by a group of key-value pairs is: {16B, 32B, 48B, 64B}.

The performance model refers to the performance parameters of read and write operations corresponding to different key-value pairs. For example, in the check operation, the delay time of a 16B KV pair is 0.01ms, and the delay time of a 32B KV pair is 0.005ms, that is The performance parameters of read and write operations corresponding to key-value pairs with different occupied space are also different.

Specifically, before the server obtains the operating parameters of the workload and the read/write operation performance parameters of each key-value pair, the server may pre-establish performance models of different KV pair sizes. That is, the server can obtain a set of space sizes occupied by a set set of key-value pairs, and determine the read and write operation performance parameters of key-value pairs with different space sizes when the key-value pairs occupy different space sizes, so as to make the server Based on the performance parameters of read and write operations, a performance model of key-value pairs of different space sizes can be established, that is, the server establishes the mapping relationship between key-value pairs of different space sizes and performance parameters of read and write operations, so that subsequent servers can be based on the performance model. Directly obtain the performance parameters of read and write operations corresponding to key-value pairs of different space sizes.

For example, assuming that the set of space sizes occupied by a set of preset key-value pairs is: {16B, 32B, 48B, 64B}, then through a series of experiments in advance, it is possible to measure the size of each KV pair in each typical Performance under I/O operations. Typical I/O operations include at least one of update operations, insert operations, delete operations, point query operations, or range query operations. That is, the performance parameters of 16B KV pairs in update, insert, delete, point query and range query operations, and 32B KV pairs in update, insert, delete, point query and Performance parameters in range query operations, 48B KV pairs in update operations, insert operations, delete operations, point query operations, and performance parameters in range query operations, and 64B KV pairs in update operations, insert operations, and delete operations , point query operation and performance parameters in range query operation, these test results will be used as the judgment basis for subsequent steps. Further, the server can establish a performance model of key-value pairs of 16B, 32B, 48B, and 64B space sizes based on the performance parameters corresponding to the above-mentioned typical I/O operations, that is, the server establishes key-value pairs of different space sizes and each read and write. The mapping relationship between operational performance parameters, these test results will be used as the judgment basis for subsequent steps.

In this embodiment, through a series of experiments in advance, the performance of each size KV pair under each typical I/O operation can be measured, so that the subsequent server can directly obtain the corresponding key-value pairs of different space sizes based on the performance model. Read and write operation performance parameters, combined with the operating parameters of different workloads, quickly and accurately estimate the optimal range of space occupied by key-value pairs, and improve the computing efficiency in the data processing process.

In one embodiment, the step of determining the first space size of the space occupied by the key-value pair according to the read-write operation ratio and the read-write operation performance parameter includes:

According to the ratio of read and write operations and the performance parameters of read and write operations, determine the overall performance parameters of the workload when the key-value pair occupies space;

Based on the overall performance parameter, the first space size of the space occupied by the key-value pair is determined.

Among them, the overall performance parameter refers to the overall performance parameter obtained by the overall evaluation of the performance parameters of each read and write operation. For example, the server can obtain 16B of KV pairs from the performance model respectively. The consumption of the full table scan operation and the update operation The time is T1 and T2. After summing up T1 and T2, the total time is T=T1+T2, and the total time can be used as the overall performance parameter corresponding to the 16B KV pair.

The first space size refers to the optimal range of the space size occupied by the key-value pair, that is, the first space size may be an interval range or an optimal target value. For example, in workload A, the first space size of the space occupied by key-value pairs is determined to be 16B, and in workload B, the first space size of the space occupied by key-value pairs is determined to be 16B-17B.

Specifically, after the server obtains the operating parameters of the workload and the read and write operation performance parameters of each key-value pair, the server can read and write operations of each key-value pair in the pre-established performance model according to the ratio of read and write operations in the operating parameters and the pre-established performance model. Performance parameters: determine the overall performance parameters when the space occupied by key-value pairs under the current workload is determined, and based on the overall performance parameters, determine the optimal range of space occupied by key-value pairs under the current workload. Wherein, the parameter used to characterize the overall performance parameter in this application may include at least one of delay time, bandwidth, or IOPS (Input/Output Operations Per Second). In this application, when determining the overall performance parameters corresponding to key-value pairs of different space sizes, the weighted average method can be used to estimate the overall performance of the current workload under each KV pair size, and then the overall performance can be selected. The highest KV pair size is used as the optimal value for the system settings.

For example, assuming that the current workload B contains 1,000 point query operations, 10 full table scan operations involving 100,000 rows, 1,000 update operations, 0 insert operations, and 0 delete operations, the server obtains the The running parameters of workload B include 1,000 point query operations, 10 full table scan operations involving 100,000 rows, 1,000 update operations, 0 insert operations, and 0 delete operations. Further, the server can obtain the performance parameters of each size KV pair under different I/O operations from the pre-established performance model. Suppose the server obtains the IOPS corresponding to the 16B KV pair in the point query operation. The number of reads and writes per second is I _a1 =850, the IOPS of a KV pair with a size of 32B is I _a2 =750, and the IOPS of a KV pair with a size of 48B is I _a3 =950. By analogy, the server can estimate that the number of reads and writes per second of the 16B KV pair in the full table scan operation and the update operation are I _b1 and I _c1 respectively. After the IOPS in the update operation are summed, the total IOPS can be obtained as I _{total 1} =I _a1 +I _b1 +I _c1 . Similarly, for KV pairs of other sizes, the server can also calculate an estimated total IOPS. Assuming that the server sums the IOPS of 32B KV pairs in the check operation, full table scan operation and update operation, the total IOPS can be obtained. is Itotal ₂ =I _a2 +I _b2 +I _c2 . After the server sums the IOPS of the 48B KV pair in the check operation, the full table scan operation and the update operation, the total IOPS can be obtained as I _{total 3} =I _a3 +I _b3 +I _c3 . Since Itotal ₁ <Itotal ₃ <Itotal ₂ , the server can select the KV pair size corresponding to the maximum value Itotal ₂ in the estimated total IOPS, that is, 32B as the optimal KV pair size, that is, the server can select the KV pair size according to the current work The ratio of each read and write operation in load B and the read and write operation performance parameters of different KV pairs determine the optimal value range of the space occupied by the key-value pair under the current workload B to be 32B. As a result, the server can directly obtain the performance parameters of read and write operations corresponding to key-value pairs of different space sizes based on the performance model, and combine the operating parameters of different workloads to quickly and accurately estimate the space occupied by key-value pairs. Optimal range to improve computational efficiency during data processing.

In one embodiment, the step of determining the first space size of the space occupied by the key-value pair according to the read-write operation ratio and the read-write operation performance parameter includes:

When the overall performance parameter is the overall time-consuming, select the overall time-consuming that satisfies the time-consuming condition among the overall time-consuming as the target overall time-consuming;

The size of the space occupied by the key-value pair corresponding to the total time-consuming of the target is taken as the first space size.

The time-consuming condition refers to a preset overall time-consuming condition. For example, the time-consuming condition may be preset to be less than a certain threshold, for example, less than a threshold of 15. The time-consuming condition can also be set to automatically select the minimum value among multiple total time-consuming.

Specifically, after the server obtains the operating parameters of the workload and the read and write operation performance parameters of each key-value pair, the server can read and write operations of each key-value pair in the pre-established performance model according to the ratio of read and write operations in the operating parameters and the pre-established performance model. Performance parameters: determine the overall performance parameters when the space occupied by key-value pairs under the current workload is determined. When the overall performance parameter is the overall time-consuming, the server can select the total time-consuming that satisfies the time-consuming conditions among the total time-consuming as the target total. time-consuming, and take the space occupied by the key-value pair corresponding to the target total time-consuming as the optimal range of the space occupied by the key-value pair under the current workload.

For example, take the overall performance parameter as the overall time consumption as an example for illustration. Assuming that the current workload A contains 1,000 point query operations, 10 full table scan operations involving 100,000 rows, 1,000 update operations, 0 insert operations, and 0 delete operations, the server obtains the data of workload A within a preset time period. The running parameters include 1000 point query operations, 10 full table scan operations involving 100,000 rows, 1000 update operations, 0 insert operations and 0 delete operations. Further, the server can obtain the performance of each size KV pair under different I/O operations from the pre-established performance model. For example, the server obtains a delay time of 0.01 for a 16B KV pair in the check operation. ms, the delay time of a 32B-sized KV pair is 0.005ms, and the 48B-sized KV pair’s delay time is 0.009ms, then the server can estimate the time-consuming of the 16B KV pair in the current workload A in the check operation. t _a1 is 1000*0.01ms, the time consuming t _a2 of the 32B KV pair in the enumeration operation is 1000*0.05ms, and the time consuming t _a3 of the 48B KV pair in the enumeration operation is 1000*0.09ms. By analogy, the server can estimate that the time-consuming of 16B KV pairs in the full table scan operation and the update operation are t _b1 and t _c1 respectively, and the server uses the 16B KV pair in the check operation, the full table scan operation and the update operation. The total time consumption T1=t _a1 +t _b1 +t _c1 is obtained by summing the time consumption in . Similarly, for KV pairs of other sizes, the server can also calculate an estimated total time-consuming. Assuming that the server sums the time-consuming of 32B KV pairs in the check operation, full table scan operation and update operation, the total time is calculated as the total time. Time-consuming T2=t _a2 +t _b2 +t _c2 . After the server sums up the time consuming of the 48B KV pair in the check operation, the full table scan operation and the update operation, the total time consuming is T3=t _a3 +t _b3 +t _c3 . Since T3<T1<T2, the server can select T3 with the shortest estimated total time-consuming as the target total time-consuming, and take the KV pair size corresponding to T3 as the target total time-consuming, that is, 48B, as the optimal KV pair size. That is, the server determines that the optimal value range of the space occupied by the key-value pair under the current workload A is 48B according to the ratio of each read and write operation in the current workload A and the read and write operation performance parameters of different KV pairs. As a result, the server can directly obtain the performance parameters of read and write operations corresponding to key-value pairs of different space sizes based on the performance model, and combine the operating parameters of different workloads to quickly and accurately estimate the space occupied by the key-value pairs. Optimal range to improve computational efficiency during data processing.

In one embodiment, the step of determining the partition mode of the storage area according to the semantic information of the query statement includes:

Obtain the query statements and the total number of query statements involved in the data table;

Determine the ratio between the number of each query statement and the total number of query statements;

Among the query statements involved, determine the target query statement based on the ratio;

Based on the column information in the target query statement, determine how the storage area is partitioned.

The total number of query statements refers to the number of all query statements involved in the current workload. For example, suppose the current workload A contains 1000 point query operations, 10 full table scan operations involving 100,000 rows, and 1000 update operations , 0 insert operations and 0 delete operations, the total number of query statements involved in the current workload A is S=1000+10+1000=2010.

Specifically, after the server determines the first space size of the space occupied by the key-value pair according to the read-write operation ratio and the read-write operation performance parameters, the server can obtain the query statements and the total number of query statements involved in the data table, and determine each query statement The ratio between the number of query statements and the total number of query statements, and among the query statements involved, the target query statement is determined based on the ratio; further, the server can determine the partition mode of the storage area based on the column information in the target query statement. That is, the server can extract relevant column information according to the semantic information of the query statement, so as to deduce the candidate scheme of column partitioning. For example, as shown in (1) in Figure 3, column partitioning refers to dividing a data table into several subsets in the vertical direction.

For example, take the data table A in the database as an example for illustration. Assuming that there are 100 query statements involving data table A in workload A, among which, there are 10 query statements for full table scan operations, 50 query statements of the first type, and 40 query statements of the second type, then the server All the query statements and query statements involved in the data table A can be obtained and the total amount is 100. For each query statement, the server can parse its syntax, fetch and save the column information involved. The server can determine the ratio between the number of each query statement and the total number of query statements, that is, the proportion of the query statement obtained by the full table scan operation is S1=10/100=0.1, and the proportion of the first type of query statement is S2= 50/100=0.5, and the proportion of the second type of query statement is S3=40/100=0.4, then the server can sort each query statement according to the proportion of the above various query statements, and retrieve the top n with the highest proportion Bit query statement as the target query statement. Assuming that the query statement A with the highest proportion is: querying the data in the 10th and 11th columns, the server can start from the query statement A with the highest proportion and partition according to the relevant columns in the query statement A, that is, the server Columns 10 and 11 in Data Table A can be aggregated into a column group. By analogy, the server then retrieves the query statement B with the second highest proportion, performs partitioning according to the relevant columns in query statement B, and repeats the above column partitioning operation until all attributes in data table A have been partitioned.

In addition, partitioning algorithms can employ different strategies when processing the same column in multiple queries. When the same column is involved in multiple query statements, this column is called a "conflict column", and the processing strategies for conflicting columns in this application may include: Query refers to the query statement with the top sorting position. Under this strategy, more important queries, i.e. those with higher priority or weight, add the conflicting column to its own grouping, while other groups do not include this column. The second strategy is to combine these groupings. Under this strategy, groups containing conflicting columns are merged into a larger group. Both strategies have their own advantages. The first strategy is more likely to conform to the characteristics of high-priority queries, and is more suitable for situations where the proportion of different queries has a large gap; the second strategy is more suitable for the proportion gap between different queries. Not a big case. Therefore, it is possible to determine the vertical partition mode of the data table based on the proportion of query statements in the operating parameters of different workloads, so as to solve the problem that the optimal storage mode cannot be matched according to different loads in the traditional method, which effectively improves the The I/O efficiency of the system can effectively improve the overall performance of the system.

In one embodiment, the data density includes a first data density; the step of determining the data density under the candidate grouping range according to the data distribution includes:

Determine the candidate grouping range;

Determine the data grouping based on the primary key value of the data table and the candidate grouping range;

determining the second data density in each data packet according to the data distribution;

The average value of the second data density is taken as the first data density under the candidate grouping range.

The first data density refers to the average data density in each candidate grouping range. For example, if the grouping range is 8, the data in data table A is divided into 4 data groups, and the server can divide the data density of the 4 data groups into After taking the average value, the obtained average data density S1 is taken as the first data density corresponding to the grouping range of 8.

Specifically, after the server determines the partition mode of the storage area according to the semantic information of the query statement, the server can determine the candidate grouping range. For example, the candidate grouping range can be a set of candidate grouping ranges preset in the system {2 ¹ , 2 ² and 2 ³ }. Further, the server may determine the data groups in each candidate grouping range based on the primary key value of the data table and the candidate grouping ranges {2 ¹ , 2 ² and 2 ³ }, and determine the data groups in each data group according to the data distribution under the current workload. For the second data density, the server uses the average value of the second data density as the first data density in each candidate grouping range.

For example, assuming that the preset candidate grouping range in the system is {2 ¹ , 2 ² and 2 ³ }, and the data table A contains two rows of data, after the server obtains the above candidate grouping range, the server can base on the data table A. The primary key value and the above candidate grouping range determine the data grouping, that is, when the grouping range is 2, the primary key of the first row of data in data table A is int type and the value is 32; the primary key of the second row of data in data table A is The value is 31. Assuming that the preset grouping strategy in the system is to use a hash function, take the hash function as the divisible function as an example, that is, the grouping function is y=primary key value÷grouping range, and y represents the grouping sequence number, that is, the grouping sequence number=primary key value÷ grouping range, the server can determine the first row of data with a primary key value of 32 based on the above grouping function, and its grouping sequence number=32÷2=16, which should be in the 16th group; for the second row of data with a primary key value of 31 , its grouping sequence number=31÷2=15, and it should be in the 15th group. By analogy, when the grouping range is 4, the server can determine the first row of data with a primary key value of 32 based on the above grouping function, and its grouping sequence number=32÷4=8, which should be in the 8th group; for the primary key value The second line of data is 31, and its grouping sequence number=31÷4=7, which should be divided into the 7th group. When the grouping range is 8, the server can determine, based on the above grouping function, that the first row of data whose primary key value is 32, whose grouping sequence number=32÷8=4, should be in the 4th group; for the first row whose primary key value is 31 Two lines of data, whose grouping sequence number=31÷8=3, should be divided into the third group.

Further, for each candidate grouping range in the candidate grouping ranges {2 ¹ , 2 ² and 2 ³ }, the average data density under each candidate grouping range is calculated. Since the distribution of primary key values is not necessarily strictly increasing, it may happen that the actual elements in a certain data group cannot reach the grouping range. For example, taking the grouping range of 8 as an example, when the grouping range is 8, the data in data table A is divided into 4 data groups, and the server can count the data in group 1, group 2, group 3 and group 4 respectively. Density, if the data with the primary key value of 1 to 7 in data table A does not exist, only the data with the primary key value of 0 is divided into group 1, so the positions of the primary key value of 1 to 7 in this group are empty. , the server can count the data density of the data group, that is, the data density of group 1 is 1/8, and the server counts the data density of each data group when the candidate grouping range is 8 one by one, and obtains group 1, group 2, group 3 and group 4 The data densities are S1=1/8, S2, S3 and S4 respectively. The server can calculate the average value S of the data densities of all data groups obtained by statistics, and the obtained average value S is the corresponding value when the grouping range is 8. The first data density of S ₈ =(S1+S2+S3+S4)÷4=S. By analogy, the server can calculate the corresponding first data densities when the grouping range is 4 and the grouping range is 2 respectively as S ₄ and S ₂ , that is, the server finally obtains the average data density under each candidate grouping range as S ₈ . , S ₄ and S ₂ . As a result, the data density in each candidate grouping range can be determined based on the data distribution in the operating parameters of different workloads, so as to solve the problem that the optimal storage mode cannot be matched according to different loads in the traditional method, and effectively improve the I/O of the system. O efficiency, thereby effectively improving the overall performance of the system.

It can be understood that the grouping strategy in this application includes, but is not limited to, a grouping method using a hash function, and can also be other grouping strategies, such as a sequential grouping strategy. The data are stored in the same data group. For the sequential grouping strategy, the corresponding data density can also be calculated in the above manner.

In one embodiment, the step of determining the storage mode of the data table in the database when the workload is running, based on the partition mode, the candidate grouping range, the data density and the first space size, includes:

Based on the partition mode, the candidate grouping range, and the first data density in the candidate grouping range, determine the size of the second space occupied by the key-value pairs in the candidate grouping range;

When the difference between the second space size and the first space size satisfies the preset difference condition, the storage mode of the data table in the database when the workload is running is determined based on the partition mode and the candidate grouping range corresponding to the second space size.

The second space size refers to the size of the space occupied by the key-value pair calculated according to the partitioning method, the candidate grouping range, and the first data density under the candidate grouping range, for example, numerically, grouping range * data density * partition size = the size of the space occupied by the KV pair, the server may obtain the second size of the space occupied by the key-value pairs in different candidate grouping ranges based on the above calculation method.

Specifically, after the server determines the data density in each candidate grouping range according to the data distribution, the server may determine the occupied key-value pairs in each candidate grouping range based on the partition mode, the candidate grouping range, and the first data density in the candidate grouping range When the difference between the second space size and the first space size satisfies the preset difference condition, the server can determine when running the workload based on the partition mode and the candidate grouping range corresponding to the second space size The optimal storage mode for data tables in the database. As shown in Figure 3, the server will divide the data table horizontally and vertically according to the partition method and grouping range to obtain the final storage mode. That is, the server can obtain the size of the KV pair according to the partition mode determined in step 206 , the range of each candidate group and the data density determined in step 208 . Numerically, when a certain candidate grouping range A*data density S*partition size B under the candidate grouping range, the obtained second space size of the KV pair is between the optimal first space size determined in step 204 When the difference between the two satisfies the preset difference threshold, the server may determine the optimal storage mode of the data table in the database when running the current workload based on the partition mode and the candidate grouping range corresponding to the second space size. In addition, after the server determines the optimal storage mode of the data table in the database when running the current workload, in an idle state, the server can re-encode and store the data of the data table in the database according to the above-obtained optimal storage mode.

For example, assuming that the preset candidate grouping ranges in the system are {2 ¹ , 2 ² and 2 ³ }, the data table A contains two rows of data, and the server calculates that the grouping range is 8, the grouping range is 4 and the grouping range respectively. When it is 2, the corresponding first data density is S ₈ =1/8, S ₄ =1/4, and S ₂ =3/4. The first data density is to determine the second space occupied by the key-value pairs under each candidate grouping range, assuming that the partition mode A is to aggregate the first and second cells in each column of data in table A is a column group, each cell stores 4 bytes of data, and the size of each column group is 8 bytes, then the server can calculate the function based on the following: grouping range * data density * partition size = occupied by KV pairs Space size, calculate the second space size occupied by key-value pairs under each candidate grouping range, that is, when the grouping range is 8, the second space size of the space occupied by the KV pair calculated by the server L ₈ = grouping range* Data density*partition size=8*1/8*8=1; when the grouping range is 4, the second space size L ₄ of the space occupied by the KV pair calculated by the server = grouping range*data density*partition size=4 *1/4*8=8; when the grouping range is 2, the second space size L ₂ of the space occupied by the KV pair calculated by the server = grouping range*data density*partition size=2*3/4*8= 12. Suppose the server determines in step 204 that the first space size L of the space occupied by the key-value pair is 16B according to the read-write operation ratio in the current workload and the read-write operation performance parameters in the performance model, and the preset difference condition is is less than the difference threshold value of 5, the server can calculate the absolute difference between the second space size occupied by the key-value pairs in each candidate grouping range, that is, the difference between L ₈ , L ₄ , L ₂ and the first space size L value, we get |L ₈ -L|=|1-16|=15, |L ₄ -L|=|8-16|=8, |L ₂ -L|=|12-16|=4, since | L ₂ -L|=|12-16|=4 is less than the difference threshold 5, that is, when the difference between the second space size L ₂ and the first space size L satisfies the preset difference condition, the server may The partition mode A corresponding to the second space size L ₂ and the candidate grouping range 2 determine the optimal storage mode of the data table in the database when the current workload is running, that is, the server can determine the optimal storage mode of the data table in the database when the current workload is running The storage mode is: the server simultaneously divides the data table A horizontally according to the grouping range of 2, and divides it vertically according to the partition method A, that is, the server aggregates the data of each two cells in each column of data in the data table A into a column group. , at the same time, group each row of data in data table A according to the grouping range of 2, so as to obtain a schematic diagram of the optimal storage mode as shown in (3) in FIG. 3 . This solves the problem that the traditional method cannot match the optimal storage mode according to different loads, effectively improves the I/O efficiency of the system, and thus effectively improves the overall performance of the system.

In one embodiment, the method further includes:

When the workload is replaced with other workloads, determine the target storage mode of the other workloads in the database;

When idle, transition the storage mode to the target storage mode.

The other workload is used to distinguish the current workload. For example, when workload A is replaced with workload B, workload B is the other workload.

The target storage mode refers to the storage mode of the data table in the database when running other workloads. For example, the server can determine the maximum size of the data table in the database when running workload A according to the adaptive method of the database storage mode provided in this application. The optimal storage mode is a multi-row storage mode. When workload A is replaced with workload B, the server can re-determine the maximum size of the data table in the database when running workload B according to the adaptive method of the database storage mode provided in this application. optimal storage mode. It can be understood that the target storage mode may be the same as or different from the current storage mode.

Specifically, in actual operation, the server system can automatically switch the storage mode of the replica node according to different workloads. When the adaptive module in the server senses the change in load, it will re-evaluate the optimal storage mode and the corresponding conversion cost. During a relatively idle period of the system, the server can perform the work of storage mode conversion, and convert the current storage mode to the target storage mode, that is, to a new optimal storage mode.

For example, suppose there are 3 service nodes in the distributed server cluster, namely A service node, B service node and C service node. The storage mode corresponding to the A service node is row storage mode, and the storage mode corresponding to the B service node is multiple. The row storage mode and the storage mode corresponding to the C service node are the column family segment storage mode. At a certain moment, workload A is replaced with workload B. When the adaptive model in the server determines that the storage model required by the replaced workload B is column storage, there is no column storage in the three server nodes in the current service cluster. mode, you need to select one of the service nodes to convert the storage mode, which may be the conversion from row storage to column storage. In addition, the load of the service node needs to be considered when performing the conversion, and the node with the smaller load is preferentially selected. The storage mode in this application includes at least one of row storage mode, column storage mode, cell storage mode, multi-row storage mode, column segment storage mode, column family storage mode, column family segment storage mode or whole table storage mode . As shown in FIG. 4 , which is a schematic diagram of the conversion of storage modes, 8 different storage modes are considered in FIG. 4 , corresponding to a total of 7*8=56 conversion modes. This solves the problem that the traditional method cannot match the optimal storage mode according to different loads. On the basis of the diversity of storage modes, a multi-copy heterogeneous collaborative computing scheme is proposed, which can be implemented on different copies of the same consensus group. Store data in different modes and select the most suitable storage node for different workloads. Compared with the traditional distributed system, the method in this embodiment can simultaneously select the storage node with the optimal storage mode for the AP and the TP, thereby better adapting to the HTAP scenario. At the same time, the method in this embodiment takes into account the problem of load balancing among different service nodes, therefore, the utilization rate of each node can be effectively improved, thereby improving the overall performance of the system.

In one embodiment, after converting the storage mode to the target storage mode, the method further includes:

According to the encoding mode corresponding to the target storage mode, re-encode the data in the data table to obtain the encoded data;

Store the encoded data.

Specifically, when the workload is replaced with another workload, the server determines the target storage mode of the other workload in the database, and when in an idle state, the server can convert the storage mode to the target storage mode. That is, the server can re-encode the data in the data table according to the encoding mode corresponding to the target storage mode, obtain the encoded data, and store the encoded data.

For example, assuming that the current storage mode is row storage and the target storage mode is column storage, row storage means that data is stored in the underlying storage engine with a row as a KV pair, and column storage means that data is stored in the underlying storage with a column as a KV pair in the engine. Because the encoding method corresponding to the row storage mode is: use the table ID tableA of data table A, the row ID rowID of each row of data in data table A as the key, and store the data in each row as the value, then when the server is in an idle state At this time, the server can re-encode the data in the data table A according to the target storage mode, that is, the encoding method corresponding to the column storage, that is, the server reads the data in the data table A, and identifies the table A and the data table A in the data table A. The column ID of each column of data is used as the key, and the data in each column is used as the value to obtain the data composed of key-value, and store the data composed of the encoded key-value. As a result, the storage mode of the copy can be automatically switched according to different workloads. When the adaptive module senses a change in the load, it will evaluate the optimal storage mode and the corresponding conversion cost. The problem of load matching the optimal storage mode effectively improves the I/O efficiency of the system, thereby effectively improving the overall performance of the system.

In one embodiment, the method further includes:

When the storage mode is row storage mode and the target storage mode is cell storage mode, read the data in the data table;

Use the table ID of the data table, the row ID of the target row in the data table, and the column ID of the target column in the data table as the key, and use the data in the intersecting cell between the target row and the target column as the value, and get the value between the key and the value. composed cell data;

Stores cell data consisting of keys and values.

Among them, cell storage refers to storing cells in a row or column as KV pairs in the underlying storage engine. Cell storage breaks the storage mode of the entire row or column, making the granularity of the KV unit smaller. In some workloads that only want to operate on a single cell, it will show a better performance advantage. In the traditional storage mode of row storage and column storage, when a cell needs to be updated, the server must first read out the entire row and column data, modify it and then write it back, which causes serious read and write amplification. In this case, using cell storage can eliminate this write amplification very well. The cell storage mode in this application can be further divided into cell row storage and cell column storage. Cell row storage refers to organizing cells according to the format of rows, so that the overall storage maintains continuity on the row; Grid storage refers to organizing cells according to the format of columns, so that the overall storage can maintain continuity on the columns.

Specifically, since there are many types of conversions, in general, the conversion storage mode can be abstracted into two types of conversions, namely splitting and reorganization. The application scenario of splitting is mainly to change the data from one large KV into several smaller KVs. That is, when data is written in row storage mode, the encoding form of its key is: table ID + row ID, and Value is the data in each row. In some scenarios, when the row storage mode needs to be converted to the cell storage mode, the server needs to re-encode the key-value and set a corresponding cell ID for each attribute, that is, when the data is written in the cell mode When the key is encoded in the form of: table ID + row ID + column ID, or table ID + column ID + row ID, Value is the data in each cell, thus splitting the data from the row storage mode into cells Grid mode.

In this embodiment, the conversion of single row storage to cell storage is taken as an example for detailed description. If the current storage mode is row storage mode and the target storage mode is cell storage mode, the server can read the data in the data table according to the encoding method corresponding to the target storage mode, that is, the cell storage mode, and store the data in the data table. The table ID, the row ID of the target row in the data table, and the column ID of the target column in the data table are used as the key, and the data in the intersecting cell between the target row and the target column is used as the value, and the cell composed of the key and the value is obtained. The conversion of storage mode can be completed by storing the cell data composed of key and value.

For example, assuming that the structure of data table A is a 2*2 two-dimensional table, the server can read the data in data table A, and identify table A in data table A and the target row in data table A as the first row. The row identifier row1 of the row, and the column identifier column1 of the target column in the data table A, that is, the first column, are used as the key, that is, the key is: tableA+row1+column1, and the target row is the first row and the target column is the second row. The data in the intersecting cells is used as value, the first cell data composed of key-value is obtained, and the first cell data composed of key-value is stored, and so on, the server can follow the above coding method, encode all the data in the data table A, and obtain 4 key-value pairs composed of key-value for storage, and the 4 key-value pairs correspond to 4 cell data respectively. It can be understood that the above encoded key is: tableA+row1+column1, which is a cell row storage, and if the encoded key is: tableA+column1+row1, it is a cell column storage. As a result, the storage mode of the copy can be automatically switched according to different workloads. When the adaptive module senses a change in the load, it will evaluate the optimal storage mode and the corresponding conversion cost. The problem of load matching the optimal storage mode effectively improves the I/O efficiency of the system, thereby effectively improving the overall performance of the system.

In one embodiment, the method further includes:

When the storage mode is the cell storage mode and the target storage mode is the column storage mode, write the cells in the cell storage mode into the buffer;

When the number of cells in the buffer meets the number required by the column storage mode, the table ID of the data table and the column ID of the target column in the data table are used as keys, and the data in the target column is used as the value. composed of column data;

Stores column data consisting of keys and values.

Specifically, when switching the storage mode, the application scenario of reorganization is mainly to reorganize the data from several smaller KVs into a larger KV, for example: conversion from single-line storage to multi-line storage, conversion from cell storage to row storage, etc. , in this embodiment, the conversion from cell storage to column storage is taken as an example for detailed description.

Assuming that the data on a replica node starts to be stored in cell storage, as the load changes, the storage mode of the replica node needs to be converted to column storage, but the cells required for column storage are not enough. The server can temporarily write these cells into the buffer, and then re-encode and convert when the buffer has enough cells to convert to column storage. That is, when the storage mode is the cell storage mode and the target storage mode is the column storage mode, the server can write the cells in the cell storage mode into the buffer; when the number of cells in the buffer meets the requirements of the column storage mode. When the required number is required, the server can use the table ID of the data table and the column ID of the target column in the data table as the key, and the data in the target column as the value to obtain the column data composed of the key and the value, and combine the key and value. The composed column data is stored, and the conversion of the storage mode can be completed. As a result, the storage mode of the copy can be automatically switched according to different workloads. When the adaptive module senses a change in the load, it will evaluate the optimal storage mode and the corresponding conversion cost. The problem of load matching the optimal storage mode effectively improves the I/O efficiency of the system, thereby effectively improving the overall performance of the system.

In one embodiment, the method further includes:

When the storage mode is column segment storage mode, at least two cells in the target column are aggregated into a group;

The table ID of the data table, the column ID of the target column and the group ID of at least two cells are used as keys, and the data in at least two cells in the target column is used as the value for storage.

Among them, the column segment storage refers to the aggregation of at least two cell data in a column into a KV pair for storage. This mechanism can be understood as the vertical partition of MySQL. The reason for introducing this mechanism is that the query may not need to return all the column data in a whole column. For some specific workloads, the performance will be improved after the introduction of column segments.

Specifically, when the server determines that the storage mode of the data table in the database is the column segment storage mode when the current workload is running, when the server is in an idle state, the server can aggregate at least two cells in each column of the data table as A group is stored with the table ID of the data table, the column ID of each column and the group ID of at least two cells as keys, and the data in at least two cells in each column as values.

For example, as shown in FIG. 5 , it is a schematic diagram of a column segment memory mode. In Figure 5, row1co6 in the first cell in the first row and the sixth column represents the first row and the sixth column. The key is: tableID+columnID+groupID, which means: table ID+column ID+group ID . When the server is in an idle state, the server can aggregate every three cells in the target column of data table A, that is, the sixth column, into a group, and use the table of data table A to identify tableA and the target column, that is, the column of the sixth column. The identifier column6 and the grouping identifier group1 of every three cells are used as keys, and the data in every three cells in the sixth column is stored as the value to obtain two key-value pairs stored in the column segment storage mode, namely The key of the first key-value pair is: tableA+column6+group1, and the corresponding value is: the data in cells 1, 2, and 3 in column 6; the key of the second key-value pair is: tableA+column6 +group2, the corresponding value is: the data in the 4th, 5th, and 6th cells in the 6th column. By analogy, when the server is in an idle state, the server can process each column of data table A as a target column, and can obtain multiple key-value pairs stored in data table A according to the column segment storage mode. Therefore, according to the granularity and sorting method of the data, more storage modes can be expanded, so that the system can obtain support for diversified storage modes.

In one embodiment, the method further includes:

When the storage mode is the column family segment storage mode, at least two cells in each column located in the first direction in the data table are aggregated into a column family;

Aggregate at least two cells in each row located in the second direction in the data table into data groupings;

Using the table ID of the data table, the family ID of the column family, and the group ID of the data grouping as keys, the data in at least two cells in each column and the data in at least two cells in each row are stored as values.

Among them, column family storage means that certain attributes in a row are aggregated into a KV pair, and column family segment storage means that several attributes in multiple rows are aggregated into a KV pair, thereby improving the throughput of the system in the AP scenario. , which can be understood as increasing the number of rows stored in the column family.

The first direction may be a vertical direction, and the second direction may be a horizontal direction.

Specifically, as shown in FIG. 6 , it is a schematic diagram of a column family segment storage mode. In Figure 6, row1co1 in the first cell in the first row of the first column represents the first row and the first column. The key is: tableID+CFID+groupID, which means: table ID+column family ID+grouping logo. When the server determines that the storage mode of the data table in the database is the column family segment storage mode when the current workload is running, when the server is in an idle state, the server can store the first two in each row located in the horizontal direction in the data table A. The cells are aggregated into a data group, and the last four cells are aggregated into a data group, so that 12 data groups can be obtained; further, the server can aggregate the 6 data groups on the left in the vertical direction in the data table A into one Column family, the 6 data groups on the right are aggregated into a column family, and the table ID tableA of data table A, the family ID column family1 of the column family, and the group ID group1-6 of the data grouping are used as the keys of the first key-value pair. Store the data in the 12 cells on the left as the value of the first key-value pair; at the same time, use the table ID tableA of data table A, the family ID columnfamily2 of the column family, and the group ID group7-12 of the data grouping as the second The key of a key-value pair is stored with the data in the 24 cells on the right as the value of the second key-value pair. Therefore, according to the granularity and sorting method of the data, more storage modes can be expanded, so that the system can obtain support for diversified storage modes.

In one embodiment, the method further includes:

When the storage mode is the whole table storage mode, the table ID of the data table is used as the key, and the data in the data table is used as the value for storage.

Among them, the whole table storage refers to the storage of the entire table as a KV. The performance of the entire table is significantly improved under the query condition of full table scan.

Specifically, when the server determines that the storage mode of the data table in the database is the whole table storage mode when running the current workload, when the server is in an idle state, the server uses the table identifier of the data table as the key, and the data in the data table as the key value is stored.

For example, as shown in FIG. 7 , it is a schematic diagram of the whole table storage mode. When the server is in an idle state, the server can use the table identifier tableA of the data table A as a key, and store all the data in the data table A as a value. You can get a key-value pair stored in the whole table storage mode, that is, the key of the key-value pair is: tableA, and the corresponding value is: all the data in data table A. Therefore, according to the granularity and sorting method of the data, more storage modes can be expanded, so that the system can obtain support for diversified storage modes.

In one embodiment, the storage mode is the first storage mode; after the determining the storage mode of the data table in the database when the workload is running, the method further includes:

Receive different types of query requests;

Determine the execution time, wait time and transmission time of the query request;

Determine the second storage mode corresponding to the query request based on the execution time, the waiting time, the transmission time and the preset weight; the first storage mode and the second storage mode are different storage modes;

The query request is routed to the replica node corresponding to the second storage mode, so that the replica node performs data query based on the query request.

The first storage mode refers to the optimal storage mode of the data table in the database when running a certain workload, and the second storage mode refers to the optimal storage mode of the data table in the database corresponding to a query request.

Specifically, the query cost is an important indicator for formulating a query plan, which consists of three parts: execution time T _proc , waiting time T _wait and transmission time T _trans , that is, the total time spent processing query requests T=T _proc +T _wait + T _trans , the storage mode of the data table in the database mainly affects the execution time T _proc of the query request. Therefore, in this embodiment, the impact of multiple replica nodes on query plan customization is considered. That is, after the server determines that the storage mode of the data table in the database is multi-row storage mode when running the current workload, when the server receives different types of query requests, the server can determine the execution time, waiting time and transmission time of each query request. And based on the execution time, the waiting time, the transmission time and the preset weight, the second storage mode corresponding to each query request is determined. Wherein, when the first storage mode and the second storage mode are different storage modes, the server may route the query request to the corresponding second storage mode based on the query policy. One of the replica nodes with less load, so that the replica node can perform data query based on the query request.

For example, suppose there are 3 service nodes in the distributed service cluster, namely A service node, B service node and C service node. The storage mode corresponding to service node A is row storage mode, and the storage mode corresponding to service node B is the storage mode. It is a multi-row storage mode, and the storage mode corresponding to the C service node is a column family segment storage mode. When the B service node receives the query request A, the server of the B service node determines that the execution time of the query request A is T _proc , the waiting time is T _wait , and the transmission time is T _{trans .} The time T _wait , the transmission time T _trans and the preset weight determine that the second storage mode corresponding to the query request A is the row storage mode. Since the storage mode of the current service node B is the multi-row storage mode, it is determined that the query request A corresponds to The second storage mode is row storage mode. Therefore, the server of service node B can route query request A to the replica node corresponding to row storage mode, that is, service node A, so that service node A can perform data query based on query request A.

In this embodiment, due to the use of a multi-copy heterogeneous solution based on diversified storage, under mixed loads, different types of requests can use the copies of different storage modes to better utilize the advantages of disk reading and reduce network bandwidth usage.

In one embodiment, the determining the execution time, waiting time and transmission time of the query request includes:

Obtain the lookup time, processing time, and tuple construction time of the query request, and determine the execution time of the query request based on the lookup time, read and write data volume processing time, and tuple construction time;

Obtain the request queue time, machine load delay time and slave node data synchronization time of the query request, and determine the query request waiting time based on the request queue time, machine load delay time and slave node data synchronization time;

Determines the transmission time of the query request.

The processing time refers to the time to read or write data.

Specifically, when the server receives different types of query requests, the server can obtain the search time, processing time and tuple construction time of each query request, and based on the search time, read and write data volume processing time and tuple construction time of each query request The construction time determines the execution time of each query request; further, the server can obtain the request queue time, machine load delay time and slave node data synchronization time of each query request, and based on the request queue time, machine load delay time and The data synchronization time of the slave node determines the waiting time of each query request; the server can determine the transmission time of each query request. In this embodiment, due to the expansion of the lower-layer storage mode, a better configuration scheme can be obtained for query optimization, and the database can speed up the processing speed of user requests. Therefore, the user's satisfaction with the system will also increase.

In one embodiment, the storage mode is the first storage mode; the method further includes:

Receive range query requests;

Determine the total number of columns in the query table corresponding to the range query request, and determine the number of target columns required by the range query request; the target column is the data column in the query table;

Determine the third storage mode corresponding to the range query request based on the number of columns, the total number of columns and the preset threshold; the first storage mode and the third storage mode are different storage modes;

The range query request is routed to the replica node corresponding to the third storage mode, so that the replica node performs data query based on the range query request.

Specifically, when the read/write operation request received by the server is a range query request, the server can determine the total number of columns in the query table corresponding to the range query request, and determine the number of target columns required by the range query request, and the target column is query the data columns in the table; further, the server may determine the third storage mode corresponding to the range query request based on the number of columns, the total number of columns and a preset threshold. When the first storage mode and the third storage mode are different storage modes, the server may route the range query request to the replica node corresponding to the third storage mode, so that the replica node performs data query based on the range query request.

For example, suppose that after the server determines that the storage mode of the data table in the database is multi-row storage mode when running the current workload, when the server receives the range query request A, the server can determine the query table A corresponding to the range query request A. The total number of columns in the query request A is Col_num, and the number of target columns required to determine the range query request A is Col, and the target column is the data column in the query table A; further, the server can be based on the number of columns Col, the total number of columns The threshold α is set to determine the third storage mode corresponding to the range query request A. For example, when Col/Col_num<α, it can be determined that the column storage mode is the best storage mode; when Col/Col_num≥α, it means that the range query request A needs to read a large number of columns. For example, the range query request A needs to read 19 columns of 20 data, and 19 iterators need to be created when reading in the column-based storage mode. Only one iterator needs to be created on the row memory, and the overall overhead will be greatly reduced.

Suppose the server determines that the third storage mode corresponding to the range query request A is the column storage mode. Since the storage mode of the data table in the current server database is the multi-row storage mode, the server can route the range query request A to the multi-row storage mode. Corresponding replica nodes, so that other replica nodes perform data query based on the range query request A. In this embodiment, the original system is supported by diversified storage. At the same time, due to the expansion of the lower-layer storage mode, the upper-layer query optimization can obtain better parameter adjustment schemes, so developers can save more computing and storage costs.

The present application also provides an application scenario, where the above-mentioned adaptive method for database storage mode is applied to the application scenario. Specifically, the application of the adaptive method of the database storage mode in this application scenario is as follows:

When it is necessary to decide the most suitable storage structure according to the characteristics of different loads, the above-mentioned adaptive method of database storage mode can be used, that is, when running a certain workload, for each data table in the database, the The above-mentioned adaptive method of database storage mode decides the optimal storage scheme.

The methods provided by the embodiments of the present application can be applied to any scenario in which the workload is running normally. The following takes the optimization scenario of the distributed database storage mode based on the LSM-TreeKV storage engine as an example to describe the database storage mode provided by the embodiments of the present application. The adaptive method is described.

In the traditional way, the storage mode of row storage or column storage is usually adopted, so that these storage modes can improve the read/write (I/O) performance of the database when processing queries under a certain workload. For example, OLTP type workloads have many write operations to data, and OLAP operations generally have many range query operations. In the design of traditional databases, OLTP and OLAP databases are generally divided into independent products. Among them, OLTP databases basically use row storage as the storage mode, which is convenient for write operations and point query operations; while OLAP databases generally use column storage as the storage mode to accelerate Range queries with continuous access, especially scan operations on one or several columns. Obviously, OLTP and OLAP are contradictory in the choice of storage mode, therefore, the selection and optimization of storage mode in HTAP (Hybrid Transactional/Analytical Processing) database is a very challenging problem. HTAP is an emerging application architecture that supports transaction processing and analytics well. Specifically, in the new distributed database system based on LSM-Tree KV, the problem of storage mode becomes more complicated. Since the storage mode is limited by row storage and column storage, parameter adjustment mostly depends on hardware configuration and query characteristics , it is impossible to adjust the underlying basic configuration such as the storage mode, so it is easy to make the final selected storage mode often not optimal, which may cause a relatively large storage overhead or even a waste of space, resulting in poor overall performance of the database system.

Therefore, in order to solve the above problem, the present application provides an optimization method for a distributed database storage mode based on the LSM-Tree KV storage engine, so as to solve the problem of poor overall performance of the database system. In this method, according to the characteristics of the LSM-Tree KV storage engine, the design space of the database storage mode is expanded, and through the statistical information and cost evaluation function of the database, the optimal storage scheme for the current load can be decided to adapt to different businesses of the enterprise. different needs. This makes it possible to select the most suitable storage mode according to the user's access load. Compared with the traditional method, the method in this embodiment can find the storage structure that is most suitable for the query load in a wider range, and can store data of different modes on different copies of the same consensus group, which can be different. Select the most appropriate storage node for the workload. Compared with the traditional distributed system, the method can simultaneously select the storage node with the optimal storage mode for the AP and TP type loads, so as to better adapt to the HTAP scenario. At the same time, the method also considers the problem of load balancing between the master and slave nodes, which can improve the utilization rate of each node, thereby improving the overall performance of the system.

On the product side, the method provided in this application can adapt to the user's query request, and select an appropriate storage mode for different workloads. Traditional databases based on row storage and column storage have too few storage modes to choose from, and cannot provide optimal storage modes for different query requests, which may lead to waste of space and loss of performance. In this embodiment, a distributed database system based on diversified storage modes is proposed, which expands the types of storage modes, which not only improves the I/O efficiency of disks, reduces space waste, but also ensures data integrity between different replica nodes. Consistency increases the concurrent performance of the system and improves the performance of the system under mixed loads.

The features on the product side are as follows:

The product has storage and computing capabilities. On the storage side, the data will be sharded, and each data shard has several copies, and each copy provides access functions. The storage modes corresponding to different copies of data slices can be the same or different. At the computing layer, according to the analysis and statistics, the type of request is judged, and the replica with better performance is determined. At the same time, load balancing is considered, and the request is sent to the selected replica for processing. After the node where the replica resides executes the request, the data is returned to the computing layer, and then returned to the client through the computing layer. For upper-level users, the diversification of the underlying storage mode is not perceived, but the management of the diversified storage mode is completed by the database product itself. At the same time, developers only need to modify the rules of KV mapping and transaction processing flow to be directly compatible with the changes of this method, so that the system can obtain support for diversified storage modes.

On the technical side, as shown in Figure 8, it is the overall architecture diagram of the system.

Section 1 - Overall description.

This method is suitable for databases using LSM-Tree KV as the underlying storage engine. The system can adopt the common storage and computing separation architecture in distributed service systems to separate the storage layer and the computing layer. As shown in Figure 8, SQLENGINE is the SQL engine in the computing layer. The SQL engine is an important part of the database system. Its main responsibility is to generate an efficient execution plan for the SQL statement input by the application under the current load scenario. important role in efficient execution. As shown in Figure 8, in the storage layer, consensus group 1 includes multiple replica nodes, namely storage node 1, storage node 2, and storage node 3, and the server forms a consensus group with multiple replicas through the consistency protocol layer, so that the The data stored in each storage node in the consensus group is the same, which improves the fault tolerance rate of the system, and the storage mode of the replica nodes in each consensus group can be different or the same.

For example, assuming that the current load is load A, in the scenario that the current load A is running in the database, the server of the storage node 1 can be based on the optimization method of the distributed database storage mode of the LSM-Tree KV storage engine proposed in the embodiment of this application, The optimal storage solution for the current load A is decided. As shown in Figure 8, the storage mode of the state machine in the storage node 1 in the consensus group 1 is row storage, that is, the storage mode in the database at this time is the row storage mode as the reference mode, and the server can obtain the current load A's storage mode. Running parameters, including the ratio of read and write operations, query statements, and data distribution; the server can determine the space occupied by key-value pairs according to the ratio of read and write operations in the running parameters of current load A and the performance parameters of read and write operations of each key-value pair The first space size of the storage area is determined according to the semantic information of the query statement in the running parameters of the current load A, and the partition mode of the storage area is determined; further, the server determines the data density in the candidate grouping range according to the data distribution in the running parameters of the current load A, And based on the partition mode, candidate grouping range, data density and first space size, it is determined that the optimal storage mode of the data table in the database is the multi-row storage mode when the current load A is running, then when the server is in an idle state, the server can store The storage mode of the state machine in the storage node 1 corresponding to the current load A is converted from the row storage mode to the multi row storage mode, that is, the server can re-encode the data in the data table according to the encoding method corresponding to the multi row storage mode Then store it, so that the data in the data table is stored in a multi-line storage mode. In addition, when the load A is replaced with another load B, the server may re-determine the target storage mode of the other load B in the database based on the optimization method for the distributed database storage mode of the LSM-Tree KV storage engine proposed in the embodiment of the present application , and when the server is idle, convert the current storage mode to the target storage mode.

Further, in the scenario where the current load A is running in the database, when the server determines that the optimal storage mode of the data table in the database is the multi-row storage mode when the current load A is running, and when the server is in an idle state, the current load A is stored in the database. After the storage mode of the state machine in the corresponding storage node 1 is converted to the multi-line storage mode, when the server receives different types of query requests, first, the SQL engine in the computing layer as shown in Figure 8 and the user That is, the SQL engine in the computing layer is responsible for processing the SQL statements corresponding to different query requests initiated by the user, parsing the SQL statements and formulating query plans. That is, in the computing layer, the server can determine the execution time, waiting time and transmission time of each query request, and determine the optimal storage mode corresponding to each query request based on the execution time, waiting time, transmission time and preset weight.

For example, as shown in Figure 8, there are three storage nodes in consensus group 1, namely storage node 1, storage node 2 and storage node 3. The storage mode corresponding to storage node 1 shown in Figure 8 is row storage mode, storage node 2 and storage node 3. The storage mode corresponding to the storage node 2 is the column segment storage mode, and the storage mode corresponding to the storage node 3 is the row storage mode. When the server of storage node 1 receives query request A, the server determines the execution time, waiting time and transmission time of query request A, and determines the corresponding query request A based on the execution time, waiting time, transmission time and preset weight. The optimal storage mode is the column-segment storage mode. Since the storage mode corresponding to the current storage node 1 is the row-storage mode, the server can route the query request A to the replica node corresponding to the column-segment storage mode, that is, storage node 2. The storage node 2 is made to perform data query processing based on the query request A. If the server determines that the optimal storage mode corresponding to the query request A is the row storage mode, since the storage mode corresponding to the current storage node 1 is the row storage mode, there is no need to route to other replica nodes for processing. If the current storage node 1 fails and becomes unavailable, the server can route the query request A to another replica node corresponding to the row storage mode, that is, the storage node 3, so that the storage node 3 performs data query processing based on the query request A.

In the embodiment of the present application, for the two major modules of the computing layer and the storage layer, their specific functions are as follows:

1. Computing layer:

The optimal storage mode can be determined through the computing layer, and reference may be made to step 210 in the above-mentioned embodiment of FIG. 2 . Specifically, the specific functions of the computing layer are as follows:

1. Interact with user input.

2. Responsible for processing the SQL statement of the business, parse it and formulate a query plan, that is, the server can determine the execution time, waiting time and transmission time of each query request according to different types of query requests received, and based on the execution time, waiting time Time, transmission time and preset weight, determine the optimal storage mode corresponding to each query request, and route each query request to the replica node corresponding to the optimal storage mode, so that the replica node can perform data query based on each query request.

3. For different workloads, determine the storage mode of the data table in the database based on the partition mode, candidate grouping range, data density and size of the first space, and route to different nodes for execution.

4. When the metadata changes, the computing layer re-selects the appropriate storage mode.

In this embodiment, the improvement of the computing layer mainly lies in the formulation of query plans, that is, the computing layer will analyze and process according to the current state of the system, and select appropriate storage modes for different query requests. Section 2 is described in detail; requests for metadata changes are discussed in Section 12.

2. Storage layer: The storage layer is further divided into transaction processing layer, distributed consistency protocol layer and state machine. The functions of each module are as follows:

1. Transaction processing layer:

The transaction processing layer is responsible for: 1) receiving transaction processing requests sent by the computing layer 2) coordinating and processing 2pc transactions.

The changes to the transaction processing layer in this embodiment are mainly for different storage modes, and the granularity of the lock will change accordingly during transaction processing. The specific transaction processing process will be described in detail in Section 5.

2. Distributed consistency protocol layer:

The distributed consistency protocol layer is responsible for: 1) controlling data synchronization and ensuring data consistency between replicas; 2) receiving and processing read and write requests from the computing layer, and controlling access to data in the storage layer; 3) master node election.

The distributed consistency protocol layer adopts the Raft protocol, which is divided into two modules: leader, that is, master node election and log replication. Raft is a strong leader consistency protocol. When writing data, it must pass through the primary node and then replicate to other secondary nodes to ensure data consistency between replicas. The workflow of the Raft protocol will be described in detail in Section 10. The storage mode used by each copy can be the same or different. In this method, Raft is used to realize the heterogeneity among multiple copies. The specific scheme is described in detail in Section 8. At the same time, each replica can switch the storage mode according to the different load during the running process. The specific content is elaborated in Section 4. In the actual operation of the distributed system, the configuration of replicas, the splitting and aggregation of data on the replicas, etc. are all controlled by the multi-replica manager. The management strategy of the multi-replica manager will be elaborated in Section 9.

3. State machine:

The state machine is responsible for: 1) receiving and processing access requests from the distributed consistency protocol layer; 2) managing multiple copies of data to ensure data consistency between copies.

In this embodiment, the state machine adopts RocksDB. RocksDB is a storage engine based on LSM-Tree KV. It uses key-value pairs as the basic unit of storage, and aggregates data into SSTables and stores them in a hierarchical structure. Introduction to LSM-Tree It will be elaborated in Section 11.

The focus of this embodiment is on the coding part at the interface of the storage layer. Different coding schemes are used to realize a diversified storage structure, and an adaptive algorithm is used to formulate an optimal scheme for loads with different access characteristics. The specific coding scheme is The implementation is elaborated in Section 3. The processing flow of the adaptive algorithm is elaborated in Section 7.

Section 2 - Storage Mode Expansion

In the storage engine based on LSM-Tree KV, the external order of KV cannot be guaranteed, only the internal order of KV can be guaranteed not to be destroyed, so what data is mapped into a KV has a great impact on the overall read and write performance of the system, in order to ensure data The ordering of the data is sorted before the data is mapped to KV, and then the overall result is mapped to a KV, that is, a larger amount of data can be placed in a KV pair. Since the KV pair is the basic unit in the KV storage system, it can ensure that the internal data will be accessed sequentially. According to the method provided by the present application, more storage modes can be obtained according to the granularity and sorting method of the data. details as follows:

1. Line storage:

Data is stored in the underlying storage engine in a row as a KV pair. As the most intuitive and common storage method, row storage has relatively balanced read and write performance. The storage method of row storage is very common in stand-alone databases, such as MySQL and PostgreSQL, which use row storage. Row storage is widely used in distributed databases such as Spanner and TiDB. When dealing with TP-type transactions, row storage can often achieve better performance, because the operation granularity of TP-type transactions is row-based. However, when processing AP-type queries, row storage will expose problems such as low amount of effective data and low total bandwidth.

2. Column storage:

Data is stored in the underlying storage engine with a column as a KV pair. Like row storage, column storage is a common storage mode. Column storage often has better performance for AP-type queries. When considering the physical implementation, the size of the KV cannot be increased infinitely. When the columns in the storage mode face a large amount of data, they will show a huge performance disadvantage or induce other engineering problems. Therefore, in the method of the present application, it is only recommended to use this storage mode on tables with a small amount of data, such as the Warehouse table in TPC-H.

3. Cell storage:

Store by cell refers to storing cells in a row or column as KV pairs in the underlying storage engine. The cell storage breaks the storage mode of the entire row and column, making the granularity of the KV unit smaller. In some workloads that only operate on a single cell, there will be better performance advantages. In the traditional storage mode of row storage and column storage, when a cell needs to be updated, the server must first read out the entire row and column data, modify it and then write it back, which causes serious read and write amplification. Cell storage is a good way to eliminate this write amplification. Among them, cell storage can be divided into: 1) cell row storage and 2) cell column storage, as follows:

1) Cell row storage: Cell row storage refers to organizing cells according to the row format, so that the overall storage is continuous on the row, as shown in Figure 9, which is a schematic diagram of cell row storage. row1co1 in the first cell in the first row of the first column in Figure 9 represents the first row and the first column. The key in Figure 9 is: tableID+rowID+columnID, which means: table ID+row ID +Column ID.

2) Cell column storage: Cell column storage refers to organizing cells in a column format to maintain the continuity on the column, as shown in Figure 10, which is a schematic diagram of cell column storage. The row1co1 in the first cell in the first row of the first column in Figure 10 represents the first row and the first column. The key in Figure 10 is: tableID+columnID+rowID, which means: table ID+column ID +Line ID.

4. Multi-line storage:

Multi-row aggregation refers to storing multiple rows as a KV pair in the underlying storage engine. Compared to treating a row as a KV, the granularity of its KV storage becomes larger. For scan operations, the amount of data read each time will have a great impact on performance. Therefore, compared with single-row KV, in the case of multi-row aggregation, the performance of scan operations will be greatly improved. At the same time, there will also be problems in the update of multi-row aggregation. Updating a row in multiple rows means that a larger granularity of RMW is required. In response to this problem, a Merge scheme is proposed, which is to store a row to be updated in Memtable first, and then merge it into the row group when Rocksdb performs Compaction. As shown in Figure 11, it is a schematic diagram of multi-line storage. In Figure 11, row1co1 in the first cell in the first row of the first column represents the first row and first column. The key in Figure 11 is: tableID+groupID, which means: table ID+row group ID.

5. Column segment storage:

Column segment storage means that at least two cells in a column are aggregated into one KV for storage. This mechanism can be understood as MySQL's vertical partition. The reason for introducing this mechanism is that a query may not need to store all of the entire column. All column data is returned. For some specific workloads, the performance will be improved after the introduction of column segments. As shown in FIG. 5 , it is a schematic diagram of a column segment storage format.

6. Column family storage:

Data is aggregated in column families. A column family represents a set of attributes in a data table, that is, at least two cells in a row are aggregated into a KV for storage. In practical use, columns that are frequently read/written together are often set as a column family to improve system throughput. When data is aggregated in column families, optimizations for specific queries can be achieved. Treating the column family as a key-value pair can effectively improve the performance of such queries. As shown in Figure 12, it is a schematic diagram of the column family storage format. The row1co1 in the first cell in the first row of the first column in Figure 12 represents the first row and the first column. The key in Figure 12 is: tableID+CF ID+rowID, which means: table ID+column Family ID + Row ID.

7. Column family segment storage:

In column family storage, certain attributes in a row are aggregated into a KV pair. Column family segment storage means that several attributes in multiple rows are aggregated into a KV pair, thereby improving the throughput of the system in the AP scenario. That is, it can be understood as increasing the number of rows stored in the column family. As shown in FIG. 6 , it is a schematic diagram of column family segment storage.

8. Whole table storage: Whole table storage refers to storing the entire table as a KV. The performance of the entire table is significantly improved under the query condition of full table scan. As shown in Figure 7, it is a schematic diagram of the entire table storage.

Section 3 - Coding Schemes

This section provides a detailed introduction to the encoding schemes for various storage modes. As shown in FIG. 13 , it is a schematic diagram of a coding scheme of diversified storage modes.

1. Row storage coding scheme:

The row store takes the data of a row in the data table as a KV pair. In coding, the table ID, namely TableID, and the row ID, namely RowID, are used as Key, and the data in this row is stored as Value. In implementation, the Key may include timestamps, Hash values, and other information.

2. Column storage coding scheme:

The column store takes the data of a column in the data table as a KV pair. In coding, the table ID, namely TableID, and the column ID, namely ColumnID, are used as Key, and the data in this entire column is stored as Value. In an implementation, the amount of data in an entire column can be large, so this encoding has the potential to produce large KV pairs.

3. Cell storage coding scheme:

Cell storage treats a cell in the data table as a KV pair. There are two ways to encode by row and by column. For example, TableID, RowID, and ColumnID are encoded as Key in sequence, and the data stored in this cell is stored as Value. This encoding method will make each KV pair arranged in the SST according to the same RowID, which belongs to the row storage. In the same way, if the Key is encoded in the order of TableID, ColumnID and RowID, the KV pairs are arranged in the SST according to the same ColumnID, which belongs to the column storage.

4. Multi-line storage coding scheme:

Multi-row storage groups several rows in the data table into a group and stores them in the same KV pair. In coding, the TableID and the group ID, that is, the GroupID, are used as the Key, and the data in the group is stored as the Value.

The GroupID is determined by the grouping method. Common grouping methods include index grouping and hash grouping. Index groups are grouped in the order in which data is inserted, and consecutive data tuples are stored in the same group until the group is full of data. The hash grouping maps the RowID of the data tuple to the GroupID based on a certain hash function, such as an integer division function, and stores it in the group.

5. Column family storage coding scheme:

Column family storage aggregates certain attributes of a row in a data table into a group. In coding, the TableID, the group ID, that is, the GroupID, and the row ID corresponding to the row, that is, the RowID, are used as the Key, and some attributes in the row are stored as the Value.

6. Column family segment storage coding scheme:

Column family segment storage aggregates an attribute group in a row in the data table into a column family, and then aggregates several consecutive column families. Among them, the method of attribute aggregation is the same as that of column family, and the method of grouping is the same as that of multi-row storage. That is, at least two cells in each row in the horizontal direction of the data table are aggregated into a data group, and at least two cells in each column in the vertical direction in the data table are aggregated into a column group; in coding, The TableID, the identifier CFID of the column group, and the group identifier GroupID of the data group are used as the Key, and the data in the column group and the data group are stored as the Value.

7. Column segment storage coding scheme:

Column segment storage aggregates several consecutive cells in the same column in the data table into a KV pair. In coding, use TableID, ColumnID and column grouping CFID as Key, and store the data in the column grouping of this column as Value. The column segment memory also needs to determine the way of grouping. The grouping method is consistent with the multi-line storage. Compared with cells stored in columns, when processing full table scan operations, due to the larger granularity of column segments, the number of kv pairs read can be reduced, thereby improving overall performance. Compared with column storage, column storage aggregates all data in a column into a kv pair. It can be considered that column segment storage decomposes a kv pair in column storage into several small kv pairs. The size of column segment memory is between single-column memory and column memory, which can balance read and write performance.

8. Entire table storage coding scheme:

The whole table storage aggregates the data of the entire data table into a KV pair. In coding, TableID is used as Key, and all data in the data table is stored as Value. For full table storage, it is necessary to determine the internal data arrangement of the KV pair, and the options include row-by-row and column-by-column. Full table storage will generate huge KV pairs, so in practice it is only suitable for smaller tables.

Section 4 - Interconversion of storage modes

This section mainly discusses the conversion between different storage modes.

In actual operation, the system can automatically switch the storage mode of replicas according to different workloads. When the adaptive module senses a change in load, it evaluates the optimal storage mode and the corresponding conversion cost. When the system is relatively idle, the storage mode conversion can be performed to convert the current storage mode into a new optimal storage mode. For example, when the adaptive model determines that the storage model required by the current workload is column storage, but there is no column storage mode in the current node, a replica node needs to be selected to convert the storage mode, which may be the conversion from row storage to column storage. The load of the node needs to be considered during the conversion, and the node with the smallest load is preferred. The specific adaptive transformation method is described in detail in Section 7 Query Adaptation. By calculating the operating parameters of the current load, plus the structure and data distribution of the current data table, the optimal storage mode can be solved through the adaptive model. Considering that a total of 8 different storage modes are discussed in Section 3, there are 7*8=56 corresponding conversion modes, as shown in Figure 4.

Since there are many types of transformations, we abstract them into two types of transformations, namely splitting and reorganization, as follows:

1. Splitting: The application scenario of splitting is mainly that the data is changed from a large KV to several smaller KVs. Here, the conversion from single-line storage to cell storage is taken as an example to describe in detail:

When data is written in row storage mode, its key is encoded in the form of table ID + row ID. In some scenarios, the server needs to convert row storage mode to cell storage mode, so the server needs to change each attribute in Value Recode, set a corresponding CeilID (TableID+RowID+ColumnID) for each attribute, and split the data from row storage mode into Ceil (cell storage) storage mode.

2. Reorganization: The application scenario of reorganization is mainly to reorganize data from several smaller KVs into a larger KV, for example: conversion from single-line storage to multi-line storage, conversion from cell storage to row storage, etc. Here, the unit The conversion from grid storage to column storage is taken as an example to describe in detail:

Assuming that the data on a copy starts to be stored in cell storage, as the load changes, we need to convert the storage mode of the copy to column storage, but the cells required for column storage are not enough, we temporarily store these cells Write into the buffer, and then re-encode and convert when the buffer has accumulated enough for the number of column-to-store conversions.

Section 5 - Impact of novel storage modes on transactions

This section mainly introduces the impact of the new storage mode on transactions in the database:

The transaction concurrency control mechanisms of mainstream NewSQL databases (CockRoachDB, TiDB, TDSQL3.0) are all bound to KV. Taking locks as an example, the traditional one-row-one-KV storage mode corresponds to row locks in traditional databases. When different storage modes are used, such as KV split into cell granularity, it corresponds to smaller granularity locks, while KV aggregated into multiple row or column segment granularity corresponds to larger granularity locks. For the former, as long as each read and write is guaranteed to acquire the locks of all relevant KVs, the correctness of the corresponding transaction can be guaranteed; if each write acquires the locks in the order defined by the fields corresponding to the cells, the It can destroy the cyclic waiting in the deadlock condition, and will not cause more deadlocks. That is, in the embodiment of the present application, in order to eliminate the deadlock, the locking unit sequencing method can be adopted. Deadlock, such as a row of data contains two fields id and name, transaction A and transaction B access this row of data at the same time. Transaction A locks the id first, and transaction B locks the name first. At this time, transaction A waits for transaction B to release the lock on name, transaction B waits for transaction A to release the lock on id, and waits for each other to release resources, that is, death occurs. Lock. After adopting the ordering strategy, this phenomenon can be avoided: it is stipulated that the id must be locked first, and then the name can be locked. At this time, after transaction A locks the id, transaction B tries to lock the id and finds that it is occupied, so it enters the waiting queue. There is no deadlock at this point.

Section 6 - Query Optimization

This section mainly introduces how the computing layer optimizes the query plan based on metadata, query characteristics, storage mode and other information, and improves the query performance of the database system based on diversified storage modes.

The query cost is an important indicator for formulating a query plan, which consists of three parts: execution time T _proc , waiting time T _wait and transmission time T _trans , that is, T=T _proc +T _wait +T _trans . In these three parts, the execution time consists of the search time T _search , the processing time T _io and the tuple construction time T _cons , namely T _proc =T _search +T _io +T _cons ; the waiting time is composed of the request queue time T _queue , the machine load The delay T _load is composed of the slave node data synchronization time T _sync , namely T _wait =T _queue +T _load +T _sync ; the transmission time is the time of network transmission. In this solution, the influence of multiple copies on query plan formulation is mainly considered, so the influence factors of execution time are mainly considered. Several strategies are considered here:

1. If the wide table has fewer columns, the column storage mode takes precedence. The storage mode mainly affects the execution time of the query. Directly selecting the column storage mode may reduce T _search and T _io compared with the row storage mode. However, due to the need to reorganize the results, T _cons may increase, and the number of columns required for the result is more. , the larger T _cons is. For analytical query requests, count the number of columns Col required by the request and the total number of columns Col_num in the table. If Col/Col_num<α, where the threshold α can be adjusted according to the actual situation, it is considered that the column storage mode is the best storage mode. If Col/Col_num≥α, it means that there are many columns to be read. Generally, the storage mode of row storage or multi-row storage can be used. For example, 19 out of 20 columns need to be read, 19 iterators need to be created when reading in the column storage mode, and only one iterator needs to be created in the row storage or multi-row storage, the overall overhead will be reduced.

2.Scan scan is multi-line storage priority. Since the scan operation needs to scan multiple rows of data or even the entire table data in sequence, storing data together in the storage mode aggregated by multiple rows can effectively reduce T _search and T _io compared to other storage modes, and the upper-level results do not need to be reorganized , has no effect on T _cons , so the multi-line storage mode can be used as the best storage mode for Scan operation.

3. Click the query to save the line first. The query goal of point query is to obtain a certain piece of data that meets the expectations. Regardless of the column storage mode or multi-row aggregation, the data needs to be split at the upper layer, which will lead to an increase in T _cons . The row storage can simultaneously ensure that T _search and T _io are not affected. In the case of influence, T _cons is optimal, so it can be considered that row storage is the best storage mode for point queries.

4. For update operations, cell storage takes precedence. The update operation is often to update an attribute in a row. Selecting row storage requires reading the entire row of data and then modifying it, and then writing the entire row, resulting in read and write amplification. Selecting column storage will also have the same impact. It has an adverse effect on T _io and T _cons . Logically, cell storage can just match the granularity of update operations, so it can be considered that cell storage is the best storage mode for update operations.

At the same time, we also discuss other factors that affect the query plan, as follows:

5. The replica where the node with low load is located has priority. The load of the node where the replica is located mainly affects T _queue and T _load in the waiting time of the query. The lower the node load, the smaller the time of these two items. The load status of the nodes where each replica is located can be obtained from the metadata manager, and the replica with the lowest load on the node is selected as the best replica.

6 Near computing nodes are preferred. The physical distance from the node where the replica is located affects the transmission time T _trans , the closer the distance, the smaller the T _trans . Multiple copies of data shards may be scattered in different computer rooms or even different data centers. Selecting the node where the copy of the nearest computing node is located can reduce the overhead of network transmission.

7. The copy with the latest data synchronization status takes precedence. The read request needs to wait for the node log to be synchronized to the latest. The synchronization time T _sync affects the waiting time T _wait . Therefore, the newer the data synchronization state of the replica, the shorter the waiting time.

The above strategies can work individually or in combination through weights and other methods. The formula for the total cost of the query is as follows:

C=a1(t _search +t _io )+1/a1(t _cons )+a2(t _queue +t _load )+a3(T _trans )+a4(t _sync )

Among them, a1, a2, a3, and a4 represent the weight of each strategy, where a1 specifically represents the weight of the storage mode selection strategy, and a2 and a3 represent the weight of other strategies. The selection of the strategy needs to consider the actual system situation. In actual deployment, due to the influence of factors such as node performance and network speed, there are differences in the magnitude of T _proc , T _wait and T _trans . The weight setting should ensure that the part with a longer total time is accelerated as much as possible.

Since t _search , t _io , and t _cons are all related to the choice of storage model, when the choice of storage model is more favorable to t _search and t _io , it will deviate from the storage model of tuples, so that the construction time of tuples (t _cons ) increases, and the two are inversely proportional. Therefore, in the total query cost, when we choose a storage model that is more conducive to query requests to shorten t _search and t _io , the weight a1 increases, which also means that the weight of t _cons decreases, and the weights of the two are inversely proportional. relationship, therefore, set the weight of t _cons to 1/a1.

Section 7 - Storage Mode Adaptive Adjustment Method

This section will undertake the various storage structures discussed in Section 2, and continue to discuss how to decide the most suitable storage structure for the characteristics of different loads in the actual system of the database. For each data table, we can use the adaptive storage mode to decide the optimal storage scheme.

As shown in FIG. 14 , it is a flowchart of the storage mode adaptation process. The method of storage mode adaptation is divided into the following six steps:

1. Build performance models for different KV pair sizes.

2. Collect the operating parameters of the load.

3. Calculate the optimal range of the size of the KV pair according to the load I/O operation ratio, and the optimal range may be the first space size of the space occupied by the key-value pair in the above embodiment.

4. According to the query statement information of the load, a candidate solution for column partitioning (ie, the partitioning method in the above embodiment) is determined.

5. Determine the candidate grouping range and data density according to the data distribution of the load.

6. Consider the partition mode, candidate grouping range, data density and first space size obtained in 2, 3, and 4, and decide the optimal storage mode.

Step 1 Through a series of experiments in advance, measure the performance of each size KV pair under each typical I/O operation (such as update, insert, point query, delete, range query, etc.), these test results will be used as the judgment of subsequent steps in accordance with.

Step 2 needs to collect the parameters of the database when the load is running normally, which can be used as a basis for decision-making in the subsequent steps. The database at this time can be any storage mode. In general, row memory can be selected as the benchmark mode for testing. In this step, the information to be collected includes the following three types. One is the proportion of each I/O operation in the load, such as the corresponding proportion of single-point query, update, insert, delete, and full table scan. The second is the proportion of all query statements involved in the load, and the meta information corresponding to the columns involved. The third is the distribution of data in the load, such as the scope of the primary key and the corresponding proportion.

Step 3: According to the proportion of each I/O operation, find the appropriate KV pair size. The KV pair of the key-value storage system has a great impact on performance. Generally, KV pairs with large granularity are more suitable for processing full table scan operations, and KV pairs with small granularity are more suitable for processing single-point query, update, insert, delete and other operations. According to the proportion of various I/O operations counted in step 2, and the performance of various I/O operations of each possible KV pair size in step 1, through the weighted average method, it can be estimated that the current workload is in each The overall performance under various KV pair sizes can be selected, and the KV pair size with the highest overall performance can be selected as the system setting.

For example, the current workload contains 1000 checkpoints, 10 full table scans involving 100000 rows, 1000 update operations, inserts, deletes. Combined with the performance of each size KV pair collected in step 1 under different I/O operations, such as (in the check operation, the delay of 16B KV pair is 0.01ms, and the delay of 32B is 0.005ms), it can be estimated that the 16B KV pair has a delay of 0.01ms. The time-consuming of the KV pair in the enumeration is 1000*0.01ms. By analogy, the time-consuming of 16B KV pairs in full table scan and update can be calculated, and the summation is the total time-consuming. The weight of the weighted average mentioned in this paragraph is the total number of rows involved in each operation in this example. Similarly, for other sizes of KV pairs, an estimated total time can also be obtained. Finally, the KV pair size with the shortest estimated total time consumption is the optimal KV pair size.

Step 4: According to the semantic information of the query statement and the information of related columns, a candidate scheme of column partitioning is deduced. As shown in (1) in Figure 3, partitioning divides a data table into subsets in the vertical direction. First, the server obtains all the queries and corresponding scales involved on the data table. For each query, the server can parse its grammar, extract and save the column information involved from the projection clause and the WHERE conditional clause. After that, the server can sort each query statement according to the proportion of various query statements faced by the application, and retrieve the top n query statements with the highest proportion. Then, the server can start with the query with the highest proportion and partition according to the relevant column corresponding to the query. After that, the server takes out the query with the second highest proportion and repeats the partition operation until all attributes have been partitioned.

In addition, the partitioning algorithm is dealing with the same column in multiple queries, these columns are called "conflicting columns", and different strategies can be adopted: the first strategy is that the high-priority query, i.e., the top-ranked grouping exclusives the conflicting columns. Under this strategy, more important queries, i.e. higher priority or more weight, add the conflicting column to their own grouping, while other groupings do not include this column. The second strategy is to combine these groupings. Under this strategy, groups containing conflicting columns are merged into a larger group. The two strategies have their own advantages. The first strategy is more inclined to meet the characteristics of high-priority queries, and is more suitable for situations where the proportion of different queries is far apart; the second strategy , which is more suitable for cases where the proportion of different queries is not very different.

Step 5: According to the data distribution of the load, obtain the candidate grouping range and data density. Grouping and aggregation can aggregate multiple rows of data into a KV pair, improving the efficiency of reading and writing data. The grouping strategy and the size of the grouping need to be determined according to the data distribution of the current load. As shown in (1) in Figure 3, grouping divides a data table into several subsets in the horizontal direction. Grouping strategies include hash grouping and sequential grouping. Hash grouping stores data of the same hash value in the same data group through a certain hash function. Sequential grouping is to store a series of consecutive data in the same data group according to the arrival order of the data. A common and feasible way to determine the optimal grouping range and data density is as follows:

i) The grouping function adopts a hash function. If the value of the primary key is used to divide the grouping range, the result of the division is the grouping sequence number. For non-integer data, if the grouping range is a power of 2, it can be grouped by bitwise right shift. For example, the primary key of a row of data is of type int and the value is 32. Another row of data has a primary key value of 31. At this time, the hash function is used to group the serial number=key divisible by 16. For the data whose key is 32, its grouping sequence number=32 divisible by 16=2, it should be in the second group; for the data whose key is 31, its grouping sequence number=31 divisible by 16=1, it should be in the first group.

ii) A set of grouping ranges are predefined. The value of the grouping range can be any integer, but in practice, to facilitate the implementation of the grouping algorithm and reduce the amount of calculation, a power of 2 can be taken as the grouping range.

iii) For each grouping range, calculate the average data density. Since the distribution of primary keys is not necessarily strictly increasing, it may happen that the actual elements in a group cannot reach the grouping range. For example, the grouping range is set to 8, but the data whose primary key is 1 to 7 does not exist in the data table, and only the data whose primary key is 0 is assigned to this group. Therefore, these positions are vacated, and the density of the packet is 1/8 at this time. The average of the densities of all groups is the average data density under the grouping range.

The grouping range and average data density obtained in this step will be combined for decision-making in step 6. For the sequential grouping algorithm, the data density can also be calculated in the same way, and the corresponding parameters are submitted to step 6 for final decision. The size of the grouping is determined by the range and data distribution. For example, when hash grouping by primary key value, if some primary key value is not used, then those positions will be empty. The range of a group of groups can be predefined, the data distribution can be scanned, and the actual group size can be counted.

In step 6, the above three steps are considered comprehensively, and the optimal storage mode is obtained. As shown in (3) in Figure 3, the data table will be divided horizontally and vertically at the same time to obtain the final storage mode. According to the partition scheme given in step 4, the grouping range and data density obtained in step 5, the size of the KV pair can be obtained. Numerically, the extent of the grouping times the data density times the partition size should equal the size of the KV pair. When the size of the KV pair corresponding to a certain storage mode is equal to or closest to the size of the KV pair given in step 3, the storage mode is the optimal storage mode.

Section 8 - Heterogeneity of storage schemas

In order to meet the needs of different environments, we apply a multi-copy heterogeneous collaborative computing scheme based on the diversification of storage modes. After applying multi-copy heterogeneity, the problem of how to convert storage modes between different copies, the consensus problem of heterogeneous copies, and the transaction problems caused by heterogeneous copies will be introduced. The following is a detailed discussion:

1. Conversion between heterogeneous storage modes: Assuming that there are three members in our consensus group, which store S1 mode copies, S2 mode copies, and S3 mode copies respectively, from the perspective of the consensus protocol layer, the master node will still keep the same log It is sent to each node, and the state machine in the node will convert the format of the data into the corresponding storage mode according to the log translation technology in the node when applying the log, and then write it layer by layer.

2. Consensus problem between heterogeneous storage modes: In the conversion scheme between heterogeneous copies, the change of consensus group members, the transfer of data between nodes, and the persistence of snapshots to the state machine can all go through the original process of the consensus protocol. Implementation, can guarantee the correctness of the system. Since the storage mode switching involves the reading and writing of the state machine, during the storage mode switching process, the selection of the switching mode can be determined according to the node load: when the load of the node where the S1 mode copy is located is small and the available space of the node is large, choose direct switching . When the node load is large or the space is insufficient, it should be re-selected. In practice, when the row storage leader node in the system is offline and has not been successfully reconnected, a copy of other storage mode can be selected as a leader node as a temporary option, and then converted to a leader node after recovery.

3. Transaction problems of heterogeneous storage mode:

There are three main problems in the implementation of heterogeneous multi-replica: providing a read interface (that is, Follower Read) from the replica, concurrency control of the read transaction from the replica and the write transaction on the primary replica, and log translation issues.

At present, most NewSQL databases (CockRoachDB and TiDB) use the Lease Read mechanism for replica read implementation, while Spanner uses Paxos for replica synchronization. Synchronize to the slave node, that is, to ensure that the data before the timestamp has been copied and ensured to be up-to-date. If the read request timestamp is greater than the next time, it means that there may be data that has not been copied, and you need to block and wait.

The concurrency control of the read transaction from the replica and the write transaction on the primary replica mainly includes distributed locks and snapshot read security timestamps.

The distributed lock mechanism enables both the master node and the slave node to access the locks related to the current transaction by replicating locks among multiple nodes, thereby performing cross-node concurrency control. Taking TiDB as an example, in the Percolator transaction model of TiDB, three kinds of data need to be persisted, including the Lock (lock) required for transaction concurrency control. As a distributed database, TiDB itself provides a multi-copy mechanism of data, so Lock It is also used as a part of multi-copy replication data to synchronize between multiple copies, thus naturally providing distributed locks. However, due to the need to replicate a large amount of data across the network, distributed locks themselves are still an expensive concurrency control method. .

The security timestamp mechanism, that is, the master-slave node synchronization security timestamp mechanism, needs to satisfy that it is impossible for a new transaction to be submitted before. Therefore, snapshot read requests less than this timestamp at this time can be safely satisfied. At the same time, the slave node is only allowed to provide external snapshot reads less than this timestamp. Taking Spanner as an example, in addition to the above-mentioned timestamp to ensure data freshness, a secure transaction conflict timestamp will be maintained at the same time (in fact, the two timestamps will go to the minimum value and appear as one timestamp externally), One implementation is to record the Prepare timestamp and Commit timestamp of each distributed transaction. In this case, the minimum Prepare timestamp of all write transactions on the master node can be used as the security timestamp to ensure that commits before this timestamp can be guaranteed. All transactions have been committed. Even if the ongoing transaction may be committed, the commit timestamp must be after the security timestamp. At this time, the read transaction on the secondary node with a timestamp smaller than this timestamp must not have concurrent write transactions that would cause conflicts. , although this eliminates the cost of maintaining distributed locks, the above timestamp itself represents the overall safe and readable time of all data of a certain shard. If the scope of the read transaction on the secondary node and the primary node are The data range of the concurrent write transaction does not conflict. In fact, the secondary node only needs to wait for the synchronization of the multi-copy data to complete before executing the read transaction. However, at this time, due to the existence of the security timestamp of the transaction, the secondary node only knows that there is concurrency on the leader. It is difficult to confirm the write set of the transaction, so it is difficult to reduce the granularity of the security timestamp. Although CockroachDB also naturally provides distributed locks due to the fact that there is a mechanism similar to TiDB in its transaction mechanism, and the lock (Write Intent) is used as persistent data for multi-copy replication, it still chooses the implementation of secure timestamps.

In a Raft system using heterogeneous replicas, non-row-stored replicas can be selected as Leader nodes, but it may reduce the performance of the overall system. More generally, a replica of any storage mode can be used as a leader node, and the data of this storage mode is recorded in the Raft log at this time. Some storage modes, such as row storage and column family storage, have better write performance and are more suitable as row storage; while some storage modes, such as column segment storage, have poor write performance and are not suitable for row storage. For example, when the column segment is used as the leader, all write operations will be converted into multiple write operations, resulting in a decrease in the overall system write performance. Therefore, under normal circumstances, replicas with poor write performance are not recommended to be elected as leaders. In practice, when the leader node with good write performance in the system is offline and has not been successfully reconnected, copies of other storage modes can be selected as the leader node as a temporary option, and then converted to the leader node after recovery.

Section 9 - Multiple Replica Management Strategies

This section mainly introduces the management strategy of multiple copies in the storage layer.

1. Copy storage mode switching: For a copy in the storage layer, its storage mode can be dynamically adjusted during the actual operation of the system. The scheme is as follows:

A new copy of the data shard is established on the current node, which is not counted as a consensus group member (that is, does not participate in all processes of consensus, only synchronizes data). Read the data of all S1 mode replicas, generate new data in the S2 mode through the format converter, re-persist it to the state machine through the new temporary replica, and synchronize the unpersisted logs of the S1 mode replica to the new replica. After the synchronization is completed, the copy of the S1 schema is destroyed, and the S2 schema is added to the consensus group as a new member.

2. Replica configuration strategy: For each data shard, the replica configuration strategy is not static. During the operation of the system, the number of replicas in different storage modes is adjusted according to the changes in the data access mode (load changes). , When the load of the column storage copy is large, it is judged that the current load is a partial column storage type on the data shard, and select the copy in the storage type with a small number of processing requests (representing the low load of this type) during this period of time. Switch to columnar copy.

3. Data splitting: When a data fragment is too large or the data is overheated, in order to balance the load, the system re-splits the data fragment to split one data fragment into two data fragments. The replica configuration status of the newly generated data shard can be selected to be consistent with that before the data split, or can be re-determined and configured through the policy manager.

For example: when the row-stored copy is split, only part of the data needs to be migrated separately; when the column-stored copy is split, because the cost of reorganizing all rows in the column-store format is high, splitting directly from the row-stored copy and Convert to columnar storage format, and destroy the split columnar storage copy after completion.

4. Error handling: When one or several copies of a data shard fail to work properly, a new copy should be created immediately to ensure that the total number of copies matches the expected configuration. The storage mode used by the newly online copy is determined by the current policy configuration of the system, and may not be consistent with the state before the error. For newly online replicas, if there are other replicas with the same storage mode, synchronize data from this replica (this replica needs to be synchronized with the primary node first). If not, synchronize data from the master node using the scheme for re-selecting nodes in the schema transition above. Consensus protocol guarantees the availability of data shards and the correctness of replica data in the process of creating a new replica and after the creation of a new replica.

Section 10 - Raft Workflow

Raft is a consensus protocol that is easy to understand and easy to build practical systems. It decomposes the consensus algorithm into three modules: leader election, log replication and security. By first electing a leader (Leader), the leader is responsible for log management to achieve consistency, which greatly simplifies the state to be considered and enhances It improves the comprehensibility and reduces the difficulty of engineering practice.

1. Node status

There are three types of nodes in the Raft cluster, namely Leader, Follower, and Candidate. There is only one Leader node, and all other nodes are Followers. Raft will first elect a leader, and the leader will fully manage the replica log. The Leader is responsible for receiving the log entries of all clients and copying them to other Follower nodes, and telling each Follower to apply these log entries to their own state machines when it is safe. If the leader fails, the Followers will re-elect a new leader. Followers do not send any requests themselves, but are only responsible for responding to requests from Leaders and Candidates. If Followers cannot receive messages, they will convert to Candidates and initiate Leader elections. Candidates that get most votes in the cluster will become Leaders.

Raft divides time into terms of arbitrary length, each term has a term number, and a new term starts with each leader election. If the Leader or Candidate finds that its term number is out of date, it will immediately switch to the Follower state: if a node receives a request containing an outdated term number, it will reject the request. The conversion relationship between Follower, Candidate and Leader is shown in the figure:

2. Leader election

Raft triggers leader election through the heartbeat mechanism. In the initial state, each node is a Follower. The follower node and the leader node maintain continuity through the heartbeat mechanism. If no message is received within a period of time, the follower considers that the system has no available leader and initiates a leader election.

The Follower node that initiates the election increases the local current term number, and the Follower state switches to Candidate, then it will vote for itself and send the voting request to other Follower nodes. Each Follower node may receive multiple voting requests, but it can only cast one vote on a first-come, first-served basis, and the log information owned by the candidate node that has won the vote cannot be older than its own.

Candidate waits for voting replies from other Follower nodes, and the received replies may have the following three results:

The Candiadate node receives more than half of the votes, wins the election, and becomes the leader. At this time, it will send heartbeat messages to other nodes to maintain its leader status and prevent the generation of new elections.

The Candidate node receives a message with a larger term number sent by other nodes, which means that other nodes are elected as Leaders. At this time, Candidate will switch to the Follower state. If Candidate receives a smaller term number, the node will reject the request and keep the Candidate state.

If each candidate node does not get half of the votes, the election times out. At this point, each Candidate node starts a new round of election by incrementing the current term number. In order to prevent multiple election timeouts, Raft uses a random election timeout algorithm. When each candidate starts an election, a random election timeout will be set to prevent multiple candidate nodes from timing out at the same time and starting the next round of elections at the same time. Likelihood of votes being split in new elections.

In a Raft system that uses heterogeneous replicas, unlike traditional Raft, the storage mode of the leader has a great impact on the performance of the overall system. Therefore, the weights of different storage modes in leader election should also be different. For example, the row storage mode is more suitable for processing write operations, so the weight in the election should be higher; the column storage mode is not suitable for processing write operations, so the weight in the election should be lower.

3. Log replication

Each server node is implemented by a replicated state machine based on a replicated log. If the initial state of the state machine is the same and the order of execution instructions obtained from the log is also the same, the final state of the state machine must also be the same.

When the leader is elected, the system provides services to the outside world. The leader receives requests from clients, and each request contains a command that acts on the replica state machine. The Leader encapsulates each request into a log entry, appends it to the tail of the log, and sends these log entries to the Followers in parallel in order. Each log entry contains a state machine command and the current term number of the leader that received the request, as well as an index of the log entry's location in the log file. When the log entry is safely replicated to the majority of nodes, the log entry is called Committed, the Leader returns success to the client, and notifies each node to apply the state machine commands in the log entry to the replicated state machine in the same order. The log is called Applied.

In a Raft system using heterogeneous replicas, the same log synchronization process is used as in traditional Raft. After the log is synchronized, the information in the log needs to be replayed before it can be converted into table-structured data. At this time, since the structure of Leader and Follower may be different, the process of log playback is more complicated than traditional Raft. When a Follower performs log playback, it can usually adopt batch processing to convert a batch of data into the corresponding storage mode at the same time, so as to reduce the extra overhead caused by log playback.

It can be seen that Raft log replication is a Quorum process that can tolerate n/2-1 replica failures. The leader completes the log for the lagging replicas in the background.

In order to ensure that the follower's log is consistent with the leader's, the leader needs to find the index position of the follower and its log, and let the follower delete the log entry after this position, and then send the entry after the index position to the follower. In addition, the leader maintains a NextIndex for each follower, which is used to indicate the index of the next log entry that the leader will send to the follower. When a leader starts its term, it will initialize the NextIndex to its latest log entry index + 1. If the follower finds that its log index is inconsistent with the leader in the pot of consistency check, it will refuse to accept the log entry. After the Leader receives the response, it decrements the NextIndex, and then tries again until the nextIndex reaches a position consistent with the Leader and Follower logs. At this point, the log entry from the leader will be appended successfully, and the leader and follower's logs will reach an agreement. Therefore, the Raft log replicator has the following characteristics:

If two log entries in different logs have the same log index and term number, then the two logs store the same state machine commands.

If two log entries in different logs have the same log index and term number, then all log entries before them are also the same.

To prevent the committed log from being overwritten, Raft requires that Candidate needs to have all committed log entries. If a node is newly elected as Leader, it can only submit logs of the current Term that have been replicated to most nodes. Even if the log of the old term number has been copied to most nodes, it cannot be directly submitted by the current leader, but needs to be submitted indirectly through log matching when the leader submits the log of the current term number.

Section 11 - LSM-Tree

The full name of LSM-Tree is the log-structured merge tree, which was proposed by Professor Patrick O'Neil in The Log-Structured Merge-Tree in 1996. The name log-structured merge tree is taken from the log-structured file system. The implementation of LSM-tree is similar to the log file system. It is based on the immutable storage method and uses buffering and append-only writing to implement sequential write operations, avoiding most random write operations in the variable storage structure and reducing the impact of write operations. The impact of multiple random I/Os on performance improves the utilization of data space on disk. It guarantees the orderliness of disk data storage. The immutable disk storage structure facilitates sequential writes. Data can be written to the disk once, and it exists in the form of append only, which also makes the immutable storage structure have higher data density and avoids the generation of external fragmentation.

Since the file is immutable, write operations, insert operations and update operations do not need to locate the data location in advance, greatly reducing the impact caused by random I/O, and significantly improving write performance and throughput. However, for immutable large files, duplication is allowed. With the continuous increase of appended data, the number of disk resident tables continues to increase, and the problem of file duplication caused by reading needs to be solved. Maintenance of the LSM-Tree can be done by triggering a merge operation.

In LSM-Tree, data exists in the form of an ordered string table (Sorted String Table, SSTable). SSTable usually consists of two components, namely an index file and a data file. The index file stores keys and their offsets in the data file. The data file consists of concatenated key-value pairs, and each SSTable consists of multiple pages. When querying a piece of data, instead of directly locating the page where the data is located like the B+ tree, it first locates the SSTable and then finds the page corresponding to the data according to the index file in the SSTable.

1.LSM-Tree structure

The overall architecture of LSM-tree is shown in the figure, which includes memory-resident components and disk-resident components. When executing a write request to write data, the operation is first recorded on the disk CommitLog for fault recovery, and then the record is written to the variable memory component (Memtable). When the Memtable reaches a certain threshold, it will be converted into immutable memory Resident component (Immemtable) and flushes data to disk in the background. For the disk-resident component, the written data will be divided into multiple levels. The data input from Immentable will enter the Level0 layer first, and the corresponding SSTable will be generated. This method is merged into Level1ceng, and merged down layer by layer in this way.

Memory resident component: The memory resident component consists of Memtable and Immemtable. Data is usually stored in an ordered Skip List structure in Memtable to ensure the orderliness of disk data. Memtable is responsible for buffering data records and acts as the primary target for read and write operations. Immemtable completes the drop operation of the data.

Disk resident component: The disk resident component is composed of WAL and SSTable. Since the Memtable exists in the memory, in order to prevent the loss of data that has not been written to the disk in the memory due to system failure, before writing data to the Memtable, it is necessary to write the operation record to the WAL to ensure the persistence of the data record. SSTables are constructed from data records that Immetable flushes to disk. SSTables are immutable and can only be used for read merge and delete operations.

2. Update and delete of LSM-Tree

Since LSM-Tree is based on an immutable storage structure, the update operation cannot directly modify the original data, and only a new piece of data can be inserted with a timestamp as a mark. Therefore, the insertion operation and the update operation cannot be clearly distinguished in the LSM-Tree. The same is true for delete operations, which can be implemented by inserting a special delete marker, sometimes called a tombstone. This entry states that the data record corresponding to this key has been deleted.

3. LSM-Tree search

The access order of LSM-Tree to find a piece of data is as follows:

Access variable memory resident components.

Access immutable memory-resident components.

Access the disk-resident components, starting from the Level0 layer, because the data at the lower level is newer, so when you find the data you want to find, you can return immediately to get the latest value of the data.

In addition, there are some optimizations for read operations. Bloom filters are often used to determine whether an SSTable contains a specific key. The lower layer of the Bloom filter is a bitmap structure, which is used to represent a collection and can determine whether an SSTable contains a specific key. Whether an element belongs to this set. Applying a bloom filter can greatly reduce the number of disk accesses. However, it also has a certain false positive rate. Since its bitmap value is determined based on a hash function, a hash collision problem of multiple values will eventually occur. When judging whether an element belongs to a certain set, elements that do not belong to this set may be mistaken as belonging to this set, that is, the Bloom filter has false positives, and at the same time, judging that an element in the set needs to be multi-bit values in the bitmap 1, which also fundamentally determines that the Bloom filter does not have false negatives. That is to say, he may have the following two situations:

Bloom filter determines that an element is not in the set, then this element must not be.

Bloom filter determines that an element is in the set, then this element may or may not be.

4. Merging strategy of LSM-Tree

In LSM-Tree, with the continuous increase of disk resident table data, repeated data can be reduced through periodic compaction operations. There are two basic merge strategies, Tiered Compaction and LeveledCompaction.

(1) The specific manifestations of the two merger strategies

TieredCompaction: The maximum number of SSTable files allowed for each layer is determined by the same threshold. As Immemtable is continuously written into SSTables, when the number of SSTables in a certain layer reaches the threshold, all SSTables in the cover layer are merged into a large new SSTable , and place it on a higher level. The priority is simple implementation, but the disadvantage is that the space enlargement problem during merging is more serious, and the higher the level of the SSTable, the larger the read enlargement problem is.

Leveled Compaction: The SSTable size of each layer is fixed, the default is 2MB, and the maximum number of SSTables per layer is N times that of the first layer.

(2) The process of merging the strategy

When the L0 layer is full, all the SSTables in the L0 layer are merged with all the SSTables in the L1 layer, and the duplicate Key values are removed. Based on the size limit of the SSTable, multiple SSTable files are merged and classified into the L1 layer.

When the L1-LN layer is full, select an SSTable of the full layer and merge it with the next layer.

The advantage is that it reduces space amplification, but the disadvantage is that it can cause serious write amplification problems when merging.

5. Read Amplification, Write Amplification and Space Amplification

The LSM-Tree based on the immutable storage structure will have the problem of read amplification, just as the B+ tree based on the variable storage structure will have the problem of write amplification, which is inevitable. But different merging strategies in LSM-Tree will bring new problems. In the distributed field, the famous CAP theory proves that a distributed system can only satisfy at most two of the three items of consistency (Consistency), availability (Availability) and partition tolerance (Partition Tolerance). Similar to this, Manos Athanassoulis et al. proposed the RUM conjecture in 2016, which pointed out that for any data structure, at most Read Amplification, Write Amplification and Space Amplification can be optimized simultaneously. ) at the expense of the other. To sum up, LSM-Tree based on immutable storage structure will face the following three problems when storing data.

Read amplification, in order to retrieve data, requires layer-by-layer search, resulting in additional disk I/O operations, especially in range queries, the phenomenon of read amplification is obvious.

Write amplification, which is continuously rewritten to new files during the merge process, causes write amplification.

Space enlargement, because duplication is allowed, and expired data will not be cleaned up immediately, which will lead to space enlargement.

Due to the different implementations of these two merging strategies, space amplification and write amplification will be caused respectively.

The merge process of Tiered Compaction will cause the SSTable file of the higher layer to be very large. When the merge operation is performed, in order to ensure fault tolerance, the original SSTable file will not be deleted before the end of the merge operation, which will cause the amount of data to become nearly two in the short term. After the merge operation is completed, the old data will be deleted, and the data volume will return to normal. Although only temporary, this is still a serious space magnification problem.

Leveled Compaction fixes the size of the SSTable, but its merging strategy is not to merge all SSTables in the entire layer with the next layer, but to select an SSTable with the same Key value as the next layer to merge, reducing the problem of space enlargement: However, since one SSTable may have duplicate Key values with the 10 SSTables in the next layer during the merging process, 10 SSTable files need to be rewritten at this time, which will lead to serious write amplification.

Section 12 - Impact of Metadata Changes on Storage Schema

In the diversified storage mode, the change of metadata may affect the choice of storage mode, and even convert the data stored on the copy to another storage mode. For the change of metadata, this solution provides two types of storage modes. The solution is discussed in detail below. When metadata changes, some storage modes are affected. For example, if a column is added to the table structure, the column storage mode only needs to add a corresponding column;

The row storage and multi-row storage modes are greatly affected, and the data in this column needs to be added to the row storage/multi-row storage data one by one; in the Cell storage mode, because the cell's key is (tableid, rowid, cloumnid) Combined, when adding a column, we only need to split according to the same rules, so cell row storage and cell column storage will not cause additional overhead.

For column family storage and column family segment storage, the storage mode can be changed in the following two ways.

1. Select the optimal storage mode: When the table structure changes, the data distribution under the current workload will change accordingly, which will affect the grouping range in the adaptive query. In this case, the current storage model may not be the optimal solution for the current workload. Therefore, we need to perform query adaptation again and choose the optimal storage mode.

2. Select the storage mode with the least change: In scheme 1, we re-selected the storage mode. Although we found the optimal storage mode, the overhead of this scheme is too high, and we need to re-transform all the data in the table. storage mode. In order to avoid such a large overhead, we can choose the storage mode with minimal changes. For example, when the storage mode of the copy is column family storage, and a column is added to the table structure, we can select column family storage for the newly added column, and complete the adaptation to metadata changes without affecting other data in the table.

For column segment storage, it may be necessary to aggregate the column into a column segment, which will cause some additional combination overhead.

When inserting this column exists in the whole table, it will generate some overhead necessary for inserting, and will not cause much impact on system performance.

The beneficial effects produced by the methods provided in the embodiments of the present application include:

1. The diversified storage mode proposed by this solution has clear layers and clear logic. It does not need to modify any query plan or consensus protocol processing process, and does not need to perceive changes in the underlying storage engine. It only needs to change a small amount of code to change the rules of KV mapping. Compatible with the changes of this scheme, the original system can obtain the support of diversified storage. At the same time, due to the expansion of the lower-layer storage mode, the upper-layer query optimization can obtain better parameter adjustment schemes, so developers can save more computing and storage costs.

2. Due to the expansion of the underlying storage mode, the query optimization can obtain a better configuration scheme, and the database can speed up the processing speed of user requests. Therefore, the user's satisfaction with the system will also increase.

3. In this solution, a multi-copy heterogeneous solution based on diversified storage is used, so that under mixed load, different types of requests can better utilize the advantages of disk reading and reduce network bandwidth on replicas with different storage modes. occupancy.

4. Adopting the separation architecture of computing and storage, it is convenient to change the distribution of storage nodes;

5. On the whole, this solution expands the storage mode, solves the problem that the query request cannot match the storage mode well, saves the storage space of the disk, improves the I/O efficiency of the system, and finally achieves the problem of improving the overall performance of the system. .

In addition, for the management method of diversified storage modes, Raft is used as the narrative object in this scheme, and Raft is a distributed protocol with strong leader. But for the distributed protocol of Leaderless Replication, it also works. For example, Dynamo is a distributed protocol for LeaderLess Replication. Compared with Raft, which must have a leader, the log must first go through the leader, then synchronize between followers, wait for more than half of the members to approve and then commit the workflow, Dynamo The central strategy is to ensure that the number of write replicas + the number of read replicas > the total number of replicas, so that each read operation can get the latest data. On this distributed protocol, we can also support diversified storage modes to improve the performance of the system.

For the heterogeneous multi-copy scheme of diversified storage, other distributed copy management protocols can also be used, such as Paxos, Multi-Paxos, and Quorum mechanism. It is only necessary to reasonably design KV mapping rules and use reasonable log translation technology between different replicas to realize heterogeneous multi-copy of diversified storage.

To sum up, this solution realizes the diversification of storage modes in the storage engine based on LSMTree, and basically includes all KV storage modes. Even if new storage modes appear in the future, it is only for the storage mode proposed in this application. Some changes will not go beyond the scope discussed in this program.

It should be understood that, although the steps in the flowcharts involved in the above embodiments are sequentially displayed according to the arrows, these steps are not necessarily executed in the order indicated by the arrows. Unless explicitly stated herein, the execution of these steps is not strictly limited to the order, and these steps may be performed in other orders. Moreover, at least a part of the steps in the flowcharts involved in the above embodiments may include multiple steps or multiple stages, and these steps or stages are not necessarily executed and completed at the same time, but may be performed at different times The execution order of these steps or phases is not necessarily sequential, but may be performed alternately or alternately with other steps or at least a part of the steps or phases in the other steps.

Based on the same inventive concept, an embodiment of the present application also provides a database storage mode adaptation apparatus for implementing the above-mentioned database storage mode adaptation method. The implementation solution for solving the problem provided by the device is similar to the implementation solution described in the above method, so the specific limitations in the embodiments of the adaptive device for one or more database storage modes provided below can refer to the above for database storage The limitation of the mode adaptive method is not repeated here.

In one embodiment, as shown in FIG. 15, an adaptive apparatus for database storage mode is provided, including: an acquisition module 1502 and a determination module 1504, wherein:

The obtaining module 1502 is configured to obtain the operation parameters of the workload and the read-write operation performance parameters of each key-value pair; the operation parameters include the read-write operation ratio, the query statement and the data distribution.

The determining module 1504 is configured to determine the first space size of the space occupied by the key-value pair according to the read-write operation ratio and the read-write operation performance parameter; determine the size of the storage area according to the semantic information of the query statement. Partitioning mode; determining the data density under the candidate grouping range according to the data distribution; determining the database when running the workload based on the partitioning mode, the candidate grouping range, the data density and the first space size The storage mode of the data table in .

In one embodiment, the apparatus further includes: the obtaining module is further configured to obtain the size of the space occupied by the key-value pair; the determining module is further configured to determine the size of the key-value pair when the space is occupied. a read-write operation performance parameter; a building module is configured to establish a performance model of the key-value pair based on the read-write operation performance parameter.

In one embodiment, the determining module is further configured to determine the overall performance parameter of the workload when the key-value pair occupies the space size according to the read-write operation ratio and the read-write operation performance parameter; based on The overall performance parameter determines the first space size of the space occupied by the key-value pair.

In one embodiment, the device further includes: a selection module, configured to select the overall time consumption that satisfies the time-consuming condition in each of the overall time-consuming as the target overall time-consuming when the overall performance parameter is the overall time-consuming; The size of the space occupied by the key-value pair corresponding to the total time-consuming of the target is taken as the first space size.

In one embodiment, the acquiring module is further configured to acquire the query statements and the total amount of query statements involved in the data table; the determining module is further configured to determine the difference between the number of each of the query statements and the total amount of the query statements Ratio; in the query statement involved, the target query statement is determined based on the ratio; the partition mode of the storage area is determined based on the column information in the target query statement.

In one embodiment, the determining module is further configured to determine a candidate grouping range; determine a data grouping based on the primary key value of the data table and the candidate grouping range; determine the second data in each data grouping according to the data distribution Density; taking the mean value of the second data density as the first data density under the candidate grouping range.

In one embodiment, the determining module is further configured to determine, based on the partition mode, the candidate grouping range, and the first data density in the candidate grouping range, the first data density occupied by the key-value pair in the candidate grouping range Two space sizes; when the difference between the second space size and the first space size satisfies the preset difference condition, determine the running The storage mode of the data table in the database when the workload is described.

In one embodiment, the apparatus further includes: a determining module is further configured to determine a target storage mode of the other workload in the database when the workload is replaced with another workload; a conversion module, configured to When in the idle state, the storage mode is converted to the target storage mode.

In one embodiment, the apparatus further includes: an encoding module, configured to re-encode the data in the data table according to the encoding mode corresponding to the target storage mode, to obtain encoded data; a storage module, used to store the encoded data.

In one embodiment, the apparatus further includes: a reading module, configured to read the data in the data table when the storage mode is a row storage mode and the target storage mode is a cell storage mode The storage module is also used to use the table identification of the data table, the row identification of the target row in the data table and the column identification of the target column in the data table as a key, and the target row and the target column The data in the intersecting cells is taken as the value, and the cell data composed of the key and the value is obtained; the cell data composed of the key and the value is stored.

In one embodiment, the apparatus further includes: a writing module, configured to write the data in the cell storage mode when the storage mode is the cell storage mode and the target storage mode is the column storage mode The cells are written into the buffer; the storage module is further configured to store the table identifier of the data table and the target in the data table when the number of cells in the buffer meets the number required by the column storage mode The column identifier of the column is used as the key, the data in the target column is used as the value, and the column data composed of the key and the value is obtained; the column data composed of the key and the value is stored.

In one embodiment, the apparatus further includes: an aggregation module, configured to aggregate at least two cells in the target column into a group when the storage mode is the column segment storage mode; the storage module is further configured to The table identifier of the data table, the column identifier of the target column and the grouping identifier of the at least two cells are used as keys, and the data in the at least two cells in the target column are stored as values.

In one embodiment, the aggregation module is further configured to aggregate at least two cells in each column located in the first direction in the data table into a column family when the storage mode is a column family segment storage mode; At least two cells in each row located in the second direction in the data table are aggregated into data groups; the storage module is further configured to use the table identifier of the data table, the family identifier of the column family, and the data grouping The group identifier of is a key, and the data in at least two cells in each column and the data in at least two cells in each row are stored as values.

In one embodiment, the storage module is further configured to use the table identifier of the data table as the key and the data in the data table as the value to store when the storage mode is the whole table storage mode.

In one embodiment, the apparatus further includes: a receiving module configured to receive different types of query requests; the determining module is further configured to determine the execution time, waiting time and transmission time of the query request; based on the execution time, The waiting time, the transmission time and the preset weight determine the second storage mode corresponding to the query request; the first storage mode and the second storage mode are different storage modes; the routing module, using and routing the query request to a replica node corresponding to the second storage mode, so that the replica node performs data query based on the query request.

In one embodiment, the obtaining module is further configured to obtain the search time, processing time and tuple construction time of the query request, and the determining module is further configured to obtain the search time, the read and write data volume processing time and the The tuple construction time determines the execution time of the query request; the obtaining module is further configured to obtain the request queue time, machine load delay time and slave node data synchronization time of the query request, and the determining module is further configured to obtain the request queue time based on the query request , the machine load delay time and the slave node data synchronization time determine the waiting time of the query request; determine the transmission time of the query request.

In one embodiment, the receiving module is further configured to receive a range query request;

Determining the total number of columns in the query table corresponding to the range query request, and determining the number of target columns required by the range query request; the target column is a data column in the query table; the determining module is further configured to based on The number of columns, the total number of columns, and a preset threshold determine a third storage mode corresponding to the range query request; the first storage mode and the third storage mode are different storage modes; the routing module further for routing the range query request to the replica node corresponding to the third storage mode, so that the replica node performs data query based on the range query request.

Each module in the above-mentioned adaptive device for database storage mode can be implemented in whole or in part by software, hardware and combinations thereof. The above modules can be embedded in or independent of the processor in the computer device in the form of hardware, or stored in the memory in the computer device in the form of software, so that the processor can call and execute the operations corresponding to the above modules.

In one embodiment, a computer device is provided, and the computer device may be a server, and its internal structure diagram may be as shown in FIG. 16 . The computer device includes a processor, a memory, an input/output interface (Input/Output, I/O for short) and a communication interface. Wherein, the processor, the memory and the input/output interface are connected through the system bus, and the communication interface is connected to the system bus through the input/output interface. Among them, the processor of the computer device is used to provide computing and control capabilities. The memory of the computer device includes non-volatile storage media and internal memory. The nonvolatile storage medium stores an operating system, a computer program, and a database. The internal memory provides an environment for the execution of the operating system and computer programs in the non-volatile storage medium. The database of the computer device is used to store adaptive data of the database storage mode. The input/output interface of the computer device is used to exchange information between the processor and external devices. The communication interface of the computer device is used to communicate with an external terminal through a network connection. The computer program, when executed by a processor, implements a method of adapting a database storage schema.

Those skilled in the art can understand that the structure shown in FIG. 16 is only a block diagram of a part of the structure related to the solution of the present application, and does not constitute a limitation on the computer equipment to which the solution of the present application is applied. Include more or fewer components than shown in the figures, or combine certain components, or have a different arrangement of components.

In one embodiment, a computer device is also provided, including a memory and a processor, where a computer program is stored in the memory, and the processor implements the steps in the foregoing method embodiments when the processor executes the computer program.

In one embodiment, a computer-readable storage medium is provided, which stores a computer program, and when the computer program is executed by a processor, implements the steps in the foregoing method embodiments.

In one embodiment, there is provided a computer program product or computer program comprising computer instructions stored in a computer readable storage medium. The processor of the computer device reads the computer instructions from the computer-readable storage medium, and the processor executes the computer instructions, so that the computer device executes the steps in the foregoing method embodiments.

It should be noted that the user information (including but not limited to user equipment information, user personal information, etc.) and data (including but not limited to data for analysis, stored data, displayed data, etc.) involved in this application are all It is the information and data authorized by the user or fully authorized by all parties, and the collection, use and processing of the relevant data need to comply with the relevant laws, regulations and standards of the relevant countries and regions.

Those of ordinary skill in the art can understand that all or part of the processes in the methods of the above embodiments can be implemented by instructing relevant hardware through a computer program, and the computer program can be stored in a non-volatile computer-readable storage In the medium, when the computer program is executed, it may include the processes of the above-mentioned method embodiments. Wherein, any reference to a memory, a database or other media used in the various embodiments provided in this application may include at least one of a non-volatile memory and a volatile memory. Non-volatile memory may include Read-Only Memory (ROM), magnetic tape, floppy disk, flash memory, optical memory, high-density embedded non-volatile memory, resistive memory (ReRAM), magnetic variable memory (Magnetoresistive Random Memory) Access Memory, MRAM), Ferroelectric Random Access Memory (FRAM), Phase Change Memory (Phase Change Memory, PCM), graphene memory, etc. Volatile memory may include random access memory (Random Access Memory, RAM) or external cache memory, and the like. By way of illustration and not limitation, the RAM may be in various forms, such as static random access memory (Static Random Access Memory, SRAM) or dynamic random access memory (Dynamic Random Access Memory, DRAM). The database involved in the various embodiments provided in this application may include at least one of a relational database and a non-relational database. The non-relational database may include a blockchain-based distributed database, etc., but is not limited thereto. The processors involved in the various embodiments provided in this application may be general-purpose processors, central processing units, graphics processors, digital signal processors, programmable logic devices, data processing logic devices based on quantum computing, etc., and are not limited to this.

The technical features of the above embodiments can be combined arbitrarily. In order to make the description simple, all possible combinations of the technical features in the above embodiments are not described. However, as long as there is no contradiction in the combination of these technical features It is considered to be the range described in this specification.

The above-mentioned embodiments only represent several embodiments of the present application, and the descriptions thereof are relatively specific and detailed, but should not be construed as a limitation on the scope of the patent of the present application. It should be pointed out that for those skilled in the art, without departing from the concept of the present application, several modifications and improvements can be made, which all belong to the protection scope of the present application. Therefore, the scope of protection of the present application should be determined by the appended claims.

Claims (20)

1. an adaptive method for database storage mode, characterized in that the method comprises: Obtain the operating parameters of the workload and the read-write operation performance parameters of each key-value pair; the operating parameters include read-write operation ratio, query statement and data distribution; Determine the first space size of the space occupied by the key-value pair according to the read-write operation ratio and the read-write operation performance parameter; Determine the partition mode of the storage area according to the semantic information of the query statement; determining the data density under the candidate grouping range according to the data distribution; Based on the partition mode, the candidate grouping range, the data density, and the first space size, a storage mode of a data table in the database is determined when the workload is running. 2. The method according to claim 1, characterized in that, before acquiring the operating parameters of the workload and the read-write operation performance parameters of each key-value pair, the method further comprises: Obtain the size of the space occupied by the key-value pair; In the case of occupying the size of the space, determine the read and write operation performance parameters of the key-value pair; Based on the read-write operation performance parameters, establish a performance model of the key-value pair; The obtaining of the operating parameters of the workload and the read-write operation performance parameters of each key-value pair includes: Acquire the running parameters of the workload, and acquire the read and write operation performance parameters of the key-value pair based on the performance model. 3. The method according to claim 2, wherein, determining the first space size of the space occupied by the key-value pair according to the read-write operation ratio and the read-write operation performance parameter, comprising: According to the read-write operation ratio and the read-write operation performance parameter, determine the overall performance parameter of the workload when the key-value pair occupies the space size; Based on the overall performance parameter, a first space size of the space occupied by the key-value pair is determined. 4. The method according to claim 3, wherein, determining the first space size of the space occupied by the key-value pair according to the read-write operation ratio and the read-write operation performance parameter, comprising: When the overall performance parameter is the overall time-consuming, select the overall time-consuming that satisfies the time-consuming condition in each of the overall time-consuming as the target overall time-consuming; The size of the space occupied by the key-value pair corresponding to the total time-consuming of the target is taken as the first space size. 5. The method according to claim 1, characterized in that, determining the partition mode of the storage area according to the semantic information of the query statement, comprising: Obtain the query statements and the total amount of query statements involved in the data table; determining the ratio between the number of each said query statement and the total amount of said query statement; Among the query statements involved, determining the target query statement based on the ratio; Based on the column information in the target query statement, the partition mode of the storage area is determined. 6. The method according to claim 1, wherein the data density comprises a first data density; and the determining the data density in the candidate grouping range according to the data distribution comprises: Determine the candidate grouping range; Determine a data group based on the primary key value of the data table and the candidate grouping range; determining a second data density within each of the data packets according to the data distribution; Taking the mean value of the second data density as the first data density under the candidate grouping range. 7 . The method according to claim 6 , wherein the database is determined when running the workload based on the partition mode, the candidate grouping range, the data density and the first space size. 8 . The storage mode of the data table in , including: Based on the partition mode, the candidate grouping range, and the first data density in the candidate grouping range, determine the second space size occupied by the key-value pairs in the candidate grouping range; When the difference between the second space size and the first space size satisfies a preset difference condition, determining when running the workload based on the partition mode and candidate grouping range corresponding to the second space size The storage mode of the data table in the database. 8. The method of claim 1, wherein the method further comprises: When the workload is replaced with another workload, determining the target storage mode of the other workload in the database; When in the idle state, the storage mode is converted to the target storage mode. 9 . The method according to claim 8 , wherein after converting the storage mode to the target storage mode, the method further comprises: 10 . According to the encoding mode corresponding to the target storage mode, re-encode the data in the data table to obtain encoded data; The encoded data is stored. 10. The method according to claim 9, wherein the method further comprises: When the storage mode is a row storage mode and the target storage mode is a cell storage mode, read the data in the data table; Using the table identifier of the data table, the row identifier of the target row in the data table, and the column identifier of the target column in the data table as keys, the cell that intersects the target row and the target column is The data is taken as the value, and the cell data composed of the key and the value is obtained; The cell data consisting of the key and the value is stored. 11. The method of claim 9, wherein the method further comprises: When the storage mode is the cell storage mode and the target storage mode is the column storage mode, writing the cells in the cell storage mode into the buffer; When the number of cells in the buffer meets the number required by the column storage mode, the table ID of the data table and the column ID of the target column in the data table are used as keys, and the target column is stored in the data table. The data is used as the value, and the column data composed of the key and the value is obtained; The column data composed of the key and the value is stored. 12. The method of claim 1, wherein the method further comprises: When the storage mode is the column segment storage mode, at least two cells in the target column are aggregated into one group; The table identifier of the data table, the column identifier of the target column, and the grouping identifier of the at least two cells are used as keys, and the data in the at least two cells in the target column is stored as values. 13. The method of claim 1, wherein the method further comprises: When the storage mode is a column family segment storage mode, at least two cells in each column located in the first direction in the data table are aggregated into a column family; aggregating at least two cells in each row located in the second direction in the data table into data groupings; Using the table identifier of the data table, the family identifier of the column family, and the group identifier of the data grouping as keys, using the data in at least two cells in each column and at least two in each row The data in the cell is stored as a value. 14. The method of claim 1, wherein the method further comprises: When the storage mode is the whole table storage mode, the table identifier of the data table is used as the key, and the data in the data table is used as the value for storage. 15. The method according to claim 1, wherein the storage mode is the first storage mode; after the determining the storage mode of the data table in the database when the workload is running, the method further comprises: Receive different types of query requests; determining the execution time, waiting time and transmission time of the query request; Based on the execution time, the waiting time, the transmission time and the preset weight, a second storage mode corresponding to the query request is determined; the first storage mode and the second storage mode are different storage modes model; The query request is routed to a replica node corresponding to the second storage mode, so that the replica node performs data query based on the query request. 16. The method according to claim 15, wherein the determining the execution time, waiting time and transmission time of the query request comprises: Obtain the search time, processing time and tuple construction time of the query request, and determine the execution time of the query request based on the search time, the processing time of the read and write data volume, and the tuple construction time; Obtain the request queue time, machine load delay time and slave node data synchronization time of the query request, and determine the waiting time of the query request based on the request queue time, the machine load delay time and the slave node data synchronization time time; Determine the transmission time of the query request. 17. The method according to claim 1, wherein the storage mode is the first storage mode; the method further comprises: Receive range query requests; determining the total number of columns in the query table corresponding to the range query request, and determining the number of target columns required by the range query request; the target column is a data column in the query table; determining a third storage mode corresponding to the range query request based on the number of columns, the total number of columns and a preset threshold; the first storage mode and the third storage mode are different storage modes; The range query request is routed to the replica node corresponding to the third storage mode, so that the replica node performs data query based on the range query request. 18. An adaptive device for database storage mode, characterized in that, the device comprises: an acquisition module, used to acquire the operating parameters of the workload and the read-write operation performance parameters of each key-value pair; the operating parameters include the read-write operation ratio, query statements and data distribution; A determination module, configured to determine the first space size of the space occupied by the key-value pair according to the read-write operation ratio and the read-write operation performance parameter; determine the partition of the storage area according to the semantic information of the query statement determining the data density under the candidate grouping range according to the data distribution; The storage mode of the data table. 19. A computer device comprising a memory and a processor, wherein the memory stores a computer program, wherein the processor implements the method according to any one of claims 1 to 17 when the processor executes the computer program. step. 20. A computer-readable storage medium on which a computer program is stored, characterized in that, when the computer program is executed by a processor, the steps of the method according to any one of claims 1 to 17 are implemented.

Images