CN114816322B - SSD external ordering method, SSD external ordering device and SSD memory - Google Patents

Abstract

The application relates to an external ordering method, an external ordering device, computer equipment and a storage medium of SSD. The method comprises the following steps: the method comprises the steps of obtaining small files read into a memory, sequencing the small files to obtain an ordered intermediate result, and writing the ordered intermediate result back into a flash memory, wherein the small files are obtained by cutting large file data; constructing an index table in the memory of the SSD according to the minimum value of each data page in the ordered intermediate result and the position information of the data page on the flash memory; the index table comprises index information corresponding to the position information; and when data merging is carried out, sorting the index table according to the minimum value of the data page, carrying out data merging according to the sorting result of the index table and the index information to obtain an ordered result, and writing the ordered result back to the flash memory. By adopting the method, the read-write multi-channel concurrency of the SSD can be improved, and the channel resource utilization rate of the SSD is improved.

Description

SSD external sorting method, device and SSD storage device

Technical Field

The present application relates to the field of novel non-volatile storage technology, and in particular to an SSD external sorting method, device and SSD memory.

Background Art

With the development of new non-volatile storage technology, flash memory has been widely used in large servers, personal mobile devices, embedded sensor devices and high-performance computing systems. Flash memory is a block-addressed persistent external memory. The minimum granularity of reading and writing is the flash memory block. The read and write granularity of new non-volatile memory is smaller. From the perspective of flash memory type, flash memory can be divided into NAND Flash and NOR Flash. Flash-based solid state drive (SSD) is a new semiconductor storage device based on flash memory chips. Active SSDs are intelligent SSDs that can perform some computing functions. ActiveSort is an external sorting algorithm based on Active SSDs. ActiveSort is divided into two stages, the stage of generating ordered intermediate results and the stage of merging. The main idea of ActiveSort is to build a merge module inside Active SSDs, which can effectively reduce data transmission and reduce the read and write operations on SSD. When the host initiates a query request, ActiveSort will perform a merge-on-the-fly operation inside the Active SSD, merge the ordered intermediate results, and return the final ordered results to the host.

However, ActiveSort has two main problems. First, ActiveSort does not save the final ordered results on the SSD side. Every time the host side initiates a query request, the SSD side needs to perform a merge operation, which increases the computing overhead. Second, ActiveSort cannot predict the order of reading data blocks during the merge stage. It can only wait until the data blocks in the input cache are processed before reading the next data block from the intermediate result file where the data block is located. It cannot give full play to the internal read and write multi-channel concurrency of the SSD, especially in the scenario where the data is partially ordered. This will cause data blocks with larger values to remain in the SSD's DRAM, occupying cache resources and failing to improve the execution efficiency of the merge algorithm.

Summary of the invention

Based on this, it is necessary to provide an SSD external sorting method, device and SSD memory to address the above technical problems.

An external sorting method for SSDs, the method comprising:

Obtain small files read into the memory, sort the small files to obtain ordered intermediate results, and write the ordered intermediate results back to the flash memory, wherein the small files are obtained by segmenting the large file data;

According to the minimum value of each data page in the ordered intermediate results and the position information of the ordered intermediate results written back to the flash memory, an index table is constructed in the memory of the SSD; the index table contains index information corresponding to the position information;

When data merging is performed, the index table is sorted according to the minimum value of the data page, and data merging is performed according to the sorting result of the index table and the index information to obtain an ordered result, which is written back to the flash memory.

In one of the embodiments, it also includes: reading data pages in sequence into the input cache of the SSD according to the sorting result of the index table and the index information; merging the data pages to obtain an ordered result, recording the minimum value of the next data page to be merged, and when the data size in the input cache does not exceed the minimum value, writing the ordered results back to the flash memory in batches.

In one of the embodiments, it also includes: when the data size in the input cache is greater than the minimum value, writing the data page containing the minimum data in the ordered result back to the flash memory, reading the next data page to be merged into the input cache, and iteratively merging the data pages in the input cache.

