シート 1
中心トピック
  研究概要
    メールで出したやつ
  研究目的
    世の中のデータは木構造が多い
      RDBは木構造を格納するのには向いていない
        表で保存するとプログラムでのデータ構造とのギャップが大きい
      そのまま格納したい
        そこでjungle
        一応kvsやjsonをそのまま保存できるNoSQLというDBもある
      DBは負荷に強くないと駄目
        性能を上げる方法
          スケールアップ
            高性能のマシンを用意することで処理速度を上げる
              単一のマシンじゃ限界がある
          スケールアウト
            汎用的なマシンを追加することで性能を上げる
              マシンを追加すればするほど性能は上がる
          スケールアウトの方が良い
      スケーラビリティ大事
        Cap定理
          永続性
          可用性
          分断耐性
          大抵の分散DBは２つしか保証できない
            Jungleは閉じた整合性を持つためCap定理を回避している
              木ごとに閉じた整合性を持っている
  Jungleの説明
    非破壊的木構造
      編集時に上書きせず木の複製を作って変更を行う
        書き込みと読み込みを同時に行える
    閉じた整合性を持っている
      そうやってcap定理を回避している
        木ごとに閉じた整合性
          木をマージすることで新しい整合性のある木を生成する
      cap定理の説明はいる？
    Jungleのデータ構造
      Jungle
        JungleはTreeの集まり
          TreeはNodeの集まりでできている
        どんなデータでもそのまま格納できる
          ただしどのような形でマッピングするかは定義したほうが良い
          そうした方が効率よくデータを扱える
      Node
        自身の子供のListとAttributeを持つ
          StringのkeyとByteBufferのvalue
    木の変更方法
      Editorを使って更新を行う
        addNewChild
          指定した位置に子Nodeを追加する
        deleteChildAt
          指定した位置のNodeを削除する
        putAttribute
          指定した位置のNodeにkeyとValueの組み合わせでNodeを挿入する
        deleteAttribute
          Pathで指定した位置のNodeのkeyで保持されているAttributeを破棄する
        pushPoP
          木のルートの上にノードを追加する
            log(1)でノードを追加できる
            線形のTreeの構築に使える
        これらの更新はLogとして木に保存される
    Jungleの永続性
      LogをmsgPack形式で書き出すことで行われる
      TreeOperationLog形式
    データの検索
      検索はIndexとTraverserを使用して行う
        Indexは自作の非破壊赤黒木を使用した
          型はTreeMap<String,TreeMap<String,List<TreeNode>>>
          条件に一致したNodeのIteratorを返す
          Jungleは親ノードへのリンクを持っていないためParentIndexを使用し親を参照する
            型はTreeMap<TreeNode,TreeNode>
            必要な検索がある
        Traverserは木のノードを順番に走破しながら条件に一致したNodeのIteratorを返す
        検索条件はTraverserに実装されているfindを使用する
          引数
            検索の条件のQuery
            Indexを使った検索に使うString key
            Indexを使った検索に使うString value
    過去のTreeにもアクセスできる
      全てのverの木を持っているためuuidを指定することでそのversionの木にアクセスできる
    XML形式のファイルをImportもできる
  C#版
    和馬くん
  NetWork版も軽く紹介する
    並列信頼研で作っている並列分散フレームワークAliceを使用している
      DS CSの説明はどうする？
    トポロジーの作成
      トポロジーを記述したfileをAliceのトポロジーマネージャーに読み込ませる
        例を書く
      トポロジーマネージャーに自分がどこに接続を行えばいいかを問い合わせる
    データの伝播はpsgPackに変換したLogを送る
      LogにはどのNodeにどんな処理を行ったかが書かれている
        Logを受け取ったJungleはLogに書かれた処理を行う
      msgPackでシリアライズできるよう新しいNetworkLogを作成
        クラスに@Message アノテーションを付ける
        クラスの中身を全てプリミティブ型にする
        またLogにはどの木に対しての変更化が書かれていなかった
          NetWorkLogには変更を行ったTreeNameも記述
          Timestampも
    データが衝突したらタイムスタンプが早い方のデータを優先する
      他のマージ方法を実装したい
  Jungleを使った例題アプリケーション
    Htmlのレンダリングエンジン
      どのような条件でRenderingするかが書かれたLayoutFile
        component
          table
            colsで区切られたしたをtableとして分割する
          date
          text
          image
            imageは画像を保存したddirectoryまえのPathをJungleに保存する
              そこを参照する
              保存先は /image/保存年/保存月/保存日/imageName
          title
        どこに対応しているかは use = title　といったように記述されている
      Renderingする内容が保存されたContextTree
      この２つを参照してhtmlを作る
        outputStreamを持って木をtraverseする
          確定するたびoutputStreamにwriteする
      ちゃんと考えてTreeを構築しないと大変なことになる
        コードが読みづらい
        余計な処理が増える
        良い例と悪い例を書く
          図にすると良いかな？
            Attributeを各Nodeにわけるのは駄目
  測定
    どうしよう
      昔のをとりあえず使う？
      レンダリングエンジンの測定って比較対象どうすんの？
  今後の課題
    データの書き出し
      木に変更が加わる度にlogを書き出しているためBufferingしてまとめて書き出したい
    データの設計指標の定義
    差分Listの実装とか
    Indexの差分アップデート
    マージ部分の実装
      今はタイムスタンプの早い方を実装する部分しか書かれていいない
  目次
    研究目的
    非破壊的木構造データベースJungle
      JungleはTreeの集合で出来ていること
        TreeはNodeの集合で出来ている
          Nodeは子供のListと
    Jungleを使った例題アプリケーション
      BBS
        どうして実装した？
          Jungleを可視化したい
          ブラウザ上から直感的に操作したいよね
        Browserを実装する上で新しく追加した機能
          NodePathを使って木から対応するNodeを取ってくる機能
      maTrix
        maTrixの説明
          どうして実装した？
            Jungleに実用データベースたる性能はあるか？
              表現力はあるか？
              速度は出る？
              機能は足りているか？
          複数の木構造のデータからなる
            人
            役職
            役割
            権限
          複数の木構造のデータがお互いを参照することで組織構造を表現している
            Indexを使って参照する
              Indexを使用するために検索機能が必要
                find
        検索時親をたどる必要があった
          親への参照をNodeは持っていなかった
            ParentIndexを実装することで解決した
        必要になったもの
          検索API
          Index
          ParentIndex
          非破壊赤黒木
          XMLReader
        性能測定
          昔の結果だけど書く？
          書くならrenderingEngineの性能評価はRenderingEngineのsubsectionになる
      C#版Jungle
      renderingEngine
        どうして実装した？
        ２つの木を参照しHtmlを出力する
          どのように出力するかが記述されたlayoutTree
            component
              table
              text
              title
              date
              image
                imageはJungleに保存するのではなく保存したディレクトリのpathを保存する
            どこのlayoutがどこに対応しているかはuse = "conponent"で記述する
          出力する内容が記述されたContextTree
        出力する際はOutputStreamを持ってwriteしていく
          確定したら即write
        作った上でわかったこと
          ちゃんと考えてデータを格納しないとコードが大変なことになる
          ちゃんとデータの設計をしようね
        性能測定
          ギャップがあるTreeとの比較
          多分少し早いと思う
    まとめ