分散木構造データべースJungleによる企業向け許認可システム

enterprise Authorization system on distributed tree structure database Jungle

琉球大学工学部情報工学科

金川竜己指導教員河野真治目次

第 1 章世の中の知的構造を全て格納できるデータベースの開発 1 1.1 研究目的 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1

第 2 章分散データベース Jungle 2 2.1 Jungle のデータ構造 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 2.2 分散機能 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4

第 3 章組織の中の許認可を管理するアプリケーション maTrix 5 3.1 maTrix の保持するデータ構造 . . . . . . . . . . . . . . . . . . . . . . . . . 5 3.2 アカウント管理 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 3.3 申請の許認可 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 3.4 XACML . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

第 4 章 Jungle 上での matrix の実装 12 4.1 Jungle 上での maTrix のデータ構造の表現 . . . . . . . . . . . . . . . . . . 12 4.2 Jungle 上の許認可 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 4.3 検索 API の実装 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 4.4 Jungle 上の Index の設計 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 4.5 親 Node を返す特殊な Index . . . . . . . . . . . . . . . . . . . . . . . . . . 19 4.6 過去の Tree に対するアクセス . . . . . . . . . . . . . . . . . . . . . . . . . 21 4.7 JungleXMLReader . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 4.8 XACMLInterpreter . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

第 5 章実装の評価 24 5.1 実験環境 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 5.2 検索の API の測定 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 5.3 read&write の測定 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26

第 6 章結論 27 6.1 まとめ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 6.2 今後の課題 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28

6.2.1 push/pop . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 6.2.2 index の IncrementalUpdate . . . . . . . . . . . . . . . . . . . . . . 28 6.2.3 differencialList . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 6.2.4 exponential backoff . . . . . . . . . . . . . . . . . . . . . . . . . . . 28

図目次

2.1 破壊的木構造の編集 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 2.2 非破壊的木構造の編集 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 2.3 非破壊的木構造の編集 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 2.4 Jungle-network のトポロジの形成例とデータの伝搬順序 . . . . . . . . . . . 4

3.1 maTrix の構成情報例 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 3.2 maTrix の構成情報例 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 3.3 maTrix におけるアカウント管理例 1 . . . . . . . . . . . . . . . . . . . . . . 8 3.4 maTrix におけるアカウント管理例 2 . . . . . . . . . . . . . . . . . . . . . . 8 3.5 XACML のデータ構造 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

4.1 Jungle 上での人物 Tree 表現例 . . . . . . . . . . . . . . . . . . . . . . . . . 13 4.2 構成情報モデル Tree 表現例 . . . . . . . . . . . . . . . . . . . . . . . . . . 14 4.3 構成情報モデル Tree 表現例 2 . . . . . . . . . . . . . . . . . . . . . . . . . 15 4.4 find の検索順序 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 4.5 FindInSubTree の検索順序 . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 4.6 Jungle の Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 4.7 ParentIndexExample . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 4.8 XACMLInterpreter で用いられている stack . . . . . . . . . . . . . . . . . . 23

5.1 inActive の実行時間 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 5.2 read&write の測定 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26

表目次

3.1 Person.xml の要素 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 3.2 Rule の評価 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 3.3 XACML のルール結合アルゴリズム . . . . . . . . . . . . . . . . . . . . . . 11

4.1 構成情報 Tree の TreeNode が保持している Attribute . . . . . . . . . . . . 14 4.2 ParentIndex の返り値 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 4.3 sax の主要なイベント一覧 . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

5.1 実験環境 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24

第1章{世の中の知的構造を全て格納でき \atop るデータベースの開発}

1.1 研究目的

知識を記した書物等において、節が複数集まって章になり、章が集まって書物になるように、我々があつかっている知識は主に木構造である。しかし、知識の量は膨大であり、人が全てを記憶しておくのは難しいため、データベースに格納したい。しかし、 RDB 上に木構造データを格納するためには、煩雑なデータ設計が必要になる。

また、データベースを使用するウェブサービスの規模も年々大きなものとなり、それに比例してデータベースへの負荷も増大し、その結果サービスが停止する自体が多々見られるようになった。そのため、データベースの処理性能はそのままサービスの質につながっている重要な項目となっている。

