大データストレージコースノート

第一章

産生背景

水平スケーリング；より多くのノードを使用してより多くのリクエストをサポートします。

垂直スケーリング；1つのノードの能力を拡張してより多くのリクエストをサポートします。

大データの特徴：volume，velocity，variety，value

水平スケーリングのニーズ、システムの信頼性と可用性、一貫性のニーズは従来のリレーショナルモデルでは効果的に解決できません

大データに必要なストレージ

大データストレージのクラスターシステムは、次の要件を満たす必要があります：

1. クラスター内のコンピュータおよびストレージリソースを統一的に管理、スケジュール、監視できる
2. クラスター内のデータを分散ストレージおよび統一管理できる
3. クラスター内のコンピュータが共同でタスクを完了でき、分業協力、負荷分散を行う
4. クラスター内のあるコンピュータが故障した場合、クラスターは機能の有効性を保証し、データが失われない（パーティション耐障害性）
5. 簡単な方法でクラスターをデプロイ、拡張し、故障ノードを置き換えることができる（スケーラビリティ）

技術分類

• メタ情報管理方式による分類： ピアノードの戦略、中央ノードの束縛がないため、より高い可用性を持つ。 中央ノードの戦略、より良いスケーラビリティ。
• データモデルによる分類： 異なるビジネスモデルに対応する異なるデータモデルのデータベース
• 分散型アーキテクチャ Partition All -分庫分表

Partition Engine -Share Nothing

Partition Storage -Share Storage 存算分离

NoSQLとnewSQL

NoSQLは非リレーショナルデータベースで、主にSQLのスケーラビリティ問題を解決するために使用されます。ACID特性を保証せず、トランザクション管理がなく、余分な操作なしで水平スケーリングが可能です；

NewSQLはリレーショナルデータベースで、Nosqlデータベースの大規模ストレージ管理能力とリレーショナルデータベースのACID特性とSQLの利便性を兼ね備えています。

第二章

C/Sベースの階層構造

APとDP

APはユーザー向けのアプリケーションプロセッサで、データ処理を完了するためのソフトウェアであり、CMにユーザーのリクエストとデータを伝えることができます。

DPはデータプロセッサで、データ管理を担当し、集中型データベース管理システムに似ており、CMからのコマンドとデータを受け取り、フィードバックを提供します。

AP機能の変化

集中庫 -データを保存せず、入力に相当し、ホストがすべてのソフトウェアを実行

多クライアント/単一サーバー -アプリケーション、クライアントサービス（クエリ）、通信

多クライアント/多サーバー -アプリケーション、クライアントサービス（ディレクトリ管理、キャッシュ管理、クエリ処理、コミットプロトコル）、通信

シンクライアント/サーバー -クライアントServer2Sever 上記の機能をサーバーに移し、SQLインターフェースとプログラムインターフェースのみを保持；APは計算関連の内容：ディレクトリ管理、キャッシュ管理、クエリ処理、トランザクション処理、ロック管理、アクセス制御。さらに、サーバー側にはストレージ関連の機能：ログリプレイ、障害復旧、インデックス設計、物理ストレージがあります。

三つのアーキテクチャ

個人的な理解であり、正確性は保証できません。 参考記事

1. Server-to-serverシンクライアント/サーバーアーキテクチャに基づいてこれらの3つの分散型アーキテクチャを議論
2. サーバー-検索エンジン -クエリ、最適化、抽出；並行制御；トランザクションコミット； engine-トランザクション部分（復旧に対するもので、ログが必要で、状態を持つ）、インデックス、ログ、障害復旧、物理ストレージの部分
3. 三つのアーキテクチャの定義
4. 各部分のスケーラビリティと互換性の特徴

三つのアーキテクチャの本質は、newSQLがSQLの強い一貫性、トランザクションサポートとNoSQLの容易なスケーラビリティを兼ね備えたいという異なる実現方法ですが、スケーラビリティと互換性の綱引き競争に陥っています。

上から下へ、順にPartition ALL(分庫分表)，Partition Engine(share nothing)，Partition Storage（存算分离)；上から下へスケーラビリティが低下し、エコシステムの互換性が向上します。 分庫分表はスケーラビリティが非常に優れており、パフォーマンスが高い；しかし、ビジネス結合が大きく、通常はビジネスシーンに基づいて設計する必要があり、ユーザー自身が分片戦略、分散型トランザクション、分散型クエリを処理する必要があり、汎用性が低い。各ノードは完全なDBMSです。 Share Nothingはエンジン層でのみ分片を行い、ノード間は相対的に独立しています。従来の分庫分表に比べて、分散型トランザクションと分散型クエリなどの問題をデータベース内部で処理し、ユーザーに分散型トランザクションなどの詳細を隠し、統一されたデータベースサービスを提供し、ユーザーの使用を簡素化しました。

