Steps

    1. Go from level 0 to highest level to pick the level, Lb, that the score of this level is the largest and is larger than 1 as the compaction base level.

    2. Determine the compaction output level Lo = Lb + 1

    3. If we choose f3 in step 3, then in step 4, we have to expand inputs from {f3} to {f2, f3, f4} because the boundary of f2 and f3 are continuous, as are f3 and f4. The reason that two files may share the same user key boundary is that RocksDB store InternalKey in files which consists of user key, sequence number of key type. So files may store multiple InternalKeys with the same user key. Therefore, if compaction happens, all the InternalKeys with the same user key have to be compacted altogether.

    4. Check that the files in current inputs don’t overlap with any files being compacted. Otherwise, try to find any manual compaction available. If not, abort this compaction pick job.

    5. Find all the files on Lo that overlap with the files in inputs and expand them as the same way in step 4 until we find a “clean cut” of files on Lo. If anyone of these files are being compacted, abort this compaction pick job. Otherwise, put them into output_level_inputs.

    6. The files in inputs and output_level_inputs are the candidate files for this level compaction.