NAKADATE Naoki

前回からつづいてYugabyteDBのドキュメントを読んでいきます。前回はArchitecture > Core functions > Write I/O pathを読みました。今回はArchitecture > Core functions > Read I/O pathを読みます。ドキュメントのバージョンは最新のv2.19 previewです。また画像は同ドキュメントより引用しています。Read I/O pathI/O Pathはタブレットリーダーが特定されリード処理を実行する単一キーの例で説明することが出来る。Tablet leader identificationユーザーが発行したYQLクエリレイヤに作用するリードリクエストはポートから適切なAPI(YQLまたはYCQL)を経由して行なわれる。このユーザリクエストはYQLレイヤで内部キーに変換され、YQLレイヤがタブレットとそれをホストするYB-TServerを発見するのに利用される。YQLレイヤはこれをYB-MasterにたしてRPC呼び出しを実行するために行なう。またそのレスポンスは将来の利用のためにキャッシュされる。その後YQLレイヤはリーダータブレットピアーをホストするYB-TServerに対してリード処理を行なう。このリード処理は内部キーを保持するタブレットのRaftグループのリーダーによって処理される。このリードリクエストを処理するRaftグループのリーダーはDocDBから読み込みを実行し、その結果をユーザーに戻す。Write I/O Pathで説明した通り、YugabyteDBのスマートクライアントではアプリケーションのリクエストを直接適切なYB-TServerに送信することが出来るため、余計なネットワークホップやマスターへのアクセスを省略することが出来る。Read operation performed by tablet leaderkという値をKというプライマリキー行に持つテーブルT1からデータを取得するケースについて考える。またテーブルT1はキー行Kと値行Vを持つものとする。1下記の画像はリード処理について説明している。YugabyteDBはデフォルトでは強整合性の読み取りを採用している。リードクエリはさらに複雑になることもある。YQLクエリレイヤーは式やビルトイン関数、算術演算を含むクエリを処理するfully-optimized2されたクエリエンジンを持っている。SELECT K,V from T1 where K = 'k'ということ↩↩

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

前回からつづいてYugabyteDBのドキュメントを読んでいきます。前回はArchitecture > Core functions > Table Creationを読みました。今回はArchitecture > Core functions > Write I/O pathを読みます。ドキュメントのバージョンは最新のv2.19 previewです。また画像は同ドキュメントより引用しています。Write I/O pathWrite I/O pathはYQLレイヤーで処理され、タブレットリーダーによってレプリケーションの準備が行なわれるシングルキーでの書き込みとして例示することが出来る。アトミックなアップデートを共なう複数キーでの分散トランザクションなど複雑なケースについては分散トランザクションに記載する。Write operation processing by YQL layerユーザーが発行したYQLクエリレイヤに作用するライトリクエストはポートから適切なAPI(YQLまたはYCQL)を経由して行なわれる。このユーザーリクエストはYQLレイヤで内部キーに変換される。シャーディングで説明するように、それぞれのキーは一つのタブレットが所有する。どのタブレットがキーを所有するか特定するために、YQLレイヤはYB-MasterにRPC1呼び出しを実行する。そのレスポンスは将来の利用のためにキャッシュされる。YugabyteDBはタブレットの場所をキャッシュし直接参照することでネットワークホップを減らすことで、YQLレイヤが直接適切なYB-TServerにホストされるタブレットリーダーにリクエストを送信することが出来るスマートクライアントを持つ。YQLレイヤがローカルノードにタブレットリーダーを見つけた場合、RPCはローカルファンクションコールになりリクエストをシリアライズとデシリアライズしてネットワーク越しに送信する時間を節約することが出来る。その後YQLレイヤはタブレットリーダーをホストするYB-TServerへの書き込みを発行する。この書き込みはキーを所有するRaftグループのタブレットリーダーによって処理される。Preparation of the operation for replication by tablet leader下記の図はタブレットリーダーがレプリケーションを実行する処理を説明している。タブレットのRaft Groupリーダーは以下の処理を実行する。現在実行されている処理が現在のスキーマに対応しているかを判別するキーに対してローカルin-memoryロックマネージャーを利用してロックを取得する。このロック機構はフォロワーには存在しない必要であればデータを読み込む(read-modify-writeや条件付きアップデート命令など)DocDBに書き込まれる変更のバッチを準備する。この書き込みバッチは殆ど最終的にRocksDBに書き込まれるKey-Valueペアに近く、それぞれのキーの末尾に最終的なhybrid timestampが添えられていないだけであるRaft replication of the write operation書き込みのRaftレプリケーション処理の流れは以下のように説明することが出来る。リーダーがバッチをRaft logにアペンドし、書き込みのためのhybrid timestampを選択するRaftを利用しデータをピアーに複製する成功したRaft replicationのデータをローカルのDocDBに反映するユーザーに成功を返すフォロワータブレットはRaftを利用したデータの複製を受けつけ、コミットされた事が分ったタイミングでその複製をローカルのDocDBに反映する。リーダーは以下のようにコミットポイントに於ける後続のRPCリクエストの進行を進める。書き込みバッチを含むRaftエントリーは過半数以上のタブレットRaft Groupピアーに複製されるRaftのサブシステムから"Replication Successful"のコールバックを取得したあと、リーダーはローカルのDocDBにバッチの書き込みを適用するリーダーからの次の更新でエントリーがコミットされたことがフォロワーに通知され、フォロワーはそれぞれのRocksDBインスタンスにバッチの書き込みを適用する。Response to the clientInformation Pending2Exampleskとvという値をKという行とVという行をもつテーブルT1に挿入する例について考える3。この例ではユーザーアプリケーションがランダムなYugabyteDBサーバにWriteクエリを送信し、そのサーバがリクエストを適切にルーティングすると仮定して簡略化している。特にYCQLではYugabyteDB Smart Clientを使うことで、余分なネットワークホップを避けることが出来る。↩原文ママ。過去のバージョンでも記載無し↩INSERT INTO T1 (K,V) VALUES('k','v')ということ↩

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

前回からつづいてYugabyteDBのドキュメントを読んでいきます。前回はArchitecture > Core functions > Universe creationを読みました。今回はArchitecture > Core functions > Table Creationを読みます。ドキュメントのバージョンは最新のv2.19 previewです。また画像は同ドキュメントより引用しています。Table CrationYugabyteDBではユーザーにより実行されるテーブルの作成はYB-Masterのリーダーが実行する非同期APIによって管理される。YB-MasterはそのAPIでテーブルのスキーマと障害耐性を高めるために形成するRaftグループに所属するYB-Masterでのテーブル作成に必要な他の情報のレプリケーションが完了した段階でAPIの成功を返す。YB-Masterのリーダーがテーブル作成を実行するときは複数のステップが存在する。ValidationYB-Masterリーダーはテーブルスキーマの検証を行ない、指定された数のタブレットを作成する。これらのタブレットはこの段階ではYB-TServerには割り振られていない。ReplicationYB-MasterリーダーはYB-MasterのRaftグループにテーブルスキーマと新しく作成されたタブレット(この時点ではYB-TServerへの割り当て行なわれていない)の複製を行なう。この処理はYB-Masterリーダに障害が発生してもテーブル作成が成功することを保証する。Acknowledgementテーブル作成処理はYB-Masterリーダーに障害が発生しても処理を継続することが出来るため、この段階で非同期テーブル作成APIは成功を返す。ExecutionYB-Masterリーダーはそれぞれのタブレットをレプリケーションファクターとして指定された数だけYB-TServerに割り当てを行なう。このタブレットピアーの配置は指定された障害耐性を実現でき、またタブレットの割り当てがYB-TServerに均等に行なわれるように実行される。タブレットのYB-TServerへの割り当てはタブレットのレプリカが複数クラウド、リージョン、アヴェイラビリティゾーンをまたいで分散するといった追加の制約を満す必要がある。Continuous monitoringYB-Masterリーダーは全てのタブレットの割り当て処理を監視し、その実行状態と完了をユーザーが実行したAPIコールに対して応答する必要がある。Examplesテーブルが4ノードからなるYugabyteDBUniverseに作成される処理について考える。このときテーブルは16のタブレットと3つのレプリケーションファクターを持つとする。YB-Masterリーダーはスキーマを検証する。また16タブレット(合計48のタブレットピアー)を作成し、Raftを利用して過半数のYB-TServerにテーブルの作成に必要なデータを複製する。作成したタブレットをRaftグループを成すYB-TServerの中の指定された数のYB-TServer割り当て、リーダーの選出を行なう。このタブレットに属するキーに対する全てのリードとライトは、タブレットピアーのリーダーとRaftグループが責任を持つ。タブレットが割り当てられると長期に渡る障害か将来のロードバランシングが発生しYB-Masterにオーナーシップを変更されるまで、割り当て先のYB-TServerが所有する。タブレットリーダーをホストするYB-TServerの内の1台に障害が発生した場合、タブレットのRaftグループはI/Oを処理するために即座にリーダーエレクションを実行する。そのためYB-MasterはI/Oにおけるクリティカルパスになることはない。レプリケーション先となる候補を探す。この複製処理は段階的かつGracefulに実行される。

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

