# GearsOSの分散ファイルシステムの設計
author: 一木 貴裕, 河野 真治

profile: 琉球大学理工学研究科情報工学専攻 河野研究室

lang: Japanese

code-engine: coderay


## OSと密に結合したファイルシステムの設計
- 信頼性と拡張性の保証を目的としたGearsOSを開発中
- GearsOSの分散ファイルシステムを開発したい
- 分散フレームワークChristieの構成をもとにする
- Christieが持つTopologyManagerという機能を使う
    - プログラムの通信とストレージの接続を管理する

## 従来のファイルシステムの問題点
- データベースになっていない
- 重複度やリカバリをアプリケーションが担当している
- 暗号化などのセキュリティもアプリケーションが担当している
- OS自体がこれらの機能を持つのが望ましい

### 従来のファイルシステムのトランザクション
- レコードのTransactionとして提供していない
    - 提供しているのは
        - ファイルのロック
        - ディレクトリの名前の置き換え
- FileSystemのAPIを総括してトランザクションとして設計したい
        
### ファイルの型
- OSレベルから見たファイルの型が存在しない
    - 実行形式のみをOSが認識している
    - 型の区別はアプリケーションに委ねられている
        - lsとreadmeなどの型の区別がつかない
- OS自体がファイルの型を見分けるように設計したい

### ファイルの名前自体がデータベースのkeyとなっていない
- 従来ではファイル固有のIDとファイル名を紐付けしたりする
- 様々なファイル単位が混同になっている
    - 複数のレコード
    - 複数の表
    - sqlite3
- OS自体がユニークなファイルIDのリストを保持する設計にしたい

### 重複度とファイルリカバリ
- ファイルの複製が行われた際の安全性が確保できない
- バックアップデータを勝手な場所に置かれてしまう
    - バックアップデータをOSが管理する

### 署名と暗号化
- ファイルの署名もしくは暗号化の機能をOSファイルシステムに持たせたい
- 公開鍵と秘密鍵
    - 秘密鍵を持つファイルを作成したユーザと公開鍵を持つ任意のユーザが相互にエンコードとデコードが行える仕組み
    - 署名はファイルにメタデータとして保持できるようにする
    - 鍵の管理もOSが担うようにしたい

## OSの信頼性について
- アプリケーションを動かすOSには高い信頼性が保証されるべきである
- OSの処理やコードの量は膨大になる
    - テストコードを用いた信頼性の保証は困難であると言える
- 数学的な背景に基づいた形式手法を用いて検証したい
    - 定理支援証明
    - モデル検査
- OSを形式手法にて証明するには状態遷移単位での記述が求められる
- GearsOSはメタレベルとノーマルレベルの計算を分離して記述が行える構成である
    - メタレベルの計算でプログラムの整合性を検証する

## Continuation based C(CbC)
- CbCとはC言語の下位言語である
- CbCは関数呼び出しでなくjmp命令で移動する継続を導入している
    - jmp命令でコード間を移動することにより軽量な継続を実現している
    - CbCでは継続を用いてfor 文などのループ文を実装する
- Gearというプログラム概念を持つ
- CbCでは関数の代わりにCodeGearという単位でプログラムを行う
    - CodeGearによる記述は形式手法に必要な状態遷移そのものとして見ることができる。

## Gearsの概念
- CodeGear:従来のプログラムやスレッド
- DataGear:変数データ
- CodeGearはDataGearと呼ばれる変数データを入力として受け取る
    - CodeGearの処理結果を別のDataGear に書き込む
- 入力のDataGearをInputDataGear
- 出力されるDataGearをOutputDataGear
    - CodeGearが参照できるDataGearはInput/output DataGearに限定される。
- CodeGearは関数呼び出しのスタックを持たない
    - 一度コードブロックを遷移すると元の処理に戻ってこられない

<center><img src="https://i.imgur.com/zCiaOrY.jpg" width="500px"></center>
<center>

    
## GearsOS
- CbCを用いて記述されたOSである
    - CodeGearとその入出力であるDataGearを基本とする
- 現在は並列フレームワークとして実装されている
    - 実用的なOSのプロトタイプとして実装を目指している
