The migration was idempotent and the order was not

# Self-authored for the EML case corpus (no external origin). A schema
# migration is twelve steps and every step is idempotent. It was replayed onto
# three shards and two of them ended up different. What idempotence covers is
# computed below.
#
# Making each step idempotent is correct and it is the property that makes a
# migration operable. A step that can be rerun turns a partial failure into a
# retry instead of a restore, lets an operator resume from the middle without
# working out where the middle was, and makes the whole thing safe under an
# at-least-once runner. Every step here was tested for it, repeatedly.
#
# Idempotence is a property of one step against itself. A migration is a
# sequence, and a sequence has a second property that no individual step can
# carry: whether the steps commute.
#
# Both facts are true at once. Each step run twice leaves the same state, and
# two steps run in the other order do not.

12 => steps
50 => reruns_per_step
4 => order_sensitive_pairs
3 => shards

steps * reruns_per_step => idempotence_checks

"steps in the migration     : " + str(steps) ^0
"reruns tested per step     : " + str(reruns_per_step) ^0
"idempotence checks run     : " + str(idempotence_checks) ^0
"idempotence checks passed  : " + str(idempotence_checks) ^0
"idempotence failures       : 0" ^0
"" ^0

# ---- the property that was tested, and the one that was not ----

int(steps * (steps - 1) / 2) => ordered_pairs

"what was measured" ^0
"  step applied twice equals step applied once : " + str(steps) + " of " + str(steps) ^0
"  pairs of steps checked for commuting        : 0 of " + str(ordered_pairs) ^0
"" ^0
"  pairs that do not commute : " + str(order_sensitive_pairs) ^0
"  and none of the " + str(idempotence_checks) + " checks can observe one, because" ^0
"  every check runs a single step against itself" ^0
"" ^0

# ---- one non-commuting pair, both steps idempotent ----

"step 7  add column state, default null            rerun safe : yes" ^0
"step 9  set state to active where state is null   rerun safe : yes" ^0
"" ^0
"order    result" ^0
"  7 then 9   every existing row gets state active" ^0
"  9 then 7   the update finds no such column yet, is skipped by" ^0
"             the runner as already-applied, and every existing" ^0
"             row keeps state null" ^0
"" ^0
"  both orders complete, both report success, neither retries" ^0
"" ^0

# ---- why the shards disagreed ----
#
# The runner replays the migration log. It sorts the log by step id so a resume
# is deterministic, which is a reasonable thing to want. Two shards were
# resumed; one ran straight through.

2 => shards_resumed
shards - shards_resumed => shards_straight_through

"shard   path              order applied      final state" ^0
"  1     straight through  recorded order     state active" ^0
"  2     resumed           sorted by step id  state null" ^0
"  3     resumed           sorted by step id  state null" ^0
"" ^0
"  shards agreeing with shard 1 : " + str(shards_straight_through) ^0
"  shards differing             : " + str(shards_resumed) ^0
"  migration steps that failed  : 0" ^0
"  migration steps that retried : 0" ^0
"" ^0

# ---- the rows ----

4200000 => rows_per_shard
shards_resumed * rows_per_shard => rows_with_null_state
shards * rows_per_shard => rows_total

"rows per shard          : " + str(rows_per_shard) ^0
"rows in total           : " + str(rows_total) ^0
"rows left with state null : " + str(rows_with_null_state) ^0
"share of the table      : " + str(int(rows_with_null_state * 100 / rows_total)) + " percent" ^0
"" ^0
"  the migration is marked complete on all " + str(shards) + " shards" ^0
"" ^0

# ---- what a rerun does now ----
#
# The operator's instinct is right: the steps are idempotent, so run it again.
# Running it again on shard 2 changes nothing, because every step is already
# applied and each one is a no-op against its own result. Idempotence is
# working, and it is what makes the wrong state stable.

"rerunning the whole migration on shard 2" ^0
"  steps re-executed : " + str(steps) ^0
"  steps that changed anything : 0" ^0
"  rows repaired : 0" ^0
"" ^0
"  the property that makes a retry safe is the same property" ^0
"  that makes this retry useless" ^0
"" ^0

# ---- the control ----
#
# Idempotence, against what it was put there for. It was put there so a failed
# run could be resumed rather than restored, and it delivered that on every
# step, every time, including the two resumes that produced this.

"control - is idempotence holding" ^0
"  steps proven rerun-safe : " + str(steps) + " of " + str(steps) ^0
"  checks run              : " + str(idempotence_checks) ^0
"  check failures          : 0" ^0
"  restores required       : 0" ^0
"  defects in any step     : 0" ^0
"" ^0
"  without it the two resumes would have needed a restore each" ^0
"" ^0

# ---- the null control ----
#
# The same twelve steps, same idempotence, same two resumes, on a migration
# whose steps all commute. Sorting the log then reorders nothing that matters
# and all three shards land identically.

0 => nc_order_sensitive_pairs
0 => nc_shards_differing

"null control - the same runner where every pair commutes" ^0
"  order-sensitive pairs : " + str(nc_order_sensitive_pairs) ^0
"  shards resumed        : " + str(shards_resumed) ^0
"  shards differing      : " + str(nc_shards_differing) ^0
"  same sort, same resume, same idempotence" ^0
"  the runner did not become correct; the steps stopped caring" ^0
"" ^0

# ---- the rule ----

"what idempotence certifies" ^0
"  this step, applied again, changes nothing : yes, measured" ^0
"  this step, applied later, does the same   : not measured" ^0
"  the set of steps commutes                 : not measured, not implied" ^0
"  and a per-step property has no place to record a pair" ^0
"" ^0
"the missing test is not a longer rerun; it is two steps in the" ^0
"other order, and the number of those to check is " + str(ordered_pairs) ^0
"" ^0

"Every one of the " + str(steps) + " steps is idempotent and " + str(idempotence_checks) + " rerun checks confirm it" ^0
"with 0 failures, which is why two shards could be resumed without a restore." ^0
"The runner sorts the log by step id, " + str(order_sensitive_pairs) + " of the " + str(ordered_pairs) + " step pairs do not commute," ^0
"and " + str(rows_with_null_state) + " of " + str(rows_total) + " rows - " + str(int(rows_with_null_state * 100 / rows_total)) + " percent - now hold a value the" ^0
"migration was written to remove, on shards it reports as complete." ^0

steps = 12
reruns_per_step = 50
order_sensitive_pairs = 4
shards = 3
idempotence_checks = steps * reruns_per_step
print("steps in the migration     : " + str(steps))
print("reruns tested per step     : " + str(reruns_per_step))
print("idempotence checks run     : " + str(idempotence_checks))
print("idempotence checks passed  : " + str(idempotence_checks))
print("idempotence failures       : 0")
print("")
ordered_pairs = int(steps * (steps - 1) / 2)
print("what was measured")
print("  step applied twice equals step applied once : " + str(steps) + " of " + str(steps))
print("  pairs of steps checked for commuting        : 0 of " + str(ordered_pairs))
print("")
print("  pairs that do not commute : " + str(order_sensitive_pairs))
print("  and none of the " + str(idempotence_checks) + " checks can observe one, because")
print("  every check runs a single step against itself")
print("")
print("step 7  add column state, default null            rerun safe : yes")
print("step 9  set state to active where state is null   rerun safe : yes")
print("")
print("order    result")
print("  7 then 9   every existing row gets state active")
print("  9 then 7   the update finds no such column yet, is skipped by")
print("             the runner as already-applied, and every existing")
print("             row keeps state null")
print("")
print("  both orders complete, both report success, neither retries")
print("")
shards_resumed = 2
shards_straight_through = shards - shards_resumed
print("shard   path              order applied      final state")
print("  1     straight through  recorded order     state active")
print("  2     resumed           sorted by step id  state null")
print("  3     resumed           sorted by step id  state null")
print("")
print("  shards agreeing with shard 1 : " + str(shards_straight_through))
print("  shards differing             : " + str(shards_resumed))
print("  migration steps that failed  : 0")
print("  migration steps that retried : 0")
print("")
rows_per_shard = 4200000
rows_with_null_state = shards_resumed * rows_per_shard
rows_total = shards * rows_per_shard
print("rows per shard          : " + str(rows_per_shard))
print("rows in total           : " + str(rows_total))
print("rows left with state null : " + str(rows_with_null_state))
print("share of the table      : " + str(int(rows_with_null_state * 100 / rows_total)) + " percent")
print("")
print("  the migration is marked complete on all " + str(shards) + " shards")
print("")
print("rerunning the whole migration on shard 2")
print("  steps re-executed : " + str(steps))
print("  steps that changed anything : 0")
print("  rows repaired : 0")
print("")
print("  the property that makes a retry safe is the same property")
print("  that makes this retry useless")
print("")
print("control - is idempotence holding")
print("  steps proven rerun-safe : " + str(steps) + " of " + str(steps))
print("  checks run              : " + str(idempotence_checks))
print("  check failures          : 0")
print("  restores required       : 0")
print("  defects in any step     : 0")
print("")
print("  without it the two resumes would have needed a restore each")
print("")
nc_order_sensitive_pairs = 0
nc_shards_differing = 0
print("null control - the same runner where every pair commutes")
print("  order-sensitive pairs : " + str(nc_order_sensitive_pairs))
print("  shards resumed        : " + str(shards_resumed))
print("  shards differing      : " + str(nc_shards_differing))
print("  same sort, same resume, same idempotence")
print("  the runner did not become correct; the steps stopped caring")
print("")
print("what idempotence certifies")
print("  this step, applied again, changes nothing : yes, measured")
print("  this step, applied later, does the same   : not measured")
print("  the set of steps commutes                 : not measured, not implied")
print("  and a per-step property has no place to record a pair")
print("")
print("the missing test is not a longer rerun; it is two steps in the")
print("other order, and the number of those to check is " + str(ordered_pairs))
print("")
print("Every one of the " + str(steps) + " steps is idempotent and " + str(idempotence_checks) + " rerun checks confirm it")
print("with 0 failures, which is why two shards could be resumed without a restore.")
print("The runner sorts the log by step id, " + str(order_sensitive_pairs) + " of the " + str(ordered_pairs) + " step pairs do not commute,")
print("and " + str(rows_with_null_state) + " of " + str(rows_total) + " rows - " + str(int(rows_with_null_state * 100 / rows_total)) + " percent - now hold a value the")
print("migration was written to remove, on shards it reports as complete.")

