CN118377463A - A software design method, device and equipment for mobile database - Google Patents

Abstract

The application discloses a software design method, a device and equipment of a mobile database, and relates to the field of databases supporting object agent models developed by small mobile terminals; execution of TOTEM-SQL commands is completed through a TOTEM query system; the redox operation is performed by comparing the operation record in the log file with the operation actually performed based on the WAL method to record the redox information to the log file. The application stores and organizes the data in a structuring way, so that the data can be efficiently read and written in by calculation, and the system crash can be timely recovered by the log management part, thereby ensuring the data security.

Description

A software design method, device and equipment for mobile database

Technical Field

The present application relates to the field of databases supporting object proxy models developed for small mobile terminals, and specifically to a software design method, device and equipment for a mobile database.

Background technique

Totem Mobile Database (TMDB) software is a small mobile database designed for lightweight database systems on mobile devices and embedded systems. Mobile databases are carried by handheld terminals, small portable devices, etc. for field operations and geographic information collection. Current mobile databases have the following problems: too much resource consumption, unable to guarantee efficient operation in a limited mobile environment; there are application limitations for some applications with high real-time requirements; and the need for remote calls leads to slow usage.

Summary of the invention

The present application provides a software design method, device and equipment for a mobile database, which saves and organizes data in a structured manner so that the calculation can efficiently read and write data, and through the log management part, ensures that the system crash can be recovered in time to ensure data security.

In a first aspect, an embodiment of the present application provides a software design method for a mobile database, the software design method for a mobile database comprising:

Based on the storage hierarchy design, the data table is converted into a key-value pair and stored in the LSM-Tree. The compaction mechanism is introduced into the LSM-Tree to perform periodic merging and optimization operations. B-Tree is used as the index and the Bloom Filter fast search algorithm is applied to achieve storage management.

The TOTEM-SQL command is executed through TOTEM's query system, and the query system receives the query service command and compiles it in the analyzer to form a query tree, which enters the executor after rewriting and optimization. The storage system completes the acquisition of disk data and returns the query results to realize the compiled query.

Based on the WAL method, redo information is recorded in the log file, and the redo operation is performed by comparing the operation record in the log file with the actual operation, so as to restore the mobile database when the mobile database crashes and realize log management.

In combination with the first aspect, in one implementation,

For storage management, in memory, data is stored as a list of tuples, and metadata is distributed in multiple tables, including class table, sub-table, object table, switch table and bidirectional pointer table;

The table is managed by a memory manager, which is used to provide data insertion functions and monitor the size of MemTable. When the size of MemTable exceeds a threshold, the MemTable is converted into an immutable MemTable, and a compaction process is started to convert the immutable MemTable into an SSTable and store it at the bottom layer.

The external storage data is organized through the LSM-Tree structure. The level manager is responsible for tracking the level and key information of each SSTable. The level manager is also used to perform compaction, including selecting appropriate levels and SSTables for merging, and implementing the merge operation of multiple SSTables.

In combination with the first aspect, in one implementation,

The LSM-Tree stores data in MemTable, which is divided into mutable MemTable and immutable MemTable. Data is first written into the mutable MemTable, and then converted into the immutable MemTable after it is filled. New data needs to wait for the free mutable MemTable to be written.

The immutable MemTable is merged into external memory through compaction operations and converted back to a mutable MemTable for writing again;

The data in the external memory is stored in the form of SSTable. The data is sorted and layered by key, from the bottom layer to the top layer. The higher the layer, the more SSTables there are and the larger the size of each SSTable.

Data starts to be compacted from the immutable MemTable in memory, first converted to the bottom-level SSTable, and then when a certain level of SSTable reaches the threshold, it is further compacted to a higher level until the highest level is reached.

In conjunction with the first aspect, in one implementation, the operation steps for specifying a key in the SSTable specifically include:

Read Footer to obtain component information, check the minimum and maximum keys of SSTable to determine whether the key is in the range. If so, verify whether the key exists in SSTable through Bloom Filter, then locate the data block containing the target key according to the information in the index block, and search for the key in the data block.

In combination with the first aspect, in one implementation, the compaction is used to clear data layer overlap and duplicate key accumulation generated after the memory data is flushed to disk, and the compaction is also used to clean up old version data by periodically merging multiple layers of data.

In combination with the first aspect, in one embodiment, for compiled queries, the analyzer is used to check the input query string and ensure the correctness of the query string through lexical, grammatical and semantic analysis. If the query string is valid, the analyzer creates a query tree and passes it to the planner. If it is invalid, an error prompt is returned.

In combination with the first aspect, in one implementation, for compiled queries, JSqlParser is extended by JavaCC to generate a Java lexical and syntax analyzer, wherein the JSqlParser is a lightweight Java library for parsing SQL into a tree structure and supporting a wide range of SQL commands.

In combination with the first aspect, in one implementation,

For log management, before data is written to Memtable, records are persisted to disk through WAL, and the function of managing the log system is implemented through the LogManager.java file;