- ノーマルレベルからではCodeGearの遷移は単純にCodeGearがDataGearをInput/Outputを繰り返し、コードブロックを移動するように見える
    - 実際にはCodeGearから別のCodeGearへの遷移の際、データ整合性の確認などのメタ計算が加わる
    - これをMetaCodeGearと呼ぶ
    - MetaCodeGearはCodeGearごとに実装される
    - MetaCodeGear内で参照されるDataGearをMetaDataGearと呼ぶ
- MetaCodeGearやMetaDataGearはプログラマが直接実装することはない
- 現在はPerlスクリプトにより、GearsOSのビルド時に生成される

<center><img src="https://i.imgur.com/eL9rOF5.jpg" width="500px"></center>
<center>
CodeGearから別のCodeGearへ遷移する際のDataGearなどの関係性
</center>    

## Christie
- Christieは並列分散フレームワークである
    - java言語で構成される
- GearsOSと似てはいるが別のGearというプログラミング概念をもつ
- Gearは以下の四種類が存在しする。
   - CodeGear (CG) : スレッド、クラス
   - DataGear (DG) : 変数データ
   - CodeGearManager (CGM) : ノード
   - DataGearManager (DGM) : データプール


### CodeGear(以下CG)
- DataGearを参照しながらプログラムを実行する
- 処理に必要なDataGearのkeyをプログラム内に記述する必要がある
- CGMがsetupという処理を行うことで待ち合わせが始まる
- プログラム(CG)内に記述された全てのDataGearのkeyにデータが格納されると実行される
    
### DataGear(以下DG)
- keyと変数データの組み合わせで構成される
- アノテーションを用いて記述する
    - アノテーションの種類によりkeyの変数データの参照方法が変わる
    
### CodeGearManager(以下CGM)
- CodeGear,DataGear,DataGearManagerを管理する
- 分散処理のノードに相当する
    - それぞれポートを持つ
- putという操作でDagaGearを任意のCGMの持つDataGearManagerに格納する
    
### DataGearManager(以下DGM)
- 各CodeGearManagerが1つづつ所持している
- データプールになっておりCGMが利用するDGを全て保持している
- LocalDGMとRemoteDGMの二種類存在する(後述)

## Christieのコード例
- Christieを用いてHelloWorldを記述した際のコードが以下となる。
```
public class StartHelloWorld extends StartCodeGear {

    public static void main(String[] args){
        CodeGearManager cgm = createCGM(10000); 　//CGMの作成
        cgm.setup(new HelloWorldCodeGear());　//CGMにCGをsetupする
        cgm.getLocalDGM().put("hellokey","hello");　//setupされたCGが持つDGのkeyにデータを設定する
        cgm.getLocalDGM().put("hellokey","world");//同上
    }
}
```

```
public class HelloWorldCodeGear extends CodeGear {

    @Take //アノテーション
    String hellokey; //待ち合わせ&プログラム内で使用するDataGear

    @Override
    protected void run(CodeGearManager cgm) { //CGの処理内容
        System.out.print(hellokey + " ");
        cgm.setup(new HelloWorldCodeGear());
    }
}
```


## LocalDGMとRemoteDGM
- LocalDGMは各ノード固有のデータプールである
- RemoteDGMは他ノードのLocalDGMに対応するプールである
   - 接続しているノードの数だけ存在する
- DGMのput操作を行う際にはLocalとRemoteのどちらかを選ぶ  
  - Localであれば、LocalのCGMが管理するDGMに対しDGを格納する
  - RemoteDGMを指定してputすると、接続している任意のノードにDGを送信する
- CGMの接続をする=接続先のRemoteDGMを作成する

![](https://i.imgur.com/BJNVkii.jpg)


## TopologyManager
- Christieがもつ通信形成を簡潔に行う機能である
    - Topologyに参加を表明したノードを自動的に配線する
        - Topologyの形状に合わせ、各ノードにRemoteDGMを作成する
    - ノードは相対的に接続された別のノードにラベルをつけ参照することができる 
- ソケット接続などの処理を全てTopologyManagerに任せることができる


## GearsOSのファイルアクセスAPI
- WordCount例題を通して構築する
    - WordCount 
        - 指定したファイルの中身の文字列を読み取る
        - 文字数と行列数のcount
        - 加えて文字列を出力する 
- WordCountのコードブロックは大きく分けて二つに分類できる
    - FileOpenスレッド 
        - 指定した名前のファイルをFile構造体としてOpenする
        - ファイル内文字列を1行づつブロックとしてWordCountスレッドに送信する
    - WordCountスレッド 
        - 文字列のブロックを受け取る
        - 文字列を表示する
        - 文字数と行列のCountUpをする
- WordCountとファイルの接続はプログラムの外で接続される
    - 将来的にChristieのTopologyManagerで接続を行いたい

<center><img src="https://i.imgur.com/IFffeMq.jpg" width="600px"></center>

## 競合アクセスを可能とするChristieAPI　
- GearsOS上のファイルは名前のついた大域的な資源として扱われる
    - 複数のCodeGearから競合的にアクセスされる場合がある
- 上記のAPIではファイルとWordCountが直接的に結合されている
    - 競合的なアクセスには対応していない
- Christieを元とした、DataGearsStreamに名前をつけてアクセスするAPIを導入する

    
<center><img src="https://i.imgur.com/K3nYFkh.jpg" width="600px"></center>
<center>
WordCountをRemoteDGMを用いて構成する際の協調図
</center>    
    
- NodeAにて任意のファイルを開く
    - ファイルの中身を1行ごとに文字列をNodeBに送信する
- NodeBにてWordCountの処理(countup,文字列表示など)を行う
    - ackとしてフラグをNodeAに返信する
- 文字列ブロックの送信と受け取りのフラグのやり取りでループする 
- NodeBがeofをフラグとしてNodeAから受け取った場合、WordCountの結果を表示する
        - 両ノードの処理の終了を行う
- NodeA,B間のファイル内文字列のBlockとフラグの送受信は、RemoteDGMを介して行う
    - RemoteDGMにはkeyとデータの組み合わせとなる(Christie仕様の)DataGearが必要となる。
    - DGのpushにあたる操作はmeta部分で実装を行う    


##  FileSystem Implementation
- GearsOS FileSystemは単なるDGのリストとなる
   - これはDataGearManagerにあたる
   - ファイルの中身を要求された際、リスト内部のDGを順次に送受信する形となる
- 別ノードからファイルを参照する際はRemoteDGMを通してファイルの中身を送受信する
- 持続的なファイルシステムとして保存する場合、DGのリストをSSDなどのデバイスに格納する
- メモリ領域において不要となったメモリはmeta部分にて回収を行う

    
<center><img src="https://i.imgur.com/lcqdiSx.jpg" width="600px"></center>
<center>
ファイルを別ノード上から参照する際の図
</center>


## File Persistency
- 持続性のあるファイルとして保存されたDGMを操作するには、SSDなどデバイス上に保存されたDGMをLocalDGMとして呼び出せば良い
<center><img src="https://i.imgur.com/GWzj9qW.jpg " width="600px"></center>
<center>
<center>
デバイス上に保存されたDGMを呼び出す際の図
</center>
    

## UNIX FileSystemとの比較 
- UNIX FileSystem において File Stream と Socket Stream は煩雑な処理が必要となる
    - GearsOSではSocket Stream部分をTopologyManagerが担う
    - FileStreamはmetaCodeGear部分で実装することでユーザレベルから隠蔽することができる
- UNIXではStreamに型がないので不完全なデータが生じてしまう
    - GearsOSではこれらはDGMのメタな機能として実装することができる
- UNIXファイルシステムにはfsckと呼ばれる修復機能があるが、メモリに対する修復機能は存在しない。
    - GearsOSではメモリの一部不良に対応する機能をDGMとして作るといったことが考えられる。
-  GearsOSではDGMの名前とその中のDataGear Streamに対応するkeyでアクセスする対象が決まる
    - 自由な名前空間の構成が行える
    - これはUNIXでいうi-node番号に相当する
    
## まとめ
- GearsOS におけるファイルシステム API の設計を議論した
- 現在のファイルシステムの問題点
- Gearsファイルシステムに搭載する機能の考察
- GearsファイルシステムのAPIは二種類が存在する
    - アプリケーションで閉じた決定的な実行を行う直接接続したもの
    - DataGearManagerに名称をつけ、競合的なアクセスを許可するもの
- ファイルはDataGearManager
- DataGearManagerは分散環境での通信でもある
- 精進して実装していきたい