Searching for a path to identify where to move entries among hash tables with storage for multiple entries per bucket during insert operations

• US 7,827,182 B1
• Filed: 06/02/2004
• Issued: 11/02/2010
• Est. Priority Date: 06/02/2004
• Status: Expired due to Fees

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Panigrahy, Rina
• Primary Examiner(s): Cottingham; John R.
• Assistant Examiner(s): LOVEL, KIMBERLY M
• Application Number:
  US10/859,260
• Time in Patent Office: 2,344 Days
• Field of Search: 707/2, 707/999.002, 707/747, 709/238
• US Class Current: 707/747
• CPC Class Codes: G06F 16/10 File systems; File servers

Abstract

Entries are arranged in hash tables with storage for multiple entries per bucket with entries being shifted among hash tables to make room for entries being added. A path is determined through a search of the hash tables to identify where to move entries during insert operations among the hash tables to make room for a data item being added. Entries are moved and a data item added according to the identified path. Many different types of searches may be used, such as breadth-first, depth-first, random walk, etc. Also, a free position at the end of the path may be identified by being a bucket having a lowest occupancy level in a first predetermined number of levels of the search, a first bucket encountered having space available or an occupancy level less than a predetermined threshold level, with the predetermined threshold level typically being less than that of a full bucket, etc.

Claims

1. A method used in storing values in hash tables for use in hash-based lookup operations, the method comprising:

determining a first bucket within a first hash table of a plurality of hash tables based on hashing a particular data item using a first hash function, each of the plurality of hash tables including a plurality of buckets, each of the plurality of buckets sized to store a plurality of data items, the plurality of hash tables including the first hash table and a second hash table;

determining a second bucket within the second hash table based on hashing the particular data item using a second hash function;

in response to identifying that the first and second buckets are both full, performing a breadth-first search in the first and second hash tables from the first hash bucket to identify an identified bucket having space to add a data item along a path identified by said breadth-first search to the identified bucket, the breadth-first search including traversing buckets and data items stored within the first and second hash tables based on stored data items in each particular bucket encountered;

updating the first and second hash tables to move previously stored data items based on the path identified, including moving one of said previously stored data items to the identified bucket; and

adding the particular data item to the first hash bucket;

wherein said operation of updating the first and second hash tables is performed after completion of said performing said breadth-first search in the first and second hash tables.

2. The method of claim 1, wherein the breadth-first search traverses at least two bucket levels.

3. The method of claim 1, wherein the breadth-first search traverses at least three bucket levels.

4. The method of claim 1, comprising:

identifying a second particular data item;

determining a third bucket within the first hash table using the first hash function on the second particular data item;

determining a fourth bucket within the second hash table based on hashing the second particular data item using the second hash function;

in response to identifying an empty position in either the third or fourth bucket, storing the second particular data item in the empty position.

5. A method used in storing values in hash tables for use in hash-based lookup operations, the method comprising:

performing a breadth-first search in a plurality of hash tables to identify an identified bucket having space to add a particular data item along a path identified by said breadth-first search through the plurality of hash tables to the identified bucket, the breadth-first search including traversing buckets and data items stored within the plurality of hash tables based on stored data items in particular buckets encountered and traversing to buckets in different hash tables using corresponding hashing functions for each of the items stored in said particular buckets;

updating the plurality of hash tables to move previously stored data items based on the path identified including moving one of said previously stored data items to the identified bucket; and

adding the particular data item to the first bucket in the path identified;

wherein said operation of updating the plurality of hash tables is performed after completion of said performing the breadth-first search in the plurality of hash tables.

6. The method of claim 5, wherein the breadth-first search traverses at least two bucket levels.

7. The method of claim 5, wherein the breadth-first search traverses at least three bucket levels.

8. The method of claim 5, wherein said breadth-first search is performed for a predetermined number of levels, and the identified bucket is determined by selecting one of the buckets encountered during said breadth-first search with a lowest occupancy level.

9. The method of claim 8, wherein the predetermined number of levels is a constant value of at least two.

10. The method of claim 8, wherein the predetermined number of levels is a constant value of at least three.