前回からつづいてYugabyteDBのドキュメントを読んでいきます。前回はArchitecture > Key Concepts > YB-Master serviceを読みました。今回はArchitecture > Core functions > Universe creationを読みます。ドキュメントのバージョンは最新のv2.19 previewです。また画像は同ドキュメントより引用しています。Universe creationYugabyteDBのユニバース作成は複数のステップを含む。Start YB-MastersYBユニバース作成の最初のステップはレプリケーションファクターで指定された数だけYB-Masterを作成することである。作成されたYB-Masterはそれぞれを認識している。YB-Masterはユニバース内でユニークなID(UUID)をそれぞれに割り当て、それぞれを認識しあったあとにリーダーエレクションを実行する。このステップの終りにYB-Masterの中のひとつがリーダーとして確立される。Start YB-TServersノードの数だけYB-TServerを起動し、それぞれにマスターのアドレスを渡す。それぞれのYB-TServerはマスターにハートビートを送信し、正常に動作していることを確認する。ハートビートはYB-TServerが現在ホストしているタブレットとその負荷情報についても通信するが、この時点ではタブレットにデータは登録されていない。Examples4ノードからなるYBユニバースにテーブルを作成する場合について考える。テーブルのレプリケーションファクターは3とする。3つのマスターがcreateモードで起動される。これはマスターがすでに起動しているために発生するエラーを防ぐために明示的に実行される。リーダーエレクションを実行し、リーダーを選出する。YB-TServerが起動し、全てのYB-TServerがマスターにハートビートを送信する。

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

