Method and apparatus using a binary search engine for searching and maintaining a distributed data structure

[0002] Data conversion tables frequently take the form of large tables of data having ordered index or “key” entries, each associated with a respective data entry or entries. Each key entry is for storing a key value, and each data entry is for storing a data value. Such a table is illustrated in FIG. 1, wherein the table is comprised of 1 to n key entries, each having an associated data entry. Thus, key entry 5 has a key value of A458 and an associated data entry has the data value of 1005 (key and data values being given in hexadecimal format unless otherwise noted).

[0003] A search value is used to return a desired data value from the table. The search value is compared to the key values in a specified order, and the desired data value is retrieved when a key value is located which correlates to the search value.

[0004] Tables such as illustrated in FIG. 1 are typically provided from a single physical memory element to simplify data retrieval and table maintenance. In this case, the key entries and the data entries are said to be “unified.” Operations affecting the table such as insertions and deletions are referred to “atomic operations” since both a key value and a data value or values are affected at the same time. Such tables have found wide use, such as for data unit address conversion in a variety of settings and data management in database applications.

[0005] Sequential processing of a unified data structure is possible, where a search begins at an upper or lower bound of the table and progresses until the desired key value is located or until the opposite bound is reached. The associated data value(s) is then retrieved if a match occurs. This approach is commonly referred to as a linear search.

[0006] Linear searching is impractical for large tables (i.e. tables having a relatively large number of entries) due to the length of time necessary to compare or “probe” a search value with the key value at each location. It is possible to suspend linear searching of an ordered table should the key values being compared go beyond the search value, indicating that the searched for value is not in the list. However, given an even chance of successfully finding any one of the key values, on average, half of the key values must be analyzed in performing a linear search.

[0007] To improve upon the performance of a linear search, ordered lists are commonly probed using a technique referred to as a binary search, a dichotomizing search in which the table to be searched is divided at each iteration into two equal, or nearly equal, parts. For instance, in an ordered list of twelve entries, a search for a particular search value begins at the sixth key entry. If the key value associated with the sixth key entry of the table is larger than the search value, the lower half of the table contains the searched for key value, if the key value is in the table at all. Otherwise, the key value is in the upper half of the table, if at all. Obviously, the search terminates if the value associated with the sixth key entry equals the search value. The divide by two and compare approach is repeated until the search value is matched to a key value, or it is established that there is no key value equivalent to the search value and the search is aborted.

[0008] Unified data structures such as in FIG. 1 are rarely static. Insertions in an ordered table can be performed by overwriting an existing set of key and data values with new values, or by executing a “shuffle up” operation. Deletions are performed by overwriting an existing set of key and data values with a new, dummy set of key and data values, or by executing a “shuffle down” operation. “Up” and “down” are relative directions based upon the ordering of the table.

[0009] The problem with inserting by overwriting lies in that it may be desired to keep the overwritten set of key and data values in the table. Thus, the overwritten pair must be rewritten in the next, higher set of entries. The process is repeated until a key/data value set is identified which does not need to be maintained in the table.

[0010] Alternatively, the shuffle up approach illustrated in FIG. 3 is employed for key and data value insertion. Here, it is desired to insert key value A457 and associated data value B321 into the first illustrated data structure. Key value FFFF may be regarded as a key value which is undesired, having any associated data value xxxx. In the second illustration, unified key and data values BCA2/0105 are copied into the next higher entries, formerly retaining “FFFF/xxxx”. In the third illustration, unified key and data values A458/1005 are copied into the entries formerly occupied by BCA2/0105. Finally, the new values A457/B321 are written into the entries formerly for A458/1005. The proper insertion point is assumed to have been identified by a binary search such as described previously.

[0011] A shuffle down operation for the purpose of removing a key/data value pair from the unified data structure is illustrated in FIG. 4. Here, it is desired to remove key value A457 and associated data value B321. In essentially the reverse of the shuffle up process described with regard to FIG. 3, key/data values A458/1005 are overwritten into the entries formerly occupied by the values to be removed. BCA2/0105 take the place of A458/1005, and a new key/data value pair, FFFF/xxxx, is inserted in the place of BCA2/0105. FFFF/xxxx may be dummy values, or new values which were being held for an opportunity to be inserted into the table. The shuffle up and shuffle down operations maintain the integrity of the data in the table so that other searches can be performed during insert and delete operations.

