rust concurrency

Send and Sync

  • A type is Send if it is safe to send it to another thread.
  • A type is Sync if it is safe to share between threads (T is Sync if and only if &T is Send).
  • raw pointers are neither Send nor Sync (because they have no safety guards).
  • UnsafeCell isn’t Sync (and therefore Cell and RefCell aren’t).
  • Rc isn’t Send or Sync (because the refcount is shared and unsynchronized).

Types that aren’t automatically derived can simply implement them if desired:

1
2
3
4
struct MyBox(*mut u8);

unsafe impl Send for MyBox {}
unsafe impl Sync for MyBox {}

one can also unimplement Send and Sync:

1
2
3
4
5
6
7
#![feature(negative_impls)]

// I have some magic semantics for some synchronization primitive!
struct SpecialThreadToken(u8);

impl !Send for SpecialThreadToken {}
impl !Sync for SpecialThreadToken {}

reference

rust std data structure (2D)

collections

BTreeMap

  • clear(&mut self) Clears the map, removing all elements.
  • get(&self, key: &Q) Returns a reference to the value corresponding to the key.
  • get_key_value(&self, k: &Q)
  • first_key_value(&self) eturns the first key-value pair in the map.
  • first_entry(&mut self) Returns the first entry in the map for in-place manipulation
  • pop_first(&mut self)
  • last_key_value(&self)
  • last_entry(&mut self)
  • pop_last(&mut self)
  • contains_key(&self, key: &Q)
  • get_mut(&mut self, key: &Q) Returns a mutable reference to the value corresponding to the key
  • insert(&mut self, key: K, value: V)
  • try_insert(&mut self, key: K, value: V) If the map already had this key present, nothing is updated, and an error containing the occupied entry and the value is returned.
  • remove(&mut self, key: &Q)
  • remove_entry(&mut self, key: &Q)
  • retain<F>(&mut self, mut f: F) Retains only the elements specified by the predicate.
    1
    2
    3
    4
    5
    use std::collections::BTreeMap;
    let mut map: BTreeMap<i32, i32> = (0..8).map(|x| (x, x*10)).collect();
    // Keep only the elements with even-numbered keys.
    map.retain(|&k, _| k % 2 == 0);
    assert!(map.into_iter().eq(vec![(0, 0), (2, 20), (4, 40), (6, 60)]));
  • append(&mut self, other: &mut Self) Moves all elements from other into self, leaving other empty.
  • range<T: ?Sized, R>(&self, range: R) -> Range<'_, K, V> Constructs a double-ended iterator over a sub-range of elements in the map.
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    use std::collections::BTreeMap;
    use std::ops::Bound::Included;
    let mut map = BTreeMap::new();
    map.insert(3, "a");
    map.insert(5, "b");
    map.insert(8, "c");
    for (&key, &value) in map.range((Included(&4), Included(&8))) {
        println!("{key}: {value}");
    }
    assert_eq!(Some((&5, &"b")), map.range(4..).next());
  • range_mut<T: ?Sized, R>(&mut self, range: R) -> RangeMut<'_, K, V>
  • entry(&mut self, key: K) Gets the given key’s corresponding entry in the map for in-place manipulation.
    1
    2
    3
    4
    5
    6
    7
    8
    9
    use std::collections::BTreeMap;
    let mut count: BTreeMap<&str, usize> = BTreeMap::new();
    // count the number of occurrences of letters in the vec
    for x in ["a", "b", "a", "c", "a", "b"] {
        count.entry(x).and_modify(|curr| *curr += 1).or_insert(1);
    }
    assert_eq!(count["a"], 3);
    assert_eq!(count["b"], 2);
    assert_eq!(count["c"], 1);
  • split_off<Q: ?Sized + Ord>(&mut self, key: &Q) Splits the collection into two at the given key. Returns everything after the given key,
  • drain_filter<F>(&mut self, pred: F) Creates an iterator that visits all elements (key-value pairs) in ascending key order and uses a closure to determine if an element should be removed. If the closure returns true, the element is removed from the map and yielded. If the closure returns false, or panics, the element remains in the map and will not be yielded
  • into_keys(self) Creates a consuming iterator visiting all the keys, in sorted order. The map cannot be used after calling this
  • into_values(self)

rust std data structure (1D)

array

A fixed-size array, denoted [T; N], for the element type, T, and the non-negative compile-time constant size, N.

1
todo!()

slice

