GitLabリポジトリのバックアップ、48時間が41分になった方法！
引用元：https://news.ycombinator.com/item?id=44201975
GitLabがGitに貢献したパフォーマンス改善は、v2.50.0でリリースされる予定だよ！
詳しくはこちらを見てね→https://github.com/git/git/commit/bb74c0abbc31da35be52999569…
GitLabがGit本家で頑張ってるのいいね！もしかしてGitの主要な貢献者ってGitLab社員が多い感じ？
どうしてそう思ったの？過去2年のトップ4貢献者を見るとね、Googleに1人(gitster)、GitHubに2人、GitLabに1人(pks-t)だよ。[1]を見てみて！
[1]: https://github.com/git/git/graphs/contributors?from=6%2F3%2F…
あー、月間の活動を見てたんだ。確かに、もっと長い期間で見ると全然違うね。教えてくれてありがとう。
あれ、不思議だな。私も月間を見たけどGitLabの人は見当たらなかったんだよね。ひょっとして、別のGitリポジトリでも見てたんじゃない？
記事を書いた者だけどさ、最近GitLabにはGit専門のチームができたんだ[1]。だから、Gitへの貢献はこれからもっともっと増えると思うよ！:)
[1]: https://handbook.gitlab.com/handbook/engineering/infrastruct…
経験上、コードにあるO(n^2)の処理を無くすのは常に正しい判断だったよ。別に難しいアルゴリズムを書くわけじゃないけど、nが小さくても問題になるからいつも驚かされる。
Bruce Dawsonがね、こう言ってるんだ。「これをDawsonの第一法則って呼びたいね。O(n^2)は、ダメなスケールするアルゴリズムの『ちょうどいい落としどころ』なんだ。本番投入できるくらい速いけど、データが増えるとすぐにダメになる。」
元の投稿はこちら→https://bsky.app/profile/randomascii.bsky.social/post/3lk4c6…
面接でO(n^2)より遅い、もうヤバすぎる二つの解法を同じレベルで語るっていう「間違い」を犯したんだよね。私が言いたかったのはDawsonの法則みたいな意味で、どっちも議論する価値もないくらい馬鹿げてるってこと！
まあ、そんな馬鹿げた方法でも、それよりマシな解決策が他に一つも存在しないなら、アリなのかもしれないけどね。
絶対ダメだね。何かをするコストが二次（O(n^2)）を超えるなら、やるべきじゃないんだ。顧客とのやり取りごとにコストが増える一方で、その増え方に対応できないからね。金を穴に埋めて火をつけてるようなもんだ。うまくできないならやめるか、直す見込みがないなら外部に任せるべきだよ。
（誰かの）第二法則は、O(n * log n)は実際的にはO(n)と同じくらいだ、って話だよ。
はっきり言うと、それは彼の第二法則じゃないよ、少なくとも2ヶ月前時点ではね。このリンク（https://bsky.app/profile/randomascii.bsky.social/post/3lk4c6…）によると違うらしいから。
まあフェアだけど、俺の頭の中ではn log nが歴史的な「安心して夜眠れる」レベルなんだ。大学でデータ構造を習った時、先生がしょっちゅう言ってたからね。「メモリはCPUよりずっと安い」って賢い言葉もね。毎回20〜100MBのJsonをパースするより、メモリに構造体としてキャッシュする方がよっぽど効率いいのにって思うこと、結構あるんだ。
最近のPCは小さいメモリブロックを繰り返しスキャンするのが得意だから、小さいNならマップ使うよりn^2が速いこともあるんだ。Blinkでn^2を直すのに時間かけたけど、面白い発見もあったよ。例えば、:nth-childマッチングは、兄弟が多いとn^2スキャンで遅いけど、少ない場合はキャッシュのオーバーヘッドの方がn^2より悪かったりする。線形探索が定数時間のマップより速いとか、n^2が洗練されたアルゴリズムより良いとか、意外な場所でそうなるんだよね。メモリの遅延とか命令のタイミングが、現実世界のアルゴリズムの落とし穴だったりするわけ。
https://source.chromium.org/chromium/chromium/src/+/main:thi…
俺の経験則で問題の80〜90％はね、複雑なアルゴリズムが必要なら、それはデータモデルが間違ってるってことだと思うんだ。もちろん、コンパイラとかDBの内部とか経路探索とか、そういうのは複雑なのいるけど、まあ少数派だよね。
滅多にないけど、たまにバグがないのが明らかなn log nのアルゴリズムを、見た感じバグがないO(n)のアルゴリズムより選ぶことがあるよ。壊れにくさの方が数パーセント以上の価値があるんだ。特にそれが他の（時間）複雑さを見つけやすくしてくれるならね。
俺から言わせりゃ数パーセントどころじゃないと思うけどね。:)
でも俺はこの分野にそこまで詳しくないから、O(n)を実装・検証するのが何年も泣きと苦労の連続だったのかどうかは分からないんだけど。
表はNが5から100までのnとn log nを比較してるね。
Nが10くらい未満で、ハードウェアに制約されるもの（例えばOBDIIコネクタにあるCANインターフェースの数とか）を数える場合は、O(n^2)でもいい例外だと思うね。なぜなら、Nを増やすには物理的にハードウェアを交換しなきゃいけないからさ。でも、そうじゃない場合は、絶対O(n^2)の操作は避けるべきだよ。たとえそうでも、Nが大きくなりすぎたら明示的に失敗させる、ってことも慎重に検討すべきだね。
＞Nが大きすぎたら明示的に失敗させる
それが問題なんだよ。こういう二次時間のアルゴリズムの多くは、制限を設定してないんだよね。階乗(n!)だって小さい’n’ならいいけど、本番のユースケースじゃ’n’は小さくないからね。
現代のNeural Network AIってさ、GEMMっていうO(n^2)の計算が基本なんだ。O(n^3)より速いやつもあるらしいけど、キャッシュのせいで実際には速くならないみたい。あと、nって大体”customers”とかと関係ないから、nが増えなきゃ計算量とかあんま気にしなくていいんだよ。
これ、そんな難しいアルゴリズムじゃないよ。Pythonだと、重複なくすならいつもhash map（dictionary）かhash set使うのが一番簡単だしコードも少なくて済む。でもCだと違くて、hash mapよりarraysとnested loopsの方が全然書きやすいんだよね。
＞ where linear search beats constant time maps
ってとこ、例を挙げてくれない？記事は良かったけど、そこだけちょっと信じられないんだ。実際のwall clock timesとかreal world impactとかも見たかったな。
Good call. O(N^2)ってマジ最悪のtime complexityだよ。testing環境だと一瞬なのに、prod環境だとexplodeするくらいslowになるんだ。こういうのseveral times前に見たことあるし、exactly what happened hereだと思ったよ。
I feel this is too hardline and e.g. eliminiates the useful things people do with SAT solvers.
Skiena has a great table in his algorithms book mapping time complexity to hypothetical times for different input sizes.
For n of 10^9, where lgn takes 0.03 us and n takes 1 s, nlgn takes 29.9 s and n^2 takes 31.7 years.
The GEMM is O(n^3) actually. Transformersはquadratic in the size of their context window.
We just had this exact problem. Tests ran great, production slowed to a crawl.
I read that as a typo given the next sentence.
I’m on the fence about cubic time. I was mostly thinking of exponential and factorial problems. I think some very clever people can make cubic work despite my warnings. But most of us shouldn’t. General advice is to be ignored by masters when appropriate. That’s also the story arc of about half of kung fu movies.
Did chess solvers really progress much before there was a cubic approximation?
＞ That is not the case in C though, as it is much easier to use arrays and nested loops instead of hash maps.
I am confused. There are plenty of open source, fast hash map impls in C.
もっとコメントを表示（1）
アルゴリズムの速さは定数とかnの値で変わるんだよ。もしO(n log n)の定数がO(n)の5倍なら、nが100以下ならO(n)の方が速いんだ。もしnが常に100以下って分かってるなら、両方のアルゴリズムを書いたり、いつ切り替えるか探す時間を使うより、O(n)だけ実装して、nが250とかになったら警告出す方がいいかもね（1000超えたらエラーとか）。
チェスエンジンは二次関数よりひどいスケーリングに直面したけど、乗り越えてきたんだよね。ソフトウェアってマジで色んな分野があって、制約も全然違うんだ。
でも、定数（C）が十分に大きければ、どの解決策が利益を出すか変わってくることもあるんだ。
N^3の処理がボトルネックになってて、1万要素なのにめっちゃ遅いんだ。どうしたらいいか分からないや。
クールな発見だけど、記事は10分の1くらいの長さで十分伝わったよね。少なくともビデオじゃなかったのは良かった！おかげで重要な詳細だけざっと読めたし。
複数の人が同じことに気づいてるのが面白いね。私にとって、この記事はこう書けば十分だったかも：
“GitLabのリポジトリバックアップに48時間かかってた大きな原因は、git bundle createの中の、コマンドライン引数で渡された参照の重複をチェックする関数だったんだ。このチェックにネストされたforループ（O(N2)）があって、これをMapデータ構造に変えてGit本家に修正パッチを送ったんだ。パッチは採用されたけど、次のGitバージョンを待たずに修正をバックポートしたら、バックアップ時間が41分になったよ。”
それは「Impact」スタイルの技術文書だね。問題と規模を強調して、ソリューションをビジネスや顧客成功の視点で見せるやり方。寛大に見れば、チームや個人のビジネス価値を示すためで、昇進とかにつながる。でも、確かにこのスタイルは読むのがイライラすることもあるね。
そうそう。記事全部読んでさ、これLLMが書いたんじゃない？って思ったんだよね。文体がLLMっぽいんだもん。
彼らはエムダッシュを取りに来た時、俺は黙っていた。そして箇条書きを取りに来た時も、俺は黙っていた…
俺だけじゃなくてよかった！あとさ、技術記事なのにコードスニペットがないのが残念。コード見せてくれよ。ChatGPTのせいで箇条書きが台無し…正直、この記事書くのに数分だろ？LLMでダメにするなよ。文法チェックとかに使えばいいじゃん。
まさに俺も同じこと思った。もっと短い文章なら、記事の読む体験は絶対によくなったはず。
まだ記事読んでない人へ。フレイムグラフまでスクロールして、修正をバックポートする話が始まるとこまで読め。そこでストップ。
”GitLabリポジトリのバックアップ、48時間が41分になった方法！”を読む時間を4.8分から41秒に減らす方法
もっと長くてもよかったな。なんで彼らが2つの参照（refs）でバックアップバンドルを作ってたのか、いまだに分からないんだよね :)
修正を見るとね、パフォーマンスが悪かったのは、デデュープ処理が参照が多い全部のケースで走ってたからみたいだよ。修正内容はこのリンク見てね→https://github.com/git/git/commit/bb74c0abbc31da35be52999569…
でもさ、実際バックアップする前にさ、コマンドラインで参照をデデュープできなかったのかな？参照なんてブランチごとにせいぜい数百個くらいでしょ？
要するに、パフォーマンスが悪かったのは重複の数じゃなくて、参照の数が多かったのが原因だったんだよ。
そうそう！GitLabのリポジトリの中にはね、何百万もの参照があるところもあるんだよ。
Gitのフォルダ圧縮に48時間はありえないよ、数GBなのに！41分でも長い気がするな。
Git bundleじゃなくて、スナップショットとアーカイブじゃダメなの？ZFSのバックアップと比べてGit bundleって何がいいの？
Gitの公式FAQによると、Gitの整合性チェックをバイパスするリスクがあるからバックアップは推奨されてるけど、安全な方法は載ってないんだって。個人的にはSyncthingとBtrfs snapshotsで十分いけるよ。ストレージとかネットワークと同じくらい速いし。https://git-scm.com/docs/gitfaq#_transfers
俺はSyncthing使ったときに、初めてGitのリポジトリを壊しちゃったことがあるんだよね。
Btrfs snapshotsってところがポイントだと思うんだ。直接.gitディレクトリを同期するのは危険だよね。Btrfs snapshotsなら、Gitの整合性が保たれた状態だけバックアップできるんじゃない？
確かに俺のやり方はSyncthingを先に使って、それをBtrfsスナップショットでバックアップするっていう変なやり方だけどね。個人の範囲なら、同時に作業しない限り大丈夫。
Git fsckとかスナップショットとかSyncthingのバージョン管理、Gitの期限切れファイル削除でリカバリーできるし。10年で一度だけ壊したけど、すぐ直せたよ。
もしファイルシステムのスナップショットが安全じゃないってんなら、停電とかクラッシュしたときもGitは壊れるってこと？それってGitのバグじゃないの？
ZFSスナップショットをS3みたいなZFSじゃないとこにオフサイトするのは難しいよね。でも、git clone --bundle-uriっていうあんまり知られてないGitの機能があるんだ。これはクライアントがbundleの場所指定したり、サーバーがクライアントにbundleの場所を教えて、クライアントがbundle取ってきて展開、それから差分をサーバーから取るっていうやり方。大きいリポジトリのクローンでサーバーの負担が軽くなるし、クライアントの初回クローンがめっちゃ速くなるよ。
ZFSじゃないところにちゃんと一貫性のあるスナップショットバックアップ取りたいなら、スナップショットをクローンしてそこからrsyncするのが一番安全だと思うよ。これだと一手間かかるけど、スナップショットのアトミック性は保てるんだ。追記だけど、.zfsスナップショットディレクトリが有効になってるなら、そこからrsyncするのもありだよ。
ZFSはファイルとか好きなものにパイプして送れるんだよ。インクリメンタル送信もできるし、送信側でブックマークに変換すれば、送った後に古い履歴データ残しておく必要もなくなるんだ。
・・・ってことは、キャッシュされるべきものにキャッシュを追加しただけなの？
これってホントにみんながGitリポジトリを”バックアップ”するやり方なの？だってGitって分散バージョン管理システムでしょ。別のリポジトリに変更をミラーして、そっちでZFSとかスナップショットとかバックアップソフト使うようにすればいいんじゃないの？バージョン管理の情報は・・・分散させるべきでしょ？
記事読んで全く同じこと思ったよ！ZFSだったらどれくらい時間かかるのかめっちゃ知りたいな。
”アルゴリズム変更でバックアップ時間が指数関数的に短縮”って表現だけど、もしバックアップ時間がO(n^2)だったのがO(n^2 / 2^n)になったってこと？そんなわけないよね。
もっとコメントを表示（2）
これは”指数関数的”っていう言葉の正確な数学的な定義じゃなくて、口語的な意味で”めちゃくちゃ”ってことだよ。
正確な数学的意味を持つ単語を、まさに数学的表記を使って正確に話そうとしてる文章で使うべきじゃないし、読み手がその単語を正確な数学的な意味で解釈しないと思っちゃダメだよ。
意味なくて非建設的な重箱の隅をつつくような行為だね。
ちょっと同意だけど、他にいい言葉ないかな？「二次関数的に」じゃパンチ効かないよね。
n^2のアルゴリズムをlog(n)のルックアップに置き換えたら指数関数的なスピードアップになる…わけないか。ハッシュマップは普通O(1)だから、それよりさらに速いんだけどね。
普通の人間なら文脈でわかるって期待するならそうすべき。細かいことつつくのが大好きな、文脈わかるくせに揚げ足取るHN読者相手じゃなきゃね。
それ違うよ。n^C ＼ e^n = log(n) とかなら別だけど、そうじゃないから。log(n)と多項式の差は対数的であって、指数関数的じゃないんだ。
僕は反対だな。「指数関数的」の誤用はマジでイラつくポイント。嘘くさい文章でよくある「数学的に正確な表現を使って賢そうに見せる」ってやつの典型だよ。ここでは成長関数を指してる珍しいケースだし、正直な書き方（これも珍しい）だけど、それでも間違ってる。二次関数的とか二次関数vs線形って書くべきだったね。どっちにしても、だらしない言葉遣いはだらしない思考につながるんだよ。
＼u003epedantry
指数関数的な削減を探して人生の2分を無駄にしたよ。他にもいっぱいいるでしょ。今もこうやってクソ投稿してさらに人生を無駄にしてるけど、それは意識的な選択だからマシかな。
修正した関数自体（6倍改善）ではアルゴリズムの複雑性は下がったけど、アルゴリズムをどう使ってたかって文脈では全体的な影響はずっと大きかった（1％になった）。これなら「指数関数的」って言ってもおかしくないかもね。実際の複雑性を計算するのは関係ないし、時間の無駄だよ。
最近、雑な書き方が桁違いに増えてる気がするね。
個人的に特にイラつくのは、「指数関数的に」っていう言葉をたった2つのデータポイント間の変化に使うことかな。君が言ってるやつの特定バージョンだね。「わかってないって言わずに、わかってないって言う方法」みたいな感じ。
君に返信してるOPじゃないけど、フェアに言えば、Big-Oの性能特性について話してて「アルゴリズム」って言葉まで使ってる文で、「指数関数的に」を日常的な意味で使うのは、絶対に最悪な言葉の選択だね。
ああ、うん、だって”普通の人間”はO(n^2)の意味は知ってるけど、クソっ、exponentialは間違って使うんだもんな。
”言葉には意味がある”。これに同意できないなら、喋ったり書いたりすべきじゃないね、個人的には。違う意味の言葉が実際には等しいって主張する奴は、言語を扱う仕事なんてするべきじゃないよ。
それは”speedup”をランタイムを割ることだって考えるか、ランタイムに関数を適用することだって考えるかに依るよね。つまり、君はf(n) speedupがT(n)＼f(n)だって言ってるけど、他の人はf(T(n))かその変形だって言うだろうね。
でも、たまたまn=2^cなら、logarithmic complexityのアルゴリズムはcしか時間かかんないんだ。だから計算量理論では通常、O(2^n)からO(n)みたいにexponential speedupって呼ばれるんだよ。もっと具体的に言えば、最初のアルゴリズムが1024秒かかるなら、二番目はどっちの場合もたった10秒だよ。だから、意味は通じると思うな。
いやいや、君は読解力を高めるのに2分を費やしただけだよ。
＞pedanticgit bundle createのアルゴリズムに関する記事の対象読者って誰だと思うんだよ？O(n^2)アルゴリズムがどういう風にexponentialに影響を与えてるのか理解しようと俺の人生の約2分を使ったよ。Exponentialはbig-Oと同じ文で太字になってた。50＼50で荒らしか筆者の見落としだね。
＞実際の計算量を理解するのは関係ないし経済的な時間の使い道じゃない
修正は入れ子ループをmapに置き換えることだったんだ。言葉の意味を知ってて、問題を特定して修正するくらい理解してるなら、これがO(n^2)からO(n)になる（バケット数みたいな詳細は別として）って理解するのはすぐできることだよ。
コンピュータサイエンスではbig O notationを簡略化するんだよ。これは標準的なやり方だからね。
もし技術的な意味じゃなく単に”すごく”って意味で言ってるだけなら、いっぱい言葉があるじゃん。enormouslyとか、immenselyとか、tremendouslyとか、remarkablyとか、incrediblyとか、vastlyとかさ。
mapをループの中でまだ使ってるなら、tree-based mapならO(n log n)か、hash mapならO(n)になるだろうね。
