CN104462124B - Data storing platform method for organizing and data storing platform based on linear Hash table - Google Patents

Abstract

The invention discloses a data storage platform organization method and a data storage platform based on a linear hash table, and relates to the field of cloud computing. The present invention expands the structure of the hash table and the address mapping mode. When a new node joins the cluster, the original mapping between the key value and the address remains unchanged, and only the effective number of bits of the address and the length of the hash table are extended. The newly generated address is given to the new node, and the data is gradually migrated while keeping the system running; similarly, when a node leaves the cluster, the original mapping between the key value and the address remains unchanged, only the effective number of bits and Hash table length, and gradually migrate data while keeping the system running. This organization method not only retains the high real-time advantages of organizing cloud clusters through hash tables, but also makes the clusters easy to maintain and expand. The present invention is applicable to all cloud storage platforms, especially service platforms such as billing or flow control that have high real-time requirements and run on memory databases.

Description

Data storage platform organization method and data storage platform based on linear hash table

technical field

The invention relates to the field of cloud computing, in particular to a data storage platform organization method and a data storage platform based on a linear hash table.

Background technique

With the advent of the big data era, the cloud model is the development trend of data storage platforms. The organization method of cloud storage refers to the method of determining which data is stored in which node according to the key value, which can be divided into tree organization method and hash table organization method. Among them, the hash table organization method is suitable for single-record query and modification. The advantage is that the structure is simple and the access speed is fast. The disadvantage is that the cluster is not easy to maintain. Adding and deleting nodes requires stopping the cluster operation and reorganizing the data.

The method of organizing the cloud storage platform through the hash table is as follows:

1) For the sake of simplifying the model, we consider that the data has a unique key value k, and the cloud storage platform has N nodes, numbered from 0 to N-1, and the nodes are equal.

2) The cloud storage platform maintains a hash table with a length of N. Each column of the table points to a node, and maintains a hash function H. The result of H(k) ranges from 0 to N-1. Hash itself is a mature technology, and the existing hash function can do it. Regardless of the distribution of k, the distribution of H(k) is basically uniform.

3) When new data (key value k1) is loaded into the cloud storage platform, the cloud storage platform calculates H(k1), assuming H(k1)=n, then finds node n on the hash table, and The data is stored in node n;

4) When a user requests access to data with a key value of k1 from the cloud storage platform, the cloud storage platform also looks up the hash table according to H(k1)=n, and forwards the request to node n.

FIG. 1 is a schematic diagram of an existing hash table organization principle. As shown in Figure 1, if a new node joins the cluster, the system needs to expand the hash table so that its length reaches N+1, and the address number of the new node is N; replace the hash function with a new hash function H' (k) ranges from 0 to N; migrate data according to the new hash function, for any k, H'(k) is the storage node of the data represented by k. The data migration process involves almost all nodes in the entire cluster, so the cluster service has to be stopped.

The process for a node to leave the cluster is similar to that of joining the cluster above, and the hash function also needs to be replaced. The data migration process also involves almost all nodes in the entire cluster.

From the above analysis, it can be seen that the existing hash table organization method cluster is not easy to maintain. Adding and deleting nodes requires stopping the cluster operation and reorganizing data, which is not suitable for data storage platforms with high real-time requirements.

Contents of the invention

A technical problem to be solved by the embodiments of the present invention is to solve the problem that the cluster existing in the existing hash table organization method is not easy to maintain, and adding and deleting nodes requires stopping the cluster operation and reorganizing data.

According to an aspect of the embodiments of the present invention, a method for organizing a data storage platform based on a linear hash table is proposed, including: for a cluster with N nodes, if a new node joins the cluster, the length of the hash table is extended to N+1, the address number of the new node is recorded as N; part of the data on the node pointed to by the hash table split pointer is migrated to the new node with the address number N; the hash table split pointer is shifted one bit to point to the next Node; update the value of the hash table bit counter Among them, d represents the value of the hash table bit counter, Indicates rounding up.