前回](https://nnaka2992.hatenablog.com/entry/reading_yugabytedb_docs_3)からつづいてYugabyteDBのドキュメントを読んでいきます。前回はArchitecture > Key Concepts > YB-TServer serviceを読みました。今回はArchitecture > Key Concepts > YB-Master serviceを読みます。ドキュメントのバージョンは最新のv2.19 previewです。また画像は同ドキュメントより引用しています。YB-Master serviceYB-Masterサービスはテーブルやそのタブレットの場所、ユーザー・ロールの権限といったシステムのメタデータとレコードの管理を行っている。それに加えYB-Masterはロードバランシングやレプリケーションの開始といったバックグラウンドオペレーションの管理や、テーブルのCREATEやALTER、DROPといった様々な管理オペレーションの責任を持つ。YB-MasterはRaft Groupを組むことで高可用性を実現し、またテーブルに対するI/Oの単一障害点にならない。Functions of YB-MasterYB-Masterはシステムの重要な機能を複数持っている。Coordination of universe-wide administrative operationsCREATE 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-TServersYB-Masterは全てのテーブルとそれらをホストするYB-TServerの情報を保存している。一般のクライアントではそれらの情報はクライアントからクエリレイヤなどを通して取得された上で、クライアントにメタデータを返しデータアクセスが行なわれる。一方でスマートクライアントではYB-Masterに保存されたメタデータを利用して特定のYB-TServerが保持するタブレットやキャッシュを利用することが出来るため、データアクセス時のネットワークをまたぐ通信を減らすことができパフォーマンスを高めることができる。Background operationsいくつかのオペレーションはUniverseのライフタイムを通してバックグラウンドで行なうことで、フォアグラウンドのRead/Writeに影響を与えずに実行することが出来る。Data placement and load balancingYB-MasterのリーダーはCREATE TABLE時にタブレットの初期配置をYB-TServerをまたいで行なう。そのときにユーザー定義のデータ配置制約を強制し均一な読み込みを保証する。Universeのライフタイム中のノード追加や障害が発生しても、負荷分散を継続しデータ配置の制約を自動的に適用する。Leader balancing複数のYB-TServerに配置されたタブレットへのアクセスがUniverseをまたいで分散されることを保証している一方で、YB-Masterは対象となるノード1間でそれぞれのノードが同じ数のtablet-peer leader2をもつことを保証する。Rereplication of data on extended YB-TServer failureYB-Masterは全てのYB-TServerからハードビートシグナルを受け取ることでYB-TServerの死活監視を行なっている。そしてYB-MasterはYB-TServerの異常を検知したときに、どれぐらいのあいだYB-TServerが異常であったかを追跡する。閾値を超えると、YB-Masterは障害中のYB-TServerに配置されていたタブレットを再配置するYB-TServerを探し、レプリケーションを実行する。レプリケーションはYB-Masterリーダーに抑制された状態で実行されるため、Universeのフォアグラウンドオペレーションには影響をおよぼさない。Raft Groupのリーダーになれるノード↩↩

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

YugabyteDBのドキュメントを全部読む Day3前回からつづいてYugabyteDBのドキュメントを読んでいきます。前回はArchitecture > Key Concepts > Universeを読みました。今回はArchitecture > Key Concepts > YB-TServer serviceを読みます。ドキュメントのバージョンは最新のv2.19 previewです。また画像は同ドキュメントより引用しています。それはそれとして技術系の単語をカタカナ表記で誤魔化していて、体系的に学んでいないことがバレてしまう。特にストレージまわりが分からない……YB-TServer serviceYB-TServer(YugabyteDB Tablet Servcer)はユーザからの受けつけたYugabyteDBクラスタへのリクエストのI/Oの処理をする。テーブルのデータは一つ以上のTablet peerに分割(シャーディング)される。peerの数はレプリケーションファクターによって決定される。YB-TServerは一つ以上のTablet peerをホストする。Tablet peerはRaftグループを形成してグループ間でデータの複製を行ない、タブレットはYB-TServer上で最大の効率になるように管理される。Server-global block cacheブロックキャッシュは一つTB-TServer上の異なるタブレット間で共有される。YB-TServerのメモリ効率は一つのテーブルからの読み込みが多いほど最適化される。Space AmplificationYugabyteDBではSize-tired Compactionというライトアンプリフィケーション1が小さい圧縮方式を利用している。Size-tired Compactionはスペースアンプリフィケーション2が大きいという問題があるが、YugabyteDBではテーブルは複数のタブレットに分割され、タブレット間でのConcurrent Compactionは特定の最大値まで絞られるため問題になりにくい。YugabyteDBでは凡そ10-20%のスペースアンプリフィケーションにおさまる。つまりSize-tired Compaction一単位が扱うデータ量を小さく(タブレット化)して、同時に実行される圧縮処理数を絞ることで特定のタイミングで圧縮に使用されるストレージ容量を抑えているということ？Throttled compactionsYB-TServerではタブレット間で実行される圧縮処理の同時実行数を制限することで、圧縮処理が多量のリソースを占有することを防いでいる。この機能は圧縮されるファイル同士のサイズを比べ、実行される圧縮処理が妥当であることを確認することで実現されている。Small and large compaction queuesYB-TServerでは圧縮処理を大きい圧縮処理と小さい圧縮処理に分けて優先度を決めることで、I/Oが大きな場合でもシステムの機能を保っている。YugabyteDBでは圧縮処理数を制限することに加え、様々な最適化を実行することで圧縮処理の影響を最小化している。Manual compactionYugabyteDBではyb-admin utilityのcompact_tableコマンドにより、任意のタイミングでテーブルに対して圧縮を実行することが出来る。この方法はデータが新しく書き込まれない場合や、DDLやTTLの超過によるデータ削除時によりデータが断片化したときに有効である。Statistics-based full compactions to improve read performanceYugabyteDBでは読み込まれたkey-valueペアをDocDBレベルで監視している。監視対象となる時間軸はauto-compact-stat-window-secondsで管理されている。YugabyteDBがデータ読み込み時に多量の廃棄されたデータのスキップを検知した場合、full compactionがトリガーされ不要なキーの削除が行なわれる。Full compactionがトリガーされる詳細な条件は対象の時間軸で以下が満された時である。廃棄されたキーとアクティブなキーが読まれる割り合いがauto-compact-percent-obsoleteで定義された閾値を超たとき。廃棄されたキーの読み込みauto-compact-min-obsolete-keys-foundで定義された閾値を超たとき。この機能はTTLを設定したテーブルと互換性があり、TTL file expirationが有効なテーブルではスケジュールされた圧縮を実行しない。Scheduled full compactionsYugabyteDBでは全てのデータに対するデータ圧縮をスケジュール実行することが出来る。スケジュール実行はscheduled-full-compaction-frequency-hoursとscheduled-full-compaction-jitter-factor-percentageのフラグで管理される。この機能は大量のDELETEとUPDATEを定常的に実行するワークロードでのパフォーマンスとディスクスペースの再割り当てに有効である。スケジュール化したデータ圧縮はTTLと互換しているが、TTL file expirationとは互換していない。つまりスケジュールされた圧縮は実行されない。Server-global memstore limitServer-global memstore limitは一つのYB-TServer上のタブレット間でシェアされるメモリサイズを追跡し、強制する。この機能はタブレット間の書き込みに偏りがある場合に有効である。一つのテーブルに書き込みが集中しているばあい、メモリ制限以上のメモリを割り当てることでパフォーマンスを向上させることが出来る。Auto-sizing of block cache and memstoreBlock Cacheとmemstoreは何れも多量のメモリを使用している。これらはtablet-peer間で共有されるリソースのため、メモリ管理とこれらのコンポーネントの様々な環境に合せたサイジングを容易にしている。YB-TServerでは自動で特定の割合のメモリをBlock CacheとMemstoreに割り当てる。Distributing tablet load uniformly across data disks複数のSSDを利用するハードウェアでは、テーブルのデータ(SSTable)とWALはテーブル毎に利用可能なディスクに均等に分散される。このストライピングと呼ばれる負荷分散は、それぞれのディスクがそれぞれのテーブルの負荷を均等に処理することを保証する。SSDで実際に書き込んだデータより書き込み量が増幅する現象。もちろんライトアンプリフィケーションが小さいほうが望ましい。↩↩

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

YugabyteDBのドキュメントを全部読む Day2前回からつづいてYugabyteDBのドキュメントを読んでいきます。前回はArchitecture > Design goalsを読みました。今回はArchitecture > Key Concepts > Universeを読みます。また画像は同ドキュメントより引用しています。UniverseYugabyteDBは耐久性とスケーラビリティを兼ねそなえた分散データベースを達成するために、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やメンテナンスの実行、ロードバランシングといったオペレーションを管理する。UniverseとClusterUniverseは一つのプライマリクラスタとゼロ個以上のレプリカクラスタによって構成されている。プライマリクラスタプライマリクラスタはRead/Write両方の実行と、プライマリクラスタ内のノード間の同期的なレプリケーションを担当する。リードレプリカクラスタリードレプリカクラスタはRead処理のみを実行する。Write処理は自動的にプライマリクラスタにルーティングされる。リードレプリカクラスタを利用することで、地理的に分散したデータに対する読み取りの遅延を小さくすることができる。データはプライマリクラスタから非同期的にとりこまれる。これはRaftの書き込みには関与しないRaftオブザーバとして機能する。GoogleのCloud Spannerでも同様にUniverseと呼ばれている↩PostgreSQLではSchemaの裏側に存在するデータ構造↩

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

Day1最近Twitter改めXで「俺はDBのドキュメント端から端まで読んで強くなった」というX's1を複数みかけました。周りのエンジニアに一歩差をつける方法として、フレームワークやミドルウェアやライブラリのドキュメントを最初から最後までちゃんと読む、というのがあって、これはマジでコスパ抜群です。— 徳永広夢 (@tokuhirom) July 21, 2023 確かに私のRedisはこれ。 https://t.co/2y1E01aLGw— maru (@maruloop) July 22, 2023 私のMySQLもこれ。 https://t.co/BxiOjeQVPk— yoku0825 (@yoku0825) July 22, 2023 俺のpostgresqlもこれ。 https://t.co/URRjyXCpGI— そーだい@初代ALF (@soudai1025) July 22, 2023 PostgreSQL系NewSQLで最強になりたいのでYugabyteDBのドキュメントを順番に読んで行きます。ドキュメントはv2.19に対応したものです。手始めにArchitectureの一番先頭にあるDesign goalsから読みはじめます。また画像は同ドキュメントより引用しています。Design goalsYugabyteDBは以下を達成することを目標としている。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 APIYugabyteDBではYSQLとYCQLという2種類のQuery APIをサポートしている。YSQLYSQLはPostgreSQLに互換したAPIでPostgreSQLのクエリレイヤを再利用している。新しい変更は互換性を崩さない。YSQLは新しいPostgreSQLに互換しつづけることを目標としている。YCQLYCQLはCassandraのクエイ言語から派生した半リレーショナルなクエリ言語で、Webスケールな膨大なwriteに対応してスケールし素早いデータ取得を目標としている。パフォーマンスC++で実装されているため高いパフォーマンスと巨大なHeap(RAM)をCacheとして利用できる。SSDとNVMeに最適化している。高いWriteスループットとクライアントの同時実行性、高いデータ密度、増加し続けるデータへの対応を目標としている。地理的分散Zone、Multi Region、Multi Cloudいずれにも対応している。これに対応するために、ノード障害やトラヒックのルーティングなどに対応できる必要がある。クラウドネイティブアーキテクチャパブリッククラウドやオンプレミスで利用される一般てきなハードウェアで利用可能にする。原子時計のような特別なものに依存しない。Kubernatesに対応している。OSSで提供している。https://twitter.com/SawyerMerritt/status/1683365478582951936↩

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

Google CloudではPublic IPを利用した際に割り振られる可能性のあるCIDRの一覧がcloud.jsonでJSON形式で公開されています。この記事は雑な検証用のTerraformで承認済みネットワークにasia-notheast1のCIDRを全部登録してやろうとしたとき、上記のJSONファイルからscopeがasia-northeast1のprefixes.ipv4Prefixを抜きだそうとしたときにハマったのでその対応方法のメモです 結論以下のような感じで書いたら対応できました。contains(keys(hoge), "fuga") # hogeのkeyにh...

Terraformでmapにkeyが含まれないときにスキップしたい

クラウドを利用する一番のメリットの一つとしてオンデマンドでリソースを調達し、アクセス負荷に応じてスケールイン・アウト出来ることが上げられます。そのため大体のアプリケーションではシングルリージョンまたは隣接するリージョン2~3程度で運用を始めることが多いと思います。(日本の場合asia-northeast-1とasia-northeast-2など)アプリケーションがグローバルに拡大すると、それだけ物理的な距離が広がりユーザ・サーバ間のアクセスにかかる時間が拡大します。例えばユーザ・サーバ共に日本にある場合(沖縄・北海道間約3,000km)、ネットワークによる遅延は片道約15ms以下...

光に負けルナ~Google Cloudでのマルチリージョンデータベースについて~

GitHub Copilot便利ですね。2021年にTechnical Previewとして発表された時から便利だ便利だと言われていたGitHub Copilotに、2023年の4月末ごろからデビューしました。デビューしたは良いものの最近は仕事ではコーディングよりアーキテクト的な方面でのお仕事が多かったり、個人の時間でもコーディングするよりOSSのコードを読むことのほうが多くコーディングのアシスタントツールとしては使いこなせていません。そのため最近はPostgreSQLのコードを読むときのアシスタントとして利用することが多いです。なのでこの記事ではCopilotでコードリーディン...

Copilotでらくらくコードリーディング

今年に入ってからCarnegie Mellon UniversityのAdvanced Database SystemsでReading Assignmentとして出ている論文リストで必須とされているものや講義資料を読みました。https://nnaka2992.hatenablog.com/archive/category/論文この記事では紹介されていた論文やAdvanced Database Systemsの講義資料・動画を振り替えることで、BigQueryやRedShift、Snowflakeといった最新の分析用データベースがどのように優れたパフォーマンスを実現しているかを考え...

OLAPデータベースを支える技術

この記事の趣旨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データ分析などを統合した最初のツールである。手法SQLの採用Googleでは殆どのデータはBigTableなどNoSQLデータベースで管理されていたため、SQLを用いないデータアクセスが主流であった。しかしトランザクション型ビッグデータシステムにおける、SQLの採用に共ないDremelでもSQLを採用した。ストレージの分離メモリの分離MapReduceのシャッフルのボトルネックを回避するためにDisaggregated Memory Shuffle Systemを採用した。In situデータ分析への対応DBMSへのデータロードを必要としないデータ分析のことで、DremelではGFSに移行するときにGoogle内で共有のストレージフォーマットを使用することでGoogle内のデータに対応した。加えてGoogle Cloud StorageやGoogle Drive、MySQL、BigTableなどからのデータ取得もフェデレーションとして対応した。サーバレスアーキテクチャフォールトトレラントリスタート、仮想スケジューリングユニットによりマルチテナントかつオンデマンドなリソースを提供可能とし、低価格な利用を可能とした。現在ではサーバレスアーキテクチャを進化させ、集中型スケジューリングやShuffle Persistent Layer、柔軟なDAG実行、動的クエリ実行などを実装することでより優れたサーバレスアーキテクチャを実現した。ネストデータにおけるカラムナストレージ[[32])]Figure 5Figure 6Figure 7クエリレイテンシの最小化インタラクティブな実行のレイテンシは大きくなる。それを解決するためにDremelではスタンバイサーバプール、マルチレベル実行ツリー、列指向スキーマ表現、CPUとIO負荷のバランス調整、ファイルオペレーションの再利用、保証されたキャパシティ、適合的なクエリスケーリングにより実現している。作業時間read27:5027:50author32:024:12summary68:5026:48

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

