Skip to content

blockstm: support rolling commit #25776

@yihuang

Description

@yihuang

Basically we want to know when does a transaction is committed during parallel block execution, a committed transaction won’t be re-executed again.

A transaction is committed iff:

  1. All the txs before it are committed
  2. The last validation is successful and late enough (there's no pending validations that will fail it later).

The first property can be implemented with a commit_idx atomic counter, it’s increased when a transaction get committed.

The second property is tricker, we observe that a validation can only be scheduled in two ways:

  1. schedule validation of a specific transaction (by return TaskKindValidation in FinishExecution)
  2. validate a wave of validations for all transactions after i (by setting the validationIdx counter in DecreaseValidationIdx).

To make sure the current validation execution is triggered late enough, we need to track is the current validation is the last one in the triggered ones. We need to add some atomic counters to record the ordering information between events:

  1. validation_wave increased whenever a validation wave is triggered.
  2. [BlockSize]triggered_wave record the wave counter when tx i trigger wave validation.
  3. commit_wave, when tx i commit, record the maximum triggered_wave[i] in i and all txs before it.
  4. required_wave record the current wave number when trigger a specific tx validation.

When validation succeeds, it check commit_idx to be i-1, and wave number equal to or larger than both commit_wave, and required_wave.

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Type

    No type

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions