Mercurial > hg > Papers > 2022 > ikki-master

title: GearsOSの分散ファイルシステムの設計
author: Takahiro Ikki, Shinji Kono
profile: 琉球大学理工学研究科情報工学専攻
lang: Japanese
code-engine: coderay


## GearsOSのファイルシステムの設計と実装
- DataGearとCodeGearという単位を用いるOS
- DataGear単位のTransactionとしてファイルシステムを設計
  - 従来のOSのファイルシステムには型とTransactionが無い
- APIとしてTake/Put/Peekを採用した
- 通信としてもDBアクセスとしても使える(メモリからSSDへの通信に見える)
- 本研究ではsocket baseな通信とWordCountの例題を作成した


## GearsOSの基本単位
- CodeGear
  - 実行Codeの単位
  - 入力DataGearと出力DataGearを持つ
  - goto文(jump命令)を使って遷移する
  - 実行単位は途中で割り込まれたりしない(Atmocity)
- DataGear
  - Cの構造体に相当する
  - ノーマルレベルでは変更されない(関数型プログラミング)
- C言語を拡張する形でCbC言語により実装される


## CodeGearとDataGear
- InputDataGearを受け取って、CodeGearが処理し、OutputDataGearを出力する
- OutputDataGearは次のCodeGearのInputDataGearとなる
- ファイルシステムではDataGearをkeyで待ち合わせる
<div style="text-align: center;">
  　<img src="images/cg-dg.pdf" alt=cgdgの関係図 width="600">
</div>

## GearsOSのInterface
- JavaのInterfaceに相当する
- APIとなるCodeGearの名前と型を書く(__next(...)が継続)
- 引数渡しの構造体として使う(引数はすべてここに定義される必要がある)
```
typedef struct Tree<>{
    union Data* tree;
    struct Node* node;
    __code put(Impl* tree,Type* node, __code next(...));
    __code get(Impl* tree, Type* node, __code next(...));
    __code remove(Impl* tree,Type* node, __code next(...));
    __code next(...);
} Tree;
```


## Interfaceの呼び出し
- createで作成する(通常の関数呼び出し)
- DataGearとして作成する場合はnewを使う
- gotoでputAPIを呼び出す(nextは継続)
- InterfaceなどのDataGearは、プロセスに相当するContextにすべて格納される
```
struct Queue* queue = createSychronizedQueue(context);
struct Task* task = new Task();
goto queue->put(task, next(...));
```


## Interfaceの実装
- Interfaceの実装に使われるデータ構造を、記述するImplementがある
- 実装で使われるDataGearを記述する(ヒープに確保される)
- create時にAPIを実装するCodeGearが、Interfaceの構造体に代入される
```
typedef struct SynchronizedQueue <> impl Queue {
  struct Element* top;
  struct Element* last;
  struct Atomic* atomic;
} SynchronizedQueue;
```


## CodeGearとDataGearにはメタレベルなものが存在する
- メタレベルな記述はトランスコンパイラにより自動生成される(記述することも可能)
- CodeGearの前後にMetaなCodeGearが挿入される
<div style="text-align: center;">
　<img src="images/meta-cg-dg.pdf" alt="ノーマルレベルとメタレベルの視点からのGearの関係" width="800">
</div>

## stubCodeGearとgoto meta
- ContextからInputDataGearを取り出す(stubCodeGear)
- OutputDataGearをContextに書き込み、次のCodeGearを呼び出す(goto meta)
- stubCodeGear/goto metaは変更可能(メタプログラミング)
<div style="text-align: center;">
　<img src="images/meta-cg-dg.pdf" alt="ノーマルレベルとメタレベルの視点からのGearの関係" width="800">
</div>

## GearsOSのファイルシステムの設計
- DataGearの単位でデータを操作したい
- ファイルは通信データに対応した複数のストリームを持つ
- Transactionとしてatomicに操作したい
  - 従来のファイルシステムのTransactionはUserレベルで実装される