When the mobile database crashes, data is restored to the last normal state through the persisted log file records, in which all object operations are recorded. When the mobile database is restarted, the mobile database applies the log file records starting from the most recent checkpoint to restore to a consistent state.

In a second aspect, an embodiment of the present application provides a software design device for a mobile database, the software design device for a mobile database comprising:

The storage management module is used to convert data tables into key-value pairs based on the storage hierarchy design and store them in LSM-Tree. The compaction mechanism is introduced into LSM-Tree to perform periodic merging and optimization operations. B-Tree is used as the index and Bloom Filter fast search algorithm is applied to achieve storage management.

Compile query module, which is used to complete the execution of TOTEM-SQL commands through TOTEM's query system. The query system receives query service commands and compiles them in the analyzer to form a query tree. After rewriting and optimization, it enters the executor, and the storage system completes the acquisition of disk data and returns the query results to realize compiled query;

The log management module is used to record redo information to the log file based on the WAL method, and to perform redo operations by comparing the operation records in the log file with the actual operations performed, so as to restore the mobile database when the mobile database crashes and realize log management.

In a third aspect, an embodiment of the present application provides a software design device for a mobile database, wherein the software design device for a mobile database comprises a processor, a memory, and a software design program for a mobile database stored in the memory and executable by the processor, wherein when the software design program for a mobile database is executed by the processor, the steps of the software design method for a mobile database described above are implemented.

The beneficial effects brought by the technical solution provided by the embodiments of the present application include:

(1) Small size: small mobile databases take up very little space, making them very suitable for mobile devices with limited storage space, such as mobile phones, tablets, and IoT devices. They can run in a storage space of a few hundred KB or even a few MB.

(2) Resource efficiency and lightweight design. Small mobile databases consume relatively little memory, CPU, and battery during operation, ensuring stable and efficient operation in resource-limited mobile environments. Embedded integration means that they can be directly embedded into applications without the need for a separate database server, simplifying deployment and management and making them suitable for standalone application scenarios. Easy to port. Due to their small size and low dependencies, small mobile databases are easily ported across platforms and can run on a variety of mobile operating systems.

(3) Local data storage: Even without a network connection, mobile devices can access and operate small databases stored locally, ensuring data availability and reducing dependence on the network;

(4) Fast response: Since data is directly stored locally, query and update operations are usually faster than remote calls to cloud databases, which is especially suitable for applications with high real-time requirements. High security: Direct processing and analysis on the mobile terminal can save network transmission overhead, thereby enabling quick decision-making to avoid economic losses or security risks caused by delays.

BRIEF DESCRIPTION OF THE DRAWINGS

FIG1 is a flow chart of a software design method for a mobile database of the present application;

Figure 2 is a LSM-Tree hierarchy diagram of the mobile database software;

FIG3 is a B-Tree example diagram of mobile database software record offset;

FIG4 is a timing diagram of inserting data when the mobile database software is storing TMDB;

FIG5 is a timing diagram of querying data when storing in TMDB;

FIG6 is a schematic diagram of the functional modules of the software design device for the mobile database of the present application;

FIG. 7 is a schematic diagram of the hardware structure of the software design device for the mobile database.

Detailed ways

In order to enable those skilled in the art to better understand the solution of the present application, the technical solution in the embodiments of the present application will be clearly and completely described below in conjunction with the drawings in the embodiments of the present application. Obviously, the described embodiments are only part of the embodiments of the present application, not all of the embodiments. Based on the embodiments in the present application, all other embodiments obtained by ordinary technicians in this field without creative work are within the scope of protection of this application.

In order to make the objectives, technical solutions and advantages of the present application more clear, the implementation methods of the present application will be further described in detail below with reference to the accompanying drawings.

On the first aspect, the embodiments of the present application provide a software design method for a mobile database, which saves and organizes data in a structured manner so that the calculation can efficiently read and write data, and through the log management part, ensures that the system crash can be recovered in time to ensure data security.

In one embodiment, referring to FIG1 , FIG1 is a flow chart of the software design method of the mobile database of the present application. As shown in FIG1 , the software design method of the mobile database includes:

S1: Based on the storage hierarchy design, the data table is converted into key-value pairs and stored in the LSM-Tree. The compaction (data merging) mechanism is introduced in the LSM-Tree, and periodic merging and optimization operations are performed. B-Tree (a self-balancing tree that can keep data in order) is used as the index, and the Bloom Filter fast search algorithm is applied to achieve storage management. Tree-LSTM is a deep learning model, which is an extension of LSTM (Long Short-Term Memory) and is designed to better process data with a tree-like hierarchical structure.

The design of mobile database includes storage management, compiled query and log management. For storage management, the design of storage software is a key component responsible for data storage and retrieval in computer systems. Through the design of storage hierarchy, data is effectively processed and managed. Data tables are stored in LSM-Tree by converting them into key-value pairs. In LSM-Tree, compaction mechanism is introduced, and regular merging and optimization operations are performed to ensure efficient storage and access of data. At the same time, B-Tree is used as index and Bloom Filter fast search algorithm is applied.

