alms.dev

Aidemy の開発者ブログです。

MongoDB からの CSV 生成を20倍高速化するデータ取得のパイプライン化とバイナリサーチ

f:id:ogata_y:20211006114328p:plain
大幅な高速化

TL;DR .

  • データベースからのデータ取得を並列化して、バイナリサーチにより集計ロジックを最適化したことで,従来直列的なデータ取得と単純集計により実装されていた進捗CSVデータの生成・ダウンロードを20倍高速化しました。

  • あわせて、今後の開発能率向上・不具合抑制につながるように、進捗CSVソースコード全体をリファクタリングしました。

進捗CSVの課題

1. バグが多く、CSV生成・ダウンロードが極めて遅い

ALMSでは近年特に管理者向け機能の充実化を進めてますが、中でも「進捗CSV」では管理者が受講者の進捗状況を細かく把握するための情報を集約したデータを提供しており、受講者の進捗管理において欠かせないものとなってます。

お客様や事業部門から機能追加のご要望も多く頂いており、今後益々の充実が期待されている機能です。

一方で、集計するデータの種類・量ともにシステムの中で最も多く、集計のビジネスロジックも複雑化していくことによる不具合が、近年特に目立ってきていました。

  • 表示する進捗率表示が100%を超えてしまうバグ
  • CSVと管理画面の進捗率数値に差分が出るバグ
  • 進捗データの多い大規模チームでダウンロード速度が極端に遅くなる

バグについては個別に取り除いたものの、バグが生まれやすい構造は解消しきれずに抱え続けていました。また、3つめのスピードの遅さは致命的で、とあるチームでは受講者の人数が増えて学習データの蓄積が進んだことで、進捗CSVのダウンロードのための生成処理に時間がかかりすぎるために不適切な通信とみなされてセッション断されるようになり、完全にダウンロード不能となってしまった事例もありました。*1

2. ソースコードの見通しが悪い

進捗CSVは当初の機能リリース後も機能追加が多く後付けで仕様が変更されることも多かったという背景もあってか、ソースコードは混沌としており、開発者目線でも今後継続して効率よくメンテナンスしていくことは非常に難しいと感じさせられるものでした。

例えば、型指定のない再代入可能な変数が上書き更新され続け、関数間では大量の変数がバケツリレーで渡される状況となっていたため、仕様の把握にも一苦労の状況という状況です。

システム全体の結合度や凝集度が近年加速度的に厳しくなってきていますが、進捗CSVはその代表格でもありました。

改善ポイント1: CSV生成の高速化

諸々の課題がある中でも、速度低下の原因を切り分けて、「DBからのデータ取得速度の改善」「集計アルゴリズムの改善」の2軸から速度改善に着手しました。*2

1. DBからのデータ取得速度を改善

「データ取得」の工程を集約する等、全体の集計プロセスを再構成しました。

まず、数万件規模のデータを複数取得する処理が、集計プロセスの中で各所に分散して結果として直列的な処理になっていました。プロセスの呼び出し直後に各種データ取得を並列同時実行するように見直したことで、DBへの負荷を増やすことなく実行速度を改善しました。

加えて、データ取得の手続き上どうしても直列的にならざるをえない箇所(例: ユーザ情報取得→ユーザの進捗情報まとめを取得→ユーザの詳細な進捗情報を取得)は、下図のような工夫を通じて擬似的に並列化することで、DBの特定コレクションへの負荷や同時接続数が極端に高まることがないように配慮しながら高速化を達成しました。

f:id:ogata_y:20211005132047p:plain
データ取得処理のパイプライン化

全工程の律速ユーザビリティに直結する箇所のため、並列取得化により若干複雑な実装となりますが、処理の高速さを優先して実装した箇所になります。

特に、CosmosDB(MongoAPI)の処理能力や負荷を意識して「分割取得数(step)」や「待機時間(wait)」を組み合わせて最適な組み合わせを実験しながら導出することは大変でしたが、適切なパラメータに設定することで実行速度・DB負荷・安定性に雲泥の差が出たため、地道に検証に取り組みました。*3 *4

f:id:ogata_y:20211005132210p:plain
詳細に効果測定

シート名のようにstep, waitのパラメータを組み換えての検証を繰り返して最適な設定値を模索しました。step数を増やしすぎるとクエリがサイズ超過で失敗することもあり、入念な微調整により安定かつ高速なクエリ実行を実現しています。*5

スピードアップ以外の副次的な効果としては、「データ取得→加工→CSV出力」と誰が見てもわかる手順に分割したことで、コードの見通し改善に大きく寄与しています。CSV文字列を生成するClassの唯一の公開責務(CSV文字列生成の全体統括)を担う関数は、以下の15行に要約されました。

  generate = async (): Promise<IResult<ResponseCsv<string>>> => {
    /* 事前準備 */
    this.data = await fetchData(this.userId, this.teamId, this.curriculumId); // データ取得
    this.targetCourses = this.listTargetCourses(); // 出力対象となるコース一覧を絞り込み
    this.preSortForBinarySearch(); // バイナリサーチ用のソート
    this.data.users.sort(this.rowSortLogic); // 行出力順のソート

    /* JSON2CSV用のデータを生成 */
    // ヘッダ部
    const fields: { value: string; label: string }[] = await withInfo('fieldの生成', this.generateFields());
    // データ部
    const body: { [key in string]: string }[] = await withInfo('bodyの生成', this.generateBody(this.data.users));
    this.deleteColumns(fields, body); // 不要列の削除
    return { data: { body, header: fields } };
  };

