Uploaded image for project: 'Solr'
  1. Solr
  2. SOLR-8241

Evaluate W-TinyLfu cache

    XMLWordPrintableJSON

    Details

    • Type: Improvement
    • Status: Resolved
    • Priority: Major
    • Resolution: Fixed
    • Affects Version/s: None
    • Fix Version/s: 8.3
    • Component/s: search
    • Labels:
      None

      Description

      SOLR-2906 introduced an LFU cache and in-progress SOLR-3393 makes it O(1). The discussions seem to indicate that the higher hit rate (vs LRU) is offset by the slower performance of the implementation. An original goal appeared to be to introduce ARC, a patented algorithm that uses ghost entries to retain history information.

      My analysis of Window TinyLfu indicates that it may be a better option. It uses a frequency sketch to compactly estimate an entry's popularity. It uses LRU to capture recency and operate in O(1) time. When using available academic traces the policy provides a near optimal hit rate regardless of the workload.

      I'm getting ready to release the policy in Caffeine, which Solr already has a dependency on. But, the code is fairly straightforward and a port into Solr's caches instead is a pragmatic alternative. More interesting is what the impact would be in Solr's workloads and feedback on the policy's design.

      https://github.com/ben-manes/caffeine/wiki/Efficiency

        Attachments

        1. SOLR-8241.patch
          14 kB
          Ben Manes
        2. SOLR-8241.patch
          11 kB
          Shawn Heisey
        3. proposal.patch
          19 kB
          Ben Manes
        4. SOLR-8241.patch
          19 kB
          Ben Manes
        5. SOLR-8241.patch
          31 kB
          Andrzej Bialecki
        6. SOLR-8241.patch
          38 kB
          Andrzej Bialecki
        7. caffeine-benchmark.txt
          6 kB
          Andrzej Bialecki
        8. solr_caffeine.patch.gz
          2 kB
          Ben Manes
        9. solr_jmh_results.json
          18 kB
          Ben Manes
        10. EvictionBenchmark.png
          86 kB
          Andrzej Bialecki
        11. GetPutBenchmark.png
          57 kB
          Andrzej Bialecki
        12. SOLR-8241.patch
          53 kB
          Andrzej Bialecki

          Activity

            People

            • Assignee:
              ab Andrzej Bialecki
              Reporter:
              ben.manes Ben Manes
            • Votes:
              7 Vote for this issue
              Watchers:
              15 Start watching this issue

              Dates

              • Created:
                Updated:
                Resolved: