METHOD AND APPARATUS FOR DATA STORAGE AND RETRIEVAL

• US 20160253322A1
• Filed: 10/18/2013
• Published: 09/01/2016
• Est. Priority Date: 10/18/2013
• Status: Abandoned Application

• Current Assignee: Telefonaktiebolaget LM Ericsson
• Original Assignee: Telefonaktiebolaget LM Ericsson
• Inventors: Li, Qingsong
• Application Number:
  US15/028,554
• Publication Number:
  US 20160253322A1
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 12/0864 using pseudo-associative means, e.g. set-associative or hashing
• CPC Class Codes: G06F 16/137 Hash-based content-based indexing of textual data G06F16/31
• CPC Class Codes: G06F 16/2255 Hash tables

Abstract

Methods and apparatuses for data storage and retrieval have been provided. More specifically, a hash table is provided. The hash table comprises a first level slot array with a constant number of slots and at least one second level slot array with a variant number of slots. Each slot of the first level slot array is associated with a hash code range, and each slot of the first level slot array is linked to at most one second level slot array. Various operations, such as PUT, GET, RANGE_SEARCH of the hash table have been described. Moreover, a hash method has been provided for network management information to use the proposed hash table.

Claims

1. A method for processing data in a hash table, wherein said hash table comprises a first level slot array with a constant number of slots and at least one second level slot array with a variant number of slots, each slot of the first level slot array being associated with a hash code range generated with a first hash function, and each slot of the first level slot array being linked to at most one second level slot array, said method comprising:

receiving data to be processed, said data being represented by a key and value pair;

obtaining a first hash code which is generated from the key according to the first hash function;

determining a slot of the first level slot array associated with a hash code range to which the first hash code corresponds; and

storing said key and value pair into a second level slot array to which the determined slot of the first level slot array is linked.

2. The method of claim 1, wherein the constant number N of slots of the first level slot array is determined based on a maximum possible number of key and value pairs to be put into said hash table and a space factor for the first level slot array.

3. The method of claim 1, wherein slots of the first level slot array are arranged to be associated with a respective hash code range in the order of hash codes generated according to the first hash function.

4. The method of claim 1, wherein storing said key and value pair into a second level slot array comprises:

deciding whether the second level slot array needs resizing;

resizing the second level slot array in response that the second level slot array needs resizing;

determining a slot of the second level slot array or of the resized second level slot array from said key according to a second hash function; and

storing said key and value pair into the determined slot of the second level slot array or of the resized second level slot array as a hash entry.

5. The method of claim 1, wherein

said data includes network management information consisted of a set of managed objects, a managed object belongs to a managed object class, MOC, a set of MOCs is represented by an MOC tree based on parent-child inheritance relationships among the MOCs, the managed object'"'"'s distinguished name is used as a key, and the managed object'"'"'s data is a value associated with the key, and

said first hash function is arranged to map a distinguished name of a managed object to a first hash code, preserving an order where a hash code of any MO belonging to any MOC is larger than a hash code of any MO belonging to any parent MOC of the MOC, or a hash code of any MO belonging to any MOC is smaller than a hash code of any MO belonging to any parent MOC of the MOC.

6. The method of claim 5, wherein said hash table is initialized by:

traversing the MOC tree in an order that, for any MOC node, its ancestor MOC nodes are traversed prior to it;

for each traversed MOC node, allocating a code range based on a cardinal number of the MOC node and cardinal numbers of its all ancestor MOC nodes till a root node; and

dividing a space consisted of the code ranges into hash code ranges with which the slots of the first level slot array are associated.

7. The method of claim 6, wherein said first hash function is arranged to map a distinguished name of a managed object to a first hash code by:

parsing the managed object'"'"'s distinguished name into a set of relative distinguished names, RDNs;

for each RDN, determining a relative position i(RDN) of said RDN within an allocated code range of a MOC node to which said RDN belongs; and

generating the first hash code based on the relative position of each RDN.

8. A method for retrieving data from a hash table, wherein said hash table comprises a first level slot array with a constant number of slots and at least one second level slot array with a variant number of slots, each slot of the first level slot array being associated with a hash code range generated with a first hash function, and each slot of the first level slot array being linked to at most one second level slot array, and wherein said data represented by key and value pairs are stored as hash entries in the hash table, said method comprising:

receiving a key;

obtaining a first hash code which is generated from the key according to the first hash function;

determining a slot of the first level slot array associated with a hash code range to which the first hash code corresponds; and

retrieving a value corresponding to said key from a second level slot array to which the determined slot of the first level slot array is linked.

9. The method of claim 8, wherein slots of the first level slot array are arranged to be associated with a respective hash code range in the order of hash codes generated according to the first hash function.

10. A method for searching data in a range of a hash table, wherein said hash table comprises a first level slot array with a constant number of slots and at least one second level slot array with a variant number of slots, each slot of the first level slot array being associated with a hash code range in the order of hash codes generated with a first hash function, and each slot of the first level slot array being linked to at most one second level slot array, and wherein said data represented by key and value pairs are stored as hash entries in the hash table, said method comprising:

obtaining a start hash code and an end hash code which define the range of the hash table;

determining a slot range of the first level slot array, wherein a start slot of the slot range is associated with a hash code range to which the start hash code corresponds, and an end slot of the slot range is associated with a hash code range to which the end hash code corresponds;

searching hash entries in each second level slot array to which each slot within the slot range is linked; and

returning searched hash entries.

11. The method of claim 10, wherein obtaining a start hash code and an end hash code comprises:

receiving a start key and an end key; and

generating the start hash code from the start key according to the first hash function and the end hash code from the end key according to the first hash function.

12. The method of claim 10, wherein

said data includes network management information consisted of a set of managed objects, a managed object belongs to a managed object class, MOC, a set of MOCs is represented by an MOC tree based on parent-child inheritance relationships among the MOCs, the managed object'"'"'s distinguished name is used as a key, and the managed object'"'"'s data is a value associated with the key, and

said first hash function is arranged to map a distinguished name of a managed object to a first hash code, preserving an order where a hash code of any MO belonging to any MOC is larger than a hash code of any MO belonging to any parent MOC of the MOC, or a hash code of any MO belonging to any MOC is smaller than a hash code of any MO belonging to any parent MOC of the MOC.

13. The method of claim 12, wherein said hash table is initialized by:

traversing the MOC tree in an order that, for any MOC node, its ancestor MOC nodes are traversed prior to it;

for each traversed MOC node, allocating a code range based on a cardinal number of the MOC node and cardinal numbers of its all ancestor MOC nodes till a root node; and

dividing a space consisted of the code ranges into hash code ranges with which the slots of the first level slot array are associated.

14. The method of claim 13, wherein obtaining a start hash code and an end hash code comprises:

receiving a retrieval request for retrieving data of a set of managed objects belonging to a given MOC, said retrieval request containing said given MOC'"'"'s name;

searching the MOC tree for said given MOC to obtain its allocated code range; and

determining the start hash code as the start of the allocated code range, and the end hash code as the end of the allocated code range.

15. The method of claim 13, wherein obtaining a start hash code and an end hash code comprises:

receiving a retrieval request for retrieving data of a set of managed objects belonging to one or more MOCs, the managed objects of said set of managed objects being descendants from a given managed object, said retrieval request containing said given managed object'"'"'s distinguished name and a set of MOC names which are descendents of the given managed object'"'"'s MOC; and

for each descendent MOC,

searching the MOC tree for said descendent MOC to obtain its allocated code range;

extracting a hash code range corresponding to descendents of the given managed object from the allocated code range, based on a first hash code generated from the given managed object'"'"'s distinguished name according to the first hash function; and

determining the start hash code as the start of the extracted hash code range, and the end hash code as the end of the extracted hash code range.

16. The method of claim 10, further comprising:

obtaining a filter condition; and

filtering the searched hash entries with the filter condition.

17. An apparatus for processing data in a hash table, wherein said hash table comprises a first level slot array with a constant number of slots and at least one second level slot array with a variant number of slots, each slot of the first level slot array being associated with a hash code range generated with a first hash function, and each slot of the first level slot array being linked to at most one second level slot array, said apparatus comprising:

a receiving unit, configured to receive data to be processed, said data being represented by a key and value pair;

a first level unit, comprising a first hashing unit configured to generate obtain a first hash code which is generated from the key according to the first hash function, and a first slot determination unit configured to determine a slot of the first level slot array associated with a hash code range to which the first hash code corresponds; and

a second level unit, configured to store said key and value pair into a second level slot array to which the determined slot of the first level slot array is linked.

18. The apparatus of claim 17, wherein the constant number N of slots of the first level slot array is determined based on a maximum possible number of key and value pairs to be put into said hash table and a space factor for the first level slot array.

19. The apparatus of claim 17, wherein slots of the first level slot array are arranged to be associated with a respective hash code range in the order of hash codes generated according to the first hash function.

20. The apparatus of claim 17, wherein said second level unit comprises:

a decision unit, configured to decide whether the second level slot array needs resizing;

a resizing unit, configured to resize the second level slot array in response that the second level slot array needs resizing;

a second slot determination unit, configured to determine a slot of the second level slot array or of the resized second level slot array from said key according to a second hash function; and

a storing unit, configured to store said key and value pair into the determined slot of the second level slot array or of the resized second level slot array as a hash entry.

21. The apparatus of claim 17, wherein

said data includes network management information consisted of a set of managed objects, a managed object belongs to a managed object class, MOC, a set of MOCs is represented by an MOC tree based on parent-child inheritance relationships among the MOCs, the managed object'"'"'s distinguished name is used as a key, and the managed object'"'"'s data is a value associated with the key, and