Further, for storage management, in memory, data is stored as a list of tuples, and metadata is distributed in multiple tables, including a class table, a sub-table, an object table, a switch table, and a bidirectional pointer table;

The table is managed by a memory manager (Mem Manager), which is used to provide data insertion functions and monitor the size of MemTable (memory table). When the size of MemTable exceeds a threshold, the MemTable is converted to an immutable MemTable, and a compaction process is started to convert the immutable MemTable into an SSTable (a data storage structure) and store it at the bottom layer (level-0);

The external storage data is organized through the LSM-Tree structure. The level manager is responsible for tracking the level and key information of each SSTable, such as the maximum/minimum key value and size. The level manager is also used to perform compaction, including selecting the appropriate level and SSTable for merging, and implementing the merge operation of multiple SSTables.

Furthermore, LSM-Tree stores data in MemTable, which is divided into mutable MemTable and immutable MemTable. Data is first written into mutable MemTable, and then converted into immutable MemTable after it is full. New data needs to wait for the free mutable MemTable to be written.

The immutable MemTable is merged into external memory through compaction operations and converted back to a mutable MemTable for writing again;

The data in the external memory is stored in the form of SSTable. The data is sorted and layered by key, from the lowest level (level-0) to the highest level (level-n). The higher the level, the more SSTables there are and the larger the size of each one.

Data starts to be compacted from the immutable MemTable in memory, first converted to the bottom-level SSTable, and then when a certain level of SSTable reaches the threshold, it is further compacted to a higher level until the highest level is reached.

SSTable is an efficient key-value file storage format. Further, the operation steps for specifying a key in SSTable include:

Read Footer (locate the starting index of the file) to obtain component information, check the minimum and maximum keys of SSTable to determine whether the key is in the range. If so, verify whether the key exists in SSTable through Bloom Filter, and then locate the data block containing the target key according to the information in the index block, and search for the key in the data block.

In computer systems based on the LSM-Tree architecture, compaction is a core mechanism that is used to clear data layer overlaps and duplicate key accumulations generated after memory data is flushed to disk. Compaction is also used to clean up old versions of data by periodically merging multiple layers of data. That is, compaction is used to solve the problems of data layer overlaps and duplicate key accumulations generated after memory data is flushed to disk, which can lead to reduced reading performance and waste of storage space. Compaction improves reading efficiency and saves space by periodically merging multiple layers of data and cleaning up old versions.

S2: The TOTEM-SQL (Structured Query Language) command is executed through the query system of TOTEM (Totem Patent System, a patent query system), and the query system receives the query service command and compiles it in the analyzer to form a query tree, which enters the executor after rewriting and optimization, and the storage system completes the acquisition of disk data and returns the query results to realize the compiled query;

Furthermore, for compiled queries, the analyzer is used to check the input query string and ensure the correctness of the query string through lexical, grammatical and semantic analysis. If the query string is valid, the analyzer creates a query tree and passes it to the planner. If it is invalid, an error prompt is returned.

For compiled queries, JSqlParser (a SQL parser) is extended through JavaCC (a generator that can generate syntax and lexical analyzers) to generate Java (an object-oriented programming language) lexical and syntax analyzers, simplifying creation and supporting advanced features and error reporting; the JSqlParser is a lightweight Java library used to parse SQL into a tree structure, and supports a wide range of SQL commands without dependencies, and is suitable for development of multiple database tools.

S3: Based on the WAL method, redo information is recorded in the log file, and redo operations are performed by comparing the operation records in the log file with the actual operations performed, so as to restore the mobile database when the mobile database crashes and realize log management.

That is, the WAL (write-ahead log) method is used to ensure data consistency and recovery capabilities by recording redo (rewrite) information in the log file. WAL allows the program to perform redo operations by comparing the operation records in the log with the actual operations performed, thereby quickly recovering the database when the system crashes. Because the system uses non-rewrite technology, the consistency of the database can be guaranteed even without undo (undo) operations.

Furthermore, for log management, before data is written to Memtable, the records are persisted to disk through WAL, and the functional functions of managing the log system are implemented through the LogManager.java file (java operation log management file), that is, a series of functional functions of the log management system are implemented, including initializing new log files, initializing new index B-tree files, deleting old log files, persisting logs to disk, and loading and displaying log records;

When the mobile database crashes, the data is restored to the last normal state through the persisted log file records. The log file records all object operations, ensuring that even if non-persistent changes (dirty pages) are lost, they can be safely restored through the log. When the mobile database is restarted, the mobile database applies the log file records from the most recent checkpoint to restore to a consistent state.

It should be noted that TMDB (Totem Mobile Database) is a database designed for mobile terminals that supports the object proxy model. The architecture of TMDB includes key modules such as storage management, compiled query, and log management. In addition, the Transaction module is responsible for processing user read and write requests, dispatching these requests to the corresponding modules for execution, and coordinating the work between modules and processing business logic.

Storage management is a key component responsible for data storage and retrieval in a mobile database (TMDB). It saves and organizes data in a structured way so that computers can read and write data efficiently.

