日本ソフトウェア科学会第 30 回大会 (2013 年度) 講演論文集

Haskell による非破壊的木構造を用いた CMS の実装
當眞 大千

河野 真治

永山 辰巳

ウェブサービスではユーザの増加に対応し、容易に拡張できるスケーラビリティが求められる。コンテンツマネージ
メントシステムにおいてスケーラビリティを実現するためには、並列にデータへアクセスできる設計が必要となる。
本研究では、編集元の木構造を破壊することなく編集できる非破壊的木構造を利用する。非破壊的木構造では、少ない排他制御で変更を行えるためスケーラビリティを確保できる。コンテンツマネージメントシステムの実装にはプログラミング言語 Haskell を用いた。Haskell で書かれた HTTP サーバ Warp を用いて簡易掲示板システムを開発し、既存の Java の実装と比較して短い開発期間やコード行数で、同程度の性能を達成できた。

非破壊的木構造を用いたデータベースとして、本研

1 はじめに究室による Java による実装が既に存在する。しかしブロードバンド環境やモバイル端末の普及により、ながら、Functional Java を多用しており、それならウェブサービスの利用者数は急激に伸びている。リクば純粋関数型言語である Haskell のほうが相性がいエスト数の増加を予想することは困難であり、負荷がいのではないかと考え、本研究では Haskell による増大した場合に容易に拡張できるスケーラビリティが実装を行った。

求められる。ここでいうスケーラビリティとは、利用

Haskell による実装では、Java と比較して開発期者や負荷の増大に対し、単なるリソースの追加のみで間およびコード行数が非常に短くなるといったメリッサービスの質を維持することができる性質のことでトがあった。

ある。コンテンツマネージメントシステムにおいてス

また、性能比較のために Haskell で書かれた HTTPケーラビリティを実現するためには、並列にデータへサーバ Warp を用いて簡易掲示板システムを開発し、アクセスできる設計が必要となる。

既存の Java の実装と同程度の性能を達成できた。

本研究では、並列にデータへアクセスする手法として、非破壊的木構造を利用する。非破壊的木構造で2 Haskell

は、少ない排他制御で変更を行えるためスケーラビリ

Haskell は、純粋関数型プログラミング言語であティを確保できる。

る。関数型プログラミング言語では、引数に関数を作用させていくことで計算を行う。変数への代入は一度Implementation of the CMS using Nondestructive
Tree Structure and Haskell
Daichi TOMA, Shinij KONO, 琉 球 大 学 大 学 院
理 工 学 研 究 科 情 報 工 学 専 攻 並 列 信 頼 研 究 室,
Dept.Concurrency Reliance Laboratory, Information Engineering Course, Faculty of Engineering
Graduate School of Engineering and Science, University of the Ryukyus.
Tatsumi NAGAYAMA, 株 式 会 社 Symphony, Symphony Co., LTD.

のみで、書き換えることはできない。遅延評価や、強い静的型付けも Haskell の特徴である。

3 Warp
Warp [1] は、軽量、高速な HTTP サーバである。
Haskell の軽量スレッドを活かして書かれている。
Haskell の ウェブフレームワーク である Yesod のバックエンドとして用いられており、現在も開発が続

main
HTTP サーバを起動するには、Warp の run 関けられている。

数を利用する。run 関数は、利用する Port 番号と、3. 1 Warp を用いたウェブアプリケーションの構築

application というリクエストを受けて何かしらのレスポンスを返す関数の 2 つを引数として受け取る。

Warp を用いてウェブアプリケーションを構築する

関数型言語では、関数を第一級オブジェクトとして方法について考察する。

扱える。また、今回は Haskell のカリー化された関application counter request = function
counter
wherefunction = routes $ pathInfo request数の特性を利用し、main 内で作成した IORef 型のcounter を部分適用させている。
IORef を用いることで、Haskell で更新可能な変数を扱うことができる。参照透過性を失うようにみえる

routes path = findRoute pathrouteSetting

が、Haskell は IO モナドを利用することで純粋性を保っている。IORef 自体が入出力を行うわけではな

