Cache query results

[the-mikedavis]

From the discussion in https://github.com/rabbitmq/khepri/discussions/33

This adds an ETS-based cache for each server in the khepri cluster. Local caches are immediately consistent - Ra auxiliary commands evict stale items from each cache as a node is changed in the store. Reading from remote caches (like a leader query) is eventually consistent: it's possible to read from the other node's cache faster than the aux commands can evict stale entries. Paths are added to the cache when queried.

Still TODO:

• use a cache replacement strategy
• split the current cache into a behaviour plus default implementation
• unit tests

[codecov[bot]]

Codecov Report

Merging #118 (838c643) into main (cd2d894) will increase coverage by 91.25%. The diff coverage is 72.72%.

@@            Coverage Diff            @@
##           main     #118       +/-   ##
=========================================
+ Coverage      0   91.25%   +91.25%     
=========================================
  Files         0       15       +15     
  Lines         0     2641     +2641     
=========================================
+ Hits          0     2410     +2410     
- Misses        0      231      +231     

Flag	Coverage Δ
erlang-23	89.78% <72.72%> (?)
erlang-24	89.62% <72.72%> (?)
erlang-25	89.13% <72.72%> (?)
os-ubuntu-latest	91.25% <72.72%> (?)
os-windows-latest	91.17% <72.72%> (?)

Flags with carried forward coverage won't be shown. Click here to find out more.

Impacted Files	Coverage Δ
src/khepri.erl	95.73% <ø> (ø)
src/khepri_query_cache.erl	69.56% <69.56%> (ø)
src/khepri_machine.erl	92.23% <75.00%> (ø)
src/khepri_condition.erl	90.35% <0.00%> (ø)
src/khepri_event_handler.erl	89.36% <0.00%> (ø)
src/khepri_app.erl	100.00% <0.00%> (ø)
src/khepri_cluster.erl	80.33% <0.00%> (ø)
src/khepri_path.erl	97.14% <0.00%> (ø)
src/khepri_sproc.erl	80.00% <0.00%> (ø)
src/khepri_utils.erl	95.41% <0.00%> (ø)
... and 7 more

Help us with your feedback. Take ten seconds to tell us how you rate us. Have a feature suggestion? Share it here.

[the-mikedavis]

I hooked this branch into khepri-benchmark and the results are not quite what I expected.

Results...

System information:
  OS: Linux
  CPU: Intel(R) Core(TM) i7-9700KF CPU @ 3.60GHz
  Number of cores: 8
  Memory: 31 GiB
  Erlang: 25.0



Queries, 3-node cluster, no concurrency
           Khepri (low_latency): ■■■■■■■ 25497 ops/s
    Khepri (low_latency, cache): ■■■■■ 19723 ops/s
            Khepri (compromise): ■■■■ 15353 ops/s
     Khepri (compromise, cache): ■■■■ 16149 ops/s
           Khepri (consistency): ■■■ 10285 ops/s
    Khepri (consistency, cache): ■■ 7953 ops/s
                         Mnesia: ■■■■■ 18716 ops/s

Queries, 3-node cluster, 50 concurrent workers
           Khepri (low_latency): ■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■ 194921 ops/s
    Khepri (low_latency, cache): ■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■ 207256 ops/s
            Khepri (compromise): ■■■■■■■■■■■■■■■■■■■■■■■■■■■ 111131 ops/s
     Khepri (compromise, cache): ■■■■■■■■■■■■■■■■■■■■■■■■■■■■ 112456 ops/s
           Khepri (consistency): ■■■■■■■■■■■■■■■■ 65081 ops/s
    Khepri (consistency, cache): ■■■■■■■■■■■■ 48045 ops/s
                         Mnesia: ■■■■■■■■■■■■■■■■■■■■■■■■■■ 104147 ops/s

Queries, 3-node cluster, 100 concurrent workers
           Khepri (low_latency): ■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■ 182162 ops/s
    Khepri (low_latency, cache): ■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■ 203128 ops/s
            Khepri (compromise): ■■■■■■■■■■■■■■■■■■■■■■■■■■■■ 112743 ops/s
     Khepri (compromise, cache): ■■■■■■■■■■■■■■■■■■■■■■■■■ 103000 ops/s
           Khepri (consistency): ■■■■■■■■■■■■■■■■■ 67991 ops/s
    Khepri (consistency, cache): ■■■■■■■■■■■■ 47243 ops/s
                         Mnesia: ■■■■■■■■■■■■■■■■■■■■■■■■■■■ 109361 ops/s

Queries, 3-node cluster, 200 concurrent workers
           Khepri (low_latency): ■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■ 193764 ops/s
    Khepri (low_latency, cache): ■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■ 207993 ops/s
            Khepri (compromise): ■■■■■■■■■■■■■■■■■■■■■■■■■■ 107299 ops/s
     Khepri (compromise, cache): ■■■■■■■■■■■■■■■■■■■■■■■■■■ 104635 ops/s
           Khepri (consistency): ■■■■■■■■■■■■■■■■■ 67081 ops/s
    Khepri (consistency, cache): ■■■■■■■■■■■ 45187 ops/s
                         Mnesia: ■■■■■■■■■■■■■■■■■■■■■■■■■■■■■ 116947 ops/s

The speed boost for local queries is nice but it's a noticeable penalty for compromise and consistency queries. It seems like the overhead of the rpc call is not worth the time we save by not querying the Ra server. We could only use local caches but the speed boost is not tremendous there. Maybe Ra is just so fast to query that it ends up not being worth it to cache queries?

[the-mikedavis]

Closing this in favor of #135. This approach is simpler than #135 in terms of usage - you only need to pass use_cache => true in the query options - but it's slower than having dedicated and customizable ETS tables.

It's also not possible to efficiently evict stale entries from the cache table: the cache uses the query pattern as a key and the machine knows when a path is updated. We can't write a simple ets:delete or even a ets:select_delete that covers all possible query patterns which could match the given path. To evict correctly, we would need to traverse the whole cache table and check does_path_match(ChangedPath, QueryPattern, [], TreeRoot) for all cached queries, and this is prohibitively expensive if there are many reads and writes.