In one of the embodiments, it also includes: setting a read flash channel and a write flash channel between the flash memory and the input cache.

In one of the embodiments, the further includes: the read flash channel processes a read request for data merging, and reads data from the read flash channel to an input cache.

In one of the embodiments, it also includes: the write flash channel processes a write-back request for data merging, writes the ordered result back to the write flash channel, and writes the ordered result back to the flash memory through the write flash channel.

In one of the embodiments, the method further includes: allocating the ordered intermediate results to each flash memory channel between the memory and the flash memory in an interleaved manner with data pages as basic units, and writing the ordered intermediate results back to the flash memory through the flash memory channel.

In one of the embodiments, the number of data pages of the ordered intermediate result is equal to the number of data pages that can be accommodated by the SSD input cache.

An external sorting device for an SSD, the device comprising:

An ordered intermediate result generation module obtains small files read into the memory, sorts the small files, obtains ordered intermediate results, and writes the ordered intermediate results back to the flash memory. The small files are obtained by segmenting the large file data.

An index table construction module, used to construct an index table in the memory of the SSD according to the minimum value of each data page in the ordered intermediate result and the location information of the data page on the flash memory; the index table contains index information corresponding to the location information;

The data merging module is used to sort the index table according to the minimum value of the data page when performing data merging, merge the data according to the sorting result of the index table and the index information, obtain an ordered result, and write the ordered result back to the flash memory.

A computer device comprises a memory and a processor, wherein the memory stores a computer program, and when the processor executes the computer program, the following steps are implemented:

An ordered intermediate result generation module obtains small files read into the memory, sorts the small files, obtains ordered intermediate results, and writes the ordered intermediate results back to the flash memory. The small files are obtained by segmenting the large file data.

An index table construction module, used to construct an index table in the memory of the SSD according to the minimum value of each data page in the ordered intermediate result and the location information of the data page on the flash memory; the index table contains index information corresponding to the location information;

The data merging module is used to sort the index table according to the minimum value of the data page when performing data merging, merge the data according to the sorting result of the index table and the index information, obtain an ordered result, and write the ordered result back to the flash memory.

A computer-readable storage medium stores a computer program, which, when executed by a processor, implements the following steps:

An ordered intermediate result generation module obtains small files read into the memory, sorts the small files, obtains ordered intermediate results, and writes the ordered intermediate results back to the flash memory. The small files are obtained by segmenting the large file data.

An index table construction module, used to construct an index table in the memory of the SSD according to the minimum value of each data page in the ordered intermediate result and the location information of the data page on the flash memory; the index table contains index information corresponding to the location information;

The data merging module is used to sort the index table according to the minimum value of the data page when performing data merging, merge the data according to the sorting result of the index table and the index information, obtain an ordered result, and write the ordered result back to the flash memory.

The above-mentioned SSD external sorting method, device, computer equipment and storage medium divide the large data file into small files that can be accommodated in the host-side memory, read each small file into the memory in turn for sorting, obtain an ordered intermediate result, write the ordered intermediate result back to the SSD side in units of data pages, build an index table in the SSD memory according to the minimum value and position information of each data page, sort the index table according to the minimum value of the data page, and determine the order of reading data pages in the data merging stage according to the index table, which can avoid the data pages with large values residing in the memory, and improve the execution efficiency of the algorithm. Merge data according to the sorting result of the index table and the index information to obtain an ordered result, and write the ordered result back to the flash memory. When the host side frequently queries the ordered result, the ordered result can be directly output without re-executing the merge operation. The embodiment of the present invention can improve the multi-channel concurrency of SSD reading and writing and improve the channel resource utilization of SSD.

BRIEF DESCRIPTION OF THE DRAWINGS

FIG1 is a schematic flow chart of an external sorting method for SSDs in one embodiment;

FIG2 is a schematic diagram of data page reading and writing in the data merging phase of IndexSort in one embodiment;

FIG3 is a schematic diagram showing the effect of different ratios of read and write channels on the performance of a write-back strategy in one embodiment;

FIG4 is a schematic diagram of the merging phase of IndexSort in another embodiment;

FIG5 is a schematic diagram showing the effect of different data set sizes on the performance of Isort and Baseline in one embodiment;

FIG6 is a schematic diagram showing the effect of different DRAM sizes on the performance of Isort and Baseline in one embodiment;

FIG7 is a block diagram of an external sorting device of an SSD in one embodiment;

FIG. 8 is a diagram showing the internal structure of a computer device in one embodiment.

DETAILED DESCRIPTION

In order to make the purpose, technical solution and advantages of the present application more clear, the present application is further described in detail below in conjunction with the accompanying drawings and embodiments. It should be understood that the specific embodiments described herein are only used to explain the present application and are not used to limit the present application. The present invention is based on the external sorting algorithm of Active SSD and proposes an external sorting algorithm called IndexSort.

In one embodiment, as shown in FIG1 , a method for external sorting of SSDs is provided, comprising the following steps:

Step 102, obtain the small files read into the memory, sort the small files, obtain ordered intermediate results, and write the ordered intermediate results back to the flash memory.

Small files are obtained by splitting large file data. Due to limited memory space, large file data is split into small files that can be accommodated in the memory. The small files are read into the memory and sorted in memory to obtain ordered intermediate results. The ordered intermediate results are written back to the flash memory of the SSD in units of data pages. The ordered intermediate results are sorted through data merging to obtain ordered results.

Step 104: construct an index table in the memory of the SSD according to the minimum value of each data page in the ordered intermediate result and the location information of the data page on the flash memory.

The index table contains index information corresponding to the position information, detects the minimum value of each data page in the ordered intermediate result, builds a data page minimum value index table based on the minimum value of the data page and the position information on the flash memory, and sorts the index table from small to large based on the minimum value of the data page. The main function of the index table is to determine the order in which data blocks are read from the flash memory to the input cache of the SSD during the merge phase. By building the index table, the order in which data pages are read during the merge phase is determined, thereby speeding up the execution of external sorting.

Step 106, when merging data, sort the index table according to the minimum value of the data page, merge the data according to the sorting result of the index table and the index information, obtain an ordered result, and write the ordered result back to the flash memory.

Merging externally sorted data within the SSD can reduce data transmission and read and write operations on the SSD, while utilizing the internal concurrency and high I/O bandwidth of the SSD to greatly improve algorithm execution performance. The merged ordered results are written back to the flash memory to save the ordered results. When the host frequently queries the ordered results, there is no need to re-execute the merge operation, which can save time.

In the above-mentioned external sorting method of SSD, the large data file is divided into small files that can be accommodated in the host-side memory, and each small file is read into the memory in turn for sorting to obtain an ordered intermediate result, and the ordered intermediate result is written back to the SSD side in units of data pages. An index table is constructed in the memory of the SSD according to the minimum value and position information of each data page, and the index table is sorted according to the minimum value of the data page. The order of reading data blocks can be predicted according to the index table, and the execution performance of the algorithm is improved by pre-reading the data. Data is merged according to the sorting result and index information of the index table to obtain an ordered result, and the ordered result is written back to the flash memory. When the host side frequently queries the ordered result, the ordered result can be directly output without re-executing the merge operation. The embodiment of the present invention can improve the multi-channel concurrency of SSD reading and writing, and improve the channel resource utilization of SSD.

In one of the embodiments, data is merged according to the sorting results and index information of the index table to obtain an ordered result, and the ordered result is written back to the flash memory, including: reading data pages in sequence according to the sorting results and index information of the index table to the input cache of the SSD; merging data pages to obtain an ordered result, recording the minimum value of the next data page to be merged, and when the data size in the input cache does not exceed the minimum value, the ordered results are written back to the flash memory in batches. In this embodiment, merging data pages according to the index table realizes that the data page with the smallest data in the large file data is read into the input cache first to participate in the merge. By writing back small value data in batches, the time that data pages with larger values stay in the memory can be reduced, and more space can be freed up in the memory, thereby speeding up the execution of the merge stage.

