ブログ@nnaka2992

データベースってなんだよ

YugabyteDBのドキュメントを全部読む Day4

DB 論文

前回からつづいてYugabyteDBのドキュメントを読んでいきます。

前回はArchitecture > Key Concepts > YB-TServer serviceを読みました。 今回はArchitecture > Key Concepts > YB-Master serviceを読みます。

ドキュメントのバージョンは最新のv2.19 previewです。 また画像は同ドキュメントより引用しています。

YB-Master service

YB-Masterサービスはテーブルやそのタブレットの場所、ユーザー・ロールの権限といったシステムのメタデータとレコードの管理を行っている。

それに加えYB-Masterはロードバランシングやレプリケーションの開始といったバックグラウンドオペレーションの管理や、テーブルのCREATEや ALTER、DROPといった様々な管理オペレーションの責任を持つ。

YB-MasterはRaft Groupを組むことで高可用性を実現し、またテーブルに対するI/Oの単一障害点にならない。

master_overview

Functions of YB-Master

YB-Masterはシステムの重要な機能を複数持っている。

Coordination of universe-wide administrative operations

CREATE TABLEやALTER TABLE、DROP TABLEといったユーザーからのリクエスト処理やバックアップの実行などUniverseをまたぐ オペレーション実行の調整を担当している。

YB-Masterではこれらのオペレーションがテーブルを保持するYB-TServerの状態に関わらず、全てのテーブルに伝搬されることを保証する。

YugabyteDBは分散システムのため、Universeをまたぐ処理中にYB-TServerに障害が発生し一部のタブレットへの適用に失敗してもオペレーションの 結果に問題が発生しないことが重要だからである。

Storage of system metadata

それぞれのYB-Masterではネームスペースやテーブル、ロール、パーミッション、YB-TServerへ割り当てたテーブル情報を含む システムメタデータを保存している。

これらのシステムレコードはYB-Masterを対象にRaftグループを組みレプリケーションすることで冗長性を実現している。 またシステムレコードはYB-Masterが管理するDocDBに保存される。

Authoritative source of tablet assignments to YB-TServers

YB-Masterは全てのテーブルとそれらをホストするYB-TServerの情報を保存している。

一般のクライアントではそれらの情報はクライアントからクエリレイヤなどを通して取得された上で、クライアントにメタデータを返し データアクセスが行なわれる。 一方でスマートクライアントではYB-Masterに保存されたメタデータを利用して特定のYB-TServerが保持するタブレットやキャッシュを利用 することが出来るため、データアクセス時のネットワークをまたぐ通信を減らすことができパフォーマンスを高めることができる。

Background operations

いくつかのオペレーションはUniverseのライフタイムを通してバックグラウンドで行なうことで、フォアグラウンドのRead/Writeに 影響を与えずに実行することが出来る。

  1. Data placement and load balancing YB-MasterのリーダーはCREATE TABLE時にタブレットの初期配置をYB-TServerをまたいで行なう。そのときにユーザー定義の データ配置制約を強制し均一な読み込みを保証する。
    それに加えUniverseのライフタイム中のノード追加や障害が発生しても、負荷分散を継続しデータ配置の制約を自動的に適用する。

  2. Leader balancing 複数のYB-TServerに配置されたタブレットへのアクセスがUniverseをまたいで分散されることを保証している一方で、 YB-Masterは対象となるノード1間でそれぞれのノードが同じ数のtablet-peer leader2をもつことを保証する。

  3. Rereplication of data on extended YB-TServer failure YB-Masterは全てのYB-TServerからハードビートシグナルを受け取ることでYB-TServerの死活監視を行なっている。 そしてYB-MasterはYB-TServerの異常を検知したときに、どれぐらいのあいだYB-TServerが異常であったかを追跡する。
    異常であった時間が閾値を超えると、YB-Masterは障害中のYB-TServerに配置されていたタブレットを再配置するYB-TServerを探し、 レプリケーションを実行する。
    レプリケーションはYB-Masterリーダーに抑制された状態で実行されるため、Universeのフォアグラウンドオペレーションには影響をおよぼさない。

  1. Raft Groupのリーダーになれるノード↩
  2. Raft Groupのリーダーのことでいい。はず↩