- ファイル操作と通信を同じAPIで実現する
  - Take/Put/Peek
  - ChristieのDataGearManagerを参考にする


## Take/Put/Peek
- ファイルはQueueで構成される
- putでQueueに追加
- takeでQueueからの取り出し
- peekでQueueから取り出さない読み出し
  - 次にTakeされるDataGearを先読みする
<div style="text-align: center;">
  　<img src="images/QueueElement.pdf" alt=Queueの構造 width="800">
</div>

## GearsFSのトランザクション
- GearsOSのCodeGear操作はatomicなので割り込まれない
  - atomicityはOSが保証する
  - これによりTake/Put/PeekがTransactionであることを保証する

## QueueによるGearsOSのファイル
- GearsOSのファイルはDataGearを保持するQueueとなる
- オンメモリのファイルに相当する
- Queueをデバイスにcopyして持続性を実現する
- 書き込み先はDataGearManagerで選択する

## PutのImplementation
- QueueのElementをnewで作成する
  - Elementには任意の型のDataGearが格納されている
- Queueのリンクを構築する
- 継続nextに跳ぶ

```
__code putSingleLinkedQueue(struct SingleLinkedQueue* queue, union Data* data, __code next(...)) {
    Element* element = new Element();
    element->data = data;
    element->next = NULL;
    queue->last->next  = element;
    queue->last = element;
    goto next(...);
}
```

## TakeのImplementation
- QueueからElement経由でDataGearを取り出す
- Queueのリンクを修正し、取り出されるデータをnextへ引き渡す
```
__code takeSingleLinkedQueue(struct SingleLinkedQueue* queue, __code next(union Data* data, ...)) {
    printf("take\n");
    struct Element* top = queue->top;
    struct Element* nextElement = top->next;
    if (queue->top == queue->last) {
        data = NULL;
    } else {
        queue->top = nextElement;
        data = nextElement->data;
    }
    goto next(data, ...);
}
```


## GearsOSのDataGearManager
- Take/Put/PeekはDataGearManagerに対して行う
- LocalDGM:メモリ上のQueue
- RemoteDGM:他のノードやプロセスあるいはストレージデバイスをあらわす
  - RemoteDGMは対応する相手のLocalDGMと接続される
- DataGearManager上には複数のQueueがあり、keyで識別する
- Take/Peekは書き込みを待ち合わせる
- 複数のTakeを待ち合わせることができる

## DataGearManagerによる通信構成
- 任意の相手のRemoteDGMを作成することでTopologyが形成される
- RemoteDGMはproxy(RemoteDGMに書き込むと相手のLocalDGMに書き込める)
- この構成は分散フレームワークChristie(当研究室作成)と同じ
<div style="text-align: center;">
　<img src="images/Remote_DataGearManager.pdf" alt="RemoteDGMの関係図" width="550">
</div>


## socket通信によるRemoteDGMの実装
- GearsOSはUnix上の言語フレームワークとして実装されている
- Unixのsocket通信を使ってQueueのputを実装する(send/recvはUnixのAPI)
- proxy側はQueueにputされたDataをsocketで送信する
```
__code sendDataRemoteDGMQueue(struct RemoteDGMQueue* cQueue, union Data* data, __code next(...), __code whenError(...)){
    char recv_buf;
    int send_size, recv_size;

    send_size = send(cQueue->socket, data, sizeof(union Data), 0);
    recv_size = recv(cQueue->socket, &recv_buf, 1, 0);
    //error処理は省略
    goto next(...);
}
```

## 受信側の実装
- ファイル本体(Local側)はsocketからDataを取り出す
- 取り出されたデータはQueueにputされる
```
__code getDataLocalDGMQueue(struct LocalDGMQueue* cQueue, __code next(...), __code whenError(...)){
    int recv_size, send_size;
    char send_buf;

    union Data* recv_data;
    recv_size = recv(cQueue->socket, recv_data, sizeof(union Data), 0);

    //error処理は省略
    Gearef(context, cQueue)->data = recv_data;
    goto putLocalDGMQueue(recv_data, next);
}
```

