Repository: vercel/next.js
Pull request: Turbopack: Fix sst filter handling and order for meta files

### What?

* fixes a bug where it crashes with `Unable to open static sorted file 00000286.sst` after a compaction which leaves a partial meta file.
  meta files need to be handled in reverse order as higher sequence numbers override lower ones
* fixes another bug where SST files in meta files were processed in incorrect order
  This could cause reading outdated values, maybe causing the incorrect graph problem or stale tasks/errors

Closes PACK-4770

Changed files:
filename: turbopack/crates/turbo-persistence/src/db.rs
patch: @@ -333,7 +333,7 @@ impl TurboPersistence {
             .collect::<Result<Vec<MetaFile>>>()?;
 
         let mut sst_filter = SstFilter::new();
-        for meta_file in meta_files.iter_mut() {
+        for meta_file in meta_files.iter_mut().rev() {
             sst_filter.apply_filter(meta_file);
         }
 
@@ -468,7 +468,7 @@ impl TurboPersistence {
             .collect::<Result<Vec<_>>>()?;
 
         let mut sst_filter = SstFilter::new();
-        for meta_file in new_meta_files.iter_mut() {
+        for meta_file in new_meta_files.iter_mut().rev() {
             sst_filter.apply_filter(meta_file);
         }
 
@@ -501,10 +501,12 @@ impl TurboPersistence {
 
         {
             let mut inner = self.inner.write();
-            for meta_file in inner.meta_files.iter_mut() {
+            for meta_file in inner.meta_files.iter_mut().rev() {
                 sst_filter.apply_filter(meta_file);
             }
             inner.meta_files.append(&mut new_meta_files);
+            // apply_and_get_remove need to run in reverse order
+            inner.meta_files.reverse();
             inner.meta_files.retain(|meta| {
                 if sst_filter.apply_and_get_remove(meta) {
                     meta_seq_numbers_to_delete.push(meta.sequence_number());
@@ -513,6 +515,7 @@ impl TurboPersistence {
                     true
                 }
             });
+            inner.meta_files.reverse();
             has_delete_file = !sst_seq_numbers_to_delete.is_empty()
                 || !blob_seq_numbers_to_delete.is_empty()
                 || !meta_seq_numbers_to_delete.is_empty();

filename: turbopack/crates/turbo-persistence/src/meta_file.rs
patch: @@ -258,7 +258,7 @@ impl MetaFile {
             return Ok(MetaLookupResult::FamilyMiss);
         }
         let mut miss_result = MetaLookupResult::RangeMiss;
-        for entry in self.entries.iter() {
+        for entry in self.entries.iter().rev() {
             if key_hash < entry.min_hash || key_hash > entry.max_hash {
                 continue;
             }

filename: turbopack/crates/turbo-persistence/src/sst_filter.rs
patch: @@ -22,14 +22,11 @@ impl SstFilter {
         meta.retain_entries(|seq| match self.0.entry(seq) {
             Entry::Occupied(mut e) => {
                 let state = e.get_mut();
-                match state {
-                    SstState::Active => false,
-                    SstState::UnusedObsolete => {
-                        *state = SstState::Obsolete;
-                        false
-                    }
-                    SstState::Obsolete => false,
+                if matches!(state, SstState::UnusedObsolete) {
+                    // the obsolete state is used now
+                    *state = SstState::Obsolete;
                 }
+                false
             }
             Entry::Vacant(e) => {
                 e.insert(SstState::Active);
@@ -47,20 +44,14 @@ impl SstFilter {
     pub fn apply_and_get_remove(&mut self, meta: &MetaFile) -> bool {
         let mut used = false;
         for seq in meta.obsolete_sst_files() {
-            match self.0.entry(*seq) {
-                Entry::Occupied(e) => match e.get() {
-                    SstState::Active => {}
-                    SstState::UnusedObsolete => {
-                        e.remove();
-                    }
-                    SstState::Obsolete => {
-                        e.remove();
-                        used = true;
-                    }
-                },
-                Entry::Vacant(e) => {
-                    e.insert(SstState::UnusedObsolete);
+            if let Entry::Occupied(e) = self.0.entry(*seq) {
+                if matches!(e.get(), SstState::Obsolete) {
+                    // This obsolete sst entry was used, so we need to keep the meta file.
+                    used = true;
                 }
+                // Only the first obsolete sst entry is needed, so we can clear this flag, so
+                // that following meta files won't see it as used anymore.
+                e.remove();
             }
         }
 

filename: turbopack/crates/turbo-persistence/src/tests.rs
patch: @@ -477,3 +477,83 @@ fn persist_changes() -> Result<()> {
 
     Ok(())
 }
+
+#[test]
+fn partial_compaction() -> Result<()> {
+    let tempdir = tempfile::tempdir()?;
+    let path = tempdir.path();
+
+    const READ_COUNT: u32 = 2_000; // we'll read every 10th value, so writes are 10x this value
+    fn put(b: &WriteBatch<(u8, [u8; 4]), 1>, key: u8, value: u8) -> Result<()> {
+        for i in 0..(READ_COUNT * 10) {
+            b.put(0, (key, i.to_be_bytes()), vec![value].into())?;
+        }
+        Ok(())
+    }
+    fn check(db: &TurboPersistence, key: u8, value: u8) -> Result<()> {
+        for i in 0..READ_COUNT {
+            // read every 10th item
+            let i = i * 10;
+            assert_eq!(
+                db.get(0, &(key, i.to_be_bytes()))?.as_deref(),
+                Some(&[value][..]),
+                "Key {key} {i} expected {value}"
+            );
+        }
+        Ok(())
+    }
+
+    for i in 0..50 {
+        println!("--- Iteration {i} ---");
+        println!("Add more entries");
+        {
+            let db = TurboPersistence::open(path.to_path_buf())?;
+            let b = db.write_batch::<_, 1>()?;
+            put(&b, i, i)?;
+            put(&b, i + 1, i)?;
+            put(&b, i + 2, i)?;
+            db.commit_write_batch(b)?;
+
+            for j in 0..i {
+                check(&db, j, j)?;
+            }
+            check(&db, i, i)?;
+            check(&db, i + 1, i)?;
+            check(&db, i + 2, i)?;
+
+            db.shutdown()?;
+        }
+
+        println!("Compaction");
+        {
+            let db = TurboPersistence::open(path.to_path_buf())?;
+
+            db.compact(3.0, 3, u64::MAX)?;
+
+            for j in 0..i {
+                check(&db, j, j)?;
+            }
+            check(&db, i, i)?;
+            check(&db, i + 1, i)?;
+            check(&db, i + 2, i)?;
+
+            db.shutdown()?;
+        }
+
+        println!("Restore check");
+        {
+            let db = TurboPersistence::open(path.to_path_buf())?;
+
+            for j in 0..i {
+                check(&db, j, j)?;
+            }
+            check(&db, i, i)?;
+            check(&db, i + 1, i)?;
+            check(&db, i + 2, i)?;
+
+            db.shutdown()?;
+        }
+    }
+
+    Ok(())
+}