CN1949761B - A data synchronization method and its differential encoding method - Google Patents

Abstract

The invention relates to a data synchronization method, which is used for data synchronization between a data synchronization center and a synchronization terminal; it includes steps: the data synchronization center and the synchronization terminal negotiate to start differential encoding synchronization; the data synchronization center compares the data files since the last synchronization The data synchronization center sends the coded string and the newly generated latest synchronization serial number to the synchronization terminal; after receiving the synchronization information sent by the data synchronization center, the synchronization terminal decodes the aforementioned coded string, and Set the data file obtained by the last synchronization according to the decoding result; when the data synchronization is completed, the synchronization terminal saves the aforementioned latest synchronization serial number. In the present invention, after the data synchronization center and the synchronization terminal start the data synchronization process through negotiation, no further negotiation is required during the synchronization process, so the time overhead of the negotiation can be reduced, and the synchronization terminal does not need to perform verification operations, which can improve work efficiency.

Description

A data synchronization method and its differential encoding method

technical field

The invention relates to electronic data processing technology, in particular to a data synchronization method and a differential encoding method thereof.

Background technique

With the development of information technology, various electronic data processing systems and networks are increasingly widely used. In many Internet value-added services, in order to enhance communication between users and enhance user experience, many services and application servers need to sense user status information. In some other fields, such as e-commerce search and other fields, it is also necessary to sense the user's online status and provide search filtering functions.

In order to improve the efficiency of processing user status information, it is necessary to synchronize the user status data from the status data center (also called the data synchronization center) to each service server (also called the synchronization terminal) that accepts the user status data middle.

Therefore, it is necessary to design and implement some kind of data synchronization scheme to efficiently synchronize these frequently updated state data to each service server without increasing the load of the service server.

In the prior art, there are some data synchronization methods. At present, more general and efficient data synchronization schemes are generally based on the verification algorithm of data blocks between the synchronization center and the synchronization terminal, such as the more popular remote data synchronization tool Rsync, which belongs to the incremental synchronization method.

The working principle of the data synchronization method based on the verification algorithm is that the synchronization center generates a check code Checksum for each fixed-size data block (Chunk) in the file for each file in the data directory to be synchronized. Uniquely identify the data of a data block in the file; then send it to the synchronization terminal; after the synchronization terminal receives the information, it first generates a checksum Checksum' for the data block of the corresponding file, and compares the generated checksum Checksum' with the synchronization center The checksum Checksum sent is checked; if the checksum is consistent, the data in the data block is consistent, and the synchronization center is notified that data synchronization is not required; if the checksums at both ends are inconsistent, the synchronization terminal sends a synchronization request to the synchronization Center, the synchronization center sends data to the synchronization terminal. In this way, the check code is checked and synchronized block by block until the entire file is processed.

Please refer to FIG. 1 , which is a flowchart of a data synchronization method in the prior art for data synchronization.

The synchronization center generates a check code Checksum1 for the data block Chunk1 (0, 1000) of the file; sends information Check_update (filename, Chunk1, Checksum1, ...) to the synchronization terminal; , 1000) using the same algorithm to generate the check code Checksum1'; then compare Checksum1 and Checksum1'; since the two are consistent, a notification that does not need to be synchronized is sent to the synchronization center, carrying parameters (proto_version, chunkid, oper_type, ...), where proto_version is the protocol version, chunkid is the data block identifier, and oper_type is the operation type (synchronous or not).

Subsequently, the synchronization center generates a check code Checksum2 for the data block Chunk2 (1000, 2000) of the file; sends information Check_update (filename, Chunk2, Checksum2, ...) to the synchronization terminal; (1000, 2000) generates a checksum Checksum2'; then compares Checksum2 and Checksum2'; since the two are inconsistent, a synchronization request is sent to the synchronization center with parameters (proto_version, chunkid, oper_type, ...); the synchronization center sends it to the synchronization terminal Data synchronization message (filename, chunk2, data); the synchronization terminal receives the data and updates the corresponding chunk2; then sends a synchronization success message to the synchronization center.

For Rsync, the verification code is generated using md4. At the beginning, a series of checksum lists are generated for each data block of the file, and then checked one by one.

However, there are defects in this prior art: first, both the data synchronization center and the synchronization terminal need to perform verification calculation and negotiation synchronization on each data block in the file, and the number of times of negotiation depends on the size of the file data block. If the block size is small, more times need to be negotiated, and the time-consuming overhead caused by the negotiation is relatively large; secondly, when the check codes at both ends of the synchronization are inconsistent, even if only 1 bit of data in the data block changes, the synchronization The center also needs to send the entire data block or compress the entire data block to the synchronization terminal, and the data compression coding rate is relatively low.