In one of the embodiments, it also includes: when the data size in the input cache is greater than the minimum value, writing the data page containing the minimum data in the ordered result back to the flash memory, reading the next data page to be merged into the input cache, and iteratively merging the data pages in the input cache.

In this embodiment, taking the data page reading and writing schematic diagram of IndexSort in the data merging stage shown in FIG2 as an example, according to the order of the index table, b1, b2, a1, a2, a3, c1, c2 and a4 are read in sequence, and the merging and comparison operation is performed, and the minimum value of the next data page is recorded at the same time, that is, the minimum value of data page b3 is used as a threshold. If all the data in the data cache area is smaller than the threshold, it means that this part of the data is also the smallest data that has not been written back to the flash memory channel. Then, this part of the data can be written back to the flash memory in batches after sorting, thereby improving the flash memory channel writing multi-channel concurrency and improving the flash memory channel resource utilization. At the same time, the data cache area will also free up more space. At this time, multiple data pages can be read according to the current data cache area free space status, which can improve the flash memory reading multi-channel concurrency and improve the flash memory channel resource utilization.

In one of the embodiments, it also includes: setting a read flash channel and a write flash channel between the flash memory and the input cache; the read flash channel processes the read request for data merging, and reads data from the read flash channel to the input cache; the write flash channel processes the write back request for data merging, writes the ordered result back to the write flash channel, and writes the ordered result back to the flash memory through the write flash channel. In this embodiment, the read and write channel separation strategy is used to process the read and write requests for data merging. The read and write channel separation strategy means that the read flash channel is specifically used to process the read request for data merging, the input cache reads data from the read flash channel, and the write flash channel is mainly used to process the write back request for data merging, and writes the merged ordered result back to the flash channel. In this way, the channel resource utilization rate of the SSD can be fully improved, the idle channel situation can be reduced, the concurrency of the read and write multi-channels can be improved, and the execution performance of the algorithm can be accelerated.

In a specific embodiment, as shown in FIG3 , a schematic diagram of the performance impact of different read-write channel ratios on the write-back strategy is provided, Baseline refers to ActiveSort, RT represents read time, WT represents write-back time, Avg represents average, and the write-back strategy refers to the read-write channel hybrid strategy and the read-write channel separation strategy. The read-write channel hybrid strategy means that the flash memory channel must process both the read request of data merging and the write request of data merging. In FIG3 , the horizontal axis is the ratio of the read-write channel when the read-write channel is separated. The SSDSim simulator is set with 16 flash memory channels in total. The SSDSim simulator is a configurable, modular solid-state disk simulator. The parameter configuration of the SSDSim simulator is shown in the following table:

SSDSim simulator parameter settings

The horizontal axis 16:16 refers to the average processing delay of read and write requests under the read-write channel hybrid strategy. At this time, the read-write hybrid strategy has the best performance because 16 channels are used to process read and write requests in the merge stage, reducing the idleness of the SSD flash channel. The read-write channel hybrid strategy can improve the flash channel resource utilization and speed up the execution of the merge stage. The horizontal axis 12:4 means that 12 channels are used to process read requests in the merge stage, and 4 channels are used to process write requests in the merge stage. The merged ordered results are written back to the independent 4 channels without occupying the resources of the read channel. However, when performing read operations and algorithm merge operations in the merge stage, the write channel will be idle, which does not improve the channel resource utilization of the SSD well. Under the read-write channel separation strategy, as the number of read channels increases and the number of write channels decreases, it can be seen that the average response time for processing read requests in the line graph gradually increases, while the average processing time for write requests decreases. In summary, the read-write channel hybrid strategy can give full play to the read-write multi-channel concurrency of the SSD and improve the channel resource utilization.