2.集計アルゴリズムの改善

集計面では、ユーザとユーザ進捗データの突合処理について全探索ではなくバイナリサーチで突合するようにしたことで、加工処理について進捗データ数にもよりますが100〜1,000倍程度の速度改善を実現しました。*6

  export const binarySearch = <T extends { [key: string]: any }>(
    searchKey: string,
    searchValue: string | undefined,
    sortedArray: T[],
    limit = 20
  ): T | undefined => {
    try {
      if (typeof searchValue === 'undefined') return;
      if (!sortedArray.length || sortedArray.length > 2 ** limit) return;
      let left = 0;
      let right: number = sortedArray.length;
      let counter = limit; // 無限ループ防止のためのカウンター
      
      while (left + 1 < right && counter) {
        const mid: number = Math.floor((left + right) / 2);
        const target: string = sortedArray[mid][searchKey];
        target > searchValue ? (right = mid) : (left = mid);
        counter -= 1;
      }

      const exists: boolean = sortedArray[left][searchKey] === searchValue;
      return exists ? sortedArray[left] : undefined;
    } catch (e: any) {
      log4js.getLogger().error(e);
    }
  };

あわせて、集計中に繰り返し利用する情報(例えばコース毎の総エクササイズ数)については予め前計算しておく等の手順も追加しています。

スピードアップの効果としては、テストで作った20,000人チームでの集計作業に元のロジックだと数十分単位かかるところ、数秒程度まで圧縮されました。人数が計算量が指数的に増える部分*7であったため、特に大規模チームになるほどに大きな改善効果の出たポイントです。*8  

改善ポイント2: ソースコードを見通し良くリファクタリング

1. Classベースの再設計でコンポーネントの責務を適切な粒度に分割

バグが発生しやすい内部構造がソースコードに生じていたため、クラス化した上で責務を適切な粒度で分割し、メソッド切り出しやクラス変数等を通じて処理に命名した上で各々の依存関係を再構築しました。

あわせて、変数が関数で複数回バケツリレーされてしまう課題についても、オブジェクト指向で設計し直した柔軟さを活かしてクラス変数として保持することで解消しました。

2. 宣言的な書き方で仕様を見える化

基幹クラスから再代入可能な変数(let)を完全に消せたことは、宣言的に記述できていることの示唆になると思います。

例えば、下記のconstで宣言されている変数については、「総回答数(totalAnsweredNum)とは、カリキュラムコース(filteredCourse)に含まれる受講済コース(userCourse)の回答数の合計である。」と宣言的に書き直したものです。従前では、400行コードリーディングしないと仕様を把握できなかったもので、コードリーディングの量と認知負荷を軽減しました。

  // ユーザーごとの進捗率の分子部分(総回答数)の定義
  // filteredCourse、calcAnsweredNumの詳細については、各変数(関数)内にて同じく宣言的に書かれています
  const totalAnsweredNum = sum(
    filteredCourses.map((course: ExtendedICourse) => {
      const userCourse: IUserCourse | undefined = 
      binarySearch('userCourseId', `${user.userId}_${course.courseId}`, this.data.userCourses);
      return userCourse ? this.calcAnsweredNum(userCourse, course.exerciseNum) : 0;
    })
  );

3. 生成工程の進度の見える化律速箇所特定のためのログ出力

細かい点ですが、将来的にも律速となりうる箇所は、「開始・終了」のログ出力をラップして呼び出すことで、実行プロセス(データ取得→加工プロセス1, 2, 3... → 出力)のどの工程の処理をしているのか、時間を要しているかをさくっと検証・調査できるようにしました。

例えば、ログを通じてオブジェクトの生成を100回繰り返す場所が遅いと検知できて、実装をObject.assignに置き換えたことで実行速度が最大30秒程度も改善した箇所がありました。

4. 型管理の徹底(ex: 列情報をUnion型で管理)

列情報をUnion型で定義し管理することで、出力列に依存した操作に対しても型を頼りにMECEを担保できることで、コーディングの精度・能率・可読性を向上させるとともに、今後の列追加にあたっても整理整頓された状態を維持することができるようになりました。

  // ユーザの基本情報列
  export type BaseColumn =
    | 'userName' 
    | 'email' 
    | 'referenceId' 
    | 'department' 
    | 'memberTag' 
    | 'curriculumName' 
    | 'licenseStartAt' 
    | 'licenseEndAt';

  // 進捗情報列
  export type ProgressColumn = 
    | 'lastAnswered' 
    | 'lastAnsweredTerm' 
    | 'startAt' 
    | 'endAt'
    | 'answeredNum' 
    | 'exerciseNum' 
    | 'progressRate';

  // コース別進捗列
  export type CourseColumnSeed =
    | 'courseId' 
    | 'level' 
    | 'isCurriculumCourse' 
    | 'answeredNum' 
    | 'exerciseNum' 
    | 'progressRate' 
    | 'isCorrectionComplete';

コード行数も、元々は750行あったものが自然と450行程度まで圧縮されました。型情報も隅々まで浸透し、全体を通してコードリーディング時の認知負荷を抑えた設計に出来ました。

まとめ

実行速度を十分に高速化してお客様に不満を感じさせなくなったという改善ももちろんですが、見通しを改善することで今後の機能開発を効率化し、バグ発生リスクを抑制できるコードベースへと全面書き直しできたことに、一番大きな手応えがありました。

特に、進捗CSV全体を通じて宣言的に記述しきれきたことで、従来だと何か仕様について聞かれても「多分こうです...」としか語れなかったり、語るためには多大なコードリーディングの労を要したものでしたが、今は自信を持って「こうです!」と説明できるようになりました。

また、直近では、メール配信用に進捗データを連携させる他案件で今回責務分割したパーツを適切に転用できたことで、追加工数をほとんど発生させずにスピーディーかつ正確に対応できた、という成果も出てきています。

全体を振り返ると、CSVダウンロードに求められる速度のネック感はおおよそ解消し、今後の機能拡張の高速化と保守工数抑制を見据えたコードベースの立て直しが出来ました。経営視点でもROIが非常に良好なリファクタリングになったと振り返っています。

システム全体の結合度の高さ・凝集度の低さを一度に全て改善しきることはとても不可能ですが、今回バックエンド一番の大玉をうまく解きほぐすことができたので、今後も続くリファクタリングの取り組みの中で大きく前進できたと感じています。

Appendix:Repository層を新設・リリースしました

2021年8月27日の執筆日現在、7月以降進捗CSVリファクタリングと同時並行で進めてきたRepository層の新設プロジェクトについても、無事にリリースまで完了しました。

Repository層の新設は、DBとのやりとり(永続化責務)について、窓口ごとに責務集約をしようというシステム安定化・ドメイン知識の偏在解消・コードの可読性向上のための取り組みです。巨大なシステム全体に渡る書き直しとなったため、7・8月のエンジニア工数の大部分を投入し、チームの総力を結集しての取り組みとなりました。

概念検討からプロジェクト進行管理まで大変骨が折れましたが、既存メンバーはもちろん他チームから移管してきた新メンバーも存分に力を発揮してくれたこともあり、本日のリリースまで対計画オンスケジュールで進行し、無事リリースまで結了しています。

*1:本ケース発生時には、フロント側で再帰的に待ち時間を増やすポーリングロジックを実装して、アドホックに対処しました。ポーリングロジックは当時から捨てやすく実装することを意識できていたため、今回のリファクタリング実施後には工数をかけず安全に依存を解消できています。

*2:ユーザー毎の進捗率を要求時に都度計算する必要があるために、一度の処理に必要なデータ量が多く、DBへの負荷軽減のために取得速度を抑制していることが最大のボトルネックでした。さらに、DBからのデータ取得以外にも、集計アルゴリズムに速度低下の要因となっている箇所がありました。

*3:参考: Cosmos DB レート制約の最適化

*4:残課題としては、DBからのデータ取得については分割取得化でかなり改善したものの、取得件数と速度のバランスを見ると本来のMongoの性能を引き出しきれていないという点が気になっています。進捗CSVに限らずシステム全体に渡る課題ですが、今後Mongo・Mongooseのバージョンを更新して適切にクエリ実行計画をログ取得できるようになった段階で、追加で調査・クエリチューニングを実施して更に改善していきたいと考えています。

*5:通常、関係データベースで組まれているシステムであれば、データ取得時点でトランザクション、テーブル間のJOIN(マージ結合やハッシュ結合)で前計算してデータを取得して適切な計算量に抑え込めるケースが多いものかと思います。但し、ALMSはNoSQLのデータベースに依存しており、またデータ取得タイミングもコードの中で区々であったという事情も相重なってか、必要なデータを別々で取得した後にデータ間の突合(findによる全探索)をかける方策を取らざるをえませんでした。

*6:イナリサーチはTypeScriptで適当なライブラリが見当たらず、20行程度で簡単にスクラッチ実装しました。

*7:対象人数n人、進捗データ数m個(nおよびコース数に比例)として、素朴な実装だと計算量O(n * m)となる突合計算をO(n log m)に最適化

*8:今回の集計アルゴリズムの効率化については、今後はmongoのクエリ側に回収することも検討余地があるかと思います。とはいえ、律速にはならない水準まで速度改善できたこと、現状のデータモデリングの都合上でDBではなくアプリ側がハンドリングする方が使い勝手が良いことを鑑みると、このままでも問題ないと感じています。