It can be seen from the above that if the data block is too small, it will lead to an increase in the verification operation and negotiation delay at both ends of the synchronization; if the data block is too large, the data compression rate will be reduced, so it is difficult to find an optimal Data chunking value, making it suitable for all application scenarios.

In the prior art, another method that is widely used in the field of data synchronization is the full synchronization method. After the synchronization center and the synchronization terminal negotiate, a data transmission channel is established and the entire data file to be synchronized is transmitted to the synchronization terminal. Only a few bits of the data file are changed.

The mechanism of the full synchronization method is relatively simple, only one negotiation is required, and there is no time overhead for multiple negotiations and verification operations in the synchronization process. However, since the entire data file is always synchronized, the data compression coding rate is very low, thereby increasing Network I/O and bandwidth consumption of the server.

Contents of the invention

The technical problem to be solved by the present invention is to provide a data synchronization method and a differential coding method thereof, the time overhead of the negotiation and verification operation is small, and the compression coding rate can be relatively high.

For this reason, the technical scheme that the present invention solves technical problem is: provide a kind of data synchronization method, be used for the data synchronization between data synchronization center and synchronization terminal; Described method comprises steps:

11) The data synchronization center negotiates with the synchronization terminal to start differential encoding synchronization; the data synchronization center reads in multiple bytes of the current data file and the data file after the last synchronization and performs an XOR operation. If the XOR result is zero, the statistics The offset value of the data block, if the XOR result is not equal to zero, then calculate the offset value and difference value of the current data block, compress the offset value and difference value of the current data block and add them to the code string;

12) The data synchronization center sends the encoded code string and the newly generated latest synchronization serial number to the synchronization terminal;

13) After the synchronization terminal receives the synchronization information sent by the data synchronization center, it decodes the aforementioned code string to obtain the offset value and difference value of the current data block, and obtains the data of the relative offset value from the data file obtained in the last synchronization Block, and perform XOR operation with the difference value, and then write back to the data file obtained from the last synchronization to obtain the data file to be synchronized;

14) After the data synchronization is completed, the synchronization terminal saves the aforementioned latest synchronization serial number.

Preferably, the negotiation in said step 11) is: the synchronization center and the synchronization terminal carry out the latest synchronization serial number proofreading negotiation; if the latest synchronization serial number is consistent, then start the differential encoding synchronization; if not, then adopt the full synchronization mode to perform data synchronization .

Preferably, the step 11) is periodically initiated by the synchronization center, and the synchronization frequency is configurable.

Preferably, the number of bytes read in the step 11) is configurable; the offset value of the step 11) is the difference between the current data block position and the data block position where the difference characteristic occurred last time; the step 11) The compression algorithm adopted for the compression is a Vint compression algorithm, a zip compression algorithm, or a prefix compression algorithm of discrete binary strings.

Preferably, the decoding in step 13) includes obtaining the offset value and difference value of the current data block; the setting in step 13) includes: obtaining the data block of the corresponding data file according to the offset value in the coded string; An XOR operation is performed on the difference value and the aforementioned data block to obtain an updated data block; the updated data block is written into the data file to obtain a synchronized data file.

In addition, the present invention also provides a differential encoding method, said method comprising the steps of:

81) Multi-byte reading is carried out to the current data file and the data file after the last synchronization and XOR operation is performed;

82) If the XOR result is zero, the offset value of the statistical data block;

83) If the XOR result is not equal to zero, then calculate the offset value and difference value of the current data block;

84) Composing the offset value and difference value of the current data block into an element pair; compressing it and adding it to the coded string.

Preferably, the number of bytes read in the step 81) is configurable; the offset value of the step 83) is the difference between the current data block position and the data block position where the difference characteristic occurred last time; the step 84) The compression algorithm adopted is a Vint compression algorithm, a zip compression algorithm, or a prefix compression algorithm of discrete binary strings.

The method further includes the steps of:

101) Decoding the received code string to obtain the offset value and difference value of the current data block;

102) Obtain the data block of the corresponding data file according to the offset value in the code string;

103) Execute an XOR operation on the difference value and the aforementioned data block to obtain an updated data block;

104) Write the updated data block into the data file to obtain the synchronized data file.