はじめにこの記事ではNewSQLの特徴であるノード間の分散とトランザクションや分断耐性などがTiDBではどのような技術によって実現されているかを説明することを目的としています。Spannerの論文が2012年に発表されてから10年以上の年月が流れ、優れた論文や実装ドキュメント、個人による解説ブログなど技術的詳細について述べた資料は多くあります。加えてこの記事を入門的なものと位置づけているため各コンポーネントを網羅的に解説するというよりは、キーコンセプトをどのように実装しているのかを実験を混じえながら動作の実現方法の解説を中心に扱います。また今回はTiDBをベースに説明し...

TiDBで学ぶNewSQLのアーキテクチャ for Beginners

この記事の趣旨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. クエリ性能に対するカーディナリティ・コストモデル・列挙アルゴリズムの貢献度を定量化し、最適なクエリプラン生成のためのガイドラインを策定している。作業時間read29:3829:38author33:083:30summary48:4414:36感想時間が無くまとめ途中で切り上げてしまった。やらないよりマシではあるものの、ちゃんと纏めるときにくらべて理解度に影響が出そうなので時間に余裕を持っておきたい。内容自体はGW中にPostgreSQLの実装を読んでいたこともあり、わりと理解しやすかった。

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

この記事の趣旨1998年に発表されたクエリオプティマイザの基礎としてとくに重要な手法をまとめた論文を読みました。An Overview of Query Optimization in Relational Systems著者についてSurajit Chaudhuriによる論文Microsoft所属の研究者でRDBMSの研究を行なっており、近年ではCloudにおけるDBMSの研究を行なっている。概要RDBMSが提案された1970年代からクエリ最適化は大規模で幅の広く研究が行なわれてきた。この論文では執筆当時(1998年)までの重要な研究の基礎を説明している。手法探索空間統計情報とコストの推定列挙アルゴリズムアルゴリズムについて説明している。論文内では拡張可能なオプティマイザとして、StarburstとVolcano/Cascadeの2種類のオプティマイザの詳細を論じている。最新(当時)の最適化リアライズドビューについて説明している。作業時間read31:4031:40author33:402:00summary52:5519:15感想ベクトル化やパラレルジョインで扱われていたVolcanoオプティマイザの端に触れることが出来ました。内容としては基礎的な内容が多いものの、知らない概念もいくつかあり引用している論文も読みたいです。クエリ最適化の基礎を学ぶのに非常にいい内容でした。

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

この記事の趣旨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 10Table 11Table 12PostgreSQLに比べMonetDBが優れている理由はPostgreSQLの行指向データを列指向に変換するコストのためである。作業時間read31:2131:21author35:384:17summary70:1334:35感想論文出版時にはTPC/IPプロトコルが前提でQuic登場前のため、ネットワークプロトコル自体は考慮されていない。現在であればTPC/IPとQuicに適合した手法の比較が行なわれると思うので気になるところ。

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

この記事の趣旨2017年に発表されたSQL ServerでUDFを最適化しているFroidという手法についての論文を読みました。Froid: Optimization of Imperative Programs in a Relational Database著者についてKarthik Ramachandra、Kwanghyun Park、K. Venkatesh Emani、Alan Halverson、Cesar Galindo-Legaria、Conor Cunninghamのグループによる論文。ほとんどの著者はMicrosoftに所属しており、いずれもトランザクショナルワークロードでのRDBMSの最適化や分析ワークロードにおけるRDBMS最適化の研究をしている。問題意識RDBMSではSQLによるデータ処理アプローチと、UDFやストアドプロシージャなどによる命令型のデータ処理アプローチを提供している。SQLによるデータアクセスは高度に最適化されてきた一方で、命令型のデータ処理は非効率なため性能を阻害し利用を禁止している組織すらある。UDFによるデータアクセスは非効率であるものの、SQLに比べ下記のような利点を提供するため幅広く利用されているのも事実である。1. SQL間でコードの再利用方法を提供する1. 複雑なビジネスロジックやMLアルゴリズムなどSQLでは難しい表現を可能にする1. 単純なSQLの組み合わせのため、ユーザーの意図が明確に表現できるこれらのメリットを享受するためにRDBMSにおける命令型データアクセス手法のパフォーマンスを向上しする必要があった。手法提案手法であるFroidはMicrosoft SQL Serverにおける命令型コードのパフォーマンス向上の手法として、UDFを複雑なサブクエリとしてみなすアプローチを取っている。UDFを構成する命令はDECLARE、SELECT、IF/ELSE、RETURN、他のUDF、リレーショナルオペレーションの6つに分ることができる。提案手法ではこれらの命令を一般的なT-SQLに置き換え、Apply演算により一つの関係式に結合する方法で実現している。Table 1命令が一般SQLに置き換えられることでUDFに対して、SQLに用いられていた高度な最適化を導入することが出来る。また提案手法ではい以下の理由から、SQLとして命令を置換するときにクエリ最適化時に行なうのではなくバインド時に置換をしている。1. 実際のワークロードでの実験ではほぼ全てのケースでバインド時のほうが性能がよかった1. クエリオプティマイザの変更が不要1. バインディング時に特定の最適化を行なえるとくにクエリオプティマイザの変更はSQL Serverが商用データベースなため重要であった。作業時間read28:5028:50author32:103:20summary57:0024:50

