詳説 データベース ―ストレージエンジンと分散データシステムの仕組み

詳説 データベース ―ストレージエンジンと分散データシステムの仕組み

by Alex Petrov, 小林 隆浩, 成田 昇司
Released July 2021
Publisher(s): O'Reilly Japan, Inc.
ISBN: 9784873119540

Read it now on the O’Reilly learning platform with a 10-day free trial.

O’Reilly members get unlimited access to books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.

Start your free trial

Book description

データベースを選択し、使用し、管理するには、その内部構造を理解することが不可欠です。しかし、今日ではたくさんの分散型データベースやツールが存在するため、それぞれが何を提供しているのか、どのように異なるのかを理解することは困難です。本書はデータベースとストレージエンジンの内部で利用されている概念を解説します。データベースそれぞれで大きな違いがあるストレージエンジンの内部構造や、データの分散方法を決定するサブシステムについて詳述する本書は、データべースシステムを使ってソフトウェアを構築するすべての人に必携の一冊です。

Table of contents

  1. 　大扉
  2. 　原書大扉
  3. 　クレジット
  4. 　謝辞
  5. 　監訳者まえがき
  6. 　はじめに
  7. 第Ⅰ部　ストレージエンジン
  8. 　　Ⅰ.1　データベースの比較
  9. 　　Ⅰ.2　トレードオフの理解
  10. 　1章　基本事項の紹介と概要
  11. 　　1.1　DBMSアーキテクチャ
  12. 　　1.2　メモリベースのDBMSとディスクベースのDBMS
  13. 　　　1.2.1　メモリベースのストアの永続性
  14. 　　1.3　列指向DBMSと行指向DBMS
  15. 　　　1.3.1　行指向のデータレイアウト
  16. 　　　1.3.2　列指向のデータレイアウト
  17. 　　　1.3.3　相違点と最適化
  18. 　　　1.3.4　ワイドカラムストア
  19. 　　1.4　データファイルとインデックスファイル
  20. 　　　1.4.1　データファイル
  21. 　　　1.4.2　インデックスファイル
  22. 　　　1.4.3　間接参照としてのプライマリインデックス
  23. 　　1.5　バッファリングとイミュータビリティおよびオーダリング
  24. 　　1.6　まとめ
  25. 　2章　Bツリーの基本
  26. 　　2.1　二分探索木
  27. 　　　2.1.1　ツリーのバランシング
  28. 　　　2.1.2　ディスクベースのストレージ用のツリー
  29. 　　2.2　ディスクベースの構造
  30. 　　　2.2.1　ハードディスクドライブ
  31. 　　　2.2.2　ソリッドステートドライブ
  32. 　　　2.2.3　ディスク上の構造
  33. 　　2.3　ユビキタスBツリー
  34. 　　　2.3.1　Bツリーの階層
  35. 　　　2.3.2　セパレータキー
  36. 　　　2.3.3　Bツリーの検索の計算量
  37. 　　　2.3.4　Bツリーの検索アルゴリズム
  38. 　　　2.3.5　キーのカウント
  39. 　　　2.3.6　Bツリーノードの分割
  40. 　　　2.3.7　Bツリーノードのマージ
  41. 　　2.4　まとめ
  42. 　3章　ファイルフォーマット
  43. 　　3.1　モチベーション
  44. 　　3.2　バイナリエンコーディング
  45. 　　　3.2.1　プリミティブな型
  46. 　　　3.2.2　文字列と可変長のデータ
  47. 　　　3.2.3　ビットパック化データ：ブール型と列挙型とフラグ
  48. 　　3.3　一般的な原則
  49. 　　3.4　ページ構造
  50. 　　3.5　スロット化ページ
  51. 　　3.6　セルのレイアウト
  52. 　　3.7　セルをスロット化ページに結合
  53. 　　3.8　可変長データの管理
  54. 　　3.9　バージョン管理
  55. 　　3.10　チェックサム
  56. 　　3.11　まとめ
  57. 　4章　Bツリーの実装
  58. 　　4.1　ページヘッダ
  59. 　　　4.1.1　マジックナンバー
  60. 　　　4.1.2　兄弟（Sibling）リンク
  61. 　　　4.1.3　右端のポインタ
  62. 　　　4.1.4　ノードハイキー（Node High Key）
  63. 　　　4.1.5　オーバーフローページ
  64. 　　4.2　二分探索
  65. 　　　4.2.1　間接ポインタによる二分探索
  66. 　　4.3　スプリットとマージの伝播
  67. 　　　4.3.1　パンくずリスト
  68. 　　4.4　リバランシング
  69. 　　4.5　右側限定の追加
  70. 　　　4.5.1　バルクロード
  71. 　　4.6　圧縮
  72. 　　4.7　バキュームとメンテナンス
  73. 　　　4.7.1　更新と削除による断片化
  74. 　　　4.7.2　ページのデフラグ
  75. 　　4.8　まとめ
  76. 　5章　トランザクション処理とリカバリ
  77. 　　5.1　バッファ管理
  78. 　　　5.1.1　キャッシュの概要
  79. 　　　5.1.2　キャッシュの退避
  80. 　　　5.1.3　キャッシュにおけるページのロック
  81. 　　　5.1.4　ページの置換
  82. 　　5.2　リカバリ
  83. 　　　5.2.1　ログの概要
  84. 　　　5.2.2　操作とデータログ
  85. 　　　5.2.3　stealポリシーとforceポリシー
  86. 　　　5.2.4　ARIES
  87. 　　5.3　同時実行制御
  88. 　　　5.3.1　直列化可能性
  89. 　　　5.3.2　トランザクションの分離
  90. 　　　5.3.3　読み取りと書き込みのアノマリー
  91. 　　　5.3.4　分離レベル
  92. 　　　5.3.5　楽観的同時実行制御
  93. 　　　5.3.6　マルチバージョン同時実行制御
  94. 　　　5.3.7　悲観的同時実行制御
  95. 　　　5.3.8　ロックベースの同時実行制御
  96. 　　5.4　まとめ
  97. 　6章　Bツリーの亜種
  98. 　　6.1　コピーオンライト
  99. 　　　6.1.1　コピーオンライトの実装：LMDB
  100. 　　6.2　ノード更新の抽象化
  101. 　　6.3　遅延Bツリー
  102. 　　　6.3.1　WiredTiger
  103. 　　　6.3.2　遅延適応ツリー
  104. 　　6.4　FDツリー
  105. 　　　6.4.1　フラクショナルカスケーディング
  106. 　　　6.4.2　対数的な配列
  107. 　　6.5　Bwツリー
  108. 　　　6.5.1　アップデートチェーン
  109. 　　　6.5.2　コンペアアンドスワップによる同時実行性の制御
  110. 　　　6.5.3　構造を変更する操作
  111. 　　　6.5.4　統合とガベージコレクション
  112. 　　6.6　キャッシュオブリビアスBツリー
  113. 　　　6.6.1　van Emde Boasレイアウト
  114. 　　6.7　まとめ
  115. 　7章　ログ構造化ストレージ
  116. 　　7.1　LSMツリー
  117. 　　　7.1.1　LSMツリー構造
  118. 　　　7.1.2　更新と削除
  119. 　　　7.1.3　LSMツリーの検索
  120. 　　　7.1.4　マージイテレーション
  121. 　　　7.1.5　調停
  122. 　　　7.1.6　LSMツリーにおけるメンテナンス
  123. 　　7.2　読み取りと書き込みおよび領域の増幅
  124. 　　　7.2.1　RUM予想
  125. 　　7.3　実装の詳細
  126. 　　　7.3.1　Sorted String Table
  127. 　　　7.3.2　ブルームフィルタ
  128. 　　　7.3.3　スキップリスト
  129. 　　　7.3.4　ディスクアクセス
  130. 　　　7.3.5　圧縮
  131. 　　7.4　順序付けされないLSMストレージ
  132. 　　　7.4.1　Bitcask
  133. 　　　7.4.2　WiscKey
  134. 　　7.5　LSMツリーにおける並行性
  135. 　　7.6　ログスタック
  136. 　　　7.6.1　フラッシュトランスレーションレイヤ
  137. 　　　7.6.2　ファイルシステムログ
  138. 　　7.7　LLAMAと注意深いスタック
  139. 　　　7.7.1　Open-Channel SSD
  140. 　　7.8　まとめ
  141. 　第Ⅰ部　むすび
  142. 第Ⅱ部　分散システム
  143. 　　Ⅱ.1　基本的な定義
  144. 　8章　基本事項の紹介と概要
  145. 　　8.1　並行実行
  146. 　　　8.1.1　分散システムでの共有された状態
  147. 　　8.2　分散コンピューティングの誤謬
  148. 　　　8.2.1　プロセス
  149. 　　　8.2.2　クロックと時間
  150. 　　　8.2.3　状態の一貫性
  151. 　　　8.2.4　ローカル実行とリモート実行
  152. 　　　8.2.5　障害への対処の必要性
  153. 　　　8.2.6　ネットワーク分断と部分障害
  154. 　　　8.2.7　カスケード障害
  155. 　　8.3　分散システムの抽象化
  156. 　　　8.3.1　リンク
  157. 　　8.4　2人の将軍の問題
  158. 　　8.5　FLPの不可能性
  159. 　　8.6　システムの同期性
  160. 　　8.7　障害モデル
  161. 　　　8.7.1　クラッシュ障害
  162. 　　　8.7.2　欠落障害
  163. 　　　8.7.3　任意障害
  164. 　　　8.7.4　障害の処理
  165. 　　8.8　まとめ
  166. 　9章　障害検出
  167. 　　9.1　ハートビートとping
  168. 　　　9.1.1　タイムアウトフリーな障害検出機能
  169. 　　　9.1.2　ハートビートのアウトソーシング
  170. 　　9.2　Phi-Accural Failure Detector
  171. 　　9.3　ゴシップと障害検出
  172. 　　9.4　障害検出の問題記述の反転
  173. 　　9.5　まとめ
  174. 　10章　リーダー選出
  175. 　　10.1　ブリーアルゴリズム
  176. 　　10.2　次候補へのフェイルオーバー
  177. 　　10.3　候補者／一般人の最適化
  178. 　　10.4　招待アルゴリズム
  179. 　　10.5　リングアルゴリズム
  180. 　　10.6　まとめ
  181. 　11章　レプリケーションと一貫性
  182. 　　11.1　可用性の実現
  183. 　　11.2　悪名高いCAP
  184. 　　　11.2.1　注意が必要なCAPの使用
  185. 　　　11.2.2　収穫と収量
  186. 　　11.3　共有メモリ
  187. 　　11.4　オーダリング
  188. 　　11.5　一貫性モデル
  189. 　　　11.5.1　厳密な一貫性
  190. 　　　11.5.2　線形化可能性
  191. 　　　11.5.3　逐次一貫性
  192. 　　　11.5.4　因果一貫性
  193. 　　11.6　セッションモデル
  194. 　　11.7　結果整合性
  195. 　　11.8　調整可能な一貫性
  196. 　　11.9　ウィットネスレプリカ
  197. 　　11.10　強力な結果整合性とCRDTs
  198. 　　11.11　まとめ
  199. 　12章　アンチエントロピーと情報散布
  200. 　　12.1　読み取り修復
  201. 　　12.2　ダイジェスト読み取り
  202. 　　12.3　ヒンテッドハンドオフ
  203. 　　12.4　Merkleツリー
  204. 　　12.5　ビットマップバージョンベクトル
  205. 　　12.6　ゴシップの散布
  206. 　　　12.6.1　ゴシップの仕組み
  207. 　　　12.6.2　オーバーレイネットワーク
  208. 　　　12.6.3　ハイブリッドゴシップ
  209. 　　　12.6.4　部分的なビュー
  210. 　　12.7　まとめ
  211. 　13章　分散トランザクション
  212. 　　13.1　アトミックに見せる操作
  213. 　　13.2　ツーフェーズコミット
  214. 　　　13.2.1　2PCにおけるコホートの障害
  215. 　　　13.2.2　2PCにおけるコーディネータの障害
  216. 　　13.3　スリーフェーズコミット
  217. 　　　13.3.1　3PCにおけるコーディネータの障害
  218. 　　13.4　Calvinによる分散トランザクション
  219. 　　13.5　Spannerによる分散トランザクション
  220. 　　13.6　データベースパーティショニング
  221. 　　　13.6.1　コンシステントハッシュ法
  222. 　　13.7　Percolatorによる分散トランザクション
  223. 　　13.8　調整の回避
  224. 　　13.9　まとめ
  225. 　14章　合意
  226. 　　14.1　ブロードキャスト
  227. 　　14.2　アトミックブロードキャスト
  228. 　　　14.2.1　Virtual Synchrony
  229. 　　　14.2.2　Zookeeper Atomic Broadcast（ZAB）
  230. 　　14.3　Paxos
  231. 　　　14.3.1　Paxosアルゴリズム
  232. 　　　14.3.2　Paxosにおけるクォラム
  233. 　　　14.3.3　障害シナリオ
  234. 　　　14.3.4　Multi-Paxos
  235. 　　　14.3.5　Fast Paxos
  236. 　　　14.3.6　Egalitarian Paxos
  237. 　　　14.3.7　Flexible Paxos
  238. 　　　14.3.8　合意の汎用ソリューション
  239. 　　14.4　Raft
  240. 　　　14.4.1　Raftにおけるリーダーの役割
  241. 　　　14.4.2　障害シナリオ
  242. 　　14.5　ビザンチン合意
  243. 　　　14.5.1　PBFTアルゴリズム
  244. 　　　14.5.2　リカバリとチェックポイント
  245. 　　14.6　まとめ
  246. 　第Ⅱ部　むすび
  247. 　付録A　参考文献
  248. 　著者紹介
  249. 　奥付

Product information

  • Title: 詳説 データベース ―ストレージエンジンと分散データシステムの仕組み
  • Author(s): Alex Petrov, 小林 隆浩, 成田 昇司
  • Release date: July 2021
  • Publisher(s): O'Reilly Japan, Inc.
  • ISBN: 9784873119540

You might also like

book

Node.jsデザインパターン 第2版

by Mario Casciaro, Luciano Mammino, 武舎 広幸, 阿部 和也

Node/JavaScriptアプリの設計技法を、実際に手を動かしながら学ぶハンズオン形式の解説書。本書では最初に、JavaScriptの大きな特徴でありながら多くの開発者にとって馴染みの薄い非同期処理（コールバックを用いた処理）についてその仕組みを詳しく説明するとともに主なデザインパターンを説明し、Node.jsの基礎を押さえます。次に、ストリームや一般的なデザインパターンのNode.jsでの実装、Node.js専用のデザインパターンといった事柄を解説します。最後に、ユニバーサルJavaScript、スケーラビリティ、Node.jsを使ったエンタープライズアプリの開発といったより高度なトピックを扱います。中級以上のウェブ開発者を対象としています。バージョン11対応。

book

動かして学ぶAI・機械学習の基礎 ―TensorFlowによるコンピュータビジョン、自然言語処理、時系列データの予測とデプロイ