困ったことに、ほとんどの分庫分表の実装もミドルウェア（データ処理、データ管理、負荷分散、データベース駆動）の導入を通じて分散型トランザクションなどの実装の詳細を隠し、同様にMulti Paxosのような一貫性プロトコルを採用してレプリカの一貫性を保証し、ユーザーに統一されたデータベースアクセスを提供します。したがって、Partition Engineの戦略の優位性はあまり大きくないようです。

分片の境界線をトランザクションおよびインデックスシステムの下層に移動し続けます。この時点で、Part 1部分は完全なトランザクションシステムを保持しており、無状態ではなく、通常はサービスを処理するために独立したノードを保持します。このようにして、Part 1は主に計算関連のロジックを保持し、Part 2はストレージ関連のREDO、ダーティページのフラッシュ、および障害復旧を担当します。この構造は、計算ストレージ分離アーキテクチャとも呼ばれ、Share Storageアーキテクチャとも呼ばれます。

完全な計算層を保持しているため、従来のデータベースがユーザーに感知させる必要がある変化が非常に少なく、より大きな程度でエコシステムの互換性を実現できます。同時に、ストレージ層のみが分片と分散を行っているため、スケーラビリティは上記の2つのソリューションほどではありません。

DDBSのコンポーネント構造

– アプリケーションプロセッサ（AP）機能：

ユーザーインターフェース：ユーザーの身元を確認し、ユーザーコマンド（例：SQL）を受け取る

セマンティックデータコントローラー：いくつかの制約（ビュー管理、セキュリティ制御、セマンティック整合性制御）

グローバルクエリプロセッサ：ユーザーコマンドをデータベースコマンドに翻訳する；グローバルクエリプランを生成する；ローカルクエリ結果を収集してユーザーに返す

グローバル実行モニター（グローバルトランザクションマネージャー）：APとDPをスケジュールおよび監視する；複製データの一貫性を保証する；グローバルトランザクションの原子性を保証する

– データプロセッサ（DP）機能：

ローカルクエリプロセッサ：グローバルコマンド —> ローカルコマンド；最良のアクセスパスを選択して実行する

ローカルトランザクションマネージャー：ローカルサブトランザクション単位でスケジュール実行

ローカルスケジュールマネージャー：ローカルサイトでの並行制御を担当する

ローカルリカバリーマネージャー：ローカルデータベースの一貫性を維持する障害復旧

ストレージマネージャー：データベースにアクセスする；データベースキャッシュマネージャーを制御する；ローカル実行結果を返す

DDBSのモード構造

• グローバル外部モード(GES): グローバル外部モードはグローバルユーザービューであり、分散型データベースのグローバルユーザーに対する分散型データベースの最高層の抽象です。
• グローバル概念モード(GCS): グローバル概念モードはグローバル概念ビューであり、分散型データベースの全体的な抽象であり、すべてのデータ特性と論理構造を含みます。グローバル概念モードは分片モードと配分モードを通じてローカル概念モードにマッピングされます。
• 分片モードはグローバルデータの論理分割ビューを記述します。つまり、グローバルデータ論理構造を特定の条件に基づいて分割し、グローバルデータ論理構造をローカルデータ論理構造に分割します。各論理分割は1つの分片と呼ばれます。リレーショナルデータベースでは、1つのリレーション内の1つのサブリレーションはそのリレーションの1つのフラグメントと呼ばれます。
• 配分モードはローカルデータ論理のローカル物理構造を記述し、つまり分割された分片の物理配分ビューです。
• ローカル概念モード(LCS) ：ローカル概念モードはローカル概念ビューであり、グローバル概念モードのサブセットです。ローカル概念モードはローカルサイト上のローカルデータ論理構造を記述するために使用されます。グローバルデータモデルとローカルデータモデルが異なる場合、データモデル変換などの内容も含まれます。
• ローカル内部モード(LIS) ：ローカル物理ビューを定義し、物理データベースの記述であり、集中型データベースの内部層に似ています。

DDBSのデータ透明性