SQL ServerにおけるUDF最適化の論文を読みました

この記事はDBMSの登場以前から現代のDBMSを取り巻く環境までを振り返ることで、なぜNewSQLが必要とされ登場したのかをまとめます。 おことわり筆者はあくまでDBMSユーザーであり、研究者ではないため内容は個人の見解です。また対象読者はある程度DBMSに関わりがあり、OLTPやOLAP、列指向や行指向といった基本的な単語を理解しているものとします。またNewSQLの技術的詳細はスコープ外とします。 DBMS以前データベースという言葉は1950年代に米軍が情報基地を集約したことに由来します。一方で学術的なデータベースの起源はW. C. McGeeが1959年に発表...

DBMSの歴史とNewSQL

この記事の趣旨2018年に発表された分析ワークロードなどで発生しがちな最終結果に比べ、非常に大きな中間結果を作成してしまうクエリを多方向結合で最適化する論文を読みました。Adopting Worst-Case Optimal Joins in Relational Database Systems著者についてMichael Freitag、Maximilian Bandle、Tobias Schmidt、Alfons Kemper、Thomas Neumannによるグループの論文いずれの著者もDBMSにおける最適化を中心に研究しており、それぞれ分析ワークロードにおける最適化や最新のハードウェアにおける最適化などを研究している。問題意識従来のRDBMSにおける結合処理のほとんどはバイナリ結合に依存して複数のリレーションにまたがるクエリを処理してきた。数十年に渡る研究によりバイナリ結合は幅広い柔軟性と優れた性能を発揮するようになった。その一方でバイナリ結合による実行計画は特定のワークロードでは最適ではないケースを示すことが知られている。主な原因として実際のクエリ結果に比べて非常に大きな中間結果を生成するためである。とくにPK以外のキーによる結合が多くなる分析ワークロードではそのような状態を避けることが難しく、またグラフ分析のようなクエリパターンでも多く見られる。近年の論理的な進歩により中間結果の列挙を避ける多方向結合のアルゴリズムが開発可能になった。この手法はバイナリ結合計画より優れた実行時間を保証できるため、RDBMSの堅牢性を大幅に向上させる可能性を持っている。しかし現状最悪ケース最適化結合アルゴリズムでは以下のような問題を抱えている。1. 膨大なストレージとメンテナンスを必要とする結合に参加出来るカラムを含むインデックスを必要とする。1. RDBMSは挿入と更新のサポートが必要なものの、既存のアルゴリズムは高価な事前計算を必要とする。そのため本論文は以下の制約を満たすアプローチを提案している1. 多方向結合が有益な場合のみ多方向結合を使用するオプティマイザを必要とする。1. 実行中に効率的に実行でき、ディスクのに永続化する必要のないパフォーマントインデックスを必要とする。手法提案手法では比較ベースではなくハッシュベースの結合のため、2の「実行中に効率的に実行でき、ディスクのに永続化する必要のないパフォーマントインデックスを必要とする。」という要素の考慮を除いている。またオプティマイザについては既存のコストベースのものを拡張し適応している。提案手法では潜在的に成長している結合のカスケードを最悪の場合の最適結合に置き換えることで、最適化されたバイナリ結合計画を洗練させるヒューリスティックなアプローチを提案している。通常の結合順序最適化で使用されるのと同じカーディナリティ推定値に基づいて、中間テーブルが膨大になる結合を特定する。作業時間read22:1322:13author25:483:35summary52:5826:50感想とても難しい内容に感じてしまい、殆ど頭を通りすぎてしまった気がする。今まで最適化は触れずに来たため、理解が浅い領域だった。よくよく考えるとDBMSの話しに最適化が登場するのはあたりまえなので、今後はその方面にも触れて行きたい。

中間結果が莫大になるときの結合を最適化する最悪ケース最適化結合をRDBMSに適応する論文を読みました

この記事の趣旨2013年に発表された"Multi-Core, Main-Memory Joins: Sort vs. Hash Revisited"という論文を読みました。当時最新のアルゴリズムとハードウェアにおける、ソートとハッシュによる結合のパフォーマンスを比べた論文です。Multi-Core, Main-Memory Joins: Sort vs. Hash Revisited著者についてCagri Balkesen、Gustavo Alonso、Jens Teubner、M. Tamer Ozsuらのグループによる論文いずれもDBMSにおけるクエリ最適化やビッグデータにおけるパフォーマンスを研究している。またGustavo Alonsoはハードウェアや分散システムもメインのフィールドとしている。問題意識DBMSにおいて常にソートマージとハッシュ結合の性能比較が行われており、最新の研究ではSIMDやNUMAへの適正に基づいてソートマージがより優れていると結論づけられていた。しかしこれらの分野は常に研究が重ねられ、過去の検証時には登場していなったハッシュ結合の最適化手法が生れた。この論文ではそれらを適用し再度ソートマージとハッシュ結合の性能比較を行なう。手法本論文では以下に分けて結合手法の評価を行なっている。1. ソートフェーズの評価SIMDソートアルゴリズムとC++のSTLソートアルゴリズムを比較している。マージフェーズの評価入力サイズの調整によるマージフェーズの最適化パーマンスを検証している。ソートマージジョインにおける影響要因の特定結果結合対象のデータサイズに拘わらずハッシュによる結合がソートベースの結合のパフォーマンスを上回っている。Figure 14ソートマージによる結合は入力サイズが著しく大きくなったときのみハッシュ結合のパフォーマンスに近づく。Figure 15ソートマージ、ハッシュ結合におけるデータの偏りはパフォーマンスに大きな影響を及ぼさなかった。Figure 16いずれのアルゴリズムも物理的なコア数では線形にスケールした。Figure 17作業時間read23:1123:11author27:093:58summary60:1232:57

マルチコアメインメモリにおけるソートジョインとハッシュジョインのパフォーマンスを検証した論文を読みました

この記事の趣旨2016年に発表された"An Experimental Comparison of Thirteen Relational Equi-Joins in Main Memory"という論文を読みました。様々な結合手法を包括的に比較した論文でどのような結合方法がどのような時に適しているかを示しています。An Experimental Comparison of Thirteen Relational Equi-Joins in Main Memory著者についてStefan Schuh、Xiao Chen、Jens Dittrichのグループによる論文。いずれもDBMSや分析システム、Hadoopなどにおける検索高速化・最適化の研究を行なっている。問題意識関係結合はほとんど全てのクエリプランにおいて中核をなす処理であり、定期的に研究・改良され再検討されてきた。新たな手法が提案され実験を行なわれるものの、それぞれ結果において比較を困難にする要素や幾らかの矛盾を孕んでいた。例えば同じハッシュベースの結合アルゴリズムの比較でも実装が異なったり、複数の論文でパフォーマンス比較で正反対の結果を示しているためである。そのため単純に論文執筆時点で最も高速な結合アルゴリズムを結論づけることが困難であった。手法本論文では結合方法を以下の3つに分類した1. パーティションベースハッシュジョインパーティションに分割し結合する手法。ハッシュテーブルの構築と結合されるデータの探索のキャッシュミスを最小にする事を目的としている。非パーティションベースハッシュジョインパーティションテーブルを構築しながら結合を行なう手法で、マルチスレッドと順番に依存しない実行によりキャッシュミスのパフォーマンス劣化を隠蔽している。ソートマージジョインSIMDによりベクトル化される。検証ではこれらの結合方法を以下の3つのテストで使用するために、全部で13のアルゴリズムを検証している。1. ブラックボックス比較ブラックボックス的に比較する。ホワイトボックス比較ブラックボックス比較で検証する結合方法に先行研究で示された最適化を施した上で比較を行なう。パラレルラディックスジョイン比較Table 2結果パーティション結合の一種であるリモート書込みを排除したCPR系アルゴリズムは小さな入力に対して有効ではないスケールの大きい結合ではとくに理由が無い場合、パーティションベースのジョインを利用する大きなサイズのページを利用するソフトウェアライトコンバインバッファ()を利用するパーティションジョインでは適切なパーティションビットを利用するできるかぎりシンプルなアルゴリズムを利用するNUMAを考慮したアルゴリズムを利用する実行時間とクエリ時間は同一ではない作業時間read31:3431:34author35:183:46summary77:5042:32

