設計パターン・最適化図鑑 · 基礎から応用へ

Copy-on-writeによるデータ共有

読み手の不変スナップショットを保ち、更新時のコピーと公開を分けて考える。

この記事をロゲイアに質問する確認問題3問に進むこれまでの誤答を復習する

更新日

この記事の目次
  1. 読み手が持つ配列を変えない
  2. 走査中に通知先が増える例
  3. 浅いコピーと公開の境界
  4. 更新が多いデータには費用が増える
  5. この記事をロゲイアに質問する理解を確かめる

読み手が持つ配列を変えない

データ構造のCopy-on-writeは、読者が参照中の構造を直接変更せず、新しい版を作って公開します。通知先のリストを多数のスレッドが走査し、登録変更はまれという場面で役立ちます。JavaのCopyOnWriteArrayListは、変更操作で内部配列をコピーする具体例です。OSのページ単位のCopy-on-writeとは、同じ考え方でもコピーの単位や更新の契機が違います。配列の全要素を深く複製する仕組みとも限りません。

走査中に通知先が増える例

通知先が[A,B]の時点で走査を開始し、その後にCを追加すると、新しいリストは[A,B,C]です。旧版を持つ読者はAとBを処理し、次の走査からCを含む版を使います。途中からCを追加するかは実装のスナップショット契約に従います。Javaのこのリストのイテレータは作成時点の配列を参照します。最新の登録が必ず現在進行中の通知へ間に合う、という保証とは違います。

浅いコピーと公開の境界

配列をコピーしても、要素Aの内部フィールドまで不変になるとは限りません。Aが指すオブジェクトを別スレッドが更新すれば、その競合は残ります。構造のスナップショットと、要素の深いスナップショットを区別します。自作する場合は新しい版を安全に公開する同期も必要です。共有ポインタへ通常の代入をするだけで十分かは言語のメモリモデル次第であり、参照の寿命や回収方法も合わせて設計します。

更新が多いデータには費用が増える

要素数nの配列を更新のたびにコピーする方式では、1回の更新にO(n)の参照コピーが必要です。1万要素のリストへ1件ずつ1000回追加すると、多くの重複コピーが起こります。まとめて変更する操作や、部分構造を共有する永続データ構造が適する場合があります。古いスナップショットを長く持つ読者は回収も遅らせます。読み取りの容易さと引き換えに、更新時間、確保量、保持メモリを支払う方式です。

削除した通知先が旧スナップショットに残ることもあります。解除操作の直後に一切呼び出されない保証が必要なら、単なる構造の置き換えに加えて、進行中の走査を待つなどの仕組みを設計します。通知登録の使い勝手と、解除の厳密な意味を揃えてください。

読了と問題の結果を、言語ごとにこのブラウザへ保存します。

コースの順番に沿って学ぶ

CS基礎を固める · STEP 18

サーバーの中で起きていること · STEP 15

学習コースから次を選ぶ