ハクソク

世界を動かす技術を、日本語で。

Unixが原子的に行えること (2010)

109日前原文(rcrowley.org)

概要

UNIX系やPOSIX準拠OSで カーネルが保証するアトミック操作 のカタログ。 マルチスレッドや多プロセス環境 で安全なプログラム作成の基礎。 ロックやミューテックスなし で活用可能な手法。 ファイルシステムやファイルディスクリプタ を対象とした例多数。 NFS等の分散FSでは動作保証外 な点に注意。

UNIXでアトミックにできること

  • カーネルによるアトミック性保証 プログラム上で明示的なロックを使わず、 カーネルが内部で排他制御 する操作 ロック処理による CPU負荷の回避

  • パス名操作（ローカルファイルシステム推奨） NFS等のネットワークFSでは アトミック性保証外 mv -T <oldsymlink> <newsymlink>

    • <newsymlink>のターゲットを アトミックに<oldsymlink>へ切替
    • 実体は rename(2) システムコール呼び出し
    • Mac OS Xのmv(1) ではrename(2)を使わないため非対応 link(oldpath, newpath)
    • ハードリンク作成。newpathが既存なら EEXISTエラー
    • ファイルロック用途 として利用可能（lsで可視化） symlink(oldpath, newpath)
    • シンボリックリンク作成。既存ならEEXISTエラー
    • ディレクトリロック にも応用可能
    • ダングリングシンボリックリンク （ターゲット消失時）に注意
    • inode数は有限資源 rename(oldpath, newpath)
    • 同一ファイルシステム内でパス名変更をアトミックに実行
    • oldpathが無い場合 ENOENTエラー
    • ファイル削除予定時に 自然なロック手法 open(pathname, O_CREAT | O_EXCL, 0644)
    • 新規ファイル作成と同時オープン
    • 既存なら EEXISTエラー
    • 排他処理やタスク担当決定 に活用 mkdir(dirname, 0755)
    • 新規ディレクトリ作成。既存ならEEXISTエラー
    • ディレクトリ用排他制御 手法

  • ファイルディスクリプタ操作 fcntl(fd, F_GETLK, &lock), fcntl(fd, F_SETLK, &lock), fcntl(fd, F_SETLKW, &lock)

    • ファイル領域ごとのロック
    • F_SETLKW はロック取得まで ブロック
    • Linuxの mandatory locking は競合条件があり非推奨 fcntl(fd, F_GETLEASE), fcntl(fd, F_SETLEASE, lease)
    • 他プロセスによる オープン/トランケート時SIGIO通知
    • 通知後は F_SETLEASE, F_UNLCK でリース解除
    • fcntl(fd, F_NOTIFY, arg) は同期用途には不向き mmap(0, length, PROT_READ | PROT_WRITE, MAP_SHARED, fd, 0)
    • ファイル内容をメモリマップ し、複数プロセス間で共有
    • msync(addr, length, MS_INVALIDATE) でデータ同期
    • mmap(2), msync(2)

  • 仮想メモリ操作（GCC Atomic Builtins） __sync_fetch_and_add, __sync_add_and_fetch, __sync_val_compare_and_swap

    • フルバリア付きアトミック操作
    • ロックフリーアルゴリズムの基礎
    • GCC組込関数 として提供

注意点・補足

  • NFS等分散FSではアトミック性保証外
    • 複数カーネルが絡むため、 ローカルFS限定 で利用推奨
  • inodesは有限資源
    • 大量ロックやシンボリックリンク利用時は枯渇に注意
  • 競合条件やレースコンディション
    • 新たな事例や発見があれば rcrowleyへ連絡推奨

まとめ

  • カーネルのアトミック操作を最大限活用 し、 安全かつ効率的な排他制御 を実現
  • ファイルシステムやメモリ操作を適切に選択 し、 ロックレス設計 を推進
  • 分散FSや実装差異（例：Mac OS X）には要注意

Hackerたちの意見

lnの原子性を使えば、シンプルでポータブルなロックシステムが作れるよね。https://gist.github.com/pwillis-els/b01b22f1b967a228c31db3cf...

└

すごく役立つパターンの説明だね。あの有名な壊れたNFSでも、ハードリンクの作成の原子性を守ってるって知って驚いたよ。

rename()は、ファイルシステムベースの同期には間違いなく一番使いやすいよ。

そんなに多くはないみたいだけど、シンボリックリンクの変更については知らなかったな。それは結構役立つかも。

原子性を持つことができるけど、一度に一つのファイルしか扱えないから、レースコンディションが起こる可能性もあるんだよね（たとえ一つのファイルだけが必要でも）。O_EXCLみたいなものは役に立つけど、結局一度に一つのことしかできないから、場合によっては問題になることもある。複数のオブジェクトを使ったトランザクションはできないしね。だから、複数のオブジェクトでトランザクションができるオペレーティングシステムを設計したいと思ってるんだ。

└

