Enum mz_storage::upsert::types::StateValue

pub enum StateValue<O> {
    Snapshotting(Snapshotting),
    Value(Value<O>),
}

UpsertState has 2 modes:

• Normal operation
• Consolidation of snapshots (during rehydration).

This struct and its substructs are helpers to simplify the logic that individual UpsertState implementations need to do to manage these 2 modes.

Normal operation is simple, we just store an ordinary UpsertValue, and allow the implementer to store it any way they want. During consolidation of snapshots, the logic is more complex. See the docs on StateValue::merge_update for more information.

Note also that this type is designed to support partial updates. All values are associated with an order key O that can be used to determine if a value existing in the UpsertStateBackend occurred before or after a value being considered for insertion.

O typically required to be : Default, with the default value sorting below all others. Values consolidated during snapshotting consolidate correctly (as they are actual differential updates with diffs), so order keys are not required.

Variants

Snapshotting(Snapshotting)

Value(Value<O>)

Implementations

impl<O> StateValue<O>

pub fn value(value: Result<Row, UpsertError>, order: O) -> Self

A normal value occurring at some order key.

pub fn tombstone(order: O) -> Self

A tombstoned value occurring at some order key.

pub fn is_tombstone(&self) -> bool

Whether the value is a tombstone.

pub fn order(&self) -> &O

Pull out the order for the given Value, assuming ensure_decoded has been called.

pub fn into_decoded(self) -> Value<O>

Pull out the Value value for a StateValue, after ensure_decoded has been called.

pub fn memory_size(&self) -> u64

The size of a StateValue, in memory. This is:

1. only used in the InMemoryHashMap implementation.
2. An estimate (it only looks at value sizes, and not errors)

Other implementations may use more accurate accounting.

impl<O: Default> StateValue<O>

pub fn merge_update( &mut self, value: Result<Row, UpsertError>, diff: Diff, bincode_opts: DefaultOptions, bincode_buffer: &mut Vec<u8>, ) -> bool

We use a XOR trick in order to accumulate the snapshot without having to store the full unconsolidated history in memory. For all (value, diff) updates of a key we track:

• diff_sum = SUM(diff)
• checksum_sum = SUM(checksum(bincode(value)) * diff)
• len_sum = SUM(len(bincode(value)) * diff)
• value_xor = XOR(bincode(value))

Return value

Returns a bool indicating whether or not the current merged value is able to be deleted.

Correctness

The method is correct because a well formed upsert snapshot will have for each key:

• Zero or one updates of the form (cur_value, +1)
• Zero or more pairs of updates of the form (prev_value, +1), (prev_value, -1)

We are interested in extracting the cur_value of each key and discard all prev_values that might be included in the stream. Since the history of prev_values always comes in pairs, computing the XOR of those is always going to cancel their effects out. Also, since XOR is commutative this property is true independent of the order. The same is true for the summations of the length and checksum since the sum will contain the unrelated values zero times.

Therefore the accumulators will end up precisely in one of two states:

1. diff == 0, checksum == 0, value == [0..] => the key is not present
2. diff == 1, checksum == checksum(cur_value) value == cur_value => the key is present

Robustness

In the absense of bugs, accumulating the diff and checksum is not required since we know that a well formed snapshot always satisfies XOR(bincode(values)) == bincode(cur_value). However bugs may happen and so storing 16 more bytes per key to have a very high guarantee that we’re not decoding garbage is more than worth it. The main key->value used to store previous values.

pub fn merge_update_state(&mut self, other: &Self)

Merge an existing StateValue into this one, using the same method described in merge_update. See the docstring above for more information on correctness and robustness.

pub fn ensure_decoded(&mut self, bincode_opts: DefaultOptions)

After consolidation of a snapshot, we assume that all values in the UpsertStateBackend implementation are Self::Snapshotting, with a diff_sum of 1 (or 0, if they have been deleted). Afterwards, if we need to retract one of these values, we need to assert that its in this correct state, then mutate it to its Value state, so the upsert operator can use it.

Trait Implementations

impl<O: Clone> Clone for StateValue<O>

fn clone(&self) -> StateValue<O>

Returns a copy of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl<O: Debug> Debug for StateValue<O>

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<O> Default for StateValue<O>

fn default() -> Self

Returns the “default value” for a type.

impl<'de, O> Deserialize<'de> for StateValue<O>

where O: Deserialize<'de>,

fn deserialize<__D>(__deserializer: __D) -> Result<Self, __D::Error>

where __D: Deserializer<'de>,

Deserialize this value from the given Serde deserializer.

impl<O> Serialize for StateValue<O>

where O: Serialize,

fn serialize<__S>(&self, __serializer: __S) -> Result<__S::Ok, __S::Error>

where __S: Serializer,

Serialize this value into the given Serde serializer.