RDBでの結合手法を比較した論文を読みました

この記事の趣旨2018年に発表された"Everything You Always Wanted to Know AboutCompiled and Vectorized Queries But Were Afraid to Ask"という論文を読みました。最新のクエリエンジンの特性をまとめ、どのようなワークロードに向くのかという指針を示すないようです。Everything You Always Wanted to Know About Compiled and Vectorized Queries But Were Afraid to AskTimo Kersten, Viktor Leis, Alfons Kemper, Thomas Neumann, Andrew Pavlo, Peter Boncz著者についてTimo Kersten, Viktor Leis, Alfons Kemper, Thomas Neumann, Andrew Pavlo, Peter Bonczのグループによる論文。いずれも大規模データにおけるクエリパフォーマスや最適化に関する研究を行なっている。問題意識分析ワークロードに向いた最新のクエリエンジンはベクトル化またはデータ中心のコード生成に基づいている。どちらのモデルも従来のエンジンに比べオーバーヘッドが少く、非常に効率的なものの概念的には大きく異なっている。この2つのモデルの違いは、DBMSの実行エンジンのソースコードの構成とその性能特性を決定する基本的なもので、クエリ実行モデルを超える多くの設計で異なる。本論文はことなる2つのモデルを再実装し、環境差異のないマシンで実行することでそれぞれのモデルがどのように違うのか。どのような用途に最適なのかを検証している。手法検証手法は著者らがC++で再実装したデータ中心モデルの「Taper」とベクトル化中心の「Tectorwise」を同一のマシンでパフォーマンス検証を行っている。検証項目は以下から成る1. インメモリOLAPワークロードでのマイクロアーキテクチャ分析1. SIMDの利点の検証1. マルチコアCPUにおけるクエリ並列化1. 異なるハードウェアでのパフォーマンス結果インメモリOLAPワークロードでのマイクロアーキテクチャ分析Figure 3: Performance – TPC-H SF=1, 1 threadSIMDの利点の検証SIMDを評価するにはTectorwiseのみを用いた。SIMDではスカラーなデータをベクトルに変換するペナルティは少く、最大8.4倍の性能向上が確認された。Figure 6: Scalar vs. SIMD Selection in TectorwiseマルチコアCPUにおけるクエリ並列化異なるハードウェアでのパフォーマンスIntel Skylake、Intel Knights Landing、AMD Ryzenで対照実験を行なったものの、いずれのハードウェアでもTyper、Tectorwiseともに有効に動作した。作業時間read29:2629:26author33:233:57summary76:3742:44感想VoectorwiseとHyperのいずれを使うべきか。どちらが優れているかといった疑問に答えるないようだった。

コンパイルとベクトル化による最適化のパフォーマンスを比較した論文を読みました

この記事の趣旨2020年に提案された"Make the most out of your SIMD investments: counter control flowdivergence in compiled query pipelines"という論文を読みました。SIMDによるベクトル処理の最適化とRDBでの応用について扱った、最適化に関する論文です。Make the most out of your SIMD investments: counter control flow divergence in compiled query pipelinesHarald Lang, Linnea Passing, Andreas Kipf, Peter Boncz, Thomas Neumann, Alfons Kemper著者についてHarald Lang、 Linnea Passing、 Andreas Kipf、 Peter Boncz、 Thomas Neumann、 Alfons Kemperのグループによる研究いずれも最新のアーキテクチャでのクエリ最適化やデータ分析における検索手法などを研究している。問題意識CPUの発展にともないあたらしいCPUアーキテクチャが登場した。Single Instruction Multiple Data(SIMD)ではRDBはSIMDによるベクトル処理能力の向上により、クエリコンパイラの実行パイプライン全体をベクトル化して高度なデータ並列性の恩恵を受けることが出来るようになった。一方でクエリ全体をベクトル化して実行することで、SIMDによるクエリ評価が忙しくなる。SIMD評価で結果に寄与しない評価が単純にオーバーヘッドとなってしまう。手法本論文ではリフィルアルゴリズムとそのアルゴリズムをクエリパイプラインプランに統合する手法で上記の問題の解決を試みている。リフィルアルゴリズムは基本的に新しい要素を宛先レジスタの希望する位置にコピーするアルゴリズムで、メモリからレジスタとレジスタからレジスタへのコピーの2パターンが存在する。クエリパイプラインプランに統合するリフィル戦略ではConsume EverythingパターンとPartial Consumeパターンが存在する。Consum Everything戦略は、タプルをバッファリングするために使用される追加のベクターレジスタを割り当てる方法で利用率が低い場合、オペレータはこれらのタプルの処理を延期する。つまり、この反復ではボディは実行されず(条件が満たされない場合)、代わりにアクティブなタプルがこれらのバッファレジスタに移動することになる。Partial Consume戦略ではconsume()コードを入力の一部に適用する方法で、制御フローを前のオペレータに戻し、アクティブなデータ断片のみをベクトルレジスタに残すことで実行を延期している。作業時間read29:4029:40author33:404:00summary60:0426:36感想前回に引続き個人的には難しいと感じる論文だった。2000年前後の提案にくらべ、2015年前後の論文ではハードウェアアーキテクチャを中心とした手法がピックアップされている。単純に自分の知識不足、理解力不足なので勉強するしかない。

SIMDによるベクトル処理の最適化とRDBでの応用について扱った、最適化に関する論文を読みました