Compared with the prior art, the beneficial effects of the present invention are as follows: firstly, after the data synchronization center and the synchronization terminal start the data synchronization process through negotiation in the present invention, no further negotiation is required in the synchronization process, so the time overhead of the negotiation can be reduced , and the synchronization terminal does not need to perform verification operations, which can improve work efficiency; secondly, due to the use of differential encoding, the difference characteristics of the data file since the last synchronization are encoded, and the data encoding rate is high, which can reduce network I/O and bandwidth usage overhead.

In the preferred solution of the present invention, the data synchronization center and the synchronization terminal only need to negotiate the latest synchronization serial number once, and the time overhead for the negotiation is small.

In addition, on the basis of differential coding, a compression algorithm is applied to achieve compression, and the data compression coding rate is high, thereby further reducing the overhead of network I/O and bandwidth usage.

Description of drawings

Fig. 1 is a flow chart of performing data synchronization by a data synchronization method in the prior art;

Fig. 2 is a flowchart of the data synchronization method of the present invention;

3 is a schematic diagram of differential encoding in an embodiment of the data synchronization method of the present invention;

4 is a schematic diagram of differential decoding in an embodiment of the data synchronization method of the present invention;

Fig. 5 is the work flowchart of the differential encoder in the data synchronization method of the present invention;

Fig. 6 is a working flowchart of the differential decoder in the data synchronization method of the present invention.

Detailed ways

Please refer to FIG. 2 , which is a flow chart of the data synchronization method of the present invention.

In step S211, the synchronization center and the synchronization terminal perform a negotiation on the latest synchronization serial number. If the latest synchronization serial numbers are consistent, go to step S221; if not, go to step S231, and use the full synchronization method to perform data synchronization.

In the present invention, the process of checking and negotiating the latest synchronization serial number can be initiated periodically by the synchronization center, and the synchronization frequency can be configured.

The synchronization center sends a message <file, last_sync_seq> to the synchronization terminal for a specific file, where last_sync_seq is the latest synchronization serial number corresponding to the file file; the synchronization terminal extracts the latest synchronization serial number of the file (data obtained from the last synchronization) stored locally (The serial number of the last synchronization), check it; if it is inconsistent, it means that the synchronization terminal has not obtained the latest synchronized data from the synchronization center, and the synchronization terminal sends a request for data synchronization in a full synchronization mode to the synchronization center <file, full_sync_type>; When the synchronization center receives the request, it sends the data file to be synchronized to the synchronization terminal through the established data channel, and the format is <file, last_sync_seq, full_sync_type, code_string>.

In step S221, if the latest synchronization serial number is consistent, start compression differential encoding synchronization between the synchronization terminal and the data synchronization center.

In step S222, the data synchronization center compresses and encodes the data files and the difference characteristics of the data files since the last synchronization.

In step S223, the data synchronization center sends the compressed coded character string and the newly generated latest synchronization serial number to the synchronization terminal.

Step S224, after receiving the synchronization information sent by the data synchronization center, the synchronization terminal decodes the coded character string, and sets the data file obtained in the last synchronization.

Step S225, when the data synchronization is completed, save the latest synchronization serial number.

In order to facilitate a further understanding of the present invention, the present invention will be described in detail below in conjunction with examples.

Firstly, the data synchronization center and the synchronization terminal perform the latest serial number collation and negotiation. If the latest synchronization serial number is inconsistent, the full synchronization method will be used for data synchronization. If they are consistent, the synchronization terminal notifies the data synchronization center to perform compressed differential encoding synchronization, and the format of the notification can be <file, last_sync_seq, sync_type>.

Secondly, after receiving the notification, the data synchronization center starts the differential compression encoder to compress and encode the data file and the difference characteristics of the data file since the last synchronization, and compare the encoded string after compression with the newly generated latest The synchronization sequence number <last_sync_seq, code_string> is sent to the synchronization terminal. Among them, the purpose of compressing and coding the difference features is to reduce the number of bytes to be transmitted, thereby reducing the overhead of network bandwidth.

Please refer to FIG. 3 , which is a schematic diagram of differential encoding in an embodiment of the data synchronization method of the present invention.

Assuming that the time t of the data file D is D1, and the current time is D2, after passing through the differential encoder (DiffEncoder) 300, the code string code string represented by the difference between the data files D1 and D2 will be obtained.

In this embodiment, when the data synchronization center and the synchronization terminal are synchronizing, the compressed code string (Code String) format is defined as:

Vint {(offset, diff_value) ^<diff_count> }.

Among them, the difference characteristics of the data files D1 and D2 are represented by element pairs (offset, diff_value), diff_count is the number of difference element pairs, offset is the data block offset relative to the last element pair representing the difference characteristics, and diff_value is the difference value.

The difference value is obtained by XOR operation between the data file and the corresponding data block of the last synchronization data file.

Of course, those skilled in the art may also directly use the position of the byte to represent the position of the data block (that is, the offset relative to the file header).

It is preferable to use a relative offset, which is beneficial to compression. Using the compression algorithm mentioned in this embodiment, generally only one byte can be used for representation. And if it is expressed directly by the position of the byte, multiple bytes will be required.

The Vint compression algorithm adopted in this embodiment is a simple and highly efficient shaping compression algorithm, and its main idea is to use one byte for every 7 bits for representation. Of course, those skilled in the art can understand that other compression algorithms can also be used for compression. For example, the zip compression algorithm, or the prefix compression algorithm of discrete binary strings, etc.

See Table 1 for an example of compression.

Table 1 value First byte Second byte Third byte

0 00000000 1 00000001 2 00000010 … 127 01111111 128 10000000 00000001 129 10000001 00000001 130 10000010 00000001 … 16,383 11111111 01111111 16,384 10000000 10000000 00000001 16,385 10000001 10000000 00000001 …

Table 1 lists the correspondence of some values before and after compression, and clearly shows the compression characteristics. Among them, Value is the value to be compressed, and first byte, second byte, and third byte respectively represent the value of each byte after compression.

Again, after receiving the synchronization information <last_sync_seq, code_string> sent by the data synchronization center, the synchronization terminal starts the differential compression decoder to decode the code_string, obtains multiple binary groups (offset, diff_value), and sets the data obtained from the last synchronization document. When the data synchronization is completed, set the latest synchronization serial number to the data synchronization registration table.

Please refer to FIG. 4 , which is a schematic diagram of differential decoding in an embodiment of the data synchronization method of the present invention.

Start the differential compression decoder (Diff_Decoder) 400 to decode code_string to obtain multiple binary groups (offset, diff_value); for each (offset, diff_value), obtain the data relative to offset from the data file D1 that was synchronized last time block, and perform XOR operation with diff_value, and then write back to the D1 data file to obtain the data file D2 to be synchronized.

Please refer to FIG. 5 , which is a working flowchart of the differential encoder in the data synchronization method of the present invention.

Step S510, when the differential encoder performs encoding, multi-byte reading is performed on the data files D1 and D2 and an XOR operation is performed (the number of bytes to be read is an adjustable parameter of the differential encoder, and the default is 32 bits).

Step S520, if the XOR result is 0, calculate the offset value.

Step S530, if the XOR result is not equal to 0, calculate its offset and diff_value. Compose offset and diff_value into an element pair (offset, diff_value).

Among them, the offset and diff_value values can be calculated in this way:

offset=current data block position - the data block position where the difference characteristic occurred last time;

If data_d1 and data_d2 represent the data of corresponding data blocks (chunks) of data files D1 and D2 respectively, then diff_value=data_d1^data_d1.

Step S540, use a compression algorithm to compress the offset and diff_value values, and add them to the encoding queue.

Please refer to FIG. 6 , which is a working flowchart of the differential decoder in the data synchronization method of the present invention.

Step S610, when the differential decoder performs decoding, obtain the coded string generated by the differential encoder.

Step S620, obtain the corresponding data block of the data file D1 according to the offset in the code string.

Step S630, XOR operation is performed on the diff_value value and the aforementioned data block to obtain an updated data block.

Step S640, write it into the data file D1 to obtain the data file D2 to be synchronized.

Those skilled in the art understand that, in the present invention, the differential encoder/decoder adopts a manner of encoding and compressing while reading or decoding while reading, and the efficiency is relatively high.

Applications

Applying the technical scheme of the invention to synchronize data between the user state data center and each application server (synchronization terminal), the effect is relatively good.

The 140M user status data needs to be synchronized every 5s between the status synchronization center and the synchronization terminal, and the synchronization update is relatively frequent. There are about 25,000 user status changes within 5 seconds (online, offline or stealth, each status uses 2bit express).

