ABEJA で Research Engineer をやっている中川です．普段は論文読んだり，機械学習モデルを実装したり，インフラを構築したりしています．今回のブログでは，Insight for Retail の一機能として提供しているリピータ分析に用いる特徴量DBの改善に向けた言語選定について紹介します．

※ たくさんの方々からのコメントありがとうございます．いただいた観点をベースに「2020-04-14 追記」以下に実験を追加しました．

モチベーション

リピート分析では，任意の特徴量をクエリに最も類似した特徴量を数100msec以内に検索する必要があり，一般的なデータベースでは実現することが難しいという課題がありました．そこで，われわれは python で独自のインメモリデータベースを実装し運用してきました．このデータベースがサービスの成長に合わせて限界を迎えつつあるので，アルゴリズムと実装を見直したいというのが今回の活動のきっかけです．さらに，どうせ見直すならモダンなコンパイル言語を採用して，勉強しつつ高速化できたら楽しいよねというのが本ブログのテーマである言語選定に繋がってきます．そして，モダンなコンパイル言語なら Go か Rust かなという気持ちで言語選定を始めました．なお，本ブログの筆者である中川は Go も Rust も駆け出し修行中なので，指摘事項等ご指導いただけたら幸いです．

ここで，特徴量DBの特徴を挙げると以下のようなポイントがあります．

数十程度のリクエストが常に並列して投げられる．
read と write が同程度発生する．
トランザクションはちゃんと守ってデータの整合性は保ちたい．
数100msec 以内にレスポンスを返す必要がある．

まず，これらのポイントを Go と Rust で比較して実装できるかを調査したところ，両者とも何の問題もなく実装できそうなことが分かりました．詳細は後続の章をご覧ください．続いて，今回の改善活動の主眼である性能について調査を行いました．確かに Go と Rust の性能を比較した記事はググればそれなりに見つかりますが，特徴量DBの特徴を鑑みると，いろいろな要素が絡んだ性能を計測する必要があり，これにばっちりとハマった比較を見つけることは出来ませんでした．そこで特徴量DBを簡単な問題設定に落とし込んでやることで Go と Rust の性能を比較することにしました．なお，チームでの開発を考えた際，性能以外の例えば習得難易度なども非常に重要な要素になってくることは承知の上です．まずは性能を見た上でその他もろもろを見て実際に言語選定したいよね，というのと，ぶっちゃけ久しぶりにちゃんと新しい言語を書いて覚えたいというのが一番のモチベーションだったりしています．

問題設定

特徴量DBの全機能を実装した上で Go と Rust の性能を比較するのはさすがに現実的ではないので簡易な問題設定のインメモリDBを実装することで性能を比較することにしました．

まず，インメモリDB としての最低限の機能を備えるため，以下の機能を挙げました．

search と update の gRPC の口を持っている．
search はリクエストとして value を受け取り，一致するレコードを全て返す．
update はリクエストとしてレコードの index と新しい value を受け取り，既存のレコードに上書きする．
search と update には RWLock をかける．

さらに，特徴量DBへのリクエストを模して以下のようなクライアント処理を考えます．

ある value を持つレコードを全件検索する．
取得したレコードの value を新しい値に書き換えて更新する．

この処理を並列してインメモリDBに投げることで必要最低限の実装により特徴量DBを模した問題設定で性能検証を行いました．

実装

つらつらと説明するよりも，実際にコードを見た方が早いだろうということで，性能検証に用いたコードの主要部分を載せます．なお，コードの全体は中川の github から確認できます．

github.com

gRPC

まずはインターフェースとなる gRPC の実装です．上記を愚直に実装しただけです．

syntax = "proto3";

import "google/protobuf/empty.proto";

package db;

// In memory DB definition.
service DB {
  // Search record.
  rpc Search (Value) returns (Records) {}
  // Update record.
  rpc Update(Records) returns (google.protobuf.Empty) {}
}

// DB records.
message Records {
  repeated Record records = 1;
}

// DB record which contains index and value.
message Record {
  int32 index = 1;
  int32 value = 2;
}

// The value of record.
message Value {
  int32 value = 1;
}

サーバ実装

現状の実装からどの程度高速化されうるのかにも興味があったため python も含め Go, Rust の3つの言語でサーバは実装しました．

python

python の標準ライブラリでは RWLock がサポートされていないので，直近でも開発が比較的盛り上がっている fasteners を用いて実装しています．