steps in the migration     : 12
reruns tested per step     : 50
idempotence checks run     : 600
idempotence checks passed  : 600
idempotence failures       : 0

what was measured
  step applied twice equals step applied once : 12 of 12
  pairs of steps checked for commuting        : 0 of 66

  pairs that do not commute : 4
  and none of the 600 checks can observe one, because
  every check runs a single step against itself

step 7  add column state, default null            rerun safe : yes
step 9  set state to active where state is null   rerun safe : yes

order    result
  7 then 9   every existing row gets state active
  9 then 7   the update finds no such column yet, is skipped by
             the runner as already-applied, and every existing
             row keeps state null

  both orders complete, both report success, neither retries

shard   path              order applied      final state
  1     straight through  recorded order     state active
  2     resumed           sorted by step id  state null
  3     resumed           sorted by step id  state null

  shards agreeing with shard 1 : 1
  shards differing             : 2
  migration steps that failed  : 0
  migration steps that retried : 0

rows per shard          : 4200000
rows in total           : 12600000
rows left with state null : 8400000
share of the table      : 66 percent

  the migration is marked complete on all 3 shards

rerunning the whole migration on shard 2
  steps re-executed : 12
  steps that changed anything : 0
  rows repaired : 0

  the property that makes a retry safe is the same property
  that makes this retry useless

control - is idempotence holding
  steps proven rerun-safe : 12 of 12
  checks run              : 600
  check failures          : 0
  restores required       : 0
  defects in any step     : 0

  without it the two resumes would have needed a restore each

null control - the same runner where every pair commutes
  order-sensitive pairs : 0
  shards resumed        : 2
  shards differing      : 0
  same sort, same resume, same idempotence
  the runner did not become correct; the steps stopped caring

what idempotence certifies
  this step, applied again, changes nothing : yes, measured
  this step, applied later, does the same   : not measured
  the set of steps commutes                 : not measured, not implied
  and a per-step property has no place to record a pair

the missing test is not a longer rerun; it is two steps in the
other order, and the number of those to check is 66

Every one of the 12 steps is idempotent and 600 rerun checks confirm it
with 0 failures, which is why two shards could be resumed without a restore.
The runner sorts the log by step id, 4 of the 66 step pairs do not commute,
and 8400000 of 12600000 rows - 66 percent - now hold a value the
migration was written to remove, on shards it reports as complete.

Trace event types