A dynamically-sized view into a contiguous sequence, [T].

  • len(): Returns the number of elements in the slice
  • is_empty()
  • first() Returns the first element of the slice, or None if it is empty.
  • first_mut() Returns a mutable pointer to the first element of the slice, or None if it is empty
  • split_first() Returns the first and all the rest of the elements of the slice, or None if it is empty.
  • split_first_mut()
  • split_last()
  • split_last_mut()
  • last()
  • last_mut()
  • get<I>(index: I) Returns a reference to an element or subslice depending on the type of index.
    1
    2
    3
    let v = [10, 40, 30];
    assert_eq!(Some(&40), v.get(1));
    assert_eq!(Some(&[10, 40][..]), v.get(0..2));
  • get_mut<I>(index: I)
  • get_unchecked<I>(index: I) Returns a reference to an element or subslice, without doing bounds checking
  • get_unchecked_mut<I>(index: I)
  • as_ptr(&self) -> *const T Returns a raw pointer to the slice’s buffer
    1
    2
    3
    4
    5
    6
    7
    let x = &[1, 2, 4];
    let x_ptr = x.as_ptr();
    unsafe {
        for i in 0..x.len() {
            assert_eq!(x.get_unchecked(i), &*x_ptr.add(i));
        }
    }
  • as_mut_ptr(&mut self) -> *mut T 
    1
    2
    3
    4
    5
    6
    7
    8
    let x = &mut [1, 2, 4];
    let x_ptr = x.as_mut_ptr();
    unsafe {
        for i in 0..x.len() {
            *x_ptr.add(i) += 2;
        }
    }
    assert_eq!(x, &[3, 4, 6]);
  • as_ptr_range(&self) -> Range<*const T> Returns the two raw pointers spanning the slice.
    1
    2
    3
    4
    5
    pub const fn as_ptr_range(&self) -> Range<*const T> {
        let start = self.as_ptr();
        let end = unsafe { start.add(self.len()) };
        start..end
    }
  • as_mut_ptr_range(&mut self) -> Range<*mut T>
  • swap(&mut self, a: usize, b: usize) Swaps two elements in the slice.
  • reverse(&mut self) Reverses the order of elements in the slice, in place.
  • windows(&self, size: usize) Returns an iterator over all contiguous windows of length size. The windows overlap. If the slice is shorter than size, the iterator returns no values.
    1
    2
    3
    4
    5
    6
    let slice = ['r', 'u', 's', 't'];
    let mut iter = slice.windows(2);
    assert_eq!(iter.next().unwrap(), &['r', 'u']);
    assert_eq!(iter.next().unwrap(), &['u', 's']);
    assert_eq!(iter.next().unwrap(), &['s', 't']);
    assert!(iter.next().is_none());
  • chunks(&self, chunk_size: usize) Returns an iterator over chunk_size elements of the slice at a time
    1
    2
    3
    4
    5
    6
    let slice = ['l', 'o', 'r', 'e', 'm'];
    let mut iter = slice.chunks(2);
    assert_eq!(iter.next().unwrap(), &['l', 'o']);
    assert_eq!(iter.next().unwrap(), &['r', 'e']);
    assert_eq!(iter.next().unwrap(), &['m']);
    assert!(iter.next().is_none());
  • chunks_mut()
  • chunks_exact(&self, chunk_size: usize)
    1
    2
    3
    4
    5
    6
    let slice = ['l', 'o', 'r', 'e', 'm'];
    let mut iter = slice.chunks_exact(2);
    assert_eq!(iter.next().unwrap(), &['l', 'o']);
    assert_eq!(iter.next().unwrap(), &['r', 'e']);
    assert!(iter.next().is_none());
    assert_eq!(iter.remainder(), &['m']);
  • as_chunks_unchecked<const N: usize>(&self) Splits the slice into a slice of N-element arrays, assuming that there’s no remainder
  • as_chunks<const N: usize>(&self) Splits the slice into a slice of N-element arrays, starting at the beginning of the slice, and a remainder slice with length strictly less than N
  • as_rchunks<const N: usize>(&self) r means reverse
  • group_by<F>(&self, pred: F) Returns an iterator over the slice producing non-overlapping runs of elements using the predicate to separate them. The predicate is called on two elements following themselves, it means the predicate is called on slice[0] and slice[1] then on slice[1] and slice[2] and so on
    1
    2
    3
    4
    5
    6
    7
    #![feature(slice_group_by)]
    let slice = &[1, 1, 2, 3, 2, 3, 2, 3, 4];
    let mut iter = slice.group_by(|a, b| a <= b);
    assert_eq!(iter.next(), Some(&[1, 1, 2, 3][..]));
    assert_eq!(iter.next(), Some(&[2, 3][..]));
    assert_eq!(iter.next(), Some(&[2, 3, 4][..]));
    assert_eq!(iter.next(), None);
  • split_at(&self, mid: usize) Divides one slice into two at an index.
  • split<F>(&self, pred: F) Returns an iterator over subslices separated by elements that match pred. The matched element is not contained in the subslices.
  • splitn<F>(&self, n: usize, pred: F)
  • contains(&self, x: &T) Returns true if the slice contains an element with the given value.
  • starts_with(&self, needle: &[T]) eturns true if needle is a prefix of the slice
    1
    2
    3
    4
    let v = [10, 40, 30];
    assert!(v.starts_with(&[10]));
    assert!(v.starts_with(&[10, 40]));
    assert!(!v.starts_with(&[50]));
  • ends_with(&self, needle: &[T])
  • strip_prefix Returns a subslice with the prefix removed.
    1
    2
    3
    4
    5
    6
    let v = &[10, 40, 30];
    assert_eq!(v.strip_prefix(&[10]), Some(&[40, 30][..]));
    assert_eq!(v.strip_prefix(&[50]), None);
    let prefix : &str = "he";
    assert_eq!(b"hello".strip_prefix(prefix.as_bytes()),
               Some(b"llo".as_ref()));
  • strip_suffix
  • binary_search(&self, x: &T) Binary searches this slice for a given element.
  • sort_unstable(&mut self) Sorts the slice, but might not preserve the order of equal elements.
  • rotate_left(&mut self, mid: usize) Rotates the slice in-place such that the first mid elements of the slice move to the end while the last self.len() - mid elements move to the front.
  • fill(&mut self, value: T) Fills self with elements by cloning value.
  • clone_from_slice(&mut self, src: &[T]) Copies the elements from src into self.
  • copy_from_slice(&mut self, src: &[T])
  • is_sorted(&self)
  • take<'a, R: OneSidedRange<usize>>(self: &mut &'a Self, range: R) Removes the subslice corresponding to the given range
  • get_many_mut<const N: usize> Returns mutable references to many indices at once.
    1
    2
    3
    4
    5
    6
    7
    #![feature(get_many_mut)]
    let v = &mut [1, 2, 3];
    if let Ok([a, b]) = v.get_many_mut([0, 2]) {
        *a = 413;
        *b = 612;
    }
    assert_eq!(v, &[413, 2, 612]);

