WO2018019119A1 - Method and device for dynamic partial-parallel data layout for continuous data storage - Google Patents

Abstract

A method and device for a dynamic partial-parallel data layout (DPPDL) for continuous data storage being applicable in the storage of continuous data. The method is specifically realized by the technical solutions of stripe dividing, storage space dynamic mapping, access competition avoidance and performance requirement sensing, and comprises: firstly acquiring a performance requirement of a storage application via performance requirement sensing, subsequently executing a storage space dynamic mapping mechanism, dynamically allocating a storage space having an appropriate level of hard disk parallelism according to the performance requirement, and lastly optimizing the storage space dynamic mapping mechanism via access competition avoidance, wherein, the storage space dynamic mapping is a core component, and the performance requirement sensing is the basis of the storage space dynamic mapping, stripe dividing is a prerequisite for the storage space dynamic mapping, and access competition avoidance optimizes and completes the storage space dynamic mapping. The DPPDL utilizes a dynamic partial-parallel strategy, and dynamically allocates storage space having an appropriate level of parallelism according to the performance requirements of different loads, thus guaranteeing power-saving when the majority of the hard disks are on standby for a long time, and dynamically providing appropriate partial parallelism, thereby providing better usability and higher power-saving efficiency.

Description

Dynamic local parallel data layout method and device for continuous data storage Technical field

The present invention relates to the field of redundant array technology for independent hard disks, and in particular, to a dynamic local parallel data layout method and apparatus for continuous data storage.

Background technique

In recent years, video surveillance, backup, archiving and other related technologies have been widely used. Taking video surveillance as an example, video surveillance has become an ubiquitous security facility in modern society because it plays an irreplaceable role in forensics and identification. This kind of application requires a large amount of storage space, mainly performs write operations, mainly sequential access, and has low requirements on random performance. The storage system is called a continuous data storage system.

In the massive data storage, in order to meet the performance, capacity and reliability requirements of the storage system, various types of Redundant Arrays of Independent Disks (RAID) have been proposed. RAID combines multiple physical storage devices, such as disks and Solid State Disks (SSDs), to form a unified logical storage device that provides greater capacity, higher performance, and more reliable data security.

The technical terms commonly used in RAID are as follows:

Striping: A method of dividing a piece of continuous data into blocks of the same size and writing each piece of data to different disks in RAID.

Fault Tolerance: Generates redundant verification data and saves it using some kind of operation, such as XOR operation. When the hard disk fails and data is lost, the verification data can be used for data recovery. XOR operations are usually indicated by "".

Distribution check: The check data is distributed on each disk constituting the RAID according to a certain rule.

Partial Parallelism: Only some of the hard disks in the array are parallel, rather than all hard disks in parallel, providing the right performance and facilitating the scheduling of the remaining hard drives.

Commonly used RAIDs are RAID0, RAID5, and so on. RAID0 is only striped, and does not have redundancy check capability. RAID 5 writes data to the hard disks in the array in a stripe manner. The verification data is distributed and stored on each disk in the array. The access speed is improved by global parallelism, and the single disk is fault tolerant.

Continuous data storage systems are based on sequential access, which does not require random performance and generally does not require high performance provided by global parallelism. To this end, the invention patents ZL201010256899.5, ZL201010256665.0, ZL201010256711.7, ZL201010256908.0, ZL201010256679.2, ZL201010256699.X, ZL201010575578.1, ZL201010575625.2, ZL201010575611.0, etc. propose a variety of local parallel data layout, Energy-efficient RAIDs using this type of locally parallel data layout are collectively referred to as S-RAID.

The basic idea of S-RAID is: 1 to divide the storage in the array into several groups, and provide appropriate performance in parallel within the group. The grouping is convenient for scheduling some hard disks to run while the remaining hard disks are standby energy-saving; 2 adopting greedy addressing method in sequential access mode To ensure that the read and write operations are distributed over a certain period of time on a certain hard disk, other hard disks can be used for a long time to save energy.

The data layout of the S-RAID adopts the static mapping mechanism of the storage space, that is, when creating, the logical block address (LBA) and the physical block address of the hard disk are established according to parameters such as the number of disk blocks, the S-RAID type, and the strip size. (Physical Block Address, PBA) mapping; this mapping remains unchanged throughout the life of the S-RAID.

However, the static data layout of S-RAID is suitable for a relatively stable workload, and the local parallelism cannot be dynamically adjusted according to the performance requirements of fluctuating load and burst load. For fluctuating load and burst load, S-RAID needs performance according to peak load. The demand determines the degree of local parallelism, but the degree of parallelism is clearly excessive for the valley load. This excess performance leads to additional energy consumption and increases significantly with fluctuating loads and burst load strength.

In continuous data storage, strong fluctuation loads and burst loads are common. For example, in video surveillance, the dynamic nature of video content can create severe fluctuating loads. Video data is generally compressed and transmitted and stored. Existing video compression standards, such as H.264/MPEG-4, are based on the temporal and spatial redundancy of video content for video compression. The video compression ratio will be very high. Change within a wide range. There are more moving objects during the day, the video compression is relatively small, and the amount of video data generated is large; there are fewer moving objects at night, the video compression is relatively high, and the amount of generated video data is small. In addition, when the working time and resolution of each camera in video surveillance are different, a high-intensity fluctuation load is also generated.

