自己設計システムとは、システム内の選択可能なプリミティブから、データベースのワークロードとハードウェアに最適な組み合わせを自動的に生成するという概念のものです[1]。今回は、この自己設計システムのコンセプトの著者の、キーバリューストアを題材とした直近の論文を紹介してみます[2]。 自己設計によるカスタマイズ (Customization through Self-Design)とは? 自己設計(Self-Design)は中世の原子論的に、基礎となる設計要素を組み合わせ、最適な組み合わせとなるシステムを構成する概念のものです。選択可能なプリミティグには、ハードウェアだけではなく、分散システムのパーティショニング方法(例: ハッシュ分割、レンジ分割)やデータアクセス方法(例: スキャン、ソート済検索など)などのソフトウェア(アルゴリズム)も含まれます [3]。 自己設計による最適化手法には、学習コストモデルを用いた最適化や機械学習が用いられ、新しい組み合わせが未知のアルゴリズムやデータ構造を生み出すことで、パフォーマンスを大幅に向上させる可能性があります[1][3]。本論文では、具体的な評価対象システムとしてキーバリューストアを題材に、自己設計(Self-Design)における手法を提案しています。 キーバリューストアとは？ キーバリューストアは、キーと値のペアを格納するデータ構造を実装したものです。キーバリューストアは、ソーシャルメディアのグラフ処理、アプリケーションデータのキャッシング、NoSQLストレージ、オンライントランザクション処理などの、多種多様なアプリケーションの基盤として活用されています[2]。 また、近年のリレーショナルデータベースであるGoogleのSpannerや、RockDBをMySQLのバックエンドストレージとしたMyRocks、FoundationDBをバックエンドストレージとしたデータウェアハウスのはSnowflakeなども、バックエンドにキーバリューストアが採用されています [2][5]。 主要なKey-Valueデータ構造 キーバリューストアのデータ構造については、読み取り・書き込み・メモリ消費量には常にトレードオフが存在し、この３つ全てを最適とするデータ構造は存在しません[2]。結論としては各目的に応じたデータ構造が必要となるのですが、現時点で代表的なデータ構造として、B+Tree、LSMツリーなどが存在しています。 B+Tree B+Treeは、RDBMSやファイルシステムでも採用されている主要なツリー構造で、合理的なメモリ消費量で読み取りと書き込み性能のバランスに優れ、現在はOracleの製品であるBerkeleyDBや、近年でもMongoDBの標準ストレージエンジンとなったWiredTiger、FoundationDBなどのキーバリューストアに採用されています。 LSMツリー LSMツリー(Logs-structured merge-tree)は、高速な書き込みと読み取り性能を共存させるデータ構造で、GoogleのLevelDBやBigTable、FacebookのRocksDB、Apache CassandraやHBase、さらにはMySQLやSQLiteなどのRDBMSの主なキー管理などにも採用されています。ただし、B+ツリー構造より書き込み性能は優れますが、読み込み性能は悪化する場合があります。 その他 (LSHテーブル、ハイブリッドな構成など) 近年はRiakのBitCaskやSpotifyのSparkeyに用いられているLSHテーブル(Log-Structured Hash-table)などの新しい構造もあります。また、アプリケーションに適切なパフォーマンスを提供するため、複数のデータ構造を排他的に提供する場合もあります。例えば、MongoDBのWireTigerでは、B+TreeとLSMツリー実装を排他的に個別にサポートしており、RocksDBでは部分的にハッシュテーブル構造を取り入れて最適化しています。 多くの最新のキーバリューストアは、相互に排他的なスワップ可能なデータレイアウト設計のセットで構成され、多様なパフォーマンス特性を提供します。たとえば、WiredTigerはBツリーとLSMツリーの実装を個別にサポートして読み取りまたは書き込みをそれぞれ最適化しますが、RocksDBファイルはソートされた文字列レイアウトまたはハッシュテーブルレイアウトをサポートして、範囲の読み取りまたはポイントをさらに最適化しますそれぞれ読み取ります。 自己設計(Self-Design)の目的 自己設計(Self-Design)の長期的な研究課題は、例えば前述のキーバリューストアの場合、対象の問題に最適なデータ構造を、簡単または自動的に選択できるかが重要な課題となります。自己設計は、対象となるドメイン知識となる原則を導き出すことを目的としており、今回の論文では、自己設計を実現するものとして、連続体(Design Continuums)の概念を提唱しています。…

Read more

