CN107103055B - Hourglass method for intensive program for memory updating - Google Patents

Abstract

The invention discloses a Hourglass and Piggyback algorithm oriented to a memory update intensive program, the excellent performance of the Hourglass and Piggyback algorithm is derived from a pointer exchange technology between an updater thread and a dumper thread, and a large amount of data copying can be avoided. It periodically takes place the role swap of the updater and dumper threads, which can be periodically reused endlessly, swapping up and down roles once the upper part is empty. Less memory and substantially no jitter delay effects can be achieved. It is one of the lightweight checkpoint algorithms, Hourglass combines the two currently best algorithms, zig-zag and pingpong, to take advantage of the two advantageous pointer swapping and bit flags. The Piggyback algorithm improves performance by providing a full snapshot that can support real-time olap and oltp applications. The method has the advantages of smaller memory occupation, full snapshot overhead, smaller delay and more uniform delay.

Description

Hourglass method for intensive program for memory updating

Technical Field

The invention relates to the technical field of backup recovery of a memory database, in particular to a Hourglass method oriented to a memory update intensive program, which belongs to a lightweight checkpoint algorithm.

Background

One large class of applications involves data intensive update operations, most of which seek transient response, high throughput, and highly available performance. For example, at the end of the 20 th century, the performance of the back-office Electronic Trading System (ETS) of large stock exchanges, such as the shanghai stock exchange, has reached 100000 transactions per second and can guarantee zero loss of transactions at the time of disaster recovery. There are also more examples, such as large online games (MMOS) and e-commerce systems that are sufficient to support black Friday performance scenarios. These data update intensive programs are typically implemented using memory computing techniques. One strategy is to employ an in-memory database, which can provide faster and predictable performance advantages over disk databases (since data is directly accessible in memory).

High availability of in-memory databases relies on a more sophisticated recovery subsystem. Since conventional recovery mechanisms for disk databases (DRDBs) are not specifically directed to update-intensive programs, overall system performance may be limited by the recovery system if the previous recovery system is employed directly without any modification. Based on this, we believe that the recovery system of the in-memory database, especially the transaction log and checkpoint subsystems, needs to be redesigned.

For the transaction log, due to the high throughput performance of the memory database, more logs are generated in a unit time, so that the cost of IO is increased, and in order to prevent the transaction log from becoming the bottleneck of system performance, many relevant optimization methods are proposed, such as accelerating the IO performance (by means of novel hardware), reducing the IO frequency (transaction group commit strategy), or reducing the IO size (log compression, log rewriting). This part of the study is currently relatively thorough.

For the checkpoint technique, we can achieve the goal of reducing the log by periodically generating snapshots and truncating the log. Clearly, the more frequent and faster checkpoints are generated the better, with the benefit that the amount of logs generated between checkpoints is relatively smaller. However, the overhead of performing checkpoints so frequently is not negligible. First, the increased latency due to the execution of checkpoints can have a large impact on system throughput and response time. Second, unlike disk checkpoints, memory checkpoints require that a fully consistent copy of data be maintained in memory before the data is flushed to disk. Improper processing can result in significant jitter in the delay and even system stall.

Consistency checkpoint algorithm under serial transaction model. The difficulty in requiring a checkpoint algorithm to backup consistent data without excessive throughput loss is how to generate consistent memory snapshots in memory as quickly as possible and then asynchronously backup the data to disk. The most straightforward algorithm is

Snapshot (ns), which creates a copy of the data by locking all the data. However, NS utilizes a coarse-grained lock operation, which results in a very noticeable latency jitter. Another algorithm, Copy On Update (COU), takes the form of a shadow Copy, at the time of the first data write. The snapshot generation phase does not cause an oversized card shell of the system, but requires memory copy operation and fine-grained lock operation for each data access. Both the NS and the COU need to maintain a consistent state with lock operations. In order to ensure that the system has low delay and no jamming phenomenon, the algorithm design of lock free is significant.

To our knowledge, only a few studies have involved the consistency checkpoint algorithm for lock free, and the typical work is that Tuan cao proposed two checkpoint algorithms for wait free, Zigzag and Pingpong. The main idea is to avoid the use of locks by using extra memory and bit arrays and to eliminate the delay jitter. Unfortunately, Zigzag still has severe jitter when the amount of data is large. The Pingpong algorithm requires 3 to 4 times the memory footprint and relies on a redundant write. Although large capacity high speed physical memory has been abundant, the use of memory as little as possible is reasonable from both a price and energy perspective, especially for update-intensive programs. Therefore, it is necessary to design a lightweight lock-free memory checkpoint algorithm by comprehensively considering memory overhead and performance (low latency, uniform latency distribution, fast recovery).

Disclosure of Invention

Aiming at the defects of the prior art, the invention provides a Hourglass and Piggyback algorithm for intensive memory update programs, which belong to a lightweight check point algorithm. Can solve the defects of the prior art and has better high availability.

In order to achieve the purpose, the technical scheme adopted by the invention is as follows:

a Hourglass algorithm for a memory update intensive program, comprising the steps of:

s1, assuming that the update-intensive program will periodically reach a consistent state, describing the characteristic of the transaction that periodically reaches the consistent state by the concept of tick 1/T, where T is the duration of tick; one tick represents the interval between the time points at which the dataset reaches the coherency state twice;

s2, at time t, D is assumed to be the state of data D_tIndicating that D is a data set in the memory; one checkpoint C being responsible for maintenance D_tA compact data snapshot to the disk device, but guaranteed to be at t + t_cBefore the moment of time, where t_cIs the execution cycle of the checkpoint;

s3, abstracting the data D into a continuous memory space, and organizing the data D according to the form of a memory page; any additional memory area for performing checkpointing

Is expressed in terms of form;

s4, the recovery system of the simulated IMDB is two concurrent threads of an Updater thread and a Dumper thread, D and

accessed by two threads of different algorithms;

s5, dividing the periodic check into a preparation stage and a dump stage; d_tThe actual generation time of the checkpoint is at the end time of each dump phase, t_pAnd t_dRespectively representing the duration of the preamble and dump phases; total time overhead t to perform checkpoints_o＝t_p+t_dTime t of check point period is not exceeded_c＝t_p+k(k∈N⁺) That is to say t_o≤tc；

S6, using pingpong pointer exchange technique and zigzag bit check technique to obtain a uniform access delay and ensure only two memories, data sets D and shadow copy numbersAccording to

Each data set is accompanied by a bit array

And

the value of (D) represents D [ i]Whether it is updated in the current checkpoint period and whether it needs to be backed up in the next checkpoint period;

the value of (D) represents D [ i]Whether it needs to be persisted within the current checkpoint period;

s7, in a checking period, for updated data set (D or

) Indicated by the "pU" pointer, and the "pD" pointer, which is used for backup, is used for another data set;

s8, the pointer exchange occurs in the starting period of each check point; to ensure that the update thread does not read dirty data, additional flag bit data is provided

For indicating which data is used to read the most recent data

I.e. from D [ i ]]Read data, otherwise from

And reading the data.

As an improvement to the above solution, the Updater thread represents an update-intensive program, and the Dumper thread is responsible for periodic execution checkpoints.

The invention also provides a memory update intensive program oriented Piggyback algorithm, which comprises the following steps:

s1, pointing the pointers pU and pD to D and pD respectively

The dump thread copies the data pointed by the persistent pD in batch, and the Piggyback maintains an array of one bit and two bits

There are three states, {0, 1, 2}, which represent from which data we need to read the latest data;

updater read data page i is a line from any one data set because

When D is present_b[i]1, updater from D [ i]The data page i is read. When D is present_b[i]2, updater from

Reading a data page;

pU and pD point to D and pD, respectively

Initialized bits are all 0 s, and in the first checkpoint cycle, assume that the Updater thread updated numbersAccording to page D [0]，D[2]And D [3 ]]The corresponding flag bit is set to 1;

s2, starting at the second check point, exchanging the pointers pU and pD, and backing up the data of D pointed by the current pD in a full-scale mode; at the same time, the user can select the desired position,

receiving update operation of updater; around the second checkpointPeriod of timeAt the end of the time, the data in D is the current latest state,

s3, define additional Dumper: : writetonline () function. And the data of the corresponding position in the pU is covered by the latest data in the latest state of the pD.

Compared with the prior art, the invention has the advantages and positive effects that:

the Hourglass and Piggyback algorithms for the memory update-intensive programs of the present invention derive their excellent performance from pointer swapping techniques between the updater and dumper threads, which can avoid large data copies. It periodically takes the role of the updater and dumper threads to swap, as if it were an hourglass, and can be periodically reused endlessly, swapping up and down roles once the upper part is empty. Less memory and substantially no jitter delay effects can be achieved.

Both of the above algorithms belong to one of the lightweight checkpoint algorithms, and Hourglass combines the two best algorithms at present, namely zigzag and pingpong, thereby utilizing the two advantageous pointer exchange and bit flag. The Piggyback algorithm improves performance by providing a full snapshot that can support real-time olap and oltp applications. The method has the advantages of smaller memory occupation, full snapshot overhead, smaller delay and more uniform delay.

Detailed Description

The technical solutions in the embodiments of the present invention will be clearly and completely described below with reference to the embodiments of the present invention, and it is obvious that the described embodiments are only a part of the embodiments of the present invention, and not all of the embodiments. All other embodiments, which can be derived from the embodiments of the present invention by a person skilled in the art without any creative effort, should be included in the protection scope of the present invention.

The Hourglass algorithm facing the intensive program with memory updating comprises the following steps:

s1, dataset D and shadow copy data

Each data set is accompanied by a bit array

And

the value of (D) represents D [ i]Whether it is updated in the current checkpoint period and whether it needs to be backed up in the next checkpoint period;

the value of (D) represents D [ i]Whether it needs to be persisted within the current checkpoint period;