alloc::vec::Vec

  • fn truncate(&mut self, len: usize) Shortens the vector, keeping the first len elements and dropping the rest

std::collections::VecDeque

A double-ended queue (deque) implemented with a growable ring buffer.
Since VecDeque is a ring buffer, its elements are not necessarily contiguous in memory. If you want to access the elements as a single slice, such as for efficient sorting, you can use make_contiguous. It rotates the VecDeque so that its elements do not wrap, and returns a mutable slice to the now-contiguous element sequence.

  • swap(&mut self, i: usize, j: usize)
  • reserve_exact(&mut self, additional: usize) Reserves the minimum capacity for at least additional more elements to be inserted in the given deque. Does nothing if the capacity is already sufficient.
  • reserve(&mut self, additional: usize)
  • shrink_to_fit(&mut self) Shrinks the capacity of the deque as much as possible.
  • truncate(&mut self, len: usize) Shortens the deque, keeping the first len elements and dropping the rest.
    1
    2
    3
    4
    5
    6
    7
    8
    use std::collections::VecDeque;
    let mut buf = VecDeque::new();
    buf.push_back(5);
    buf.push_back(10);
    buf.push_back(15);
    assert_eq!(buf, [5, 10, 15]);
    buf.truncate(1);
    assert_eq!(buf, [5]);
  • iter(&self)
  • as_slices(&self)
  • slice_ranges<R>(&self, range: R) Given a range into the logical buffer of the deque, this function return two ranges into the physical buffer that correspond to the given range
  • range<R>(&self, range: R) Creates an iterator that covers the specified range in the deque.
    1
    2
    3
    4
    5
    6
    7
    use std::collections::VecDeque;
    let deque: VecDeque<_> = [1, 2, 3].into();
    let range = deque.range(2..).copied().collect::<VecDeque<_>>();
    assert_eq!(range, [3]);
    // A full range covers all contents
    let all = deque.range(..);
    assert_eq!(all.len(), 3);
  • drain<R>(&mut self, range: R) Removes the specified range from the deque in bulk, returning all removed elements as an iterator.
  • clear(&mut self)
  • contains(&self, x: &T) Returns true if the deque contains an element equal to the given value
  • front(&self) Provides a reference to the front element
  • front_mut(&mut self)
  • back(&self)
  • back_mut(&mut self)
  • pop_front(&mut self)
  • pop_back(&mut self)
  • push_front(&mut self, value: T)
  • push_back(&mut self, value: T)