最近、「人工現実感の世界[1]」のリニューアル版として「VR原論[2]」の刊行がありました。時期的には、1990年にホールアース研究所により開催されたサイバーソン(Cyberthon)[3][4]前後の、当時のVRの雰囲気をまとめた書籍です。 「人工現実感の世界」は、VR黎明期当時のVRを取り巻く状況を取材したものであり、その刊行時期において「思考のための道具」などでも著名なラインゴールド(Howard Rheingold)氏の「Virtual Reality(邦訳:バーチャル・リアリティ)[5][6]」に匹敵する、VR黎明期の状況をまとめた先駆的な書籍であると思います。 「VR原論」では、「人工現実感の世界」が発刊された1990年前後の状況についての対談形式での補足があり、今回の記事はその対談に触発されてものです。私自身も「人工現実感の世界」の発刊に感銘をうけた世代でもあり、なんとも懐かしく読んでしまいました。 「VR原論」の冒頭にもありますが、黎明期のVRが忘れ去られているのは、驚きでもあり残念でもあります。考えてみれば、VR黎明期は、いまのようにインターネットやデジタルカメラが普及しておらずデジタルコンテンツは残りづらく、「人工現実感の世界」がそうであったように書籍も絶版になっているため、致し方ないことかもしれません。 私自身は、1990年代のVR黎明期から2000年のVRML盛衰頃までは、仕事も趣味もどっぷりVR/3Dに浸かった生活だったのですが「HMDとグローブをしながらプログラミングしていた」なんて話をすると驚かれてしまい、こちらも驚いてしまいます。 今回は「人工現実感の世界」の発刊以降の1991年から、インターネットが普及する1995年ぐらいまでの、VR黎明期の失われた時代の状況を、手持ちの資料や関連書籍を参考にしつつ、振り返ってみたいと思います。 「Reality Engine Builders」たちのその後 「人工現実感の世界」は、1990年前後の米国と日本のVRの状況を取材した書籍で、その中に「Reality Engine Builders」として紹介されている米国のVRベンチャーが紹介されています。以下の写真は、その当時よく引用されていたVR黎明期のNASAエイムズ研究所の写真[10]でNASAのHMDとVR原論に登場するVPL社のデータグローブを装着しています。まずはVR原論で紹介されていたベンチャーのその後を補足してみたいと思います。 VR原論に登場する米国のVRベンチャーは、いずれも低価格のVRシステムやVR専用のSDK(Software Development Kit)の商用販売に挑戦していきます。 ただ、結末としては、これらの米国のVRベンチャー達は、1995年以降のPC/3Dグラフィックス性能の劇的な向上および、OpenGLやDirect3Dなどの3DAPIの標準化の影響もあり、彼らのVR専用システムおよびSDK(独自3DグラフィックスAPI + VRデバイス対応)は、徐々に姿を消すことになります。 VPL Research 実質的な活動期間は短かったとしても、VPL (Virtual Programming Languages) Researchおよび、ジャロン(Jaron Lanier)氏が、現在につながるVR(Virtual Reality)の概念および名称を一般にさせ、黎明期のVRブームの立役者であることは、皆さんの異論のないところだと思います。 世界初となるデーターグローブやアイフォンを商品化したVPL…

Read more

MongoDB プロトコル実装調査 – v3.6移行の現状について MongoDBは、DB-Enginesの2019年8月のランキング[1]で第5位と、近年でも安定した人気を得ているドキュメントデータベースです。また、マイクロソフトのCosmosDBや、FoundationDBの「Document Layer」に代表されるように、既存のデータベースでもMongoDBインターフェースを互換APIで対応する動向も見受けられます[2][3]。 ただし、2019年8月現在、MongoDB公式の最新バージョンは4.0系であるにも関わらず、CosmosDBはv3.2ベース、Document Layerはv3.0ベースの実装に留まっています。 今回は、このようなMongoDB互換APIの実装背景を理解する上で必要となる、MongoDBの基本通信プロトコルであるWire Protocol[4]の概要と、MongoDB公式のv3.6以降の通信プロトコル実装状況についての調査結果をまとめてみます。 MongoDB Wire Protocolの概要 MongoDB Wire Protocolは、MongoDBの基礎となる要求応答の通信プロトコル仕様です。 MongoDBクライアントは、TCP/IPソケットでMongoDBサーバーと接続し、この基本プロトコルを用いて通信しています。 共通ヘッダ MongoDBの通信プロトコルのWire Protocloでは、通信メッセージの共通ヘッダが規定されています。共通ヘッダは、メッセージ総合計バイト数(Message Length)、メッセージ要求識別子(RequestID)、メッセージ応答識別子(ResponseTo)、メッセージ種別(OpCode)の4種類の整数(int32)から構成されます。 メッセージ総合計バイト数(Message Length)のデータ形がini32であるため、仕様的には2GB以上のデータの送受信にはメッセージの分割必要となります。MongoDB公式の標準的な実装としては46MB(48,000,000byte)[5]程度を上限としているようです。 なお、Wire Protocloの整数型は、TCP/IPヘッダのバイトオーダーとは異なり、リトルエンディアン順序での送受信となります。エンディアン選択については、BSON仕様[6]と同じ経緯で、実装効率メインで仕様が決定された感があります。 メッセージ種別 (OpCode) MongoDBのメッセージ種別(OpCode)は、廃止(Deprecated)されたものを含めると、現在まで以下の11種類の送受信メッセージが規定されています。 OpCoce 値…