class DB(db_pb2_grpc.DBServicer):

    N = int(1e6)

    def __init__(self):
        self.lock = ReaderWriterLock()
        self.records = [random.randint(0, DB.N / 10) for _ in range(DB.N)]

    def Search(self, request, context):
        with self.lock.read_lock():
            records = [
                db_pb2.Record(index=index, value=value)
                for index, value in enumerate(self.records)
                if value == request.value
            ]
        return db_pb2.Records(records=records)

    def Update(self, request, context):
        with self.lock.write_lock():
            for record in request.records:
                self.records[record.index] = record.value
        return empty_pb2.Empty()

Go

初めてマトモに Go を実装しましたが，標準で filter がサポートされていないのはちょっと驚きでした．

// Server is used to implement db.DBServer.
type Server struct {
    sync.RWMutex
    records []int32
}

// Initialize with random records.
func NewServer () *Server {
    const N int32 = 1e6
    records := make([]int32, N)
    var i int32 = 0
    for ;i < N; i++ {
        records[i] = rand.Int31n(N / 10)
    }
    return &Server{records: records}
}

// Implement RPC methods.
func (s *Server) Search(ctx context.Context, in *pb.Value) (*pb.Records, error) {
    query := in.GetValue()
    records := make([]*pb.Record, 0)
    s.RLock()
    for index, value := range s.records {
        if value == query {
            records = append(records, &pb.Record{Index: int32(index), Value: value})
        }
    }
    s.RUnlock()
    return &pb.Records{Records: records}, nil
}

func (s *Server) Update(ctx context.Context, in *pb.Records) (*empty.Empty, error) {
    s.Lock()
    for _, record := range in.GetRecords() {
        s.records[record.GetIndex()] = record.GetValue()
    }
    s.Unlock()
    return &empty.Empty{}, nil
}

Rust

gRPC のデファクト実装がなかったので，どうせ使うなら最新ライブラリがよいよねという気持ちで tonic を採用しました．また，ちゃんと性能が出るように計測においては --release ビルドをしています．さらに tokio も rt-threaded 付きにすることで高速化しています．

[package]
name = "rust"
version = "0.1.0"
authors = []
edition = "2018"

[dependencies]
rand  = "0.7"
tonic = "0.1"
prost = "0.6"
tokio = { version = "0.2", features = ["rt-threaded", "macros"] }

[build-dependencies]
tonic-build = "0.1.0"

// Define DbImpl as implementation of DB package.
#[derive(Debug, Default)]
pub struct DbImpl {
    records: Arc<RwLock<Vec<i32>>>,
}

// Initialize with random records.
impl DbImpl {
    fn default() -> Self {
        const N: i32 = 1e6 as i32;
        let mut rng = rand::thread_rng();
        let records: Vec<i32> = (0..N).map(|_| rng.gen_range(0, N / 10)).collect();

        DbImpl {
            records: Arc::new(RwLock::new(records))
        }
    }
}

// Implement RPC methods.
#[tonic::async_trait]
impl Db for DbImpl {
    async fn search(&self, request: Request<Value>) -> Result<Response<Records>, Status> {
        let query = request.into_inner().value;
        let records = self.records.read().unwrap().iter().enumerate().filter_map(
            |(i, &value)|
            if value == query {
                Some(Record {
                    index: i as i32,
                    value: value
                })
            } else {
                None
            }).collect();
        let records = Records {
            records
        };

        Ok(Response::new(records))
    }

    async fn update(&self, request: Request<Records>) -> Result<Response<()>, Status> {
        let mut records = self.records.write().unwrap();
        for record in request.into_inner().records {
            records[record.index as usize] = record.value;
        };

        Ok(Response::new(()))
    }
}

クライアント実装

クライアントは最も慣れた言語である python を用いて実装しています．以下の関数をマルチスレッドで並列化して実行しました．なお，localhost は実験の際には適宜変えています．

def test_update(query, value, cycle):
    for _ in range(cycle):
        with grpc.insecure_channel('localhost:50051') as channel:
            stub = db_pb2_grpc.DBStub(channel)
            # Search records.
            start = time.time()
            response = stub.Search(db_pb2.Value(value=query))
            logger.info('receive request.', extra={'type': 'read', 'elapsed': time.time() - start})
            # Update records value.
            records = response.records
            for record in records:
                record.value = value
            start = time.time()
            stub.Update(db_pb2.Records(records=records))
            logger.info('receive request.', extra={'type': 'write', 'elapsed': time.time() - start})

検証結果