findRoute path [] = notFound
findRoute path (( p , f ): xs )| path == p = f| otherwise = findRoute path xs

く、単なる入出力操作の指示にすぎない。IO モナドとして糊付けされた単一のアクションに main という名前を付けて実行することで処理系が入出力処理をrouteSetting = [([ " hello " ] , hello ) ,([ " hello " ," world " ] ,world )]行う。

notFound _ = return $responseLBS status404 [( " Content type " , " text / html " )] $ " 404 "自に定義して、URL によって出力を変更している。

application 及び routes , findRouteapplication の実装では、routes という関数を独application に渡されるリクエストはデータ型で様々な情報が含まれている。その中のひとつに pathInfo

hello _ = return $responseLBS status200 [( " Content type " , " text / html " )] $ " hello "という、URL から hostname/port と、クエリを取り除いたリストがある。この情報を routes という関数に渡すことで、routeSetting というリストから一致

world counter = docount <- lift $ incCount counter
return $ responseLBS status200 [( "Content - type " , " text / html " )] $fromString $ show countする URL がないか調べる。routeSetting は、URLのリストとレスポンスを返す関数のタプルのリストである。

notFound 及び hello
incCount counter = at om icM odi fyI OR e f
counter (\ c -> ( c +1 , c ))レスポンスを返す関数は、いくつか定義されている。その中で利用されている responseLBS は文字列

main = docounter <- newIORef 0
run 3000 $ application counterからレスポンスを構築するためのコンストラクタである。

world 及び incCount
ソースコード 1

Warp を用いたウェブアプリケーション

world は、インクリメントされる counter を表示の例するための関数である。IORef 内のデータは直接

ソースコード 1 は、URL によって出力する結果を変触ることができないため、incCount 内で atomic-

更するウェブアプリケーションである。/hello/world

ModifyIORef を利用してデータの更新を行なっていへアクセスがあった場合は、インクリメントされるる。atomicModifyIORef は、データの更新をスレッ

counter が表示される。

ドセーフに行うことができる。また、responseLBS

で構築したレスポンスは、Resource T というリーソ

1. 変更したいノードまでのパスを求める。

スの解放を安全に行うために使われるモナドに包ま

2. 変更したいノードをコピーし、コピーしたノーれている。lift 関数を用いて、incCount の型を持ちドの内容を変更する。

3. 求めたパス上に存在するノードをルートノード上げ調整している。
実際にプログラムを例にして説明したが、Warp はに向かって、コピーする。 コピーしたノードに一容易にプログラムに組み込むことができる。我々のシつ前にコピーしたノードを子供として追加する。

4. 影響のないノードをコピー元の木構造と共有

ステムでは Warp を用いて開発を行う。

する。

4 コンテンツマネージメントシステムの設計

この編集方法を用いた場合、閲覧者が木構造を参照

コンテンツマネージメントシステムのデータ構造してる間に、木の変更を行っても問題がない。閲覧者

としては木構造を用いる。スケーラビリティのあるは木が変更されたとしても、保持しているルートノーCMS の実現のために非破壊的木構造 [2] を利用した。

ドから整合性を崩さずに参照が可能である。ロックを非破壊的木構造とは、編集元の木構造を破壊することせずに並列に読み書きが可能であるため、スケーラブなく新しい木構造を構成することで木構造を編集すルなシステムに有用であると考えられる。元の木構造る方法である。

は破壊されることがないため、自由にコピーを作成し破壊的木構造と異なりロックせずに並列に読むことができるため、自由にコピーを作成することが可能でても構わない。したがってアクセスの負荷の分散も可能である。

ある。コピーを複数作成し、アクセスを分散させるこ

編集前の木構造

編集後の木構造

新しい木構造を作成とで性能を維持することができる。
1

1を閲覧

複数の閲覧者4. 1 非破壊的木構造

22を閲覧

非破壊的木構造は、木構造を書き換えることなく編

435

1

新しく木構造を作成しノード6をAとして追加

264

135

編集者

36A集を行うため、読み書きを並列に行うことが可能である。図 1 では、ノード 6 をノード A へ書き換える処

図2

並列に読み書きが可能な非破壊的木構造