According to another aspect of the embodiment of the present invention, a method for organizing a data storage platform based on a linear hash table is proposed, including: for a cluster with N+1 nodes, if the address number at the end of the hash table is N When the node leaves the cluster, the split pointer of the hash table moves forward one bit to point to the previous node; the value of the bit counter of the hash table is updated Among them, d represents the value of the hash table bit counter, Indicates rounding up; migrate all data on the node whose address number is N to the node pointed to by the split pointer of the hash table; reduce the length of the hash table to N.

The aforementioned data storage platform organization method also includes: when a user requests access to data with a key value of k, calculate the hash value of k according to H(k)=n, where H represents a hash function, and n represents the calculated hash value; Obtain the value d of the hash table digit counter; intercept the last d digits of n to obtain n'; intercept the last d-1 digits of n to obtain n"; compare the position of the hash table split pointer with the address number n", if the address number After the hash table splits the pointer, the node with n” locates the request to the node with the address number n”, if the node with the address number n” locates the request to the address number n’ before the hash table splits the pointer of nodes.

Wherein, the value range of the hash function is larger than the range of the address numbers of the nodes in the cluster.

According to still another aspect of the embodiments of the present invention, a data storage platform is proposed, including: a node joins a processing unit or/and a node leaves a processing unit; a node joins a processing unit for a cluster whose number of nodes is N, if a new node joins the Cluster, expand the length of the hash table to N+1, record the address number of the new node as N; migrate some data on the node pointed to by the split pointer of the hash table to the new node with the address number N; split the hash table Move the pointer back one bit to point to the next node; update the value of the bit counter in the hash table Among them, d represents the value of the hash table bit counter, Represents rounding up; the node leaves the processing unit. For a cluster with the number of nodes N+1, if the node whose address number is N at the end of the hash table leaves the cluster, the split pointer of the hash table moves forward one bit, pointing to the previous Node; update the value of the hash table bit counter Among them, d represents the value of the hash table bit counter, Indicates rounding up; migrate all data on the node whose address number is N to the node pointed to by the split pointer of the hash table; reduce the length of the hash table to N.

The data storage platform also includes: a data access processing unit, which is used to calculate the hash value of k according to H(k)=n when a user requests to access data with a key value of k, H represents a hash function, and n represents the calculated hash value Hash value; obtain the value d of the hash table digit counter; intercept the last d digits of n to obtain n'; intercept the last d-1 digits of n to obtain n"; compare the position of the hash table split pointer with the address number n", If the node with the address number n" is after the hash table split pointer, locate the request to the node with the address number n", if the node with the address number n" is before the hash table split pointer, locate the request to the address number is the node of n'.

Wherein, the data storage platform may be, for example, a cloud storage platform, or other service platforms such as billing or traffic control that have high real-time requirements and run on an in-memory database.

The present invention expands the structure of the hash table and the address mapping mode. When a new node joins the cluster, the original mapping between the key value and the address remains unchanged, and only the effective number of bits of the address and the length of the hash table are extended. The newly generated address is given to the new node, and the data is gradually migrated while keeping the system running; similarly, when a node leaves the cluster, the original mapping between the key value and the address remains unchanged, only the effective number of bits and Hash table length, and gradually migrate data while keeping the system running. This organization method not only retains the high real-time advantages of organizing cloud clusters through hash tables, but also makes the clusters easy to maintain and expand. The present invention is applicable to all cloud storage platforms, especially service platforms such as billing or flow control that have high real-time requirements and run on memory databases.

Other features of the present invention and advantages thereof will become apparent from the following detailed description of exemplary embodiments of the present invention with reference to the accompanying drawings.

Description of drawings

In order to more clearly illustrate the technical solutions in the embodiments of the present invention or the prior art, the following will briefly introduce the drawings that need to be used in the description of the embodiments or the prior art. Obviously, the accompanying drawings in the following description are only These are some embodiments of the present invention. For those skilled in the art, other drawings can also be obtained according to these drawings without any creative effort.

FIG. 1 is a schematic diagram of an existing hash table organization principle.

FIG. 2 is a schematic flowchart of the method for organizing a data storage platform in the present invention when nodes join a cluster.

Fig. 3 is a schematic diagram of the organization principle of the hash table of the present invention.

FIG. 4 is a schematic diagram of a data access flow in the present invention.

FIG. 5 is a schematic diagram of the organization process of the data storage platform when nodes join the cluster in the present invention.

FIG. 6 is a schematic flowchart of the method for organizing a data storage platform when a node leaves the cluster according to the present invention.

Fig. 7 is a schematic structural diagram of an embodiment of the data storage platform of the present invention.

Fig. 8 is a schematic structural diagram of another embodiment of the data storage platform of the present invention.

Detailed ways

The following will clearly and completely describe the technical solutions in the embodiments of the present invention with reference to the accompanying drawings in the embodiments of the present invention. Obviously, the described embodiments are only some, not all, embodiments of the present invention. The following description of at least one exemplary embodiment is merely illustrative in nature and in no way taken as limiting the invention, its application or uses. Based on the embodiments of the present invention, all other embodiments obtained by persons of ordinary skill in the art without creative efforts fall within the protection scope of the present invention.

The relative arrangements of components and steps, numerical expressions and numerical values set forth in these embodiments do not limit the scope of the present invention unless specifically stated otherwise.

In order to solve the problem that the existing hash table organization method is not easy to maintain the cluster, adding and deleting nodes need to stop the cluster operation and reorganize the data, the present invention proposes a data storage platform organization scheme based on a linear hash table. There is no need to change the hash function when adding and deleting nodes, and the data can be gradually migrated while keeping the system running. The cluster is easy to maintain and expand. The solution of the present invention will be described in detail below.

To simplify the model, we consider that the data has a unique key value k, the data storage platform has N nodes, and the addresses are numbered from 0 to N-1. The data storage platform maintains a hash table with a length of N, each column of the table points to a node, and maintains a hash function H, and the result of H(k) ranges from 0 to N-1. Hash itself is a mature technology, and the existing hash function can do it. Regardless of the distribution of k, the distribution of H(k) is basically uniform. The following describes the organization methods of the data storage platform when nodes join and leave the cluster.

FIG. 2 is a schematic flowchart of the method for organizing a data storage platform in the present invention when nodes join a cluster.

As shown in Figure 2, the data storage platform organization method of this embodiment when a node joins the cluster includes the following steps:

S201, for a cluster with N nodes, the address number of each node is 0-N-1, if a new node joins the cluster, the length of the hash table is extended to N+1, and the address number of the new node is recorded as N .

S202. Add a hash table split pointer used to record the data migration situation, and migrate part of the data on the node pointed to by the hash table split pointer to a new node whose address number is N.

FIG. 3 shows a schematic diagram of the organization principle of the hash table in the present invention. As shown in Figure 3, the present invention only needs to migrate the data on one node, and can migrate about half of the data to the new node.

S203, the hash table split pointer is moved backward by one bit to point to the next node.

S204, increase the hash table digit counter used to record the overall size of the cluster, and update the value of the hash table digit counter Among them, d represents the value of the hash table bit counter, Indicates rounding up.

Based on the data storage platform organization method shown in Figure 2, when a user requests access to data with a key value of k, as shown in Figure 4, the method further includes the following steps:

S401. Calculate the hash value of k according to H(k)=n.

Among them, H represents the hash function, k represents the key value of the data to be accessed, and n represents the calculated hash value. In the present invention, there is no need to replace the hash function, the value range of the hash function can be expressed as 0 to 2 ^m -1, and the value range (or m) of the hash function is large enough to ensure that no matter how the cluster expands, The node address numbers will not exceed this range, that is, the value range of the hash function is greater than the range of the address numbers of the nodes in the cluster. The last few bits of the hash function are intercepted as the hash output, and the number of intercepted bits depends on the situation, which is explained in detail below.

S402. Obtain the value d of the digit counter of the hash table.

S403, intercepting the last d bits of n to obtain n'.

S404, intercepting the last d-1 digits of n to obtain n".

S405, compare the location of the hash table split pointer and the address number n";

S405a, if the node with the address number n" locates the request to the node with the address number n" after the hash table split pointer;

S405b, if the node with the address number n" is before the hash table split pointer, locate the request to the node with the address number n'.

In order to make the solution of the present invention more clear, an example of a hash table organization method and a user accessing data when a node joins the cluster is listed below. It will be appreciated by those skilled in the art that in all examples shown and discussed herein, any specific values should be construed as exemplary only and not as limiting. Therefore, other examples of the exemplary embodiment may have different values.

FIG. 5 is a schematic diagram of the organization process of the data storage platform when nodes join the cluster in the present invention.

Assuming that the cluster has 4 nodes, the address numbers of each node are 00, 01, 10, and 11 in sequence, and the initial position of the hash table split pointer points to the node with address number 00. At this time, the value d of the hash table digit counter is 2 .

If a new node joins the cluster, extend the length of the hash table to 5, and record the number of the new node as 3-digit binary 100. Since the initial position of the split pointer of the hash table points to the node with address number 00, the node 00 The corresponding data is migrated to node 100. About half of the data on node 00 is migrated to node 100, and the rest is still on node 00. The hash table split pointer moves backwards to point to node 01. At this time, the number of digits in the hash table counter The value d is 3. Since the output length of the hash function is long, the address number of node 00 becomes 000.

If a new node joins the cluster, the serial number of the new node is 101. Since the hash table split pointer points to node 01 at this time, the corresponding data on node 01 is migrated to node 101, and the data on node 01 is about half Migrating to node 101, the split pointer of the hash table moves backwards to point to node 10, and the value d of the bit counter of the hash table is still 3 at this time. Similarly, the address number of node 01 becomes 001.

If a new node joins the cluster again, and so on, until node 11 is split, then the hash table split pointer returns to 000. At this time, all nodes have gone through a round of split, and all node address numbers are 3 digits.

When the user requests to access data with key value k, the system first calculates H(k)=n, then takes the value d of the digit counter, intercepts the last d digits of n to obtain n', and the last d-1 digits of n' are called is n”; look at the split pointer, if n” is after the split pointer, then directly locate the data request to the n” node, if n’’ is before the split pointer, then locate the request to the n’ node.

FIG. 6 is a schematic flowchart of the method for organizing a data storage platform when a node leaves the cluster according to the present invention.

As shown in Figure 6, the data storage platform organization method of this embodiment when a node leaves the cluster includes the following steps:

S601, for a cluster with the number of nodes being N+1, if the node whose address number is N at the end of the hash table leaves the cluster, the split pointer of the hash table is moved forward by one bit to point to the previous node;

S602, update the value of the bit counter of the hash table Among them, d represents the value of the hash table bit counter, Indicates rounding up;

S603, migrating all the data on the node whose address number is N to the node pointed to by the split pointer of the hash table;

S604. Reduce the length of the hash table to N.

Based on the data storage platform organization method shown in FIG. 6 , the processing of the user's request to access data with a key value of k may refer to the embodiment shown in FIG. 4 , which is only briefly outlined here. When a user requests to access data with a key value of k, calculate the hash value of k according to H(k)=n, where H represents the hash function and n represents the calculated hash value; obtain the value d of the digit counter of the hash table ; Intercept the last d bits of n to get n'; intercept the last d-1 bits of n to get n"; compare the hash table split pointer with the position of address number n", if the node with address number n" is split in the hash table After the pointer, locate the request to the node with the address number n", if the node with the address number n" is before the hash table split pointer, locate the request to the node with the address number n'.