In storage management, the storage hierarchy includes CPU, main memory, cache, and auxiliary memory. The storage hierarchy is designed to balance access speed, cost, and capacity through hierarchical memory. Fast but expensive memory (such as cache) is used to store the most frequently used data, while slower but larger and less expensive memory (such as auxiliary memory) is used for long-term storage and expansion. This hierarchical structure enables computer systems to process and manage data more efficiently, improving performance and response speed.

The log-first (WAL) strategy is adopted to ensure that all operations are recorded in the log, which is convenient for data recovery and exception handling. In LSM-Tree, data is initially written to the memory, and then gradually merged from the smaller disk file C1 to the larger file CL through a series of merge (compaction) operations. Unlike the in-place update of traditional databases, LSM-Tree implements out-place update, that is, all changes are first written to the memory and then refreshed to the disk in sequence, so as to optimize data storage and access efficiency.

SSTable is an efficient key-value storage format used in TMDB. The Footer of SSTable records the location information of internal components for fast access. Data is sorted by key, stored in 4KB data blocks, and indexed by index block for fast location, including the minimum key and offset. To speed up the search, SSTable also saves the minimum key and Bloom Filter. The steps to query a specified key are as follows:

This accesses Footer to obtain component information;

Check the minimum and maximum keys to determine the query range;

Use Bloom Filter to quickly determine whether a key exists;

Locate possible data blocks through index blocks;

Traverse the data block to find the target key.

The compaction mechanism is introduced in the system with LSM-Tree architecture. When the data in the memory reaches the upper limit, it is constantly flushed to the disk. The number of layers with overlapping data ranges increases, and the data with the same key continues to accumulate, causing the read performance to degrade and the space to expand. Therefore, the compaction mechanism is introduced to optimize the read performance and space usage issues by periodically reclaiming old version data and merging multiple layers into one layer through periodic background tasks.

In TMDB, the steps for selecting levels and SSTables in the compaction process are as follows:

Calculate the score of each level and select the level-i with the highest score for compaction;

If i=0, all SSTables in level-0 are compacted into new SSTables and moved to level-1, and the old SSTables are deleted; otherwise, the files set is initialized, and the SSTablex with the smallest file name suffix in level-i is selected and added to the files;

Find all SSTables in level-i that overlap with x (e.g. y and z) and add them to files;

Determine the SSTables (such as a and b) in level-(i+1) that overlap with files and add them to files_2;

Traverse the SSTables of level-i, find SSTable t that can be added to files and will not cause a new SSTable to be added to files_2, and add it to files.

Finally, all SSTables in files and files_2 constitute the merged set of this compaction.

In the mobile database (TMDB), B-Tree is used as the index.

B-Tree is a self-balancing tree that keeps data in order. This data structure allows data search, sequential access, data insertion and deletion to be completed in logarithmic time, which optimizes the system's large-scale data read and write operations. B-Tree speeds up access by reducing the intermediate process of locating records.

In the mobile database (TMDB), the Bloom Filter algorithm is used. Bloom Filter is a probabilistic data structure with high space efficiency, which is used to quickly determine whether an element belongs to a set. It can quickly determine whether the data exists, thereby avoiding expensive disk I/O operations or reducing unnecessary calculations. The basic principle of Bloom Filter is to use a bit array and multiple hash functions. Each bit of the bit array is initialized to 0, and the hash function is used to map the element to a specific position in the bit array. When an element is added to the set, k hash values are calculated by the hash function, and the corresponding k bits in the bit array are set to 1. When querying an element, the hash function is also used to calculate k bits. If all bits are 1, it is considered that the element may exist in the set; if any bit is 0, the element is definitely not in the set.

In the mobile database (TMDB), two cache modes combined with LSM-Tree are designed:

MetaCache: caches the metadata blocks of SSTable, including key range and offset information. This design allows quick location of the required SSTable, reduces disk IO, and improves query efficiency and hit rate.

DataCache: A key-value cache based on the FIFO strategy. It uses OrderedMap to record data and maintain the insertion order and mapping relationship. Newly inserted data items are placed at the top to ensure that recently accessed data is retained first, while accessed data items are kept at the top of the cache by reinserting. These cache strategies significantly improve the query performance of TMDB, achieving a 100-fold performance gain.

It should be noted that compiled queries convert query statements in the mobile database (TMDB) into instruction sequences that can be efficiently executed by the database kernel, while ensuring the security and effectiveness of the query statements and improving query performance through optimization.

In compiling a query, the lexical and grammatical analysis process first converts the query string into an internal grammatical structure, and performs a grammatical check to ensure that it complies with the TOTEM-SQL specification, and finally generates a parse tree that reflects the query content. The lexical analyzer will recognize the information and convert it into corresponding labels and pass it to the grammatical analyzer. After receiving the query symbol string, the grammatical analyzer will recognize it as a SELECT query command and perform corresponding actions to generate a parse tree structure.

The second is the semantic analysis part, or the conversion stage, which accepts the analysis tree from the syntax analyzer and checks whether the command conforms to the system regulations. If not, it is finally converted into a query tree and returned.