[0012] The number of entries in the key table can be indicated by a “limit” value or by the key values stored in the table. If a limit value is not used, unused key entries at the “top” of the table should be filled with a value which is greater than the highest currently used key value to enable the binary search. The unused entries can all have the same, greater value, or can have increasing values. Either way, the binary search process will search for desired key values in the correct manner.

[0013] A limitation to the typical binary search approach is that it only works for a table such as illustrated in FIG. 1 comprised of contiguous, ordered key values. If a key value is not ordered with respect to its neighbors, a binary search may be skewed, leading to the failure of the search.

[0014] A further drawback associated with unified data tables such as in FIGS. 1, 3 and 4 lies in the amount of memory required if plural data entries are associated with each key entry, or if the data entry or entries are relatively long, or both. Larger unified memory implies higher cost. Further, while memory densities continue to increase with time, a practical limitation will always exist on the size of the data entry or entries for a given key entry size, particularly if ASIC based memory arrays are used.

[0015] One proposed resolution to the limitations associated with a unified data table is the provision of a distributed data structure, whereby key values are resident in key entries in a discrete memory element, and respective data entries are located in a separate, discrete memory element. Key and data entries are associated through the use of a pointer field stored in conjunction with each key entry.

[0016] Shuffle up and down processes are performed on such distributed data structures as well, though atomic updates are still required in order for the data structure to be searched contemporaneously with table updates. Otherwise, it would be possible for a data entry to temporarily have a value not properly associated with a respective key value, for the search process to identify that key value as matching a search value, and for an incorrect data value to be retrieved.

[0017] The requirement for atomic updates for a distributed data structure utilizing pointers to associate respective key and data entries introduces problems in synchronizing the key and data value updates. This typically results in the lowering of update speeds for such structures. Lower update speeds necessarily limit the speed at which search values can be processed using the distributed data structure since the search function must wait for the update function to avoid retrieving incorrect data values. In the context of data communications, such speed limitations result in the need to provide input buffering due to the delays at the distributed data structure. Such buffering means increased cost, space requirements, and design complexity, and introduces the possibility of data loss due to buffer overflow. Additional overhead is consumed in maintaining the key entry-associated pointers.

[0018] It is thus desired to have a distributed data structure to avoid the data entry size limitations associated with a unified data structure, and to have the distributed data structure capable of being searched and updated simultaneously without the need for buffering incoming data due to delays associated with the update processes.

[0019] The present invention provides a distributed data structure in order to avoid the limitations associated with data entry size in unified data structures. Further, the present invention provides an indication of the validity of a data value or values associated with a given key value. This validity indication in a preferred embodiment is a bit set to a first value to indicate that the data value(s) associated with the key value is valid, and set to a second value to indicate that the data value(s) associated therewith are invalid.

[0020] The validity indication enables updates to the presently described distributed data structure to be performed asynchronously, or non-atomically, using a variant on the previously described shuffle up and shuffle down procedures. Specifically, while new key/data value sets are inserted into the data structure by moving existing key/data sets up, as previously described, each move is performed first on the key value, then on the associated data value(s). During the period when the key value has been moved, but not the data value, the key value is indicated as being invalid. Once the associated data has been updated, the key value is marked as being valid. Thus, retrieval of invalid data during a data structure update is avoided.

[0021] While affecting the data retrieval function performed using the presently disclosed distributed data structure, the validity indication associated with each key entry is ignored during binary search, except if the search value equals the present key value. If the search value equals a key value marked invalid, the search process moves either up or down, depending upon the embodiment, to the next probe location in the search sequence. Thus, the validity indication enables asynchronous updating of the distributed data structure without affecting contemporaneous searching and data retrieval. By enabling updating and searching at the same time, processing speed is optimized and the need for buffering input data units is removed, or at least reduced.

[0022] In addition, the validity indication allows the data structure to be sparsely populated. In known data structures, it is necessary when removing a key/data value set to move all other sets above the target set down to fill in the entries thus vacated. In the presently disclosed distributed data structure, it is possible to simply mark the key value as being invalid without shuffling any entries. Binary searching would be unaffected using the rules developed here for key value ordering, and invalid data is not retrieved. Similarly, given an invalid key entry in the proper location among the ordered key values, it is possible to insert a new key/data value set merely by overwriting an invalid key/data value set at that location. Data structure overhead is thus reduced, further obviating the need for input buffering due to data structure update delays.

[0023] The invention will be more fully understood by reference to the following description in conjunction with the accompanying drawings of which:

[0024] FIG. 1 illustrates a unified data structure as known in the art;

[0025] FIG. 2 illustrates a distributed data structure as presently disclosed;

[0026] FIG. 3 illustrates a shuffle up procedure as known in the art;

[0027] FIG. 4 illustrates a shuffle down procedure as known in the art;

[0028] FIGS. 5A and 5B illustrate an asynchronous shuffle up procedure for the distributed data structure of FIG. 2;

[0029] FIGS. 6A and 6B illustrate an asynchronous shuffle down procedure for the distributed data structure of FIG. 2;

[0030] FIG. 7 illustrates the operation of a binary search used in conjunction with the data structure of FIG. 2;

[0031] FIG. 8 illustrates an alternative embodiment of the binary search of FIG. 7;

[0032] FIG. 9 illustrates the ability to perform a binary search on a sparsely populated example of the data structure of FIG. 2; and

[0033] FIGS. 10 and 11 provide exemplary pseudocode routines for performing shuffle up and down procedures using the data structure of FIG. 2.

[0034] A data conversion table as known in the art is illustrated in FIG. 1. This single table is divided into two linear arrays, an array of 1 to n index or “key” entries, and a like number of data entries. Each key entry has an associated data entry. In other known configurations, each key entry has plural data entries. Each key entry retains a key value, and likewise each data entry retains a data value. The illustrative values shown in FIG. 1 are sixteen bits wide and presented in hexadecimal format, though other value lengths are employed as well.

[0035] As previously described, such prior art tables are commonly searched using a linear search or, depending upon the application, using a binary search algorithm.

[0036] FIG. 2 illustrates an improvement over the unified data structure of FIG. 1. Specifically, the data structure of FIG. 2 is divided into two discrete tables, a search table comprised of valid bits and the key entries having respective key values, and a data table comprised of the data entries having respective data values. As before, the width of the valid bits and the key and data entries can vary depending upon the requirements of the application. Further, there can be more than one data entry per data field, though for the sake of simplicity, only one sixteen bit wide data entry is shown per key entry. For example, key entry 3 in the search table has the key value of 813C (hex), and the associated data table entry has the data value 0309 (hex). In a first embodiment of the present invention, the search table, comprising the valid and key entries, and the data table, comprising the data entries, are disposed in respective memory elements. For example, in one embodiment, the data table is disposed in SRAM.

[0037] The valid bits associated with each key entry are illustrated in FIG. 2 as being a single binary digit. In a first embodiment, a value of one indicates that the data value(s) associated with the respective key entry is valid and capable of being retrieved as part of a data conversion operation, to be discussed in greater detail below. A value of zero for the valid bit indicates that the data value is invalid and cannot be retrieved during the data conversion operation. However, a key value is still employed for the purposes of searching the search table, even if an associated valid bit (or bits) indicate that the associated data value is invalid.

[0038] The length of the search and data tables is irrelevant to the presently disclosed invention, and can be specified according to the needs of the particular application. In one embodiment, the search table has 128 entries stored in an ASIC-based memory structure and the data table has 16,384 entries stored in a discrete SRAM device.

[0039] Each data entry in the data table of FIG. 2 is associated with a respective key entry in the search table based upon the relative position of the key entry within the search table. For instance, since A457 is the key value for entry 4 in the search table, 1008 is the respective data value, being the fourth entry in the data table. As illustrated, the entry number for the search table is used to address the data table. This fixed association of data table entries to search table entries avoids the necessity of employing and maintaining address pointers associated with each key entry to the respective data entry or entries. Accessing data associated with a key entry is thus quicker and requires less hardware in terms of, for instance, ASIC gates. In one embodiment, the position value of a key entry is included in a hash function to select a cache entry, or a set of cache entries, associated with the respective key entry.

[0040] A significant benefit of providing the data structure distributed across two tables is that each can be provided within a separate memory device. In the case where the data table is relatively large, placing the valid, key and data fields within a single memory device can significantly increase the cost of the apparatus due to the premium placed on higher density memory devices. Thus a cost savings is realized by physically separating the search table from the data table. However, in certain circumstances, such as where the memory requirements of the data table are not particularly large, it may be more economical to dispose the search table and the data table in the same device.

[0041] Separation of the search and data tables also facilitates the independent, asynchronous searching and accessing of the two tables, since separate clock, address and data lines are provided to each when they are disposed apart.

