Uploaded image for project: 'Jackrabbit Oak'
  1. Jackrabbit Oak
  2. OAK-7083 CompositeDataStore - ReadOnly/ReadWrite Delegate Support
  3. OAK-7090

Use Bloom filters for composite data store blob ID lookup table

Attach filesAttach ScreenshotAdd voteVotersWatch issueWatchersLinkCloneUpdate Comment AuthorReplace String in CommentUpdate Comment VisibilityDelete Comments
    XMLWordPrintableJSON

Details

    Description

      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.

      1. 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).
      2. 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, or this may be as simple as using data store GC time to rebuild the Bloom filter appropriately.

      Attachments

        Activity

          This comment will be Viewable by All Users Viewable by All Users
          Cancel

          People

            Unassigned Unassigned
            mattvryan Matt Ryan

            Dates

              Created:
              Updated:

              Slack

                Issue deployment