Concerning Git’s Packing Heuristics

こいつぁ、まったく馬鹿げた質問だけどな:

      Gitの
   パッキングヒューリスティックの
詳細はどこいきゃ確認できるんだい？

    <njs`> ええっと、本当にアホな質問するけど、
\tGitのパッキングヒューリスティックの詳細はどこで確認すりゃいいんだい？
        ググっても分からんし、
        ソースを読んでも役に立たんかったし、
        そしてメーリングリスト全体を探し歩くなんてやりたくもない。

<pasky> ええ、パッキング関連のデルタとかは
    私にとってさえちょっぴり神秘的です ;)

<linus> njs、ドキュメントは存在しないと思うわ。
     それは私以外の誰も実際に関与した事が無いと思う。
     Gitの他のほとんど（特にJunio）は活発で忙しいですが、
     私がそれを行った後、誰も触れませんでした。

<njs`> 次のステップは「ソースをもう一度読む」ことだと思うけどな。
    しかし、私は最初に、ある程度の強迫観念を惹起しなければなるまいて :-)

<linus> パッキングヒューリスティックは実際には本当に本当に単純なんだぜぃ。

<linus> でもオカシイ。

<linus> 思い出しな。Gitは実際にはファイルを追跡しねぇのよ。だからGitがすることは、
    - 全部のオブジェクトのリストを生成するじゃろ
    - そのリストを魔法のヒューリスティックに従ってソートするんじゃ
    - スライディングウィンドウを使用してリストを散歩し、
      ウィンドウ内の別のオブジェクトに対してオブジェクトを比較できるかどうかを確認するんじゃ
    - そんでもって最近の順序でリストを書き出す

<njs`> 私が見逃しているのは「魔法」という言葉の
    正確な定義だと思います

<pasky> そうだな

<njs`> ああ、うーん、このスライディングウィンドウの意味も分からんわ

<pasky> iirc、コードを何気なく読んでいると、
    オブジェクトのsha1にすぎないように見えたけどね…

…単純に、非常に優れたヒューリスティック、には見えないけどなぁ ;)

<njs`> …そして最新の順序。さて、私は自分がどれだけ気づいていないのかさえ
   気づいていなかったのは明らかだと思います :-)

<linus> 「魔法」は理論的には完全に恣意的です。
    どの順番でも作業パックが提供されますが、
    SHA-1順ではありません。

スライディングデルタウィンドウの順序について説明する前に、
最新の順序について説明しましょう。
それはある意味でより重要です。

<njs`> しかり。物をパックする作業方法だけが必要な場合は、
    catを使用するだけで、
    問題を回避できます…

<linus> 最新の順序付け(recency ordering)
    (基本的には、オブジェクトを、ヘッドから「到達可能」な順序で、「物理的に」パックに入れる)
    が重要です。

<njs`> そりゃ分かるよ

<linus> それがパックに良い局所性を与えるものなので、それは重要です。
    パックの先頭でオブジェクトをヘッドの近く
    (古いものでも新しいものでも、ヘッドから「到達可能」です）に保ちます。
    そうすることで、パックには実際に絶対に
    「素晴らしい」IOパターンがあります。

<linus> ただし、最新の順序付けは、
    実際にデルタを生成する方法を決定するのにまったく役に立たないため、
    デルタの順序付けは別のものです。

解説しよう！デルタ順位付け(delta ordering)とは！:
- オブジェクトリストを生成するときに、
  「最初に」到達した名前で定義される、
  オブジェクトの「ベース名」で最初に並べ替えます
- 同じベース名内で、オブジェクトのサイズで並べ替えます
- ただし、常に異なるタイプを個別に並べ替えます(コミットが最初です)。

正確には違いますが、ほぼこんな感じです。

<njs`> 「最初に到達した」ことはそれほど重要ではありません。
    同じオブジェクトにさまざまな方法で到達できる可能性があるため、
    関係を解消するための何らかの方法が必要だってだけよ？

<linus> 重要なのは、
    それはすべて実際にはランダムなヒューリスティックであり、
    順序付けは正確さにとってまったく重要ではないということですが、
    ヒューリスティックが互いにうまく差分化する可能性のあるものに
    「凝集」(clumping)を与える場合、それは大いに役立ちます。

<gitster> 上記のlinusからの引用は、
    少し書き直す必要があります:
    - 最初にタイプでソートします。
      異なるオブジェクトが互いに差分化(delta)することはありません。<
    - 次に、ファイル名/ディレクトリ名で並べ替えます。
      ベース名のハッシュは先頭からBITS_PER_INT〜DIR_BITSビットを占め、
      末尾のDIR_BITSは先頭のパス要素のハッシュ用です。
    - 次に、「薄い」パッキングを実行している場合、
      パックしないオブジェクトは、
      他のオブジェクトよりも早くソートされます。
    - そして最後に、サイズで大きいものから小さいものへと並べ替えます。

<gitster> これがソート順です。これが意味することは:
    - 異なるオブジェクトタイプを差分化(delta)することはありません。
    - 同じフルパスのオブジェクトを差分化(delta)することを好みますが、
      異なるディレクトリからの同じ名前のファイルを許可します。
    - 送信しないオブジェクトがある場合は、
      それに対して差分化(delta)することを常に好みます。
    - 大きなオブジェクトに対して差分化(delta)することを好むので、
      多くの削除があります。

最後から2番目のルールは「薄い」パッキング用です。他の側にそのようなオブジェクトがあることがわかっている場合に使用されます。

<jdl> 薄いパックって何？

<gitster> pack-objectsの上流として、 `--objects-edge` を伴って rev-listを実行します。
    パック転送プロトコルはそれをネゴシエートします。

<gitster> 2つの方向があります。プッシュとフェッチです。

<gitster> プッシュのために、git-send-packは相手側でgit-receive-packを呼び出します。
    receive-packには、「I have up to these commits」(これらのコミットまであります)と書かれています。
    send-packはそれらを調べ、相手側から欠落しているものを計算します。
    したがって、「薄い」がデフォルトになる可能性があります。

他の向きでは、fetchとgit-fetch-packとgit-clone-packが、
相手側でgit-upload-packを呼び出します
(sshを介して、またはデーモンと通信します)。

2つのケースがあります: `-k` を伴ったfetch-pack と clone-pack がひとつ、 `-k` なしの fetch-pack でもうひとつです。
`-k` を伴ったfetch-pack と clone-pack は、
ダウンロードされたパックファイルを展開せずに保持するため、
薄いパック転送(thin pack transfer)は使用しません。
それ以外の場合、生成されたパックには、
同じパック内にベースオブジェクトのないデルタ(差分)が含まれます。

ただし、 `-k` を伴わないfetch-packは、受信したパックを個々のオブジェクトに分解するため、
upload-packがサポートしている場合は、
upload-packに薄いパック(thin pack)を提供するように自動的に問合せます。

<njs`> そして「basename」は、「basename(3)に従って、
    ファイルオブジェクトとdirオブジェクトのパスの終わりの末尾であり、
    すべてのcommitオブジェクトとtagオブジェクトが同じbasenameを持つように宣言する」
    などの意味です。

<linus> さまざまなデルタ化アルゴリズムを試し、
    「デルタウィンドウ」を大きくしましたが、スライディングウィンドウが大きすぎると、
    パックの生成に非常にコストがかかります。
    すべてのオブジェクトを他の大量のオブジェクトと比較する必要があります。

他にも多くの些細なヒューリスティックがありますが、
デルタに価値がないことを事前に知ることができれば
(サイズの違いにより、以前のデルタ結果を考慮に入れて、
「わかりました。それを試してみても意味がありません。
悪化する」と判断できます)、
基本的に「このペアをデルタにするのは割に合わない」に要約されます。

最終結果: パッキングは実際には非常にサイズ効率が良いです。
CPUパワーをいくらか浪費する一方で、
実際には月に1回しか実行しないことになっているため(夜間に実行できます)、
誰も気にしません。

<njs`> それじゃあ、繰り返しになるけど、私がついていけてるか確認するために、
    パックするオブジェクトのリストを取得することから始め、
    このヒューリスティックでソートします
    (基本的にタプル(タイプ, ベース名, サイズ)で辞書式順序)。

次に、このリストを調べて、
(調整可能なパラメーターである)最後のn個のオブジェクトに対する各オブジェクトのデルタを計算し、
これらのデルタの最小のものを選択します。

<linus> その通りだ。

<njs`> 次に、各オブジェクトを表すデルタまたはフルテキスト(fulltext)を選択したら、
    最新性で再並替え(re-sort by recency)して、
    その順序で書き出します。

<linus> <linus>うん。それで、その他の細々を言うと:

<linus> - デルタ深度を別のマジック値に制限します
    (現在、ウィンドウとデルタ深度のマジック値はどちらも「10」です)

<njs`> うーん、私の直感では、必要なものが近くにあるため、
    マヂで悪いIOパターンになってしまう気がします。
    実際にそれらを再構築するには、
    ランダムな方法でジャンプする必要があるかもしれません。

<linus> - デルタを書き出すにあたって、
    デルタであるオブジェクトをまだ書き出していない場合、最初にベースオブジェクトを書き出します。
    しかし、それらを再構築すると、実際には優れたIOパターンが得られます。
    理由は以下のとおりです:
    - 大きなオブジェクトは「より最近」になる傾向があります(リーナスの法則:ファイル達は成長します)
    - 大きなオブジェクトから小さなオブジェクトへのデルタの生成を
      積極的に試みます
    - これは、ツリーの最上位にデルタがほとんどないことを意味します
      (つまり、実際のデルタは「後方デルタ」(backwards deltas)です）

<njs`> つまり、実際には、
    デルタの順序と最近の順序は非常によく一致しているということです。

<linus> ええそうです。これには別の良い面があります
    (そして、それは以下のように設計されました):
    - 大きなオブジェクトに対してデルタを生成する理由は、
      実際には大きなスペース節約にもなります。

<njs`> うーん、でもあなたの最後のコメント（「デルタであるオブジェクトをまだ書き出していない場合は、
    最初にベースオブジェクトを書き出す」）は、
    これらの事実をほとんど無関係にするようです。
    実際には、あまり歩き回る必要はありません。
    実際、歩き回らなければならない場合は、
    そうしないでくださいとチカラずくで言います :-)

<linus> 答えは、イエスでもありノーでもある。ルールに注意してください。
    最初にベースオブジェクトを書き出すのは、それに対するデルタがより最近のものである場合のみです。
    つまり、実際には、
    デルタオブジェクトに近くないベースオブジェクトを参照するデルタを持つことができますが、
    これは、古いオブジェクトを生成するためにデルタが必要な場合にのみ発生します。

<linus> お分かり？

<linus> これにより、パックの前側が密になります。
    パックの前側には、「最近の」オブジェクトに関連しないデータが含まれることはありません。
    サイズの最適化は、xdeltaの使用に由来します
    (ただし、他の多くのデルタアルゴリズムにも当てはまります)。
    データの削除は、データの追加よりも(サイズ的に)安価です。

データを削除するときは、「バイトn--mをコピー」と言うだけで済みます。
対照的に、データを追加するデルタでは、
「これらのバイトを追加します： '実際のデータはここにあります'」と言わなければなりません。

<linus> njs、何か見逃しましたか？

<njs`> クソルーターめ、グレムリンめ

<njs`> イエスもありノーでもある。ルールに注意してください。
最初にベースオブジェクトを書き出すのは、それに対するデルタがより最近のものである場合のみです。

私はこれらすべての順番で迷子になっています、再読させてください:-)
それで、書き込みの順番は新しいものから順にということですよね？
(おそらく逆の方法かもしれませんが、私たちが言ったかどうかはわかりません）
自宅に戻ったら私の接続はログに記録されているので、
そこであなたが言ったことを読むことができるでしょう :-)

<linus> そうだよ。常に最新のものを最初に書きます

<njs`> そして、ええっと、歴史の深いものはIOの特性が悪くなる、
という部分は理解できましたが、ある種、気にならないものです。

<linus> 「最新の」オブジェクトがデルタ化するために
    古いオブジェクトを必要とする場合(しばしば縮小が起こる)、
    我々はデルタを伴って古いオブジェクトを書き出します。

<njs`> (それがもっともっと起こったら…)

<linus> とにかく、パックファイルはさらに簡単に高密度になる可能性がありますが、
    ストリーミング(Gitプロトコル)とディスク上の操作での両方に使用されるため、
    ちょいとばかり冗長でパフォーマンスが良くありません(it has a few pessimizations)。

<linus> 特に、pack-fileは圧縮されますが、
    一度に1つのオブジェクトだけが圧縮されるため、実際の圧縮率は理論上の圧縮率よりも低くなります。
    しかし、それは、「オブジェクト名→パックファイル内の場所」の変換を行うための、
    単純なインデックスを使用した、
    すべてにおいて優れたランダムアクセスであることを意味します。

<njs`> 大→小 をデルタ化することの本当の勝利は、
    gzipが実行されるより均一な統計であると思いませんか？

(あなたはバイトをどこかに配置する必要がありますが、
より大きなブロブに配置すると、圧縮が優先されます)

実際、圧縮戦略とは何でしょうか -- 各デルタは個別にgzipで圧縮され、
ファイル全体がgzipで圧縮され、
その間のどこかでは圧縮はまったく行われませんが…？

正しい。

<pasky> 残りは朝に読みます、私は本当に眠らなければなりません、
    さもなければ今日の試験で私には何の希望もありません…
    皆さんお休みなさい。

<linus> pasky: おやすみ

<njs`> pasky: グッドラック

<linus> 正しい: 圧縮動作のために、大きい→小さい ことが問題になります。
    圧縮されていない場合は、
    おそらく違いはありません。

<njs`> うんうん。

<linus> とにかく：パックファイルが完璧だと主張するつもりはありませんが、
    それは密度と使いやすさのバランスが
    うまく取れている傾向があります。

<linus> さらに重要なことは、Gitが概念的にデルタをまったく処理せず、
    「オブジェクト全体」のストアになることを可能にすることです。

これにはいくつかの問題があります
(先日、Gitメーリングリストで
巨大ファイルの良くない振る舞いについて説明しました)が、
基本的なGitの概念が本当に単純で素直であることを意味します。

それはすべて非常に安定しています。

これは非常に単純な基本的な考え方の結果であると私は思います。
そのため、
何が起こっているのかについて混乱することはありません。

バグは発生しますが、それらは「単純な」バグです。
また、オブジェクトストアの詳細を実際に間違えるバグは、
ほとんどの場合非常に明白であるため、見間違えようがありません。

<njs`> ああ。

<linus> とにかく。 私は寝る。まだ午前6時ではありませんが、
      私には3人の子供がいて、子供らを送り出すために早朝に起きなければなりません。
      私には素晴らしい睡眠が必要です。

<njs`> :-)

<njs`> <njs`> infodumpに感謝します、
    私は本当にGitパックの詳細を見つけることができませんでした :-)