この記事の趣旨"Morsel-Driven Parallelism: A NUMA-Aware Query Evaluation Framework forthe Many-Core Age"という2014年に発表された、多コアサーバにおけるクエリ最適化手法をあつかった論文を読みました。[Morsel-Driven Parallelism: A NUMA-Aware QueryEvaluation Framework for the Many-Core Age](https://15721.courses.cs.cmu.edu/spring2023/papers/07-scheduling/p743-leis.pdf)Viktor Leis, Peter Boncz, Alfons Kemper, Thomas Neumann著者についてViktor Leis、 Peter Boncz、 Alfons Kemper、Thomas Neumannのグループによる研究いずれもデータベースと 高速化かを中心に研究している。問題意識コンピュータアーキテクチャの進化にともない、二つのあたらしい問題が生じた。多コアを利用するためにクエリを数百のスレッドに均等に分散させるそれをNUMA(Non-Uniform Memory Access)による順序通りではないメモリアクセスで実現する必要がある。これらの要因からplanベースの並列処理による不可分散とコンテキストスイッチとボトルネックが問題になりスケールが難しかった。NUMAによってデータとアクセススレッドがどのチップに配置されるかによって、データ項目のアクセスコストが異なるため、コンピュータ自体がネットワークになっており、多コア並列化では、RAMやキャッシュ階層を考慮する必要がある。この論文ではMoral-drivenクエリ実行フレームワークを提案している。手法提案手法は並列クエリ処理のため、morselドリブンクエリ評価フレームワークを提示した。これはメニーコア時代の分析クエリ性能の主要なボトルネックである負荷分散、スレッド同期、メモリアクセス局所性およびリソース弾力性を解決することを目的としている。ベースとなるアイデアは以下の2つに分けられる。メモリ上のデータをmorselと呼ばれる小さなバッチに分割し、バッチごとに処理を実行したあとにそれぞれの処理結果をグローバルハッシュテーブルとしてまとめる。Figure 3: NUMA-aware processing of the build-phaseディスパッチャと呼ばれる並行パイプライン制御を行ない、ワーカースレッドをタスクに割り当てるFigure 5: Dispatcher assigns pipeline-jobs on morsels to threads depending on the coreまとめとして著者はきめ細かいスケジューリング、完全演算子並列化、低オーバーヘッド同期、NUMA対応スケジューリングの原理を用いて、他のシステムでもメニーコアスケーリングを改善できると示唆している。作業時間read28:3628:36author32:453:09summary60:3727:52感想近現代のサーバアーキテクチャで主流になっているNUMAでのクエリパフォーマンス向上のための論文のため、古典的なものに比べ概念が難しいものが多い。もう少し理解を深めたい。

NUMAアーキテクチャでのクエリ最適化に関する論文を読みました

この記事の趣旨"MonetDB/X100: Hyper-Pipelining Query Execution"という2005年に発表された、列指向DBMSを提案した論文を読んでいきます。分析ワークロード向けRDBMSにおける初期実装であるMonetDBを扱った論文で、提案時期が2005年と古くはあるものの現代のDWHの礎となる内容です。MonetDB/X100: Hyper-Pipelining Query ExecutionPeter Boncz, Marcin Zukowski, Niels Nes著者についてPeter Boncz、Marcin Zukowski、Niels Nseのグループによる論文。いずれの著者も機械学習や分析におけるDBMSについて研究している。問題意識2005年当時のDBMSは他のアプリケーションに比べ、IPCが低くなる傾向にあった。原因はほとんどのDBMSがコンパイラの最適化を阻害する実装だったためである。これはRDBMSが実装された当時に比べCPUやコンパイラが発達したためで、この論文ではC-store DBMSであるMonetDBと従来のR-store DBMSをそれぞれTPC-Hで評価を行い、パフォーマンス阻害要件と最適化方法を提案している。手法CPUによるIF文の処理方法はDBMSにとっては選択性が低く、そういった実行は予測不可能でありクエリ実行を著しく劣らせた。提案手法ではMonetDB/X100として効率的なシーケンシャルアクセスに向けた、C-storeストレージとクエリエンジンを実装した。RAMは提案手法のデータアクセスと同様の方法で圧縮して保存し、Cacheではなベクトル化された処理にもとづくパイプライン実装を使用した。CPUにおいてもベクトル型における式計算を提供し、コンパイラが高効率な処理を生成した。結果として提案手法は従来のDBMS実行に比べTPC-Hで優れた性能をしめした。作業時間read21:3221:32author29:007:28summary56:2027:20感想2005年と古く、またVolcano-likeなど知らない概念も登場した。提案内容としては現代のDWHが採用しているものだった。論文外の感想今回本文を読む時間を大幅に短くしてみたが、それにともない理解度も低下した気がする。やっぱり30分以上で読むのがよさそう。

列指向DBMSにおけるデータを提案した論文を読みました

この記事の趣旨"Integrating Compression and Execution in Column-Oriented Database Systems"という2006年に発表されたそれまで行指向DBMSで培われてきた圧縮方法による、検索高速化手法を列指向DBMSに適用・評価した論文を読んで行きます。Integrating Compression and Execution in Column-Oriented Database SystemsDaniel J. Abadi, Samuel R. Madden, Miguel C. Ferreira著者についてDaniel J. Abadi、Samuel R. Madden、Miguel C. Ferreiraのグループ。それぞれDBMSやデータ分析に関連する手法やパフォーマンスについて研究している。問題意識2006年ごろの研究ということもありC-storeデータベースの研究が少なかった時期の論文。既に検索パフォーマンスに寄与することがしられていたR-storeデータベースの圧縮手法を、C-storeへ応用や評価を行なった。手法提案手法は以下の圧縮技術の組み合わせからなる。Null圧縮辞書エンコーディングRun Lengthエンコーディングビットベクターエンコーディングエンコーディングで、それぞれのカテゴリに属するかどうかをバイナリで表現する圧縮方法Lempel-ZivエンコーディングGZIPでも使用されている圧縮方式。データの非重複ブロックを解析して既存のデータは対応するブロックへのポインタに、それ以外のみを新規に追加する。提案手法は圧縮方式が増えてもアクセスパターンをシンプルに留めるためにアクセス方法をAPIとして隠蔽した。そのため異なるエンコーディングも同一のAPIで保存でき、同一のAPIでも取得できる。当然ながら一つのエンコーディングで全てのデータに対応することは難しく、論文では使用すべき圧縮スキームの選び方を以下のようにまとめている。Figure10感想C-storeにおける古典的な圧縮手法がまとまった論文だった。近代DWHを利用する側では意識することが少ない部分だったためあたらしい知識も多かった。作業時間read26:5026:50author33:306:40summary58:2024:50

列指向DBMSにおけるデータ圧縮手法の論文を読みました

この記事の趣旨前回と同様にCMU Advanced Databas Systems Spring2023のReading Assignmentとして出ている論文を読んで行きます。最近論文を読めてなかったのですが、この記事でモーベーションが上がったので再開しました。ころころやり方を変えるのはよろしくないものの、モチベーションのために先の記事のやり方でやります。今回はColumn Sketchという名前のIndex手法を提案した論文です。Lossy Compressionを採用した当手法がどのように、高速で堅牢な検索を実現しているのかについて述べています。Column Sketches: A Scan Accelerator for Rapid and Robust Predicate EvaluationBrian Hentschel, Michael S. Kester, Stratos Idreos著者についてBrain、Michael、Stratosのグループによる論文。いずれも機械学習とデータアクセスについて研究している。問題意識既存のindex手法ではそれぞれに得意/不得意があり多くのアクセスパターンに対応できる方法がなかった。またデータ分析で用いられるような列指向ストレージに対応しているものが少なかった。Column SketchはデータをLossy Compressionを使用してindexを作成する手法でこれらの問題を解決した。手法提案手法はデータを任意のbit長に変換し、bitで表わされたデータに対して初回の検索を行なうことで大幅に検索速度を向上させた。またこの手法は数値型のみではなく、varcharなどで表わされたカテゴリカルタイプを数値として扱うことで、データ分析に必要なデータタイプに対応している。提案手法は8bit数値型であれば以下のようなマッピングによって達成される。for x, y ∈ I8, S (x) ≠ S (y) ⇒ x ≠ yfor x, y ∈ I8, S (x) < S (y) ⇒ x < y以下の図は8bitデータに対してWHERE x < 90がどのようにindex作成され評価されるかの例である。Figure2: Column Sketchindex作成段階では数値をレンジベースで任意の個数のbitに圧縮する。そして評価時には90を含むデータより大きい値をすべて取得し、90を含むレンジに対しては個別に評価を行なう。感想読んでいる段階では数値型のみに対応したindexであれば、B-treeで十分ではないかと思ったものの読み進めていくと限定的ながらも文字型にも対応していて、分析用途では必要な機能が備わっているなと思った。全文テキスト検索のような用途には応用が難しそうで、銀の弾丸はないなと感じた。作業時間read27 min27 minauthor32 min5 minsummary58 min26 min論文以外への感想今回採用した論文の読み方をやってみた思ったのは事前に1時間で読んでまとめるぞと決めたことで随分集中して論文を読めました。あと今まで論文を原文で読まなきゃという個人的な使命感があったのですが、翻訳することで随分効率があがったので今後は翻訳してしまおうと思いました。Readableは文末のrea-dableのような表記や翻訳されない部分(おそらく数式を含む文章？)があるものの、フォーマットが維持されているため原文と照しあわせながら読めば非常に効率がよかったです。毎日論文読むなら正直買いです。毎日論文読みたいので課金しました。がんばるぞ!

Column Sketchesというindex手法の論文を読みました

この記事の趣旨前回と同様にCMU Advanced Databas Systems Spring2023のReading Assignmentとして出ている論文を読み論文紹介のやり方 / How to reviewで紹介されている方法をまとめていきます。今回はBigQueryやSnowflake、Amazon Redshiftといった分析向けデータベースが採用している行指向ストア(Column-store)と列指向ストア(Row-store)の差と行指向ストアがのどうのような最適化がパフォーマンスに影響を与えているかについて扱った論文を読んで行きます。Column-Stores vs. Row-Stores: How Different Are They Really?研究全体の背景行指向データベースシステムは分析用ワークロードで列指向データベースシステムより優れたパフォーマンスを発揮することで知られている。なぜなら行指向ストアはクエリ実行に必要なデータのみをディスクまたはメモリから取得するため、優れたI/Oパフォーマンスを達成できるからである。問題意識垂直パーティショニングや全ての行をパーティショニングすることで、列指向データベースで行指向データベースのようなパフォーマンスを実現できるだろうか？ また行指向データベースが高速に動作するのはどのような最適化手法の影響が大きいのか？論文の目的列指向データベースで垂直パーティショニングやクエリ実行で使われる全ての行にインデックスを張るなどして、擬似的に行指向データベースを再現することで分析用途でのパフォーマンスが向上するのか？ また行指向データベースの高速化に用いられるテクニックを一つずつ無効化し、パフォーマンスを比較することでどのような要素が行指向データベースのパフォーマンスを向上させているかを検証しする。手法の説明Star Schema Benchmarkを用いてC-Storeと商用列指向データベースの比較を行う。リアライゼーション、ブロックプロセッシングをそれぞれ無効化しどの要素の影響が最も大きいか。またこの論文で提案されたinvisible joinの評価を行なう。結果列指向ストアに置けるマテリアライズトビューリアライズドビュー(MV)に比べ非常に優れたパフォーマンスを発揮する。一方でCSの一つの行にMVとして期待するアウトプットのタプルをStringとして保存すると、普通のRSよりも低いパフォーマンスとなる。 RS MV > RS > CS MVとなる。列指向ストアに行指向ストアを再現する一般的な列指向のアプローチを適用し、効果的であればbitmap1またはbloom filter2を適用する(T)一般的な列指向のアプローチを適用するが、bitmapを積極的に使用する(T(B))一つのテーブルを複数のテーブルとして垂直分割を行う(VP)全ての行にインデックスを貼り、値の読み込みは全てインデックス経由で行う(AI)結果としては平均してMV > T > T(B) > VP > AIとなる。列指向ストアに置ける最適化手法とその影響列指向ストアの最適化手法においてどの影響が大きいかを測定するためそれぞれを無効化することで検証を行なう。測定対象の最適化項目としては以下の4つを対象とする。ブロックプロセッシングの有効化(B)または無効化(b)Invisible joinの有効化(I)または無効化(i)保存時のデータ圧縮の有効化(C)または無効化(c)遅延マテリアライゼーションの有効化(L)または無効化(l)結果は平均するとBICL > bICL > BiCL > biCL > BicL > bicL > biclとなる。まとめと考察既に知られていたように行指向ストアは列指向ストアに対して常に優れたパフォーマンスを発揮した。リアライゼーションとデータの圧縮はパフォーマンスの改善に大きく影響した。ブロックプロセッシングやInvisible Joinも上記の二つに比べると影響は小さいものの最適化として有効に働いた。Oracle Document 索引↩Bloom Filters↩

行指向と列指向の違いについての論文を読む

この記事の趣旨前回と同様にCMU Advanced Databas Systems Spring2023のReading Assignmentとして出ている論文を読み、感想と抄訳のようなものにまとめます。まとめていたのですが、そもそも全体をまとめてしまっていいのか？ 文量もふえてしまうので論文紹介のやり方 / How to reviewで紹介されている方法を参考にやっていきます。ただし実装論文が対象なので手法の説明は厚めにとりあげ、結果については省略します。今回は近年DWHとして存在感を増しているSnowflakeがどのようなアーキテクチャを取っているか、そしてどのように分散システムの上にデータベースシステムを構築しているかについての内容になります。https://15721.courses.cs.cmu.edu/spring2023/papers/02-modern/vuppalapati-nsdi22.pdfBuilding An Elastic Query Engine on Disaggregated Storage研究全体の背景Cloud技術をベースとしたデータウェアハウス(DWH)であるSnowflakeの運用経験に基づいた論文。Snowflakeは計算リソースとストレージの柔軟性、マルチテナント、高いパフォーマンスを目的にデザインされている。この論文ではSnowflakeが設計と実装においてどのようにCloud技術を応用し目的を達成しているかについて書かれている。問題意識既存のクエリ実行エンジンやDWHではShared-nothing方式を採用することでデータをノードに分散させ、処理をスケールさせたり高いパフォーマンスを実現していた。一方でワークロードによって要求のことなる各種コンピュータリソースを適切に分配することが難しい、Shared-nothingによる静的にパーティションされたデータでは要求によってノードを増減させることが難しいという問題があった。論文の目的SnowflakeがどのようなアーキテクチャによってShared-nothingが抱える問題を解決し、またクエリプランニングと最適化、同時実行制御を行っているのかの実装をまとめ、紹介している。手法の説明設計の概要Snowflakeでは永続(persistent)データと中間(intermediate)データで扱かいを変えている。Figure1: Snowflake (Virtual) Warehouse Architecture一時ストレージの設計SSDで構成されている。一時データは可能な限りメモリに保存されメモリで保持しきれないデータはスワップ領域のようにSSDに保存される。さらにSSDの空き容量が枯渇した場合、一時的に永続ストレージに保存される。一時ストレージは永続化が不要なデータの保管以外にも永続化データのキャッシュとしても機能する。このキャッシュは日和見的(opportunistically)キャッシュと呼ばれており、その理由は中間データを常に優先するからである。クエリスケジューリングユーザーからのクエリはサービスエンドポイントでパース、実行計画の生成、最適化、実行に必要タスクの生成が行なわれ、ここで生成されたread/writeを含むタスクは計算リソースに割り振られ、計算リソースから必要に応じて一時、永続ストレージからのデータ取得が行なわれる。このときタスクの割り振りは一時ストレージが対象の永続データをキャッシュしているかも考慮される。またSnowflakeは Work stealingという他ノードに割り振られたタスクをあるノードの方が速く処理できる場合、臨機応変にタスクを実行するしくみがある。リソースの柔軟性ストレージと計算リソースを分離することでSnowflakeはそれぞれを独立してスケールアウトさせている。ストレージの柔軟性はデータストアであるS3に委任している一方で、計算リソースの柔軟性は事前に暖気運転されたノードプールによって実現している。Snowflakeでは永続データのキャッシュ時に保存されるノードが決っている一方で、対象となるデータをキャッシュするノードがない場合、一時的にほかのノードにタスクを割り振り計算リソースがスケールし対象となるデータがキャッシュされた時に再度タスクを割り当てるという機能が存在する。まとめと考察SnowflakeはS3を永続ストレージとして使用、VM全体を計算リソースとそのメモリ、スワップ領域とみなすことでスケーラビリティと高いパフォーマンスを実現した。とくに日和見的キャッシュとタスクスケジューリングメカニズムはShared-nothing方式の抱えていた、リバランスの問題を解決した。Snowflakeが現在達成できていないマルチテナントや計算リソースの高いユーティリゼーションの実現方法としてあげている手法をとっているため、今後の機能追加が競争力維持のために重要となる。

Snowflakeの論文を読む

CMU Advanced Database Systems Spring2023のReading Assignmentを読む part1

SQL*Loaderで複数の文字コードが混ざったデータをロードする 概要単一のテキストファイル内で特定のカラムのみ文字コードが違うファイルをSQL*Loaderでデータベースに取り込む方法 注意本記事で扱っている対処方法はおそらく紛れ込んだ文字コードが本来あるべき文字コードの一部として解釈できない場合使用できないと思います。(未検証)最低限文字化けしながらも読み込める状態を想定しています。 結論コントロールファイル内で文字コードの変換が必要なカラムに以下の関数を適用する。column "CONVERT(:column, 'target_charset', 's...

SQL*Loaderで複数の文字コードが混ざったデータをロードする

Oracleインストール中にでたSysctl系エラーであたったkernel parameterについてTable of ContentsOracleインストール中にでたSysctl系エラーであたったkernel parameterについてMotivationそもそもsysctlとは何なのか？Oracleセットアップ中に遭遇したkernel parameterssemopm変更方法セマフォ(semaphore)とは？SEMSMLSEMMNSSEMOPMSEMMNIfile-max変更方法rem_default/rem_max/...