said first hash function is arranged to map a distinguished name of a managed object to a first hash code, preserving an order where a hash code of any MO belonging to any MOC is larger than a hash code of any MO belonging to any parent MOC of the MOC, or a hash code of any MO belonging to any MOC is smaller than a hash code of any MO belonging to any parent MOC of the MOC.

22. The apparatus of claim 21, wherein said hash table is initialized by an initialization unit which is configured to:

traverse the MOC tree in an order that, for any MOC node, its ancestor MOC nodes are traversed prior to it;

for each traversed MOC node, allocate a code range based on a cardinal number of the MOC node and cardinal numbers of its all ancestor MOC nodes till a root node; and

divide a space consisted of the code ranges into hash code ranges with which the slots of the first level slot array are associated.

23. The apparatus of claim 22, wherein said first hash function is arranged to map a distinguished name of a managed object to a first hash code by a hash unit, which comprises:

a parsing unit, configured to parse the managed object'"'"'s distinguished name into a set of relative distinguished names, RDNs;

an index determination unit, configured to, for each RDN, determine a relative position i of said RDN within a code range of a MOC node to which the RDN belongs; and

a hash code generation unit, configured to generate the first hash code based on the relative position of each RDN.

24. An apparatus for searching data in a range of a hash table, wherein said hash table comprises a first level slot array with a constant number of slots and at least one second level slot array with a variant number of slots, each slot of the first level slot array being associated with a hash code range in the order of hash codes generated with a first hash function, and each slot of the first level slot array being linked to at most one second level slot array, said apparatus comprising:

a parameter obtaining unit, configured to obtain a start hash code and an end hash code which define the range of the hash table;

a range determination unit, configured to determine a slot range of the first level slot array, wherein a start slot of the slot range is associated with a hash code range to which the start hash code corresponds, and an end slot of the slot range is associated with a hash code range to which the end hash code corresponds;

a searching unit, configured to search hash entries in each second level slot array to which each slot within the slot range is linked; and

a result output unit, configured to return searched hash entries.

25. The apparatus of claim 24, wherein said parameter obtaining unit comprises:

a receiving unit, configured to receive a start key and an end key; and

a hashing unit, configured to generate the start hash code from the start key according to the first hash function and the end hash code from the end key according to the first hash function.

26. The apparatus of claim 24, wherein

said data includes network management information consisted of a set of managed objects, a managed object belongs to a managed object class, MOC, a set of MOCs is represented by an MOC tree based on parent-child inheritance relationships among the MOCs, the managed object'"'"'s distinguished name is used as a key, and the managed object'"'"'s data is a value associated with the key, and

said first hash function is arranged to map a distinguished name of a managed object to a first hash code, preserving an order where a hash code of any MO belonging to any MOC is larger than a hash code of any MO belonging to any parent MOC of the MOC, or a hash code of any MO belonging to any MOC is smaller than a hash code of any MO belonging to any parent MOC of the MOC.

27. The apparatus of claim 26, wherein said hash table is initialized by an initialization unit which is configured to:

traverse the MOC tree in an order that, for any MOC node, its ancestor MOC nodes are traversed prior to it;

for each traversed MOC node, allocate a code range based on a cardinal number of the MOC node and cardinal numbers of its all ancestor MOC nodes till a root node; and

divide a space consisted of the code ranges into hash code ranges with which the slots of the first level slot array are associated.

28. The apparatus of claim 27, wherein said parameter obtaining unit comprises:

a request receiving unit, configured to receive a retrieval request for retrieving data of a set of managed objects belonging to a given MOC, said retrieval request containing said given MOC'"'"'s name;

an MOC tree searching unit, configured to search the MOC tree for said given MOC to obtain its allocated code range; and

a start-end determination unit, configured to determine the start hash code as the start of the allocated code range, and the end hash code as the end of the allocated code range.

29. The apparatus of claim 27, wherein said parameter obtaining unit comprises:

a request receiving unit, configured to receive a retrieval request for retrieving data of a set of managed objects belonging to one or more MOCs, the managed objects of said set of managed objects being descendants from a given managed object, said retrieval request containing said given managed object'"'"'s distinguished name and a set of MOC names which are descendents of the given managed object'"'"'s MOC;

an MOC tree searching unit, configured to, for each descendent MOC, search the MOC tree for said descendent MOC to obtain its allocated code range;

a range extracting unit, configured to, for each descendent MOC, extract a hash code range corresponding to descendents of the given managed object from the allocated code range, based on a first hash code generated from the given managed object'"'"'s distinguished name according to the first hash function; and

a start-end determination unit, configured to, for each descendent MOC, determine the start hash code as the start of the extracted hash code range, and the end hash code as the end of the extracted hash code range.

30-33. -33. (canceled)