11. The method of claim 5, wherein the identified bucket is the first bucket encountered with space available to store a data item.

12. The method of claim 5, including comparing an occupancy level of the identified bucket with a predetermined threshold occupancy level, the predetermined threshold occupancy level being less than the maximum number of data items that can be stored by the identified bucket.

13. A computer-readable medium tangibly encoded thereon computer-executable instructions for performing steps used in storing values in hash tables for use in hash-based lookup operations, said steps comprising:

performing a breadth-first search in a plurality of hash tables to identify an identified bucket having space to add a particular data item along a path identified by said breadth-first search through the plurality of hash tables to the identified bucket, the breadth-first search including traversing buckets and data items stored within the plurality of hash tables based on stored data items in particular buckets encountered and traversing to buckets in different hash tables using corresponding hashing functions for each of the items stored in said particular buckets;

updating the plurality of hash tables to move previously stored data items based on the path identified including moving one of said previously stored data items to the identified bucket; and

adding the particular data item to the first bucket in the path identified;

wherein said operation of updating the plurality of hash tables is performed after completion of said performing the breadth-first search in the plurality of hash tables.

14. The computer-readable medium of claim 13, wherein the breadth-first search traverses at least two bucket levels.

15. The computer-readable medium of claim 13, wherein the breadth-first search traverses at least three bucket levels.

16. The computer-readable medium of claim 13, wherein said breadth-first search is performed for a predetermined number of levels, and the identified bucket is determined by selecting one of the buckets encountered during said breadth-first search with a lowest occupancy level.

17. The computer-readable medium of claim 16, wherein the predetermined number of levels is a constant value of at least two.

18. The computer-readable medium of claim 16, wherein the predetermined number of levels is a constant value of at least three.

19. The computer-readable medium of claim 13, wherein the identified bucket is the first bucket encountered with space available to store a data item.

20. The computer-readable medium of claim 13, including comparing an occupancy level of the identified bucket with a predetermined threshold occupancy level, the predetermined threshold occupancy level being less than the maximum number of data items that can be stored by the identified bucket.

21. An apparatus used in storing values in hash tables for use in hash-based lookup operations, the apparatus comprising:

means for performing a breadth-first search in a plurality of hash tables to identify an identified bucket having space to add a particular data item along a path identified by said breadth-first search through the plurality of hash tables to the identified bucket, the breadth-first search including traversing buckets and data items stored within the plurality of hash tables based on stored data items in particular buckets encountered and traversing to buckets in different hash tables using corresponding hashing functions for each of the items stored in said particular buckets;

means for updating the plurality of hash tables to move previously stored data items based on the path identified including moving one of said previously stored data items to the identified bucket; and

means for adding the particular data item to the first bucket in the path identified;

wherein the apparatus is configured update the plurality of hash tables after completion of the breadth-first search in the plurality of hash tables.

22. The apparatus of claim 21, wherein the breadth-first search traverses at least two bucket levels.

23. The apparatus of claim 21, wherein the breadth-first search traverses at least three bucket levels.

24. The apparatus of claim 21, wherein said breadth-first search is performed for a predetermined number of levels, and the identified bucket is determined by selecting one of the buckets encountered during said breadth-first search with a lowest occupancy level.

25. The apparatus of claim 24, wherein the predetermined number of levels is a constant value of at least two.

26. The apparatus of claim 24, wherein the predetermined number of levels is a constant value of at least three.

27. A method used in storing values in hash tables for use in hash-based lookup operations, the method comprising:

performing a random walk in a plurality of hash tables to identify an identified bucket having space to add a particular data item along a path identified by said random walk through the plurality of hash tables to the identified bucket, the random walk including traversing buckets and data items stored within the plurality of hash tables based on stored data items in particular buckets encountered and randomly selecting one of the data items in an encountered bucket of said particular buckets and determining a next-level bucket using hashing function corresponding to a hashing table within the plurality of hashing tables that is different than the hashing table in which said one of the data items is currently stored;

updating the plurality of hash tables to move previously stored data items based on the path identified including moving one of said previously stored data items to the identified bucket; and