• 分片透明性：分片は1つのリレーションをいくつかのサブリレーションに分割し、各サブリレーションは1つの分片と呼ばれます。ユーザーがデータがどの分片に属するかを考慮する必要がない性質を分片透明性と呼びます。グローバル概念モードと分片モードの間に位置します。
• 配分透明性：分散型データベースは制御されたデータ冗長性をサポートし、つまりデータを異なるサイトに繰り返し保存できます。ユーザーが各フラグメントの保存サイトを考慮する必要がない性質を配分透明性と呼びます。分片モードと配分モードの間に位置します。
• ローカルマッピング透明性：ユーザーがデータのローカルストレージ形式を考慮する必要がない性質をローカルマッピング透明性と呼びます。配分モードとローカル概念モードの間に位置します。

1
2
3
4

select . from S --分片透明性
select . from S1 & S2 --配分透明性
select . from S1 at site1 --ローカルマッピング透明性
Execute:$SUPIMS($SNO,$FOUND,$SNAME) at L1 --不透明

MDBS V.S. DDBS 4点

分散型データベースシステム：上から下へ(top-down) データベースを設計し、分片と配分設計を柔軟に行うことができます。しかし、分散型データベースシステムはデータベースコンポーネントの数に制限があり、通常は数十のデータベースコンポーネントを超えません。

多データベース統合システム：データとデータベースは既に存在し、下から上へ(bottom-up) 各ローカルサイトのデータを統合します。データ統合システムはデータ管理能力を制約することで（読み取りのみをサポート）、データベースコンポーネントの数を数百に拡張できます。

どちらもユーザーに統一されたデータアクセス環境を提供する必要がありますが、データは分散して保存されます。違いは次のとおりです：

• データモードが事前に定義されているかどうか
• DBMSが同構かどうか
• クエリ最適化戦略が自動生成されるかどうか
• ローカルユーザーが必ず存在するかどうか（MDBSは）

第三章

3.1 分散型データベース設計（分片，配分，複製）

3.1.1 設計の戦略とステップ

トップダウン、ニーズ分析->概念設計->分布設計->物理設計->パフォーマンス調整

3.1.2 分片の定義と役割

分片（Fragmentation)：グローバルデータの論理分割。

配分（Allocation）：フラグメントの保存サイトの指定を配分と呼びます。フラグメントが1つ以上のサイトに保存される場合、データ複製（Replication）と呼ばれます。各フラグメントが1つのサイトにのみ保存される場合、データ分割（Partition）保存と呼ばれます。

分片の役割：

• ネットワーク伝送データ量を減少させる
• トランザクション処理の局所性を増大させる
• データのクエリ効率とシステム信頼性を向上させる
• 負荷を均等にする 分片プロセスはグローバルデータを論理的に分割し、実際の物理配分を行うプロセスです。グローバルデータは分片モードによって各フラグメントデータに定義され、各フラグメントデータは配分モードによって各サイトに保存されます。

分片の原則：完備性（データが失われない）、可再構成性（リレーションが失われない）、非交差性（形式的な記述）

分片の種類：水平分片（元組による）、垂直分片（属性による）、混合分片

3.1.3 水平分片

水平分片：選択

導出式：半結合

設計は分片のニーズ情報に基づいており、アプリケーション要因とデータベース要因からのものです

設計基準：完備性と最小性を持つ一組の単純な述語集合を定義する

3.1.4 垂直分片

分片表現：射影演算

完備性の証明：和演算（属性）

可再構成性の証明：結合演算

非交差性の証明：交差演算、結果が空でない場合、主キー

3.1.5 分片の表現方法

グラフィカル表現法（表）とツリー表現法

3.1.6 配分設計

フラグメントを物理サイトに保存するマッピングプロセスを配分設計プロセスと呼びます。

• 非複製配分 各フラグメントが1つのサイトにのみ保存される場合、分割式分布と呼ばれ、対応する分布庫は全分割式分布庫と呼ばれます。
• 複製配分 各フラグメントが各サイトに副本を持つ場合、全複製配分と呼ばれ、対応する分布庫は全複製分布庫と呼ばれます。 各フラグメントが一部のサイトにのみ副本を持つ場合、部分複製配分と呼ばれ、対応する分布庫は部分複製分布庫と呼ばれます。

3.1.7 データ複製技術

同期複製と非同期複製；マスタースレーブ複製と対等複製；

3.2 分散型クエリ最適化

(重要なステップを示し、分片を展開するなど、∪は二項演算、空の円)

3.2.1 クエリ最適化の意義

3.2.2 クエリプロセッサ

3.2.3 クエリ分解

グローバル概念モードに基づいて演算クエリを代数クエリに分解します。グローバル論理クエリプランツリーを取得します。以下の5ステップ：

1. クエリの正規化（交換律結合法則分配法則）
2. 構文および意味解析（構文エラー、無意味なクエリ、無権限、クエリグラフを通じて）
3. クエリの簡約
4. クエリの書き換え

3.2.4 データの局所化

• グローバルテーブルを使用して和演算と結合演算を利用してローカルテーブルに分解します
• グローバルツリーを描画し、グローバルツリーを最適化し、フラグメントクエリツリーに変換します
• 選択演算、結合演算を即座に空にし、∞を∪の前に下げて実行します（分配法則を利用）

3.2.5 フラグメントクエリの最適化

3.3 分散型アクセス最適化

3.3.1 基本概念

3.3.2 最適化の理論的基礎

リレーションの基： リレーションRが含むタプルの数、Card(R)と記します

• 属性の長さ：属性Aが定義する値のバイト数、Length(A)と記します • タプルの長さ：リレーションRの各タプルのバイト数、Length(R)と記します

Length(R)=∑Length(Ai) • リレーションのサイズ：リレーションRが含むバイト数、Size(R)と記します Size(R)=Card(R) Length(R) • 属性Aの特性値：リレーションRの属性Aが取る異なる属性値の数、 Val(A)と記します • 属性Aの最大値と最小値：Max(A)とMin(A)と記します

選択演算： 基数：Card（S）=ρ Card（R）* ρの計算：選択属性A条件の等値の場合のみ考慮**、AはRの属性で、Xは定数です。 その場合$\rho = \frac{1}{Val(R,A)}$

Val(S,B)の計算： 属性Bが選択条件に含まれる場合、Val(S,B)=1 属性Bがキー（主キー）の場合、Val(S,B)=ρ Val(R,B) 属性Bが選択述語に含まれない場合、 $$Val(S,B)=\begin{cases} Card(S), \quad if \quad Card(S) <= \frac{Val(R,B)}{2} \ \frac{Card(S)+Val(R,B)}{3} \ Val(R,B), \quad if \quad Card(S)>=2Val(R,B) \end{cases}$$

結合演算：

半結合演算：

3.3.3 半結合最適化方法

この一周を見て、半結合が全結合よりも多くの代価を払っているかどうかを確認します。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

課題一 分片設計
ある商品ショッピングシステムが存在し、システムには2つのグローバルリレーションがあります：ユーザーテーブルUSER(UID，UNAME，ADDRESS，HOBBY，CITY) と注文テーブルORDER(UID，PID，PRICE) ，UIDはユーザー番号、UNAMEはユーザー名、CITYは所在都市です。PIDは商品番号、PRICEは注文総額で、UIDはUSERテーブルで主キー、ORDERテーブルで外部キーです。分散型データベースを構築するために、分片のルールは次のとおりです：
（1）リレーションUSERは属性の感度に基づいて垂直分片
U1は非感度属性を含む：UID，UNAME，CITY
U2は感度属性を含む：ADDRESS，HOBBY
（2）USERのすべての非感度属性はCITYに基づいて水平分片
U11：CITY IN { 北京，上海，广州，深圳}
U12：CITY NOT IN { 北京，上海，广州，深圳}
（3）リレーションORDERはUSERとの結合関係に基づいて分片され、O1とO2が得られます。

課題二 クエリ最適化
クエリQ： “徐州市のユーザーが商品番号「P1」を購入したすべての注文をクエリし、注文内のユーザー番号、ユーザー名、商品番号、注文総額を取得します” 。
（1）クエリQのリレーション代数式を書き、フラグメントクエリに変換します
（2）フラグメントクエリツリーを最適化します

課題三 アクセス最適化
以下の図

第四章 HBase

HDFSの問題

1. データのランダムな改変をサポートしていない
2. HDFSにはデータパケットの概念がない
3. HDFSは行数の統計、フィルタリングスキャンなどの一般的なデータクエリ機能に対して迅速な操作を実現できず、通常はMapreduceを通じて実現する必要があります。
4. （利点は大ファイルの保存、多重副本、自動分割）

HBaseの特徴

1. 底層はHDFSストレージを採用していますが、ファイル構造とメタデータは独自に管理されています。
2. 列+キー値ペアのストレージモードを採用しています
3. 簡単な横方向のスケーリングを実現できます
4. 自動的なデータ分片を実現できます
5. 厳格な読み書きの一貫性と自動障害転送を持っています
6. 全文の検索とフィルタリングに対応しています 利点は大量のデータの書き込みに優れ、高性能、高信頼性、スケーラビリティを持っています；欠点はテーブルの関連クエリ分析をサポートしていないことです。

Region

Region serverはRegionを保存するコンテナです；Regionはテーブルのデータの一部であり、1つのRegionはリレーショナルデータベースのテーブルの1つの分片に相当します。1つのテーブルは異なるRegionに保存される可能性があります。 特徴：

1. Regionはサーバーを跨ぐことができず、1つのRegion Serverには1つ以上のRegionがあります;
2. データ量が増加すると、Regionは分裂します；
3. 負荷分散の必要性から、Regionは移動します；
4. Regionのすべてのデータアクセス操作はHDFSのクライアントインターフェースを呼び出して実現されます。

同じテーブルの異なる行のデータは異なるサーバーに保存されることができ、同じテーブルの同じ行のデータも異なるサーバーに保存されることができます。この文はどのように理解しますか？(私は理解できません、後半の文に問題があると思います。) 1つのサーバーはRegionのストレージ機構ですが、1つのRegionを保存することは1つのテーブルを保存することを意味しません；各RegionにはいくつかのStoreが含まれており、1つのStoreは1つの列族に対応し、列族をオブジェクトとして保存します。必ずしも1つのテーブルではなく、異なるテーブルの分片である可能性があります。

事前書き込みログWAL:最初にWALに書き込みます（1つのRegionserverには1つのWALがあります）、memStoreにロードします；

各region内部には複数のstoreインスタンスがあり、各storeは1つの列族に対応しています；各storeには1つのmemStoreインスタンスがあり、memStoreが満たされると、HDFSは新しいHFileを生成します（LSMツリーを使用して保存し、最終的な書き込み前にクイックソートを行い、ランダムに書き込まれたデータを順序的に保存し、読み取り効率を向上させます）；memStoreはメモリ内のキャッシュと見なすことができ、読み書きに関係なく、最初にmemStoreを確認します。

増削改操作

• HBaseの新しいセルを追加する場合、HDFSに1つのデータを追加します
• HBaseのセルを変更する場合、HDFSに1つのデータを追加しますが、バージョン番号は以前よりも大きくなります
• HBaseのセルを削除する場合、HDFSに1つのデータを追加しますが、このデータには値がなく、タイプはDeleteであり、墓碑マーク（Tombstone）です。HFileのマージ時にこれらのレコードが実際に削除されます。

読み書きフロー

参考記事：HBase読み書きフロー Zookeeper(ROOT)->RegionServer(META)->Region->memStoore

1. クライアントがアクセスし、zookeeperの/hbase/meta-region-serverノードをクエリして、どのRegionServerにhbase：metaテーブルがあるかを確認します

2. クライアントがhbase: metaテーブルを含むregionserverに接続します。Hbase: metaテーブルはすべてのReginの行キー範囲情報を保存しており、このテーブルを通じてリクエスト行キーがどのRegionにあるか、およびそのRegionがどのRegionServerにあるかをクエリできます

3. クライアントが対応するRegionServerで、最初にMemStoreから、次にHFileから必要な情報を探します。

4. 初回アクセス後、クライアントはmeta情報をキャッシュ（BlockCache）し、次回の操作では直接BlockCacheからmeta情報を検索します。

5. クライアントがアクセスし、zookeeperの/hbase/meta-region-serverノードをクエリして、どのRegionServerにhbase：metaテーブルがあるかを確認します

6. クライアントがhbase: metaテーブルを含むregionserverに接続します。Hbase: metaテーブルはすべてのReginの行キー範囲情報を保存しており、このテーブルを通じてリクエスト行キーがどのRegionにあるか、およびそのRegionがどのRegionServerにあるかをクエリできます

7. クライアントが対応するRegionServerで、データをそれぞれHlogとmemstoreに書き込みます

8. memstoreがしきい値に達すると、データをHFIleファイルにフラッシュし、compact後、ますます大きなHFIleが形成されるとspiltがトリガーされ、現在のHFIleを2つに分割し、これは大きなregionを2つのregionに分割することに相当します

9. MemStoreのデータが失われた場合、HLogから復旧できます。複数のHFIleファイルが一定のサイズに達すると、Compactマージ操作がトリガーされ、1つのHFIleにマージされます。ここでバージョンのマージとデータ削除が同時に行われます

Rowkey設計