std::collections::LinkedList

rust functional programming

iterator

  • iter() Returns an iterator over the slice
  • into_iter() Creates a consuming iterator, that is, one that moves each value out of the vector
  • iter_mut() Returns an iterator that allows modifying each value.

flat_map

1
2
3
4
5
6
/// Creates an iterator that works like map, but flattens nested structure.
///
/// The [`map`] adapter is very useful, but only when the closure
/// argument produces values. If it produces an iterator instead, there's
/// an extra layer of indirection. `flat_map()` will remove this extra layer
/// on its own.

Examples

1
2
3
4
5
6
let words = ["alpha", "beta", "gamma"];
// chars() returns an iterator
let merged: String = words.iter()
                          .flat_map(|s| s.chars())
                          .collect();
assert_eq!(merged, "alphabetagamma");

rust crate serde 

1
2
3
4
5
6
7
#[serde(tag = "filterType")]
#[serde(untagged)]
#[serde(rename = "PRICE_FILTER")]
#[serde(rename_all = "camelCase")]

#[serde(with = "string_or_float")]
pub stop_price: f64,

geth state prune

NOTE: Offline pruning is only for the hash-based state scheme. In future release, geth will have a path-based state scheme which enables the pruning by default. Once the hash-based state scheme is no longer supported, offline pruning will be deprecated.

introduction

A snap-sync’d Geth node currently requires more than 650 GB of disk space to store the historic blockchain data. With default cache size the database grows by about 14 GB/week. Since Geth v1.10, users have been able to trigger a snapshot offline prune to bring the total storage back down to the original ~650 GB in about 4-5 hours.

how pruning works

Pruning uses snapshots of the state database as an indicator to determine which nodes in the state trie can be kept and which ones are stale and can be discarded. Geth identifies the target state trie based on a stored snapshot layer which has at least 128 block confirmations on top (for surviving reorgs) data that isn’t part of the target state trie or genesis state.

Geth prunes the database in three stages:

  1. Iterating state snapshot: Geth iterates the bottom-most snapshot layer and constructs a bloom filter set for identifying the target trie nodes.
  2. Pruning state data: Geth deletes stale trie nodes from the database which are not in the bloom filter set.
  3. Compacting database: Geth tidies up the new database to reclaim free space.

Pruning command

1
geth snapshot prune-state

references

geth sync

state

Ethereum maintains two different types of state: the set of accounts; and a set of storage slots for each contract account. Naively, storing these key-value pairs as flat data would be very efficient, however, verifying their correctness becomes computationally intractable. Every time a modification would be made, we’d need to hash all that data from scratch (which is not efficient).

Instead of hashing the entire dataset all the time, eth uses MPT. The original useful data would be in the leaves, and each internal node would be a hash of everything below it. This would allow us to only recalculate a logarithmic number of hashes when something is modified, inserted, deleted and verified. A tiny extra is that keys are hashed before insertion to balance the tries (secured trie).

state storage

MPT make every read/write of O(lnN) complexity. the depth of the trie is continuously growing; LevelDB also organizes its data into a maximum of 7 levels, so there’s an extra multiplier from there. The net result is that a single state access is expected to amplify into 25-50 random disk accesses.

Of course all client implementations try their best to minimize this overhead. Geth uses large memory areas for caching trie nodes; and also uses in-memory pruning to avoid writing to disk nodes that get deleted anyway after a few blocks.

Not all accesses are created equal

The Merkle Patricia tree is essential for writes (matain the capability to verify data), but it’s an overhead for reads.
An Ethereum node accesses state in a few different places:

  • When importing a new block, EVM code execution does a more-or-less balanced number of state reads and writes.
  • When a node operator retrieves state (e.g. eth_call and family), EVM code execution only does reads (it can write too, but those get discarded at the end and are not persisted).
  • When a node is synchronizing, it is requesting state from remote nodes that need to dig it up and serve it over the network.

if we can short circuit reads not to hit the state trie, a slew of node operations will become significantly faster.

snapshot

Geth introduced its snapshot acceleration structure (not enabled by default). A snapshot is a complete view of the Ethereum state at a given block. Abstract implementation wise, it is a dump of all accounts and storage slots, represented by a flat key-value store.
snapshot is maintained as an extra to MPT. The snapshot essentially reduces reads from O(log n) to O(1) at the cost of increasing writes from O(log n) to O(1 + log n).

devil’s in the details