以下の2つの観点から性能を比較しました．なお，どちらの場合においても初期状態で 10⁶ コのデータが溜まっているものとしました．

リクエストの並列数が増えた時の性能影響
長期運転した際の性能影響

また，性能検証にはサーバとクライアントともに AWS EC2 の m5.large を用いて計測しました．なお，AMI は Canonical, Ubuntu, 18.04 LTS, amd64 bionic image build on 2020-01-12 を使いました．

1. リクエストの並列数が増えた時の性能影響

並列数が増えた場合の処理性能の違いを明らかにするために，リクエストの並列数を 1, 5, 10, 15, 20 と増やしていった際のクライアントサイドでの処理時間を計測しました． RWLock があるため，単純に平均を取って性能を比較してよいのかというと議論はありますが，それも含めた上での平均的な性能を知るために python, Go, Rust のそれぞれで並列数に対する処理時間をプロットした結果が以下です．なお，Go と Rust に関しては1,000回施行を行っていますが，python については遅すぎて我慢ならなかったので100回しか施行は行っていません．

Search

f:id:ynaka81:20200322181846p:plain

Update

f:id:ynaka81:20200322181918p:plain

この図を見るに python に比べて圧倒的に Go, Rust の方が性能のよいことがわかります．並列数を増やせば増やすほど，その傾向は顕著です．並列数20の時を見れば100倍以上性能差がありました．一方でこれだけだと，Go と Rust の性能比較は見えないので，Go と Rust だけにフォーカスを当てると，

Search

f:id:ynaka81:20200322182354p:plain

Update

f:id:ynaka81:20200322182409p:plain

Go と Rust に大きな性能差を見ることはできないという結果になりました．そこで両者の処理時間の分布を見てみると，

Search

f:id:ynaka81:20200322182627p:plain

Update

f:id:ynaka81:20200322182644p:plain

分布の外形はおおよそ同じで Go の方がやや Update が速く，Rust の方はやや Search が速いということが見て取れます．しかし，Go と Rust の言語選択に影響を与えるほど大きな違いには見えませんでした．

2. 長期運転した際の性能影響

続いて，GCを前提とした言語かどうかは Go と Rust の大きな違いではあるので，長期運転した際の性能影響を明らかにするために，10並列で数時間程度リクエストを投げ続けた状態での性能を計測しました．まずは統計量を見てみると，

f:id:ynaka81:20200328173532p:plain

とRust の方が最大値が2倍程度大きいこと以外は Go も Rust もほぼ変わらないことがわかります．次に，より定性的に性能を分析するためにそれぞれの時間経過に対する処理時間の変化をプロットしました．

Search

f:id:ynaka81:20200328173316p:plain

Update

f:id:ynaka81:20200328173847p:plain

両者とも当然ですが時間経過に対して処理時間が変わることはありませんでした．長期運転をすると GC を前提とした Go の方が処理時間が跳ねてしまうことが多いのかと思いましたが，Rust の方が処理時間が跳ねることが多かったのはちょっと意外でした．とはいえ，75%タイルで見た性能はほぼ変わらないので気にするほどではなさそうです．

最後に

特徴量DBに適する言語選定を行うため，マジメ半分，遊び半分で Go と Rust で簡易版特徴量DBを実装し性能測定を行いました．結果としては，どちらも python よりは圧倒的に高速で，少なくともターゲットとするデータサイズにおいては大きな差異はないことが分かりました．あとでチームと相談して，習得・採用難易度や実装する楽しさなどを軸に決めていきたいと思います．

毎日ちょろちょろ勉強しながら進めて合計2,3日分の稼働で特徴量DBの言語選定の方針が見えてきたのは非常に有意義な取り組みだったかなと思います．そして，何よりも新しい言語を覚えるのは楽しかったです．やっぱりモダンなコンパイル言語って痒いところまで手が届くし速いし，言語もすごく進化しているんだなぁと感じた取り組みでした．個人的には大規模チームで採用するならしばりプレイ感があってコード品質を保てそうな Go, 少人数で遊ぶなら実装していて楽しい Rust かなという感想です笑

次回は実際にどの言語を採用し結果どうだったのかという話をできればなと考えています．

2020-04-14 追記

ブログを公開したことで多くの方から非常に有益なコメント，issue，PR をいただくことができ，感謝とともにブログを書いてよかったなと感じています．いただいたコメントに関連して，追加で以下2つの観点を検証をしたので追記しました．なお，コードはすべて上記にある中川の github にあるので，今回は結果の記載だけにして，実装が気になる方はレポジトリもご確認ください．

