Context:
Sorting L0 files by largest_seqno has at least two inconvenience:

• File ingestion and compaction involving ingested files can create files of overlapping seqno range with the existing files. force_consistency_check=true will catch such overlap seqno range even those harmless overlap.
  • For example, consider the following sequence of events ("key@n" indicates key at seqno "n")
    • insert k1@1 to memtable m1
    • ingest file s1 with k2@2, ingest file s2 with k3@3
    • insert k4@4 to m1
    • compact files s1, s2 and result in new file s3 of seqno range [2, 3]
    • flush m1 and result in new file s4 of seqno range [1, 4]. And force_consistency_check=true will think s4 and s3 has file reordering corruption that might cause retuning an old value of k1
  • However such caught corruption is a false positive since s1, s2 will not have overlapped keys with k1 or whatever inserted into m1 before ingest file s1 by the requirement of file ingestion (otherwise the m1 will be flushed first before any of the file ingestion completes). Therefore there in fact isn't any file reordering corruption.
• Single delete can decrease a file's largest seqno and ordering by largest_seqno can introduce a wrong ordering hence file reordering corruption
  • For example, consider the following sequence of events ("key@n" indicates key at seqno "n", Credit to @ajkr for this example)
    • an existing SST s1 contains only k1@1
    • insert k1@2 to memtable m1
    • ingest file s2 with k3@3, ingest file s3 with k4@4
    • insert single delete k5@5 in m1
    • flush m1 and result in new file s4 of seqno range [2, 5]
    • compact s1, s2, s3 and result in new file s5 of seqno range [1, 4]
    • compact s4 and result in new file s6 of seqno range [2] due to single delete
  • By the last step, we have file ordering by largest seqno (">" means "newer") : s5 > s6 while s6 contains a newer version of the k1's value (i.e, k1@2) than s5, which is a real reordering corruption. While this can be caught by force_consistency_check=true, there isn't a good way to prevent this from happening if ordering by largest_seqno

Therefore, we are redesigning the sorting criteria of L0 files and avoid above inconvenience. Credit to @ajkr , we now introduce epoch_num which describes the order of a file being flushed or ingested/imported (compaction output file will has the minimum epoch_num among input files'). This will avoid the above inconvenience in the following ways:

• In the first case above, there will no longer be overlap seqno range check in force_consistency_check=true but epoch_number ordering check. This will result in file ordering s1 < s2 < s4 (pre-compaction) and s3 < s4 (post-compaction) which won't trigger false positive corruption. See test class DBCompactionTestL0FilesMisorderCorruption* for more.
• In the second case above, this will result in file ordering s1 < s2 < s3 < s4 (pre-compacting s1, s2, s3), s5 < s4 (post-compacting s1, s2, s3), s5 < s6 (post-compacting s4), which are correct file ordering without causing any corruption.

Summary:

• Introduce epoch_number stored per ColumnFamilyData and sort CF's L0 files by their assigned epoch_number instead of largest_seqno.
  • epoch_number is increased and assigned upon VersionEdit::AddFile() for flush (or similarly for WriteLevel0TableForRecovery) and file ingestion (except for allow_behind_true, which will always get assigned as the kReservedEpochNumberForFileIngestedBehind)
  • Compaction output file is assigned with the minimum epoch_number among input files'
    • Refit level: reuse refitted file's epoch_number
  • Other paths needing epoch_number treatment:
    • Import column families: reuse file's epoch_number if exists. If not, assign one based on NewestFirstBySeqNo
    • Repair: reuse file's epoch_number if exists. If not, assign one based on NewestFirstBySeqNo.
  • Assigning new epoch_number to a file and adding this file to LSM tree should be atomic. This is guaranteed by us assigning epoch_number right upon VersionEdit::AddFile() where this version edit will be apply to LSM tree shape right after by holding the db mutex (e.g, flush, file ingestion, import column family) or by there is only 1 ongoing edit per CF (e.g, WriteLevel0TableForRecovery, Repair).
  • Assigning the minimum input epoch number to compaction output file won't misorder L0 files (even through later Refit(target_level=0)). It's due to for every key "k" in the input range, a legit compaction will cover a continuous epoch number range of that key. As long as we assign the key "k" the minimum input epoch number, it won't become newer or older than the versions of this key that aren't included in this compaction hence no misorder.
• Persist epoch_number of each file in manifest and recover epoch_number on db recovery
  • Backward compatibility with old db without epoch_number support is guaranteed by assigning epoch_number to recovered files by NewestFirstBySeqno order. See VersionStorageInfo::RecoverEpochNumbers() for more
  • Forward compatibility with manifest is guaranteed by flexibility of NewFileCustomTag
• Replace force_consistent_check on L0 with epoch_number and remove false positive check like case 1 with largest_seqno above
  • Due to backward compatibility issue, we might encounter files with missing epoch number at the beginning of db recovery. We will still use old L0 sorting mechanism (NewestFirstBySeqno) to check/sort them till we infer their epoch number. See usages of EpochNumberRequirement.
• Remove fix Fix corruption with intra-L0 on ingested files #5958 (comment) and their outdated tests to file reordering corruption because such fix can be replaced by this PR.
• Misc:
  • update existing tests with epoch_number so make check will pass
  • update Fix corruption with intra-L0 on ingested files #5958 (comment) tests to verify corruption is fixed using epoch_number and cover universal/fifo compaction/CompactRange/CompactFile cases
  • assert db_mutex is held for a few places before calling ColumnFamilyData::NewEpochNumber()

Test:

• make check
• New unit tests under db/db_compaction_test.cc, db/db_test2.cc, db/version_builder_test.cc, db/repair_test.cc
• Updated tests (i.e, DBCompactionTestL0FilesMisorderCorruption*) under Fix corruption with intra-L0 on ingested files #5958 (comment)
• [Ongoing] Compatibility test: manually run ajkr@36a5686 (with file ingestion off for running the .orig binary to prevent this bug affecting upgrade/downgrade formality checking) for 1 hour on simple black/white box, cf_consistency/txn/enable_ts with whitebox + test_best_efforts_recovery with blackbox
• [Ongoing] normal db stress test
• [Ongoing] db stress test with aggressive value [CI only]Aggressive crash test value #10761