Self-balancing binary search capable distributed database

• US 10,540,370 B2
• Filed: 06/26/2017
• Issued: 01/21/2020
• Est. Priority Date: 06/26/2017
• 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: Ashwood-Smith, Peter James
• Primary Examiner(s): Corrielus, Jean M
• Application Number:
  US15/633,340
• Publication Number:
  US 20180373771A1
• Time in Patent Office: 939 Days
• Field of Search: 707736
• CPC Class Codes: G06F 12/06 Addressing a physical block of locations, e.g. base addressing, module addressing, memory dedication G06F12/08 takes precedence
• CPC Class Codes: G06F 16/21 Design, administration or maintenance of databases
• CPC Class Codes: G06F 16/27 Replication, distribution or synchronisation of data between databases or within a distributed database system; Distributed database system architectures therefor
• CPC Class Codes: G06F 9/5027 the resource being a machine, e.g. CPUs, Servers, Terminals

Abstract

A self-balancing binary search capable distributed database (DB) includes a number of computing devices associated with a communication system and/or network. Each of the respective computing devices forming the distributed DB stores a subset of the overall information included within the distributed DB. Based on keys of key-value pairs (KVPs) stored in the computing devices, the computing devices are arranged logically to form a sorted key-ordered ring such that each computing device includes KVPs with keys higher than a predecessor computing device and lower than a successor computing device. A requested KVP query is made to any computing device in the distributed DB, which may include generating and transmitting another query to one or more other computing devices until the requested KVP is found. The distributed DB performs balancing operations moving the KVPs from computing devices with higher storage usage to computing devices with lower storage usage.

Claims

1. A computing device comprising:

network communication circuitry configured to communicate via a communication network;

memory that stores operational instructions; and

processing circuitry that is coupled to the network communication circuitry and the memory, wherein the processing circuitry, when executing the operational instructions, is configured to;

store, in the memory, a subset of a plurality of key-value pairs corresponding to a subset of a plurality of device identifiers associated with the communication network, wherein based on a sorted key-order of a plurality of computing devices including the computing device, and wherein the subset of the plurality of key-value pairs includes keys that are greater than keys of a predecessor subset of the plurality of key-value pairs stored within a predecessor computing device and that are lower than keys of a successor subset of the plurality of key-value pairs stored within a successor computing device;

transmit, via the network communication circuitry, local storage usage information of the subset of the plurality of key-value pairs within the computing device to at least one of the predecessor computing device or the successor computing device;

receive, via the network communication circuitry, at least one of predecessor storage usage information of the predecessor subset of the plurality of key-value pairs within the predecessor computing device or successor storage usage information of the successor subset of the plurality of key-value pairs within the successor computing device; and

when the plurality of key-value pairs of at least one of the predecessor storage usage information or the successor storage usage information is outside a range of the plurality of key-value pairs of the local storage usage information, perform a key-value pair storage balancing operation with the at least one of the predecessor computing device or the successor computing device.

2. The computing device of claim 1, wherein the processing circuitry, when executing the operational instructions, is further configured to:

transmit, via the network communication circuitry, the local storage usage information to the predecessor computing device and to the successor computing device;

receive, via the network communication circuitry, the predecessor storage usage information from the predecessor computing device;

receive, via the network communication circuitry, the successor storage usage information from the successor computing device; and

when the plurality of key-value pairs of at least one of the predecessor storage usage information or the successor storage usage information is outside the range of the plurality of key-value pairs of the local storage usage information, perform at least one of;

transmit, via the network communication circuitry, at least one of a first key-value pair of the subset of the plurality of key-value pairs to the predecessor computing device or a second key-value pair of the subset of the plurality of key-value pair the successor computing device to be stored therein;

or

receive, via the network communication circuitry, at least one of a predecessor key-value pair of the predecessor subset of the plurality of key-value pairs from the predecessor computing device or a successor key-value pair of the successor subset of the plurality of key-value pairs from the successor computing device to be stored within the computing device.

3. The computing device of claim 2, wherein the processing circuitry, when executing the operational instructions, is further configured to:

update the local storage usage information to generate updated local storage usage information based on an updated subset of the plurality of key-value pairs to be stored in the computing device including identification of a lowest key value and a highest key value therein; and

transmit, via the network communication circuitry, the updated local storage usage information to the predecessor computing device and to the successor computing device.

4. The computing device of claim 1, wherein the processing circuitry, when executing the operational instructions, is further configured to:

transmit, via the network communication circuitry, full local storage usage information of the computing device that specifies full storage capacity of the computing device to the at least one of the predecessor computing device or the successor computing device; and

transmit, via the network communication circuitry, all of the subset of the plurality of key-value pairs to the at least one of the predecessor computing device or the successor computing device to be stored therein.

5. The computing device of claim 1, wherein the processing circuitry, when executing the operational instructions, is further configured to:

transmit, via the network communication circuitry, full local storage usage information of the computing device that specifies empty storage capacity of the computing device to the at least one of the predecessor computing device or the successor computing device; and

receive, via the network communication circuitry, the subset of the plurality of key-value pairs from the at least one of the predecessor computing device or the successor computing device to be stored in the memory.

6. The computing device of claim 1, wherein the processing circuitry, when executing the operational instructions, is further configured to:

perform the key-value pair storage balancing operation with the at least one of the predecessor computing device or the successor computing device until a key-value pair percentage difference between key-value pairs stored in the computing device and at least one of first other key-value pairs stored in the predecessor computing device or second other key-value pairs stored in the successor computing device is less than a threshold.

7. The computing device of claim 1, wherein a key of a key-value pair of the plurality of key-value pairs corresponds to at least one of a User Equipment (UE), a username, a phone number, an International Mobile Subscriber Identity (IMSI), or an International Mobile Equipment Identity (IMEI).

8. The computing device of claim 1, wherein a value of a key-value pair of the plurality of key-value pairs corresponds to at least one of a location associated with key of the key-value pair, an Internet Protocol (IP) address associated with the key of the key-value pair, a port address-IP address pair associated with the key of the key-value pair, a base station (BS) associated with the key of the key-value pair, a wireless local area network (WLAN) associated with the key of the key-value pair, or a local area network (LAN) associated with the key of the key-value pair.

9. A method for execution by a computing device, the method comprising:

storing, in a memory of the computing device, a subset of a plurality of key-value pairs corresponding to a subset of a plurality of device identifiers associated with a communication network, wherein based on a sorted key-order of a plurality of computing devices including the computing device, and wherein the subset of the plurality of key-value pairs includes keys that are greater than keys of a predecessor subset of the plurality of key-value pairs stored within a predecessor computing device and that are lower than keys of a successor subset of the plurality of key-value pairs stored within a successor computing device;

transmitting, via network communication circuitry of the computing device, local storage usage information of the subset of the plurality of key-value pairs within the computing device to at least one of the predecessor computing device or the successor computing device;

receiving, via the network communication circuitry, at least one of predecessor storage usage information of the predecessor subset of the plurality of key-value pairs within the predecessor computing device or successor storage usage information of the successor subset of the plurality of key-value pairs within the successor computing device; and

when the plurality of key-value pairs of at least one of the predecessor storage usage information or the successor storage usage information is outside a range of the plurality of key-value pairs of the local storage usage information, perform a key-value pair storage balancing operation with the at least one of the predecessor computing device or the successor computing device.

10. The method of claim 9 further comprising:

transmitting, via the network communication circuitry, the local storage usage information to the predecessor computing device and to the successor computing device;

receiving, via the network communication circuitry, the predecessor storage usage information from the predecessor computing device;

receiving, via the network communication circuitry, the successor storage usage information from the successor computing device; and

when the plurality of key-value pairs of at least one of the predecessor storage usage information or the successor storage usage information is outside the range of the plurality of key-value pairs of the local storage usage information, perform at least one of;

transmitting, via the network communication circuitry, at least one of a first key-value pair of the subset of the plurality of key-value pairs to the predecessor computing device or a second key-value pair of the subset of the plurality of key-value pair the successor computing device to be stored therein;

or

receiving, via the network communication circuitry, at least one of a predecessor key-value pair of the predecessor subset of the plurality of key-value pairs from the predecessor computing device or a successor key-value pair of the successor subset of the plurality of key-value pairs from the successor computing device to be stored within the computing device.

11. The method of claim 10 further comprising:

updating the local storage usage information to generate updated local storage usage information based on an updated subset of the plurality of key-value pairs to be stored in the computing device including identification of a lowest key value and a highest key value therein; and

transmitting, via the network communication circuitry, the updated local storage usage information to the predecessor computing device and to the successor computing device.

12. The method of claim 9 further comprising:

transmitting, via the network communication circuitry, full local storage usage information of the computing device that specifies full storage capacity of the computing device to the at least one of the predecessor computing device or the successor computing device; and

transmitting, via the network communication circuitry, all of the subset of the plurality of key-value pairs to the at least one of the predecessor computing device or the successor computing device to be stored therein.

13. The method of claim 9 further comprising:

transmitting, via the network communication circuitry, full local storage usage information of the computing device that specifies empty storage capacity of the computing device to the at least one of the predecessor computing device or the successor computing device; and

receiving, via the network communication circuitry, the subset of the plurality of key-value pairs from the at least one of the predecessor computing device or the successor computing device to be stored in the memory.

14. The method of claim 9 further comprising:

performing the key-value pair storage balancing operation with the at least one of the predecessor computing device or the successor computing device until a key-value pair percentage difference between key-value pairs stored in the computing device and at least one of first other key-value pairs stored in the predecessor computing device or second other key-value pairs stored in the successor computing device is less than a threshold.

15. The method of claim 9, wherein a key of a key-value pair of the plurality of key-value pairs corresponds to at least one of a User Equipment (UE), a username, a phone number, an International Mobile Subscriber Identity (IMSI), or an International Mobile Equipment Identity (IMEI).

16. The method of claim 9, wherein a value of a key-value pair of the plurality of key-value pairs corresponds to at least one of a location associated with key of the key-value pair, an Internet Protocol (IP) address associated with the key of the key-value pair, a port address-IP address pair associated with the key of the key-value pair, a base station (BS) associated with the key of the key-value pair, a wireless local area network (WLAN) associated with the key of the key-value pair, or a local area network (LAN) associated with the key of the key-value pair.