理を行なっている。
非破壊的木構造を用いて、コンテンツマネージメン編集前の木構造

12

編集後の木構造

1

新しく木構造を作成しノード6をAとして追加

32トシステムの開発を行う。

1
35 コンテンツマネージメントシステムの実装
コンテンツマネージメントシステムのデータ構造

3としては木構造を用いると述べた。我々が開発してい45645

図1

木構造の非破壊的編集

6Aる木構造データベース Jungle [3] について説明する。

Jungle は、非破壊的木構造を扱う木構造データベースで、既に Java による実装が存在する。本研究では、Haskell を用いて実装を行った。コンテンツマネージ
非破壊的木構造の基本的な戦略は、変更したいノードへのルートノードからのパスを全てコピーする。そして、パス上に存在しない (編集に関係のない) ノードはコピー元の木構造と共有することである。
編集は以下の手順で行われる。

メントシステムに組み込んで利用しているが、他のシステムに組み込むことも可能である。

5. 1 データベースオブジェクトと木の作成

5. 3 データ構造

木の作成

木のデータ構造は、データ型で定義されている。

Jungle は複数の木を保持することができる。木には名前がついており、名前を利用して判別を行う。また、作成・編集・削除を行うことができる。
jungle = createJungle
new_jung = createTree jungle " new_tree "data Node =|
{,}

Empty
Node
children:: Children
attributes :: Attributes
deriving ( Show )ソースコード 5ソースコード 2

データベースオブジェクトと木の作成

データ構造

各ノードは、Children としてノードを複数持つこ

createTree 関数を利用して木構造を作成する。とができる。Children および Attributes も、Map を木と木を構成するノード用いて定義されている。

データベースオブジェクトを作成し、木構造とルートノードを取得するためには以下のように記述する。

5. 4 ルートノードの取り扱い

tree = getTreeByName new_jung " new_tree "node = getRootNode tree

非破壊的木構造であっても、どのノードが最新のソースコード 3

木とノードの取得ルートノードなのかという情報が必要である。スレッドセーフに取り扱う必要があるため、Haskell のソフ
トウェア・トランザクショナル・メモリを用いて管理

getTreeByName 関数で名前を指定することで木構している。

造を取得できる。getRootNode 関数でルートノードを取得できる。

5. 5 開発期間の短縮

木の編集

Java 版の Jungle の実装と比較すると、コード行addNewChildAt 関数で、ノードに新しい子を追加数は約 3000 行から約 150 行へ短くなった。また開することができる。また、putAttribute 関数で、ノー発期間は Java 版の実装で、3 ヶ月程度かかったが、ドが持つ連想リストを編集できる。どのノードを編集

Haskell 版の実装は 2 週間程度であった。これによするかという情報は、ルートノードからのパスを渡す

り、関数型プログラミングではコードは短くなり、生ことで解決する。木を編集したあと、updateTree 関産性が向上することが分かった。

数を用いて既存の Jungle に変更を加え新しい Jungle

6 木 構 造 デ ー タ ベ ー ス Jungle を 用 い たを作成する。
new_tree = addNewChildAt tree [0 ,1] 0
new_tree2 = putAttribute new_tree[0 ,1 ,0] " key " " value "new_jungle = updateTree jungle new_tree2

CMS の検証
木構造データベース Jungle 及び Warp を用いて簡単な掲示板ウェブアプリケーションを作成した。同様のウェブアプリケーションを、Java による Jungle 実

ソースコード 4

木の編集

装 及び Cassandra [4] 上でも動かし性能比較を行う。

Cassandra は、Facebook が自社のために開発した分
5. 2 木の取り扱い

散 Key-Value ストアデータベースであり、Dynamo

Jungle の 木 の取り扱いには、Haskell の Map を[5] と BigTable [6] を合わせた特徴を持っている。Java用いている。Map は、平衡木を使った Haskell の連版では、組み込みウェブサーバである Jetty を利用想リストである。連想リストを用いて、名前と木を結する。

びつけている。

6. 1 実験方法

表3

検証に利用するクラスタの仕様

複数のクラスタを利用して、サーバに対して並列名前

概要にアクセスを 5000 回行い、それぞれクラスタの実行CPU
MemoryOS
HyperVisor

RRIntel⃝Xeon⃝X5650@2.67GHz
8GB
CentOS 5.6
VMWare ESXi

平均時間をとる。クラスタ台数を増やすことにより並列度を上昇させ、並列度と実行時間の平均をグラフ化する。測定するのは書き込みと読み込みであり、掲示板のメッセージの取得と掲示板のメッセージの編40集を行う。

35

jungle_haskell
jungle_java
cassandra

負荷をかける対象であるサーバは、マルチコア環境が生かされているか確認するためにコア数の多いマ

avarage time(sec)30

6. 2 実験環境

シンを用いる。サーバの仕様を表 1 に示す。

25

20

15

105

表1

検証に使用するサーバーの仕様
0

名前概要

CPU
物理コア数
論理コア数
MemoryOS
JavaVM
GHC

RRIntel⃝Xeon⃝X5650@2.67GHz * 21224132GB
Fedora 16
1.6.0 39-b04
7.6.30510

図3152025
number of nodes

30354045

読み込みの実験結果

45jungle_haskell
jungle_java
cassandra
40

Warp 及び Cassandra, Jetty は表 2 のバージョンを利用した。

avarage time(sec)3530252015

表2Warp と Cassandra, Jetty のバージョン

名前バージョン

Warp

1.3.9

Cassandra

1.2.6

Jetty

6.1.261050510

図4152025
number of nodes

30354045

書き込みの実験結果と比較して、僅かながら Jungle が速く処理を終えている。
サーバに並列に負荷をかけるクラスタの仕様を表 3に示す。クラスタは最大で 45 台使用する。

6. 4 遅延評価
Haskell は遅延評価を行うが、書き込みの際に問題

6. 3 実験結果が生じる。何かしらの結果を表示するまで、簡約可能

読み込みの実験結果を図 3、書き込みの実験結果をな式の状態で積まれたままとなる。その際メモリを消図 4 に示す。

Haskell 版および Java 版の Jungle は、ほぼ同程度の速度が出ていることが分かる。また、Cassandra

費し、効率のよい領域に入りきらないサイズになると非常に実行結果が遅くなる。
図 6 では、メモリ消費量を表している。実行中メモリ消費量は増えていくが、木の表示を行う 22 秒前込みを繰り返すと実行時間が悪化し、読み込み後、急後まで簡約化は行われない。表示を行った際に簡約化激に実行時間が下がる。読み込みの際には、数万回以され、メモリ消費量が急激に下がっている。

上の書き込みを処理するため数秒から数十秒かかる。
書き込みは、インクリメントしている値を書き込んでいるが順序などは正しく処理できている。
この問題を解決するために、全て遅延評価するので8,854,197,849 bytes x seconds

Mon Jul 15 08:40 2013

bytes

App +RTS -K60G -hcはなく適切な箇所で即時評価を行うことで領域効率を改善する必要がある。

(342)PINNED
500M
MAIN
450M
(1167)editMessageJungle/edi...
400M
350M

(1168)editMessageJungle’/ed...

300M(1258)addChild/addNewChildA...

250M

6. 5 並列処理
Haskell 版 Jungle では、並列実行に問題を抱えて(1256)addChild/addNewChildA...

いる。複数のスレッドが立ち上がり、並列実行してい200M(1260)addChild/addNewChildA...
150M
100M

(1245)putAttribute/putAttri...

50M
0M
0.0

ることは確認したが、シングルコアで実行した場合と(1225)putAttribute/putAttri...

2.0

4.0

6.0

8.0

10.0

12.0

14.0

16.0

18.0

20.0

22.0

比較して実行結果が遅くなる。図 3 や図 4 の結果でsecondsは、Haskell 版はシングルコアで実行している。
並列に動かした場合の実験結果を図 7 に示す。

図5遅延評価のメモリ消費

508 CPU
1 CPU4540

図 4 の結果では、オプションで推奨されるヒープ領サイズを変更しない場合の実験結果を図 6 に示す。

avarage time(sec)

