RFC: Persistent Cache Storage

[LingyuCoder]

Feature Name: Design the storage module of persistent cache
Start Date: 2024/12/09

Summary

Persistent cache storage module design:

1. Read cached data from the file system before starting a phase of the build process
2. Write the resulting cached data after a phase of the build process is completed

The storage module does not care about how the data is generated and consumed (what occassion modules do) or the serialization/deserialization of the data (what serializers do), but only focuses on the organization and reading/writing of the data in the file system.

Motivation

Cached data consists of KV pairs, and isolated cached data is generated during the make, seal, and other phases. Therefore, the storage system needs to have the following capabilities:

1. A storage instance is divided into multiple storage areas (named scope) for storing caches generated/consumed at each phase of the build process.
2. A scope can be read on demand before caching consumption in the corresponding phase to prevent reading too much data at once from blocking the main process
3. A scope can be written after the building process enters the idle phase, and atomicity should be ensured as much as possible to prevent the situation where only part of the cache is written, making the overall cache unavailable
4. A scope maps to multiple files on file system and needs to control the size of the files
5. A single file should not be too large (such as storing all KVs in one file), which makes it difficult to concurrently read and write on demand
6. A single file should not be too small (such as one file per KV), resulting in too many files and too many IO operations.
7. When the cache is modified in incremental building, the writing of files should be minimized as much as possible. The unmodified part should not be written.
8. There should be basic validation for cached files to prevent data from being unavailable in the following scenarios
9. Stored files are modified, deleted, etc.
10. Storage configuration changes

Glossary

1. Storage: A storage instance mounted on the compiler, so it will cross multiple compilation under dev mode
2. Scope: A storage area distinguished by name, will be used in different building phases
3. Pack: A storage block which maps to a stored file on file system, containing multiple KV data items.
4. Meta: A metafile used to manage storage packs of a scope, used to read and verify storage blocks of this scope.

User Guide

For the upper-level persistent cache modules, a storage instance exposes the following interfaces:

#[async_trait::async_trait]
pub trait Storage: std::fmt::Debug + Sync + Send {
  async fn load(&self, scope: &'static str) -> Result<Vec<(Arc<Vec<u8>>, Arc<Vec<u8>>)>>;
  fn set(&self, scope: &'static str, key: Vec<u8>, value: Vec<u8>);
  fn remove(&self, scope: &'static str, key: &Vec<u8>);
  fn trigger_save(&self) -> Result<Receiver<Result<()>>>;
}

• load() : Asynchronously reads all data items under a Scope
• set(): Add/modify specified data items under scope, will not be written immediately, will be uniformly processed in the last idle
• remove() : Remove the specified data item under the scope, it will not be written immediately, and it will be uniformly processed in the last idle
• trigger_save() : notify storage to write all data, which will be processed in an independent thread, and notify the write result through the oneshot channel

async fn compiler() {
  let storage = Storage::new();
  
  let compilation = Compilation::new();
  // make phase
  let raw_make_cache = storage.load("make").await;
  let make_cache = deserialize(&raw_make_cache).await;
  for item in serialize(make().await) {
    storage.set/* or remove */("make", item.key, item.value);
  }
  
  // seal phase
  let raw_seal_cache = storage.load("seal").await;
  let seal_cache = deserialize(&raw_make_cache).await;
  for item in serialize(make().await) {
    storage.set/* or remove */("seal", item.key, item.value);
  }
  
  // after process assets
  let rx = storage.trigger_save();
  
  // build: wait for saving
  let res = rx.recv().await; 
  match res {
    Err(e) => compilation.addDiagnostic(e),
    _ => ()
  }


  // watch: just print the error
  tokio::spawn(async move || {
    let res = rx.recv().await;
    match res {
      Err(e) => infrastructure_logger.warn(format!("{}", e)),
      _ => ()
    }
  });
  
  compilation_done().await;  
  
  let next_compilation = Compilation::clone(&compilation);
  
  for item in serialize(incremental_make().await) {
    storage.set/* or remove */("seal", item.key, item.value);
  }
  
  let rx = storage.trigger_save();
  // ...
}

It should be noted that the waiting for idle channels can be different according to the mode:

1. compiler.build(): should wait and add storage error to diagnostics
2. compiler.watch(): no need to wait, the data will be updated to scopes when saved, and the write task will use the queue to execute in order. If the storage fails, the error from the channel needs to be print into stderr.

Detailed design

Modules

Include several parts:

1. Storage API: provides API for upper layer, almost no logic
2. Manager: management module used to schedule reading, updating, and writing of scopes. Internally includes:
3. Scopes: Storage area for storing data in memory
4. Updates: used to temporarily store the data items which will be merged into scopes when idle
5. Task Queue: a thread write queue, used to asynchronously execute write operations to the scopes when idle
6. Strategy: define the logic of validating, reading, updating, and writing on the scope, will split a scope to multiple packs
7. File System: interacting with intermediate file system
8. Meta File/Pack File: the final data files

Interaction

The APIs are handled as follows:

1. get_all()：
2. First, try to read the meta data of the scope and the keys at the header of pack files from the file system, and verify them. The validation includes the configuration object, expiration time, file size, last modify time, keys hash, etc., and will not verify the complete storage content.
3. If the validation passes, all contents of the stored file are read and stored in the scope, and the reference is returned for upper-level consumption
4. set/remove：
5. Temporarily store the item in manager without any processing
6. idle：
7. Update the temporary items to the scopes, and inform the task queue to write when idle.
8. In the task queue, take out all scopes for writing, and return ownership after writing is completed. And notify the result of writing through the channel

After the idle call, the latest data can be obtained through the load(). However, since the asynchronous write task will acquire ownership of scopes, it will be locked during the write process to prevent the load() reading empty values at this time.

sequenceDiagram
activate Compilation
loop every phase
Compilation ->> Manager: load()
activate Manager

Manager -->> FileSystem: read meta
deactivate Manager
activate FileSystem

FileSystem -->> Manager: meta & pack keys
deactivate FileSystem
activate Manager

Manager ->> Manager: validate
Manager -->> FileSystem: read contents
deactivate Manager
activate FileSystem

FileSystem -->> Manager: pack contents
deactivate FileSystem
activate Manager

Manager ->> Compilation: cache items
deactivate Manager

Compilation ->> Compilation: start make phase
activate Compilation

Compilation ->> Manager: set()/remove()
activate Manager
deactivate Manager

Compilation ->> Manager: set()/remove()
activate Manager
deactivate Manager

deactivate Compilation
end

Compilation ->> Manager: trigger_save()
activate Manager
Manager ->> Manager: update scopes
Manager ->> TaskQueue: scopes ownership
activate TaskQueue
Manager ->> Compilation: receiver
deactivate Manager

Compilation ->> Compilation: done()
activate Compilation

TaskQueue ->> FileSystem: write pack files
activate FileSystem
FileSystem ->> TaskQueue: file metadatas
deactivate FileSystem
TaskQueue ->> TaskQueue: create scope meta
deactivate Compilation
TaskQueue ->> FileSystem: write meta file
activate FileSystem
FileSystem ->> TaskQueue: write end
deactivate FileSystem
TaskQueue ->> Manager: scopes ownership
activate Manager

deactivate Manager
TaskQueue -> Compilation: async write result
deactivate TaskQueue

deactivate Compilation

Loading

Strategy

Since usually when a rspack project builds, the vast majority of modules come from the node_modules, these modules will not change frequently, only a small number of user modules will be frequently modified, in the dev mode this situation is particularly obvious. Therefore, consider using buckets to incrementally write within a certain range:

1. First, the data items are bucketed according to the hash of the key, and the total number of buckets can be configured (like 10 or 20).
2. For all data in the bucket, it is partitioned to packs, and the maximum size of a pack can be configured (like 500kb).
3. After all pack files under bucketing are written, a meta file is generated, which includes the current configuration items of the scope and the final file name and file hash (calculated from keys + mtime + size).

Validation

1. Read the meta file to load the configuration and the time of writing the storage
2. Compare the current configuration and expiration time, if it does not match, the cache is not available
3. Read the metadata of pack files, obtain mtime and size, and read the keys part of the header of the pack file and calculate the hash.
4. Compared with the hash in the meta file, if it does not match, the cache file has been modified and the cache will not be available
5. Read the whole body of pack files and get the data items
6. If the read data item corresponds to keys, the cache is available

flowchart TB
Validate --> ReadMeta[read meta file]
ReadMeta --> ValidateMeta{options match?}
ValidateMeta -- changed or expired --> Invalid[invalid]
ValidateMeta -- passes --> ReadKeys[read packs & pack keys]
ReadKeys --> ValidateHash{hashes match?}
ValidateHash -- not match --> Invalid
ValidateHash -- passes --> ReadContents[read pack contents]
ReadContents --> ValidateContents{contents match?}
ValidateContents -- length not match --> Invalid
ValidateContents -- passes --> Valid

Loading

Updating

Set 80% of the maximum size of a pack as stable size limit:

1. If a stable pack has no data items modified/deleted, its file does not need to be operated on, and the structure in memory will be directly reused
2. If there are no data items modified/deleted in an unstable pack, the pack is also considered dirty due to the possibility of adding new data items
3. If any data item in a pack is modified/deleted, the pack will be dirty
4. For dirty packs, it is believed that they will be modified, that is, the files will be rewritten, so the data in their memory will be moved out and their files will be deleted
5. Merge the data items took from the dirty pack with the newly added/modified/deleted data items to form a new list of data items, and fill the pack one by one according to size until a pack is not filled enough
6. A single data item that exceeds a stable size limit will generate an independent package, regardless of its size

flowchart TD
OldPacks["take(scope.packs)"] --> GetItemMapping[get item to pack mapping]
GetItemMapping --> CheckPackDirty[find out dirty packs]
UpdateItems["take(update[scope_name])"] -- removed/updated items --> CheckPackDirty
CheckPackDirty -- items in dirty packs --> NewItems[generate new items list]
UpdateItems -- insert/updated items --> NewItems
CheckPackDirty -- unchanged packs --> UnchangedPacks[unchanged stable packs]
NewItems -- filled new packs --> CreatedPacks[created new packs]
UnchangedPacks --> FinalPacks[final packs]
CreatedPacks --> FinalPacks

Loading

Exception handling

Any errors that occur during the caching process should not block the main process, and in the worst case, only cause the cache to be unavailable. Therefore, errors generated during the process should be regarded as warnings.

1. While calling load(), if the validation fails or reads abnormally, it will fallback to the cache is not available, and there will be an empty scope in memory
2. While writing scopes, the files that need to be changed will be written to the temp directory first. If it fails, an error will be sent through the channel, but the data in the memory scope is still available. It can be updated normally and processed at the next write.
3. After all scopes are written to the temp directory, the files in the temp directory will be moved to the cache directory to ensure atomicity as much as possible. Of course, if an error occurs during the movement, it may cause damage to the cache files.
4. After the move is completed, all files in the directory will be detected based on the scope object in the current memory, and irrelevant files will be removed.

Unresolved Questions & TODOs

1. There is still a lot of room for optimization in the current strategy
2. Refer to some optimization ideas of webpack
3. For stable packs, if only few KVs are changed and it is still in a stable state after the change, local changes in the file can be considered
4. A single large package will currently exceed the limit volume and need to be split
5. For incremental scenarios, special treatment should be given. Currently, in order to update the cache, a complete copy is kept in memory, which consumes a lot of memory. In the future, we will consider releasing the cache in memory and only reading the affected pack to generate incremental updates in the incremental case
6. Implement more strategies for different scenarios
7. Exception handling is rough, and exception prompts still need to be optimized.
8. Provide detailed failure reasons when the validation fails
9. Provide the cause of the exception and the files related when an exception occurs
10. Other performance issues
11. At present, when processing data writing, ownership transfer has actually been done, but because cloning is required for upstream consumption, Arc is still needed. Perhaps there is a better way
12. Need more test cases and benchmarks