JP6280000B2 - データベース装置およびその動作方法 - Google Patents

Description

本発明は、データベース装置およびその動作方法に関するものである。

近年のＩＴの発展に伴い情報システムで取り扱うデータ量が増大しており、１台のデータベース装置では性能や記憶容量が不足するほどデータ量が多くなるケースもみられるようになってきた。そこで、複数のデータベース装置にデータを分散収容して、複数のデータベース装置をひとつのデータベースとみなせるようにする分散データベースが研究・開発されている。データを複数のデータベース装置に分散させることはシャーディングと呼ばれている。

シャーディングにおいて、データとデータを収容するデータベース装置の対応付け方法は種々あるが、そのひとつとしてデータのキー値の範囲に応じて収容装置を決めるキーレンジ分割がある。キーはデータを一意に識別する属性である。たとえば、電話番号に関するデータベースでは、電話番号をキーとすることが行われる。多くの場合、キーは人がデータを言い表す際によく使われる属性であるので、キーレンジ分割はシステム管理者にとってデータとデータベース装置との対応関係を理解しやすいシャーディング方法であると言える。

キーレンジ分割された分散データベースでデータ操作を行うためには、キーの範囲とデータベース装置との対応関係を管理する必要がある。本稿ではキーからそのキーを収容するデータベース装置を特定することを分散解決と呼ぶ。データの操作を行うためにはキー範囲とデータベース装置との対応関係を知っている必要がある。キー範囲とデータベース装置との対応関係を表すデータを本稿では分散解決データと呼ぶ。本稿では、分散データベースシステムの個々のデータベース装置が分散データベースシステム全体のデータの分散解決データをデータベース内にテーブルとして保持し（共有し）、任意のデータベース装置が外部からデータ操作の要求を受け付け、データ操作要求を受け付けたデータベース装置が分散解決データテーブルを索引することで分散解決を行い操作対象のデータを収容するデータベース装置を特定し、データ操作要求を受け付けたデータベース装置がデータを収容するデータベース装置へ実際のデータ操作を要求するような分散データベースシステムを仮定する。

通常、分散データベースシステムはデータベース装置を追加し収容データ量の限界を引き上げること（スケールアウトと呼ばれる）を可能とする仕組みを有する。シャーディングにキーレンジ分割を用いている場合には、既存のデータベース装置と新規のデータベース装置との間でキー範囲の割り当てを変更し、新規のデータベース装置に割り当てられたキー範囲に既存のデータがある場合には既存のデータベース装置から新規のデータベース装置にデータを移動する必要がある。

データベースの使い方は用途に応じて様々であるが、単にひとつのキー値からキーに対応するひとつのデータレコードを取得する使い方だけでなく、なんらかの関連がある複数のデータレコードのグループを管理することも広く行われる。たとえば、電話回線管理システムにおいて、ひとつの収容装置に収容されている回線をひとつのグループとしてデータベースにて管理することが行われる。

鶴見俊輔、阿部健二、徳永茂樹、佐々木潤子「大規模分散DBシステムにおけるデータ管理方式の一検討」電子情報通信学会ソサイエティ大会B-6-80, 2013.

非特許文献１にシャーディングにキーレンジ分割を用いて、データベース装置間のキー範囲割り当て変更に伴うデータの移動の際にメモリ空間の断片化が起きないような分散データベースの実現方法が示されている。この方法では、データレコードを格納するメモリ領域である実データレコードテーブルと、実データレコードテーブル中のレコードの位置を示すインデックスと、あるキー範囲に属する実データレコードを指し示すインデックスのグループを格納する「INDEXテーブル」と呼ぶデータ構造を用いる。ひとつのキー範囲に複数の「INDEXテーブル」が対応し、キー範囲割り当て変更に伴うデータベース装置間のデータの移動は「INDEXテーブル」単位で移動される。「INDEXテーブル」のサイズ（「INDEXテーブル」に収容可能なインデックス数）を一定にすることで、「INDEXテーブル」を移動しても「INDEXテーブル」のメモリ領域が断片化することを避けることができると主張されている。

キー範囲が同一である複数のテーブルがある場合には、ひとつのキー範囲に割り当てる「INDEXテーブル」数をそれらのテーブルで同数にしてもよいし、テーブルごとに異なる数の「INDEXテーブル」数を割り当てることもできるであろう。

非特許文献１の方法では、「INDEXテーブル」を同一サイズとするため、「INDEXテーブル」内のインデックス数が「INDEXテーブル」のサイズに満たない場合、「INDEXテーブル」のメモリ領域に無駄が生じるという問題がある。ひとつのキー範囲に割り当てる複数のテーブルに対し同数の「INDEXテーブル」を割り当てる方法を用いる場合には、キー範囲内に収容されるデータレコード数がテーブル間でばらつくと「INDEXテーブル」のメモリ領域の無駄が一層著しい。