域のサイズを変更してある。推奨されるヒープ領域の3530252015140
default
large_memory

10120

500

avarage time(sec)

100510152025
number of nodes

3035404580

図7

並列に動かした場合の実験結果

6040

本研究のウェブアプリケーションとは別に、簡単な20例題を並列で動かした場合でも実行速度の向上を確
00510152025
number of nodes

30354045

認することはできなかった。並列処理で速度向上を達成することは今後の課題である。

図6

推奨されるヒープ領域のサイズを変更しない場合の実験結果

7 おわりに
7. 1 本研究のまとめ評価を行ったあとに実行時間がどのように変わるか

本研究では、Haskell による非破壊的木構造を用いを示すため実験方法を変更してある。実行時に書き込た CMS の実装を行った。Haskell は生産性が高く、みだけではなく、クラスタ台数を変更する際に 10 台

本システムの実装においても開発期間およびコード増やすごとに一度読み込みを挟むようにした。書き行数は非常に短くなった。

木構造データベース Jungle と HTTP サーバ Warp

において、D-ADD (DEOS Agreement Descriptionを用いて簡易掲示板システムを開発し、既存の JavaDatabase) [7] と呼ばれるデータベースがある。本論文の実装と同程度の性能を達成できた。

で説明する 木構造データベース Jungle は、D-ADDへの応用を目指しており、DEOS プロジェクトの一

7. 2 今後の課題環として行なっている。

書き込みの際に、遅延評価のためにメモリを多く使用する問題がある。いくつかの式の評価を正格に切り

参 考 文 献替え、領域効率を向上しなければならない。

[1] The warp package. http://hackage.haskell.
org/package/warp. [Online; accessed 19-July-2013].
[2] 玉城将士, 河野真治. Cassandra を使ったスケーラビ
リティのある cms の設計. 情報処理学会, March 2011.
[3] 玉城将士, 河野真治. Cassandra と非破壊的構造を用いた cms のスケーラビリティ検証環境の構築. 日本ソフトウェア科学会, August 2011.
[4] Avinash Lakshman and Prashant Malik. Cassandra - a decentralized structured storage system.
LADIS, March 2003.
[5] Giuseppe DeCandia, Deniz Hastorun, Madan
Jampani, Gunavardhan Kakulapati, Avinash Lakshman, Alex Pilchin, Swaminathan Sivasubramanian, Peter Vosshall, and Werner Vogels. Dynamo:
Amazon’s highly avaliable key-value store.
[6] Fay Changand Jeﬀrey Dean, Sanjay Ghemawat,
Wilson C. Hsieh, Deborah A. Wallach, Mike
Burrows, Tushar Chandra, Andrew Fikes, andRobert E. Gruber. Bigtable : A distributed storege
system for structured data.
[7] Deos. http://www.dependable-os.net/osddeos/data.html. [Online; accessed 19-July-2013].
[8] 玉城将士, 河野真治. Cassandra を使った cms の pc
クラスタを使ったスケーラビリティの検証. 日本ソフトウェア科学会, August 2010.
[9] Nancy Lynch and Seth Gilbert. Brewer’s conjecture and the feasibility of consistent, available,
partition-tolerant web services. ACM SIGACTNews, 2002.

また、並列処理を行った際に実行速度が向上するよう再設計を行う必要がある。
現在の Jungle には木構造を永続化する仕組みが備わっておらず、実装しなければならない。
分散環境で Jungle を効率よく利用するために、木構造をマージする仕組みを実装する必要がある。マージにはお互いの木の情報が必要になる。どのようにマージすべきなのかは、ユーザが知っていると考えられるが、データベース間で過度の情報をやり取りを行うと負荷が上昇するおそれがある。どの程度の情報が必要であるのか検討しなければならない。

7. 3 DEOS プロジェクト
2006 年に独立行政法人科学技術機構の CREST プ
ログラムの 1 つとして始まったプロジェクトである。

DEOS プロジェクトは、変化しつづける目的や環境の中でシステムを適切に対応させ、継続的にユーザが求めるサービスを提供することができるシステムの構築法を開発することを目標としている。DEOS プロセス