## 複数のストリームから構成されるファイル
- 入力されるデータに応じた個別のstreamを備えたい
- Streamはkey nameを持ち、keyでアクセスを行う
- Queueのリストとして赤黒木を用いる
- DataのTake/Put時には必ずkey nameの指定が必要となる

<div style="text-align: center;">
　<img src="images/newGearsFile.pdf" alt="複数ストリームの設計" width="300">
</div>

## wordCountの例題
- ファイル内の文字列を1行づつ受け取り、文字列,行数をカウントする例題
- 文字列送信側とCount側を別ノード上で行うことで、ファイルの呼び出しと通信処理が構成できる
<div style="text-align: center;">
　<img src="images/slideGearsWC.pdf" alt="リモートDGMによるWordCount" width="550">
</div>

## wordCountの例題
- 二つのDataGearManagerのペアで構成される
- acknowledgeを逆方向のRemoteDGMによる通信で実現する(現在は直接送信)
<div style="text-align: center;">
　<img src="images/slideGearsWC.pdf" alt="リモートDGMによるWordCount" width="550">
</div>


## 現在のGearsFile APIの開発状況
- 実装ずみ
  - API:put/takeに対応したファイル通信
    - 単一のQueueによる通信の記述をした
  - QueueのリストとなるTree(赤黒木)
  - atomicな操作が行えるQueue(SynchronizedQueue)
    - 複数からのアクセス時にデータ整合を保つ
- 実装中
  - key指定による任意なstreamの操作が行えるファイル
  - ファイル単位での通信の記述(Queue単体でない)


## 結論
- GearsOSのファイルの設計を行った
  - ファイルの構造の設計
    - DataGear単位での操作が行える
  - socketによる通信部分の実装
    - GearsOS上でのソケット通信の記述
  - APIの段階的な設計記述
    - Proxyによるファイル通信
- Queue(stream)単位でない、ファイル単位の通信

## 将来的な課題
- TopoplogyManagerの設計
  - 参加したノードを任意の形のTopologyに接続する機能
  - ファイルシステム向けの機能を追加したい
    - DNS
    - 中枢としてのTopologyノード監視
- Securityシステムの追加
  - ファイルpermission
  - 分散ファイルシステムへの不正なアクセスの防止


## GearsOSの生成形の問題点
- GearsOSのメタレベルの処理の記述はトランスコンパイラにより行われる
- 場合によりメタレベルの記述を行わなくてはならない
  - 他のInterfaceを継承したオブジェクトからのDataGear継承
    - 例)Queueからのデータ取り出し
    - トランスコンパイラはどのInterfaceに記述されたDataGearを参照するべきか判断が難しい

## トランスコンパイラのバグの例
- ContextからのDataGearの取り出し方が間違っている

```
__code Task3(TQueue* localDGMQueue, FileString* string){
    goto Task4();
}

__code Task3_stub(struct Context* context){   //正しいstub
  TQueue* localDGMQueue = (struct TQueue*)Gearef(context, TQueue)->tQueue;
  FileString* string = Gearef(context, TQueue)->data;
  goto Task3(context, localDGMQueue, string);
}

__code Task3_stub(struct Context* context) {  //自動生成されたErrorなstub
	TQueue* localDGMQueue = Gearef(context, TQueue);
	FileString* string = Gearef(context, FileString);
	goto Task3(context, localDGMQueue, string);
}
```

## 並列処理構文par gotoが持つ問題
- par gotoとはGearsOSに実装された並列処理構文である
- StreamQueueに対するput/takeの並列処理の実装をpar goto構文で試みた
- par gotoはトランスコンパイラへの依存性が高い
  - stubCodeGearのように任意な書き換えが行えない