In one of the embodiments, writing the ordered intermediate results back to the flash memory includes: allocating the ordered intermediate results to each flash memory channel between the memory and the flash memory in an interleaved manner with data pages as basic units, and writing the ordered intermediate results back to the flash memory through the flash memory channels. In this embodiment, the ordered intermediate results are written back to the flash memory using an interleaved data placement strategy, which means that the ordered intermediate results are interleaved to each channel of the SSD in an interleaved manner with data pages as basic units, so that the multi-channel write concurrency performance of the SSD can be fully utilized, the channel resource utilization rate can be improved, and the efficiency of writing back to the flash memory can be improved.

In one embodiment, the number of data pages of the ordered intermediate result is equal to the number of data pages that the SSD input buffer can accommodate. In this embodiment, the accuracy of the algorithm can be guaranteed only by ensuring that the number of data pages of the input buffer is equal to the number of data pages of the ordered intermediate result.

In a specific embodiment, as shown in FIG4 , a schematic diagram of the merge phase of IndexSort is provided. In FIG4 , in the traditional merge phase, a data page is read from each of the six intermediate results into the cache for merge comparison. When the data distribution is not particularly uniform, data pages with smaller values such as (2, 4, 12) and data pages with larger values (200, 400, 612) are read into the cache together, and the data with smaller values are first written back to the flash channel, and then the data with larger values are written back. The data pages with larger values (200, 400, 612) will remain in the cache and be merged and compared with the data with smaller values, occupying DRAM space until the merge phase reaches the end, and the data with larger values will be written back to the flash channel. In Figure 4, Isort refers to Indexsort, sort refers to sorting, and output buffer refers to the output cache in the flash memory. In the merging stage of IndexSort, 6 ordered intermediate results are stored in the flash memory of the SSD. The ordered intermediate results are called runs. Each ordered intermediate result contains three data pages. The values of each ordered intermediate result are sorted from small to large. The input cache in the SSD has 6 data page spaces. According to the order of the index table (page_min_index), the first 6 data pages are read into the input cache in turn and sorted. These 6 data pages containing the minimum values may come from the same run. The minimum value of the seventh data page with the minimum value is 25. Therefore, the values smaller than 25 in the cache can be directly written back to the flash memory. Because the data in the cache that are smaller than 25 are also part of the current minimum value data, they can be written back in batches.

In this embodiment, the IndexSort algorithm can solve the problem of data pages with large values being retained in the memory when the data is partially ordered, thereby improving DRAM resource utilization. At the same time, data below the threshold can be written back to the flash memory in batches, and reading data is not limited to reading only one data page. This threshold refers to the minimum value of the data page that is currently in the index table and has not been read into the DRAM. During the merging process, IndexSort concurrently writes multiple data pages in the DRAM that are below the threshold back to the flash memory, freeing up more cache space for reading the next batch of data pages from the flash memory. This is conducive to improving the multi-channel resource utilization of the SSD and improving the multi-channel concurrency of reading and writing.

In one embodiment, as shown in FIG5 , a schematic diagram of the performance impact of different data set sizes on Isort and Baseline is provided. Isort refers to Indexsort, Baseline refers to ActiveSort, RT refers to read time, WT refers to write back time, Avg refers to average, and the time on the vertical axis refers to the average response time of read and write requests. The average response time of read and write requests can be a good indicator to measure the response time of the external sorting algorithm in the merging process inside the SSD. Because the response time includes the request processing time and the waiting time, the shorter the average response time of the read and write requests, the higher the performance of the algorithm. The data volume is set to 100M, 200M, 400M, 800M and 1GB respectively. It can be seen that as the data volume increases, the average response time of the read and write requests of the two algorithms increases, but under various data volumes, the performance of IndexSort is better than that of Baseline (ActiveSort).

In a specific embodiment, as shown in FIG6 , a schematic diagram is provided of the performance impact of different DRAM sizes on Isort and Baseline, where Isort refers to Indexsort, Baseline refers to ActiveSort, RT represents read time, WT represents write back time, and Avg represents average. The internal DRAM capacity of the SD is limited, but the DRAM can cache some read and write requests, which can speed up the processing time of read and write requests in the SSD. As the DRAM capacity increases, the average response delay of the read and write requests of the two algorithms decreases. Under different DRAM conditions, the average response time of the read and write requests of IndexSort is less than that of ActiveSort, and the performance is improved by nearly 36%.

