Program cache index v2 design concept.

index_v2.rs

//! Program cache index v2 implementation.
//!
//! Consider a fork graph.
//!
//! ```
//!
//!          0 <- root
//!        /   \
//!       10    5
//!       |     |
//!       20    11              11 <- root
//!                           / | \
//!                        14  15  25             15 <- root
//!                         |   |   |              |
//!                        15  16  27             16
//!                           /  \               /  \
//!                          24  25             24  25    
//!
//! ```
//!
//! A program entry can be modified at any slot in a fork. Entries are
//! considered "modified" when they are invoked in a transaction, since their
//! usage counters will increment. Additionally, transactions which upgrade or
//! close a program will also modify the program's compilation state.
//!
//! Consider a fork graph of _only_ a program's transaction usage counter,
//! where the numbers represent transaction usage count.
//!
//! ```
//!
//!          0 <- root
//!        /   \
//!       1     1
//!       |     |
//!       1     2               3 <- root
//!                           / | \
//!                         1   2  4               5 <- root
//!                         |   |   |              |
//!                         3   1   1              1
//!                           /  \                /  \
//!                          1   1               1   1     
//!
//! ```
//!
//! In this case, each time the fork graph is rooted, the usage counter is
//! incremented. The same pattern can be followed for instruction usage.
//!
//! Once a program's compilation status changes, all slots after the change
//! in a given fork must adhere to the new status. Thus, forks need only to
//! track the last slot in which a program's status changed.
//!
//! ```
//!         Closed -----> x
//!                      11 -- 14 <--- Sees closed program
//!                     /
//!                    5
//!                   /
//! Compiled -----> 0
//!                   \
//!                    10 -- 12 <--- Sees compiled program
//!
//! ```

struct ProgramCacheEntryV2 {
    /// The program of this entry
    pub program: ProgramCacheEntryType,
    /// The loader of this entry
    pub account_owner: ProgramCacheEntryOwner,
    /// Size of account that stores the program and program data
    pub account_size: usize,
}

/// A node in the index v2 fork graph.
///
/// Keeps track of the slot in the fork graph, as well as the program's usage
/// counters and any state changes.
///
/// A fork graph comprised of these nodes is relatively lightweight, since
/// each node only stores three `u64` counters and an optional state change.
///
/// The state change is typically going to be `None`, but even when a program's
/// state changes, the state change is represented by a reference.
struct Node {
    /// This node's forks.
    forks: Vec<Node>,
    /// The state, if any, the program was modified to in this slot.
    ///
    /// A `None` value indicates the program was not modified in this slot,
    /// thus subsequent slots can continue to use the same state.
    ///
    /// A `Some` value indicates the program was modified in this slot, and
    /// subsequent slots must adhere to the new state.
    ///
    /// Similar to the root, certain rules can be made according to this state
    /// value. For example, if a program is closed in a slot, no forks need to
    /// be tracked, since the program can't be used again.
    program_state_change: Option<Arc<ProgramCacheEntryV2>>,
    /// Number of instructions that invoked this program in this slot.
    ix_usage: u64,
    /// Number of transactions that invoked this program in this slot.
    tx_usage: u64,
    /// Current slot in the fork graph.
    slot: Slot,
}

/// A program entry in the cache v2 index.
///
/// Keeps track of the program's last known state and a lightweight fork graph
/// of the program's usage counters and any state changes.
struct ProgramEntry {
    /// The last known state of the program.
    ///
    /// As the fork graph is traversed, the program's state is updated to the
    /// most recent state, but only if there is a state change.
    ///
    /// Certain rules can be made according to this state value. For example,
    /// if a program is closed in a slot, no forks need to be tracked, since
    /// the program can't be used again.
    root_program_state: Arc<ProgramCacheEntryV2>,
    /// The program's fork graph.
    root: Node,
}

struct IndexV2 {
    /// A map of all programs in the index.
    entries: HashMap<Pubkey, ProgramEntry>,
}