ブログ@nnaka2992

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

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

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 utilitycompact_tableコマンドにより、 任意のタイミングでテーブルに対して圧縮を実行することが出来る。

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

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-hoursscheduled-full-compaction-jitter-factor-percentageのフラグで管理される。

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

スケジュール化したデータ圧縮は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

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

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に互換したAPIPostgreSQLのクエリレイヤを再利用している。
  • 新しい変更は互換性を崩さない。
  • YSQLは新しいPostgreSQLに互換しつづけることを目標としている。

YCQL

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

パフォーマンス

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

地理的分散

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

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

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

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

この記事の趣旨

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 DriveMySQLBigTableなどからのデータ取得もフェデレーションとして 対応した。

  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

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

この記事の趣旨

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の実装を読んでいたこともあり、わりと理解しやすかった。

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

この記事の趣旨

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オプティマイザの端に触れることが出来ました。 内容としては基礎的な内容が多いものの、知らない概念もいくつかあり引用している論文も読みたいです。 クエリ最適化の基礎を学ぶのに非常にいい内容でした。

DBMSとクライアント間におけるデータ転送を最適化する論文を読みました

この記事の趣旨

2017年に出版されたリモートDBMSとクライアント間の大量データ転送を最適化する 手法を提案する論文を読みました。

Don’t Hold My Data Hostage – A Case For Client Protocol Redesign

著者について

Mark Raasveldt、Hannes Muhleisenらのグループによる論文。 いずれもCentrum Wiskunde & Informaticaの所属で、DuckDBのCxO。 DBMSと分析システムにおけるパフォーマンス最適化を研究している。

問題意識

DBMSからクライアントプログラムに大量のデータを転送することは一般的なタスクである。 例えばRやPythonなどを用いた分析システムはしばしばデータベース・インターフェースを利用してデータの取得 を行なっている。

一方でネットワーク越しにデータを転送することはレイテンシを増加させ、転送時間を長引かせる要因である。 そのため分析用途で大量のデータ転送を避け、一部のデータをサンプルとして利用するに止まることが多い。 このアプローチはパフォーマンスの低下を押さえられるものの、分析や機械学習の精度を下げることに繋がる。

とくに既存のクライアントではネットワークによるレイテンシとスループットの制限に大きな影響を受けパフォーマンス を劣化させる。 この問題はデータベースが別マシンやクラウドで動作するときにより大きな問題となる。

手法

本論文では既存のシリアライズ手法と圧縮手法によるパフォーマンスへの影響を計測し、新しいプロトコルとして以下の特性を持つ 手法を提案している。 1. チャンク毎のデータ転送と(デ)シリアライゼーション 1. ヒューリスティックによる圧縮方法の決定 1. text/binaryによるカスタムシリアライゼーションを使用する 1. NULL終端によるテキストの取り扱い

実験結果

提案手法を実装したMonetDB(表内ではMonetDB++)とPostgreSQL(表内ではPostgreSQL++)を既存のDBMSやnetcatと比較することで 評価を行なっている。

TCP-Hのlineitem、American Community Survay、Airline On-Time Statisticsの3つのデータセットで評価を行なったところ、 ローカル通信における非圧縮netcatを除き殆どのケースでMonetDB++系が最良のパフォーマンスを発揮し 次点でPostgreSQL++系が優れた結果を残している。

Table 10: Results of transferring the SF10 lineitem table for different network configurations.
Table 10
Table 11: Results of transferring the ACS table for different network configurations.
Table 11
Table 12: Results of transferring the ontime table for different network configurations.
Table 12

PostgreSQLに比べMonetDBが優れている理由はPostgreSQLの行指向データを列指向に変換するコストのためである。

作業時間

  • read
    • 31:21
    • 31:21
  • author
    • 35:38
    • 4:17
  • summary
    • 70:13
    • 34:35

感想

論文出版時にはTPC/IPプロトコルが前提でQuic登場前のため、ネットワークプロトコル自体は考慮されていない。 現在であればTPC/IPとQuicに適合した手法の比較が行なわれると思うので気になるところ。