The semantic analysis (converter) takes the parse tree passed by the analyzer as input and processes it recursively. Generally speaking, various commands will eventually be converted into a query node, which will be the top node of the new data structure. After forming the query node, the converter will check whether the class name in the FROM clause exists. After all the class names are recognized, the converter checks whether the attribute names used in the query are contained in the class given by the query.

All query commands will go through the above process. Some complex query commands (commands that need to generate plans) will call the converter part, mainly including SELECT, INSERT, DELETE and UPDATE commands. Their query trees will be converted into query plans by the planner, and then the executor will perform scanning work according to the plan.

Many other simpler non-planned commands (such as commands to create or delete basic classes) do not require class scanning, but only require some operations on the system's schema data. Therefore, the converter only performs a simple logical error check without any actual conversion. Their processing can be completed by directly calling the corresponding module.

The class creation operation includes creating a strict proxy class and a non-strict proxy class. The command to create a strict proxy class is quite special. The command first requires the creation of the proxy class schema information, which is equivalent to a non-plan command; after that, the source class must be queried to create a proxy object according to the declared proxy rules, and the connection between the object and the proxy object must be established. This part also calls the planner and executor similar to the plan command. In order to unify the program interface, all commands in the semantic analyzer are finally output in the form of a unified query tree.

Based on the above, various query logic designs were created, including source class logic design, object deletion logic design class, search logic design, insertion logic design, deletion class logic design, proxy class logic design, attribute modification logic design, and cross-class search logic design.

In the specific implementation, the compilation part extends the JSqlParser[5] implementation based on javacc. Java CompilerCompiler (JavaCC) is a tool for generating lexical analyzers and syntax analyzers. It uses a grammar similar to BNF, inputs the language definition, and generates Java code for performing lexical analysis and syntax analysis. JavaCC makes it easy to generate language analyzers and supports various language features such as automatic generation of state machines, syntax-directed translation, lexical priority and syntax priority. In addition, JavaCC also provides advanced features such as lexical rule highlighting and syntax error reporting. Since it generates Java code, the language analyzer generated by JavaCC is cross-platform, efficient and maintainable.

JSqlParser is a Java library that can parse SQL statements and convert them into a representation that is easy for the program to handle. It can parse SQL statements from strings or files and supports a variety of SQL commands and clauses, including SELECT, INSERT, UPDATE, DELETE, and CREATE statements. The parsed SQL statements are represented using a tree structure that can be easily traversed and modified by the program. JSqlParser is designed to be lightweight and easy to use, without any external dependencies. It can be used to build a variety of applications, including SQL query builders, database migration tools, and SQL query analysis and optimization tools, so that we implement various processes through specific code.

It should be noted that the WAL (Write-Ahead Logging) mechanism of log management in the mobile database (TMDB) is to ensure that a consistent state can be restored in the event of a crash. The crash recovery process uses the WAL log to re-execute (redo) transactions that were not completed before the crash.

First, the log must complete the initialization of the new log file and the new index b-tree file, delete the old files in the log directory, persist the log to the disk given the parameters key, op, and value, and load and display all log records in the current log file. These functions are all implemented in the file LogManager.java.

Then start writing logs. Before data is written to Memtable, records need to be written to logs and persisted to disk according to WAL.

Create a LogTableItem object using the LogTableItem(int logid, Byte op, String key, String value) constructor, where logid is set to the current currentId and the other parameters come from the input of the WriteLog method. Set the offset of the LogTableItem to currentOffset and increment the currentId.

Call the writeLogItemToSSTable(LogTableItem log) method to write the log records to the file.

According to the value attribute of LogTableItem, check whether the corresponding log record already exists. If it does, add the logid of the new record to the corresponding list; if it does not exist, create a new list and add the logid.

Insert the node containing the offset of the LogTableItem into the B-tree using the insert() method of the BTree_indexer class.

When the log file reaches the preset size threshold, the write() method of the BTree_indexer class is called to persist the B-tree index to disk to prevent data loss.

One of the most important mechanisms of log management is the crash recovery mechanism. Checkpoints are used in WAL log recovery to reduce unnecessary log reading and allow the deletion of obsolete logs. All changes before the checkpoint have been written to disk, so when the system is restored, it is only necessary to start the recovery operation from after the checkpoint, and the previous logs can be safely deleted. The log records which object in the database has done what operation. When the system crashes, although the dirty page data is not persisted, the log record has been persisted. Then, after the database is restarted, redo can be performed based on the content in the log to restore all data to the latest state. Combined with the previous description of checkpoints, it can be known that it is necessary to start reading from the log block after the checkpoint (i.e. checkpoint+1) and recover the database based on the read content.

As shown in Figure 2, the mobile database (TMDB) software LSM-Tree adopts an out-place update method. The specific process is as follows: In memory, LSM-Tree data is stored in MemTable, which is divided into immutable MemTable and mutable MemTable. The former cannot be modified, while the latter can be modified. When data is written, it is written to the mutable MemTable. When the mutable MemTable is full, it is converted to the immutable MemTable. To write data again, you need to wait for an idle mutable MemTable. Each immutable MemTable will wait for the right time to perform a compaction operation and merge it into the external memory, and then it will be converted to a mutable MemTable and become writable again.