• 三原則：長さの原則（短いほど良い）、ハッシュの原則（データが均等に分布）、一意性の原則
• ソルト付け（salting）、rowkeyの前にランダムな数を割り当てます；ランダムなプレフィックスはそれらを異なるRegionに分配することができます。
• 予分割、Regionの自動分割によるホットスポット問題と分割マージ問題を解決します（拡張を予約することもできます）；たとえば、0-499のランダムな数を生成し、0-50、50-100…などのRegionの範囲を規定します。
• ハッシュ、同じユーザーが同じ日にデータを集中して保存する必要がある場合の解決策；特定のパラメータ（例：uid、date）をハッシュに渡し、結果を500で割った余りを先頭に追加し、予分割と組み合わせることで、ニーズを満たしながらデータをRegionserverに均等に分配できます。
• 反転、rowkeyの順序性を犠牲にしてランダム性を得る；先頭が固定されていて末尾が変化するホットスポット問題を解決するため、たとえば電話番号；時間（Long.MAX_VALUE - timestamp）を使用して、最近のレコードを優先するニーズを満たします。

第五章 大データインデックス構造

3つの基本的なデータストレージエンジンは、それぞれハッシュ（効率的なランダム検索）、Bツリー（効率的な範囲検索）、LSMツリー（Log-Structured Merge Tree）です。HBaseの1つの列族は1つのLSMツリーであり、メモリ部分はスキップリストであり、外部はブルームフィルターを選択して迅速に判別します。

スキップリスト

スキップリスト（Skip List）は、挿入、削除、検索を効率的に実現できるメモリデータ構造であり、これらの操作の複雑さはすべて$O(logN)$です。

対応するシナリオ：迅速な書き込み、更新コストが低い、範囲クエリをサポート；B+ツリーとの違いは更新コストが低いことであり、大データシナリオに適しています。

スキップリストの構築：

1. 順序付けられたリンクリストを与えます。
2. リンクリストの最大および最小の要素を選択し、他の要素から特定のアルゴリズム（ランダム）に従っていくつかの要素を選び出し、これらの要素で順序付けられたリンクリストを構成します。この新しいリンクリストを1層と呼び、元のリンクリストをその下の層と呼びます。
3. 新しく選ばれた各要素にポインタフィールドを追加し、このポインタは次の層の自分と等しい値を持つ要素を指します。Topポインタはこの層の最初の要素を指します
4. ステップ2、3を繰り返し、最大および最小の要素以外の要素を選び出せなくなるまで続けます。

スキップリストの挿入フロー：

スキップリストに挿入する際、新しいノードは上層にインデックスを生成する一定の確率を持ちます。 挿入する要素の前駆ノードを見つける->挿入->ランダムに高さ値を生成する->高さ値に基づいてインデックスを変更する

LSMツリー

なぜLSMツリーは書き込みに優しいデータ構造と言われるのですか？ LSMツリーは書き込みに優れており、書き込み操作は順序書き込みで行われ、HDFSの利点を活用しています。

1. 順序書き込み：LSMツリーの書き込み操作は順序書き込みの方法で行われます。これは、新しいデータがディスク上の順序ログ（SSTables）に追加され、元のデータファイルに直接書き込まれないためです。従来のランダム書き込み操作と比較して、順序書き込みのコストは小さく、書き込み性能を大幅に向上させることができます。

2. 遅延マージ：LSMツリーのマージ操作は通常遅延実行され、つまり、複数のSSTables間のマージは各書き込み操作の後にすぐに実行されるわけではありません。これにより、書き込み中に頻繁にマージ操作を行うことを避け、書き込みの遅延とコストを削減できます。

3. メモリキャッシュ：LSMツリーは通常、最近書き込まれたデータを保存するためのデータキャッシュエリアをメモリ内に維持します。ハードディスクにフラッシュされても、メモリ内に新しいmemstoreを開いて新しい書き込みに対応します。これにより、各書き込みでディスクにアクセスする必要がなくなり、書き込み性能が向上します。同時に、メモリキャッシュ内のデータも定期的にディスク上のSSTablesにフラッシュされ、データの持続性を保証します。

対応するシナリオ：高スループット（順序）書き込み、ランダム検索、スケーラビリティ（LSMツリーはデータの分割を許可します）。

compaction：同じキー値のデータをグローバルに統合し、適切なバージョンを選択してユーザーに提供します。

主に2つのタイプがあります：

1. major compact：頻繁に使用するのは適していません 利点：マージ後は1つのファイルのみであり、読み取り性能が最高です 欠点：すべてのファイルをマージするには長い時間がかかり、大量の帯域幅を消費します。
2. minor compact： 利点：局所的なcompact操作であり、IOが少なく、ファイルの数を減らし、読み取り性能を向上させます。 欠点：グローバル操作であり、マージプロセス中に完了することはできません。

ブルームフィルター

