Pythonで書いた分散KVSのシミュレータをRustに書き換えようとして苦労している話

どうも ryo_grid です。5カ月強ぶりの投稿です。
　
今回は、Pythonで書いた分散KVSのシミュレータ（**マルチスレッドなプログラム**）をRustで書き換えようとして苦戦している話について書きます。

# Contribution
作業のメモ書きとかを書くのはガイドライン違反らしいので、この記事が単純なその手のたぐいではなく、ソフトウェア開発の世界に Contribution をするものであることを最初に書いておきます。

1. 他言語で書いたプログラムをRustにポーティングする場合の事例紹介である
2. 他言語から来た者がRustでマルチスレッドなプログラムをRustで書く時のはまりポイントについて示し、ある程度、どのように書けば良いかの情報を提供する（最適解でない可能性は高い。どころか、まったく的外れの可能性も無くはない）
3. 多言語からRustに入る時に、他言語で気楽にできていたことがRustだとそうでもない場合があるという事例の紹介を含む（筆者の知識不足の可能性もあり）


以上です。

# 書き換えようとしているプログラムについて（概要）
- Pythonで書いた分散KVSのシミュレータ。**マルチスレッドなプログラム**
  - リポジトリのルート: [rust_dkvs](https://github.com/ryogrid/rust_dkvs)
  - 書き換えようとしている元コード（Python）: [chord_sim](https://github.com/ryogrid/rust_dkvs/tree/428fbfb24d720a24f20adf9984d1a56a3b6af5bc/chord_sim)
  - 経緯としては、Rustを身に着けたく、その学習の題材として、以前から書いてみたかった分散KVSを書くことにした
     - Chordプロトコルを用いたDHTベースのKVS
     - 参考
          - [分散システムにおけるScalableな名前付けアルゴリズム「Chord Protocol」を実装してみた  - Qiita](https://qiita.com/taisho6339/items/7f849b65e2deab6759a1)
          - [ChordアルゴリズムによるDHT入門 - slideshare](https://www.slideshare.net/did2/chorddht)
          - [VIOPS04: DHTの基礎知識- slideshare](https://www.slideshare.net/viopsjp/dht20091211)
          - [Chord: A Scalable Peer- to-peer Lookup Protocol for Internet Applications - slideshare](https://www.slideshare.net/GertThijs/chord-presentation)
  - 参考としてあげたページやスライドを見ると分かるように、結構ややこしい自律分散システムであって、いきなり実システムを書き始めると悲惨なことになることが目に見えていた（初学者であるRustでやったら尚更）
  - そこで、設計の検証をまず行うことにした。具体的にはシミュレータをPythonで実装して行うことにした。Pythonを選択したのは書き慣れている言語でかつ、今回のような用途に用いても問題がないと判断したため
  - 実装しているうちに、「これ、実システムをモデリングした実装になっているので、シミュレータ内の本来ノード間のRPCとなる部分を本物のRPCに書き換えれば、ほぼそのまま実システムにできるのでは？」とか考え始めた
    - つまり、Python製シミュレータ -> Rust製シミュレータ -> Rust製実システム、 と段階を踏んでいけば、スムーズにゴールにたどり着けるのではないかと考えた
    - そんなわけで、Python版の実装の最後の方では、Rustには例外の機構がないので、Rustの標準的なエラーハンドリングのお作法であるResult型を模した方法をPythonで行うようなリライトを入れたりもしている（余談）

# 書き換えようとしているプログラムの作り（ざっくり）
※Chordの知識をいくらか必要としますが無くてもなんとなく分かるかと思います

- 実システムにおけるノードに対応したオブジェクトがわさわさいる
- 各ノードオブジェクトは実システムであっても持っているであろう情報は自前で保持している。例えば、自身のノードID、経路表、保持しているデータ（KVSシステム上で自身が担当となったもの）等々。それらでは、dictやlistを利用している
- また、各ノードには（本来、自発的に）定期的な実行を行う必要のあるstabilize処理と呼ばれるものや、KVSシステムのユーザが呼び出す put と get、Chordネットワークに参加するためのjoin処理、また、それらを実現するためのノード間でやりとりをするメソッドを公開している（Pythonではprivateメソッド化することはできなかった気がするが雰囲気で読み取って欲しい）
- 実システムでは通常存在し得ないが、シミュレータであるということで、stabilize処理を各ノードに定期的に行わせるスレッド（定期的にランダムに選択したノードの対応するメソッドを呼び出す）がいる。同様にして、put、get および join処理 についても存在する
- それらのスレッドがsleepを挟んだwhileループによって、各々に定められた時間間隔で動作することで、KVSの基盤となるChordネットワークが構築されていく過程や、その上で put や get が行われた場合に期待通りの動作が行われるかが確認できる、という寸法
- **以下が、Rustへの書き換えにおいて重要となるポイント**
  - 全てのノードオブジェクトはグローバル変数として定義された dict （以降、ノードオブジェクトdictと呼称） に仮想的なアドレス（実システムではIPアドレスなどになる）の文字列をキーとして格納されている
    - これは、**各スレッドが動作する際の頭で、処理を行わせるノードのオブジェクトを取得する必要があるため**
    - また、各スレッドはノードオブジェクトが公開しているメソッドをまず呼び出すが、そのメソッド内の処理をそのまま実行していくので、その中で他のノードとやりとりをする場面が出てくる
    - 現状はシミュレータなので、ただのメソッド呼び出しであるが、相手ノードのオブジェクトは実システムとの乖離を極力無くすため、Chordプロトコルを介して知ったノードアドレス（IPアドレスなどに相当）を用いて、**実質的にグローバルな関数（クラスメソッド）として定義されたメソッドを介して取得する**（実システムでは、IPアドレスを知っていればRPC呼び出しができる、というのと同じ）。そして、**当該メソッドは内部ではノードオブジェクトdictにアクセスしてオブジェクトを返す**
  - 他にも、各ノードオブジェクト内のフィールド（dictやlist、独自定義のクラスを含む）が前述の通り存在し、少なくともいくつかのフィールドに設定されているオブジェクトは mutable であり、複数のスレッドからアクセスされる
    - **つまり、ノード情報dictは複数スレッドからdict自体もmutableで、dict内の要素もmutable という形でアクセスされる。またノード情報dictの変数自体には実質的にグローバル変数の形でアクセスできる必要がある**
    - また、マルチスレッドからアクセスされるということは、各スレッドはロックをとるといった排他制御に従う必要がある（対応するミューテックスがグローバル変数として定義されている）。なお、各ノードオブジェクトもオブジェクト内のいくつかのフィールドの個々に対応したミューテックスを持っている

# Rustにポーティングすることを考える
- MVCで言うと、M（Model）をまず考えることが重要というプラクティス（既にあるアプリケーションの場合）？に従って、データの持ち方等々（データモデリングというんでしょうか、こういうの）がPythonコードの時と大きく変わらない形で実現できるかを考える
  - 特にRustはデータ（メモリ領域）の管理に大きな特徴を持った言語であることもあり、不確定要素として大きいのはMのところになる（はず）
- その上で、まずできないといけないことは、上の "**（略）重要となるポイント**" というところに書いた内容に対応するところで、実質的にグローバル変数としてアクセス可能なHashMap（Pythonではdictだった）や Vec（Pythonではlistだった）を、VecやHashMapのオブジェクト（Rustだとstruct）自体がmutableで、加えて、それらが格納している要素も mutable な形でアクセスできるようにすること
- そして、それを複数スレッドから排他制御を伴う形で行えるようにすること
- ついでに、元のPythonコードではコードの作り上、 reentrant（あるロックAを獲得している場合、再度同じロックAを獲得しようとしてもブロックしたりしない） なミューテックスを必要としていたため、reentrant なミューテックスを用いた排他制御とすること
- ちなみに書き替えを行っている最中のコードは以下です
  - [chord_sim_rust](https://github.com/ryogrid/rust_dkvs/tree/rust-ported-chord-sim-210507/chord_sim_rust)

# ちょっと調べてみた
- そもそも、Rustはいわゆるグローバル変数に相当するものをなるべく使わないでコードを書かせるというポリシーがあるようだ
  - 正確には immutable なものだけを許すという感じ
  - 参考: [Rustのstatic変数とthread local - Qiita](https://qiita.com/tatsuya6502/items/bed3702517b36afbdbca)
  - しかし、上の記事にも記述があるようにlazy_staticマクロを利用するなど抜け道もある
  - また、lazy_staticマクロを使えば、ミューテックス（上の記事ではRWLock型。もっとシンプルなものだとMutex型がある）を用いて、mutable なグローバル変数をマルチスレッドでアクセス可能な形で定義することもできる
  - ただ、RWLock型は reentrant ではない
  - ちなみに、多くの言語ではミューテックス変数のロックを開発者が排他する対象のデータ（複数の場合もあるはず）のアクセス時に獲得し、排他する必要が無くなったタイミングで解放するという排他制御の実装方式が標準的なものと認識しているが、Rustの排他制御の仕組みはデータそのものとミューテックスが一体となっており、ロックを獲得するメソッドの返り値として、排他されているデータへの参照が得られる、といった形になっている（C++などではそのようなライブラリがあるそうだが詳しくは知らない）
- reentrantなロックを提供する parking_lot というクレートを見つけた
  - [parking_lot - crates.io](https://crates.io/crates/parking_lot)
  - このクレートのReentrantMutexを用いることで reentrant なロックを実現できるようである
    - ただ、ReentrantMutexでそのまま排他対象のデータをラップしても、ロックを獲得した場合に可変参照は得られない、とドキュメントにある
      - [Type Definition parking_lot::ReentrantMutex](https://docs.rs/parking_lot/0.11.1/parking_lot/type.ReentrantMutex.html)
    - だが、RefCellでさらにラップすれば可能であると記述されている
- 複数のスレッドでミューテックスで保護されているデータの所有権を共有する
  - ミューテックスを生成する際にArc型でラップすることで可能となるそうです
    - [Arc＜Mutex＜T＞＞という形はデザインパターン - Rustコトハジメ](https://rustforbeginners.hatenablog.com/entry/arc-mutex-design-pattern) 
    - [状態共有並行性 - The Rust Programming Language 日本語版](https://doc.rust-jp.rs/book-ja/ch16-03-shared-state.html)
  - 正直なところいまいち理解できていないのですが、ラップしておくことにしています(まだマルチスレッドなコードを試していないので、その時に分かるのかもしれません)
  

# 上記を踏まえて最低限の動作を確認するコードを書いてみた
Rustコンパイラとの長い闘いを経て、Vecに関しては上の方に書いた要件を満たしたものを書くことができました。
以下はその検証用のコードです。
※Rustには型推論があるため、変数の側に型を明示しなくても良い場面も多いですが、下のコードでは何型が代入されるか分かるように型を明に記述しています

```text:file_placement.txt
.
├── Cargo.toml
├── src
│   ├── main.rs
│   ├── gval.rs
```

```rust:Curgo.toml
[package]
name = "rust_mt_example"
version = "0.0.1"
authors = ["Ryo Kanbayashi <ryo.contact@gmail.com>"]
edition = "2018"

[dependencies]
lazy_static = "1.4.0"
parking_lot = "0.11"
```

```rust:gval.rs
use std::sync::{Arc};
use std::cell::RefCell;
use parking_lot::{ReentrantMutex, const_reentrant_mutex};

pub struct GlobalDatas {
    pub all_data_list : Vec<Arc<ReentrantMutex<RefCell<KeyValue>>>>
    //他のメンバも本来は存在するがこの記事では省略する
}

impl GlobalDatas {
    pub fn new() -> GlobalDatas {
        GlobalDatas {all_data_list : Vec::new()}
    }
}

lazy_static! {
    pub static ref GLOBAL_DATAS : Arc<ReentrantMutex<RefCell<GlobalDatas>>> = Arc::new(const_reentrant_mutex(RefCell::new(GlobalDatas::new())));
}

#[derive(Debug, Clone)]
pub struct KeyValue {
    pub key : Option<String>,
    pub value_data : String,
    pub data_id : Option<i32>
}

impl KeyValue {
    pub fn new(key : Option<String>, value : String) -> KeyValue {
        let tmp_data_id : Option<i32> = match &key {
            Some(key_string) => Some(hash_str_to_int(&key_string)),
            None => None
        };
        KeyValue {key : key, value_data : value, data_id : tmp_data_id}
    }
}

pub fn hash_str_to_int(_input_str : &String) -> i32 {
    //return fixed value
    return 1000
}
```

```rust:main.rs
#[macro_use] extern crate lazy_static;

pub mod gval;
pub use crate::gval::*;

use std::{borrow::BorrowMut, sync::{Arc}};
use std::cell::{RefMut, RefCell};
use parking_lot::{ReentrantMutex, const_reentrant_mutex};

fn get_first_data(gd : RefMut<GlobalDatas>) -> Arc<ReentrantMutex<RefCell<gval::KeyValue>>> {
        let got_data : &Arc<ReentrantMutex<RefCell<KeyValue>>> =  &(*gd.all_data_list.get(0).unwrap());
        let ret : Arc<ReentrantMutex<RefCell<KeyValue>>> = got_data.clone();
        return ret;
}

fn main() {
    let locked_gd : &RefCell<GlobalDatas> = &*gval::GLOBAL_DATAS.lock();
    {
        let locked_gd_mut : &mut GlobalDatas = &mut locked_gd.borrow_mut();
        //Vecに一つだけデータを追加する
        locked_gd_mut.all_data_list.push(Arc::new(const_reentrant_mutex(RefCell::new(KeyValue::new(Some("ryo_grid".to_string()),"pythonista".to_string())))));

        //ここで locked_gd_mutの参照は解放される（はず）
    }

    let re_locked_gd : &RefCell<GlobalDatas> = &*gval::GLOBAL_DATAS.lock();
    let first_elem : Arc<ReentrantMutex<RefCell<gval::KeyValue>>>;
    {
        let re_locked_gd_mut : RefMut<GlobalDatas> = re_locked_gd.borrow_mut();

        //スコープ外に値を逃がしておく
        first_elem = get_first_data(re_locked_gd_mut);
        
        let first_elem_tmp : &RefCell<KeyValue> = &*first_elem.as_ref().borrow_mut().lock();
        let first_elem_to_print : &mut RefMut<KeyValue> = &mut first_elem_tmp.borrow_mut();

        //この時点でのVec内唯一の要素をprintlnする
        println!("{:?}", first_elem_to_print);

        //ここで re_locked_gd_mutの参照は解放される（はず）
    }

    // first_elem変数に逃がしておいたArc型の値の中身をあれこれしてKeyValue型の
    // 可変参照を得る
    let locked_elem : &RefCell<KeyValue> = &*first_elem.as_ref().borrow_mut().lock();
    let locked_elem_mut : &mut RefMut<KeyValue> = &mut locked_elem.borrow_mut();
    
    // 上でVecに追加した要素を可変参照を介して変更する
    locked_elem_mut.value_data = "Rustacean".to_string();

    // 変更された要素をprintlnする
    println!("{:?}", locked_elem_mut);
}
```
　

repl.it のスニペットも用意しておきました。
repl.itにログインして、下のスニペットを fork し、コンソールで cargo run とタイプして実行すると、上記のコードを試すことができます。
 
- [MTReentrantGlobalVec - replit](https://replit.com/@ryo_grid/MTReentrantGlobalVec)


**実行結果**
※初回は必要なモジュールをインストールしたりでドバーっと出力が出ますが、以下ではその出力は省略しています

```shell:shell_output
> cargo run
   Compiling rust_mt_example v0.0.1 (/home/runner/MTReentrantGlobalVec)
    Finished dev [unoptimized + debuginfo] target(s) in 0.90s
     Running `target/debug/rust_mt_example`
KeyValue { key: Some("ryo_grid"), value_data: "pythonista", data_id: Some(1000) }
KeyValue { key: Some("ryo_grid"), value_data: "Rustacean", data_id: Some(1000) }
```

# 解説
- gvalモジュールにGlobalDatas型をTとした時に```Arc<ReentrantMutex<RefCell<T>>>```という型をもつGLOBAL_DATASというグローバル変数を定義しています
  - lazy_staticマクロを用いて初期化しています
  - staticで宣言しているために大文字でないとwarningが出るので仕方なく大文字にしていますがちょっと気持ち悪いですね・・・
  - GlobalDatas型の定義もgvalモジュールにありGLOBAL_DATASと同じ要領でKeyValue型をラップした型を要素としたVecをall_data_listというメンバ変数として持つstructとして定義されています
  - KeyValue型の定義もgvalモジュールにあります
- **つまり、Vecなメンバが1つある以外メンバの無いGlobalDatas型と、Vecなメンバの格納する要素の両方を```Arc<ReentrantMutex<RefCell<T>>>```という形で型付けしたグローバル変数を定義しています**
- main.rs に定義されている main関数では、GLOBAL_DATASのロック獲得し内部のデータを取得し、Vecに要素を一つ追加し、同じファイルに定義したget_first_data関数でVecのメソッドを用いて追加した要素を取り出してみたり、それをprintlnしたり、取り出した要素のメンバ変数を書き換えて見たり、書き換えたものを printlnしてみたりしています
- 各々の処理の度にlockを取得しているので、reentrantであることは確認できたと思っています
  - ただ、RefCell型の参照にborrow_mut() して得た参照は、都度解放してあげないと、もう一度borrow_mut()しようとした際にpanicします（実行時）。可変参照は複数得られないという原則に従った結果なのでしょう。おそらく
  - そのため、上に挙げた検証用のコードでは、参照の解放のため一見意味のなさそうなブロックを中括弧で作って、そこでスコープ切れによる解放を行っています
- もろもろやっていますが、出力を見ると同じオブジェクト（同じメモリ領域にあるデータ）をちゃんと書き換えられていることが確認できるかと思います

# おわりに
- 正直なんかコンパイラに言われることを参考にしつつ、あれこれいじっていたらなんか動いた、的な状態なので、確かな理解の下でこのようなコードを書けるようにしたいところです（&、*、as_refメソッド、bollow_mutメソッド、unwrapメソッドあたりも理解の怪しいものがあり、main関数内などは特にですが、無駄な操作をしているのではないかという気がしています）
- HashMapの場合、どう書けばよいのかよく分からないなーという感じで悩み中です
- get_first_data関数は、本当は関数内でロックをとってデータを返すということをしたかったのですが、```Error : returns a value referencing data owned by the current function``` というエラーが解決できず、引数で必要なデータを渡す形になりました。lockして得たデータのスコープを考えれば当たり前なのかもしれませんが、この手の関数を書くときにいちいちlockしたデータへの参照を渡すのも煩わしいなあという感じで、私の知識不足であることを祈っています
- 他言語からRustにポーティングする場合や、他言語のユーザがRustを使う場合に、Rustではやらない方がいいことをリストしたブログ記事があって、勉強になるなあと思ったので下にリンク貼っておきます
  - [Things you can’t do in Rust (and what to do instead) - blog.logrocket.com](https://blog.logrocket.com/what-you-cant-do-in-rust-and-what-to-do-instead/)

**続編 :**
[Pythonで書いた分散KVSのシミュレータをRustに書き換えようとして苦労している話（2） - Qiita](https://qiita.com/ryo_grid/items/dfe005c980d2fbe48832)