In external memory, LSM-Tree data is stored in SSTable (Sorted-String Table), and the data in each SSTable is sorted by key. These SSTables are stored in layers, from level-0 to level-n, and the number and size of corresponding SSTables are increasing. When compacting from the immutable MemTable in memory, it is first converted to the SSTable in level-0. When the size of level-i reaches the upper limit, it will be compacted to level-(i+1), and finally reach level-n after a series of compactions.

As shown in Figure 3, this is an example of a B-Tree for recording offsets in the mobile database (TMDB) software: When persisting the B-Tree to the index block in the SSTable, it is necessary to solve the problem of how to save the child nodes. The B-Tree in memory can easily record its child nodes through pointers, but when persisting to disk, the pointer records the address in memory, and what is needed is the physical address of the child node on the disk. Therefore, the B-Tree is traversed from the root first, that is, its child nodes are saved first, and the physical offset of each child node in the SSTable is obtained before saving the parent node. The B-Tree structure shown in Figure 3 first saves the A, B, C, D, and E nodes, and obtains the offsets of these nodes, then records the F node, and replaces the pointer in the third row with the actual physical offset.

As shown in Figure 4, it is a timing diagram of inserting data when the mobile database (TMDB) software is stored: first, the Transaction accepts the request, and then writes the log. After the log is written, the add() interface provided by the Mem Manager is called to add data to the MemTable. After the data is added, it is necessary to determine whether the MemTable has reached the upper limit. If it has reached the upper limit, it is necessary to call the writeInternal() interface provided by the Mem Manager to perform compaction to convert the MemTable into an SSTable, and notify the Level Manager to add the new SSTable to level-0. After that, it is necessary to verify whether the cascade compaction is triggered. The Level Manager needs to call the compact() interface to calculate the score of each level and check whether the conditions for compaction are met. If so, calculate the level and SSTable that need to be compacted, and then call the writeToDisk() interface provided by the Level Manager to perform compaction and record the log at the same time.

As shown in Figure 5, this is a timing diagram of querying data when the mobile database (TMDB) software is stored; compared to the recursive compaction that may be induced by inserting data, the query process is much simpler. First, the Transaction accepts the request and traverses the MemTable managed by the MemManager to search for the target key. If it is not found, it is handed over to the Cache Manager to search in the cache and update the cache priority. If it is not found, it is handed over to the Level Manager to traverse all SSTables of each layer from level-0 to level-6 on the disk to search for the target key. The specific process of searching a single SSTable has been introduced in Section 2.4. The search results on the disk need to be returned to the Cache Manager to update the cache and eliminate data that has not been used for a long time in the cache.

As shown in Tables 1 and 2 below, the data structures used in TOTEM when the mobile database (TMDB) software processes a query are shown. A simple example is used to demonstrate the changes made to the data structure at each stage. The query is initially entered by the user as a string as shown above. The lexical analyzer will recognize the information shown in Table 1 and convert it into corresponding labels and pass it to the syntax analyzer. After receiving the query symbol string in the example, the syntax analyzer will recognize it as a SELECT query command and perform corresponding actions to generate the analysis tree structure in Table 2.

Table 1

Table 2

For the checkpoint principle of the mobile database (TMDB) software, the main function of the checkpoint is to avoid reading all log records when recovering based on the WAL log, while allowing some unnecessary log content to be deleted. All data changes recorded in all logs before the checkpoint position have been flushed from the cache to the disk and reflected in the disk file. Therefore, when recovering from a downtime, you only need to read the log after the checkpoint mark and recover. The logs before the checkpoint mark are meaningless and can be deleted.

The software design method of the mobile database of the embodiment of the present application is a database supporting the object proxy model developed for the mobile terminal, including storage management, compilation query, and log management. The storage management TMDB is a key-value database that supports the object proxy model and is responsible for the key component of data storage and retrieval in the system. It saves and organizes data in a structured way so that the computer can read and write data efficiently. The compilation query part is that the database checks the lexical, grammatical and semantics of the input query string through the query analyzer, and for the unification of the program interface, all commands in the semantic analyzer are finally output in the form of a unified query tree to complete data retrieval, calculation and return results. The log management part adopts the WAL (Write Ahead Log) pre-write log method. After the log records describing these changes are flushed to the memory, the atomicity and persistence of data operations are guaranteed, and the log is replayed from the latest checkpoint to achieve data recovery. The present application has the characteristics of lightweight, low resource occupation, and suitable for mobile device storage and data processing. It is a database solution designed specifically for small mobile terminal applications.

In a second aspect, an embodiment of the present application also provides a software design device for a mobile database.

In one embodiment, referring to Fig. 6, Fig. 6 is a functional module diagram of the software design device for mobile database of the present application. As shown in Fig. 6, the software design device for mobile database includes a storage management module, a compilation query module and a log management module.