It should be understood that, although the various steps in the flowchart of FIG. 1 are shown in sequence according to the indication of the arrows, these steps are not necessarily executed in sequence according to the order indicated by the arrows. Unless there is a clear explanation in this article, the execution of these steps is not strictly limited in order, and these steps can be executed in other orders. Moreover, at least a portion of the steps in FIG. 1 may include a plurality of sub-steps or a plurality of stages, and these sub-steps or stages are not necessarily executed at the same time, but can be executed at different times, and the execution order of these sub-steps or stages is not necessarily to be carried out in sequence, but can be executed in turn or alternately with other steps or at least a portion of the sub-steps or stages of other steps.

In one embodiment, an external sorting device for an SSD is provided, comprising: an ordered intermediate result generating module 702, an index table building module 704 and a data merging module 706, wherein:

The ordered intermediate result generation module 702 obtains the small files read into the memory, sorts the small files, obtains the ordered intermediate results, and writes the ordered intermediate results back to the flash memory. The small files are obtained by segmenting the large file data.

An index table building module 704 is used to build an index table in the memory of the SSD according to the minimum value of each data page in the ordered intermediate result and the location information of the data page on the flash memory; the index table contains index information corresponding to the location information;

The data merging module 706 is used to sort the index table according to the minimum value of the data page when merging data, merge the data according to the sorting result of the index table and the index information, obtain the ordered result, and write the ordered result back to the flash memory.

In one embodiment, the ordered intermediate result generation module 702 is further used to distribute the ordered intermediate results to each flash memory channel between the memory and the flash memory in an interleaved manner with data pages as basic units, and write the ordered intermediate results back to the flash memory through the flash memory channel.

In one of the embodiments, the data merging module 706 is also used to read data pages into the input cache of the SSD in sequence according to the sorting results and index information of the index table; merge the data pages to obtain ordered results, record the minimum value of the next data page to be merged, and when the data size in the input cache does not exceed the minimum value, write the ordered results back to the flash memory in batches.

In one of the embodiments, it is also used to merge two ordered intervals to obtain a merged ordered interval when the maximum value of the ordered interval is less than the minimum value of another ordered interval; and update the index table according to the position information of the merged ordered interval.

In one of the embodiments, when the data size in the input cache is greater than the minimum value, the data page containing the minimum data in the ordered result is written back to the flash memory, the next data page to be merged is read into the input cache, and the data pages in the input cache are iteratively merged.

In one of the embodiments, a read flash channel and a write flash channel are also set between the flash memory and the input cache.

In one of the embodiments, the read flash channel is also used to process a read request for data merging, and read data from the read flash channel to the input cache.

In one of the embodiments, the write flash channel is also used to process write-back requests for data merging, write the ordered results back to the write flash channel, and write the ordered results back to the flash memory through the write flash channel.

In one of the embodiments, the number of data pages used for the ordered intermediate results is equal to the number of data pages that can be accommodated by the SSD input buffer.

For the specific definition of the external sorting device of the SSD, please refer to the definition of the external sorting method of the SSD above, which will not be repeated here. Each module in the above-mentioned external sorting device of the SSD can be implemented in whole or in part by software, hardware and a combination thereof. The above-mentioned modules can be embedded in or independent of the processor in the computer device in the form of hardware, or can be stored in the memory of 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, including a memory and a processor, wherein the memory stores a computer program, and the processor implements the steps of the method in the above embodiment when executing the computer program.

In one embodiment, an SSD memory is provided, and the SSD memory is obtained by executing the steps of the SSD external sorting method in the above embodiment.

