## Abstract / TLDR

---

This document introduces a way to reduce memory footprint of several beacon state’s slices. The main idea is the introduction of a multi-value slice construct, which allows to store both shared and individual values in a single data structure.

## Background

---

We make a lot of state copies throughout our code base. To reduce the memory size of all these copies, we do not copy slice fields, but we share these slices between states. However, when we update an index of such a shared slice, we make a copy of the entire slice so that the updated slice affects only one state. In most cases this is very inefficient because we update only one or several indices in the slice, meaning that almost all values remain the same between states. Examples:

- `BlockRoots` and `StateRoots` differ by one index between slots.
- `RandaoMixes` differs by one index between epochs.
- For `Balances`, 1 balance is updated for each withdrawal (and the maximum number of withdrawals per block is 16) and 128 indices are updated when processing the sync committee. This is nothing compared to ~500,000 balances that we store in the slice.

Throughout this document we will focus on `RandaoMixes`. It is a fixed-length slice. However, as discussed later, variable-length slices are also supported.

## Current state

---

This is the most interesting part of `BeaconState.UpdateRandaoMixesAtIndex`:

mixes := b.randaoMixes
if refs := b.sharedFieldReferences[types.RandaoMixes].Refs(); refs > 1 {
   // Copy elements in underlying array by reference.
   m := *b.randaoMixes
   mCopy := m
   mixes = &mCopy
   b.sharedFieldReferences[types.RandaoMixes].MinusRef()
   b.sharedFieldReferences[types.RandaoMixes] = stateutil.NewRef(1)
}

mixes[idx] = bytesutil.ToBytes32(val)
b.randaoMixes = mixes

Whenever the function determines that mixes are shared, it copies the entire underlying array. This means that even if we want to update a single mix, we copy all mixes.

## Desired state

---

The main building block of this design is the below code. The idea is not very complicated. Each `Value` stores a value of type `V` along with identifiers to states that have this value (see the discussion section to understand why we store identifiers instead of pointers). A `MultiValue` is just a slice of `Value`s. A `Slice` contains shared items, individual items and appended items. You can think of the shared value as the original value (i.e. the value at the point in time when the multi-value slice was constructed), and of an individual value as a changed value. There is no notion of a shared appended value because appended values never have an original value (appended values are empty when the slice is created).

Whenever we call any of the slice’s functions apart from `Init()`, we need to know which state we are dealing with. This is because if a state has an individual/appended value, we must get/change this particular value instead of the shared value, or another individual/appended value. Similarly, we must set an individual/appended value and assign it to a particular state.

The way we store appended items is worth explaining in detail. Let’s say appended items were a regular slice that is initially empty. We append an item for `state0` and then append another item for `state1`. Now we have two items in the slice, but `state1` only has an item in index `1`. This makes things very confusing and hard to deal with. If we make appended items a `[]*Value`, things don’t become much better. It is therefore easiest to make appended items a `[]*MultiValue`, which allows each state to have its own values starting at index `0` and not having any “gaps”.

The `Detach()` function should be called when a state gets garbage collected. Its purpose is to clean up the slice from individual values of the collected state. Otherwise the slice will get polluted with values for non-existing states.

// MultiValueSlice defines an abstraction over all concrete implementations of the generic Slice.
type MultiValueSlice[O interfaces.Identifiable] interface {
	Len(obj O) int
}

// Value defines a single value along with one or more IDs that share this value.
type Value[V any] struct {
	val V
	ids []interfaces.Id
}

// MultiValue defines a collection of Value items.
type MultiValue[V any] struct {
	Values []*Value[V]
}

// Slice is the main component of the multi-value slice data structure. It has two type parameters:
//   - V comparable - the type of values stored the slice. The constraint is required
//     because certain operations (e.g. updating, appending) have to compare values against each other.
//   - O interfaces.Identifiable - the type of objects sharing the slice. The constraint is required
//     because we need a way to compare objects against each other in order to know which objects
//     values should be accessed.
type Slice[V comparable, O interfaces.Identifiable] struct {
	sharedItems     []V
	individualItems map[uint64]*MultiValue[V]
	appendedItems   []*MultiValue[V]
	cachedLengths   map[interfaces.Id]int
	lock            sync.RWMutex
}

// Init initializes the slice with sensible defaults. Input values are assigned to shared items.
func (s *Slice[V, O]) Init(items []V) ...

// Len returns the number of items for the input object.
func (s *Slice[V, O]) Len(obj O) int ...

// Copy copies items between the source and destination.
func (s *Slice[V, O]) Copy(src O, dst O) ...

// Value returns all items for the input object.
func (s *Slice[V, O]) Value(obj O) []V ...

// At returns the item at the requested index for the input object.
// If the object has an individual value at that index, it will be returned. Otherwise the shared value will be returned.
// If the object has an appended value at that index, it will be returned.
func (s *Slice[V, O]) At(obj O, index uint64) (V, error) ...