For strong fluctuations and sudden load, it is not feasible to adopt caching measures. For example, in video surveillance, the load not only has a large fluctuation range, but also the fluctuation period is long enough to require a large-capacity cache device. Disk caching not only increases hardware costs, but also introduces additional power consumption; while SSD caching is low in power consumption, heavy use can add significant cost. Deep cache also greatly increases the probability of data loss. Cache devices usually have no fault tolerance mechanism, and add fault tolerance to cache devices, which will further increase hardware cost and power consumption.

To this end, a Dynamic Partial-Parallel Data Layout (DPPDL) for continuous data storage is proposed. DPPDL adopts dynamic local parallel strategy to dynamically allocate storage space with appropriate parallelism according to the performance requirements of different loads. . DPPDL not only guarantees long-term standby energy saving for most hard disks, but also dynamically provides appropriate local parallelism, higher availability, and higher energy efficiency.

Summary of the invention

The object of the present invention is to solve the problem that the existing static partial parallel data layout can not be better adapted to the fluctuating load and the sudden load. In order to improve the energy-saving efficiency of the storage system, a dynamic localization oriented to continuous data storage is proposed. Row data layout method and device.

A dynamic local parallel data layout method (DPPDL) for continuous data storage is realized by the following technical solutions:

Including stripe partitioning, storage space dynamic mapping, access competition avoidance, and performance demand awareness; firstly, the performance requirements of the storage application are obtained through performance requirement perception, and then the storage space dynamic mapping mechanism is executed, and the storage with the appropriate hard disk parallelism is dynamically allocated according to the performance requirement. Space, finally optimize the storage space dynamic mapping mechanism by accessing competition avoidance; among them, storage space dynamic mapping is the core, performance requirement perception is the basis of storage space dynamic mapping, stripe partitioning is the premise of storage space dynamic mapping, and access competition avoidance It is the optimization and completeness of the dynamic mapping of storage space;

The strip is divided, and the specific steps are as follows:

Step 1.1 divides each hard disk in the N hard disks into 1×N storage blocks; wherein, 1 is greater than or equal to 1, and N is greater than or equal to 3;

In step 1.1, the N storage blocks with the same starting address in each hard disk form a stripe, which constitutes 1×N strips; each strip contains 1 parity storage block, and N-1 data storage blocks. , the check storage block is referred to as a check block, and the data storage block is referred to as a data block;

Wherein, the check block in the strip i is located in the hard disk N-1-j; if j+v<N-1, the vth data block is located on the hard disk v, otherwise it is located on the hard disk v+1, wherein 0≤i <(1×N), j=i MOD N (MOD is a modulo operation), 0≤v<N-1;

Step 1.2: Each data block and the check block in step 1.1 are M equal-sized sub-blocks, and each sub-block includes a plurality of consecutive storage areas, which are respectively called a data sub-block strip and a parity sub-block PStrip;

Step 1.3 in step 1.1, each sub-block with the same starting address in the strip is formed into a sub-strip stripe, and then the strip in the sub-strip is XORed to generate a PStrip in the sub-strip;

Wherein each strip includes M sub-strips of the same size; the sub-band PStrip m of the strip stripe stripe is generated by X X of its N-1 data sub-blocks, see equation (1), ;

The storage space dynamic mapping is specifically:

The disk array storage space is allocated and managed by the dynamic mapping mechanism of the logical block address and the physical block address, and the write data received by the disk array layer can be dynamically mapped to different numbers of hard disks; that is, according to the performance requirement parameters of the load k, dynamically allocate storage space with k hard disk parallelism, that is, k is the number of hard disks that need to write data concurrently, and does not include the hard disk where the verification data of the written data is located; when the load is minimum, only maps to one hard disk Write data only to the hard disk; when the load is maximum, it maps to the remaining hard disks of the hard disk that does not include the check data, and writes data to the remaining hard disks of the hard disk that does not include the check data;

Dynamic mapping of storage space, the specific steps are:

(1) Select the Stripe with the most free strips in CurBank as CurStripe;

The free strip is an unmapped strip; the strip list is a one-way circular list consisting of all strips, CurBank is the currently mapped strip, the initial value is strip 0; CurStripe is CurBank a stripe that can be mapped;

(2) If the number of free strips in CurStripe is 0, it means that CurStripe has no free strip mapable, equivalent to CurBank without free strip mapable, go to (3), otherwise go to (5);

(3) Determine whether NextBank has free strip mapability. If there is no free strip mappable, delete the storage data on NextBank and perform storage space recovery. Among them, NextBank is the next stripe to be mapped, adjacent to the CurBank number. The initial value is strip 1;

(4) Take NextBank as CurBank and re-acquire CurStripe, then move the NextBank back in order;