YugabyteDBのドキュメントを全部読む Day3

DB YugabyteDB

YugabyteDBのドキュメントを全部読む Day3

前回からつづいてYugabyteDBのドキュメントを読んでいきます。

前回はArchitecture > Key Concepts > Universeを読みました。 今回はArchitecture > Key Concepts > YB-TServer serviceを読みます。

ドキュメントのバージョンは最新のv2.19 previewです。 また画像は同ドキュメントより引用しています。

それはそれとして技術系の単語をカタカナ表記で誤魔化していて、体系的に学んでいないことがバレてしまう。特にストレージまわりが分からない……

YB-TServer service

YB-TServer(YugabyteDB Tablet Servcer)はユーザからの受けつけたYugabyteDBクラスタへのリクエストのI/Oの 処理をする。

テーブルのデータは一つ以上のTablet peerに分割(シャーディング)される。peerの数はレプリケーションファクターによって決定される。

YB-TServerは一つ以上のTablet peerをホストする。 tserver_overview

Tablet peerはRaftグループを形成してグループ間でデータの複製を行ない、タブレットはYB-TServer上で最大の効率になるように管理される。

Server-global block cache

ブロックキャッシュは一つTB-TServer上の異なるタブレット間で共有される。

YB-TServerのメモリ効率は一つのテーブルからの読み込みが多いほど最適化される。

Space Amplification

YugabyteDBではSize-tired Compactionというライトアンプリフィケーション1が小さい圧縮方式を利用している。

Size-tired Compactionはスペースアンプリフィケーション2が大きいという問題があるが、 YugabyteDBではテーブルは複数のタブレットに分割され、タブレット間でのConcurrent Compactionは特定の最大値まで絞られるため問題になりにくい。

YugabyteDBでは凡そ10-20%のスペースアンプリフィケーションにおさまる。

つまりSize-tired Compaction一単位が扱うデータ量を小さく(タブレット化)して、 同時に実行される圧縮処理数を絞ることで特定のタイミングで圧縮に使用されるストレージ容量を抑えているということ？

Throttled compactions

YB-TServerではタブレット間で実行される圧縮処理の同時実行数を制限することで、圧縮処理が多量のリソースを占有することを防いでいる。

この機能は圧縮されるファイル同士のサイズを比べ、実行される圧縮処理が妥当であることを確認することで実現されている。

Small and large compaction queues

YB-TServerでは圧縮処理を大きい圧縮処理と小さい圧縮処理に分けて優先度を決めることで、I/Oが大きな場合でもシステムの機能を保っている。

YugabyteDBでは圧縮処理数を制限することに加え、様々な最適化を実行することで圧縮処理の影響を最小化している。

Manual compaction

YugabyteDBではyb-admin utilityのcompact_tableコマンドにより、 任意のタイミングでテーブルに対して圧縮を実行することが出来る。

この方法はデータが新しく書き込まれない場合や、DDLやTTLの超過によるデータ削除時によりデータが断片化したときに有効である。

Statistics-based full compactions to improve read performance

YugabyteDBでは読み込まれたkey-valueペアをDocDBレベルで監視している。監視対象となる時間軸はauto-compact-stat-window-secondsで管理されている。

YugabyteDBがデータ読み込み時に多量の廃棄されたデータのスキップを検知した場合、full compactionがトリガーされ不要なキーの削除が行なわれる。

Full compactionがトリガーされる詳細な条件は対象の時間軸で以下が満された時である。

この機能はTTLを設定したテーブルと互換性があり、TTL file expirationが有効なテーブルではスケジュールされた圧縮を実行しない。

Scheduled full compactions

YugabyteDBでは全てのデータに対するデータ圧縮をスケジュール実行することが出来る。 スケジュール実行はscheduled-full-compaction-frequency-hoursと scheduled-full-compaction-jitter-factor-percentageのフラグで管理される。

この機能は大量のDELETEとUPDATEを定常的に実行するワークロードでのパフォーマンスとディスクスペースの再割り当てに有効である。

スケジュール化したデータ圧縮はTTLと互換しているが、TTL file expirationとは互換していない。 つまりスケジュールされた圧縮は実行されない。

Server-global memstore limit

Server-global memstore limitは一つのYB-TServer上のタブレット間でシェアされるメモリサイズを追跡し、強制する。

この機能はタブレット間の書き込みに偏りがある場合に有効である。

一つのテーブルに書き込みが集中しているばあい、メモリ制限以上のメモリを割り当てることでパフォーマンスを向上させることが出来る。

Auto-sizing of block cache and memstore

Block Cacheとmemstoreは何れも多量のメモリを使用している。

これらはtablet-peer間で共有されるリソースのため、メモリ管理とこれらのコンポーネントの様々な環境に合せたサイジングを容易にしている。

YB-TServerでは自動で特定の割合のメモリをBlock CacheとMemstoreに割り当てる。

Distributing tablet load uniformly across data disks

複数のSSDを利用するハードウェアでは、テーブルのデータ(SSTable)とWALはテーブル毎に利用可能なディスクに均等に分散される。 このストライピングと呼ばれる負荷分散は、それぞれのディスクがそれぞれのテーブルの負荷を均等に処理することを保証する。

  1. SSDで実際に書き込んだデータより書き込み量が増幅する現象。もちろんライトアンプリフィケーションが小さいほうが望ましい。↩
  2. データの断片化やデータの重複などにより、ディスクに保存されるデータが実際より大きくなる現象。もちろんスペースアンプリフィケーションが小さいほうが望ましい。↩

YugabyteDBのドキュメントを全部読む Day2

DB YugabyteDB

YugabyteDBのドキュメントを全部読む Day2

前回からつづいてYugabyteDBのドキュメントを読んでいきます。

前回はArchitecture > Design goalsを読みました。 今回はArchitecture > Key Concepts > Universeを読みます。

また画像は同ドキュメントより引用しています。

Universe

YugabyteDBは耐久性とスケーラビリティを兼ねそなえた分散データベースを達成するために、Universe1と呼ばれるノードのグループを持っている。 Universeはビジネス要件やレイテンシの兼ね合いでシングルゾーン、単一リージョンマルチゾーン、マルチリージョン、同期・非同期レプリケーションなどを選択することが出来る。

UnivereはClusterと表現されることもある。

データの構成

Universeは一つ以上のネームスペースを持つことができ、またネームスペースは一つ以上のテーブルを持つことができる。 YugabyteDBではUniverse上に存在するノードにまたがって保持されるテーブルを設定に従って、シャーディングし、レプリケーション、ロードバランシングを行なう。

YugabyteDBはノードやディスク、ゾーンなどに発生した障害に自動で対応し、必要であればデータを新規に分散、レプリケーションを行なう。

  • ネームスペースはYSQLではデータベースに対応し、ほかのDBにおけるネームスペースに対応する2。
  • YCQLではキースペースに対応し、Cassandraのキースペースに対応している。

サービスコンポーネント

UniverseはYugabyteDB Tablet Server(YB-TServer)とYugabyteDB Master Server(YB-Master)の二つで構成されている。 YB-MasterとYB-TServerはRaftにより分散されており、高可用性を達成している。

  • YB-Tserverはテーブルを始めとしたユーザーデータの保存、提供を担当する。
  • YB-Masterはシステムのメタデータを管理し、システム全体のテーブルに対するDDLやメンテナンスの実行、ロードバランシングといったオペレーションを管理する。

NodeとYB-TServer、YB-Masterの関係