[0042] Binary searching was described above in the context of the prior art. With regard to FIG. 7, binary searching is described with respect to the distributed data structure now disclosed. In the illustrated embodiment, there are twelve entries in each of the search and data tables, though in practice, it is expected that there would be significantly more entries.

[0043] A value being used as an index into the distributed data structure is referred to herein as a search value. With regard to FIG. 7, assume that the search value is A457. Binary searches generally operate according to the following formula: $P_N=\frac{N_T-P_P}{2}$

[0044] N_T=number of entries in table

[0045] P_N=offset for next entry to be probed

[0046] P_P=number entries encompassed by prior probes

[0047] This is also referred to as finding the order of log base 2 of N, or “O log₂(N)”.

[0048] Thus, in FIG. 7, searching for A457: $P_1=\frac{12-0}{2}=6$

[0049] The key value at entry six (point “A” in FIG. 7) equals BCA2, which is greater than the search value. The equation is executed again to find the next probe point below the present probe point. $P_2=\frac{12-6}{2}=3$

[0050] The key value at the next probe point, entry 3 (point “B” in FIG. 7) is 813C, lower than the search value. The fact that the valid bit equals zero, indicating that the associated data value is invalid, is irrelevant to this probe operation.

[0051] The formula is repeated to determine the next probe point above the current probe point. $P_3=\frac{12-\left(6+3\right)}{2}=1.5$

[0052] It is possible to probe the entry above or below the returned probe point, though the choice should always be made uniformly. Here, the number of entries to skip to the next probe point is rounded up, resulting in a directive to move up two entries to entry five, or point “C” in FIG. 7. The key value of A458 is still above the search value of A457, so the formula is repeated. $P_4=\frac{12-\left(6+3+2\right)}{2}=0.5$

[0053] Adhering to the convention of rounding up, the next probe point, entry four (point “D” in FIG. 7), contains a key value of A457, which is the search value. The valid bit in the respective valid entry indicates that the associated data value is valid, and that data value (1008) is available for retrieval.

[0054] Consider the case where entry four of the search table of FIG. 7 contains a key value of A456 instead of A457. The search would not have made a match, and this information would be returned to a process which initiated the search.

[0055] In another situation, the key value for entry four does match the search value as illustrated, though the valid bit is not set, indicating that the associated data is not valid. This, too, would be reported to the responsible process. The use of the valid bit is further explained below.

[0056] In an alternative embodiment of the present invention, the total number of entries in the tables is known, and the first probe point is predefined as being the midpoint of the table. With reference to FIG. 8, there are 128 entries in the search and data tables, as shown. Rather than executing the algorithm referenced above in order to find the first probe point, and thereby unnecessarily consuming clock cycles, the first probe point is predetermined to be at entry 64 (point “A” in FIG. 8). Thereafter, the appropriate half of the distributed data structure is treated as if it were a 64 entry long table.

[0057] The presently disclosed conversion tables are used in one embodiment in a data communications network switch operating at high data rates. Therefore, it is imperative that the conversion table be available at all times for data conversion at received data rates, despite the fact that table maintenance must be performed. If this capability to process data at line speed were not provided, expensive and complex buffering would be necessitated.

[0058] As mentioned, the valid entries are utilized to enable the performance of table maintenance in the “background” while the table is being searched in the “foreground.” A typical key/data entry insert operation is illustrated with respect to FIGS. 5A and 5B. It is desired in this example to insert key value A5A5 and associated data value 8765 into the table structure initially illustrated. In this preferred embodiment, the condition of a search value matching a key value that is marked invalid causes the search to respond as if the key value is greater than the search value.

[0059] It is necessary to push entries having a key value greater than the new key value, A5A5, up in the table to make room for the new value. As illustrated, the key value having a valid bit set to zero above and closest to the target point of insertion is identified. This is key value FFFF in FIG. 5A. The key value in the entry just below that of key value FFFF, or key value BCA2, is copied and written over FFFF (10). The associated valid bit remains set to zero.

[0060] The data value for key value BCA2, or 0105, is then copied into the data entry associated with the copy of key value BCA2 (12). Once the data value has been copied, the associated valid bit is set to one (14) indicating that if the associated key value is probed and matches a search value, this data value is valid and available for retrieval.

[0061] Note that at this point, there are two copies of the same key value/data value pair, occupying contiguous locations in the bifurcated table, and both marked as being valid. This does not have a negative impact on either table probing or on data conversion. The data is merely redundant.