(5) If the number of free strips in CurStripe is not less than k, then sequentially extract k strips from CurStripe, go to (7), otherwise go to (6);

(6) First take all the free strips from CurStripe, and then take the remaining free strips from NextStripe to form k free strips. If NextStripe does not have enough free strips, delete the stored data on NextBank and recycle the storage space. And re-acquire NextStripe; where, NextStripe is the Stripe that can be mapped in NextBank;

(7) after obtaining k free strips, performing storage space mapping, mapping the logical address space to a physical address space having k hard disk parallelism; and recording the mapping relationship in the mapping table;

Determine the offset of the disk and disk in the strip according to the strip, the sub-strip, and the number in the sub-strip where the strip is located, and record it in the mapping table. When reading, obtain data on the disk according to the mapping table. The location; the mapping table is an important part of the metadata, stored at the end of each working disk, with a version number, the version number is from small to large, and the disk array is loaded the most when the power is restored. Numbered version

The access competition avoids, the specific steps are:

1) When DPPDL selects a strip across 2 stripes for storage space mapping, first take all free strips from CurStripe, and then take the remaining free strips from NextStripe to form k+1 free strips together, if NextStripe is not enough Free Strip, delete the stored data on NextBank, reclaim storage space, and regain NextStripe;

2) DPPDL performs the access competition check. If there is no access competition or the end strip causes the access competition, the last strip is deleted; otherwise, the strip causing the access competition is deleted. Finally, obtain k strips that do not cause access competition and can be accessed concurrently;

The access competition check refers to whether two sub-blocks of the same hard disk are concurrently accessed;

The access competition avoidance can be used to replace the step (6) in the storage space dynamic mapping;

Performance demand awareness, specifically:

Continuous data storage applications require a stable data transfer rate, so DPPDL uses the data transfer rate as a performance requirement indicator.

In order to sense the performance requirements of the load online, that is, the data transmission rate requirement,

Step A. DPPDL statistics history information of the disk array layer I/O request queue;

Step B. DPPDL performs analysis and prediction;

For continuous data storage applications, the fluctuation period or burst time of the load is generally large, and the data transmission rate of the load demand can be perceived according to the average data transmission rate in the time window T, and the time is recorded by rn=(ta, pos, len). The nth I/O request in the window T; wherein, ta, pos, and len are the arrival time, the starting logical address, and the request length of the request rn, respectively, and the request length len of rn is represented by rn.len;

Data transfer rate for perceived load demand:

Where num is the number of I/Os coming in the time window T; β is the coefficient of performance, which can be between 1.2 and 1.5;

5s<T<15s;

Representing the length summation of num I/O requests in the time window T;

Where the I/O request rn in equation (2) comes from the request queue of the RAID layer.

After DPPDL senses the data transmission rate of the load demand, it determines the number of hard disks that need to concurrently write data according to the data transmission rate that can be provided by different hard disk parallelism in the actual application scenario.

Beneficial effect

The dynamic local parallel data layout oriented by continuous data storage proposed by the invention has the following advantages compared with the prior art:

1. It can provide large elastic parallelism and has higher energy saving efficiency, specifically:

DPPDL uses a dynamic local parallel strategy to dynamically allocate storage space with appropriate parallelism according to the performance requirements of different workloads. DPPDL not only guarantees long-term standby energy saving for most disks, but also dynamically provides appropriate local parallelism, higher availability, and higher energy efficiency;

2. Solved the contradiction between dynamic local parallelism and sequential deletion features, specifically:

For a continuous data storage system, when the storage space is full, the oldest stored data is generally deleted by time, and then new data is written, which is called a sequential deletion feature. There is a contradiction between the dynamic local parallelism and the sequential deletion feature. For example, when the storage space is full, if the current load requires 5 disks in parallel, but the oldest data is stored on 2 partially parallel disks, the data cannot be deleted sequentially. Under the conditions, add 3 more disks in parallel;

DPPDL sequentially allocates and reclaims storage space in strips, when the number of stripes is large (for Large-capacity disks are possible) to ensure that data is deleted in a substantially chronological order. Microscopically, Strip is used as the mapping unit, and the appropriate amount of Strip parallel is selected on Stripe according to performance requirements, and the appropriate parallelism is dynamically provided, thus solving the contradiction between dynamic local parallelism and sequential deletion characteristics.

DRAWINGS

The accompanying drawings, which are incorporated in FIG

1 is a flow chart showing the steps of a dynamic local parallel data layout method for continuous data storage according to an embodiment of the present invention;

2 is a schematic diagram of strip partitioning in a dynamic local parallel data layout method for continuous data storage according to an embodiment of the present invention;

3 is a schematic diagram of subdivision of strip partitioning in a dynamic local parallel data layout method for continuous data storage according to an embodiment of the present invention;

4 is a schematic diagram of dynamic mapping of a storage space in a dynamic local parallel data layout method for continuous data storage according to an embodiment of the present invention;

FIG. 5 is a schematic diagram of access competition generation in a dynamic local parallel data layout method for continuous data storage according to an embodiment of the present invention; FIG.