UniverseとCluster

Universeは一つのプライマリクラスタとゼロ個以上のレプリカクラスタによって構成されている。

プライマリクラスタ

プライマリクラスタはRead/Write両方の実行と、プライマリクラスタ内のノード間の同期的なレプリケーションを担当する。

リードレプリカクラスタ

リードレプリカクラスタはRead処理のみを実行する。Write処理は自動的にプライマリクラスタにルーティングされる。 リードレプリカクラスタを利用することで、地理的に分散したデータに対する読み取りの遅延を小さくすることができる。 データはプライマリクラスタから非同期的にとりこまれる。これはRaftの書き込みには関与しないRaftオブザーバとして機能する。

  1. GoogleのCloud Spannerでも同様にUniverseと呼ばれている↩
  2. PostgreSQLではSchemaの裏側に存在するデータ構造↩

YugabyteDBのドキュメントを全部読む Day1

DB YugabyteDB

Day1 最近Twitter改めXで「俺はDBのドキュメント端から端まで読んで強くなった」というX's1を複数みかけました。

PostgreSQL系NewSQLで最強になりたいのでYugabyteDBのドキュメントを順番に読んで行きます。 ドキュメントはv2.19に対応したものです。

手始めにArchitectureの一番先頭にあるDesign goalsから読みはじめます。

また画像は同ドキュメントより引用しています。

Design goals

YugabyteDBは以下を達成することを目標としている。 1. 分散トランザクションを提供しながら強い一貫性を保証する。 2. Query APIを再発明せず、既存のクエリ言語への互換を達成する。 3. 高いパフォーマンスを保証する。 4. 地理的に分散したデプロイを可能にする。 5. Cloud Native Databaseとしてデザインする。

一貫性

分断耐性

  • YugabyteDBはCAPの定理で言えばCPを中心に高い可用性を供えたデータベース
  • ネットワーク分断などを起因とするSplit BrainはRaft Group内であたらしいリーダーを選出することで対応している。
  • YugabyteDBではLeader Leaseという障害が発生しても常に一つのリーダが存在することを保証する仕組みを実装している。

直列化可能性

  • single-row Linearizable writeをサポートしている。

ACIDトランザクション

  • YugabyteDBではSeriarizable、Repetable Read、Read Committed Isolationの三つの分離レベルをサポートしている。
  • YSQL APIではこれら3つの分離レベルをサポートしているが、YCQLではRepeatable Readのみに対応している。

Query API

YugabyteDBではYSQLとYCQLという2種類のQuery APIをサポートしている。

YSQL

  • YSQLはPostgreSQLに互換したAPIでPostgreSQLのクエリレイヤを再利用している。
  • 新しい変更は互換性を崩さない。
  • YSQLは新しいPostgreSQLに互換しつづけることを目標としている。

YCQL

  • YCQLはCassandraのクエイ言語から派生した半リレーショナルなクエリ言語で、Webスケールな膨大なwriteに対応してスケールし素早いデータ取得を目標としている。

パフォーマンス

  • C++で実装されているため高いパフォーマンスと巨大なHeap(RAM)をCacheとして利用できる。
  • SSDとNVMeに最適化している。
  • 高いWriteスループットとクライアントの同時実行性、高いデータ密度、増加し続けるデータへの対応を目標としている。

地理的分散

  • Zone、Multi Region、Multi Cloudいずれにも対応している。
  • これに対応するために、ノード障害やトラヒックのルーティングなどに対応できる必要がある。

クラウドネイティブアーキテクチャ

  • パブリッククラウドやオンプレミスで利用される一般てきなハードウェアで利用可能にする。
  • 原子時計のような特別なものに依存しない。
  • Kubernatesに対応している。
  • OSSで提供している。
  1. https://twitter.com/SawyerMerritt/status/1683365478582951936↩

現在のDremelの実装を解説した論文を読みました

CMU_Advanced_Database_Systems DB Dremel/BigQuery 論文