解決する問題のタイプ：データベースに確実に存在しないデータを効果的に排除します； 実現原理：配列と複数のハッシュ関数を使用して実現します。各データに対してk回ハッシュを行い、各ハッシュ結果に対応する配列の位置を1に設定します；データをクエリする場合、すべてのハッシュ結果が指す位置が1であることがわかれば、そのデータはデータベースに存在する可能性がありますが、そうでない場合は確実にデータベースに存在しません。

なぜHBaseは「順序書き込み、ランダム検索」の分散型データベースと言われるのですか？ ランダム検索：HBaseはLSMツリーのインデックス構造を採用していますが、HBaseのクエリ操作はLSMツリーに基づいて行われるのではなく、HBaseテーブル内の行キー（row key）に基づいて行われます。Regionが組織するメタ情報。

第六章 一貫性

分散型トランザクション

トランザクションはデータベース内の一連の操作であり、すべて実行されるか、まったく実行されないかのいずれかです；開始マーク、操作、終了マーク（commitまたはabort）で構成されます；構造に基づいて平面トランザクション（トランザクションの自治、独立）とネストトランザクション（1つのトランザクションの実行に別のトランザクションが含まれる、内側の子、外側の親）に分けられます；

ネストトランザクションの特徴

• コミット依存性：子トランザクションのコミットは親トランザクションのコミットを待たなければなりません；
• 廃棄依存性：親トランザクションが廃棄されると、子トランザクションも廃棄されなければなりません；

分散型トランザクションの一貫性

この問題は分散型データベースにデータの複製が存在するために発生します（信頼性と可用性ももたらします）； 3つのレベル：

• 強い一貫性：更新されたら即座にアクセス可能
• 最終的な一貫性：しばらくしてからアクセス可能
• 弱い一貫性：アクセス不可（オンラインショッピングのレビュー、広告）

CAP

分散型システムは一貫性、可用性、パーティション耐障害性を同時に満たすことはできず、最大で2つしか満たせません；

• 一貫性はデータが複数のレプリカ間で一貫性を保つ特性です；
• 可用性は提供されるサービスが常に利用可能な状態であることを意味し、有限時間内に結果を返すことを意味します；
• パーティション耐障害性は、ネットワークパーティションに直面したときに、可用性と一貫性を保証するサービスを提供することです； たとえば、北京と広州のDBに同時に書き込みが成功した場合にのみ成功を返し、ネットワーク障害時に降格サービスを提供する（アクセス不可）場合、CPを満たします。

BASE

Bascially Available, Soft State, Eventually consistent; CAPの可用性と一貫性のトレードオフの結果です；

障害が発生した場合、一部の可用性の損失を許容します；ソフトステートはデータが不一致の中間状態にあることを許容し、可用性に影響を与えないと考えます；すべてのデータレプリカは一定時間後に最終的に一貫した状態に達することができます；

要するに、BASE理論は大規模で高可用性でスケーラブルな分散型システムを対象としており、従来のトランザクションACID特性とは反対であり、強い一貫性モデルとは異なり、強い一貫性を犠牲にして可用性を得ることを目的としており、データが一定期間不一致であることを許容し、最終的に一貫した状態に達することを許容します。

HBaseのACID特性(理解)

原子性：WALの原子性のみを保証します； 一貫性：強い一貫性；

2PC（重点）

分散型データベースのグローバルトランザクションは、各サイトで実行されるサブトランザクションに分解されます。すべてのサイトでサブトランザクションが正しく実行された場合にのみ、グローバルトランザクションをコミットできます。少なくとも1つのサブトランザクションがコミットできない場合、グローバルトランザクションは廃棄され、次にすべてのサブトランザクションもすべて廃棄されるべきです。したがって、すべてのサブトランザクションが正しくコミットできることが分散型トランザクションコミットの前提です。

実行フロー

決定フェーズ：コーディネーターがプレコミット（prepare）コマンドを送信し、参加者の応答を待ちます。すべての参加者が「コミット準備完了（ready）」を返した場合、コーディネーターはコミットの決定を行います；少なくとも1つの参加者が「廃棄準備完了」を返した場合、コーディネーターは廃棄の決定を行います。

実行フェーズ：コーディネーターは決定フェーズで行った決定を参加者に送信します。コーディネーターが各参加者に「コミット」（Commit）コマンドを送信した場合、各参加者はコミットを実行します；コーディネーターが各参加者に「廃棄」（Abort）コマンドを送信した場合、各参加者は廃棄を実行し、データベースの変更をキャンセルします。「コミット」または「廃棄」のいずれかが完了した後、各参加者はコーディネーターに「確認」（Ack）応答を返し、実行が終了したことを通知します。