6 is a schematic diagram of access competition avoidance in a dynamic local parallel data layout method for continuous data storage according to an embodiment of the present invention;

FIG. 7 is a schematic diagram of dynamic mapping of storage space after access competition avoidance in a dynamic local parallel data layout method for continuous data storage according to an embodiment of the present invention; FIG.

FIG. 8 is a schematic structural diagram of a dynamic local parallel data layout apparatus for continuous data storage according to an embodiment of the present invention.

detailed description

The present invention will be described in detail below with reference to the drawings and specific embodiments.

As shown in FIG. 1 , the dynamic local parallel data layout method for continuous data storage in the embodiment of the present invention may specifically include the following steps:

Step 101: Striping, dividing each hard disk in the N hard disks into 1×N storage blocks equally;

Step 102: Perceive performance requirements and obtain performance requirements of the storage application;

Step 103: Determine whether there is access competition, if yes, proceed to step 104, otherwise perform step 105;

Step 104: Accessing the competition avoidance and optimizing the dynamic mapping mechanism of the storage space;

Step 105: Perform allocation management on the storage space by using a dynamic mapping mechanism.

Specifically achieved through the following technical solutions:

Including stripe partitioning, storage space dynamic mapping, access competition avoidance, and performance demand awareness; firstly, the performance requirements of the storage application are obtained through performance requirement perception, and then the storage space dynamic mapping mechanism is executed, and the storage with the appropriate hard disk parallelism is dynamically allocated according to the performance requirement. Space, and finally optimize the storage space dynamic mapping mechanism by accessing the competition avoidance;

Among them, storage space dynamic mapping is the core, performance requirement perception is the basis of storage space dynamic mapping, stripe partitioning is the premise of storage space dynamic mapping, and access competition avoidance is the optimization and completeness of storage space dynamic mapping.

The embodiment of the present invention is a basic process for constructing a dynamic local parallel data layout DPPDL on five disks, including strip partitioning, storage space dynamic mapping, access competition avoidance, and performance requirement sensing; wherein each disk is The disk capacity is 4TB (1TB=103GB=106MB=109KB, 1KB=1024B).

Preferably, the strip is divided, and the specific steps are:

Step 1.1 divides each hard disk in the N hard disks into 1×N storage blocks; wherein, 1 is greater than or equal to 1, and N is greater than or equal to 3;

Step 1.2: Each data block and check block in step 1.1 is M equal-sized sub-blocks, and each sub-block includes a plurality of consecutive storage areas (such as disk sectors), which are respectively called data sub-blocks. Strip and check sub-blocks (denoted as PStrip);

In step 1.3, the sub-blocks in the strip with the same starting address in each strip form a sub-strip (recorded as stripe), and then the strip in the sub-band is XORed to generate the sub-strip. Inside the PStrip.

Preferably, in the above step 1.1, the N storage blocks having the same starting address in each hard disk form a stripe, which constitutes 1×N strips; each strip includes one parity storage block, N-1 Data storage block, check storage block referred to as check block, data storage block referred to as data block;

Wherein, the check block in the strip i is located in the hard disk N-1-j; if j+v<N-1, the vth data block is located on the hard disk v, otherwise it is located on the hard disk v+1, wherein 0≤i <(1×N), j=i MOD N (MOD is a modulo operation), 0≤v<N-1.

Preferably, in step 1.3, each strip includes M sub-bands of the same size; the parity sub-block PStrip m of the strip stripe stripe is generated by X X of its N-1 data sub-blocks, ;

Then the generation method is:

Preferably, the operation idea of the dynamic mapping of the storage space is:

The disk array storage space is allocated and managed by the dynamic mapping mechanism of the logical block address and the physical block address, and the write data received by the disk array layer can be dynamically mapped to different numbers of hard disks; that is, according to the load The performance requirement parameter k dynamically allocates the storage space with k hard disk parallelism, that is, k is the number of hard disks that need to concurrently write data, and does not include the hard disk where the verification data of the written data is located; when the load is minimum, only maps to On a certain hard disk, only data is written to the hard disk; when the load is maximum, it is mapped to the remaining hard disks except one block of one hard disk, and the data is written to the remaining hard disks except one block of one hard disk;

In the embodiment of the present invention, the storage space dynamic mapping, the basic terms involved are defined as follows:

Strip linked list: a one-way circular linked list consisting of all strips;

CurBank: the current stripe to be mapped, called the current map strip, the initial value is stripe 0;

NextBank: the next stripe to be mapped, called the adjacent map strip, adjacent to the CurBank number, the initial value is strip 1;

CurStripe: a route that can be mapped in CurBank;

NextStripe: Stripe that can be mapped in NextBank;

The storage space is dynamically mapped, and the specific steps are:

Step (1) Selecting the stripe with the largest free strip as the CurStripe in CurBank;

Wherein the free strip is a strip that is not mapped;

Step (2) If the number of free strips in CurStripe is 0, indicating that CurStripe has no free strip mappable, go to step (3), otherwise go to step (5);