The encoded data processed by the differential encoder with compression characteristics described in the technical solution of the present invention is only 65K, and the encoding efficiency is at the ms level, and the decoding synchronization speed of the synchronization terminal is even more at the microsecond level. The entire synchronization process starts from the synchronization request initiated by the data synchronization center, and the data synchronization is completed after the synchronization terminal receives the response. The time-consuming is at the ms level and the efficiency is extremely high. And because the amount of data to be synchronized is greatly compressed, the CPU and intranet bandwidth overhead at both ends are saved.

In summary, the present invention provides a method for efficiently synchronizing data between the data synchronization center and the synchronization terminal. This technical solution has a sparse characteristic for the difference between data files before and after synchronization, and the synchronization center needs to perform frequent quasi-real-time synchronization with the synchronization terminal. The application scenario works well.

The method of the invention improves the synchronization mechanism of the synchronization center and the synchronization terminal.

At the same time, the realization of the differential encoding/decoding method with compression characteristics can encode and compress the difference characteristics of the data file since the last synchronization, and the other side can obtain the data to be synchronized after obtaining the encoded string and decoding it.

The above description is only a preferred embodiment of the present invention, it should be pointed out that for those skilled in the art, without departing from the principle of the present invention, some improvements and modifications can also be made, and these improvements and modifications are also It should be regarded as the protection scope of the present invention.

Claims (8)

1. A data synchronization method, used for data synchronization between a data synchronization center and a synchronization terminal; it is characterized in that, comprising steps: 11) The data synchronization center negotiates with the synchronization terminal to start differential encoding synchronization; the data synchronization center reads in multiple bytes of the current data file and the data file after the last synchronization and performs an XOR operation. If the XOR result is zero, the statistics The offset value of the data block, if the XOR result is not equal to zero, then calculate the offset value and difference value of the current data block, compress the offset value and difference value of the current data block and add them to the code string; 12) The data synchronization center sends the encoded code string and the newly generated latest synchronization serial number to the synchronization terminal; 13) After the synchronization terminal receives the synchronization information sent by the data synchronization center, it decodes the aforementioned code string to obtain the offset value and difference value of the current data block, and obtains the data of the relative offset value from the data file obtained in the last synchronization Block, and perform XOR operation with the difference value, and then write back to the data file obtained from the last synchronization to obtain the data file to be synchronized; 14) After the data synchronization is completed, the synchronization terminal saves the aforementioned latest synchronization serial number. 2. The data synchronization method according to claim 1, characterized in that, the negotiation in the step 11) is: the synchronization center and the synchronization terminal carry out the latest synchronization serial number proofreading negotiation, if the latest synchronization serial number is consistent, then start the difference Encoding synchronization; if inconsistent, data synchronization will be performed in full synchronization mode. 3. The data synchronization method according to claim 2, wherein the step 11) is regularly initiated by the synchronization center, and the synchronization frequency is configurable. 4. The data synchronization method according to claim 1, wherein: The number of bytes read in the step 11) is configurable; The offset value of the step 11) is the difference between the current data block position and the data block position where the difference characteristic occurred last time; The compression algorithm used in the step 11) is Vint compression algorithm, zip compression algorithm, or prefix compression algorithm of discrete binary strings. 5. The data synchronization method according to claim 1, wherein: The decoding in step 13) includes obtaining the offset value and the difference value of the current data block; The setting of step 13) includes: obtaining the data block of the corresponding data file according to the offset value in the code string; performing an XOR operation on the difference value and the aforementioned data block to obtain an updated data block; The block is written into the data file, and the synchronized data file is obtained. 6. A differential encoding method, characterized in that, comprising steps: 81) Multi-byte reading is carried out to the current data file and the data file after the last synchronization and XOR operation is performed; 82) If the XOR result is zero, the offset value of the statistical data block; 83) If the XOR result is not equal to zero, then calculate the offset value and difference value of the current data block; 84) Composing the offset value and difference value of the current data block into an element pair; compressing it and adding it to the coded string. 7. differential coding method according to claim 6, is characterized in that, The number of bytes read in in step 81) is configurable; The offset value of the step 83) is the difference between the current data block position and the data block position where the difference characteristic occurred last time; The compression algorithm adopted in the step 84) is a Vint compression algorithm, a zip compression algorithm, or a prefix compression algorithm of discrete binary strings. 8. The differential encoding method according to claim 6, characterized in that the method further comprises the steps of: 101) Decoding the received code string to obtain the offset value and difference value of the current data block; 102) Obtain the data block of the corresponding data file according to the offset value in the code string; 103) Execute an XOR operation on the difference value and the aforementioned data block to obtain an updated data block; 104) Write the updated data block into the data file to obtain the synchronized data file.

Images