ソートによってファイルが誤ったレコードにサイレントに再割り当てされる場合

インプレースソートとインデックスから派生したファイル名は、ビルド、ロード、検証は正常に行われるものの、すべてのレコードが間違ったファイルを指している出力を生成します。

あるパイプラインは、アイテムをグループ単位で処理し、共有の変換ステップのためにそれらを1つのスライスにフラット化し、ループインデックスを使用して各出力ファイルを item-%04d.ext として書き込んでいました。その後、出力を所有者ごとに再グループ化するよう要求がありました。安易な変更を行ったところ、生成されたファイルは存在し、サイズも正しく、すべてのスキーマチェックに合格しましたが、すべてのレコードに誤ったデータが含まれていました。

何も例外は発生しませんでした。ビルドは成功し、テストも成功し、成果物は下流のツールで正しい構造で開くことができました。間違っていたのはペイロードだけであり、ペイロードはまさに自動チェックが検査しない傾向にあるものです。

これを可能にするセットアップ

3つのありふれた決定が組み合わさって罠となります。それぞれは単独では正当化できるものです。

第一に、共有の処理ステップはフラットなスライスを受け取ります。なぜなら、アイテムを1つのバッチでダウンロードして変換する方が、グループごとに行うよりも安価だからです。

第二に、そのステップはインプレースでソートします。タイムラインの位置、キー、その他何であれソートすることは、後続の処理が順序を前提としている場合には一般的です。ソートは正しく、それを説明するコメントも正確です。

第三に、出力ファイル名は書き込み時にループのインデックスから生成されます。

for i := range items {
    items[i].LocalPath = filepath.Join(dir, fmt.Sprintf("item-%04d.src", i))
}
sortItems(items)                                     // in-place, reorders everything
for i := range items {
    out := filepath.Join(dir, fmt.Sprintf("item-%04d.out", i))
    convert(items[i].LocalPath, out)
    os.Remove(items[i].LocalPath)                    // source deleted, field not updated
}

注意深くお読みください。入力はソート前のインデックスで命名されます。出力はソート後のインデックスで命名されます。LocalPath フィールドは出力に合わせて更新されないため、変換後は存在しないファイルを指すことになります。レコードと変換後のファイルを結びつける唯一の残されたリンクは、ソート済みスライス内でのその位置です。

これは、1つのループでマニフェストを書き込む限りは機能します：

for i, item := range items {
    manifest = append(manifest, Entry{Path: fmt.Sprintf("item-%04d.out", i), ...})
}

同じスライス、同じ順序、同じインデックス。偶然の一致で正しい。

問題を引き起こす変更

次に、出力を所有者ごとにグループ化します。ごく自然な実装では、各グループをたどり、そのファイルに番号を付けます:

idx := 0
for _, group := range groups {
    for _, item := range group.Items {
        group.Entries = append(group.Entries, Entry{
            Path: fmt.Sprintf("item-%04d.out", idx),   // fresh numbering per group
        })
        idx++
    }
}

そのマニフェスト内のすべてのパスはディスク上に存在します。すべてのパスは一意です。すべてのファイルには、正しいタイプとほぼ正しいサイズの、もっともらしいコンテンツが含まれています。そして、フラットスライスはソートされていましたが、グループウォークはソート順ではないため、それらのファイルはそれぞれ異なるレコードに属します。

これは名指しする価値のある障害モードです。**そのバグは、欠損ファイルや破損ファイルを生成するわけではありません。間違ったコンテンツを持つ有効なファイルを生成するのです。**存在チェックはパスします。サイズチェックはパスします。フォーマット検証はパスします。スキーマ検証はパスします。ダウンストリームのコンシューマーは問題なくそれを開きます。

オーディオパイプラインでは、それはクリップが正しいタイムライン位置に正しいデュレーションで配置されるものの、音声が間違っていることを意味します。ドキュメントパイプラインでは、ページ数は正しいものの、ページ本体が入れ替わっていることを意味します。画像パイプラインでは、ディメンションは正しいものの、被写体が間違っています。その症状は常に意味論的なものであり、決して構造的なものではないため、あらゆる構造チェックを通過してしまいます。

なぜ明らかな修正では不十分なのか

まず考えられるのは、ソート後もメンバーシップが維持されるように、owner フィールドを追加することです：

type Item struct {
    // ...
    GroupIdx int   // survives the in-place sort
}

それは必要であり、グルーピングは復元されます。しかし、ファイルのバインディングは修正されません。バインディングはグルーピングに依存したことがないからです。バインディングは位置に依存していました。GroupIdx を追加すると、グループを再構築してからその中で位置を再生成できますが、これがまさにスワップを引き起こすコードパスです。