to maintain a snapshot, the naitve approach is to apply changes to current snapshot upon new block. If there’s a mini reorg however (even a single block), we’re in trouble, because there’s no undo.
To overcome this limitation, Geth’s snapshot is composed of two entities: a persistent disk layer that is a complete snapshot of an older block (e.g. HEAD-128); and a tree of in-memory diff layers that gather the writes on top.
Whenever a new block is processed, we do not merge the writes directly into the disk layer, rather just create a new in-memory diff layer with the changes. If enough in-memory diff layers are piled on top, the bottom ones start getting merged together and eventually pushed to disk. Whenever a state item is to be read, we start at the topmost diff layer and keep going backwards until we find it or reach the disk.
Of course, there are lots and lots of gotchas and caveats.

  • On shutdown, the in-memory diff layers need to be persisted into a journal and loaded back up, otherwise the snapshot will become useless on restart.
  • Use the bottom-most diff layer as an accumulator and only flush to disk when it exceeds some memory usage.
  • Allocate a read cache for the disk layer so that contracts accessing the same ancient slot over and over don’t cause disk hits.
  • Use cumulative bloom filters in the in-memory diff layers to quickly detect whether there’s a chance for an item to be in the diffs, or if we can go to disk immediately.
  • The keys are not the raw data (account address, storage key), rather the hashes of these, ensuring the snapshot has the same iteration order as the Merkle Patricia tree.

The snapshot also enables blazing fast state iteration of the most recent blocks. This was actually the main reason for building snapshots, as it permitted the creation of the new snap sync algorithm.

Consensus layer syncing

all consensus logic and block propagation is handled by consensus clients. Blocks are downloaded by the consensus client and verified by the execution client. Geth cannot sync without being connected to a consensus client.
There are two ways for the consensus client to find a block header that Geth can use as a sync target: optimistic syncing and checkpoint syncing:

optimistic sync

Optimistic sync downloads blocks before the execution client has validated them. In optimistic sync the node assumes the data it receives from its peers is correct during the downloading phase but then retroactively verifies each downloaded block.
more details

checkpoint sync

Alternatively, the consensus client can grab a checkpoint from a trusted source which provides a target state to sync up to, before switching to full sync and verifying each block in turn. In this mode, the node trusts that the checkpoint is correct.

archive nodes

An archive node is a node that retains all historical data right back to genesis. There is no need to regenerate any data from checkpoints because all data is directly available in the node’s own storage.

It is also possible to create a partial/recent archive node where the node was synced using snap but the state is never pruned. This creates an archive node that saves all state data from the point that the node first syncs. This is configured by starting Geth with --syncmode snap --gcmode archive.

light nodes

A light node syncs very quickly and stores the bare minimum of blockchain data. Light nodes only process block headers, not entire blocks. they receive a proof from the full node and verify it against their local header chain. Light nodes are not currently working on proof-of-stake Ethereum.

full node

full

A full block-by-block sync generates the current state by executing every block starting from the genesis block. A full sync independently verifies block provenance as well as all state transitions by re-executing the transactions in the entire historical sequence of blocks. Only the most recent 128 block states are stored in a full node - older block states are pruned periodically and represented as a series of checkpoints from which any previous state can be regenerated on request.

snap sync (default)

Snap sync starts from a relatively recent block and syncs from there to the head of the chain, keeping only the most recent 128 block states in memory. The block header to sync up to is provided by the consensus client. Between the initial sync block and the 128 most recent blocks, the node stores occasional snapshots that can be used to rebuild any intermediate state “on-the-fly”. The difference between the snap-synced node and a full block-by-block synced node is that a snap synced node started from an initial checkpoint that was more recent than the genesis block. Snap sync is much faster than a full block-by-block sync from genesis.
sync mode

Snap sync works by first downloading the headers for a chunk of blocks. Once the headers have been verified, the block bodies and receipts for those blocks are downloaded. In parallel, Geth also begins state-sync. In state-sync, Geth first downloads the leaves of the state trie for each block without the intermediate nodes along with a range proof. The state trie is then regenerated locally.

The state download is the part of the snap-sync that takes the most time to complete and the progress can be monitored using the ETA values in the log messages. However, the blockchain is also progressing at the same time and invalidating some of the regenerated state data. (don’t really understand why regenrated state could be invalidated). This means it is also necessary to have a ‘healing’ phase where errors in the state are fixed. Geth regularly reports Syncing, state heal in progress during state healing - this informs the user that state heal has not finished.

The healing has to outpace the growth of the blockchain, otherwise the node will never catch up to the current state.

To summarize, snap sync progresses in the following sequence:

  • download and verify headers
  • download block bodies and receipts. In parallel, download raw state data and build state trie
  • heal state trie to account for newly arriving data

A node that is started using snap will switch to block-by-block sync once it has caught up to the head of the chain.

references

geth v1.10.0 summary

introduction

