[jira] [Created] (OAK-7090) Use Bloom filters for composite data store blob ID lookup table

["Matt Ryan (JIRA)" <ji...@apache.org>]

Matt Ryan created OAK-7090:
------------------------------

             Summary: Use Bloom filters for composite data store blob ID lookup table
                 Key: OAK-7090
                 URL: https://issues.apache.org/jira/browse/OAK-7090
             Project: Jackrabbit Oak
          Issue Type: Technical task
            Reporter: Matt Ryan


The composite data store attempts to keep a mapping of blob ids to delegates where that blob id should be found.  We should use Bloom filters to make this mapping more efficient.

There are a couple of challenges with implementing Bloom filters for this purpose.
# Determining the appropriate size of the Bloom filter.  Assuming OAK-7089 is completed before this one, we should have a reasonable guess as to the number of blob IDs at startup time, but this may change over time.  This may require a task to rebuild the table for a more appropriate size once the table becomes too full (too many false positives).
# Handling deletions.  Once a record has been deleted, the corresponding blob ID may also need to be removed (similar algorithm to data store GC).  Bloom filters don't typically handle deletions though.  This may require something like e.g. [Invertible Bloom Filter|http://www.i-programmer.info/programming/theory/4641-the-invertible-bloom-filter.html], or this may be as simple as using data store GC time to rebuild the Bloom filter appropriately.



--
This message was sent by Atlassian JIRA
(v6.4.14#64029)