Read more

最近ある時系列データの因果関係が分析できればと、手始めに時系列データの相関解析やクラスタリングの手法を調査しています。 今回は、時系列データクラスタリング手法の動向と、2015年に論文が発表された正規化相互相関手法を用いた形状ベース(Shape-based)の時系列クラスタリング手法であるk-Shape[3]についてまとめてみます。 クラスタリングとは？ クラスタリングとは、対象となるグループに対する高度な知識がなくとも、類似のデータを関連するグループや同種のグループに分割するデータマイニングの手法です。クラスタリングは、科学的データの探査、情報検索とテキストマイニング、CRMやマーケティング、医療診断などの、データマイニングの手法として実用的に用いられています [1]。 研究的な観点からも、クラスタリングは、統計、パターン認識、機械学習などの分野で、現在も活発に研究されています。機械学習的な観点では、クラスタリングは一般的には教師なし学習であり、クラスタリングは、多様な属性を持つ膨大なデータセットを分類したり、潜在するパターンの発見に役立ちます[1] [2]。 k-meansとは k-means(k-平均法)は、現在、科学および産業分野で最も広く使用されているクラスタリングアルゴリズムです。名称は、クラスタの平均（または加重平均）を用いてk個のクラスタに分類する手法に由来しています[3]。 クラスタリングにおいて、すべての可能な組み合わせを確認することは計算上実行不可能(NP困難)な問題です。k-meansは、貪欲法的に局所的最適解を求めて、それを反復して最適化する手法です。 具体的には、k-meansは対象データを表す点を、最初にランダムにk個のクラスタに割り当てます。各クラスタに含まれる点の平均を計算した後に、各クラスタのメンバーが不変になるまで、以下の2つのステップを反復して実行します。 STEP1 : 各対象データを、その重心に最も近い重心のクラスタに移動 STEP2 : 各クラスタの平均を再計算 反復による最適化は、各クラスタのメンバーに移動がなくなり収束した場合、または最大反復回数に達した場合に終了します。 時系列クラスタリングとは クラスタリングの手法は、時系列データの解析にも用いられており、主に時系列データセット内の潜在的、興味深いパターンの発見に利用されます。解析事例としては、株価などの時系列間の相関検出、天気予報などの関数近似と組み合わせた予測、店舗などのアイテム間の関連性の検出などがあります [2]。 時系列クラスタリングの手法 時系列クラスタリング手法を大別すると、モデルベース(Model-based)、特徴ベース(Feature-based)、形状(Shape-based)ベース手法および、その組み合わせの手法に大別されます。以下の図に、各手法に用いられるコンポーネントを示します [2]。 モデルベース(Model-based) モデルベースの手法は、時系列データを対象のモデルデータのパラメータに変換し、モデルで定義されている距離関数および(通常は従来の)クラスタリングアルゴリズムにを用いています。一般的に、モデルベースの手法はクラスタが接近している場合に性能が劣化するなど、スケーラビリティの問題が指摘されています [2]。 特徴ベース(Feature-based) 特徴ベースの手法は、時系列データが低次元の特徴ベクトルに変換され、、従来のクラスタリングアルゴリズムが適用されます。一般的に特徴ベクトルは正規化されており、ユークリッド距離などを用いたクラスタリング手法が用いられます [2]。…

Read more