geth v1.10.0 has been released on Mar 4 2021. this is a late summary of v1.10.0.

snapshots

the snapshot feature reduces the cost of accessing an account from O(logN) to O(1). Whilst snapshots do grant us a 10x read performance, EVM execution also writes data, and these writes need to be Merkle proven. The Merkle proof requirement retains the necessity for O(logN) disk access on writes.
Problems it solves

  • DoS In 2016, Ethereum sustained its worse DoS attack ever - The Shanghai Attacks - that lasted about 2-3 months. The attack revolved around bloating Ethereum’s state and abusing various underpriced opcodes to grind the network to a halt. After numerous client optimizations and repricing hard forks, the attack was repelled. The root cause still lingers: state access opcodes have a fixed EVM gas cost O(1), but an ever slowly increasing execution cost O(logN). Snapshots on the other hand reduce execution cost of state reads to O(1) - in line with EVM costs - thus solves the read-based DoS issues long term.
  • Call Checking a smart contract’s state in Ethereum entails a mini EVM execution. Part of that is running bytecode and part of it is reading state slots from disk. snap makes the state access faster.
  • Sync There are two major ways you can synchronize an Ethereum node. You can download the blocks and execute all the transactions within; or you can download the blocks, verify the PoWs and download the state associated a recent block. The latter is much faster, but it relies on benefactors serving you a copy of the recent state. With the current Merkle-Patricia state model, these benefactors read 16TB of data off disk to serve a syncing node. Snapshots enable serving nodes to read only 96GB of data off disk to get a new node joined into the network.

drawbacks of snapshot

  • A snapshot is a redundant copy of the raw Ethereum state already contained in the leaves of the Merkle Patricia trie.
    user can disable snapshot via --snapshot=false

snap sync

When Ethereum launched, you could choose from two different ways to synchronize the network: full sync and fast sync。 Full sync operated by downloading the entire chain and executing all transactions; vs. fast sync placed an initial trust in a recent-ish block, and directly downloaded the state associated with it (after which it switched to block execution like full sync).

  • full sync minimized trust, choosing to execute all transactions from genesis to head.
  • fast sync chose to rely on the security of the PoWs.it assumed that a block with 64 valid PoWs on top would be prohibitively expensive for someone to construct, as such it’s ok to download the state associated with HEAD-64

delays of fast sync

  • network latency (download node)
  • io latency (level db random disk access)
  • upload latency (requst with node hash to remote servers)

The core idea of snap sync is fairly simple: instead of downloading the trie node-by-node, snap sync downloads the contiguous chunks of useful state data, and reconstructs the Merkle trie locally:

  • Without downloading intermediate Merkle trie nodes, state data can be fetched in large batches, removing the delay caused by network latency.
  • Without downloading Merkle nodes, downstream data drops to half; and without addressing each piece of data individually, upstream data gets insignificant, removing the delay caused by bandwidth.
  • Without requesting randomly keyed data, peers do only a couple contiguous disk reads to serve the responses, removing the delay of disk IO

offline pruning

When processing a new block, a node takes the current state of the network as input data and mutates it according to the transactions in the block. only state diff is kept. Pushing these new pieces of state data, block-by-block, to the database is a problem. They keep accumulating. In theory we could “just delete” state data that’s old enough to not run the risk of a reorg. it’s exceedingly costly to figure out if a node deep within an old state is still referenced by anything newer or not.
If you have snapshots enabled and fully generated, Geth can use those as an acceleration structure to relatively quickly determine which trie nodes should be kept and which should be deleted. Pruning trie nodes based on snapshots does have the drawback that the chain may not progress during pruning. This means, that you need to stop Geth, prune its database and then restart it. To prune your database, please run geth snapshot prune-state.

transaction unindexing

Node operators always took it for granted that they can look up an arbitrary transaction from the past, given only its hash. To make transactions searchable, we need to - at minimum - map the entire range of transaction hashes to the blocks they are in. It’s also important to note that transaction indices are not part of consensus and are not part of the network protocol. They are purely a locally generated acceleration structure.
Geth v1.10.0 switches on transaction unindexing by default and sets it to 2,350,000 blocks (about 1 year). The transaction unindexer will linger in the background, and every time a new block arrives, it ensures that only transactions from the most recent N blocks are indexed, deleting older ones. user can use --txlookuplimit to control the indexing block range

preimage discarding

