Hash Database Configuration Method and Apparatus

• US 20160217167A1
• Filed: 03/31/2016
• Published: 07/28/2016
• Est. Priority Date: 11/29/2013
• Status: Active Grant

• Current Assignee: Huawei Technologies Co., Ltd. (Huawei Investment & Holding Co., Ltd.)
• Original Assignee: Huawei Technologies Co., Ltd. (Huawei Investment & Holding Co., Ltd.)
• Inventors: Bao, Dong, Zhang, Lei
• Granted Patent: US 10,331,641 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/2228 Indexing structures
• CPC Class Codes: G06F 16/2255 Hash tables
• CPC Class Codes: G06F 16/9024 Graphs; Linked lists G06F16/9027 takes precedence
• CPC Class Codes: G06F 3/0604 Improving or facilitating administration, e.g. storage management
• CPC Class Codes: G06F 3/0619 in relation to data integrity, e.g. data losses, bit errors
• CPC Class Codes: G06F 3/0638 Organizing or formatting or addressing of data
• CPC Class Codes: G06F 3/065 Replication mechanisms
• CPC Class Codes: G06F 3/0674 Disk device

Abstract

A hash database configuration method and apparatus, where the method includes establishing an index area and a data area on a disk, where the index area includes p disk pages with an equal size, and receiving an allocation request of key-value pairs, allocating m keys in the key-value pairs to disk pages in the index area, and allocating n values in the key-value pairs to the data area, where m, n, and p are all integers greater than 1, and the efficiency of accessing the hash database is improved.

Claims

1. A hash database configuration method, comprising:

establishing an index area and a data area on a disk, wherein the index area comprises p disk pages with an equal size;

receiving an allocation request of key-value pairs;

allocating each key of m keys in the key-value pairs to a disk page in the index area; and

allocating n values in the key-value pairs to the data area, wherein m, n, and p are all integers greater than 1.

2. The method according to claim 1, wherein allocating each key of m keys in the key-value pairs to the disk page in the index area comprises:

selecting a to-be-allocated key from the m keys;

performing a hash operation on the to-be-allocated key to obtain a hash value;

performing, according to the hash value and a quantity p of the disk pages, a modulo operation to obtain a serial number of a disk page to be allocated to; and

storing the to-be-allocated key on the disk page to be allocated to according to the serial number.

3. The method according to claim 2, further comprising:

establishing an extended area on the disk, wherein the extended area comprises q extended pages with the equal size, and wherein q is an integer greater than 1; and

storing an overflowed key on an extended page when the disk page to be allocated to overflows.

4. The method according to claim 3, wherein when a remaining capacity of the disk page to be allocated to is less than a length of the to-be-allocated key, and wherein storing the to-be-allocated key on the disk page to be allocated to according to the serial number comprises:

searching the extended area for an extended page whose remaining capacity is greater than the length of the to-be-allocated key; and

storing the to-be-allocated key on the extended page.

5. The method according to claim 4, further comprising managing, using a bitmap technology, allocation and reclaiming of the q extended pages in the extended area.

6. The method according to claim 5, further comprising forming the disk page and the extended page that have a same hash value into a linked list, wherein the disk page is located at the head of the linked list.

7. The method according to claim 6, further comprising:

establishing a backup area on the disk; and

copying a duplicate of data in the index area and a duplicate of data in the extended area to the backup area, wherein the backup area is neither adjacent to the index area nor to the extended area.

8. The method according to claim 1, wherein a capacity of one disk page is set to store at least two keys, and wherein the keys are allocated to a same disk page in the index area.

9. A device, comprising:

a memory configured to store instructions; and

a processor coupled to the memory to execute the instructions to execute the following operations;

establish an index area and a data area on a disk, wherein the index area comprises p disk pages with an equal size;

receive an allocation request of key-value pairs;

allocate each key of m keys in the key-value pairs to a disk page in the index area; and

allocate n values in the key-value pairs to the data area, wherein m, n, and p are all integers greater than 1.

10. The device according to claim 9, wherein when allocating each key of m keys in the key-value pairs to the disk page in the index area, the processor is further configured to execute the following operations:

select a to-be-allocated key from the m keys;

perform a hash operation on the to-be-allocated key to obtain a hash value;

perform, according to the hash value and a quantity p of the disk pages, a modulo operation to obtain a serial number of a disk page to be allocated to; and

store the to-be-allocated key on the disk page to be allocated to according to the serial number.

11. The device according to claim 10, the processor is further configured to execute the following operations:

establish an extended area on the disk, wherein the extended area comprises q extended pages with the equal size, and wherein q is an integer greater than 1; and

store an overflowed key on an extended page when the disk page to be allocated to overflows.

12. The device according to claim 11, wherein when storing the to-be-allocated key on the disk page to be allocated to according to the serial number, the processor is further configured to execute the following operations:

search the extended area for an extended page whose remaining capacity of the disk page is greater than a length of the to-be-allocated key when the remaining capacity of the disk page to be allocated to is less than the length of the to-be-allocated key; and

store the to-be-allocated key on the extended page.

13. The device according to claim 12, the processor is further configured to manage, using a bitmap technology, allocation and reclaiming of the q extended pages in the extended area.

14. The device according to claim 13, the processor is further configured to form the disk page and the extended page that have a same hash value into a linked list, wherein the disk page is located at the head of the linked list.

15. The device according to claim 14, the processor is further configured to execute the following operations:

establish a backup area on the disk; and

copy a duplicate of data in the index area and a duplicate of data in the extended area to the backup area, wherein the backup area is neither adjacent to the index area nor to the extended area.

16. The device according to claim 9, wherein a capacity of one disk page is set to store at least two keys, and wherein the keys are allocated to a same disk page in the index area.