塀の備忘録

上伊那ぼたん描いてます

GoのMinimal Version Selectionについて

はじめに

2022-01-08、オープンソースのnpmパッケージであるcolors.jsとfaker.jsの作者が、不具合を引き起こす実装を意図的に含めたこれらの最新バージョンを公開した。

それらを利用しているプロジェクトは影響を被り、問題のコードが含まれないバージョンへのダウングレードによって当座の問題を回避したはずだ。

その後、colors.jsは2022-01-11時点で問題を含むバージョン(1.4.1や1.4.2など)はnpmからunpublishされたため、npmの最新は安全なバージョン(1.4.0)へと変更済みだ。ゆえにunpublishまでの数日間において^1.0.0のようにキャレット(^)でバージョン指定していたプロジェクトでは1.4.2が選択されてしまっていた。

本件の教訓として、今後は固定バージョン指定でのパッケージ管理を原則化したプロジェクトも少なくないのではないだろうか。

ところで、GoのパッケージマネージャであるGo Modules(vgo)は、Minimal Version Selection(以下、MVS)というアルゴリズムを採用している。これによって、Goはビルドに関わるパッケージ解決において制約を満たしうる最小バージョンを一意に選択する。そのため、依存パッケージのバージョンをロックファイルによって固定する必要がない。

MVSについて

GoのReferenceにMVSに関する公式ドキュメントが存在し、アルゴリズムが簡潔に説明されている。しかし、今回はRuss Cox氏の”Go & Versioning”における解説を追うことでMVSについて理論的側面から理解を深めてみたい。

MVSというアプローチの特徴は、依存関係解決のためにSAT（SATisfiability、充足可能性）問題を直接解かない点だ。

SAT問題とは、命題変数を含む論理式に対して、その論理式を真にするような命題変数の値への割り当てが存在するかどうかを決定する問題だ。任意の問題（ハノイの塔や数独のような状態空間問題など）をそのまま解かず、SAT問題に変換してSATソルバで解くアプローチが広い分野で採用されており、現代ではパッケージ管理においてSATソルバが使われることがままある。 postd.cc

だがMVSはSAT問題としてバージョン選択問題を解かない。じゃあどうしてるのか。結論から言うと、MVSはSATと正面からぶつからず、問題を変換した上で3つのアルゴリズム（2-SAT, Horn-SAT, Dual-Horn-SAT）を利用して解く。

SATはNP完全問題に属しており、上述したいくつかのパッケージ管理システムはNP完全と向き合っている。しかし実運用における効率的観点から、バージョン選択問題解決にあたってNP完全は避けたい。ところで、Schaefer's dichotomy theoremによって、ある条件を満たすSATはPに属し、効率的な解を持つSATの部分問題としての制限SATは6種類存在することが証明されている。そして、MVSは2-SAT, Horn-SAT, Dual-Horn-SATの中間に位置することが判明したそうだ。計算の複雑度という観点からみれば、NP完全 > Pであるため嬉しい話である。

論理式ψを構成する変数xとその否定\overline{x}はリテラルと呼ばれ、リテラルの論理和のみで構成される部分は節と呼ばれる。 MVSにおいて、ビルドに対応する論理式は一連の節の論理積である。それぞれの節は、単一の正のリテラル、単一の負のリテラル、一つの負と一つの正のリテラルの論理和のいずれかとなる。

この論理式は、各節が最大2つの変数を持つため、2-CNF式(節の長さが高々2の乗法標準形で表された論理式)である。また、各節は最大1つの正のリテラルを持つから、この式はHorn式でもある。また、各節は最大1つの負リテラルを持つので、この式はDual-Horn式でもある。

つまり、MVSで提起されるすべての充足可能性問題は、3つのアルゴリズムから選択することで解けるそうだ。なるほど……？

おわりに

MVSはビルドにおいて開発者が指定したバージョンを正確に使用し、バージョンアップグレードは自動化せず完全にユーザーに委任している。このアプローチは、ロックファイルを管理せず常に開発時における依存パッケージのバージョンを忠実に再現可能なビルドにつながる。個人的には実運用を意識したアプローチだと感じる。

MVSの理論における記述には筆者による誤解、数学的に不適切な表現が含まれる可能性が多分にあることを留意されたい（すみません……）。下記の参考文献を参照いただければ幸いである。一応アルゴリズムを専門とした研究室で学んで修士出てるのに、SATと言われてもSuchmosしか思い浮かばない体たらくを反省した。今年こそ、まずは「アルゴリズムとデータ構造」を読み通すぞ。

参考

大企業は無償利用せず金銭的支援を行えと警告したのに改めないので作者がついに激怒、毎週2000万回以上ダウンロードされるcolors.jsとfaker.jsを破壊し使用不能に - GIGAZINE

Go Modules Reference - The Go Programming Language

research!rsc: Go += Package Versioning (Go & Versioning, Part 1)

充足可能性問題のいろいろ

初心者が学ぶP,NP,NP困難(Hard),NP完全(Complete)とは（わかりやすく解説） - MotoJapan's Tech-Memo

B2Bサービス不具合問合せ対応の質を上げる

はじめに

顧客影響を伴う事象が本番環境において発生した場合、エンジニアは下記のような計画外の火消し業務に追われる。

  • インフラ系
    • SLO違反などを原因としたPager発報などに端を発するインフラ周りの復旧改善対応。
  • サービス系
    • サービスのユーザー、あるいは社内（開発チーム、QAチーム、CSチーム、etc）によるサービス不具合報告に端を発する復旧改善対応。

本稿では、B2Bサービス不具合発生時における問合せ対応に焦点を絞り、その質上げを目的とした取り組みや考え方について説明する。分量が大きくなりそうなので、準備編（本稿）と対応編（予定）に分割記載する。

事前に備える

不具合問合せは当然計画外対応となり、顧客影響の程度によっては対応緊急度が高く、割り当てられる（人的、時間的）リソースもタイトになる。ゆえに、問合せ発生時に効率的に動くための事前準備が対応の質に直結する。

問合せ対応時の役割

問合せにおいて、エンジニアは技術的立場から問題解決に取り組むことになる。チームが機能的に動くため、役割に応じた動き方を意識すると良い。

指揮者

指揮者の責務は問題の着地点を定め、合意形成し、実際に着地させることだ。指揮者には以下の能力が求められる。

  • 不具合特定のために技術観点から仮説を立てられる技術力
  • プロダクトの仕様やドメイン知識、直近の本番環境に対する変更などの知見
  • 目先の状況だけでなく数手先までを見通し、複数の着地点を想定して対応を前進させるディレクション力
  • 作業者（後述）およびビジネスサイドに事実をヒアリングし、不具合についての仮説やアプローチ、着地に向かうための方針や計画を説明できる力

チームリーダーやテックリードを担うシニアエンジニアはこれらを能力を（きっと）有しているはずだ。責任感の高さも加わり、特に人的リソースが不足している場合は彼らが指揮者の役割を率先して引き受けることが多いと思う。

しかしこの状態が定常化すると属人化が進行してしまい、特定の人だけに問合せ指揮の知見が蓄積し、チームとしての問合せ対応力が向上しない。特定のエンジニアへの作業集中やトラックナンバー1を避けるため、指揮者はエンジニア間で持ち回るのが望ましい。

指揮者は調整役（交通整理役）ではない。問合せに関する意思決定責任を有し、判断根拠を各方面に説明できなければならない。

作業者

指揮者のディレクションのもとで、作業者は下記のようなタスクを担う。

  • 不具合事象の特定、再現手順の確認
  • 原因調査、コード改修およびレビュー
  • hotfixやrevertを目的とした緊急リリース作業

作業者のアサイン方法は手上げ、指揮者による任命など様々だ。しかし、指揮者は後述する不具合トリアージ結果や顧客の温度感を念頭に置いた上で、誰に何をしてもらうのが良いか、対応中は常に考え続ける必要がある。問題の切り分けが進むことで、調査や改修作業のバトンタッチもありうる。

手を動かす以外にも、作業者は自身の作業目的や内容を明らかにした上で進捗や結果を共有する責務がある。「画面からのリクエスト失敗してないか確認するためServerのログ見ます」「じゃあ自分は検証環境で再現ためしてみます」程度の共有で十分である。後から対応経緯が追えるように、誰（WHO）が何（WHAT）をどう（HOW）したかテキストベース（Slackのスレッドなど）でも共有することをおすすめする。

書記

書記は問い合わせに関する情報を書き出す役割である。指揮者がディレクションしながら兼務しても良いし、作業者が交代しながら担っても良い（勿論専任者を立てても良い。人的リソースに余裕があればの話だが）。

口頭（対面やZoomなど）で行われた共有や仮説検討、各作業者の作業状況、ネクストアクションについての情報などはテキストベースで随時共有し、後から参加した作業者やビジネスサイドに対して対応状況が可視化するよう努めるべきである。後日、振り返りがしやすくなるメリットもある。

ただし、問合せ対応時はトライアンドエラーによる手戻りや、発散段階の仮説などふわっとした情報が錯綜するため、書くべき情報の見極めや整理する能力、またレスポンスの速さがある程度求められる。

不具合トリアージの基準を定めておく

不具合の大きさに対応する基準を事前設定し、実際の対応時にある程度機械的に意思決定根拠を示せる準備をする。 （無論、マージナルな不具合は存在するし、ビジネスインパクトによって最終的な対応緊急度は上下する。あくまで判断根拠の軸であり絶対的原則ではない）。

一例として、下記のように基準が設けられる（表記例なのでMECEな書き方はしていない）。

  • High
    • 性質：セキュリティリスクやユーザー権限機能に関わる不具合
    • 影響範囲：全顧客
  • Middle
    • 性質：基幹機能が利用できない不具合
    • 影響範囲：全顧客
  • Low
    • 性質：ユーザーが運用回避できる不具合
    • 影響範囲：一部の顧客

基準設定の根拠には不具合の性質や影響範囲など、ビジネスインパクトに結びつく要素をビジネスサイドと目線合わせした上で列挙すべきである。また、本基準はエンジニアだけでなく、ビジネスサイドやボードメンバーなど、不具合発生時にエンジニア側から説明を行う相手と事前共有しておかなければならない。

問合せ対応時の情報共有場所を定めておく

リモートメンバーとオフィスメンバーが混在する状況で情報を分散させないためには、有事の際の情報共有ルールをある程度定めておく必要がある。

たとえば、問合せ対応時にグループ通話する場合は常にSlackハドルのXX部屋に集まる、などである。平時から社内で複数の類似ツールを利用している場合、有事は社内利用率が最も高く、かつ同時接続数が多くても部屋が安定しているツールの利用をおすすめする。

普段からリリース内容やインフラの変更を把握しておく

本番環境に加えられる変更について敏感であるべきだ。 リリース共有会やデイリースクラム、Slackでのパブリックな共有を通じて各種変更をキャッチアップしておくことで、不具合が直近の本番変更による影響下にあるかどうか見当をつける材料にできる。revertによる切り戻しか、改修をhotfixする前進対策かの意思決定を早めるためにも重要である。

おわりに

半分は不出来な自分に噛んで含めるように、マニフェストのつもりで書いた。

「弊社はこんな施策をしてるよ」「うちはXXな理由でそうしてないよ」などフィードバックお待ちしております。Twitterとかで教えて下さい:bow:

”UNPHAT”と問題を構造的把握する大切さについて

はじめに

ソフトウェアエンジニアであるOz Novaさんは2017年、自身のblogに”You Are Not Google”というタイトルの記事を投稿した。 彼はこの記事でエンジニアリングにおける「カーゴ・カルト」、つまりGAFAMに代表される成功したBig Techが採用しているような”イケてる”技術を使うことで自分たちも大きな成功を掴めるはずだ、という迷妄に対し警句を述べているのである。

本稿ではNovaさんが上掲の記事中で示した問題解決の指針”UNPHAT”を見ていくとともに、UNPHATの核心にあたると著者が考える、問題を構造的把握する大切さについて記す。

What is UNPHAT?

UNPHATとは、以下の6項目からなるチェックリストだ。

  1. Don’t even start considering solutions until you Understand the problem. Your goal should be to “solve” the problem mostly within the problem domain, not the solution domain.
  2. eNumerate multiple candidate solutions. Don’t just start prodding at your favorite!
  3. Consider a candidate solution, then read the Paper if there is one.
  4. Determine the Historical context in which the candidate solution was designed or developed.
  5. Weigh Advantages against disadvantages. Determine what was de-prioritized to achieve what was prioritized.
  6. Think! Soberly and humbly ponder how well this solution fits your problem. What fact would need to be different for you to change your mind? For instance, how much smaller would the data need to be before you’d elect not to use Hadoop?

引用元：https://blog.bradfieldcs.com/you-are-not-google-84912cf44afb

筆者なりに和訳してみよう。

  1. 問題を理解するまでは解決策の検討を始めない。私たちのゴールとはたいていの場合、問題の範囲内で問題を「解決」することであって、それは解決策の範囲内においてではない。
  2. 候補となる解決策をいくつか挙げよう。気に入った解決策だけを追ってはいけない。
  3. 解決策を検討するにあたり、文献があれば読もう。
  4. 解決策が設計、開発された歴史的背景を知ろう。
  5. 解決策の長所と短所を比較しよう。優先されたことと引き換えに、何が優先されなかったかを知ろう。
  6. 考えよう！　私たちの抱える問題に対し、解決策がどれだけ適しているか冷静に深慮を巡らそう。考えを変えるためにはどんな事実が必要だろうか？　たとえば、Hadoopを使わないためには、データをどれだけ小さくすれば良いだろう？

これらのチェックリストは、端的に言えば「”私たちの問題”を深く理解した上で、最良の解決策を見つけるために数多の技術を冷静に評価せよ」というステートメントである。そして、これ自体は斬新なメッセージではない。

にもかかわらず、NovaさんがUNPHATを提唱するのは、我々がこのステートメントを実行できず、アーキテクチャ検討や実装の途上において容易に思考停止してしまうからだ。

問題を構造化しよう

業務上直面する問題には、解決が容易な問題と難問とが混濁している。そして、難問とは得てして「なんもわからん」状態で現前する。この状態の問題を理解するには、問題を構造的に把握しなければならない。この時点必要なのは解決策ではない。事実の収集と、有り合わせの事実から得られる”その時点で最良の”仮説だ。

例を挙げよう。Novaさんの記事では、直面する問題と深く向き合わずにtoo muchな解決策を選んでしまったケースとして、分散データストリーミング基盤であるApache Kafkaを中心にシステム構築したとある企業（仮にA社と呼ぶ）が引き合いに出されている。Kafkaは元々LinkedInが多様な種類の大規模データをスケーラブルかつ高スループットで処理するために開発した技術基盤だ。しかしA社のビジネスにとって、システムは1日に数十件、多くて数百件のトランザクションを処理するだけで十分だった。はたしてA社の技術選定は正しかったのだろうか。

A社は「ビジネスが要請するデータ処理を実現したい」という問題に対し、可能な限り事実を集めた上で仮説を立て、仮説を満たす解決策を選定できなかったのだろう。A社はLinkedInではないため、「ビジネスが要請するデータ処理を実現したい」という問題の実質も異なる。どう異なるかが「なんもわからん」場合、そのままでは五里霧中で先へ進めない。この状況はUNPHATのUに該当する。先へ進むため、また進んだ先が正しいかどうかを評価するためには、軸となる仮説を事実から導く必要がある。

問題と十分に向き合わず、判断軸（仮説）を立てないまま、目についた”イケてそう”な解決策に飛びついてはいけない。仮説がなければ、UNPHATのTに該当する、問題と解決策との比較検討作業が十分に行えないはずだ。

終わりに

Novaさんは記事を締めるにあたって、"How to Solve It"の著者、George Pólyaの言葉を引いている。

「It is foolish to answer a question that you do not understand. It is sad to work for an end that you do not desire.（理解していない問題に答えるのは愚かなことだ。望まない結末のために働くのは悲しいことだ。）」

問題を理解可能にしよう。そのために構造化する努力を惜しんではならない。つねに、仮説という”望まれた結末”を描いて働きたいものである。

参考