adding the particular data item to the first bucket in the path identified;

wherein said operation of updating the plurality of hash tables is performed after completion of said performing the random walk in the plurality of hash tables.

28. The method of claim 27, wherein the random walk traverses at least two buckets.

29. The method of claim 27, wherein the random walk traverses at least three buckets.

30. The method of claim 27, wherein the random walk is performed for a predetermined number of levels, and the identified bucket is determined by selecting one of the buckets encountered during the random walk with a lowest occupancy level.

31. The method of claim 30, wherein the predetermined number of levels is a constant value of at least two.

32. The method of claim 30, wherein the predetermined number of levels is a constant value of at least three.

33. A method used in storing values in hash tables for use in hash-based lookup operations, the method comprising:

performing a multi-level search in a plurality of hash tables to identify an identified bucket having space to add a particular data item along a path identified by said multi-level search through the plurality of hash tables to the identified bucket, the multi-level search including traversing buckets and data items stored within the plurality of hash tables based on stored data items in each particular bucket encountered and traversing to buckets in different hash tables using corresponding hashing functions for each of the items stored in an encountered bucket;

wherein said identification of the identified bucket having space to add the particular data item includes comparing an occupancy level of the identified bucket with a predetermined threshold occupancy level, the predetermined threshold occupancy level being less than the maximum number of data items that can be stored by the identified bucket;

updating the plurality of hash tables to move previously stored data items based on the path identified including moving one of said previously stored data items to the identified bucket; and

adding the particular data item to the first bucket in the path identified;

wherein said operation of updating the plurality of hash tables is performed after completion of said performing the multi-level search in the plurality of hash tables.

34. The method of claim 33, wherein the identified bucket is a first bucket encountered during the multi-level search that said comparison of the occupancy level of the identified bucket with the predetermined threshold occupancy level identified to add data item to the identified bucket.

35. An apparatus comprising one or more processors and memory, wherein the memory stores one or more instructions that, when executed by said one or more processors, perform operations for storing values in hash tables for use in hash-based lookup operations, including storing a particular data item, said operations comprising:

performing a multi-level search in a plurality of hash tables for a predetermined number of levels or until a low-occupancy bucket is encountered with an occupancy level at or below a predetermined threshold occupancy level, the multi-level search including traversing buckets and data items stored within the plurality of hash tables based on stored data items in each particular bucket encountered and traversing to buckets in different hash tables using corresponding hashing functions for each of the items stored in an encountered bucket;

using the low-occupancy bucket as an identified bucket or if no low-occupancy bucket was encountered in the multi-level search, then selecting a bucket with a lowest-occupancy level from the buckets encountered during said multi-level search as the identified bucket, an identified patch being defined as the path through the plurality of hash tables to the identified bucket;

updating the plurality of hash tables to move previously stored data items based on the identified path including moving one of said previously stored data items to the identified bucket; and

adding the particular data item to the first bucket in the identified path;

wherein the apparatus is configured to perform the operation of updating the plurality of hash tables after completing the operation of said performing the multi-level search in the plurality of hash tables.

36. A method used in storing values in hash tables for use in hash-based lookup operations, including storing a particular data item, the method comprising:

performing a multi-level search in a plurality of hash tables for a predetermined number of levels or until a low-occupancy bucket is encountered with an occupancy level at or below a predetermined threshold occupancy level, the multi-level search including traversing buckets and data items stored within the plurality of hash tables based on stored data items in each particular bucket encountered and traversing to buckets in different hash tables using corresponding hashing functions for each of the items stored in an encountered bucket;

using the low-occupancy bucket as an identified bucket or if no low-occupancy bucket was encountered in the multi-level search, then selecting a bucket with a lowest-occupancy level from the buckets encountered during said multi-level search as the identified bucket, an identified patch being defined as the path through the plurality of hash tables to the identified bucket;

updating the plurality of hash tables to move previously stored data items based on the identified path including moving one of said previously stored data items to the identified bucket; and

adding the particular data item to the first bucket in the identified path;

wherein said operation of updating the plurality of hash tables is performed after completion of said performing the multi-level search in the plurality of hash tables.