Efficient Bloom filter

Implementation of a Bloom filter using multiple single-ported memory slices. A control value is combined with a hashed address value such that the resultant address value has the property that one, and only one, of the k memories or slices is selected for a given input value, a, for each bank. Collisions are thereby avoided and the multiple hash accesses for a given input value, a, may be performed concurrently. Other embodiments are also described and claimed.

BACKGROUND

1. Technical Field

The present disclosure relates generally to information processing systems and, more specifically, to a low-collision Bloom filter.

2. Background Art

A Bloom filter is a probabilistic algorithm to quickly test membership in a large set using multiple hash functions into an array of bits. The use of Bloom filters is known in the art, and originates from the seminal paper written by B. Bloom, “Space/Time Trade-Offs in Hash Coding with Allowable Errors,”Comm. ACM, vol. 13, no. 7, May 1970, pp. 422-426.

Bloom filters are space-efficient structures that support fast constant-time insertion and queries. A Bloom filter supports (probabilistic) membership queries in a set A={a1, a2, . . . , an} of n elements (also called keys).

A Bloom filter quickly filters (i.e., identifies), non-members without querying the large set by exploiting the fact that a small percentage of erroneous classifications can be tolerated. When a Bloom filter identifies a non-member, it is guaranteed to not belong to the large set. When a Bloom filter identifies a member, however, it is not guaranteed to belong to the large set. In other words, the result of the membership test is either: it is definitely not a member, or, it is probably a member.

DETAILED DESCRIPTION

The following discussion describes selected embodiments of methods, systems and mechanisms to implement a low-collision Bloom filter using single-ported memory banks. The apparatus, system and method embodiments described herein may be utilized with single-core or multi-core systems. In the following description, numerous specific details such as processor types, multicore system configurations, and circuit layout have been set forth to provide a more thorough understanding of embodiments of the present invention. It will be appreciated, however, by one skilled in the art that the invention may be practiced without such specific details. Additionally, some well known structures, circuits, and the like have not been shown in detail to avoid unnecessarily obscuring the present invention.

FIG. 1is a block diagram illustrating a traditional Bloom filter100with four hash functions120a-120d. The basic idea is to allocate a vector v of m bits, initially all set to 0, and then choose k independent hash functions, h1, h2, . . . , hk, each with range {1, . . . , m}.

The Bloom filter100illustrated inFIG. 1is implemented with a multi-ported memory150, where the memory150has k ports. In this manner, the k array positions104,106,108,110of the memory150may be written or queried in parallel.

The left-hand side ofFIG. 1illustrates insertion of an element (a) into a set (A). To insert an element a ε A, the bits (104,106,108,110, respectively) at positions h1(a), h2(a), . . . , hk(a) in v are set to “1”. (A particular bit might be set to “1” multiple times). It should be understood that “1” or “true” as used herein is not intended to be limited to any particular value. For at least one embodiment, the value “1” is implemented as a one-bit logic-high value. However, this example embodiment should not be taken to be limiting. Instead, for alternative embodiments the “1” value may be a logic-low value or may be a multi-bit value.

The right-hand side ofFIG. 1illustrates a query to determine if an element (b) is a member of the set (A).FIG. 1illustrates that, to query for an element (to test if it is in set A), the element is fed into each of the k hash functions, resulting in k bit positions. Given a query for b, the bits (106,107,111,105, respectively) at positions h1(b), h2(b), . . . , hk(b) are checked. Again, because the Bloom filter100illustrated inFIG. 1is implemented with a k-ported memory150, the k array positions (positions h1(b), h2(b), . . . , hk(b)) may be checked in parallel.

If any of the bits is “0”, then b is not in the set A. (If the element were in the set, then presumably all such bits would have been set to “1” when the element was added to the set). Otherwise, if all bits are “1”, then either the element is in the set, or the bits have been set to “1” during the insertion of other elements. Thus, if all bits are set to “1”, it may be assumed that b is in the set although there is a certain probability that this is not true (because the bits may have been set during the insertion of other elements). The (relatively rare) case in which the bits are set for the insertion of other elements, is called a “false positive” or “false drop”, when the query erroneously indicates membership in the set for element b.