存在する問題

同期ブロッキング、単一障害点、データ不一致、過度に保守的

コーディネーターが故障すると、参加者はリソースを占有しているがトランザクションを実行できず、ブロック状態に入ります；三段階コミットプロトコルを使用して回避できますが、すでにブロックされている場合は終結プロトコルを使用して回復します。

ステップ1：参加者PTを新しいコーディネーターとして選択します。

ステップ2：PTがすべての参加者に「状態アクセス」コマンドを送信し、各参加者が自身の状態を返します。

ステップ3：PTは各参加者の現在の状態に基づいて決定を行います：

1. 一部の参加者が「初期」状態にあり、一部の参加者が「準備完了」状態にある場合、PTはabortコマンドを送信します；
2. すべての参加者が「準備完了」状態にある場合、PTはCommitコマンドを送信します；
3. 少なくとも1つの参加者が「コミット」状態にある場合、PTはCommitコマンドを送信します；
4. 少なくとも1つの参加者が「廃棄」状態にある場合、PTはabortコマンドを送信します；

Paxos

Prepare->Accept->Learn Proposer,Accepter,Learner

第七章 並行制御

目的

並行制御の主な目的はトランザクションの隔離性を保証し、最終的にデータの一貫性を保証することです；並行によって引き起こされる修正の喪失、再現性のない読み取り、汚れたデータの読み取りの問題を解決します；並行制御は正しい方法で並行操作シーケンスをスケジュールし、データの不一致を回避します；1つのトランザクションの実行が他のトランザクションの干渉を受けないようにし、トランザクションの並行実行の可直列化性を保証します。

可直列化

1つのトランザクションの最後の操作が別のトランザクションの前にある場合、またはその逆の場合、それは直列スケジュールです。 等価判定：競合操作の順序が一致する

可直列化：直列スケジュールと等価 分散型トランザクションの可直列化： n個のトランザクションがm個のサイトでの並行シーケンスとして記録され、Eとします； 各サイトのローカルスケジュールが可直列化可能であるかつ総シーケンスで$T_{i}<T_{j}$がある場合、各ローカルスケジュールでもこの関係がある必要があります。

1
2
3
4
5

データ項目a，bがS1サイトに保存され、x，yがS2サイトに保存されているとします。分散型トランザクションT1とT2があり、以下の各実行がローカル可直列化可能かどうか、全体的に可直列化可能かどうかを判断し、それぞれ理由を説明します。
1、実行1：S 1サイトでR 1(a) R 2(a) W 2(b) W 1(a) 、
		S 2サイトでR 1(x) W 1(x) R 2(y) W 2(x) 、
2、実行2：S 1サイトでR 1(a) R 2(a) W 1(a) W 2(b) 
		S 2サイトでW 2(x) R 1(x) R 2(y) W 1(x) 。

分散型並行制御

分散型データベースの並行制御は、分散型データベースシステムでデータの一貫性と完全性を保証し、ユーザーの並行アクセスのニーズを満たすために、特定の技術手段を使用して並行アクセスを制御するプロセスです。主に以下の問題を解決します：

1. データの一貫性の問題：分散環境では、データが複数のノードに分散している可能性があるため、複数のノード間のデータの一貫性を保証し、データの競合や不一致の問題を回避する必要があります。

2. 並行制御の問題：複数のユーザーが同時に同じデータに対して読み書き操作を行う可能性があるため、並行制御戦略を採用してデータの正確性と完全性を保証し、同時にシステムの並行処理能力を最大限に発揮する必要があります。

三つの典型的な分散型ロック

データベース(MySQL)方式：ロック用のテーブルを使用し、リソースIDを主キーとして挿入し、ロック解除は削除します；

Redis分散型ロック：setnx，setnxはset if not existsの略です；keyが存在しない場合、keyの値をvalueに設定します；keyが存在する場合、何も操作しません。ロック解除はdel keyです；

Zookeeper分散型ロック：ロック管理用のディレクトリを作成し、ロックをかける際にそのディレクトリに一時的な順序ノードを作成し、順序番号が最小の場合にロックを取得し、そうでない場合はディレクトリを監視して待機します；ロック解除はノードを削除します；

比較：

• 理解の難易度の観点から（低から高へ）データベース > キャッシュ >Zookeeper
• パフォーマンスの観点から（高から低へ）キャッシュ > Zookeeper >= データベース
• 信頼性の観点から（高から低へ）Zookeeper > キャッシュ > データベース