Step (3) determines whether NextBank has a free strip mappable, and if there is no free strip mappable, delete the stored data on the NextBank to perform storage space recovery;

Step (4) takes NextBank as CurBank and reacquires CurStripe, and then moves NextBank back;

Step (5) If the number of free strips in CurStripe is not less than k, then sequentially extract k strips from CurStripe, go to step (7), otherwise go to step (6);

Step (6) First take all free strips from CurStripe, and then take the remaining free strips from NextStripe to form k free strips. If NextStripe does not have enough free strips, delete the stored data on NextBank, reclaim the storage space, and re-acquire NextStripe;

Step (7) obtains k free strips, performs storage space mapping, maps the logical address space to a physical address space having k hard disks parallelism, and records the mapping relationship in the mapping table;

Determine the offset of the disk and disk in the strip according to the strip, the sub-strip, and the number in the sub-strip where the strip is located, and record it in the mapping table. When reading, obtain data on the disk according to the mapping table. The location; the mapping table is an important part of the metadata, stored at the end of each working disk, with a version number, the version number is from small to large, and the disk array is loaded the most when the power is restored. Numbered version.

Preferably, the access competition avoids, and the specific steps are:

Step 1) When DPPDL selects a strip across 2 strips for storage space mapping, first take all free strips from CurStripe, and then take the remaining free strips from NextStripe and form k+1 free strips together. If NextStripe does not. With enough free strips, delete the stored data on NextBank, reclaim the storage space, and re-acquire NextStripe;

Step 2) DPPDL performs an access competition check. If there is no access competition or the end strip causes the access competition, the last strip is deleted; otherwise, the strip causing the access competition is deleted; finally, k strips that do not cause the access competition and can be concurrently accessed are obtained;

The access competition check refers to whether two sub-blocks of the same hard disk are concurrently accessed.

Preferably, the performance requirement is perceived, specifically:

Continuous data storage applications are not very sensitive to response time and require a stable data transfer rate, so the data transfer rate is used as a performance requirement indicator;

The data transmission rate requirement is specifically:

Step A. DPPDL statistics history information of the disk array layer I/O request queue;

Step B. DPPDL performs analysis and prediction;

For continuous data storage applications, the fluctuation period or burst time of the load is large, and the data transmission rate of the load demand can be perceived according to the average data transmission rate in the time window T, and the time window is recorded with rn=(ta, pos, len). The nth I/O request in T; where ta, pos, and len are the arrival time, the starting logical address, and the request length of the request rn, respectively, and rn.len represents the request length len of rn;

The data transfer rate for perceived load demand is expressed as:

Where num is the number of I/Os coming in the time window T; β is the coefficient of performance, which can be between 1.2 and 1.5;

5s<T<15s;

Representing the length summation of num I/O requests in the time window T;

Wherein, the I/O request rn in formula (2) comes from the request queue of the RAID layer;

After the DPPDL senses the data transmission rate of the load demand, it determines the number of hard disks that need to concurrently write data according to the data transmission rate that can be provided by different hard disk parallelism in the actual application scenario.

The strip partitioning, the storage space dynamic mapping, the access competition avoidance, and the performance requirement perception are described in detail below with reference to the accompanying drawings, specifically:

1, strip division

FIG. 2 is a schematic overall view of the strip division in the embodiment. It can be seen from Figure 2 that each disk is equally divided into 5 memory blocks (where l=1). Since each disk has a capacity of 4TB, each memory block size is 4TB. /5=800GB; each of the five memory blocks in the disk with the same starting address in the disk form a stripe, which forms a total of five strips; as can be seen from Figure 2, each strip contains one check block. And 4 data blocks, the check block of stripe 0 is located on the disk 4, the check block of the stripe 1 is located on the disk 3, ..., and the check block of the stripe 4 is located on the disk 0.

Further, the above-described strip division may be subdivided as shown in FIG. As can be seen from FIG. 3, each data block and the check block are divided into a plurality of equal-sized sub-blocks; in this embodiment, the sub-block size is 100 KB (ie, a sector containing 200 consecutive addresses, a fan) The size of the area is 512 bytes, and each data block and check block is divided into M=800,0000 equal sub-blocks, which are respectively called data sub-blocks and parity sub-blocks. The parity sub-block of the sub-strip is generated by the X-OR operation of the four data sub-blocks of the sub-strip; for example, the parity sub-block of the sub-strip 1 in the strip 0, and the four data sub-blocks of the sub-strip Or the operation is generated.

2, storage space dynamic mapping

After striping, DPPDL uses dynamic mapping mechanism to allocate and manage storage space. Figure 4 shows the address mapping process of five kinds of write loads (A ~ E) in the storage space, select strip 0 and strip 1 to illustrate, assuming each strip contains 6 sub strips (here only For convenience of description, the actual number of sub-bands in this embodiment is M=800, 0000), and the mapping granularity is the sub-block size.