最近、RDMBSの通信プロトコルに興味があり、代表的なPostgreSQL・MySQLの通信プロトコルの調査をしています。今回は、とくに興味があった問い合わせ(Query)とその応答の通信プロトコルについて整理してみます。 取っ掛りとなる調査ではありますが、その通信プロトコル仕様から、PostgreSQL・MySQLそれぞれの設計思想的なところも垣間見れ、興味深い調査となりました。端的に言えば、PostgreSQLは高速かつ合成的で合理的、対するMySQLの仕様は厳密で冗長的な設計の印象を持ちました。 RDBMSの質問(Query)操作とは RDBMSへ対する操作は、質問(query)と更新(update)に大別されます。RDBMSの基礎となるリレーショナル代数は、前者の質問操作を対象とするものであり、挿入(insert)や削除(delete)などは後者の更新処理に含まれます[1]。 リレーショナル代数の質問は再帰性(recursiveness)があり、その結果は再びリレーショナルとして表現されます。この結果を表すリレーションを、リレーショナル代数では結果リレーション(result relation)、SQLでは導出表(derived table)と呼ばれています[1]。 すなわち、質問(query)操作についてはリレーショナル代数の結果リレーション相当の情報が含まれる必要があります。 通信プロトコル PostgreSQL・MySQLともに通信プロトコルの基本となる通信パケットが定義されており、通信パケットに含まれるデータについても基本となるデータ型が定義されています。 通信パケット 通信パケットは、PostgreSQL・MySQLともに通信プロトコルの基本となるパケット形式で、全ての通信プロトコルは、このパケット仕様に準じています。 PostgreSQL・MySQLともに通信パケットのサイズを示すメッセージ(ペイロード)長が含まれています。以下の表に示す通り、相違点としては、PostgreSQLがメッセージ種別からパケットが開始されるのに対して、MySQLのメッセージ種別はペイロード部に含まれています。 項目 PostgreSQL MySQL メッセージ種別 byte<1> – ペイロード長 int<4> int<3> シーケンス番号 – int<1> ペイロード string<var> or binary string<var>…

Read more

昨年から今年に入り、マサチューセッツ工科大学とGoogleなどの共著で、SageDBなどの機械学習によるデータベース最適化の論文が発表されています[1][2]。現時点では研究レベルの論文ではありますが、将来のデータベース在り方について色々な示唆に富んでいる論文です。 今回は、この論文の主要コンセプトである「学習によるカスタマイズ」に関連する話題にふれ、今後のデータベース像について考えてみます。 データベース最適化の背景 データベース最適化の研究については長い歴史がありますが[1][5]、SageDBの論文[1]では、(データベースを含む)既存のデータ処理一般の最適化(カスタマイズ)手法を以下の３種類に分類しています。 設定によるカスタマイズ　(Customization through Configuration) まずは、最も馴染み深いであろう、データーベースのコンフィグ設定やシステム設定変更による最適化です。具体的な例としては、各データベースのページサイズ、バッファプールサイズの調整などが該当します。広義的な意味では、インデックスやマテリアライズド・ビューの作成も含まれますが、基本的には静的なカスタマイズ手法と位置付けられています。 設定によるカスタマイズについては、データベースへのワークロードやデータ特性から設定値を自動的に最適化する先行研究が数多くあり、近年では機械学習をデータベースに応用した汎用的な最適化の研究もあります[4]。 アルゴリズム選択によるカスタマイズ (Customization through Algorithm Picking) 前述の静的な「設定によるカスタマイズ」に対して、動的な実行戦略の選択によるクエリー最適化の手法で、データベースの主要な研究の分野として長い歴史があります[1][5]。具体的な例としては、クエリー最適化は、オプティマイザにより最適な実行順序（例：述語プッシュダウン、結合順序など）を決定し、利用可能な一連のアルゴリズムから最良の実装を選択（例：ネステッドループ結合、ハッシュ結合など）するものです。 この最適化手法は、実行前にそのコストを推定するため、コストに基づく最適化(cost-based optimaization)とも呼ばれ、コスト推定には統計的な手法の基づくものが広く実装されています[5]。 自己設計によるカスタマイズ (Customization through Self-Design) 自己設計システムとは、システム内の選択可能なプリミティブから、データベースのワークロードとハードウェアに最適な組み合わせを自動的に生成するという概念のものです [3]。選択可能なプリミティグには、ハードウェアだけではなく、分散システムのパーティショニング方法(例: ハッシュ分割、レンジ分割)やデータアクセス方法(例: スキャン、ソート済検索など)などのソフトウェア(アルゴリズム)も含まれます [3]。 この最適化手法には、学習コストモデルを用いた最適化が用いられており、新しい組み合わせが未知のアルゴリズムやデータ構造を生み出すことで、パフォーマンスを大幅に向上させる可能性もあるとされ[3]、今回のSageDB[1]の論文と合わせて興味深い概念です。 SageDBとは？ 現代のデータベース(原文:データ処理システム)は、多種多様なスキーマ、データ型、およびデータ分散を処理できるように汎用的に設計されています。その反面、その最適化については、前述の「アルゴリズム選択によるカスタマイズ」(=コストに基づく最適化)に基づくものが多く、特定のワークロードやデータ特性に対して適応できない可能性があります[1][2]。 SageDBでは「学習によるカスタマイズ」と名付けられた、既存のデータベース(原文:データ処理システム)のアルゴリズムとデータ構造に(機械学習の)モデルを深く埋め込むことによる最適化手法を提案しています。…

Read more