It can be seen that the data storage platform organization scheme proposed by the present invention expands the structure of the hash table and the address mapping mode. The effective number of bits of the address and the length of the hash table, assign the newly generated address to the new node, and gradually migrate the data while keeping the system running; similarly, when a node leaves the cluster, keep the original key value and address The mapping is unchanged, only the effective number of bits of the address and the length of the hash table are shrunk, and the data is gradually migrated while keeping the system running. This organization method not only retains the high real-time advantages of organizing cloud clusters through hash tables, but also makes the clusters easy to maintain and expand. The data storage platform of the present invention is applicable to all cloud storage platforms, especially service platforms such as billing or flow control that have high real-time requirements and run on memory databases.

Based on the foregoing data organization method, the present invention also proposes a corresponding data storage platform. Fig. 7 is a schematic structural diagram of an embodiment of the data storage platform of the present invention. As shown in FIG. 7 , the data storage platform of this embodiment includes: a node joining processing unit 701 or/and a node leaving processing unit 702 .

The node joining processing unit 701 is a cluster whose number of nodes is N, if a new node joins the cluster, the length of the hash table is expanded to N+1, and the address number of the new node is recorded as N; Part of the data on the node is migrated to the new node with the address number N; the split pointer of the hash table is shifted by one bit to point to the next node; the value of the bit counter of the hash table is updated Among them, d represents the value of the hash table bit counter, Indicates rounding up.

Node leaving processing unit 702 For a cluster with the number of nodes being N+1, if the node whose address number is N at the end of the hash table leaves the cluster, the split pointer of the hash table moves forward by one bit, pointing to the previous node; update the hash table The value of the Greek table bit counter Among them, d represents the value of the hash table bit counter, Indicates rounding up; migrate all data on the node whose address number is N to the node pointed to by the split pointer of the hash table; reduce the length of the hash table to N.

Fig. 8 is a schematic structural diagram of another embodiment of the data storage platform of the present invention. As shown in Figure 8, the data storage platform of this embodiment also includes:

The data access processing unit 803 is used to calculate the hash value of k according to H(k)=n when the user requests to access the data whose key value is k, H represents the hash function, and n represents the calculated hash value; The value d of the table digit counter; intercept the last d digits of n to obtain n'; intercept the last d-1 digits of n to obtain n"; compare the position of the hash table split pointer with the address number n", if the address number is n After the hash table splits the pointer, the node with the address of "n" locates the request to the node with the address number n". .

Among them, the value range of the hash function can be expressed as 0 to 2 ^m -1, and the value range (or m) of the hash function is large enough to ensure that no matter how the cluster expands, the node address number will not exceed this range , that is, the value range of the hash function is greater than the range of the address numbers of the nodes in the cluster.

The aforementioned data storage platform may be, for example, a cloud storage platform, or other service platforms that require high real-time performance and run on an in-memory database such as accounting or traffic control.

The data storage platform proposed by the present invention expands the structure of the hash table and the address mapping mode. When a new node joins the cluster, the original mapping between the key value and the address remains unchanged, and only the effective digits and The length of the hash table, assign the newly generated address to the new node, and gradually migrate the data while keeping the system running; similarly, when a node leaves the cluster, keep the original mapping between the key value and the address unchanged, just shrink The effective number of bits of the address and the length of the hash table, and gradually migrate the data while keeping the system running. This organization method not only retains the high real-time advantages of organizing cloud clusters through hash tables, but also makes the clusters easy to maintain and expand. The data storage platform of the present invention is applicable to all cloud storage platforms, especially service platforms such as billing or flow control that have high real-time requirements and run on memory databases.

Those of ordinary skill in the art can understand that all or part of the steps for implementing the above embodiments can be completed by hardware, and can also be completed by instructing related hardware through a program. The program can be stored in a computer-readable storage medium. The above-mentioned The storage medium mentioned may be a read-only memory, a magnetic disk or an optical disk, and the like.

The above descriptions are only preferred embodiments of the present invention, and are not intended to limit the present invention. Any modifications, equivalent replacements, improvements, etc. made within the spirit and principles of the present invention shall be included in the protection of the present invention. within range.

Claims (10)