Bloom filters may be used in a wide variety of applications. They may be used, for example, to minimize expensive searches in a Web server by maintaining a set of cached objects. Also, for example, Bloom filters may be used in network packet processing to detect packet sub-strings. They may also be used, for example, in various cache schemes. Regarding caches, they may be used, for example, to estimate cache hit probability in order to aid in speculation regarding the scheduling of long-latency operations in an out-of-order processor, to implement set-associative caches, to reduce snooping in multi-processor snoop-based coherence protocols.

Many of the current implementations of Bloom filters, including those for some of the applications discussed in the preceding paragraph, rely on multi-ported memories (such as150illustrated inFIG. 1) or multi-banked memories in order to compute the hash functions in parallel. If, instead, a Bloom filter were implemented with a single-ported memory, the query for each of the k hashes must occur serially, which is a relatively slow approach.

In contrast, with multi-ported memories the k hash functions may be computed in parallel, and each of the k bits of the hash may be checked in parallel via k memory ports as described above. However, multi-ported memories typically incur relatively higher cost in terms of power and area. Thus, they are fast but are big and expensive.

An alternative is to break the Bloom filter up into k smaller memories, each with its own port. However, this multi-banked memory implementation of Bloom filters may restrict the range (1 . . . m) of hash functions, thus increasing the probability of false positives.

For both multi-ported and multi-banked implementations, if accessed in parallel, there is a risk of collisions if two of the hash functions attempt to access a single port at the same time.

FIG. 2is a block diagram illustrating a sample embodiment of a multi-banked Bloom filter implementation that avoids the cost of using multi-ported memories. While the Bloom filter200shown inFIG. 2is logically the same as that100shown inFIG. 1,FIG. 2illustrates that the physical implementation of the Bloom filter200is different. That is, the embodiment200illustrated inFIG. 2utilizes k single-ported memory banks1601-160krather a single k-ported memory150(FIG. 1).

Like the multi-ported implementation100illustrated inFIG. 1, the physical organization of the k-banked Bloom filter200illustrated inFIG. 2allows parallel computation of the hash functions120a-120d. However, the k-banked implementation200may suffer a higher false positive probability than the k-ported implementation100illustrated inFIG. 1. There is a clear tradeoff between m (the size of the Bloom filter) and the probability of a false positive.

The k-ported memory150implementation100shown inFIG. 1has a false positive probability of (1−e−kn/m)k. In contrast, theFIG. 2implementation200using k single-ported memory banks1601-160kwill have a much higher probability of false positives (due to the higher rate of collisions as a consequence of the smaller size of each Bloom Filter).

To find the probability of false positives where n is the number of accesses to one bank160for theFIG. 2physical implementation, the following equation may be used:
(1−(1−1/m)kn)k(1)
Note that

Since there are ‘k’ banks in theFIG. 2embodiment200, the probability of false positives in such embodiment200is therefore:
(1−(1−k/m)n)k(2)

From equations (1) and (2) it is seen that the embodiment200illustrated inFIG. 2has a higher probability of false positives than the k-ported embodiment100illustrated inFIG. 1.

Thus, a physical implementation of a Bloom filter using multiple banked single-ported memories is a lower-cost alternative to a multi-ported memory, while still allowing parallel computation of hash functions. However, in such multi-banked implementations, each bank has a smaller range for ‘m’ in each bank than a single multi-ported bank, thereby raising the probability of false positives.

FIG. 3is a block diagram illustrating a Bloom filter implementation technique that preserves the range of hash functions (e.g., achieving the same resilience to false positives as a k-ported implementation) in contrast to the multi-banked implementation200discussed above, while at the same time allowing the use of multi-banked single-ported memories, thus enabling parallel computation of hash functions for a Bloom filter. The Bloom filter implementation300illustrated inFIG. 3thus achieves the collision probability of multi-ported memory implementations while using k single-ported memories.

FIG. 3illustrates that the Bloom filter300includes k hash circuits3021-302k. Each of the hash circuits3021-302kof the Bloom filter is devised implement a hash function (H1(a)-Hk(a), respectively), where each of the hash functions ranges over the whole set of bits in the filter (from bits1to m). In order have k single-ported memory banks without collision, the hash functions H1(a)-Hk(a) are also devised to guarantee that, if one of the k bits hashes to a particular one of the k banks, none of the other bits will hash to that particular bank.

