search

ssbc / jitdb

A database on top of a log with automatic index generation and maintenance
50 stars 7 forks source link

handle deletes in findSeqForMsgKey #230

Closed staltz closed 2 years ago

staltz commented 2 years ago

Problem

Right after compaction ends, we can resume pulling some pull-streams, and for that, we will use findSeqForMsgKey, but after compaction ends another thing that is now allowed to run is log.del.

So findSeqForMsgKey could theoretically stumble upon a delete.

Solution

My first reaction is that this problem is hairy, because we thought that findSeqForMsgKey can safely assume there are no deletes. However, there are two possible cases:

  1. The deleted records are not the record we are looking for, so scanning through them is harmless
  2. The record we are looking for was deleted

(1) is harmless, so we're good.

(2) is actually not that bad, we can just return the error (which is what this PR will do in that case) which will bubble up as a pull-stream "pull" error. This should be rare.

So the solution in this PR is to just skip deleted records if we stumble upon them.

Discussion

(2) sounds like we still have a big problem, and the scanning of the log seems like it sucks, but we would also have this problem if we were using ssb-db2 keys index, because given a msgKey, you're not guaranteed to find it in keys index if that msgKey has just been deleted!

For now I'm fine with accepting this risk and seeing what happens in production. The worst that would happen is a runtime crash which does not repeat once you restart the app. We will get those crash reports and we'll know how often this problem happens.

To "properly" solve this problem, I was thinking that AAOL compaction could produce a "mapping" (maybe as a bitset or some other highly compressed typed array) that tells us the whole "diff" between old seqs and new seqs, and then given any old seq we can mathematically determine the new seq. Maybe that would work.

github-actions[bot] commented 2 years ago

Benchmark results

Part Speed Heap Change Samples
Count 1 big index (3rd run) 1.05ms ± 1ms 5.21 kB ± 38.73 kB 31
Create an index twice concurrently 867.23ms ± 8.25ms -36.55 kB ± 39.49 kB 62
Load core indexes 1.11ms ± 0.02ms 79.52 B ± 303.78 B 6870
Load two indexes concurrently 723.87ms ± 5.71ms -7.83 kB ± 351.38 kB 16
Paginate 10 results 29.42ms ± 1.68ms 38.66 kB ± 49.99 kB 19
Paginate 20000 msgs with pageSize=5 9320.05ms ± 257.34ms -3.76 MB ± 5.27 MB 5
Paginate 20000 msgs with pageSize=500 608.14ms ± 24.09ms -77.14 kB ± 918.03 kB 18
Query 1 big index (1st run) 789.91ms ± 5.73ms -2.8 kB ± 63.84 kB 69
Query 1 big index (2nd run) 421.17ms ± 2.59ms -20.81 kB ± 31.06 kB 34
Query 3 indexes (1st run) 882.65ms ± 7.2ms -20.09 kB ± 71.03 kB 61
Query 3 indexes (2nd run) 344.95ms ± 7.57ms -24.89 kB ± 42.02 kB 36
Query a prefix map (1st run) 298.28ms ± 5.91ms 70.97 kB ± 115.33 kB 21
Query a prefix map (2nd run) 11ms ± 0.77ms 40.96 kB ± 233.54 kB 23
github-actions[bot] commented 2 years ago

Benchmark results

Part Speed Heap Change Samples
Count 1 big index (3rd run) 0.53ms ± 0.42ms 42.56 kB ± 29.84 kB 45
Create an index twice concurrently 575.43ms ± 2.17ms 23.43 kB ± 22.66 kB 95
Load core indexes 1.35ms ± 0.02ms 106.51 B ± 453.72 B 6104
Load two indexes concurrently 680.13ms ± 6.22ms 83.07 kB ± 349.6 kB 17
Paginate 10 results 22.27ms ± 0.73ms -8.55 kB ± 59.66 kB 24
Paginate 20000 msgs with pageSize=5 8973.07ms ± 444.89ms -1.52 MB ± 4.09 MB 5
Paginate 20000 msgs with pageSize=500 582.51ms ± 4.93ms -572.04 kB ± 734.28 kB 20
Query 1 big index (1st run) 797.7ms ± 3.2ms 7.48 kB ± 75.3 kB 68
Query 1 big index (2nd run) 303.24ms ± 1.79ms 11.63 kB ± 29.01 kB 48
Query 3 indexes (1st run) 1121.55ms ± 13.56ms -23.11 kB ± 89.06 kB 47
Query 3 indexes (2nd run) 340.96ms ± 2.48ms 12.64 kB ± 37.98 kB 38
Query a prefix map (1st run) 356.15ms ± 3.79ms -6.86 kB ± 460.67 kB 19
Query a prefix map (2nd run) 14.09ms ± 1.37ms 27.68 kB ± 246.72 kB 19