s2, in the first checking period, the data set D for updating is indicated by "pU" pointer, and the other data set for backup is indicated by "pD" pointer. Meanwhile, when update updates data, the update needs to be set

The data of (1). Dumper thread direct backup

The data in (c).

S3, the pointer exchange occurs in the starting period of the next check point; to ensure that the update thread does not read dirty data, additional flag bit data is provided

For indicating which data is used to read the most recent data

I.e. from D [ i ]]Read data, otherwise from

And reading the data.

As an improvement on the above technical solution, the present invention further provides a Piggyback algorithm for a memory update intensive program, including the following steps:

s1, pointing the pointers pU and pD to D and pD respectively

The dump thread copies the data pointed by the persistent pD in batch, and the Piggyback maintains an array of one bit and two bits

There are three states, {0, 1, 2}, which represent from which data we need to read the latest data;

updater read data page i is a line from any one data set because

When D is present_b[i]1, updater from D [ i]The data page i is read. When D is present_b[i]2, updater from

Reading a data page;

pU and pD point to D and pD, respectively

The initialized bits are all 0 s, and in the first checkpoint cycle, assume that the Updater thread updated data page D [0 ]]，D[2]And D [3 ]]The corresponding flag bit is set to 1;

s2, starting at the second check point, exchanging the pointers pU and pD, and backing up the data of D pointed by the current pD in a full-scale mode; at the same time, the user can select the desired position,

receiving update operation of updater; around the second checkpointPeriod of timeAt the end time, the data in D are all in the current latest state;

s3, define additional Dumper: : a writetonline () function; for correcting the data in the pU, the latest data state is guaranteed at the beginning of the checkpoint.

Compared with the prior art, the invention has the advantages and positive effects that:

the Hourglass and Piggyback algorithms for the memory update-intensive programs of the present invention derive their excellent performance from pointer swapping techniques between the updater and dumper threads, which can avoid large data copies. It periodically takes the role of the updater and dumper threads to swap, as if it were an hourglass, and can be periodically reused endlessly, swapping up and down roles once the upper part is empty. Less memory and substantially no jitter delay effects can be achieved.

Both of the above algorithms belong to one of the lightweight checkpoint algorithms, and Hourglass combines the two best algorithms at present, zigzag and Ping-Pong, thereby utilizing the two advantageous pointer swapping and bit flag. The Piggyback algorithm improves performance by providing a full snapshot that can support real-time olap and oltp applications. The method has the advantages of smaller memory occupation, full snapshot overhead, smaller delay and more uniform delay.

The foregoing shows and describes the general principles, essential features, and advantages of the invention. It will be understood by those skilled in the art that the present invention is not limited to the embodiments described above, which are given by way of illustration of the principles of the present invention, and that various changes and modifications may be made without departing from the spirit and scope of the invention as defined by the appended claims. The scope of the invention is defined by the appended claims and equivalents thereof.

Claims (1)

1. A Hourglass method for intensive memory update programs, which is characterized in that: the method comprises the following steps:

s1, assuming that the update-intensive program will periodically reach a consistent state, describing the characteristic of the transaction that periodically reaches the consistent state by the concept of tick 1/T, where T is the duration of tick; one tick represents the interval between the time points at which the dataset reaches the coherency state twice;

s2, at time t, D is assumed to be the state of data D_tIndicating that D is a data set in the memory; one checkpoint C being responsible for maintenance D_tA compact data snapshot to the disk device, but guaranteed to be at t + t_cBefore the moment of time, where t_cIs the execution cycle of the checkpoint;

s3, abstracting the data D into a continuous memory space, and organizing the data D according to the form of a memory page; d shadow copy data, with

Is expressed in terms of form;

s4, the recovery system of the simulated IMDB is two concurrent threads of an Updater thread and a Dumper thread, D and

accessed by two threads of different algorithms;

s5, dividing the periodic check into a preparation stage and a dump stage; d_tThe actual generation time of the checkpoint is at the end time of each dump phase, t_pAnd t_dRespectively representing the duration of the preamble and dump phases; total time overhead t to perform checkpoints_o＝t_p+t_dTime t of check point period is not exceeded_o＝t_p+ k being that t_o≤t_c；

S6, using the pointer exchange technique of pingpong and the bit check technique of zigzagObtaining a uniform access delay but still ensuring that only two copies of memory, dataset D and shadow copy data are needed

Each data set is accompanied by a bit array

And

the value of (D) represents D [ i]Whether it is updated in the current checkpoint period and whether it needs to be backed up in the next checkpoint period;

the value of (D) represents D [ i]Whether it needs to be persisted within the current checkpoint period;

s7, in a checking period, the data set used for updating is indicated by a 'pU' pointer, and the other data set used for backup is indicated by a 'pD' pointer;

s8, the pointer exchange occurs in the starting period of each check point; to ensure that the update thread does not read dirty data, additional flag bit data is provided

For indicating which data is used to read the most recent data

I.e. from D [ i ]]Read data, otherwise from

And reading the data.