本発明は、上記の課題に鑑みてなされたものであり、その目的とするところは、データベースにおいてメモリの消費を低減しつつ関連する複数のデータレコードグループを管理する技術を提供することにある。

上記の課題を解決するために、第１の本発明は、データベース装置であって、実データを含むレコードが実データインデクスに対応づけて記憶される１以上の実データテーブルと、実データに対応するキーを複数含む範囲を示すキー範囲情報と前記実データテーブルごとのキャビネットＩＤを含むレコードが記憶される分散解決データテーブルと、キャビネットＩＤとキャビネットテーブルに含まれるひとつのレコードの格納位置を示すキャビネットインデクスを含むレコードが記憶されるキャビネット管理テーブルと、実データインデクスと次インデクスを含むレコードが記憶される前記キャビネットテーブルと、前記キャビネットテーブルのレコードを連結してリストを構成する手段と、前記キャビネットテーブルのレコードのリストにキャビネットテーブルのレコードを挿入してリストを延長する手段と、キーを含むデータ操作信号を受信する手段と、前記分散解決データテーブルから当該キーを含む範囲を示すキー範囲情報を含むレコードを検索し、当該実データを記憶すべき実データテーブルのキャビネットＩＤを読み出す手段と、前記キャビネット管理テーブルから当該キャビネットＩＤに対応するキャビネットインデクスを読み出し前記キャビネットテーブルから当該キャビネットインデクスに対応するレコードを検索する手段と、該検索されたレコードを含むリストにキャビネットテーブルのレコードを挿入して該リストを延長し、該挿入されたキャビネットテーブルのレコードに実データインデクスを格納する手段と、前記受信された実データを記憶すべき実データテーブルにおける当該実データインデクスに対応する位置に前記受信された実データを含むレコードを追加する手段とを備えることを特徴とする。

第２の本発明は、データベース装置の動作方法であって、前記データベース装置は、実データを含むレコードが実データインデクスに対応づけて記憶される１以上の実データテーブルと、実データに対応するキーを複数含む範囲を示すキー範囲情報と前記実データテーブルごとのキャビネットＩＤを含むレコードが記憶される分散解決データテーブルと、キャビネットＩＤとキャビネットテーブルに含まれるひとつのレコードの格納位置を示すキャビネットインデクスを含むレコードが記憶されるキャビネット管理テーブルと、実データインデクスと次インデクスを含むレコードが記憶される前記キャビネットテーブルと、前記キャビネットテーブルのレコードを連結してリストを構成する手段と、前記キャビネットテーブルのレコードのリストにキャビネットテーブルのレコードを挿入してリストを延長する手段とを備え、前記動作方法は、前記データベース装置が、キーを含むデータ操作信号を受信し、前記データベース装置が、前記分散解決データテーブルから当該キーを含む範囲を示すキー範囲情報を含むレコードを検索し、当該実データを記憶すべき実データテーブルのキャビネットＩＤを読み出し、前記データベース装置が、前記キャビネット管理テーブルから当該キャビネットＩＤに対応するキャビネットインデクスを読み出し前記キャビネットテーブルから当該キャビネットインデクスに対応するレコードを検索し、前記データベース装置が、該検索されたレコードを含むリストにキャビネットテーブルのレコードを挿入して該リストを延長し、該挿入されたキャビネットテーブルのレコードに実データインデクスを格納し、前記データベース装置が、前記受信された実データを記憶すべき実データテーブルにおける当該実データインデクスに対応する位置に前記受信された実データを含むレコードを追加することを特徴とする。

本発明のデータベース装置およびその動作方法によれば、キーレンジ分割を用いる分散データベースシステムにおいてデータベース装置間でキー範囲の割り当ての変更を行う際に、メモリの断片化解消を行う必要が無く、かつ、メモリ消費が少ないようなデータベースを実現することができる。

本実施の形態に係るデータベース装置における記憶部の構成を示す図である。 メモリ空間（キャビネットテーブル４）におけるキャビネット６の配置例を示す図である。 比較例のデータベース装置における記憶部の構成を示す図である。 比較例のデータベース装置のメモリ消費に関する問題点を示す図である。 本実施の形態に係るデータベース装置の動作を示す図である。 本実施の形態のキャビネット６よるメモリ消費の低減効果を模式的に示す図である。

以下、本発明の実施の形態について図面を参照して説明する。

図１は、本実施の形態に係るデータベース装置における記憶部の構成を示す図である。

図は、複数のデータベース装置を含む分散データベースシステムの１データベース装置を示す。他のデータベース装置も同様の構成である。

データベース装置は、実データを含むレコードが実データインデクスに対応づけて記憶される１以上の実データテーブル１と、実データに対応するキーを複数含む範囲を示すキー範囲情報と配置先情報と実データテーブルごとのキャビネットＩＤを含むレコードが記憶される分散解決データテーブル２と、キャビネットＩＤと該キャビネットＩＤに対応するキャビネットのサイズであるキャビネットサイズと該キャビネットに含まれるひとつのレコードの格納位置を示すキャビネットインデクスとを含むレコードが記憶されるキャビネット管理テーブル３と、キャビネットインデクスと実データインデクスと次インデクスを含むレコードが記憶されるキャビネットテーブル４とを備える。

キャビネットテーブル４のレコードはリストを構成することができる。リストを構成するためには、キャビネットテーブル４のレコード（Ｌ１）の次インデクスに別のレコード（Ｌ２）を指し示す値を格納し、そのレコード（Ｌ２）の次インデクスにまた別のレコード（Ｌ３）を指し示す値を格納するということを繰り返すことにより、レコードＬ１、Ｌ２、Ｌ３を連結し、あるいはそれ以上のレコードを連結したリストを構成することができる。次インデクスにＮＵＬＬを格納することでリストの終端を表すことができる。

キャビネットテーブル４のレコードをリストとして連結したものをキャビネット６と呼ぶ。キャビネット６は非特許文献１に記載の「INDEXテーブル」に相当するデータ構造であり、複数のデータレコードをグルーピングする。キーレンジ分割でデータをシャーディングする際には分散解決データテーブル２によってデータの配置先をキャビネット６ごとに指定する。

実データテーブル１は、他の実データテーブル１に記憶されるデータとは異なる種類のデータを記憶するものである。つまり、分散データベースシステム全体でも、１つのデータベース装置でも、同じ実データテーブル１は存在しない。

分散解決データテーブル２は、他のデータベース装置に記憶される分散解決データテーブル２と同じものである。

キャビネット管理テーブル３、キャビネットテーブル４は、他のデータベース装置に記憶されるものとは異なるものである。

データベース装置のメモリが有限であることからキャビネットテーブル４のサイズは固定でありそのレコード数「Ｎ」を増減できないようになっている。

本実施例では、分散解決のキーに電話番号を用いることを例に記述する。すなわち、分散解決データテーブル２のキー範囲情報が”050-1111”であるとは、キー値としては”050-1111-0000”から”050-1111-9999”までの電話番号を表している。

図２は、メモリ空間（キャビネットテーブル４）におけるキャビネット６の配置例を示す図である。

キャビネットテーブル４のレコードに含まれる次インデクスは、当該レコードの次に生成されたレコード内のキャビネットインデクスを示すものである。

キャビネットＩＤ「１」のキャビネット６で最初に生成されたレコードは、メモリ空間（キャビネットテーブル４）の例えば１番目の領域に格納される。２番目のレコードは、例えば３番目の領域に格納される。最初のレコードの次インデクスは、３番目の領域を示していることになる。３番目のレコードは、例えば６番目の領域に格納される。２番目のレコードの次インデクスは、６番目の領域を示していることになる。

キャビネットＩＤ「２」のキャビネット６で最初に生成されたレコードは、メモリ空間の例えば２番目の領域に格納される。２番目のレコードは、４番目の領域に格納される。最初のレコードの次インデクスは、４番目の領域を示していることになる。３番目のレコードは、５番目の領域に格納される。２番目のレコードの次インデクスは、５番目の領域を示していることになる。４番目のレコードは、７番目の領域に格納される。３番目のレコードの次インデクスは、７番目の領域を示していることになる。

このように、本実施の形態では、キャビネットテーブル４内のメモリ空間を隙間なく利用することができる。

図３は、比較例のデータベース装置における記憶部の構成を示す図である。

１以上の実データテーブル１と、アドレスとキー範囲情報と配置先情報と次アドレスとキャビネットＩＤを含むレコードが記憶される分散解決データテーブル２Ａと、キャビネットＩＤと空塞状況を含むレコードが記憶されるキャビネット空塞管理テーブル３Ａと、キャビネットＩＤごとのキャビネット６Ａとキャビネット６Ａが配置されるキャビネットテーブル４Ａとを備える。

実データテーブル１は、他の実データテーブル１に記憶されるデータとは異なる種類のデータを記憶するものである。