// UpdateAt updates the item at the required index for the input object to the passed in value.
func (s *Slice[V, O]) UpdateAt(obj O, index uint64, val V) error ...

// Append adds a new item to the input object.
func (s *Slice[V, O]) Append(obj O, val V) ...

// Detach removes the input object from the multi-value slice.
// What this means in practice is that we remove all individual and appended values for that object and clear the cached length.
func (s *Slice[V, O]) Detach(obj O) ...

The full implementation can be found here: https://github.com/prysmaticlabs/prysm/tree/develop/container/multi-value-slice
### Example

`sX = Y` means that we set the value in state `sX` to `Y`, not that we set the state to `Y`. The whole example focuses on one slice index holding an integer value (so we technically have `Slice[uint64, *BeaconState]`).


## Benefits and drawbacks

---

The main benefit of this design is that processing time of several core code paths which dealt with copying our large slices (balances, validators, inactivity scores) should decrease significantly.

Another benefit of this solution is reduced memory usage. After running the node in Prater for about an hour, the size of randao mixes stood still at around 10MB, when normally it reaches around 60MB to 100MB. In general we can expect the size of each size to be `[num of shared values] + [num of individual values] + [number of appended values]`, where `[individual value] = [the actual value] + [one or more identifiers]` and `[appended value] = [the actual value] + [one ore more identifiers]`.

One possible drawback of this design is the amount of time it takes to loop through all indices and perform work in various functions. These are the results of benchmarking the `Value` function:

| 100,000 shared items | 0.000471609 s |
| --- | --- |
| 100,000 equal individual items | 0.000894467 s |
| 100,000 different individual items | 0.003327815 s |
| 100,000 shared items and 100,000 equal appended items | 0.000628133 s |
| 100,000 shared items and 100,000 different appended items | 0.000408510 s |
| 1,000,000 shared items | 0.003399923 s |
| 1,000,000 equal individual items | 0.009357426 s |
| 1,000,000 different individual items | 0.090267332 s |
| 1,000,000 shared items and 1,000,000 equal appended items | 0.005488982 s |
| 1,000,000 shared items and 1,000,000 different appended items | 0.004764847 s |
| 10,000,000 shared items | 0.032271737 s |
| 10,000,000 equal individual items | 0.152847482 s |
| 10,000,000 different individual items | 4.198719070 s |
| 10,000,000 shared items and 10,000,000 equal appended items | 0.101417915 s |
| 10,000,000 shared items and 10,000,000 different appended items | 1.597438640 s |

## Discussion

---

Q: The document focused on randao mixes. What about other slices of the beacon state?

A: The multi-value slice can be used for the following parts of the beacon state:

- block roots
- state roots
- randao mixes
- balances
- inactivity scores
- validators

Q: Why `Value.ids` is a slice of integers representing identifiers instead of pointers?

A: If we store pointers, then we run into a chicken-and-egg problem that results in states not being released from memory. Every state that has at least one individual value would be kept in the slice, which means we can’t collect this state before the slice is garbage collected. But since the slice is reused between states, and states keep on being copied, realistically the slice will never be claimed by the garbage collection, meaning that all these states will be forever kept in memory.

To fix the issue, we introduce an `Identifiable` interface with a single `Id()` function. The purpose of this interface is to keep track of objects in a “collection” where each object has a unique identifier and thus can be distinguished from other objects in the “collection”.

To implement the interface properly in the beacon state, we do it in the following way:

- Add an `id uint64` field to the state
- Create a global thread-safe state enumerator:

    // The below is defined in the consensus types package
    
    // Enumerator keeps track of the number of objects created since the node's start.
    type Enumerator interface {
    	Inc() uint64
    }
    
    // ThreadSafeEnumerator is a thread-safe counter of all objects created since the node's start.
    type ThreadSafeEnumerator struct {
    	counter uint64
    	lock    sync.RWMutex
    }
    
    // Inc increments the enumerator and returns the new object count.
    func (c *ThreadSafeEnumerator) Inc() uint64 {
    	c.lock.Lock()
    	c.counter++
    	v := c.counter
    	c.lock.Unlock()
    	return v
    }
    
    // The below is defined in the state package.
    
    // Enumerator keeps track of the number of states created since the node's start.
    var Enumerator consensus_types.Enumerator = &consensus_types.ThreadSafeEnumerator{}

- Populate the `id` field when creating/copying a state:

    func InitializeFromProtoUnsafePhase0(...)
    (...)
    id: types.Enumerator.Inc()
    (...)

We can also choose to use a globally unique identifier, as noticed by one of our teammates:
> Is it important the ids are increasing? If not, maybe we can just use uuidv4 as a globally unique identifier per object without need for this thread-safe enumerator