この記事の趣旨

2020年に発表されたBigQueryの元となったGoogle内で利用されている分析向けデータベースであるDremel の実装を解説した論文を読みました。

Dremel: A Decade of Interactive SQL Analysis at Web Scale

著者について

Sergey Melnik, Andrey Gubarev, Jing Jing Long, Geoffrey Romer, Shiva Shivakumar, Matt Tolton, Theo Vassilakisら2010年のDremel発表論文の著者らと、 Hossein Ahmadi, Dan Delorey, Slava Min, Mosha Pasumansky, Jeff ShuteらGoogleで分析ワークロードと 分散処理に関わる著者らによる論文。

概要

BigQueryの元となったGoogleのDremelの10年間を振り替えってアーキテクチャについて説明した論文。 Dremelは現代のクラウドネイティブ分析ツールで一般的になっている、計算リソースとストレージの 分解、カラムナストレージ、in situデータ分析などを統合した最初のツールである。

手法

  1. SQLの採用
    それまでGoogleでは殆どのデータはBigTableなどNoSQLデータベースで管理されていたため、 SQLを用いないデータアクセスが主流であった。 しかしトランザクション型ビッグデータシステムにおける、SQLの採用に共ないDremelでもSQLを採用した。

  2. ストレージの分離
    初期のDremelはシェアードナッシング方式を取っていたが、Borgへの移行にともない増大するクエリ負荷へ 対応するためにストレージをGFSへと切り出した。

  3. メモリの分離
    MapReduceのシャッフルのボトルネックを回避するためにDisaggregated Memory Shuffle Systemを採用した。

  4. In situデータ分析への対応
    In situデータ分析とはDBMSへのデータロードを必要としないデータ分析のことで、Dremelでは GFSに移行するときにGoogle内で共有のストレージフォーマットを使用することでGoogle内のデータに対応した。 加えてGoogle Cloud StorageやGoogle Drive、MySQL、BigTableなどからのデータ取得もフェデレーションとして 対応した。

  5. サーバレスアーキテクチャ
    分散、フォールトトレラントリスタート、仮想スケジューリングユニットによりマルチテナントかつオンデマンド なリソースを提供可能とし、低価格な利用を可能とした。 現在ではサーバレスアーキテクチャを進化させ、集中型スケジューリングやShuffle Persistent Layer、 柔軟なDAG実行、動的クエリ実行などを実装することでより優れたサーバレスアーキテクチャを実現した。

  6. ネストデータにおけるカラムナストレージ
    Dremelのデータフォーマットはprotobufのため半構造化データをカラムナストレージに保存する必要がある。 これはそれぞれのデータフィールドをそれぞれのカラムナストレージに保存することで実現している。

    [igure 5: Two sample nested records and their schema (based on Figure 2 in [32])]
    Figure 5
    Figure 6: Columnar representation of the data in Figure 5 showing repetition levels (r) and definition levels (d)
    Figure 6
    Figure 7: Columnar representation of the data in Figure 5 showing length (len) and presence (p
    Figure 7

  7. クエリレイテンシの最小化
    これまでに説明した手法を適用することでインタラクティブな実行のレイテンシは大きくなる。それを解決するために Dremelではスタンバイサーバプール、マルチレベル実行ツリー、列指向スキーマ表現、CPUとIO負荷のバランス調整、 ファイルオペレーションの再利用、保証されたキャパシティ、適合的なクエリスケーリングにより実現している。

作業時間

  • read
    • 27:50
    • 27:50
  • author
    • 32:02
    • 4:12
  • summary
    • 68:50
    • 26:48

クエリオプティマイザの精度を検証した論文を読みました

CMU_Advanced_Database_Systems DB 論文

この記事の趣旨

2015年に発表されたクエリオプティマイザにおけるカーディナリティ推定とコストモデル、列挙アルゴリズムの貢献度を 評価した論文を読んでいきます。

How Good Are Query Optimizers, Really?

著者について

Viktor Leis、Andrey Gubichev、Atanas Mirchev、Peter Boncz、Alfons Kemper、Thomas Neumannらの グループによる論文。

ほとんどのメンバーはDBMSにおける最適化について研究しているが、Atanas Mirchevはより 統計や探索といった最適化よりの研究をしている。

問題意識

良い結合順序を見つけることはクエリの性能に対して大きな影響を与えるため、熱心に研究されてきた。 古典的なクエリ最適化のアプローチでは以下のステップで動的計画方に基づいた最適化を行なう。 1. 有効な結合順序の列挙 1. カーディナリティ推定値を入力としたコストモデルの選択

理論的にはカーディナリティとコストモデルの推定値が正確であれば、最適なクエリプランを選択することができる。 しかし現実にはカーディナリティ推定は一様性や独立性といった単純化された仮定に基づいており、しばしばそのような 仮定は間違っているため悲惨な計画を作成する。

手法

この論文ではカーディナリティ推定器の評価と正確なコストモデルの重要性の評価、そして列挙された結合順序の空間が どの程度影響するのかを以下の方法で検証し、貢献を行なっている。 1. IMDBデータを用いたJoin Order BenchmarkというJOINにフォーカスしたベンチマークによる評価を行なう 1. 実世界のデータセットにおける現実的なクエリを用いたE2Eの検証を行なう。 1. クエリ性能に対するカーディナリティ・コストモデル・列挙アルゴリズムの貢献度を定量化し、最適なクエリプラン生成のため のガイドラインを策定している。

作業時間

  • read
    • 29:38
    • 29:38
  • author
    • 33:08
    • 3:30
  • summary
    • 48:44
    • 14:36

感想

時間が無くまとめ途中で切り上げてしまった。やらないよりマシではあるものの、ちゃんと纏めるときに くらべて理解度に影響が出そうなので時間に余裕を持っておきたい。 内容自体はGW中にPostgreSQLの実装を読んでいたこともあり、わりと理解しやすかった。

現代のクエリオプティマイザの基礎となる技術をまとめた論文を読みました

CMU_Advanced_Database_Systems DB 論文

この記事の趣旨

1998年に発表されたクエリオプティマイザの基礎としてとくに重要な手法をまとめた 論文を読みました。

An Overview of Query Optimization in Relational Systems

著者について

Surajit Chaudhuriによる論文 Microsoft所属の研究者でRDBMSの研究を行なっており、近年ではCloudにおけるDBMSの研究を行なっている。

概要

RDBMSが提案された1970年代からクエリ最適化は大規模で幅の広く研究が行なわれてきた。 この論文では執筆当時(1998年)までの重要な研究の基礎を説明している。

手法

  1. 探索空間
    一般化したJOINのプロセスを説明したのち、外部結合・グループバイによる結合・マージ処理による 結合対象のブロック化について説明している。

  2. 統計情報とコストの推定
    実行計画を決定する際に行なうコストの推定と、それに必要な統計情報について説明している。

  3. 列挙アルゴリズム
    クエリに対して高価ではない実行計画を提供するための、列挙アルゴリズムについて説明している。 論文内では拡張可能なオプティマイザとして、StarburstとVolcano/Cascadeの2種類のオプティマイザの詳細 を論じている。

  4. 最新(当時)の最適化
    当時最新であったトピックとして分散データベースと並列データベースの比較、UDFにおける最適化、そして マテリアライズドビューについて説明している。

作業時間

  • read
    • 31:40
    • 31:40
  • author
    • 33:40
    • 2:00
  • summary
    • 52:55
    • 19:15

感想

ベクトル化やパラレルジョインで扱われていたVolcanoオプティマイザの端に触れることが出来ました。 内容としては基礎的な内容が多いものの、知らない概念もいくつかあり引用している論文も読みたいです。 クエリ最適化の基礎を学ぶのに非常にいい内容でした。