Windowsでは、VistaでこういうAPIが追加されたけど、今は「複雑さや開発者が考慮すべきさまざまなニュアンスのため」に非推奨になってるんだって。https://learn.microsoft.com/en-us/windows/win32/fileio/about...

└

よくわからない、ごめん。つまり、もしこういうコマンドを実行したら：mv a b mv c d その結果、aとdが存在する状態になるってこと？そんな「順序が狂った実行」は衝撃的だと思うけど。それが言いたいことじゃないなら、できないことの具体例を教えてもらえる？

└

いくつかのケースでは、「at」関数（openat...）を使ってディレクトリツリーで作業を始めることができるよ。ツリーのトップレベルで論理的な「ロック」を行えば、いい選択肢かもしれない。他のケースでは、フォルダへのシンボリックリンクを使うパターンを使ったことがある。シンボリックリンクは原子的に作成、解決、または更新されて、必要なのは最終的な整合性だけ。最後のケースは、いくつかのAPTリポジトリインデックスを管理するためだった。インデックスは新しいテスト版や不安定版のソフトウェアを公開するために常に更新されていて、機械は定期的にリポジトリインデックスを取得してた。APTプロトコルと構造はちょっと「バカ」だから（良い意味でも悪い意味でも）、作成された順番とは逆の順番でファイルを取得する必要があって、明らかな問題が発生する。例えば、ファイルのリストが更新された後にしか署名が更新されなかったり、パッケージのリストが作成された後にしかファイルのリストが作成されなかったりする。要するに、各更新で整合性のある新しいフォルダが作成されて、シンボリックリンクが最後に作成されたフォルダを指すようにして（フォルダを入れ替えることができなかったから）、小さなHTTPサーバーが最初のファイルが取得されたときにサーバーサイドのセッションを開始して、同じインデックスリストからのファイルだけを返すようにした。すべてが最終的に整合性があって、APTが署名やハッシュの不一致について文句を言うことはなかった。重要な要素は、特定のフォルダに対して「openat」システムコールにアクセスできなかったJava実装に対処するためのシンボリックリンクの原子性だった。

記事の日付のせいか、欠けてるものがあるね：mv --exchange、つまりrenameat2+RENAME_EXCHANGE。これで2つのファイルパスを原子的に入れ替えられるよ。

└

タイトルにはUnixって書いてあるけど、renameat2はLinux専用だね。

└

ちょっと前にこれを使ってみたけど、あんまり普及してないことに気づいた。これにはcoreutilsのバージョン9.1以上が必要だけど、多くのディストリビューションはこれを出荷してないんだよね。自分の用途のために、https://github.com/rubenvannieuwpoort/atomic-exchangeを作ったよ。

fcntl(fd, F_GETLK, &lock), fcntl(fd, F_SETLK, &lock), and fcntl(fd, F_SETLKW, &lock) それに、flockっていうCLIユーティリティもあって、シェルスクリプトでフロックを使えるよ。

└

この文脈でのフロックって何？羊の数じゃないよね…？

└

UNIX/POSIXのファイルロックはアドバイザリーで、強制されるものじゃない。すべてのプロセスが協力しないと機能しないんだ。

└

flockとPOSIXロックって、全然違うシステムに基づいてるんじゃないの？

これをいくつか使って、代替のSQLiteロックプロトコルを実装してるよ。POSIXのファイルロックのセマンティクスは本当に壊れてて、修復不可能だね。https://news.ycombinator.com/item?id=46542247

POSIX仕様で保証されない限り、それらは実装依存で、ポータブルなコードには頼るべきではないよ。

└

これらの中でPOSIX仕様によって保証されてないものはどれ？しばらく勉強してなかったけど、記事に出てたやつは保証されてたはず。

著者がO_APPENDの原子的な書き込みを省いた理由が気になるな。

└

よくわからないけど、O_APPENDが指定されているほど耐久性がないファイルシステムってあるんじゃない？それが原子的な操作に悪影響を及ぼす可能性があるかも。

└

確か、これにはO_SYNCとO_DIRECTが必要だよね。でも、それを保証しているのは一部のファイルシステムだけで、ファイルサイズの更新が原子的かどうかはあまり自信ないな。その他の部分については結構確信があるけど。Matkladがこの件について書いたり動画を作ったりしてたよ。あと、ALICEっていうツールがあって、その作者たちがこのテーマについてのホワイトペーパーを出してる。さらに、Badgerデータベースがこの問題をどう解決したかについてのブログ記事もあったよ。

いいカタログだね。決定論的でステートレスなシステムを構築する中で気づいた微妙なことは、原子的なファイルシステムとメモリ操作だけがロックなしで秘密を安全に計算したり保存したりする方法だってこと。rename/link/O_EXCLパターンを一時的なメモリバッファと組み合わせることで、機密データがディスクに部分的に書き込まれることがなくなり、マルチプロセスのワークフローでの競合状態やサイドチャネルの露出が減るんだ。