[0062] Essentially the same procedure is employed to make room for the new key/data pair. The new key value A5A5 is written into the target entry and is marked as invalid (16) to avoid the return of mismatched data, since probe operations are capable of being performed during the presently described insertion routine.

[0063] Then, the associated data value, 8765, is written into the respective data entry (18). Lastly, the valid bit is set to one (20), indicating that the data associated with the new entry is now available for retrieval as part of a data conversion operation. The shuffle up operation is summarized in FIG. 10. Step 2 is included to support data structures with a variable number of data entries per key entry. All data entries associated with key entry n+1 must be removed before copying the entries associated with key entry n.

[0064] A key/data pair removal operation is illustrated in FIGS. 6A and 6B. Here, it is desired to remove key value A5A5 and associated data value 8765 (30). In a single write operation, the valid bit for the relevant entry is reset and the key value is overwritten with the value from the next higher key/data pair (32) decremented by one. In a subsequent write operation, the data value associated with the newly written key value is copied into the respective data entry (34). Since the search and data tables are disposed on separate memory elements, there is no need to attempt to synchronize the updating of the key and data values. As long as these values are not properly written, the valid bit will remain reset. The decrement operation is required to preserve the binary search since invalid but equal key values cause the search to probe lesser key values in this embodiment.

[0065] Once the data values have overwritten the data values to be removed, the valid bit is set for that entry (36) and the key value is incremented by one.

[0066] Finally, the next higher entry is made available for further insertions by being set to any appropriately higher key value and by resetting the associated valid bit to zero (38). The data value for this entry is irrelevant. Alternatively, the next higher key/data value pair can be copied down into the now invalid entry, and the process repeated until the highest, valid key value has been copied downward, thus leaving expansion room at the top of the distributed table. This shuffle down operation is summarized in FIG. 10. As with the shuffle up operation, step 2 is included to support a variable number of data entries per key entry. Invalid or dummy values inserted at the top of the distributed data structure are preferably given maximum key values to enable the binary search. It is possible that there is an extended block of invalid entries at the top of a partially populated table according to the present embodiment, each having the same maximum key value and having a reset valid bit (or other indication reflecting invalid associated data).

[0067] In an alternative embodiment, the key/data value pair to be removed is effectively done so merely by setting the respective valid bit to zero, but leaving the key and data values in place. This results in a sparsely populated, distributed table.

[0068] While the prior art is incapable of searching such a sparsely populated table because of the impact of gaps on the binary search algorithm, the presently disclosed invention can still search using invalid key values, though for data retrieval purposes, the associated data is invalid. In FIG. 9, a distributed data structure according to the present invention is illustrated in which two extended invalid regions are shown. The associated data values are effectively removed from the data structure for data retrieval purposes, but the keys are used to direct the binary search. This results in the sparsely populated table referenced above.

[0069] Certain benefits flow from the utilization of a sparsely populated table, including the increased likelihood that an “open” key/data entry pair is near a location where one wishes to insert a new key/data value pair. It is also possible that the desired insertion point is presently occupied by an invalid key/data value pair, and no shuffling is required; the new key/data values are merely written into the target entries. The sparsely populated table thus minimizes processing time required to shuffle up and shuffle down.

[0070] In an alternative embodiment, the boundary condition of a search value matching an invalid key value can cause the search to proceed as though the key value is less than the search value. The shuffle up and shuffle down mechanisms are summarized in FIG. 11 for this embodiment. An interesting boudnary condition arises in this case. The maximum value of the key will be stored in the last location of the key table. This results naturally from the algorithms described.

[0071] Certain protocols must be defined and adhered to consistently. For instance, it must be predetermined what to do if an index value equals a search value, but the associated valid bit indicates that the respective data value(s) is invalid. In one embodiment of the presently disclosed invention, which works with the insertion and removal procedures described with respect to FIGS. 5A, 5B, 6A and 6B, the next lower entry in the search sequence is probed for the search value. For instance, at reference 10 of FIG. 5A, a comparison of the upper key value of BCA2 and the same search value returns a match, but the valid bit is set to zero. By continuing the search in the lower portion of the table, the same key value is found, with an associated valid bit set. Since valid bits and key values can be written at the same time (i.e. atomically), the case where a searched-for key value is marked invalid, while the same key value marked valid is above it, will not occur.

[0072] These and other examples of the invention illustrated above are intended by way of example and the actual scope of the invention is to be limited solely by the scope and spirit of the following claims.