- 特定のCodeGearの宣言のみでしか正常な処理が生成されない
  - Interfaceに記述されたAPICodeGearではバグが生じる
  - par gotoでの使用を前提としたCodeGearを書かなくてはならない
- 処理が重いという問題点も存在する

##  GearsFile APIによるWordCount(1/3)
- FileOpen側(NodeA)とWordCount側(NodeB)でノードが別れる
- (手順1)FileOpen側はFilePloxyにDataRecordをputする
- (手順2)WordCount側は処理の後、ackを返信する
<div style="text-align: center;">
  　<img src="images/slideGearsWC.pdf" alt=ChristieAPIによるWordCount width="800">
</div>

##  GearsFile APIによるWordCount(2/3)
- (手順3)1,2をループし、FileOpen側はEoFならフラグを送信する
<div style="text-align: center;">
  　<img src="images/slideGearsWC.pdf" alt=ChristieAPIによるWordCount width="800">
</div>

##  GearsFile APIによるWordCount(3/3)
- (手順4)EoFを受信したWordCountは結果を返信し、双方の処理を終了させる
<div style="text-align: center;">
  　<img src="images/slideGearsWC.pdf" alt=ChristieAPIによるWordCount width="800">
</div>

## 以下返答用

## PeekのImplementation
- QueueからElement経由でDataGearを取り出す
- Takeとは異なり、Queueのリンクを修正せずに、取り出されるデータをnextへ引き渡す
```
__code peekSingleLinkedQueue(struct SingleLinkedQueue* queue, __code next(union Data* data, ...)) {
    struct Element* top = queue->top;
    struct Element* nextElement = top->next;
    if (queue->top == queue->last) {
        data = NULL;
    } else {
        data = nextElement->data;
    }
    goto next(data, ...);
}
```

## Take/Put/Peek
- PeekはReadOnly (最新の設定を読みこむなど)
- Take/PutはDataGearが一つならUpdateに相当する
- 書き込みが単一スレッドなら順序は保証される
- 書き込みが複数の場合、Putの順序は保証されない
- データベースとの違い
  - putがQueueとして蓄積される
  - Keyが一つしかない(通信路として使える)

## __code next(int ret, ...)の意味
- 軽量継続を表す
- nextは引数として渡されたCodeGear
- int ret は返す値
- ...は軽量継続の呼び出された時の値渡しのInterface
- 一段の呼び出しStackのような役割になる

## CodeGearと再帰呼び出し
- 再起呼び出ししなければ関数呼び出し的に使える(末尾再起)
- 再帰呼び出ししたい場合、明示的に自分でStackを作る
- ...はContextにすべて置かれている
- Processはすべて異なるContextを持っている
- Context自体は共有されない

## DataGearの型
- union Data は一つのプロセス(Context)で使われるすべてのDataGearのUnion
- GearsOSはメタ部分に型に対応する番号を持っている
- 番号を使って型を識別することができる
- 任意の型を格納できるQueueやStackを作成することが可能
- メタレベルではunion Dataを使ってDataGearの詳細に立ち入らず処理できる

## RemoteDGMとacknowledge
- Take/Put/Peekのコマンドは TCP上でacknowledgeを使って通信されている
  - これとは別に自分と相手のCodeGearどうしのacknowledgeが必要
- RemoteDataGearManager経由でacknowledgeを返すのが正しい
  - acknowledgeが重複してしまう
  - メタプログラミングを利用してこの重複を消すことは可能
    - 煩雑な処理

## 複数のストリームによる利点
- 例えばUSBは複数のチャネルを持つ
  - メタデータの取り出しは別streamになる
- 複数の通信によりファイル通信の制御を行う場合がある
  - 通信の停止などのための通信
- 通信として使う場合に複数のプロトコルがある方が良い(FTP)
author	ichikitakahiro <e165713@ie.u-ryukyu.ac.jp>
date	Mon, 28 Feb 2022 22:32:44 +0900
parents	ec3761cbbe24
children