データベースの処理性能を向上させる代表的な方法として、ハードウェア的に高性能なマシンを用意することで処理性能を上げるスケールアップと、汎用的なマシンをいくつも用意し、処理を分散させることで処理性能を上げるスケールアウトの２つがある。単純に処理能力を上げたいのなら、スケールアップは有効ではあるが、単一のマシンを高性能にするのにも限界があり、いずれはそのマシンの限界を超える負荷がかかる可能性もある。それに対しスケールアウトは、処理が重くなるに連れて汎用的なマシンを順次追加していくことで性能を上げるため、ハードウェア的に高性能なマシンを要求せずにすみ、柔軟な対応を取ることが出来るため、データベースの性能を上げる方法としてはスケールアウトが求められている。本研究で扱うスケーラビリティとはスケールアウトのことをさす。

今、最も使われているデータベースである RDB は、マシンを追加して負荷を分散することが容易ではない。そのためスケーラビリティを持つことが困難である。

当研究室では、これらの問題を解決した、煩雑なデータ設計が必要ないスケーラビリティのあるデータベースを目指して、非破壊的木構造データベース Jungle を開発している。しかし、 Jungle はまだ開発途中であり、データベースに必要な API 等もまだ十分に実装されていない。そこで、当研究では、共同研究を行っている Symphonies 社が開発している組織の中の許認可を管理するアプリケーション maTrix に Jungle を組み込み、実装すべき API の洗い出しを行い、その後実用 DB としての性能があるかテストを行う。

第2章分散データベースJungle

Jungle とは、当研究室で開発を行っている、スケーラビリティのある、世の中の知識構造を煩雑なデータ設計を行うこと無く格納できることを目標としたデータベースである。本章では、 Jungle の基本的な特徴についての解説を行う。

2.1 Jungle のデータ構造

研究目的でも述べたが、我々が扱う知識は主に木構造である。 Jungle はそれらの知識をそのまま格納するため、データ形式は非破壊的木構造を採用している。はじめに、非破壊的木構造と通常の破壊的木構造の違いについて説明を行う。

通常の破壊的木構造は、データの編集を行う際に、データを上書き更新する (図 2.1) ため、編集を行っている間ずっと木にロックをかける必要があり、また、閲覧者がいる場合、検索途中にデータが変わることを避けるために、データの検索が終わるまで書き換えを待つ必要がある。しかし、これではロックによりスケーラビリティが損なわれてしまう。

図 2.1: 破壊的木構造の編集

それに比べ非破壊的木構造は、一度生成した木を上書きすることはない。データの編集は、ルートから編集を行うノードまでコピーを行い新しく木構造を構築することで行う (図 2.2)。

図 2.2: 非破壊的木構造の編集

非破壊的木構造においてデータのロックが必要になる部分は、木のコピーを作った後に、ルートノードを更新するときだけである。また、データ編集を行っている間ロックが必要な破壊的木構造に比べ、非破壊的木構造は検索中の木が変更されないことが保証されいているため、編集中においてもデータの読み込みが可能である。 (図 2.3) そのため、非破壊的木構造に比べてスケールアウトがしやすくなっている。

図 2.3: 非破壊的木構造の編集

また、過去の Tree は全て保持しているため、いつでもアクセスすることが可能である。

2.2 分散機能

Jungle の分散機能は、当研究室で開発を行っている並列分散フレームワークである Alice を使用している。 Alice はユーザーが望んだマシンへの接続や、必要なデータへのアクセスを行う機構等、ネットワークトポロジー形成機能を提供している。

Jungle は、ネットワークトポロジーを構築する際に、木構造を想定したネットワークトポロジーを形成しサーバー同士を接続することで通信を行っている。木構造なら、一度 RootNode までデータを伝搬させることで整合性を取ることが出来る (図 2.4) からである。データの伝搬中に衝突が発生した場合、 Merge を行い結果を改めて伝搬すれば良い。

図 2.4: Jungle-network のトポロジの形成例とデータの伝搬順序

第3章{組織の中の許認可を管理するアプ \atop リケーションmaTrix}

maTrix とは Symphonies 社が開発しているアカウント管理、許諾判定システムのことである。人や組織の情報などを保持しており、それらの情報を関連付けることで組織の構造を表現している。

3.1 maTrix の保持するデータ構造

matrix は人、役職、役割、権限といった木構造の組織、許認可の判断に用いるポリシーファイルの２つのデータを持っている。また、組織のデータは、ユニークな Id を保持しており、それを利用しお互いに参照しあっている。 maTrix は、過去のデータも構成情報モデルとして全て保持し、版管理している。

図 3.1: maTrix の構成情報例 1

人物と役職の Tree の version が共に 1 の時、構成情報モデルの version も 1 とする。構成情報モデルの version:1 の人物 Tree を更新した場合、 version:2 の構成情報が構築さ

れ、 maTrix は version:1 の構成情報と version:2 の構成情報の両方を保持し、両方の構成情報にアクセスすることが可能である。

maTrix のデータ構造は、組織の Tree を xml や json 形式で出力することができる。以下に人物 Tree を xml 形式で出力したデータの一部として、 1 人分のデータを記述する。

図 3.2: maTrix の構成情報例 1

[figure]

<Persons>
<Person id="p:1" type="Person">
<accountId>a:26</accountId>
<lastName>東</lastName>
<name>東俊一</name>
<nameReading>あずましゅんいちくん</nameReading>
<roleRefIds>
<roleRefId>r:10</roleRefId>
<roleRefId>r:34</roleRefId>
</roleRefIds>
<parentOrganizations type="OrganizationMappedByRole">
<OrganizationMappedByRole type="OrganizationMappedByRole">
<organizationRefId>o:2</organizationRefId>
<roleRefId>r:10</roleRefId>
</OrganizationMappedByRole>
<OrganizationMappedByRole type="OrganizationMappedByRole">
<organizationRefId>o:11</organizationRefId>
<roleRefId>r:34</roleRefId>
</OrganizationMappedByRole>
</parentOrganizations>
<priorities type="PriorityMappedByRole">
<PriorityMappedByRole type="PriorityMappedByRole">
<priority>0</priority>
<roleRefId>r:10</roleRefId>
</PriorityMappedByRole>
<PriorityMappedByRole type="PriorityMappedByRole">
<priority>1</priority>

[figure]

[figure]

 <roleRefId>r:34</roleRefId>
 </PriorityMappedByRole>
 </priorities>
 </Person>
 </Persons>

[figure]

表 3.1: Person.xml の要素

Persons  この要素以下に Person の情報があることを意味する
Person  人の情報が以下にあることを示す。 uniqueId が割り振られている
accontId  その Person のアカウント Id
lastName  苗字
name  フルネーム
nameReading  名前のふりがな
roleRefIds  この要素以下にその人が保持する役割を記述する
roleRefId  役割の Id を記述する
parentOrganizations  この要素以下にその人が所属している組織の Id を記述する
OrganizationMappedByRole この要素以下に組織と、その組織の役割を記述する
organizationRefId  所属している組織の Id
priorities  人物に割り振られている役割の優先順位を以下に記述する
PriorityMappedByRole  この要素以下に役割と優先順位をペアで記述する
priority  役割の優先順位を記述する

Person.xml を例で上げたが、役職 Tree や役割 Tree も同じような構造でデータを保持している。人物や役割等のデータ同士の参照は Id を用いて行っている (上記の例だと、東俊一の PersonId は p:1 である)。また、 maTrix には、組織情報からデータを取得する Function が 15 種類実装されている。

3.2 アカウント管理

maTrix は、一度の利用者認証で複数のサービスを利用できるサービスである SSO を採用している。 maTrix を使用しなかった場合、図 3.3 のようにアプリケーションごとにアカウントを作る必要があり、 user の権限等が変わった際に、全てのアカウントの更新を行う必要があるため、手間がかかったり、ミスが発生するなど、業務に支障をきたすおそれがある。

図 3.3: maTrix におけるアカウント管理例 1

しかし maTrix を用いることで図 3.4 の様に、 maTrix のアカウント１つで全ての業務アプリケーションにアクセスできる。そのため、 user の権限が変わったとしても maTrix のアカウントの更新だけしか行う必要がないので、手間もかからず、ミスも発生しづらい。

図 3.4: maTrix におけるアカウント管理例 2

この様に実際の業務で、複数のアプリケーションを使用する際は、 maTrix の様なアカウント管理サービスは必須とも言える。

3.3 申請の許認可

maTrix を用いた許認可は、アクセス管理のルールを表現方法を定義する XACML という言語で記述された、ポリシーファイルを用いて行う。ポリシーファイルは、リポジトリで管理されており、アクセス要求にあったポリシーファイルが利用される。以下に maTrix での申請の許認可の流れを記述する。