私は最初のパスでこの間違いを犯しました。フィールドが追加され、グルーピングは機能しましたが、レビュー担当者から、マニフェストビルダーが依然としてカウンターからパスを派生させていると指摘されました。実際に有効な修正は、パスの派生を完全にやめることです。

// conversion updates the record to point at its own output
for i := start; i < end; i++ {
    os.Remove(items[i].LocalPath)
    items[i].LocalPath = outputs[i-start]     // the record carries its file
}

// manifest reads the field instead of computing an index
for _, item := range items {
    entries[item.GroupIdx] = append(entries[item.GroupIdx], Entry{
        Path: item.LocalPath,
    })
}

これで、レコードはそれ自身のアーティファクト参照を保持します。並べ替え、再グループ化、フィルタリング、および並列処理はすべて無害になります。なぜなら、レコードがすでに知っていることを再計算するものは何もないからです。

一般的なルールは次のとおりです。**レコードとそのアーティファクトが常に一緒でなければならない場合は、参照をレコードに保存します。**インデックスは位置であり、位置は、あらゆる並べ替え、フィルター、またはパーティションが最初に破壊するものです。2つの異なるループが両方とも「N番目のファイル」を計算した瞬間に、誰も強制していない不変条件が存在することになります。

これをテストするのは見た目よりも難しい

私は、まさにこのバグのためのリグレッションテストを作成しました。そのテストでは、交互に配置されたソートキーを持つ2つのグループをセットアップし、パイプラインのステージを実行し、すべてのエントリが自身のレコードのファイルを指していることをアサートしました。テストはパスしました。

修正を元に戻したときも、テストはパスしました。

本番の関数がネットワークコールとサブプロセスを必要とするより大きなルーチンに埋もれていたため、テストではテストファイル内でソートとマニフェストの構築を再実装していました。ロジックのコピーをテストすることは、そのコピーが正しいことを検証します。それは、出荷されるコードについては何も語りません。

修正は、テストが直接呼び出せるように、純粋な部分を抽出することでした:

func flattenWithGroupIdx(groups []Group) []Item      // tag membership
func sortItems(items []Item)                          // the actual sort, now callable
func groupIntoEntries(groups []Group, items []Item) []GroupEntries

3つの小規模な抽出を行いましたが、動作に変更はありません。また、テストで製品コードが実行されるようになりました。次に、バグが存在する場合にテストが実際に失敗することを確認しました。

$ # revert manifest to index-derived paths
$ go test -run TestKeepsBinding ./...
--- FAIL: TestKeepsBinding
    record a2 bound to wrong file: got item-0000.out, want /tmp/x/item-0000.out
    record a1 bound to wrong file: got item-0001.out, want /tmp/x/item-0001.out
    ... (5 records)
FAIL

その2分間のチェックこそが、要点のすべてです。一度も失敗したことのないリグレッションテストは、仮説であって保証ではありません。修正を元に戻してもグリーンになるのであれば、それは何か別のものをテストしており、その何か別のものとは、通常、あなたが保護しようとしたロジックのコピーです。

意味的な入れ替えを検出するアサーション

構造チェックは、その構造上この種のバグを見逃すため、アサーションはシェイプではなくアイデンティティを比較する必要があります。

並べ替えが行われる前に期待されるマッピングをキャプチャし、その後で比較します：

want := map[string]string{}
for _, item := range items {
    want[item.ID] = item.LocalPath      // snapshot before regrouping
}
// ... build manifest ...
for _, e := range entries {
    if e.Path != want[e.ID] {
        t.Errorf("%s bound to wrong file: got %s, want %s", e.ID, e.Path, want[e.ID])
    }
}

**一意性を明示的にアサートしてください。**2つのエントリが1つのアーティファクトを指している状態は、エントリごとのチェックでは検出できないスワップです:

seen := map[string]string{}
for _, e := range entries {
    if prev, dup := seen[e.Path]; dup {
        t.Errorf("path %s shared by %s and %s", e.Path, prev, e.ID)
    }
    seen[e.Path] = e.ID
}

**実際に並べ替えを行うソートキーを使用する。**項目がすでにソートされているフィクスチャでは、何も証明されません。グループをインターリーブさせて、ソートによってレコードがグループの境界を越えて移動するようにします。これがバグをトリガーする条件です。

**パスだけでなく、拡張子も確認する。**元のコードでは、変換されていない LocalPath が、削除されたソースファイルを指したままでした。サフィックスをアサートすることで、「変換後にフィールドが更新されない」という一連のミスを検出できます。

このパターンが他に隠れている場所

私がこの問題に遭遇したのはオーディオパイプラインでしたが、その形は汎用的なものです。これら3つが同時に現れる場所ならどこでも、このパターンを探してみてください:

グループごとの呼び出しよりもバッチAPIの方が安価な場合によく見られる、flatten-process-regroup (フラット化-処理-再グループ化) のシーケンス。
途中のどこかにあるインプレースソートまたはフィルター。自分で書いたものではないヘルパーの内部に隠されているものを含みます。
レコードに保存されるのではなく、ループカウンターから派生したアーティファクト名。

これが現れる具体的な場所としては、画像をバッチ処理してからアルバムごとに再グループ化するサムネイル生成、ページを一度にレンダリングしてから章ごとに組み立てるレポートビルダー、行をまとめて取得し、ウィンドウイングのためにタイムスタンプでソートし、テナントごとにパーティション分割するETLジョブ、--output-%d パターンを受け取るツールをシェルアウトするものなら何でもあります。

その兆候は、「インデックスはソート順と一致する」や「同じループ、同じインデックス」のようなコメントです。そのコメントは、強制力のない不変条件を文書化しているのです。書かれた時点では真ですが、次のリファクタリングの後には暗黙のうちに偽になり、あなたのテストスイートでは何も気づかれません。

よくある反論

「インプレースでソートしなければよい」 もっともな意見ですが、多くの場合、ソートを制御することはできません。今回の場合、そのソートは、順序に依存する別のパイプラインが使用する共有ヘルパー内に存在していました。コピーを返すように変更すると、変更範囲が広がり、それ自体のリスクが伴います。また、位置に由来する名前という根本的な問題は解決されません。

「スライスの代わりにIDをキーとするマップを使用する」 これは有効な方法で、位置の概念を完全に排除します。しかし、アロケーションと順序制御のコストがかかります。これは、次のステージがソートされた順序でストリーミングする場合に重要になります。レコードにパスを保存すれば、スライスを維持したまま同じ安全性を得られます。

「後で出力を検証する」 それも可能ですが、セマンティックな同一性を検証するには、通常、アーティファクトをデコードして内容を比較する必要があり、コストがかかり、ユニットテストでは不可能な場合が多いです。構造的に破壊不可能なバインディングを作成する方が、破壊を検出するよりも安価です。

「我々の型はイミュータブルなので、パスを保存できない」 その場合は、レコードとアーティファクトをペアにする並列構造を返し、独立して再インデックス付けする2つのスライスの代わりにそれを渡します。原則は変わりません。1つの値が両方の要素を保持するのです。

要点

「名前の入力」と「名前の出力」の間でのインプレースソートは、インデックスから派生したファイル名を、サイレントな正当性のバグへと変えてしまいます。
このバグは中身が入れ替わった有効なアーティファクトを生成するため、存在、サイズ、フォーマット、スキーマのチェックはすべてパスしてしまいます。
所有権フィールドを追加するとグルーピングは復元されますが、バインディングは復元されません。レコードにアーティファクト参照を保存してください。
テストが製品コードを呼び出すように純粋関数を抽出し、次に修正を一度元に戻してテストが失敗することを確認します。
シェイプではなく同一性と一意性をアサートし、ソート順によって実際にレコードが移動するフィクスチャを使用してください。

これらすべての中で最もコストが低いのは、修正を元に戻して確認することです。この四半期にリグレッションテストを1つ書くなら、一度は失敗するのを確認したテストにしてください。

FAQ

自分のパイプラインに今このバグがあるかどうかを知るにはどうすればよいですか？ ループインデックスでファイル名をフォーマットしているすべての箇所を見つけます。それぞれについて、その行とファイルを読み戻す行との間でスライスが並べ替えられる可能性があるかどうかを問いかけます。間にソート、フィルター、重複排除、または並列スキャッターがある場合、その状況にあります。次に、上記のマッピングアサーションを記述し、それがパスするかどうかを確認します。

静的アナライザーで検出できますか？ いいえ。個々の行はすべて正しいです。このバグは、型チェッカーが関連付ける理由のない2つのループ間の関係に存在します。これが、緩和策がリントルールではなく構造的なものである理由です。

これはoff-by-oneと同じですか？ いいえ、そしてその違いはデバッグにとって重要です。off-by-oneは通常、境界でクラッシュするか、明らかに間違った要素を1つ生成します。これは完全な順列を生成します。すべての要素が間違っており、欠落しているものはなく、数は正しいです。「すべてが微妙に間違っているが、何も壊れていない」という報告を追っている場合、算術よりも順列の方が良い仮説です。

これはファイルパイプライン以外にも適用されますか？ はい。位置によって2つのコレクション間の対応を維持する場合、並べ替えはそれを壊します。並列配列、インデックスキー付きキャッシュ、およびバッチAPIクライアントにおける「N番目の応答はN番目の要求に一致する」という仮定はすべて同じ形をしています。修正方法も同じです。2つの半分を1つの値でペアにします。