parity pruning-journaldb

//! `JournalDB` interface and implementation.
...
/// Journal database operating strategy.
#[derive(Debug, PartialEq, Clone, Copy)]
pub enum Algorithm {
	/// Keep all keys forever.
	Archive,

	/// Ancient and recent history maintained separately; recent history lasts for particular
	/// number of blocks.
	///
	/// Inserts go into backing database, journal retains knowledge of whether backing DB key is
	/// ancient or recent. Non-canon inserts get explicitly reverted and removed from backing DB.
	EarlyMerge,

	/// Ancient and recent history maintained separately; recent history lasts for particular
	/// number of blocks.
	///
	/// Inserts go into memory overlay, which is tried for key fetches. Memory overlay gets
	/// flushed in backing only at end of recent history.
	OverlayRecent,

	/// Ancient and recent history maintained separately; recent history lasts for particular
	/// number of blocks.
	///
	/// References are counted in disk-backed DB.
	RefCounted,
}

impl str::FromStr for Algorithm {
	type Err = String;

	fn from_str(s: &str) -> Result<Self, Self::Err> {
		match s {
			"archive" => Ok(Algorithm::Archive),
			"light" => Ok(Algorithm::EarlyMerge),
			"fast" => Ok(Algorithm::OverlayRecent),
			"basic" => Ok(Algorithm::RefCounted),
			e => Err(format!("Invalid algorithm: {}", e)),
		}
	}
}

impl Algorithm {
	/// Returns static str describing journal database algorithm.
	pub fn as_str(&self) -> &'static str {
		match *self {
			Algorithm::Archive => "archive",
			Algorithm::EarlyMerge => "light",
			Algorithm::OverlayRecent => "fast",
			Algorithm::RefCounted => "basic",
		}
	}
...

/// journal format:
/// ```text
/// [era, 0] => [ id, [insert_0, ...], [remove_0, ...] ]
/// [era, 1] => [ id, [insert_0, ...], [remove_0, ...] ]
/// [era, n] => [ ... ]
/// ```

/// The semantics of the `counter` are:
/// ```text
/// insert key k:
///   counter already contains k: count += 1
///   counter doesn't contain k:
///     backing db contains k: count = 1
///     backing db doesn't contain k: insert into backing db, count = 0
/// delete key k:
///   counter contains k (count is asserted to be non-zero):
///     count > 1: counter -= 1
///     count == 1: remove counter
///     count == 0: remove key from backing db
///   counter doesn't contain k: remove key from backing db
/// ```
///

///Practically, this means that for each commit block turning from recent to ancient we do the
///following:
/// ```text
/// is_canonical:
///   inserts: Ignored (left alone in the backing database).
///   deletes: Enacted; however, recent history queue is checked for ongoing references. This is
///            reduced as a preference to deletion from the backing database.
/// !is_canonical:
///   inserts: Reverted; however, recent history queue is checked for ongoing references. This is
///            reduced as a preference to deletion from the backing database.
///   deletes: Ignored (they were never inserted).
/// ```
///
/// TODO: `store_reclaim_period`

...
["Footprint Options"]
...
ARG arg_pruning: (String) = "auto", or |c: &Config| c.footprint.as_ref()?.pruning.clone(),
			"--pruning=[METHOD]",
			"Configure pruning of the state/storage trie. METHOD may be one of auto, archive, fast: archive - keep all state trie data. No pruning. fast - maintain journal overlay. Fast but 50MB used. auto - use the method most recently synced or default to fast if none synced.",

			ARG arg_pruning_history: (u64) = 64u64, or |c: &Config| c.footprint.as_ref()?.pruning_history.clone(),
			"--pruning-history=[NUM]",
			"Set a minimum number of recent states to keep in memory when pruning is active.",

			ARG arg_pruning_memory: (usize) = 32usize, or |c: &Config| c.footprint.as_ref()?.pruning_memory.clone(),
			"--pruning-memory=[MB]",
			"The ideal amount of memory in megabytes to use to store recent states. As many states as possible will be kept within this limit, and at least --pruning-history states will always be kept.",

impl Default for ClientConfig {
	fn default() -> Self {
		let mb = 1024 * 1024;
		ClientConfig {
...
			pruning: journaldb::Algorithm::OverlayRecent,
...
		}
	}
}

/// Client pruning info. See module-level docs for more details.
#[derive(Debug, Clone)]
pub struct PruningInfo {
	/// The first block which everything can be served after.
	pub earliest_chain: u64,
	/// The first block where state requests may be served.
	pub earliest_state: u64,
}

#[derive(Debug, PartialEq)]
pub enum Pruning {
	Specific(Algorithm),
	Auto,
}

impl Default for Pruning {
	fn default() -> Self {
		Pruning::Auto
	}
}

impl Default for UserDefaults {
	fn default() -> Self {
		UserDefaults {
			is_first_launch: true,
			pruning: Algorithm::OverlayRecent,
			tracing: false,
			fat_db: false,
			mode: Mode::Active,
		}
	}
}

• Fast (OverlayRecent): keep all the full states of the B[-i] blocks; geth Fast 모드와 같다

• Light (EarlyMerge): keep all the states of the B[-i] blocks but in differential (so it is smaller than fast but slower access)

CHT(Canonical Hash Trie)

• Merkle Trie 내에서 historical block number와 canonical hash를 맵핑

• 블록헤더를 trie root(블록들의 해시의 accumulation)에 맞게 discard하는 것과 특정 블록의 해시가 이전에 검증된 것임을 증명하는 것을 가능케 한다(?)

• PIP CHT는 2048 블록마다 생성된다

• 이것은 client로 하여금 체크포인트를 부트스트랩하는 것을 약간 어렵게 만들지만, 이를 통해 라이트 노드는 풀노드에게 질의 없이도 CHT-Chain을 최신으로 유지할 수 있다.

How to prune?

• CHT를 이용하여 pruning의 구현을 제안한다

• 즉, 풀노드는 대부분의 ranges of blocks를 discard하고, 그들이 discard한 ranges에 해당하는 CHT만을 유지하면 된다.

• Kademlia Node Identifier와 유사한 방식으로, 풀노드는 특정 ranges of block과 receipt를 유지하도록 요구받을 것이다 → 그들이 유지하도록 요구받은 블록을 제공하지 못할 경우, misbehavior로 간주될 것이다

• 또 다른 방법은, 블록 넘버가 아닌 블록 해시의 prefix에 기반하여 serving blocks의 책임을 갖는 것이다 → 이는 well-partitioned mesh가 되게 하지만, sync는 많이 비효율적으로 될 것이다

Pruning Modes

• Archive (Archive): keep all states; geth Archive 모드와 같다

• Fast (OverlayRecent): keep all the full states of the B[-i] blocks; geth Fast 모드와 같다

• Light (EarlyMerge): keep all the states of the B[-i] blocks but in differential (so it is smaller than fast but slower access)

• Basic (RefCounted): keep all the states of the B[-i] blocks like with OverlayRecent but remove states after x changes (so we have only the xth last changes)

Reference

• The Parity Light Protocol - Wiki

• What is the parity light pruning mode?

• Light Ethereum Subprotocol (LES)

• https://github.com/paritytech/parity-ethereum/blob/master/ethcore/light/src/cht.rs