It is assumed that the loads A to E respectively need 2, 4, 3, 1, 2 disks in parallel, and the numbers thereafter are the time period number (1 to 16) of the load duration, as shown in Figure 4, A2 indicates that the load A is in the period 2 Run; the duration of the load can vary.

Load A requires two disks (excluding the disk where the check data is located) in parallel, that is, concurrently writes data to disk 0 and disk 1, for three time periods, namely, time period 1, time period 2, and time period 3;

Load B requires 4 disks (excluding the disk where the check data is located) in parallel, that is, concurrently writes data to disk 0, disk 1, disk 2, and disk 3 for 3 time periods, that is, time period 4, time period 5, time period 6;

Load C requires 3 disks (excluding the disk where the check data is located) in parallel, that is, concurrently writes data to disk 2, disk 3, and disk 0 for 3 time periods, that is, time period 7, time period 8, time Paragraph 9;

Load D requires 1 disk (not including the disk where the parity data is located) in parallel for 5 periods. In time 10, time period 11, time period 12, data is written to disk 0; data is written to disk 1 during time period 13, time period 14.

The load E needs two disks (excluding the disk where the check data is located) in parallel, that is, concurrently writes data to the disk 1, the disk 2, and lasts for two time periods, that is, the time period 15 and the time period 16.

The data is preferentially written to the current working disk. When the current working disk can meet the performance requirements, it does not need to access the standby disk, and has good local parallelism and dynamically allocates storage space with appropriate parallelism. When the write load is minimum (such as load D), only write data to 1 disk; when the write load is maximum (such as load B), write data to 4 disks concurrently. DPPDL provides large elastic parallelism to meet the performance needs of different loads, and has very High energy efficiency.

3, access to competition to avoid

DPPDL has access competition problems when using the above dynamic mapping mechanism to allocate and manage storage space. When concurrently accessing data sub-blocks from two stripes, it may be necessary to access a certain disk concurrently, causing access competition and performance bottlenecks.

FIG. 5 is a schematic diagram of the access competition generated in the embodiment.

The prerequisites for accessing competition avoidance are:

When k free strips are taken from two strips for mapping, the same disk may be accessed concurrently due to the existence of the parity strip PStrip, causing access competition and performance bottlenecks. Access competition may seriously affect storage performance. Take effective measures to eliminate it.

As can be seen from FIG. 5, when the load C is running in the time period 8 (C8), the data sub-blocks from the strip 0 and the strip 1 are concurrently accessed. Due to the need to produce verification data, it is necessary to access disk 2, disk 3, and disk 4 concurrently in strip 0; in strip 1, concurrent access to disk 0 and disk 3 is required. At this time, the disk 3 needs to be accessed concurrently, and its load is about twice that of the disk 2, the disk 4, and the disk 0, thus becoming a performance bottleneck. There are also access competition issues in time period 7 (C7) and time period 9 (C9).

Further, in order to eliminate the problem of access competition, an access competition avoidance strategy is needed. As shown in FIG. 6, the load C7 needs to concurrently access three data sub-blocks spanning two strips, one selects four data sub-blocks first (at the dotted line in FIG. 6); 2 performs an access competition check, and finds the disk 3 The upper data sub-block (at the dashed box with × in Figure 6) and the check sub-block of strip 1 are all located on the disk 3, which will cause the access of the disk 3 to compete, thus deleting the data sub-block; 3 load C The remaining 3 data sub-blocks are written in parallel (at the dashed box labeled C7 in Figure 6). Finally, three data sub-blocks that do not cause access competition and can be accessed concurrently are obtained.

C8 and C9 use the same method to perform access avoidance. Finally, the storage space mapping for accessing the competition is eliminated, as shown in Figure 7. As can be seen from Figure 7, no sub-blocks (including data sub-blocks and parity sub-blocks) are concurrently accessed on any one disk;

4, performance demand perception

DPPDL needs to sense the performance requirements of the load and then dynamically adjust the number of parallel disks to provide the right performance for higher energy efficiency. This example uses equation (2) to sense the data transmission rate of the load demand, where β is 1.2 and window time T is 5 seconds.

Embodiments of the present disclosure can be implemented as a device that performs the desired configuration using any suitable hardware, firmware, software, or any combination thereof. FIG. 8 schematically illustrates an exemplary apparatus 1300 that can be used to implement various embodiments described in this application.

For one embodiment, FIG. 8 illustrates an exemplary apparatus 1300 having one or more processors 1302, a control module (chipset) 1304 coupled to at least one of the processor(s) 1302. a memory 1306 coupled to the control module 1304, a non-volatile memory (NVM)/storage device 1308 coupled to the control module 1304, one or more input/output devices 1310 coupled to the control module 1304, and The network interface 1312 is coupled to the control module 1306.

Processor 1302 can include one or more single or multi-core processors, and processor 1302 can comprise any combination of general purpose or special purpose processors (eg, graphics processors, application processors, baseband processors, etc.). In some embodiments, the device 1300 can be used as a server or the like of the transcoding terminal described in the embodiment of the present application.

In some embodiments, apparatus 1300 can include one or more computer readable media (eg, memory 1306 or NVM/storage device 1308) having instructions 1314 and, in conjunction with the one or more computer readable media, configured to The one or more processors 1302 that execute the instructions 1314 to implement the modules to perform the actions described in this disclosure.

For one embodiment, control module 1304 can include any suitable interface controller to provide any suitable device or component to at least one of processor(s) 1302 and/or any suitable device or component in communication with control module 1304. Interface.

Control module 1304 can include a memory controller module to provide an interface to memory 1306. The memory controller module can be a hardware module, a software module, and/or a firmware module.

Memory 1306 can be used, for example, to load and store data and/or instructions 1314 for device 1300. For one embodiment, memory 1306 can include any suitable volatile memory, such as a suitable DRAM. In some embodiments, memory 1306 can include double data rate type quad synchronous dynamic random access memory (DDR4 SDRAM).

For one embodiment, control module 1304 can include one or more input/output controllers to provide an interface to NVM/storage device 1308 and input/output device(s) 1310.

For example, NVM/storage device 1308 can be used to store data and/or instructions 1314. NVM/storage device 1308 may comprise any suitable non-volatile memory (eg, flash memory) and/or may include any suitable non-volatile storage device(s) (eg, one or more hard disk drives ( HDD), one or more compact disc (CD) drives and/or one or more digital versatile disc (DVD) drives).

NVM/storage device 1308 can include a storage resource physically part of a device on which device 1300 is installed, or it can be accessed by the device without necessarily being part of the device. For example, the NVM/storage device 1308 can be accessed via the network via the input/output device(s) 1310.

The input/output device(s) 1310 can provide an interface to the device 1300 to communicate with any other suitable device, and the input/output device 1310 can include a communication component, an audio component, a sensor component, and the like. Network connection Port 1312 can provide an interface for device 1300 to communicate over one or more networks, and device 1300 can interact with one or more components of the wireless network in accordance with any of one or more wireless network standards and/or protocols. Wireless communication is performed, such as accessing a wireless network based on a communication standard, such as WiFi, 2G or 3G, or a combination thereof for wireless communication.

For one embodiment, at least one of the processor(s) 1302 can be packaged with the logic of one or more controllers (eg, memory controller modules) of the control module 1304. For one embodiment, at least one of the processor(s) 1302 can be packaged with the logic of one or more controllers of the control module 1304 to form a system in package (SiP). For one embodiment, at least one of the processor(s) 1302 can be integrated on the same mold as the logic of one or more controllers of the control module 1304. For one embodiment, at least one of the processor(s) 1302 can be integrated with the logic of one or more controllers of the control module 1304 on the same mold to form a system on a chip (SoC).

In various embodiments, device 1300 can be, but is not limited to, a terminal device such as a server, desktop computing device, or mobile computing device (eg, a laptop computing device, a handheld computing device, a tablet, a netbook, etc.). In various embodiments, device 1300 can have more or fewer components and/or different architectures. For example, in some embodiments, device 1300 includes one or more cameras, a keyboard, a liquid crystal display (LCD) screen (including a touch screen display), a non-volatile memory port, multiple antennas, a graphics chip, an application specific integrated circuit ( ASIC) and speakers.

The above is only a preferred embodiment of the present invention, and it should be noted that those skilled in the art can make some improvements or carry out some of the technical features without departing from the principles of the present invention. These modifications and substitutions are also considered to be within the scope of the invention.

Claims (9)

A dynamic local parallel data layout method for continuous data storage, which is specifically implemented by the following technical solutions: Including stripe partitioning, storage space dynamic mapping, access competition avoidance, and performance demand awareness; firstly, the performance requirements of the storage application are obtained through performance requirement perception, and then the storage space dynamic mapping mechanism is executed, and the storage with the appropriate hard disk parallelism is dynamically allocated according to the performance requirement. Space, and finally optimize the storage space dynamic mapping mechanism by accessing the competition avoidance; Among them, storage space dynamic mapping is the core, performance requirement perception is the basis of storage space dynamic mapping, stripe partitioning is the premise of storage space dynamic mapping, and access competition avoidance is the optimization and completeness of storage space dynamic mapping. The method of claim 1 further characterized in that said striping is divided by: step 1.1: dividing each hard disk in each of the N hard disks into 1×N storage blocks; wherein, 1 is greater than or equal to 1 , N is greater than or equal to 3; Step 1.2: Each data block and the check block in step 1.1 are M equal-sized sub-blocks, and each sub-block includes a plurality of consecutive storage areas, which are respectively called a data sub-block strip and a parity sub-block PStrip; In step 1.3, the sub-blocks in the strip with the same start address in each strip form a sub-strip stripe, and then the strip in the sub-strip is XORed to generate a PStrip in the sub-strip. The method of claim 2 further characterized in that In step 1.1, the N storage blocks with the same starting address in each hard disk form a stripe, which constitutes 1×N strips; each stripe includes 1 check block and N-1 data blocks; Wherein, the check block in the strip i is located in the hard disk N-1-j; if j+v<N-1, the vth data block is located on the hard disk v, otherwise it is located on the hard disk v+1, wherein 0≤i <(1×N), j=i MOD N, 0≤v<N-1. The method of claim 2 further characterized in that In step 1.3, each strip includes M sub-bands of the same size; the parity sub-block PStrip m of the strip stripe stripe is generated by X X of its N-1 data sub-blocks, m m; Then the generation method is:

The method of claim 1 further characterized in that: the operation idea of the dynamic mapping of the storage space is: The disk array storage space is allocated and managed by the dynamic mapping mechanism of the logical block address and the physical block address, and the write data received by the disk array layer can be dynamically mapped to different numbers of hard disks; that is, according to the performance requirement parameters of the load k, dynamically allocate storage space with k hard disk parallelism, that is, k needs to write data concurrently The number of hard disks does not include the hard disk where the verification data of the written data is located; when the load is minimum, only the data is mapped to a certain hard disk, and only the hard disk is written; when the load is maximum, the data is not included in the verification data. On the remaining hard disks of the hard disk, write data to the remaining hard disks of the hard disk that does not include the check data. The storage space is dynamically mapped, and the specific steps are: Step (1) Selecting the stripe with the largest free strip as the CurStripe in CurBank; The free strip is an unmapped strip; the strip list is a one-way circular list consisting of all strips, CurBank is the currently mapped strip, and the initial value is strip 0; CurStripe is in CurBank. The route to be mapped; Step (2) If the number of free strips in CurStripe is 0, indicating that CurStripe has no free strip mappable, go to step (3), otherwise go to step (5); Step (3) determines whether NextBank has a free strip mappable. If there is no free strip mappable, delete the stored data on NextBank and perform storage space recovery; wherein NextBank is the next stripe to be mapped, and the CurBank number is Neighbor, the initial value is strip 1; Step (4) takes NextBank as CurBank and reacquires CurStripe, and then moves NextBank back; Step (5) If the number of free strips in CurStripe is not less than k, then sequentially extract k strips from CurStripe, go to step (7), otherwise go to step (6); Step (6) First take all free strips from CurStripe, and then take the remaining free strips from NextStripe to form k free strips. If NextStripe does not have enough free strips, delete the stored data on NextBank and recycle the storage space. And re-acquire NextStripe; where NextStripe is the Stripe that can be mapped in NextBank; Step (7) obtains k free strips, performs storage space mapping, maps the logical address space to a physical address space having k hard disks parallelism, and records the mapping relationship in the mapping table; Determine the offset of the disk and disk in the strip according to the strip, the sub-strip, and the number in the sub-strip where the strip is located, and record it in the mapping table. When reading, obtain data on the disk according to the mapping table. The location; the mapping table is an important part of the metadata, stored at the end of each working disk, with a version number, the version number is from small to large, and the disk array is loaded the most when the power is restored. Numbered version. The method of claim 1 further characterized in that said accessing competition avoidance comprises the following steps: Step 1) When selecting a strip spanning 2 strips for storage space mapping, first take all free strips from CurStripe, and then take the remaining free strips from NextStripe to form k+1 free strips together, if NextStripe is not enough. Free Strip, delete the stored data on NextBank, reclaim storage space, and regain NextStripe; Step 2) Perform an access competition check. If there is no access competition or the end strip causes the access competition, the last strip is deleted; otherwise, the strip causing the access competition is deleted; finally, k strips that do not cause the access competition and can be concurrently accessed are obtained; The access competition check refers to whether two sub-blocks of the same hard disk are concurrently accessed. The method of claim 1 further characterized in that The performance requirement is perceived as: Continuous data storage applications require a stable data transfer rate, so the data transfer rate is used as a performance requirement indicator; The data transmission rate requirement is specifically: Step A. Counting the history information of the disk array layer I/O request queue; Step B. Perform analysis and prediction; For continuous data storage applications, the fluctuation period or burst time of the load is large, and the data transmission rate of the load demand can be perceived according to the average data transmission rate in the time window T, and the time window is recorded with rn=(ta, pos, len). The nth I/O request in T; where ta, pos, and len are the arrival time, the starting logical address, and the request length of the request rn, respectively, and rn.len represents the request length len of rn; The data transfer rate for perceived load demand is expressed as:

Where num is the number of I/Os coming in the time window T; β is the coefficient of performance, which can be between 1.2 and 1.5; 5s<T<15s; Representing the length summation of num I/O requests in the time window T; Wherein, the I/O request rn in formula (2) comes from the request queue of the RAID layer; After the data transmission rate of the load demand is sensed, the number of hard disks that need to be concurrently written data is determined according to the data transmission rate that can be provided by different hard disk parallelism in the actual application scenario. A dynamic local parallel data layout device for continuous data storage, comprising: One or more processors; and One or more machine-readable media having instructions stored thereon, when executed by the one or more processors, cause the apparatus to perform the method of one or more of claims 1-7. One or more machine-readable medium having stored thereon instructions that, when executed by one or more processors, cause the apparatus to perform the method of one or more of claims 1-7.

Images