1. A さんが、資料 B を閲覧するために、 maTrix にアクセス許可を求める。

2. maTrix はリポジトリから、アクセス許可を与えるかを判断するためのポリシーを取得する。

3. ポリシーファイルを元に、データにアクセスを行い権限を与えるかどうかを判断する。

4. maTrix は権限に応じて、資料 B を A さんに与える。

といった流れになる。

maTrix の許認可を使用するメリットとして、許認可のログをとっておくことで、いつ、誰が、どのポリシーを元に、どんなことをしたか、の情報がいつでも取得可能であるため、不正アクセス等の問題発生時の解決等役立つ。といったメリットもある。

3.4 XACML

本節では maTrix のポリシーファイルの記述に用いられている XACML についての説明を行う。 XACML は、データに関するアクセス要求について、その要求元の情報と要求の内容、アクセス対象の組み合わせから、そのアクセス要求が許可されるか否認されるかを判断するためのルールを記述できる。実際に使用する際は、 XACML 自体がアクセス制御を行うのではなく、アクセス管理アプリケーションが XACML を参照しアクセス制御を行う。 XACML は以下の様なデータ構造を持つ (図 3.5)

図 3.5: XACML のデータ構造

Target は、誰に対して (Subject)、どのような資源を (Resource)、どのように扱うか (Action) の 3 つの要素を持ち、それぞれの要素で、評価関数を用いて評価を行う。評価の結果は、 Match、 No-Match、 Indeterminate(評価不能) の 3 つである。

Rule は、 Target に対する規則を定めるもので、ルールの方針にそってアクセス要求がこのルールに適合した場合に決定する値 (Permit、 Deny) を、 Effect として設定しておく。また、 Target とは別にオプションとして条件 (Conditions) を付けることも可能である (条件の例としては、アクセスを許可する時間の指定などがある)。ルールの評価は、 Target の評価関数の結果と Condition の、ルール結合アルゴリズム (表 3.2) にそって結合する。

表 3.2: Rule の評価

Target  Condition  評価
Match  true  Efferct(Permit or Deny)
Match  false  NotApplicable
Match  Indeteminate Indeteminate
No-Macth - NotApplicate
Indeterminate -  Indeteminate

Policy 複数の Rule をまとめたものを Policy という。 Policy の子要素には、 Target、 Rule、 Obli-

gations(責務) がある。もしも、 Policy に Obligations が規定された場合は、たとえ、ルール結合後の結果が permit であったとしても、 Obiligations に記述されていることを同時に実施することが出来なかった場合、承認を拒否する必要がある。また Policy が複数の Rule を評価するときは、ルール結合アルゴリズム (表 3.3) を用いる。

表 3.3: XACML のルール結合アルゴリズム

Deny-overrides どれか１つのルールの Effect が Deny であれば結果は Deny とする
Permit-overrides どれか１つのルールの Effect がが Permit であれば結果は Permit とする
First-applicable ポリシー内のすべてのルールについて順番に評価して、対象がマッチした場合、

対象の評価結果を Match とし、次に Condition を評価し、これが True なら結果は Effect で指定された Permit または Deny とする。

XACML の評価が終わり、最終的に Permit だった場合その申請は許可される。

第4章 Jungle上でのmatrixの実装

前章では組織の中の許認可を管理するアプリケーション maTrix について説明を行った。本章では、 maTrix を Jungle 上にどのように実装するかを記述する。

4.1 Jungle 上での maTrix のデータ構造の表現

maTrix は、前章でも説明したが、人物、役職、役割、といった情報を木構造で保持しており、それらの Tree は ID で参照しあっている。人物 Tree や役職 Tree は、木構造のデータであるためそのまま Jungle に格納することができる。実際に人物 Tree を格納した際のデータの形を (図 4.1) に示した。 (図 4.1) は前章で表示した Person.xml と対応している。 Tree 間の参照は、 Tree のデータは UniqueId を保持しているため、 Tree に対して Id で検索を行うことで表現した。図 4.1: Jungle 上での人物 Tree 表現例

13

Jungle の Tree は、全ての version の Tree でユニークな Id を保持しているため、 Id を指定すれば、過去の Tree にアクセスすることが可能である。それを利用し、 Jungle 上での過去の変更履歴を保持する構成情報モデルの表現は、構成情報モデルの version と、各 Tree の version を保持し、関連付ける構成情報モデル Tree を作成し表現した。 (図 4.2)。