For example, if function H1(a) hashes to a bit in the second bank (1602), then function H2(a), by design, hashes to a bit in one of the other banks (1601or1603-160k). Similarly, function H3(a) is devised such that whenever H1(a) and H2(a) have chosen bits in two banks, then H3(a) chooses a bit in one of the two remaining banks. Finally Hk(a) chooses a bit in the remaining bank that has not already been chosen. Each Hifunction hashes the input value a over m/k bits.

The hash functions may each be part of a set of bits that, when combined with a control value (also referred to herein as “selector bits”), are devised such that, mathematically, each of the combined values for a given input value, a, is guaranteed to pick a different one of the k banks (1601through160k). This combined set of bits is referred to herein as a “combined bit value”. For at least one embodiment, this particular feature of the combined bit value is realized by using certain bits within the combined bit value as selector bits to select a unique one of the remaining memory banks1601through160kthat has not already been selected by any of the combined bit values for a particular value of a. Any bits of the combined bit value may used as selector bits.

For at least one embodiment, the selector bits are generated by a control circuit306, which implements a bank selection control function, Hc. That is, the circuit306generates a control value. A control value generated by the hash function Hc, which is implemented in control circuit306, may be appended onto the values generated by hash functions H1through Hk, at the end or beginning or at any intermixed location with the hash values generated by the hash circuits3021-302k. That is, each of the hash values may be combined with a control value in any manner (pre-pended, appended, or intermixed) to generate a combined bit value. The combined bit value has the property that it uniquely selects one of the k memories for any given input value, a, and therefore avoids collisions for the value a.

The example embodiment300illustrated inFIG. 3uses an extra hash function Hc(a), implemented by circuit306, to select the target bank (from1601through160k) for each hash function. The output of function Hc(a) controls a multiplexer3041-304kon the address input for each bank1601-160k. The mux selection is set up such that, for a given control value, Hc(a), each bank1601through160kselects a different input.

While the following example is discussed in connection with a sample embodiment having k=4 single-ported banked memories1601-160k, one of skill in the art will understand that such example is not intended to be limiting but is instead set forth for explanatory purposes only. The embodiment illustrated inFIG. 3may utilize more or fewer memory banks.

For a four-bank embodiment, for example, a simple Hc(a) could use the value of a to select one of the 24 permutations of (0, 1, 2, 3) for the four muxes3041-304k. For the embodiment illustrated inFIG. 3, the hashing functionality for the Bloom filter mathematically combines the hash value and the control value. This organization is more resilient to artifacts in the hashing functions. For example, if one hashing function turns out to be ill-suited for a given input, the controlling hash function Hcmaps that function over k banks, thus reducing the probability of collisions.

WhileFIG. 3illustrates the selection of banks1601-160kvia a hardware circuit, it should be understood that alternative embodiments may perform such selection via software logic, firmware, or any combination of hardware, firmware and/or software. For instance, at least on alternative embodiment of the Bloom filter illustrated inFIG. 3may implement one or more of the hash functions H1(a)-Hk(a) and/or Hc(a) as software modules3021-302k, rather than as hardware circuits.

FIG. 4is a block diagram of a first embodiment of a system400capable of performing disclosed techniques. The system400may include one or more processors370,380, which are coupled to a north bridge390. The optional nature of additional processors380is denoted inFIG. 4with broken lines.

First processor370and any other processor(s)380(and more specifically the cores therein) may include Bloom filter logic402in accordance with an embodiment of the present invention. For a first embodiment, the Bloom filter logic402may be hardware circuitry (see, e.g.,300ofFIG. 3). Alternatively, rather than being a hardware circuit, the Bloom filter logic402may be one or more software or firmware modules. At least one embodiment of a software embodiment of the Bloom filter logic disclosed herein is discussed below in connection withFIGS. 6 and 8.

