RFC: Persistent Cache MakeOccasion

[jerrykingxyz]

Feature Name: Design the MakeOccasion at persistent cache
Start Date: 2024/12/05

Summary

Design MakeOccasion to support the use of persistent cache during the make stage.

Glossary

MakeArtifact: The output of the Make stage, including all the data of the Make stage, also needs to be passed as a parameter in the Make incremental build.

User Guide

The API of MakeOccasion on the user side is very simple, providing only

• save: Save MakeArtifact to persistent cache storage.
• recovery: Restore MakeArtifact from persistent cache storage.

struct MakeOccasion {}

impl MakeOccasion {
    pub fn save(&self, artifact: &MakeArtifact) {}
    pub fn recovery(&self) -> MakeArtifact {}
}

Additional before_make and after_make are required for CacheTrait to access MakeOccasion.

trait Cache {
    fn before_make(&self, make_artifact: &mut MakeArtifact) {}
    fn after_make(&self, make_artifact: &MakeArtifact) {}
}

Detailed design

Impl MakeOccasion

MakeOccassion needs to implement persistent cache features for MakeArtifact, so it needs to pay attention to the purpose and function of each field inside MakeArtifact. In MakeArtifact, fields can be divided into

• Temporary data: Some temporary data specifically used for subsequent make stage. Removing them does not affect the next make incremental build.
• Core data: the data needed for the next incremental build of make, and the data items that need attention for persistent cache. (PS. These data can also be accessed in subsequent processes, but these data are more for make itself)

pub struct MakeArtifact {
    // temporary data, used by subsequent steps of make
    // should be reset when rebuild
    pub diagnostics: Vec<Diagnostic>,
    pub built_modules: IdentifierSet,
    pub revoked_modules: IdentifierSet,
    pub has_module_graph_change: bool,
    // Field to mark whether artifact has been initialized.
    // Only Default::default() is false, `update_module_graph` will set this field to true
    // Persistent cache will update MakeArtifact when this is false.
    pub initialized: bool,

    // data
    pub make_failed_dependencies: HashSet<BuildDependency>,
    pub make_failed_module: IdentifierSet,
    pub entry_dependencies: HashSet<DependencyId>,
    pub module_graph_partial: ModuleGraphPartial,
    pub file_dependencies: FileCounter,
    pub context_dependencies: FileCounter,
    pub missing_dependencies: FileCounter,
    pub build_dependencies: FileCounter,
}

When implementing persistent cache, we need to split the large amount of data in the core data of MakeArtifact into three parts: Dependencies & ModuleGraph & Meta.

Dependencies

The processing of Dependencies mainly includes * _dependencies in MakeArtifact, that is, the incremental processing of FileCounter , which requires us to collect the dependencies information that has been changed in this build, which can be collected by adding additional fields in IncrementalInfo.

struct IncrementalInfo {
    updated_files: HashSet<PathBuf>,
}

impl FileCounter {
    fn add_file(&mut self, path: &PathBuf) {
        self.incremental_info.updated_files.insert(path.clone());
        ...
    }
    fn remove_file(&mut self, path: &PathBuf) {
        // `remove_file` will update `path` count too,
        // so we should add it to `updated_files`
        self.incremental_info.updated_files.insert(path.clone());
        ...
    }
    fn reset(&mut self) {
        self.incremental_info.updated_files.clear();
        ...
    }
    fn updated_files_count_info() -> impl Iterator<Item = (&PathBuf, usize)> {
        self.incremental_info.updated_files().iter().map(|file| {
            let count = self.inner.get(file).unwrap_or(&0);
            (file, *count)
        })
    }
}

When saving MakeArtifact, we can use FileCouter.incremental_info to get the deps affected in this build, and then update Storage by whether they currently exist in FileCounter.

fn save(file_dependencies: &FileCounter, storage: Arc<dyn Storage>) {
    file_dependencies.updated_files_count_info().for_each(|(path, count)| {
        let dep = DependencyRef {
            r#type: DepType::File,
            path
        };
        let key = to_bytes(&dep, &()).unwrap();
        if count == 0 {
            storage.remove(SCOPE, &key);
        } else {
            storage.set(SCOPE, key, count);
        }
    })
}

fn recovery(storage: Arc<dyn Storage>) -> FileCounter {
    let file_dependencies = HashMap::default();
    for (k, v) in storage.get_all(SCOPE) {
        let dep: Dependency = from_bytes(&k);
        if dep.r#type == DepType::File {
            file_dependencies.insert(dep.path, v);
        }
    }
    file_dependencies
}

ModuleGraph

ModuleGraph is a very large graph structure, and its storage requires tiling data at the module granularity.

The tiled node contains the information about the current module, such as module, mgm, block, and downstream dependencies and connection data of the current module (PS. Remove all upstream data). Its data structure is as follows:

struct Node {
    pub module: BoxModule,
    // mgm ignore incomming connections
    pub mgm: ModuleGraphModule,
    // (dependency, parent_block)
    // TODO remove parent block info after connection contains it
    pub dependencies: Vec<(BoxDependency, Option<AsyncDependenciesBlockIdentifier>)>,
    pub connections: Vec<ModuleGraphConnection>,
    pub blocks: Vec<AsyncDependenciesBlock>,
}

The ModuleGraph can incremental updates by built_module and revoked_module in MakeArtifact.

fn save(
    built_module: &HashSet<ModuleIdentifier>,
    revoked_module: &HashSet<ModuleIdentifier>,
    storage: Arc<dyn Storage>,
    context: &CacheContext
) {
    for module_id in revoked_module {
        storage.remove(SCOPE, module_id);
    }
    
    for module_id in built_module {
        // generate node from module_graph.
        let node = ...;
        storage.set(SCOPE, module_id, to_bytes(&node, context));
    }
}

When restore module_graph, in addition to setting the information in the node back, we also need to traverse all dependencies to regenerate the incoming information. If some modules fail to restore, record it in the make_failed_dependencies.

fn recovery(
    storage: Arc<dyn Storage>,
    context: &CacheContext
) -> (ModuleGraphPartial, make_failed_dependencies) {
    let mut make_failed_dependencies = HashSet::default();
 
    let parital = ModuleGraphPartial::default();
    let mg = ModuleGraph::new(vec![], Some(&mut partial));
    
    for node in storage.get_all(SCOPE) {
        mg.add_module(node.module);
        ...
    }
    
    for dep in mg.dependencies {
        let con = mg.con_by_id(dep.id);
        let mgm = mg.mgm_by_id_mut(con.module_identifier);
        if let Some(mgm) = mgm {
            mgm.incoming_connection.push(dep.id);
        } else {
            make_failed_dependencies.insert(dep.id);
        }
    }
    
    (parital, make_failed_dependencies)
}

Meta

Meta is for core data other than ModuleGraph and * _dependencies, which has a small amount of data and can be saved in full for each build.

pub struct Meta {
    pub make_failed_dependencies: HashSet<BuildDependency>,
    pub make_failed_module: IdentifierSet,
    // Ignore entry_dependencies, compile will regenerate it.
    // pub entry_dependencies: HashSet<DependencyId>,
    pub next_dependencies_id: u32,
}

API

MakeOccasion provides save and recovery , which are relatively simple to implement and only need to integrate the above functions.

struct MakeOccasion {
    storage: Arc<dyn Storage>,
}

impl MakeOccasion {
    fn save(&self, make_artifact: &MakeArtifact) {
        let MakeArtifact {
            // write all of field here to avoid forget to update occasion when add new fields
            file_dependencies,
            module_graph_partial,
            make_failed_dependencies,
            other_field: _
        } = make_artifact;
        dependencies::save(file_dependencies, ...);
        module_graph::save(module_graph_partial);
        meta::save(make_failed_dependencies, ...);
    }
    fn recovery(&self) -> MakeArtifact {
        let artifact = MakeArtifact::default();
        let (file_dependencies, ...) = dependencies::recovery(...);
        artifact.file_dependencies = file_dependencies;
        ...
        
        let (make_failed_dependencies, make_failed_module, ...) = meta::recovery(...);
        artifact.make_failed_dependencies = make_failed_dependencies;
        artifact.make_failed_module = make_failed_module;
        ...
        
        let (module_graph_partial, make_failed_dependencies) = module_graph::recovery(...);
        artifact.module_graph_partial = module_graph_partial;
        artifact.make_failed_dependencies.extend(make_failed_dependencies);
    }
}

CacheTrait

CacheTrait needs to add two additional functions before_make and after_make , which need to be called at the begin and end of the make stage.

• For PersistentCache, it is necessary to before_make according to the MakeArtifact.initialized to determine whether to use the cache, and save the MakeArtifact when after_make.

• For DisableCache, MakeArtifact needs to be erased when before_make.

• For MemoryCache, no operation is required.

impl Cache for PersistentCache {
    fn before_make(&self, make_artifact: &mut MakeArtifact) {
        if !make_artifact.initialized {
            if let Ok(artifact) = self.make_occasion.recovery() {
                *make_artifact = artifact;
            }
        }
    }
    fn after_make(&self, make_artifact: &MakeArtifact) {
        self.make_occasion.save(make_artifact);
    }
}

impl Cache for DisableCache {
    fn before_make(&self, make_artifact: &mut MakeArtifact) {
        *make_artifact = Default::default();
    }
}

Exception handling

Since some node in ModuleGraph currently does not support serialization due to some data structures. the ModuleGraph has a certain tolerance for those errors.

• For save ModuleGraph will skip nodes that fail serialization.
• For recovery ModuleGraph will record missing modules to the make_failed_dependencies, and make stage will regenerate them.

After serialization is supported for all data structures used by Occasion in the future, the fault-tolerant logic at ModuleGraph can be considered for removal.

Unresolved Questions & TODOs

• The current design of DependenyId is achieved through digital auto-increment. In the case of persistent caching, it may exceed the upper limit and requires subsequent modifications similar to ModuleId.