The storage management module is used to convert the data table into key-value pairs based on the storage hierarchy design and store it in the LSM-Tree. The compaction mechanism is introduced in the LSM-Tree, and the operations are periodically merged and optimized. B-Tree is used as the index and the Bloom Filter fast search algorithm is applied to realize storage management. The compilation query module is used to complete the execution of TOTEM-SQL commands through TOTEM's query system. The query system receives the query service command and compiles it into a query tree in the analyzer. After rewriting and optimization, it enters the executor, and the storage system completes the acquisition of disk data and returns the query results to realize the compilation query. The log management module is used to record redo information to the log file based on the WAL method, and executes the redo operation by comparing the operation record in the log file with the actual operation, so as to restore the mobile database when the mobile database crashes and realize log management.

Among them, the functional implementation of each module in the above-mentioned mobile database software design device corresponds to the various steps in the above-mentioned mobile database software design method embodiment, and its functions and implementation processes are no longer repeated here.

In a third aspect, an embodiment of the present application provides a software design device for a mobile database. The software design device for a mobile database may be a personal computer (PC), a laptop computer, a server, or other device with data processing capabilities.

Referring to Fig. 7, Fig. 7 is a schematic diagram of the hardware structure of the mobile database software design device involved in the embodiment of the present application. In the embodiment of the present application, the mobile database software design device may include a processor, a memory, a communication interface and a communication bus.

The communication bus may be of any type and is used to interconnect the processor, the memory, and the communication interface.

The communication interface includes input/output (I/O) interface, physical interface and logical interface, etc., which are used to realize the interconnection of devices inside the mobile database software design device, and the interface used to realize the interconnection between the mobile database software design device and other devices (such as other computing devices or user devices). The physical interface can be an Ethernet interface, a fiber optic interface, an ATM interface, etc.; the user device can be a display, a keyboard, etc.

The memory can be various types of storage media, such as random access memory (RAM), read-only memory (ROM), non-volatile RAM (NVRAM), flash memory, optical storage, hard disk, programmable ROM (PROM), erasable PROM (EPROM), electrically erasable PROM (EEPROM), etc.

The processor may be a general-purpose processor, and the general-purpose processor may call the software design program of the mobile database stored in the memory and execute the software design method of the mobile database provided in the embodiment of the present application. For example, the general-purpose processor may be a central processing unit (CPU). The method executed when the software design program of the mobile database is called may refer to the various embodiments of the software design method of the mobile database of the present application, and will not be repeated here.

Those skilled in the art will appreciate that the hardware structure shown in FIG. 7 does not constitute a limitation on the present application, and may include more or fewer components than shown in the figure, or a combination of certain components, or a different arrangement of components.

The terms "including" and "having" and any variations thereof in the specification and claims of this application and the above-mentioned drawings are intended to cover non-exclusive inclusions. For example, a process, method, system, product or device that includes a series of steps or units is not limited to the listed steps or units, but optionally includes steps or units that are not listed, or optionally includes other steps or units inherent to these processes, methods, products or devices. The terms "first", "second" and "third" are used to distinguish different objects, etc., and do not represent a sequence, nor do they limit the "first", "second" and "third" to different types.

In the description of the embodiments of the present application, "exemplary", "for example" or "for example" are used to indicate examples, illustrations or descriptions. Any embodiment or design described as "exemplary", "for example" or "for example" in the embodiments of the present application should not be interpreted as being more preferred or more advantageous than other embodiments or designs. Specifically, the use of words such as "exemplary", "for example" or "for example" is intended to present related concepts in a specific way.

In the description of the embodiments of the present application, unless otherwise specified, “/” means or. For example, A/B can mean A or B. The “and/or” in the text is merely a description of the association relationship of associated objects, indicating that three relationships may exist. For example, A and/or B can mean: A exists alone, A and B exist at the same time, and B exists alone. In addition, in the description of the embodiments of the present application, “multiple” refers to two or more than two.

In some processes described in the embodiments of the present application, multiple operations or steps that appear in a specific order are included, but it should be understood that these operations or steps may not be executed in the order in which they appear in the embodiments of the present application or in parallel, and the sequence number of the operation is only used to distinguish the different operations, and the sequence number itself does not represent any execution order. In addition, these processes may include more or fewer operations, and these operations or steps may be executed in sequence or in parallel, and these operations or steps may be combined.

Through the description of the above implementation methods, those skilled in the art can clearly understand that the above-mentioned embodiment methods can be implemented by means of software plus a necessary general hardware platform, and of course by hardware, but in many cases the former is a better implementation method. Based on such an understanding, the technical solution of the present application, or the part that contributes to the prior art, can be embodied in the form of a software product, which is stored in a storage medium (such as ROM/RAM, magnetic disk, optical disk) as described above, and includes a number of instructions for a terminal device to execute the methods described in each embodiment of the present application.

The above are only preferred embodiments of the present application, and are not intended to limit the patent scope of the present application. Any equivalent structure or equivalent process transformation made using the contents of the present application specification and drawings, or directly or indirectly applied in other related technical fields, are also included in the patent protection scope of the present application.

Claims (10)

1. A software design method for a mobile database, the software design method for the mobile database comprising:

Based on the storage hierarchy design, storing the data table in an LSM-Tree in a form of converting the data table into key value pairs, introducing a comparison mechanism into the LSM-Tree, periodically merging and optimizing the operation, adopting B-Tree as an index, and applying a Bloom Filter quick search algorithm to realize storage management;

The execution of TOTEM-SQL command is completed through TOTEM's query system, the query system receives the query service command and compiles the query tree in the analyzer, and the query tree is rewritten and optimized, then enters the executor, the storage system completes the acquisition of disk data, returns the query result, and realizes the compiling query;

and (3) based on the WAL method, the redox information is recorded into the log file, and the redox operation is executed by comparing the operation record in the log file with the operation actually executed so as to recover the mobile database when the mobile database crashes, thereby realizing log management.

2. A method of software design for a mobile database as in claim 1, wherein:

For storage management, in a memory, data is stored as a tuple list, and metadata is distributed in a plurality of tables, wherein the tables comprise a class table, a secondary table, an object table, a switching table and a bidirectional pointer table;

The table is managed by a memory manager, which is used for providing a data insertion function and monitoring MemTable the size, and when MemTable exceeds a threshold value, converting MemTable into invariable MemTable, starting a compatibility process, converting invariable MemTable into SSTable and storing in the bottom layer;

The external data is organized through an LSM-Tree structure, the hierarchical manager is responsible for tracking the hierarchy and key information of each SSTable, and the hierarchical manager is also used for executing the comparison, including selecting the proper hierarchy and SSTable for merging, and executing the merging operation of a plurality of SSTable.

3. A method of software design of a mobile database as claimed in claim 2, wherein:

The LSM-Tree stores data in MemTable, the data is divided into variable mutable MemTable and invariable immutable MemTable, the data is firstly written into variable MemTable, the data is changed into invariable MemTable after being filled, and new data is written into variable MemTable needing to wait for idle;

immutable MemTable is consolidated to external memory by a compare operation and converted back to mutable MemTable for re-writing;

The data in the external memory are stored in the form of SSTable, the data are ordered and layered according to keys, the higher the hierarchy is, the more SSTable number is, and the larger the single size is;

the data starts to be compatible from the immutable MemTable of the memory, is firstly converted into the SSTable at the bottom layer, and then when the SSTable at a certain layer reaches the threshold value, the data is further compatible to a higher level until the highest level is reached.

4. The method for designing software of mobile database according to claim 2, wherein the operation step of designating key in SSTable comprises:

And reading Footes to acquire component information, checking the minimum and maximum keys of the SSTable to determine whether the keys are in range, if so, verifying whether the keys exist in the SSTable through a Bloom Filter, positioning to a data block containing a target key according to information in an index block, and searching for the keys in the data block.

5. A method of software design for a mobile database as in claim 1, wherein: the compare is used to clear the overlap of data layers and repeated key accumulation generated after the memory data is flushed, and the compare is also used to clear old version data by periodically merging multiple layers of data.

6. A method of software design for a mobile database as in claim 1, wherein: for compiling query, the analyzer is used for checking the input query character string, ensuring the correctness of the query character string through lexical, grammatical and semantic analysis, creating a query tree by the analyzer if the query character string is valid, transmitting the query tree to the planner, and returning an error prompt if the query character string is invalid.

7. A method of software design for a mobile database as in claim 1, wherein: for compiled queries, JSqlParser is extended by JavaCC to generate Java lexical and grammatical parsers, JSqlParser is a lightweight Java library for parsing SQL into a tree structure and supporting extensive SQL commands.

8. A method of software design for a mobile database as in claim 1, wherein:

for log management, before data is written Memtable, the records are persisted to a disk through WAL, and the function of a log system is managed through a LogManager.java file;

And when the mobile database crashes, restoring the data to the final normal state through the durable log file record, recording all object operations in the log file, and when the mobile database is restarted, starting to apply the log file record after the latest check point, and restoring to the consistent state.

9. A software design device for a mobile database, the software design device for a mobile database comprising:

The storage management module is used for storing the data table in an LSM-Tree in a key value pair mode based on storage hierarchical structure design, introducing a compatibility mechanism into the LSM-Tree, periodically combining and optimizing operations, adopting B-Tree as an index, and applying a Bloom Filter quick search algorithm to realize storage management;

The compiling and inquiring module is used for completing the execution of TOTEM-SQL commands through an inquiring system of TOTEM, receiving an inquiring service command by the inquiring system, compiling and forming an inquiring tree in the analyzer, entering an executor after rewriting and optimizing, completing the acquisition of disk data by the storage system, returning an inquiring result and realizing compiling and inquiring;

And the log management module is used for recording the redox information to the log file based on the WAL method, and executing the redox operation by comparing the operation record in the log file with the operation actually executed so as to recover the mobile database when the mobile database crashes, thereby realizing log management.

10. A software design device of a mobile database, characterized in that the software design device of a mobile database comprises a processor, a memory, and a software design program of a mobile database stored on the memory and executable by the processor, wherein the software design program of a mobile database, when executed by the processor, implements the steps of the software design method of a mobile database according to any one of claims 1 to 8.