Those skilled in the art can understand that all or part of the processes in the above-mentioned embodiments can be implemented by instructing the relevant hardware through a computer program, and the computer program can be stored in a non-volatile computer-readable storage medium. When the computer program is executed, it can include the processes of the embodiments of the above-mentioned methods. Among them, the non-volatile memory of the SSD memory cited in the embodiments provided in this application can include a read-only memory (ROM), a programmable ROM (PROM), an electrically programmable ROM (EPROM), an electrically erasable programmable ROM (EEPROM) or a flash memory.

The technical features of the above embodiments may be arbitrarily combined. To make the description concise, not all possible combinations of the technical features in the above embodiments are described. However, as long as there is no contradiction in the combination of these technical features, they should be considered to be within the scope of this specification.

The above-mentioned embodiments only express several implementation methods of the present application, and the descriptions thereof are relatively specific and detailed, but they cannot be understood as limiting the scope of the invention patent. It should be pointed out that, for a person of ordinary skill in the art, several variations and improvements can be made without departing from the concept of the present application, and these all belong to the protection scope of the present application. Therefore, the protection scope of the patent of the present application shall be subject to the attached claims.

Claims (10)

1. A method of external ordering of SSDs, the method comprising:

the method comprises the steps of obtaining small files read into a memory, sequencing the small files to obtain an ordered intermediate result, and writing the ordered intermediate result back into a flash memory, wherein the small files are obtained by cutting large file data;

Constructing an index table in the memory of the SSD according to the minimum value of each data page in the ordered intermediate result and the position information of the data page on the flash memory; the index table comprises index information corresponding to the position information;

And when data merging is carried out, sorting the index table according to the minimum value of the data page, carrying out data merging according to the sorting result of the index table and the index information to obtain an ordered result, and writing the ordered result back to the flash memory.

2. The method of claim 1, wherein merging data according to the sorted results of the index table and the index information to obtain an ordered result, writing the ordered result back to flash memory comprises:

Sequentially reading data pages into an input buffer of the SSD according to the ordering result of the index table and the index information;

And merging the data pages to obtain an ordered result, recording the minimum value of the data pages to be merged, and writing the ordered result back to the flash memory in batches when the data size in the input cache does not exceed the minimum value.

3. The method according to claim 2, wherein the method further comprises: and when the data size in the input buffer memory is larger than the minimum value, writing the data page containing the minimum data in the ordered result back to the flash memory, reading the next data page to be merged into the input buffer memory, and iteratively merging the data page in the input buffer memory.

4. A method according to any one of claims 1-3, wherein the method further comprises:

And setting a flash reading channel and a flash writing channel between the flash and the input buffer.

5. The method of claim 4, wherein the read flash channel processes a read request for data merge, and wherein data is read from the read flash channel to the input buffer.

6. The method of claim 4, wherein the write flash channel processes a write back request for data merge, writes the ordered result back to the write flash channel, and writes the ordered result back to the flash memory via the write flash channel.

7. The method of claim 1, wherein writing back the ordered intermediate results to flash memory comprises:

and the ordered intermediate results are distributed to each flash memory channel between the memory and the flash memory in a staggered way by taking the data page as a basic unit, and the ordered intermediate results are written back to the flash memory through the flash memory channels.

8. The method of any of claims 1,2, 3, or 7, wherein the number of data pages of the ordered intermediate result is equal to the number of data pages that the SSD input cache can accommodate.

9. An external ordering apparatus of an SSD, the apparatus comprising:

the ordered intermediate result generation module is used for acquiring small files read into the memory, ordering the small files to obtain ordered intermediate results, writing the ordered intermediate results back into the flash memory, and dividing the small files into large file data;

The index table construction module is used for constructing an index table in the memory of the SSD according to the minimum value of each data page in the ordered intermediate result and the position information of the data page on the flash memory; the index table comprises index information corresponding to the position information;

And the data merging module is used for sorting the index table according to the minimum value of the data page when merging the data, merging the data according to the sorting result of the index table and the index information to obtain an ordered result, and writing the ordered result back to the flash memory.

10. An SSD memory, characterized in that the SSD memory is obtained by performing the steps of the external ordering method of the SSD of any one of claims 1 to 8.