The north bridge390may be a chipset, or a portion of a chipset. The north bridge390may communicate with the processor(s)370,380and control interaction between the processor(s)370,380and memory332. The north bridge390may also control interaction between the processor(s)370,380and Accelerated Graphics Port (AGP) activities. For at least one embodiment, the north bridge390communicates with the processor(s)370,380via a multi-drop bus, such as a frontside bus (FSB)395.

FIG. 4illustrates that the north bridge390may be coupled to another chipset, or portion of a chipset, referred to as a south bridge318. For at least one embodiment, the south bridge318handles the input/output (I/O) functions of the system300, controlling interaction with input/output components. Various devices may be coupled to the south bridge318, including, for example, a keyboard and/or mouse322, communication devices326and flash memory350which may include code BIOS code355, in one embodiment. Further, an audio I/O324may be coupled to the south bridge318, as may be other I/O devices314.

Embodiments of the present invention may be implemented in many different system types. Referring now toFIG. 5, shown is a block diagram of a multiprocessor system in accordance with an embodiment of the present invention. As shown inFIG. 5, the multiprocessor system is a point-to-point interconnect system, and includes a first processor470and a second processor480coupled via a point-to-point interconnect450. As shown inFIG. 5, each of processors470and480may be multicore processors, including first and second processor cores (i.e., processor cores474aand474band processor cores484aand484b). While not shown for ease of illustration, first processor470and second processor480(and more specifically the cores therein) may include Bloom filter logic in accordance with an embodiment of the present invention (see, e.g.300ofFIG. 3; see, e.g.,600ofFIG. 6; see, e.g.,800ofFIG. 8).

Rather having a north bridge and south bridge as shown above in connection withFIG. 4, the system500shown inFIG. 5may instead have a hub architecture. The hub architecture may include an integrated memory controller hub Memory Controller Hub (MCH)472,482integrated into each processor470,480. A chipset490may provide control of Graphics and AGP.

Thus, the first processor470further includes a memory controller hub (MCH)472and point-to-point (P-P) interfaces476and478. Similarly, second processor480includes a MCH482and P-P interfaces486and488. As shown inFIG. 5, MCH's472and482couple the processors to respective memories, namely a memory432and a memory434, which may be portions of main memory locally attached to the respective processors.

While shown inFIG. 5as being integrated into the processors470,480, the memory controller hubs472,482need not necessarily be so integrated. For at least one alternative embodiment, the logic of the MCH's472and482may be external to the processors470,480, respectively. For such embodiment one or more memory controllers, embodying the logic of the MCH's472and482, may be coupled between the processors470,480and the memories432,434, respectively. For such embodiment, for example, the memory controller(s) may be stand-alone logic, or may be incorporated into the chipset490.

First processor470and second processor480may be coupled to the chipset490via P-P interconnects452and454, respectively. As shown inFIG. 5, chipset490includes P-P interfaces494and498. Furthermore, chipset490includes an interface492to couple chipset490with a high performance graphics engine438. In one embodiment, an Advanced Graphics Port (AGP) bus439may be used to couple graphics engine438to chipset490. AGP bus439may conform to theAccelerated Graphics Port Interface Specification, Revision2.0, published May 4, 1998, by Intel Corporation, Santa Clara, Calif. Alternately, a point-to-point interconnect439may couple these components.

In turn, chipset490may be coupled to a first bus416via an interface496. In one embodiment, first bus416may be a Peripheral Component Interconnect (PCI) bus, as defined by thePCI Local Bus Specification, Production Version, Revision2.1, dated June 1995 or a bus such as the PCI Express bus or another third generation input/output (I/O) interconnect bus, although the scope of the present invention is not so limited.

As shown inFIG. 5, various I/O devices414may be coupled to first bus416, along with a bus bridge418which couples first bus416to a second bus420. In one embodiment, second bus420may be a low pin count (LPC) bus. Various devices may be coupled to second bus420including, for example, a keyboard/mouse422, communication devices426and a data storage unit428which may include code430, in one embodiment. Further, an audio I/O424may be coupled to second bus420. Note that other architectures are possible. For example, instead of the point-to-point architecture ofFIG. 5, a system may implement a multi-drop bus or another such architecture.