Ethereum stores all its data in a Merkle Patricia trie. The values in the leaves are the raw data being stored (e.g. storage slot content, account content), and the path to the leaf is the key at which the data is stored. The keys however are not the account addresses or storage addresses, rather the Keccak256 hashes of those. This helps balance the branch depths of the state tries.
the preimage is the actual key related to the hash. The preimages aren’t particularly heavy. If you do a full sync from genesis - reexecuting all the transactions - you’ll only end up with 5GB extra load. Still, there is no reason to keep that data around for users not using it, as it only increases the load on LevelDB compactions. As such, Geth v1.10.0 disables preimage collection by default, but there’s no mechanism to actively delete already stored preimages.
If you are using your Geth instance to debug transactions, you can retain the original behavior via --cache.preimages.

ETH/66 protocol

The eth/66 protocol is a fairly small change, yet has quite a number of beneficial implications. In short, the protocol introduces request and reply IDs for all bidirectional packets. The goal behind these IDs is to more easily match up responses to requests, specifically, to more easily deliver a response to a subsystem that made the original request.

chainid enforcement

Geth v1.10.0 supports reverting to the old behavior and accepting non-EIP155 transactions via –rpc.allow-unprotected-txs. Be advised that this is a temporary mechanism that will be removed long term.

Database introspection

Every now and again we receive an issue report about a corrupted database, with no real way to debug it. Geth v1.10.0 ships a built-in database introspection tool to try and alleviate the situation a bit. It is a very low level accessor to LevelDB, but it allows arbitrary data retrievals, insertions and deletions. We are unsure how useful these will turn out to be, but they at least give a fighting chance to restore a broken node without having to resync.

Unclean shutdown tracking

Fairly often we receive bug reports that Geth started importing old blocks on startup. This phenomenon is generally caused by the node operator terminating Geth abruptly (power outage, OOM killer, too short shutdown timeout). Since Geth keeps a lot of dirty state in memory - to avoid writing to disk things that get stale a few blocks later - an abrupt shutdown can cause these to not be flushed. With recent state missing on startup, Geth has no choice but to rewind it’s local chain to the point where it last saved the progress.

Geth v1.10.0 will start tracking and reporting node crashes. We’re hopeful that this will allow operatos to detect that their infra is misconfigured or has issue before those turn into irreversible data loss.

1
WARN [03-03|06:36:38.734] Unclean shutdown detected        booted=2021-02-03T06:47:28+0000 age=3w6d23h

references

go similar concepts comparison

struct{} & struct{}{}

struct is a keyword in Go. It is used to define struct types, which is a sequence of named elements.

For example:

1
2
3
4
type Person struct {
    Name string
    Age  int
}

The struct{} is a struct type with zero elements. It is often used when no information is to be stored. It has the benefit of being 0-sized, so usually no memory is required to store a value of type struct{}.

struct{}{} on the other hand is a composite literal, it constructs a value of type struct{}. A composite literal constructs values for types such as structs, arrays, maps and slices. Its syntax is the type followed by the elements in braces. Since the “empty” struct (struct{}) has no fields, the elements list is also empty:

struct{} {}
| ^ | ^
type empty element list
As an example let’s create a “set” in Go. Go does not have a builtin set data structure, but it has a builtin map. We can use a map as a set, as a map can only have at most one entry with a given key. And since we want to only store keys (elements) in the map, we may choose the map value type to be struct{}.

A map with string elements:

1
2
3
4
5
6
7
8
9
10
11
12
13
var set map[string]struct{}
// Initialize the set
set = make(map[string]struct{})

// Add some values to the set:
set["red"] = struct{}{}
set["blue"] = struct{}{}

// Check if a value is in the map:
_, ok := set["red"]
fmt.Println("Is red in the map?", ok)
_, ok = set["green"]
fmt.Println("Is green in the map?", ok)

go reflect

introduction

Reflection is the ability of a program to examine its own structure, particularly through types.

type and interfaces

Go is statically typed. Every variable has a static type, Exactly one type known and fixed at compile time. If we declare

1
2
3
4
type MyInt int

var i int
var j MyInt

The variables i and j have distinct static types and, although they have the same underlying type, they cannot be assigned to one another without a conversion.

One important category of type is interface types, which represent fixed sets of methods. An interface variable can store any concrete (non-interface) value as long as that value implements the interface’s methods. An extremely important example of an interface type is the empty interface:

1
interface{}

or its equivalent alias,

1
any

It represents the empty set of methods and is satisfied by any value at all, since every value has zero or more methods.
a variable of interface type always has the same static type, and even though at run time the value stored in the interface variable may change type, that value will always satisfy the interface.

the representation of an interface

A variable of interface type stores a pair: the concrete value assigned to the variable, and that value’s type descriptor.
For instance, after

1
2
3
4
5
6
var r io.Reader
tty, err := os.OpenFile("/dev/tty", os.O_RDWR, 0)
if err != nil {
    return nil, err
}
r = tty