Rust における複数 RwLock 実装間での性能差異
GC が発生しやすい状況で長期運転した際の性能影響

なあ，性能検証は上記同様の構成で実施しました．

1. Rust における複数 RwLock 実装間での性能差異

issue にて指摘いただいたように Rust には，非同期処理に対応しているか，read / writer 優先のいづれなのか，という点で複数の RwLock 実装があるようです．

cf. Rustの実装について。tokio::sync::RwLockを試してみてください · Issue #1 · ynaka81/in_memory_db_comparison · GitHub

そこでそれぞれの実装について，上記同様1,000回施行を行った時の性能を以下にプロットしました．なお，参照点として Go の性能も点線でプロットしてあります．また，以下では std::sync::RwLock を std，async_std::sync::RwLock を asyncstd，tokio::sync::RwLock を tokio と省略して書いていきます．

Search

f:id:ynaka81:20200414082840p:plain

Update

f:id:ynaka81:20200414082925p:plain

asyncstd は前回検証した std よりやや高速で似たような傾向を示しつつ，tokio に関しては std よりも低速という結果になりました．より深堀するために，それぞれの処理速度の分布を見てみると，

Search

f:id:ynaka81:20200414083304p:plain

Update

f:id:ynaka81:20200414083332p:plain

asyncstd と std は同じ傾向を示しつつ，tokio だけ明らかに異なる速度分布を示していることが分かります．asyncstd と std (Linux において) は reader 優先で tokio は writer 優先であることを踏まえると，その違いが明確に現れた非常に面白い結果だと思います．今回のように search と update が同程度発生するワークロードでは，並列に処理できる search をなるべく優先して処理してしまう reader 優先の方が向いているようです．さらに，非同期処理に対応していて最も高速であるという観点から，今後は asyncstd を用いるのがよさそうです．

2. GC が発生しやすい状況で長期運転した際の性能影響

前回 search & update で長期運転した時の性能影響を検証しましたが，そもそも GC の対象となるような一時オブジェクトがあまり生成されていないんじゃないか？というご指摘をいただきました．確かにその可能性は高いと考え，update の代わりに add & delete するようなワークロードで長期運転してみました．対象としては前回と同様の Go と std を用いた Rust に加えて，上記でよさそうだと判明した asyncstd を用いた Rust を検証しました．実験としては前回と同様で10並列で数時間程度リクエストを投げ続けました．まずは統計量を見てみると，

f:id:ynaka81:20200414090301p:plain

add & delete のワークロードでも特に GC が問題になることはなく，前回とほぼ同じ結果でした．ただ，こちらのケースでも asyncstd の std に対する優位性は言えそうです．また，処理時間の時間変化をプロットしてみると，

Search

f:id:ynaka81:20200414091325p:plain

Add

f:id:ynaka81:20200414091348p:plain

こちらも特筆すべきポイントはなさそうです．やはり，高々 100KB/sec の一時オブジェクトが生成される程度では GC による性能劣化は観測できないようです．この点においても，Go と Rust の言語選定に影響はなさそうです．

追記まとめ

コメントや，やり取りの中で得た知識を元に追加で検証を行いました．結果としては，少なくとも今回想定するワークロードでは，Rust で実装する場合には read 優先で非同期対応な async_std::sync::RwLock を使えば良いこと，Go で GC が発生したとしても性能に問題がある程度ではないことが分かりました．

改めてコメントや issue，PR をくださった方ありがとうございました．これがブログを公開する醍醐味ですね．

ABEJAでは一緒にチャレンジしていくメンバーを募集しています！！こちらも興味ある方はぜひ．

hrmos.co www.wantedly.com

ABEJAの中の人と話ししたい！オフィス見学してみたいも随時受け付けておりますので、気軽にポチッとどうぞ↓↓

ABEJA Tech Blog

中の人の興味のある情報を発信していきます

Go vs Rust : 特徴量DBに適するのはどっち！？ (2020-04-14 実験追記)

モチベーション

問題設定

実装

gRPC

サーバ実装

python

Go

Rust

クライアント実装

検証結果

1. リクエストの並列数が増えた時の性能影響

Search

Update

Search

Update

Search

Update

2. 長期運転した際の性能影響

Search

Update

最後に

1. Rust における複数 RwLock 実装間での性能差異

Search

Update

Search

Update

2. GC が発生しやすい状況で長期運転した際の性能影響

Search

Add

追記まとめ