by Laurence Moroney, 菊池 彰

人工知能研究の第一人者であるAndrew Ngとともに、TensorFlowの開発と普及に尽力し、Coursera教材を共同で作成したり、人気の高い講座をいくつも担当するなど、機械学習の教育に長年携わってきた著者による、とてもわかりやすい実践的な入門書です。AIや機械学習の初学者がゼロから学んでいけるように、コードをステップバイステップで解説し、Google Colabで実際に動かしながら理解を深める実践的なアプローチを取っています。Web、モバイル、クラウド、組み込み向けの豊富な具体例を通して、TensorFlowの基本知識、モデル構築の勘所、画像からの特徴量検出、自然言語処理、公開データの活用、モデルを使用するAndroidやiOSアプリの作成、Webおよびクラウド上へのモデルのデプロイといった実践的な知識とテクニックを習得できます。

book

システム運用アンチパターン ―エンジニアがDevOpsで解決する組織・自動化・コミュニケーション

by Jeffery D. Smith, 田中 裕一

上層部がDevOpsに理解のない組織で働き、組織構造を変える権限を持っていない開発者であっても、チームにDevOpsを導入するための現実的な方法を紹介します。 重厚な承認プロセス、可視化されていない運用、プロセスの最後でのみ行われるソフトウェアテスト、ノイズだらけのアラート、インシデントから学習しない習慣、時間外のデプロイ、情報のため込みなどを取り上げ、ソフトウェアシステムの開発運用が滞るチームや組織に共通してみられる陥りがちな状況や犯しがちな間違いをアンチパターンとして紹介します。そして管理職やマネージャでなく、エンジニアが実行し、繰り返すことで改善できる具体的な行動を解説します。 組織で必要とされる変化を、エンジニアが行動することで実現する本書は、ソフトウェアシステムをよりよく開発運用したいエンジニア必携の一冊です。 追加コンテンツとして、翻訳者である田中裕一氏が、本書で言及されるアンチパターンの概要について解説する動画を こちらからご視聴いただけます。併せてご覧ください。

book

アルゴリズムクイックリファレンス 第2版

by George T. Heineman, Gary Pollice, Stanley Selkow, 黒川 利明, 黒川 洋

実用上、本当に速いコードを書くにはまず正しいアルゴリズムの選択から。本書は実践的側面を重視した、新しいタイプのアルゴリズム事典です。どのアルゴリズムを使うべきか、どう実装するのか、さらに性能を向上させる方法はあるのかを解説。主要な40余りのアルゴリズムを網羅し、C、C++、Java、Pythonでの実装例を示します。改訂版では、フォーチュンアルゴリズム、マージソート、マルチスレッドクイックソート、AVL平衡二分木、R木と四分木などの新たなアルゴリズムを追加。実際にベンチマークを取る手法も紹介した実際的、実践的な一冊です。