FIG. 6is a flowchart illustrating at least one embodiment of a method600for performing Bloom filter logic in a multi-core processing system. For at least one embodiment, the method600is performed concurrently by multiple processors in the multi-core system. It will be understood by one of skill in the art that the blocks of the method600are shown in a particular order merely for convenience, and that the operations need not necessarily be performed in the order shown.

FIG. 6illustrates that the method600begins at block602and proceeds to block604. At block604, the processor that is executing the method600determines its unique identifier, which distinguishes the processor from other processor cores in the system. Processing then proceeds to block608.

At block608, the processor that is performing the method600determines the size of the slice of the Bloom filter array that has been partitioned for each processor. For example, if the bloom filter array has m memory locations, and there are k processors, then the slice size may be determined at block608to be of size m/k.

Processing then proceeds to block609, where a control module is executed. For at least one embodiment, the control module calculates, for each processor, a unique one of the slices to be used for the hashing operation to be performed (e.g., add, delete, or query). It should be noted that the logic of the control module is such that any one of the processor may be assigned to any slice—that is, each of the processors has access to the full range of the Bloom filter array entries. However, the control module logic is such that, once a particular slice is selected for one of the processors, that same slice is not selected for any other processor during the hashing function for a given input value. From block609, processing proceeds to block610.

At block610, a hash module is performed in order to determine a particular address within the slice that is to be written. Processing then proceeds to block612.

At block612, the output of the control module, calculated at block609, and the output of the hash module, calculated at block610, are combined. The manner of combination is a matter of design choice and is not limited herein. For example, for at least one embodiment the output of the control module may be pre-pended or appended to the output of the hash function. For at least one other embodiment, the outputs of the control and hash modules may be intermixed to create a combined value. At block612, this combined value is generated in order to provide a value that indicates a particular address in a particular slice of the Bloom filter array. Processing then proceeds to block614.

At block614, the processor that is performing the method600utilizes the combined value created at block612in order to access the appropriate slot in the Bloom filter array in order to perform the processor's part of the desired operation. For example, the processor may add a value to the Bloom filter by placing a non-null data value into the selected address of the selected slice. Or, the processor may increment an integer value in the selected address of the selected slice in order to add an item to the Bloom filter. Similarly, at block614the processor may delete an item from the Bloom filter by placing a null data value into the selected address of the selected slice. Or, the processor may decrement an integer value in the selected address of the selected slice in order to delete an item to the Bloom filter. Alternatively, at block614the processor may perform a query to determine whether there exists a non-null value in the selected address of the selected slice.

As is stated above, it is intended that the other processors of the system may concurrently perform the method600in order to perform their part of the desired operation. Processing then ends at block616.

FIG. 7is a block diagram illustrating at least one embodiment of a Bloom filter implementation in a system700that includes multiple processor cores. The number of cores is represented by variable k. AlthoughFIG. 7depicts k=four processor cores (470,472,474,480), such depiction is for illustrative purposes only. The number of processor cores, k, may be any positive integer greater than or equal to 2.

All m bits of the Bloom filter array are702are accessible to be hashed to by any of the k multiple cores. For at least one embodiment, the m bits are evenly distributed among k slices, such that each of the k slices is of size m/k bits,4601-460k. Accordingly, for a system700including k processor cores, each processor core computes the hash value (for a given input α) for one of the k slices (4601-460k) of the Bloom filter. However, each processor has access to the entire range of the Bloom filter array, so that for any input value a, the control function may assign any of the k slices to any of the k processors, with each processor being assigned a different one of the slices for a given input value, α.

Each of the processors cores470,472,474,480may include Bloom filter logic modules471,473,475,481, respectively to compute the control value (see, e.g., block609ofFIG. 6) and to compute the hash functions, (see, e.g., block610ofFIG. 6). Each of the processor cores470,472,474,480may execute its Bloom filter logic modules471,473,475,481, respectively, concurrently with one or more, or all, of the other cores.

FIG. 7illustrates that the multiple processor cores470,472,474,480may be part of a single chip package799, thereby constituting a chip multi-processor. The chip package799may also include the Bloom filter memory array702as part of the on-chip portion (such as a cache) of a memory hierarchy. Alternatively, the Bloom filer memory array702may be off-chip.