分散解決データテーブル２Ａは、他のデータベース装置に記憶される分散解決データテーブル２Ａと同じものである。分散解決データテーブル２Ａは実データテーブル１の種類ごとに作成される。

キャビネット空塞管理テーブル３Ａ、キャビネットテーブル４Ａは、他のデータベース装置に記憶されるものとは異なるものである。

キャビネットテーブル４Ａは、そのレコード数「Ｎ」を増減できないようになっている。

キャビネット６Ａのレコード数は一定長で固定されており増減できないようになっている。

図４は、比較例のデータベース装置のメモリ消費に関する問題点を示す図である。

例えば、ある実データテーブル１（ＴＢ＃１の実データテーブル１）について使用するためのキャビネット６Ａ（キャビネットＩＤ「１」）の全レコードに実データインデクスがある状態（満状態）で、新たな実データインデクスを記憶させる必要性が生じたなら、同じ実データテーブル１について使用するためのキャビネット６Ａ（キャビネットＩＤ「２」）が新設され、レコードに新たな実データインデクスが記憶される。

この場合、ＴＢ＃１の実データテーブル１用の分散解決データテーブル２において、キャビネットＩＤ「１」を含むレコード（既存レコードという）に次アドレスとして含まれていたＮＵＬＬ値が例えば次アドレス「０００２」に変更され、次アドレス「０００２」と同じアドレスと既存レコードのキー範囲情報「０５０−１１１１」と配置先情報「ＤＢ＃１」と次アドレスとしてのＮＵＬＬ値とキャビネットＩＤ「２」を含むレコードが分散解決データテーブル２Ａに追加される。

キャビネット６Ａ（キャビネットＩＤ「２」）では、新設当初、ほとんどのレコードに実データインデクスが記憶されず、よって、新設当初のキャビネット６Ａが過剰にメモリを消費してしまうという問題点がある。

図５は、本実施の形態に係るデータベース装置の動作を示す図である。

ここでは、データベース装置が、外部から送信されるデータ操作信号内のキー「０５０−１１１１−ｄｄｄｄ」とデータの種類が「ｎ」である実データ「ｘｘｘ」を記憶部に格納する際の動作について説明する。

データベース装置は、まず、キーとデータの種類と実データを含むデータ操作信号を受信する（Ｓ１）。

次に、データベース装置は、分散解決データテーブル２から当該キーを含む範囲を示すキー範囲情報を含むレコードを検索し（Ｓ２）、レコードの配置先情報が他のデータベース装置を示すものなら、データを収容するデータベース装置へ実際のデータ操作を要求して処理を終了する一方、配置先情報が自身（データベース装置）を示すものなら、受信したデータ操作信号内の実データを記憶すべき実データテーブル（ＴＢ＃１）用のキャビネット管理テーブル３から当該キャビネットＩＤを含むレコードを検索し（Ｓ３）、キャビネットサイズを更新する（Ｓ４）。ここで、データベース装置は、例えばキャビネットサイズを３から４にインクリメント（更新）する（Ｓ４）。

次に、データベース装置は、当該更新したレコードからキャビネットインデクス（「１」）を読み出し、キャビネットテーブル４から当該インデクスに対応するレコードを検索し（Ｓ５）、当該レコードを含むキャビネット６において最後に追加されたレコードに次インデクスとして含まれていたＮＵＬＬ値をＮＵＬＬ値でない次インデクス（例えば「６」）に変更し、当該次インデクスと同じキャビネットインデクスを含むレコードをキャビネット６から検索し、実データインデクス（例えば「１０５」）を格納する（Ｓ６）。

次に、データベース装置は、実データテーブル（ＴＢ＃１）における当該実データインデクス（「１０５」）に対応する位置に、受信された実データ「ｘｘｘ」を含むレコードを追加する（Ｓ７）。

図６は、本実施の形態のキャビネット６よるメモリ消費の低減効果を模式的に示す図である。

本実施の形態では、キャビネット６はキャビネットテーブル４のレコードを連結して構成されるものであるため、キャビネットテーブル４内に空きレコードがある限りにおいて、キャビネット６が満状態になることはなく、キャビネット６が含むレコード数を増加させることができる。データベースに実データを追加する際にキャビネット６が含むレコード数を増加させる際には、追加する実レコード数だけのキャビネットテーブル４のレコードを消費するため、キャビネット６が過剰にメモリを消費してしまうという問題点を解決できる。

［背景技術］で述べたように、他のデータベース装置にキャビネット６を移し替える場合、これに伴い、キャビネット６をそのデータベース装置のキャビネットテーブル４に移し替える必要がある。