r contains, schematically, the (value, type) pair, (tty, *os.File). Notice that the type *os.File implements methods other than Read; even though the interface value provides access only to the Read method, the value inside carries all the type information about that value. That’s why we can do things like this:

1
2
var w io.Writer
w = r.(io.Writer)

The expression in this assignment is a type assertion; what it asserts is that the item inside r also implements io.Writer, and so we can assign it to w. After the assignment, w will contain the pair (tty, *os.File). That’s the same pair as was held in r.
One important detail is that the pair inside an interface variable always has the form (value, concrete type) and cannot have the form (value, interface type). Interfaces do not hold interface values.

the first law of reflection

  1. Reflection goes from interface value to reflection object
    At the basic level, reflection is just a mechanism to examine the type and value pair stored inside an interface variable. reflect.TypeOf and reflect.ValueOf, retrieve reflect.Type and reflect.Value pieces out of an interface value.

    1
    2
    var x float64 = 3.4
    fmt.Println("type:", reflect.TypeOf(x))
    1
    type: float64
    1
    2
    3
    4
    5
    var x float64 = 3.4
    v := reflect.ValueOf(x)
    fmt.Println("type:", v.Type())
    fmt.Println("kind is float64:", v.Kind() == reflect.Float64)
    fmt.Println("value:", v.Float())
    1
    2
    3
    type: float64
    kind is float64: true
    value: 3.4

    There are also methods like SetInt and SetFloat. to keep the API simple, the “getter” and “setter” methods of Value operate on the largest type that can hold the value: int64 for all the signed integers, for instance. 

    1
    2
    3
    4
    5
    var x uint8 = 'x'
    v := reflect.ValueOf(x)
    fmt.Println("type:", v.Type())                            // uint8.
    fmt.Println("kind is uint8: ", v.Kind() == reflect.Uint8) // true.
    x = uint8(v.Uint())                                       // v.Uint returns a uint64.

  2. Reflection goes from reflection object to interface value.
    Given a reflect.Value we can recover an interface value using the Interface method;

    1
    2
    3
    4
    5
    // Interface returns v's current value as an interface{}.
    // It is equivalent to:
    //
    //	var i interface{} = (v's underlying value)
    func (v Value) Interface() interface{}
    1
    2
    y := v.Interface().(float64) // y will have type float64.
    fmt.Println(y)

  3. To modify a reflection object, the value must be settable.
    The CanSet method of Value reports the settability of a Value; in our case,

    1
    2
    3
    var x float64 = 3.4
    v := reflect.ValueOf(x)
    fmt.Println("settability of v:", v.CanSet())
    1
    settability of v: false

    we pass a copy of x to reflect.ValueOf, so the interface value created as the argument to reflect.ValueOf is a copy of x, not x itself. Thus, if the statement v.SetFloat(7.1) were allowed to succeed, it would not update x, even though v looks like it was created from x. Instead, it would update the copy of x stored inside the reflection value and x itself would be unaffected. That would be confusing and useless, so it is illegal, and settability is the property used to avoid this issue. If we want to modify x by reflection, we must give the reflection library a pointer to the value we want to modify.
    Let’s do that. 

    1
    2
    3
    4
    var x float64 = 3.4
    p := reflect.ValueOf(&x) // Note: take the address of x.
    fmt.Println("type of p:", p.Type())
    fmt.Println("settability of p:", p.CanSet())

    The reflection object p isn’t settable, but it’s not p we want to set, it’s (in effect) *p. To get to what p points to, we call the Elem method of Value, which indirects through the pointer, and save the result in a reflection Value called v:

    1
    2
    v := p.Elem()
    fmt.Println("settability of v:", v.CanSet())
    1
    settability of v: true

structs

1
2
3
4
5
6
7
8
9
10
11
12
type T struct {
    A int
    B string
}
t := T{23, "skidoo"}
s := reflect.ValueOf(&t).Elem()
typeOfT := s.Type()
for i := 0; i < s.NumField(); i++ {
    f := s.Field(i)
    fmt.Printf("%d: %s %s = %v\n", i,
        typeOfT.Field(i).Name, f.Type(), f.Interface())
}
1
2
0: A int = 23
1: B string = skidoo

There’s one more point about settability introduced in passing here: the field names of T are upper case (exported) because only exported fields of a struct are settable.
Because s contains a settable reflection object, we can modify the fields of the structure.

1
2
3
s.Field(0).SetInt(77)
s.Field(1).SetString("Sunset Strip")
fmt.Println("t is now", t)

If we modified the program so that s was created from t, not &t, the calls to SetInt and SetString would fail as the fields of t would not be settable.

references