1. A data storage platform organization method based on a linear hash table, comprising: For a cluster with N nodes, the address number of each node in the cluster is 0~N-1. If a new node joins the cluster, the length of the hash table is extended to N+1, and the address number of the new node is recorded as N ; Migrate part of the data on the node pointed to by the split pointer of the hash table to the new node whose address number is N; The hash table split pointer is shifted one bit to point to the next node; Update the value of the hash table bit counter Among them, d represents the value of the hash table bit counter, Indicates rounding up. 2. The method according to claim 1, further comprising: When a user requests to access data with a key value of k, the hash value of k is calculated according to H(k)=n, H represents the hash function, and n represents the calculated hash value; Obtain the value d of the digit counter of the hash table; Intercept the last d bits of n to get n'; Intercept the last d-1 digits of n to get n”; Compare the position of the hash table split pointer and the address number n", if the node with the address number n" is after the hash table split pointer, locate the request to the node with the address number n", if the node with the address number n" Before the hash table splits the pointer, locate the request to the node with address number n'. 3. The method according to claim 2, wherein the value range of the hash function is greater than the range of the address numbers of the nodes in the cluster. 4. The method according to claim 1, wherein the data storage platform is a cloud storage platform. 5. A data storage platform organization method based on a linear hash table, comprising: For a cluster with N+1 nodes, the addresses of each node in the cluster are numbered from 0 to N. If the node whose address number is N at the end of the hash table leaves the cluster, the split pointer of the hash table will move forward one bit. point to the previous node; Update the value of the hash table bit counter Among them, d represents the value of the hash table bit counter, Indicates rounding up; Migrate all data on the node whose address number is N to the node pointed to by the split pointer of the hash table; Reduce the hash table length to N. 6. The method according to claim 5, further comprising: When a user requests to access data with a key value of k, the hash value of k is calculated according to H(k)=n, H represents the hash function, and n represents the calculated hash value; Obtain the value d of the digit counter of the hash table; Intercept the last d bits of n to get n'; Intercept the last d-1 digits of n to get n”; Compare the position of the hash table split pointer and the address number n", if the node with the address number n" is after the hash table split pointer, locate the request to the node with the address number n", if the node with the address number n" Before the hash table splits the pointer, locate the request to the node with address number n'. 7. A data storage platform, comprising: a node joins a processing unit or/and a node leaves a processing unit; Nodes join the processing unit For a cluster with N nodes, if a new node joins the cluster, the length of the hash table is extended to N+1, and the address number of the new node is recorded as N; the node pointed to by the split pointer of the hash table Part of the data above is migrated to the new node with the address number N; the hash table split pointer is shifted by one bit to point to the next node; the value of the hash table bit counter is updated Among them, d represents the value of the hash table bit counter, Indicates rounding up; Node leaves the processing unit For a cluster with the number of nodes N+1, if the node whose address number is N at the end of the hash table leaves the cluster, the split pointer of the hash table moves forward one bit to point to the previous node; update the hash table Table bit counter value Among them, d represents the value of the hash table bit counter, Indicates rounding up; migrate all data on the node whose address number is N to the node pointed to by the split pointer of the hash table; reduce the length of the hash table to N. 8. The data storage platform according to claim 7, further comprising: The data access processing unit is used to calculate the hash value of k according to H(k)=n when a user requests to access data with a key value of k, H represents a hash function, and n represents a calculated hash value; obtain the hash The value d of the table digit counter; intercept the last d digits of n to obtain n'; intercept the last d-1 digits of n to obtain n"; compare the position of the hash table split pointer with the address number n", if the address number is n" After the hash table splits the pointer, the node locates the request to the node with the address number n", if the node with the address number n" is before the hash table splits the pointer, locates the request to the node with the address number n'. 9. The data storage platform according to claim 8, wherein the value range of the hash function is greater than the range of the address numbers of the nodes in the cluster. 10. The data storage platform according to claim 7, wherein the data storage platform is a cloud storage platform.