図 4.2: 構成情報モデル Tree 表現例

表 4.1: 構成情報 Tree の TreeNode が保持している Attribute

version  構成情報モデルの version
person  構成情報モデルの version に対応する人物 Tree の version
organization 構成情報モデルの version に対応する組織 Tree の version
role  構成情報モデルの version に対応する役割 Tree の version
rde  構成情報モデルの version に対応する役割記述要素 Tree の version

実際にどのように Jungle 上で過去の構成情報モデルにアクセスするか、例題を用いて説明する。構成情報モデル version:3 に対応する人物 Tree にアクセスする手順を以下に示す。

1. 構成情報 Tree からアクセスしたい version 情報を保持している Node を取得する (今回の例題では version3)

2. 取得した TreeNode には、構成情報:version:3 に対応した人物 Tree などの version が記述されている (図 4.2) ので、人物 Tree の verson(v:5) を取得する

3. ２で取得した version の人物 Tree にアクセスする。

といった手順で Jungle では maTrix の構成情報モデルを表現する。以下に Jungle 上での構成情報モデル表現例を図 (4.3) を記す。図 4.3: 構成情報モデル Tree 表現例 2

15

4.2 Jungle 上の許認可

Jungle 上で maTrix の許認可を行う際は、ポリシーファイルを読み込み、各 Tree に対して検索関数を用いて、その結果から許認可を行う。

例えば、 A さんが、管理者しか閲覧出来ない資料を閲覧しようとした場合は

1. 人物 Tree から、 A さんのデータを取得し、 A さんに割り振られている役割の ID を取得する。

2. 役割 Tree から、 1 で取得した役割 ID のデータを取得し、その役割 ID に割り振られている役割記述要素 ID を取得する

3. 役割記述要素 Tree から、 2 で取得した役割記述要素 ID のデータを取得し、役割記述要素名を取得する

4. 3 で取得した役割記述要素名が、管理者かどうかを調べ、一致した場合はアクセスを許可し、一致しなかった場合はアクセスを拒否する。

といった流れになる。

4.3 検索 API の実装

Jungle は、データを格納する API は実装されていたが、データの検索を行う API の実装は行われていなかった。しかし、 Jungle 上で maTrix のデータ構造を表現、許認可を行うためには検索 API が必要であったため、実装を行った。

Tree に対する検索は、 java8 の新機能である lambda 式を用いて find 関数を実装した。 lambda 式を使用することで、匿名クラスを使う時より簡潔にコードを記述できるようになった。以下に実際に lambda 式を用いた find 関数の使用例を記す。

Jungle の Query 部分のソースコード

[figure]

Iterator<TreeNode> pairPersonIterator =
traverser.find((TreeNode node) -> {
  String element = node.getAttributes().getString("element");
  if (element == null)
    return false;
    if (element.equals("Person"))
      return true;
    return false;
}, "element", "Person");

[figure]

find 関数は引数に Query、 String key、 String value の 3 つの引数を取り、条件に一致した Node の Iterator を返す。第一引数には、探索の条件を記述する関数 boolean comdition(TreeNode) を定義した InterfaceQuery を。第二、第三引数の、 String key、 String value は後述する Index を使うために使用する。

QueryInterface の定義

[figure]

  public interface Query {
      boolean condition(TreeNode _node);
  }

[figure]

find 関数の処理の流れは、まず、 Index が登録されているかを調べる、 Index がある場合は Index を使用し値を返す。 Index がない場合は、 Tree を深さ優先で全探索する。 (図 4.4)

図 4.4: find の検索順序

検索APIは、他に特定のNode以下に対して検索を行うfindInSubTree(Query,node,key,value) も実装した。 (図 4.5)

図 4.5: FindInSubTree の検索順序

findInSubTree を使用することで、更に限定的な探索が行えるようになった。

また、 maTrix 上に実装されていた、構成情報からデータを取得する Function も全て実装して、実際の maTrix と同じようにデータのアクセスを行えるようにした。

4.4 Jungle 上の Index の設計

Jungle の探索は Tree を全探索するので、探索の計算量は O(n) となり、非常に効率が悪い。しかし、 Index を使用することで効率よく探索を行えるようになる。また、 Jungle は過去の Tree を全て保持しているため、 Tree の version 毎に Index を持っていることが望ましい。そこで、メモリの消費量を抑え、各 version の Tree に Index をもたせる方法として、 FunctionalJava の TreeMap を使用した Index の実装を提案する。