比較例の場合、移し替える先のデータベース装置のキャビネットテーブル４の中の個々のレコードの領域が未使用であっても、キャビネット６の固定サイズ分の連続した空き領域が無いとキャビネット６を移動できないが、本実施形態では、キャビネットテーブル４のレコードは実際に格納する実データレコード数しか消費せず、また、キャビネットテーブル４内の空きレコードが必ずしも連続している必要がない。空きレコードが必ずしも連続している必要がないということは、キャビネット６の移し替えを行う際にメモリの断片化の解消を行う必要がないことを意味する。以上のように、不連続であっても未使用のキャビネットテーブル４のメモリを使用できることから、本実施形態はメモリの再利用性が高いといえる。

なお、本実施の形態のデータベース装置としてコンピュータを機能させるためのコンピュータプログラムは、半導体メモリ、磁気ディスク、光ディスク、光磁気ディスク、磁気テープなどのコンピュータ読み取り可能な記録媒体に記録でき、また、インターネットなどの通信網を介して伝送させて、広く流通させることができる。

１ 実データテーブル
２、２Ａ 分散解決データテーブル
３ キャビネット管理テーブル
３Ａ キャビネット空塞管理テーブル
４、４Ａ キャビネットテーブル
６、６Ａ キャビネット

Claims (2)

1. データベース装置であって、
   実データを含むレコードが実データインデクスに対応づけて記憶される１以上の実データテーブルと、
   実データに対応するキーを複数含む範囲を示すキー範囲情報と前記実データテーブルごとのキャビネットＩＤを含むレコードが記憶される分散解決データテーブルと、
   キャビネットＩＤとキャビネットテーブルに含まれるひとつのレコードの格納位置を示すキャビネットインデクスを含むレコードが記憶されるキャビネット管理テーブルと、
   実データインデクスと次インデクスを含むレコードが記憶される前記キャビネットテーブルと、
   前記キャビネットテーブルのレコードを連結してリストを構成する手段と、
   前記キャビネットテーブルのレコードのリストにキャビネットテーブルのレコードを挿入してリストを延長する手段と、
   キーを含むデータ操作信号を受信する手段と、
   前記分散解決データテーブルから当該キーを含む範囲を示すキー範囲情報を含むレコードを検索し、当該実データを記憶すべき実データテーブルのキャビネットＩＤを読み出す手段と、
   前記キャビネット管理テーブルから当該キャビネットＩＤに対応するキャビネットインデクスを読み出し前記キャビネットテーブルから当該キャビネットインデクスに対応するレコードを検索する手段と、
   該検索されたレコードを含むリストにキャビネットテーブルのレコードを挿入して該リストを延長し、該挿入されたキャビネットテーブルのレコードに実データインデクスを格納する手段と、
   前記受信された実データを記憶すべき実データテーブルにおける当該実データインデクスに対応する位置に前記受信された実データを含むレコードを追加する手段と
   を備えることを特徴とするデータベース装置。
2. データベース装置の動作方法であって、
   前記データベース装置は、
   実データを含むレコードが実データインデクスに対応づけて記憶される１以上の実データテーブルと、
   実データに対応するキーを複数含む範囲を示すキー範囲情報と前記実データテーブルごとのキャビネットＩＤを含むレコードが記憶される分散解決データテーブルと、
   キャビネットＩＤとキャビネットテーブルに含まれるひとつのレコードの格納位置を示すキャビネットインデクスを含むレコードが記憶されるキャビネット管理テーブルと、
   実データインデクスと次インデクスを含むレコードが記憶される前記キャビネットテーブルと、
   前記キャビネットテーブルのレコードを連結してリストを構成する手段と、
   前記キャビネットテーブルのレコードのリストにキャビネットテーブルのレコードを挿入してリストを延長する手段とを備え、
   前記動作方法は、
   前記データベース装置が、キーを含むデータ操作信号を受信し、
   前記データベース装置が、前記分散解決データテーブルから当該キーを含む範囲を示すキー範囲情報を含むレコードを検索し、当該実データを記憶すべき実データテーブルのキャビネットＩＤを読み出し、
   前記データベース装置が、前記キャビネット管理テーブルから当該キャビネットＩＤに対応するキャビネットインデクスを読み出し前記キャビネットテーブルから当該キャビネットインデクスに対応するレコードを検索し、
   前記データベース装置が、該検索されたレコードを含むリストにキャビネットテーブルのレコードを挿入して該リストを延長し、該挿入されたキャビネットテーブルのレコードに実データインデクスを格納し、
   前記データベース装置が、前記受信された実データを記憶すべき実データテーブルにおける当該実データインデクスに対応する位置に前記受信された実データを含むレコードを追加する
   ことを特徴とするデータベース装置の動作方法。

Images