ieb/solr — Issue #91: Convert ACL properties into a bitmap and use a Bloom filter
Author: ieb
Created: 2012-02-02 20:31:02+00:00
State: open

The current implementation of the ACL properties uses a a multi values keyword field. Thats fine for indexing however its bad for querying since it generates a huge list of OR statements that will rapidly kill query performance and go over the limits of the primary query in lucene. Obviously, that was never the intention. The search component was decigned for a limited number of readers per item and principals, representing those readers to make sensible use of groups. Unfortunately OAE has (against continued advice) gone the other way creating a new principal for just about everything.

One solution is to stop using the multi value index and has the list of readers into a single field that can then be matched. This is how Hippo do their acls in search in jackrabbit, however they have much lower cardinallity of principals, covering the ECM use case. I initially rejected this because I could not think of a way of reducing the potential number of hashed tokens, however I hadn't encountered bloom filters at that point. Bloom filters operate by hashing each element separately to produce a suitably sized hash, represented as a bitmap. All hashes are or'd together to produce a bloom filter that represents all the elements. To test if an element was present in the original set, then you hash that element and or it with the bloom filter. If the result is the test hash, then the set probably contains the element. The probability that it does not depends on the quality of the hash and the size of the bitmap. I havent done any experiments to see how big a bitmap for all the principals in OAE would need to be, but since the indexed bloom filter is computed on index and the query bitmap is computed when the query is created this is a candidate for a custom filter within Lucene. There is code in Hadoop for bloom filters but as we know what are elements are we might want to modify that.

Issues to check: How big a bit map do we need to get an acceptably low probability of a false negative ?
What type of hash function do we need to be optimal for this use case ?

References: http://en.wikipedia.org/wiki/Bloom_filter