FIG. 8is a table diagram illustrating at least one embodiment of Bloom filter logic800that may executed by each processor in a multiprocessor system, such as the logic modules471,473,475,481executed by the cores470,472,474,480, respectively, of multiprocessor system700illustrated inFIG. 7. At least one embodiment of the logic700ofFIG. 7is shown inFIG. 8as pseudocode software instructions.

That is, for at least one embodiment, the Bloom filter logic800may be implemented as a set of tangible computer-accessible instructions, organized as software logic modules, embodied in a computer program product. The instructions, when executed by the processors of the multiprocessor system, perform Bloom filter processing that utilizes multiple processors in order to make even very long Bloom filter calculations more efficient. The Bloom filter logic800illustrated inFIG. 8is designed to decrease coherence overhead. The specific code instructions illustrated inFIG. 8are intended to be illustrative pseudocode only; the specific instructions, syntax and labels used inFIG. 8should be taken to be limiting.

The pseudocode instructions illustrated inFIG. 8are grouped into logic modules that are intended to illustrate at least one embodiment of pseudocode instructions for software logic modules to implement at least one embodiment of the software Bloom Filter logic illustrated inFIG. 6.

FIG. 8illustrates that the Bloom filter logic800includes a declaration of the Bloom filter as an array of m integer elements.FIG. 8also illustrates a function, Hash, that returns an integer value. The Hash function illustrated inFIG. 8may, for at least one embodiment, roughly coincide with the logic blocks604,608,609,610, and612illustrated inFIG. 6.

More particularly,FIG. 8illustrates pseudocode instructions for an ID Module802, which provides logic to be executed during block604ofFIG. 6.

FIG. 8also illustrates pseudocode instructions for a Slice Size Module806, which provides logic to be executed during block608ofFIG. 6.

FIG. 8also illustrates pseudocode instructions for a function call to a control module,808, to be executed during block609ofFIG. 6. Such control module808selects a unique slice for the processor, such that none of the other processors will hash to the selected slice of the Bloom filter for a given input value, a.

FIG. 8also illustrates pseudocode instructions for a Hash Module804, which module, logic to be executed during block610ofFIG. 6.

FIG. 8also illustrates pseudocode instructions for a Combine Module808, which provides logic to be executed during block612ofFIG. 6.

One of skill in the art will realize that the presentation of the logic800in psuedocode form inFIG. 8should not be taken to be limiting. For at least one other embodiment, such logic800may be implemented via hardware circuit, or in firmware, or a combination of hardware, firmware and/or software.

The simplified pseudocode represented inFIG. 8assumes that the array size, m, is a multiple of k in order to simplify the presentation.

Program code may be applied to input data to perform the functions described herein and generate output information. Accordingly, alternative embodiments of the invention also include machine-accessible media containing instructions for performing the operations of the invention or containing design data, such as HDL, that defines structures, circuits, apparatuses, processors and/or system features described herein. Such embodiments may also be referred to as program products.

The output information may be applied to one or more output devices, in known fashion. For purposes of this application, a processing system includes any system that has a processor, such as, for example; a digital signal processor (DSP), a microcontroller, an application specific integrated circuit (ASIC), or a microprocessor.

The programs may be implemented in a high level procedural or object oriented programming language to communicate with a processing system. The programs may also be implemented in assembly or machine language, if desired. In fact, the mechanisms described herein are not limited in scope to any particular programming language. In any case, the language may be a compiled or interpreted language

While particular embodiments of the present invention have been shown and described, it will be obvious to those skilled in the art that changes and modifications can be made without departing from the scope of the appended claims. For example, the foregoing mechanism for preventing post-boot updates of microcode may be equally applicable, in other embodiments, to updates of other types of code rather than being limited to microcode stored in flash memory. For one such alternative embodiment, for example, the mechanisms and methods described herein may be utilized to prevent post-boot loading of other types of code patches, including macro-code or a collection of instructions encoded in the main instruction set.

Accordingly, one of skill in the art will recognize that changes and modifications can be made without departing from the present invention in its broader aspects. The appended claims are to encompass within their scope all such changes and modifications that fall within the true scope of the present invention.