Mercurial > hg > Papers > 2017 > suruga-sigos

comparison paper/sigos.tex @ 17:6caa52eb6bb8

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
sigos_ver13
author suruga
date Fri, 21 Apr 2017 22:04:41 +0900
parents 3d6da7e52aca
children c7d6641b9d62
comparison
equal deleted inserted replaced
16:a94c70db18c9 17:6caa52eb6bb8
276 一つの木が極端に大きくなる場合もあるが、それを分散して格納するのは難しい。 276 一つの木が極端に大きくなる場合もあるが、それを分散して格納するのは難しい。
277 ここでは、一つの木は一つのノードに納まる大きさだと仮定する。 277 ここでは、一つの木は一つのノードに納まる大きさだと仮定する。
278 Jungleの木は信頼性向上とアクセス速度の向上のために、複数のノードに格納される。 278 Jungleの木は信頼性向上とアクセス速度の向上のために、複数のノードに格納される。
279 木の変更は複数のノードを伝搬し、特定のJungleの木のルートノードに到達する。 279 木の変更は複数のノードを伝搬し、特定のJungleの木のルートノードに到達する。
280 そこで、木の状態が確定する。 280 そこで、木の状態が確定する。
281 一つのルートノードではなく、複数のノードに対して、多数決などの方法を用いることも考えられるが、 281 一つのルートノードではなく、複数のノードに対して、多数決Commitなどの方法を用いることも考えられるが、
282 今回は単一のルートノードを用いる。 282 今回は単一のルートノードを用いる。
283 この方法は、読み込みに対して書き込みが少ない場合、あるいは書き込みが単一ノードのみからくる場合に有効であると考えられる。 283 この方法は、読み込みに対して書き込みが少ない場合、あるいは書き込みが単一ノードのみからくる場合に有効であると考えられる。(表\ref{fig:WriteTime})
284 284
285 従来のJungleDBの分散機能の測定はJetty Webサーバー込みで行なっており、DBに対する負荷は直接的には大きくなかった。 285 従来のJungleDBの分散機能の測定はJetty Webサーバー込みで行なっており、DBに対する負荷は直接的には大きくなかった。
286 JungleDBに対して十分な負荷をかけるhttpリクエストを生成するのは困難であった。 286 JungleDBに対して十分な負荷をかけるhttpリクエストを生成するのは困難であった。
287 そこで、Jungleの分散性能そのものを調べるために、Webサーバー抜きで測定したい。 287 そこで、Jungleの分散性能そのものを調べるために、Webサーバー抜きで測定したい。
288 288
301 301
302 今回、実験で分散構造としてJungleの動くノード16台を木構造に接続する。 302 今回、実験で分散構造としてJungleの動くノード16台を木構造に接続する。
303 この木のルートノードをルートjungleと呼び、末端ノードをリーフjungleと呼ぶ。 303 この木のルートノードをルートjungleと呼び、末端ノードをリーフjungleと呼ぶ。
304 \begin{figure}[htpb] 304 \begin{figure}[htpb]
305 \begin{center} 305 \begin{center}
306 \includegraphics[width=60mm]{./pic/WriteTime.pdf} 306 \includegraphics[width=80mm]{./pic/WriteTime.pdf}
307 \end{center} 307 \end{center}
308 \caption{今回測定する木構造} 308 \caption{複数のルートノードを持つ木構造}
309 \label{fig:WriteTime} 309 \label{fig:WriteTime}
310 \end{figure} 310 \end{figure}
311 まず、末端のJungleにUserが書き込みをし、Jungleからuserにレスポンスが返ってくるまでの時間を測定する。 311 まず、末端のJungleにUserが書き込みをし、Jungleからuserにレスポンスが返ってくるまでの時間を測定する。
312 次に、Jungleの変更がルートのJungleにコピーされるまでの時間の測定方法を提案するJungle同士の接続には、当研究室で開発している分散フレームワークであるAliceを用いる。 312 次に、Jungleの変更がルートのJungleにコピーされるまでの時間の測定方法を提案する。Jungle同士の接続には、当研究室で開発している分散フレームワークであるAliceを用いる。
313 \section{まとめ} 313 \section{まとめ}
314 本研究では、始めに破壊的木構造データベースであるJungleについて説明を行い、次にJungleの性能を上げるために実装した点を挙げ、最後に分散環境での Jungle の書き出し実験の手法について述べた。実装した点は、まず Jungle の Index の Update を高速化させるために、前の版の Index と値を共有しながら Update を行う、差分 Update の実装を行なった。次に、線形の木を正順で構築する際、木の変更の手間が O(n) になる問題を解決するために、 Differential Jungle Tree の実装をした。 Differential Jungle Tree は、自身の末尾のノードの情報を保持している。この末尾ノードを使用して、木の編集や検索を行う。次に、自動的に木のバランスを行い、最適な形の木構造を構築する Red Black Jungle Tree を実装した。 Red Black Jungle Tree は、自身が Index を構築する Default Jungle Tree により、編集できる。また、ノードは、木のバランスによって Path が編集ごとに変わってしまうため、属性名と属性値のペアでノードを指定できる、 Red Black Jungle Tree Editor の実装を行なった。 314 本研究では、始めに破壊的木構造データベースであるJungleについて説明を行い、次にJungleの性能を上げるために実装した点を挙げ、最後に分散環境での Jungle の書き出し実験の手法について述べた。実装した点は、まず Jungle の Index の Update を高速化させるために、前の版の Index と値を共有しながら Update を行う、差分 Update の実装を行なった。次に、線形の木を正順で構築する際、木の変更の手間が O(n) になる問題を解決するために、 Differential Jungle Tree の実装をした。 Differential Jungle Tree は、自身の末尾のノードの情報を保持している。この末尾ノードを使用して、木の編集や検索を行う。次に、自動的に木のバランスを行い、最適な形の木構造を構築する Red Black Jungle Tree を実装した。 Red Black Jungle Tree は、自身が Index を構築する Default Jungle Tree により、編集できる。また、ノードは、木のバランスによって Path が編集ごとに変わってしまうため、属性名と属性値のペアでノードを指定できる、 Red Black Jungle Tree Editor の実装を行なった。
315 また、Jungleの分散機能に対する測定手法を提案した。 315 また、Jungleの分散機能に対する測定手法を提案した。
316 今後の課題として、Jungleは非破壊でデータを保持し続けるため、非常に多くのメモリを使用してしまう。ある程度の単位で過去のデータの掃除を行いたい。Jungleは、過去の木に対するアクセスをサポートしているため、データの掃除を行うタイミングが明確ではない。なので、メモリから追い出すタイミングを定義する必要がある。 316 今後の課題として、Jungleは非破壊でデータを保持し続けるため、非常に多くのメモリを使用してしまう。ある程度の単位で過去のデータの掃除を行いたい。Jungleは、過去の木に対するアクセスをサポートしているため、データの掃除を行うタイミングが明確ではない。なので、メモリから追い出すタイミングを定義する必要がある。
317 317