TreeMap は、 Key と Value のペアを用いて赤黒木を構築する。赤黒木の長所として、ソート済み二分木の探索なので計算量が O(logN) であること、データ編集時の最悪計算量がデータ構造のうちで最善のものの１つであるので、安定した速度でデータの編集が行える。

それに加え、 FunctionalJava の TreeMap は、データの更新が行われた際に、一度作られた Tree に対して更新を行わず過去の Tree を再利用し、更新後の TreeMap 新しく返すため、メモリの使用量を抑えつつ複数の version の TreeMap を保持できる。そのため、 Jungle の Index と非常に相性が良い。 Index は各 JungleNode がローカルに Index を持つ on the fly 形式で実装する。 (図 4.6)

図 4.6: Jungle の Index

これまでの Jungle の Tree の欠点として、親から子ノードを取得することは可能であったが、子ノードから親ノードを取得することは出来なかった。そのため、 Indexで取得できる値が Node だけでは、 Index で検索を行って取得した Node の編集が行えないため、 Index の型を、 TreeMap<String key, TreeMap< String value , List<Pair<TreeNode,NodePath>>>> と定義し、返り値を Pair<TreeNode,NodePath> というように、 TreeNode とその TreeNode への NodePath のペアにすることで Node の編集を可能にしていた。しかし、 Tree の編集を行った際に、 TreeNode への Path は常に変動する為、 Index 内の NodePath の更新コストが編集時のネックであった。しかし、後述する ParentIndex を実装することで、 TreeNode から NodePath を取得できるようになったため、 Index に NodePath を入れる必要がなくなり、 Index の型は TreeMap<String key,TreeMap<String value,List<TreeNode>>>> と定義できるようになった。

最初のTreeMap<String key,TreeMap>はIndexを格納するTreeMapである。このTreeMap に対し key で get を行うと、 key に対応する Index が登録されている場合、 Index を取得でき、取得した Index に対し value で get を行うと、 value の値を持つ Node の List が返ってくる。

4.5 親 Node を返す特殊な Index

TreeNode で get を行うと、親 Node を返す ParentIndex を実装した。 ParentIndex の型は、 TreeMap<TreeNode,TreeNode> で定義されている。

図 4.7: ParentIndexExample

上記の図 4.7 を用いた ParentIndex の例を表 4.2 にまとめた。

表 4.2: ParentIndex の返り値

返ってくる Node 渡す Node
Node2  Node4、 Node5
Node3  Node6、 Node7
Node1  Node2、 Node3

ParentIndex を使用することで、 TreeNode から NodePath を取得できるようになった。以下に ParentIndex を使用して、 NodePath を取得する方法を示す。

1. ParentIndex を用いて親 Node を取得する。

2. 親 Node から子ノードのリストを取得する。 3. 子ノードのリストから、親 Node を get するのに使用した Node がある位置のイン

デックスを取得する。

4. 3 で取得した Index を Path に追加する

5. rootNode に辿り着くまで 1 - 4 を繰り返すと、対象への NodePath が取得できる。

4.6 過去の Tree に対するアクセス

Jungle 上で maTrix の構成情報モデルの表現を行う際に、過去の Tree にアクセスする必要があるが、 Jungle には、過去の Tree に対し、アクセスする API は実装されていなかったため、実装を行った。

Jungle は、クラス ChangeSet 内に Tree のデータを保持している。 ChangeSet からは、今の revisionId と、１つ前の Tree のデータを取得できるため、再帰的に過去の Tree のデータを取得できる。

アクセスしたい Tree の revisionId を引数に取り、過去の Tree のデータの取得と revisionId の比較を繰り返すことで過去の Tree にアクセスする、 getOldTree(long revisionId) を DefaultJungleTree 内に実装した。

以下に getOldTree の実装部分のコードを示す。 getOldTree の実装部分

[figure]

@Override
public Either<Error, JungleTree> getOldTree(long revision) {
TreeContext tc = repository.get();
ChangeSet cs = tc.getChangeSet();
for (; cs.revision() != revision;) {
  cs = cs.prev();
  if (cs == null)
    return DefaultEither.newA(GetOldTreeError.OLD_TREE_NOT_FOUND);
}
TreeNode root = cs.getRoot();
TreeContext oldTc = new DefaultTreeContext(root, cs);
String oldTreeUuid = uuid + revision;
JungleTree oldTree = new DefaultJungleTree(oldTc, oldTreeUuid, writer, treeEditor);
return DefaultEither.newB(oldTree);
}

[figure]

for 文の中で、過去の Tree の取得と、 revision の比較を繰り返している。 revision が一致した場合は、その version の Tree を返し、アクセスしたい revision を持つ Tree が見つからなかった場合は、エラーを返す。

4.7 JungleXMLReader

maTrix から XML 形式で書き出されたデータを Jungle に格納するための API として、 XMLReader を実装した。 JungleXMLReader の実装には sax(Simple API for XML) を用いた。

sax は、 XML のタグやテキストデータを読んだ際にイベントを発生させながら、構文解析を行う。プログラマは、 ContentHandler という特殊なイベントリスナを sax の parser に登録すると、発生するイベントを取得できる。イベントには、読み込んだタグの名前やテキストデータが含まれている。

表 4.3: sax の主要なイベント一覧

イベント名呼び出されるタイミング
startDocument XML の Parse が始まる時
endDocument XML の Parse が終わった時
startElement 要素を読み込んだ時
endElement  要素が閉じられた時
Charactor  テキストが読み込まれた時

sax では、 org.xml.sax.helpers.DefaultHandler という形で、 ContentHandler のデフォルト機能が提供されているため、プログラマはこれを継承することで、必要なイベント処理のみを override して記述できるようになっている。

XMLReader で使用している ReadXmlHandler は、 startElement、 charactor、 endElement、 endDocument、の 4 つのイベントを使用しており、 XML を読み込む際に、 Tree を構築しながら Parse を行う。

startElement が呼ばれた時は、今いる地点の下に新しく Node を作りその Node へ移動する。その後、今いる Node に Attribute の値を格納する。 charactor が呼ばれた時は、今いる Node にテキストデータを格納する。 endElement が呼ばれたら、今いる Node の親ノードに移動する。

以上の 3 つの関数を用いて、 XML のデータを Tree に格納していき、 endDocument が呼ばれた時に木の Commit を行っている。

4.8 XACMLInterpreter

XMLReader と同じよう sax にを用いて実装している。 XACMLInterpreter は、引数に、使用する policyFile 名、どの Resource にアクセスするか、どんな処理を行うか、許認可を求める人の UserID 等を与える。

XAMLInterpreterでHandlerが使用しているイベントは、 XMLReaderと同じで、 startElement、 charactor、 endElement、 endDocument の 4 つを使用している。

startElement では、主に評価関数や、評価関数の引数等を取得する。また評価関数が入れ子になっていることがあるため、 functionStack と attributeStack を用いて評価関数と引数を関連付けている。図 (4.8) の例だと、 function3 を実行した後、 function3 の返り値と、 function2 の引数の２つを使って function2 を実行する。

図 4.8: XACMLInterpreter で用いられている stack

charactor では、評価関数の引数を取得し、 AttributeStack に push する endElement では。主に評価関数の実行を行う。 endDocumentでは、これまでに実行した評価関数等の結果から今回の許認可を判断する。 XACMLInterpreter を用いることで Jungle 単体で XACML で記述されたポリシーファ

イルのテストが行えるようになった。

第5章実装の評価

前章では、 Jungle 上に maTrix を構築する方法と、構築に必要な API の実装について述べた。本章では、実装を行った Jungle の性能評価を行う。

5.1 実験環境

表 5.1: 実験環境

名前概要

CPU Memory OS

JavaVM 1.8.0-25

5.2 検索の API の測定

Jungle に対する検索 API の測定を行う。測定には、 maTrix が保持しているデータにアクセスする際に用いる関数のうちの１つである、 boolen isActive(String personId,String version) という関数を用いる。 isActive は、第一引数で与えた PersonId を持つ人物が、第二引数で与えられた構成情報モデルの version に対応した人物 Tree にいるかどうかを調べる関数である。実験の結果は図 5.1 となる。横軸は人物 Tree にいる人の数を表しており、縦軸は探索にかかった時間を表している。

図 5.1: inActive の実行時間

isActive の実行時間は、 Index を使用しない場合は、 Person の数が増えると比例して増えていくのに対し、 Index を使用すると Person の数が増えても実行時間は変わらなかった。この結果より、 Jungle の Index の計算量は O(logn) であることがわかる。

5.3 read&write の測定

1 秒間の間 Jungle に対し書き込みと、データの検索を同時に行い、 Jungle の書き込みがどの程度検索に影響をおよぼすかを調べる。測定の条件は、 Jungle が保持している Person 数は 100、書き込みに 1Thread 使用し、読み込みを行う Thread は 1 から 12 個まで使用する。 read 関数は実験 1 と同じく関数 isActive を用いた。実験の結果は図 5.2 となる。横軸は Jungle に対し、 read を行う thread 数、縦軸は read を行った回数を表す。

図 5.2: read&write の測定

Jungle は書き込みを行う際、読み込みに対するロックをかけないため、書き込みを行ってもほとんど読み込みに影響を及ぼさない。しかし、書き込みと読み込みを同時に行っている read&write の方は、書き込み分の負荷が多くかかっているため、やはり read のみと比べると多少遅くなっている。

図 5.2 でも ThreadCount5 まではほとんど差は開いていない。しかし、 6Thread 目以降は read&write の、 8Thread 目以降では readOnly の readCount の上昇量がゆるやかになり、差が開きだしている。理由として、 Jungle の処理限界が来たためであると推測でき、 read&write が readOnly より早く処理限界が来た理由は、 write の分 readOnly よりリソースを多く使用しているためだと推測できる。

本実験で、 Jungle は書き込み中でも高速に検索が行えることがわかった。これはつまり、スケールアウトを行うためにデータのコピーを行う際、データベースをロックすること無く行えるということである。

第6章結論

6.1 まとめ

本研究では、初めに当研究室が開発している分散データベース Jungle で使われている非破壊的木構造について述べ、破壊的木構造に比べてロックが少ないというメリットがあること、当研究室で開発している並列分散フレームワーク Alice を用いて分散実装を行っていることを述べた。

その後、株式会社 Symphony が開発しているアカウント管理、許諾判定システムである maTrix が、どのようなデータ構造を保持しており、どのようにアカウント管理を行い、申請の許認可を行っているかの説明を行って、 Jungle 上で maTrix をどのように実装するかを述べた。その後 Jungle 上で maTrix を表現するために新しく Jungle に実装した API の説明を行った。検索 API は、 Java8 の新機能である lambda 式を用いて実装を行い、検索を高速化するため functionalJava の TreeMap を用いて Index の実装も行った。過去の Tree に対するアクセスは、全ての Version の Tree が持っている固有の revisionId を使用しアクセスを可能にした。

また、 maTrix が書きだした xml ファイルを読み込むために XMLReader を sax を用いて実装し、 XML ファイルを Jungle に取り込めるようにした。その後、 XACMLInterpreter を実装し、 maTrix が使用しているポリシーファイルを読み込んで、 Jungle 上で許諾判定を行えるようにした。

最後に、実際に maTrix がデータにアクセスする際に使用するアクセス関数を実装し、性能評価を行った。 1 つ目の実験では Index の性能評価を行うため、 Index を使用する場合と、使用しない場合で検索を行い、アクセス関数の実行速度の比較を行った。 2 つ目の実験では、データの検索 API に対して複数の Thread から負荷をかけ、並列に動作するかどうかを調べ、どちらの実験でも Index の性能は出ていた。

6.2 今後の課題

6.2.1 push/pop 6.2.2 index の IncrementalUpdate 6.2.3 differencialList 6.2.4 exponential backoff

参考文献^{[1] hoge}

29

謝辞

本研究の遂行，また本論文の作成にあたり、御多忙にも関わらず終始懇切なる御指導と御教授を賜わりました河野真治助教授に深く感謝したします。また、様々な研究や勉強の機会を与えてくださった、株式会社 Symphony の永山辰巳さん、同じく様々な助言を頂いた合木茂さん、株式会社 PCI ホールディングスの皆さまに深く感謝いたします。様々な研究に関わることで自身の研究にも役立てることが出来ました。研究を行うにあたり、数々の貴重な御助言と細かな御配慮を戴いた、大城信康さん、杉本優さん、並びに並列信頼研究室の全てのメンバーに深く感謝致します。最後に、有意義な時間を共に過ごした情報工学科の学友、並びに物心両面で支えてくれた両親に深く感謝致します。

2015 年 3 月金川竜己