stop-the-world

takuya-a のブログ

Goで構造体の非公開フィールドにアクセスする方法

Go の 構造体 (struct) におけるフィールドは、フィールド名が小文字始まりであれば 非公開フィールド (unexported field) となり、パッケージ外からアクセスすることができません(参考: Exported identifiers - The Go Programming Language Specification)。 組織内で管理しているソースコードなら単に修正してしまえばよいのですが、外部のライブラリなどの場合、変更してもらうのは大変です。

このような、やむを得ない理由で非公開フィールドを参照したい場合、ちょっとした工夫が必要になります。 試してみたところ、以下の2つの方法で非公開フィールドを取り出すことができました。

  1. reflect.ValueOfunsafe.Pointer を使う方法
  2. go.mod でモジュールを replace する方法

1. reflect.ValueOfunsafe.Pointer を使う方法

以下のようにして reflect.ValueOfunsafe.Pointer を併用することで、非公開フィールドにアクセスすることができます。

このソースコードは、外部パッケージ outside の構造体 OuterStruct に定義された privateStruct などの非公開フィールドを取り出したい、という設定です。

同じく OuterStruct に定義された、 int 型の privateInt や、 string 型の privateString などの非公開フィールドの読み取り・書き込みもできました。

package main

import (
    "fmt"
    "reflect"
    "unsafe"

    "github.com/takuyaa/go-private-test/outside"
)

func main() {
    var outer *outside.OuterStruct = outside.NewOuterStruct()

    // var v reflect.Value = reflect.ValueOf(*outer) としてもよいが、コピーが走ってしまうため、もとの outer は変更できないし、効率も悪い
    var v reflect.Value = reflect.ValueOf(outer).Elem()
    fmt.Printf("v: %#v\n", v) // v: outside.OuterStruct{privateInt:10, privateString:"dog", privateStruct:(*outside.InnerStruct)(0xc0000b4030)}

    // privateStruct を取得
    var psv reflect.Value = v.FieldByName("privateStruct").Elem()
    fmt.Printf("psv: %#v\n", psv) // psv: outside.InnerStruct{Message:"Hi!"}
    // 直接は中身を取れない
    // is := sv.Interface() // panic: reflect.Value.Interface: cannot return value obtained from unexported field or method
    var is *outside.InnerStruct = (*outside.InnerStruct)(unsafe.Pointer(psv.UnsafeAddr())) // unsafe.Pointer を使うと中身を取れる
    fmt.Printf("is: %#v\n", is)                                                            // is: &outside.InnerStruct{Message:"Hi!"}

    // int 型の private フィールドの取得と変更
    var piv reflect.Value = v.FieldByName("privateInt")
    pi := (*int)(unsafe.Pointer(piv.UnsafeAddr()))
    fmt.Printf("pi: %#v\n", *pi) // pi: 10
    *pi = 111                    // フィールドの値を変更できる
    fmt.Printf("pi: %#v\n", *pi) // pi: 111

    // string 型の private フィールドの取得と変更
    var pstrv reflect.Value = v.FieldByName("privateString")
    ps := (*string)(unsafe.Pointer(pstrv.UnsafeAddr()))
    fmt.Printf("ps: %#v\n", *ps) // ps: "dog"
    *ps = "cat"                  // フィールドの値を変更できる
    fmt.Printf("ps: %#v\n", *ps) // ps: "cat"

    // PublicMethod の呼び出し
    pubm := reflect.ValueOf(outer).MethodByName("PublicMethod") // Elem() 経由ではなくポインタからアクセス
    fmt.Printf("pubm: %#v\n", pubm)                             // pubm: (func())(0x1082580)
    pubm.Call(nil)                                              // Hi!

    // privateMethod の呼び出しは失敗する
    prim := reflect.ValueOf(outer).MethodByName("privateMethod") // Elem() 経由ではなくポインタからアクセス
    fmt.Printf("prim: %#v\n", prim)                              // prim: <invalid reflect.Value>
    // prim.Call(nil)                                            // panic: reflect: call of reflect.Value.Call on zero Value
}
-- go.mod --
module github.com/takuyaa/go-private-test

go 1.13
-- outside/lib.go --
package outside

type InnerStruct struct {
    Message string
}

type OuterStruct struct {
    privateInt    int
    privateString string
    privateStruct *InnerStruct
}

func NewOuterStruct() *OuterStruct {
    return &OuterStruct{
        privateInt:    10,
        privateString: "dog",
        privateStruct: &InnerStruct{Message: "Hi!"},
    }
}

func (s *OuterStruct) privateMethod() {
    println(s.privateStruct.Message)
}

func (s *OuterStruct) PublicMethod() {
    println(s.privateStruct.Message)
}

上記のソースコードThe Go Playground にコピペするか、以下の URL でも試せます*1:

https://play.golang.org/p/iomnJeRjOns

Pros

  • 既存のコードには手を入れずに、最小限の追加実装で非公開フィールドにアクセス可能
    • 2, 3 行のコードで非公開フィールドへのポインタが取得できる

Cons

  • reflectunsafe を使うので、プロダクションのコードでは採用しづらい
    • パフォーマンス上の問題も起きうる
    • あくまでテストやデバッグで使うのに留めるのが無難そう
  • この方法では非公開メソッドへのアクセスはできない(後述)

非公開メソッドの呼び出しは難しい

上で見たように、非公開メソッドは MethodByNamereflect.Value を取得しても、 invalid reflect.Value となり、それを通して関数呼び出しをすることはできませんでした。

spance/go-callprivate もダメ元で試してみましたが、残念ながらうまくいきませんでした。((プライベートメソッドの場合、 reflect.Value を取得してもそれが invalid なので、 private.SetAccessible(method) が失敗します。))

alangpierce/go-forceexporttime.now のような、レシーバではない関数を呼び出すためのもののようで、用途が異なるようです(参考: how to call a unexported Func in a struct? · Issue #1 · alangpierce/go-forceexport)。

2. go.mod でモジュールを replace する方法

2 つ目の方法は、 Go Modulesreplace の機能を使う方法です*2

  1. 対象となる外部モジュールのソースコードを取得し、利用側のリポジトリに置く
    • 以下では、 github.com/outside/module というモジュールをプロジェクトルートの ./outside/module/ に置いたとして説明します
  2. そのモジュールに go.mod がなければ go mod init で作成しておく
  3. 利用側の go.mod に、以下のような replace ディレクティブを追記する
    • replace github.com/outside/module => ./outside/module
  4. 手元のモジュールを修正し、非公開フィールドを返す外部メソッドを生やすなり自由に改造する*3

この方法なら、非公開メソッドの呼び出しも可能になります。

たとえば、 func (s *OuterStruct) privateMethod という非公開メソッドがあったとき、それを呼び出すだけの公開メソッド func (s *OuterStruct) CallPrivateMethod を定義し、利用側からはそれを呼ぶようにすれば、最小限の変更で非公開メソッドを呼ぶことができます。

Pros

  • 非公開メソッドも呼べるなど、自由度が高い
    • panic やプリントデバッグなどの命令を仕込んだりもできる

Cons

  • リポジトリに外部のソースコードをそのまま持ってきて改変するため、バージョンアップが大変になったり、元のソースからの diff が管理しづらい
    • ライセンスにも注意が必要

参考

*1:この URL ではそのうちアクセスできなくなると思います

*2:この方法は @ikawaha さんに教えていただきました。ありがとうございました!

*3:ライセンスに注意!

Rust の開発環境セットアップ

Linux (Ubuntu 19.10) に Rust の開発環境を作ったメモです。IDE として VSCode を使います。

Rust の開発環境

  • Rust ツールチェイン
    • rustc
    • cargo
      • ビルドマネージャ兼パッケージマネージャ
    • std
      • Rust の標準ライブラリ群
  • リンカ
    • コンパイル済みのオブジェクトファイルやライブラリをリンクして実行可能バイナリにするツール
    • OS ごとに標準的に用意されているもの (ld など) を使う
  • rustup
    • Rust ツールチェインや関連ツールのインストール・管理ツール
    • 複数のバージョン (stable, beta, nightly) のツールチェインを管理できる
      • rbenv, pyenv のようなイメージ
    • ロスコンパイル用のターゲットをインストールできる

開発環境のセットアップ

Rust ツールチェインと VSCode のセットアップを行う。

Rust ツールチェインのインストール

$ curl --proto '=https' --tlsv1.2 -sSf https://sh.rustup.rs | sh
info: downloading installer

Welcome to Rust!

This will download and install the official compiler for the Rust
programming language, and its package manager, Cargo.

It will add the cargo, rustc, rustup and other commands to
Cargo's bin directory, located at:

  /home/takuya-a/.cargo/bin

This can be modified with the CARGO_HOME environment variable.

Rustup metadata and toolchains will be installed into the Rustup
home directory, located at:

  /home/takuya-a/.rustup

This can be modified with the RUSTUP_HOME environment variable.

This path will then be added to your PATH environment variable by
modifying the profile files located at:

  /home/takuya-a/.profile
/home/takuya-a/.bash_profile

You can uninstall at any time with rustup self uninstall and
these changes will be reverted.

Current installation options:


   default host triple: x86_64-unknown-linux-gnu
     default toolchain: stable
               profile: default
  modify PATH variable: yes

1) Proceed with installation (default)
2) Customize installation
3) Cancel installation
>

1 を入力してインストール。

  • ~/.cargo/bin/cargo , rustc , rustup などがインストールされる
    • CARGO_HOME で変更できる
  • /.rustup/rustupメタデータとツールチェインがインストールされる
    • RUSTUP_HOME で変更できる

また、 ~/.profile~/.bash_profile に以下が追記される:

export PATH="$HOME/.cargo/bin:$PATH"

パスの設定をシェルに反映すると、 rustc , cargo , rustup などがそのまま使えるようになる。

$ . ~/.cargo/env

VSCode のセットアップ

  • Rust (rls) 拡張 のインストール
    • RLS (Rust Language Server) と通信して補完などを支援してくれる拡張
    • 拡張をインストールしたあと、 RLS をインストールするかどうかをポップアップで聞かれるのでインストールする
  • CodeLLDB 拡張 のインストール
    • デバッガ LLDB を VSCode から使うための拡張
    • VSCode 上で、ブレイクポイントの設定やステップ実行が可能

プロジェクトの作成・ビルド・実行

以下で ~/workspace/hello/ 以下に bin クレート(バイナリパッケージ向けのプロジェクト)が作成される:

$ cd ~/workspace
$ cargo new --bin hello
     Created binary (application) `hello` package

cargo build でパッケージをビルドできる:

$ cd hello
$ cargo build
   Compiling hello v0.1.0 (/home/takuya-a/workspace/hello)
    Finished dev [unoptimized + debuginfo] target(s) in 0.23s

ビルドした実行可能バイナリは target/debug/ 以下に置かれる:

$ ls target/debug/
build  deps  examples  hello  hello.d  incremental
$ target/debug/hello
Hello, world!

参考

実践Rust入門[言語仕様から開発手法まで]

実践Rust入門[言語仕様から開発手法まで]

情報検索とその周辺

これは、情報検索・検索エンジン Advent Calendar 2019 の 1 日目の記事です。

情報検索・検索エンジン Advent Calendar を作った経緯

という流れで @johtani さんから「つくってよ!」と言われて作ったのが、このアドベントカレンダーです。

そういうわけなので、このアドベントカレンダーには、これといったルールや、こういうテーマで書いてほしい、といった要望はありません。そもそも情報検索は非常に学際的な分野ですし。

ただ、なにかしらのガイドラインなりテーマの例はあったほうが参加しやすいだろうと考え、説明文は以下のようにしました。

検索 (IR) に関わることならなんでも OK!

情報検索・検索エンジンという名前のアドベントカレンダーですが、「検索に関わること」として、情報推薦や自然言語処理、地理検索、さらには画像検索まで含めています。

その意図を説明するためにも、情報検索を取り巻く現状について、ざっとまとめてみました。いちソフトウェアエンジニアの自分から見たものですので、偏りや見識不足があることをご容赦ください。

情報検索の概要と近年の動向

情報検索の原語は Information retrieval です(しばしば IR と略されます)。そのまま解釈すると、情報の取得・取り出し、情報を取ってくること、といった意味合いです。

古典的な情報検索のモデルでは、

  • ユーザはなんらかの情報ニーズ (information need) をもつ
  • 検索システムはあらかじめ静的に構築された文書集合を内部にもつ

という条件のもと、

  1. ユーザは、情報ニーズに従い、検索システムに対してクエリ (query) を入力する
  2. 検索システムは、内部に保持する文書集合から、ユーザの情報ニーズに適合すると思われる文書集合を計算し、 UI 上に検索結果ページ (SERP; search engine result page) として表示する

というユーザと検索システムとのインタラクションを対象にします*1。 たとえば、図書館の蔵書検索システムで、ある特定の書籍を検索する、といったシチュエーションです。

古典的な情報検索モデルでは、静的な文書集合のなかから、ユーザがもともと持っている固定的な「情報ニーズ」にマッチする文書を探すことに焦点が当てられていました。 しかし近年では、情報システムの高度化・複雑化に伴い、既存の情報検索モデルには当てはまらないアプリケーションが増えてきました。

みなさんが Google などの Web 検索エンジンで検索しているときのことを想像してみてください。 検索結果のリストを見たり、その中の Web ページにアクセスしたりする中で、なんらかの知識を得て、そのトピックをさらに深堀りしてみたり、関連する別のことを探してみたりする経験があると思います。 クエリを入力している最中にもクエリ補完の候補が表示したり、検索結果ページに別のクエリ候補を提示したりして、ユーザをサポートしてくれます。

また、多くのアプリケーションにおいて、検索システムに保存されている文書集合は静的ではなく、動的に増え続けるものになっています。 Web の登場などの背景から、世界全体の情報量は爆発的に増加しており、増え続ける大規模な文書集合から、適合する文書を効率的に検索する必要性が出てきました。

さらに、アプリケーションによって検索対象の種類も多様になり、テキスト情報だけではなく、いまや画像や音楽、動画までが検索の対象になりました。

情報検索分野の大家である Zobel は、近年の情報検索を取り巻く状況を鑑み、 "What We Talk About When We Talk About Information Retrieval" の中で、以下のように述べています。

Information retrieval is the study of techniques for supporting human cognition with documents, using material that is sourced from large document collections. (情報検索は、大規模な文書集合からなる材料を用いて、文書による人間の認識をサポートするための手法の研究である)

情報検索の関連分野・関連技術

以上のように、情報検索は高度化・複雑化する実アプリケーションにも追従しつつ、進化・発展してきました。

情報検索は非常に学際的な分野であり、とくに情報推薦や自然言語処理機械学習ユーザインタフェース、といった分野とは深い関係があります。 また、産業界 (industry) への応用という意味では、検索システム全体としての評価や運用も重要になってきます。

情報推薦(レコメンド)

ACM SIGIR は言わずとしれた情報検索のトップカンファレンスですが、今年の SIGIR推薦に関する論文が多く採択されていたことからも、情報推薦・レコメンドシステムが情報検索の分野からも重要な関心事になっていることがわかります。

推薦システム (recommender system) は、ユーザにとって価値があるものを特定するのを助けるためのシステムです。 具体的には、ユーザの行動や属性情報などから、様々なアイテム(本、音楽、動画、記事など)から、ユーザの好みそうなものをランク付けして提示するようなシステムです。

ユーザが積極的に検索要求・クエリをシステムに入力するか(情報検索)、システム側からユーザが好みそうなものを提示するか(情報推薦)、といった違いはありますが、ユーザの認識をサポートする、という意味では非常に近いモチベーションをもった分野だと思います。 実際、レコメンドシステムで要素技術として検索エンジンを使う例もありますし、その境界は年々曖昧になっているように感じます。

自然言語処理機械学習

自然言語処理機械学習も広大な分野ですが、以下に情報検索に関連するトピックを挙げておきます。

  • 文書とクエリの言語処理
    • 分かち書きトークナイズ) (tokenize)ストップワード (stop word) 除去、見出し語化 (lemmatization)語幹化 (stemming)類義語 (synonym) 展開など。索引付け(インデキシング)やクエリ処理で使う
  • 文書要約 (text summarization)
    • 検索結果 (SERP) に表示する文書のサマリに文書要約したテキストを使用するなど
  • 情報抽出 (information extraction)
    • 文書のなかに含まれる固有表現などを予め抽出し、クエリ時にそれらの属性でフィルタするなどの応用がある
  • 言語横断情報検索 (CLIR; cross lingual information retrieval)
    • クエリとは別の言語で検索してもヒットさせたい場面で使われる。機械翻訳が使われることも
  • ランク学習 (LTR; learning to rank)
    • ユーザの行動ログなどから、文書のランキングを最適化する。近年、ニューラル検索 (nerural information retrieval) が急速に発展している

画像検索・地理検索

スマートフォンの普及などの背景から、写真や動画をオンラインサービスに簡単に上げられるようになり、画像などを含むマルチモーダル検索 (multimodal information retrieval) の重要性も増してきています。 地理情報を考慮した検索も同様の理由ですっかり一般的になりました。

それ以外にも、検索システムとして見た場合、キーワード以外にも何らかの属性(文書の更新日時など)によってフィルタしたり、ソートしたりすることは非常に一般的です。

検索のためのアルゴリズム・データ構造

情報検索はこれまで、全文検索 (fulltext search) を中心に発展してきました。

全文検索エンジンの実装方式にはいくつかありますが、現状、最も利用されている検索エンジン転置インデックス (inverted index) 型のものでしょう(文字列検索アルゴリズムについては以前、文字列アルゴリズムの学び方という記事を書きました)。 このタイプの検索エンジンは非常に古典的でありながら、クエリ処理の手法などはいまだに発展しており、さらに効率的になっています。

一方で、数値をインデックスするためには B+-tree や LSM-tree が、多次元の数値(地理情報や IP アドレスなどのベクトルデータ)をインデックスするためには kd-tree などのデータ構造が利用されます。実際、 Apache Lucene では、 kd-tree の発展型である Bkd-tree による範囲検索を実装しています。地理検索では、これらのインデックスが役立ちます。

さらに、画像検索や、ニューラル検索などのベクトル表現を使った検索システムでは、さらに高次元のベクトルを検索する必要があり、上記のようなインデックスではパフォーマンス要件などを満たせないことがあります。この場合、近似近傍探索 (ANN; approximate nearest neighbor) と呼ばれる方法で、近似的な解を返すことで、高速にベクトルを検索することを可能にします(参考: Billion-scale similarity search with GPUs - Speaker Deck)。 画像検索では ANN を使った検索が一般的になってきています。

検索エンジンライブラリ・検索ミドルウェア

実応用で検索システムをつくるときには、現状、ElasticsearchApache Solr をベースに考えるケースが多いようです。

インデックスを保存するストレージとして安定しており、レプリケーションやスナップショット(バックアップ)といったミドルウェアとしての機能が一通り揃っています。 分散検索にも対応しており、大規模な文書集合にも対応できます。

テキストだけでなく数値や日時、ベクトルなど、さまざまなデータタイプに対してインデックスを張れ、それらを横断した柔軟なクエリを書けるため、非常に応用範囲が広いため、システム要件の変化に対しても柔軟です。

また、REST API を提供しており、メジャーな言語ではクライアントライブラリが提供されていて開発しやすいのも人気の理由でしょう。

検索システムの設計・構築・運用・評価

検索は、研究だけでなく、実務においても、まだ答えが出ていない問題がたくさん残っています。

日本語の検索においては、トークナイズ(分かち書き)が必要ですが、そのアプリケーションにとって最適なトークナイズとはなにか?というのは実は難しい問題です。

さらに、構築した検索システムの精度評価も非常に重要な問題です。 対象となるコーパス、アプリケーションによって適切な評価方法を選ばなければなりません。

また、高いパフォーマンスを発揮させつつ、安定して運用していくためには、設計段階からインフラの知識が要求されます。 最近はクラウド技術が急速に発達しており、それらを使いこなすことでシステムの運用負荷を下げていくのも重要な課題になってきています。

  • 検索システム全体のアーキテクチャ設計
  • 検索システムの運用
  • 検索精度のチューニング
    • 類義語(シノニム)辞書の構築・運用、トークナイザの選定・チューニング
  • 精度評価・精度を上げるための方法論・システム
    • オフライン評価方法、オンライン評価方法(A/B テストなど)

UI/UX

検索システム全体としての良し悪しを評価する際には、UI/UX の観点は欠かせません。 ユーザからみたとき、検索エンジンに直接クエリを叩くことはなく、必ずフロントエンドを通して検索システムを利用します。

すなわち、ユーザはフロントエンドで検索クエリを入力し、フロントエンドから検索結果を得ることになります。 この基本は音声検索であっても画像検索であっても変わりません。

おわりに

以上のように、ひとくちに検索といっても、様々な分野や技術が相互に絡んでいて、状況は単純ではないことがおわかりいただけたかと思います。 検索システムをつくる上でも、以上のようなトピックがあるということだけでも知っておくと、役に立つことがあるのではないでしょうか。

情報検索という分野は、ある意味で古典的と思われがちかもしれませんが、このように、検索は様々な分野と密接に関係しながら、学術界・産業界の両方面からともに、いまなお発展しています。

ここでは紹介しきれなかったトピックもまだまだたくさんあると思います。 すでにたくさんの多様なエントリーをこのアドベントカレンダーに登録していただいており、とても楽しみです。

情報検索・検索エンジン Advent Calendar 2019、明日は rejasupotaro さんです。よろしくお願いします!

参考文献

*1:検索結果が情報ニーズに適合しないような場合、ユーザは(ときには情報ニーズを変化させながら)クエリ修正 (query reformulation) し、検索行動を繰り返すことがあります。一般には、このような、ユーザと検索システムとの一連のインタラクションの系列(これを検索セッション (search session) と呼びます)を考慮するモデルもあります

論文メモ: Fast Approximate Filtering of Search Results Sorted by Attribute (SIGIR 2019)

前回に引き続き、 SIGIR 2019 の efficiency に関する論文を読んだメモです。

前回: stop-the-world.hatenablog.com

以下はチーム内でこの論文を紹介するときに使う予定のスライドです。あわせてご覧ください。 speakerdeck.com

1. Introduction

  • 通常、ユーザが検索で欲しいのは relevance を最大化した SERP
    • Web 検索、SNS、ストリーミングサービス、ECサイトなど
  • 多くのサービスでは、クエリに関連しつつも属性(時間やアイテムの価格など)でソートした検索に対応している
  • しかし、ソート順を指定すると、あまり関連のない結果が検索結果にたくさん現れ、ユーザ体験を損なう
    • たとえば amazon.com で "iphone" というクエリで検索すると、10万件以上の結果が得られる
    • 関連度順だと、いくつかの iPhone のモデルと関連するアクセサリが表示される
    • 価格の安い順にしたとき、最初のページには安い価格のカバーやガジェットが表示される
    • こうなると、ユーザは関連のあるアイテムを見つけるまでに、いくつかのアイテムを見て精査する必要があり、ユーザ体験がよくない
  • このような問題は Filtering task として扱うことができる
  • ソート順を崩さずに、元のリストから全体的な effectiveness を最大化する最大 k 件の結果を得るのがゴール
  • Filtering@k
    • relevance のリスト $R = [r_1, ..., r_n]$ (順序つき)が与えられる
    • メトリック $Q$ を最大化する、最大 $k$ 件の部分リストを返す
  • DCG のようなメトリクスを考慮した Filtering@k の解を見つけるのは難しい
  • 実際、最適な解を得るには、リストの最も関連性の高い結果を選択するだけでは不十分
    • かつ、k 件のサブシーケンスのみを考えるだけでもいけない
  • たとえば、$R = [2, 2, 4, 1]$ のとき、最適な DCG@3 は最初の2つの要素をフィルタすることで得られる($[4, 1]$ が最適な結果)
  • Filtering@k の先行研究: Spirin et al. [14]
  • この論文では $\epsilon$-Filtering という手法を提案
    • $\epsilon$ というパラメータで近似誤差をコントロールし、効率と効果をトレードする
    • $(1-\epsilon)$-optimal filtering
    • 時間計算量は $\Theta (n + k^{2} \log_{(1 - \epsilon)}{(\epsilon / k)})$
  • $\epsilon$-Filtering を2つの公開データセットで実験し、速度が向上することを確かめた

2. Related Work

Optimal filtering

  • 時間計算量 $\Theta (nk)$ で最適な結果(近似なし)を計算できる
    • 動的計画法(メモ化)を使って計算
    • $n$, $k$ が大きくなると遅い

Heuristics

  • Cutoff-OPT
    • あらかじめ決めた relevance の閾値でフィルタしてから OPT でさらにフィルタ
    • 最悪ケースではエラー率(精度)の保証がない
      • 閾値の設定によるため
    • 時間計算量は改善せず最悪ケースで $\Theta (nk)$
  • Top$k$-OPT
    • top-$k$ のリストを求め、それをさらに OPT でフィルタする
      • $k$ 個未満のリストにすることでメトリックを最大化できることもあるため
    • 0.5-optimal(近似によるエラー率が 50%)であることが証明できる
    • 時間計算量は最悪で $\Theta (n \log{k} + k^{2})$

3. Approximate Filtering

3.1 Analysis of heuristics

  • Cutoff-OPT と Top$k$-OPT の効果 (effectiveness) を解析した
    • Cutoff-OPT は OPT よりも悪い
    • Top$k$-OPT は 0.5-optimal

Cutoff-OPT

  • パフォーマンスの理論保証はまったくない
  • 閾値の設定によるため
  • 以下のような最悪ケースがある
    • まったくフィルタできないパターン
      • このとき、OPT の時間計算量を改善できない
    • すべてをフィルタしてしまうパターン
      • このとき、$\Theta(nk)$ の時間がかかり、解も当然悪い

Top$k$-OPT

  • 最悪時間計算量は $\Theta(n \log{k} + k^{2})$
    • $\Theta(n \log{k})$ で top-$k$ の要素を選択
    • そのあとそれらの要素に OPT でフィルタするのに $\Theta(k^{2})$ かかる
  • Theorem 1.
    • Top$k$-OPT は 0.5-optimal

3.2 $\epsilon$-Filtering

  • Cutoff や Topk などのヒューリスティックスではエラー率をコントロールできない
  • $\epsilon$-Filtering はエラー率を $\epsilon$ 以下に保証した近似解を、時間計算量 $\Theta (n + k^{2} \log_{(1 - \epsilon)}{(\epsilon / k)})$ で見つける
    • $0 < \epsilon < 1$
  • $\epsilon$-Filtering は以下の3ステップからなる
    1. Right pruning
    2. Discretization
    3. Thresholding

Right pruning

  • ロスレスなフィルタリング(最適な結果に含まれるものを落とさない)
  • 右側に $k$ 個以上の自分以上の relevance をもつ要素がある場合、その要素を落とす
  • 例:元の relevance のリストが $R = [0.9, 1.0, 1.0, 1.0]$ で $k = 3$ のとき $0.9$ を落とす
    • $0.9$ を含むようなすべての解は最適ではない
    • 実際、 DCG 最大の解は $[1.0, 1.0, 1.0]$
  • right-$k$-maximal elements
    • 右側に自分以上の relevance をもつ要素が $k$ 個未満であるような要素
      • (つまり「落としてはいけない」要素)
    • $[0.9, 1.0, 1.0, 1.0]$ のとき $0.9$ は right-3-maximal でない
      • すべての $1.0$ は right-3-maximal
    • $[1.0, 1.1, 1.2, 0.9]$ のとき $1.0$ は right-3-maximal
      • というか全要素 right-3-maximal
    • 最適な解は right-$k$-maximal elements のみからなる (Lemma 4)
  • Right pruning は right-$k$-maximal elements だけを残すフィルタリング

f:id:takuya-a:20191109191841p:plain
Right pruning のアルゴリズム

  • 補助データ構造として優先度付きキューを使う
    • $\Theta (n \log k)$ で top-$k$ の要素を計算できるデータ構造
  • 後ろから配列を走査する
    • 優先度付きキューで最低の relevance よりその要素の relevance が大きければ結果リストに入れる
  • 最後に結果リストを reverse すれば right-$k$-maximal elements が求まる
  • ただし、Right pruning はフィルタリングの効率について理論的な保証はない
  • 元のリストによっては、まったくフィルタできないことがありえる
  • $[1.2, 1.1, 1.0, 0.9]$ のときすべての要素は right-3-optimal
  • 次のステップの Discretization でこのようなケースを改善する

Discretization

  • Right pruning での最悪ケースにおいて、選択される要素数を減らすのがこのステップの目的
  • $R$ から、以下を満たすような新しいリスト $R_{\epsilon}$ をつくる
    • (要素数は $R$ と同じで)ユニークな要素数が $R$ より少なくなるように
    • $R_{\epsilon}$ に対して最適フィルタリングをかけたとき、少なくとも元の relevance の $(1-\epsilon)$ 倍以上を保証するように
  • これにより、 Right pruning は最適な解をほぼ保ったまま、より効果的に要素をフィルタすることができる
  • このステップでは近似誤差と、得られるユニークな要素数トレードオフを行う
  • $r_{max}$ をリストの最大の relevance、 $r_{min}$ を最小の relevance とする
  • 範囲 $[r_{min}, r_{max}]$ を m 個のインターバルに分割するのが、Discretization ステップの基本的なアイデア
    • 同じインターバル内の要素は、そのインターバルで最小の値に近似する
  • 近似誤差 $\epsilon$ とインターバルの数 m を保証するように $[r_{min}, r_{max}]$ をどう分割するかがトリッキー
    • $g(r) = 2^{r} - 1$ を DCG のゲインとする
    • 分割した部分の最小値と最大値のゲインの比が、少なくとも $(1-\epsilon)$ になるようにインターバルへと分割する
    • このように作ったインターバルを $\epsilon$-intervals と呼ぶ
  • 前に見た、 Right pruning での最悪ケースで、このステップがどのように実行されるかを次の例で見る
  • Example 5.
    • $R = [3.00, 2.99, 2.98, ..., 0.01]$(300個の要素をもつリスト)
    • $\epsilon = 0.5$(望んでいる近似誤差 50%)
    • ゲイン (gain function) $g(r) = 2^{r} - 1$ (DCGを仮定)
    • $R$ の $\epsilon$-intervals は以下のような10個のインターバル
      • $[0.01, 0.019)$
      • $[0.019, 0.039)$
      • ...
      • $[1.45, 2.17)$
      • $[2.17, 3.0)$
    • それぞれのインターバルにおいて、最大のゲインと最小のゲインの比は $(1-\epsilon)$ におさまる
      • たとえば最後のインターバルでは $g(2.17)/g(3) \approx 0.5$
    • $R_{\epsilon}$ は $[2.17, ..., 2.17, 1.45, ..., 1.45, ..., 0.01]$
      • (要素数は変わらず 300個)
  • 以下の Lemma 6 は Lemma 4 を $R_{\epsilon}$ に拡張し、
    • $R_{\epsilon}$ の right-$k$-maximal elements が $R$ の $(1 - \epsilon)$-optimal なフィルタリングを見つけるのに役立つことがわかる
  • Lemma 6.
    • $R_{\epsilon}$ の right-$k$-maximal elements のみからなる $R$ の $(1-\epsilon)$-optimal なフィルタリングが存在する
  • $R$ を $R_{\epsilon}$ に離散化すると、ユニークな要素数が $n$ 個から $m$ 個に減る
  • また、以下の性質は $m$ の上限を与える
  • Property 7.
    • $R$ の $\epsilon$-intervals の数 m は、$m \leq \lceil \log_{(1-\epsilon)} (g(r_{min}) / g(r_{max})) \rceil$ を満たす
  • Discretization と Right pruning を組み合わせることで、フィルタによって選ばれる要素数を最大でも $mk$ にできる
    • m は Property 7 の右辺によって bound される
  • しかし、 m の上限は $R$ の最大の relevance $r_{max}$ と最小の relevance $r_{min}$ の両方に依存している
    • これらの比が大きければ、 m の上限も大きくなってしまう
  • 実際、離散化が効率的でなくなるような、敵対的な $R$ を設計することができる
    • $r_{min}$ を固定し、 m が $n$ と等しくなるように $r_{max}$ を十分に大きくすると可能
  • このとき、$R$ はそれぞれの $\epsilon$-interval につき 1 つだけの要素をもつ、単調減少するリストであり、 $R_{\epsilon}$ は $R$ と一致する
    • Right pruning してもすべての要素($m = n$)が選ばれてしまう

Thresholding

  • このステップでは、与えられた閾値を下回る要素をフィルタする
  • この方法で $r_{min}$ の値を大きくすることができ、結果として $\epsilon$-intervals の数 m を減らすことができる
  • このステップで得られるリストを $R^{-}$ とする
  • 閾値は以下を満たすように選ばれる
    • $R^{-}$ に対する最適フィルタリングの relevance は、もとの $R$ に対してのものの少なくとも $(1-\epsilon)$ 倍になる
    • m の値が常に十分小さくなることが保証される
  • Example 8.
    • $R = [5, 0.1, ..., 0.1]$(要素は10個)
    • 最適フィルタリングはすべての要素を残したときで、DCG はおよそ 31.25
    • すべての 0.1 の要素をフィルタしたとき、 $R^- = [5]$
    • $R^{-}$ の最適フィルタリングは DCG が 31 になる
      • 0.99-approximation
  • Lemma 9.
    • $R$ から、閾値 $t = g^{-1}(\epsilon g(r_{max}/k))$ 以下の要素をフィルタし、残りの要素を $\epsilon$-intervals で離散化したリストを $R_{\epsilon}^{-}$ としたとき、 $R_{\epsilon}^{-}$ の最適フィルタリングは $(1-\epsilon)$-approximationとなる
  • Discretization と Thresholding を組み合わせて、 $R$ のユニークな要素を減らすことができる。実際、閾値 $t$ は $\epsilon$–intervals の数を制限し、right-$k$-maximal elements の計算に関係するユニークな要素数を制限する
  • とくに、Property 7 の $r_{min}$ を Lemma 9 のなかの閾値 $t$ で置き換えると、すぐに以下の性質を得る
  • Property 10.
    • $R_{\epsilon}^{-}$ の $\epsilon$-intervals の数 m は、 $m \leq \lceil \log_{(1-\epsilon)} (\epsilon / k) \rceil$ を満たす
  • $R_{\epsilon}^{-}$ の $\epsilon$-intervals の最大の数を bound するというこの性質は、$R$ やその要素からは独立である
  • 各 right-$k$-maximal element $r$ の後ろには、 $r$ 以上の relevance をもつ要素が最大 $k$ 個続くため、$R_{\epsilon}^{-}$ の right-$k$-maximal elements の数は、$\epsilon$ と $k$ のみに依存する
  • 実際 $R_{\epsilon}^{-}$ の right-$k$-maximal elements は最大でも $km \leq k \log_{(1-\epsilon)}{(\epsilon/k)}$ である
  • $R_{\epsilon}^{-}$ の right-$k$-maximal elements をみつけるこの方法を、 $\epsilon$-Pruning とする

f:id:takuya-a:20191109192005p:plain
ε-Pruning のアルゴリズム

  • $R_{\epsilon}^{-}$ の right-$k$-maximal elements の最大の数は $km$ なので、 Algorithm 2 の時間計算量は $\Theta (n + km \log{k})$
    • 最初の項は $R$ を線形にスキャンするコスト
    • 2つ目の項は、サイズ $k$ の優先度付きキューを $\Theta (km)$ 回更新するコスト
  • このように、 $\epsilon$-Pruning は、効率的かつ効果的に OPT で処理される要素の数を減らすことができる

$\epsilon$-Filtering

  • $\epsilon$-Filtering は 2 つのフェーズからなる
    • $\epsilon$-Pruning してから OPT にかける
    • $\epsilon$-Pruning により $R_{\epsilon}^{-}$ の right-$k$-maximal elements をみつける
  • 以下の定理は、 $\epsilon$-Filtering が $(1-\epsilon)$-最適な解をみつけ、近似誤差 $\epsilon$ を通して効果と効率のトレードオフをとることを示す
  • Theorem 11.
    • $\epsilon$-Filtering は $(1-\epsilon)$-最適なフィルタリングを時間計算量 $\Theta (n + k^{2} \log_{(1 - \epsilon)}{(\epsilon / k)})$ で見つける
  • Theorem 11 の証明
    • $\epsilon$-Pruning の時間計算量は $\Theta (n + km \log{k})$
    • OPT に渡される要素数は $\Theta (km)$
    • そのため、OPT の時間計算量は $\Theta (k^{2} m)$
    • Property 10 より $m \leq \lceil \log_{(1-\epsilon)} (\epsilon / k) \rceil$ なので、命題は証明された
  • $\epsilon$-Filtering は OPT と 3つのステップ(right pruning, discretization, thresholding)を組み合わせることで relevance-aware のフィルタリング問題を解決する
  • $\epsilon$-Filtering はフィルタ済みのリストに関しての強い保証と、近似誤差 $\epsilon$ による効率と効果のトレードオフを提供する

Distributed setting

4. Experiments

  • 2つのデータセット(GoogleLocalRec, AmazonRel)を使った
    • どちらも、クエリに対して何らかの relevance をもつリストが紐付けられたデータセット
  • GoogleLocalRec
    • Google Local のデータ(場所が入っている)から作成
    • sequential recommendation [11] タスクの SoTA である TransFM という推薦システムをデータに適用
    • 各ユーザに対して、そのユーザとある場所がどのくらい relevant か、というデータ
    • 10,000 ユーザ、各ユーザに対してちょうど 16,000 のレコメンデーション
  • AmazonRel
    • Crowdflower Search Results Relevance という Kaggle コンペのデータ
      • Amazon の商品データで拡張
    • Kaggle コンペの winning solution を使ってアイテムの relevance を計算
    • 250 クエリ
      • データセットに含まれる 260 クエリのなかから、結果が 500 件未満の 10 クエリを除いたもの
    • 1クエリあたり平均で 100,000 個の要素 (relevance) をもつリスト

Metric

  • 2 つのメトリックで比較
    • DCG([$r_1, ..., r_n$])
      • \Sigma^{n}_{p=1} \frac{2^{r_{p}} - 1}{\log_{2}{p + 1}}
    • DCG-LZ([$r_1, ..., r_n$])
      • \Sigma^{n}_{p=1} \frac{r_p}{p}

Filtering methods

  • Spirin+[14] で提案された3つのアルゴリズム(OPT, Top$k$-OPT, Cutoff-OPT)に対してパフォーマンスを比較
  • Cutoff-OPT の閾値は $(r{max} + r{min}) / 2$ を使った
    • $r_{max}$ はリストの最大の、$r_{min}$ は最小の relevance

Testing details

  • C++11 で実装
  • GCC 5.4.0 を使って最大の最適化でコンパイル
  • 8個の Core i7 7700 (3.60 GHz)
  • 64GiB RAM
  • 実験は各5回ずつ実行し、平均実行時間をミリ秒単位で報告

Reproducibility

4.1 Assessment of $\epsilon$-Filtering

  • $\epsilon$-Filtering のパフォーマンスを解析した
    • $\epsilon$, $k$, $n$ を変えながら実験
  • スペースの都合上、 GoogleLocalRec でのみ実験
  • 10,000 のテストクエリ

Assessment by varying $\epsilon$ and k

f:id:takuya-a:20191109192737p:plain
Figure 1 (top)

  • 予想通り、近似誤差 $\epsilon$ を小さくするとフィルタリングの時間は増える
  • $\epsilon$ が 0.05 以下ではゆるやかな増加
    • 時間の制約が厳しいオンラインアプリケーションに対しても feasible であるといえる
  • $\epsilon$ を小さくするより $k$ を増やしたときのインパクトが大きいことがわかる
    • $k$ に関わる計算コストは $k$ の二乗オーダーであるため(Theorem 11 参照)

f:id:takuya-a:20191109192628p:plain
Figure 1 (bottom)

  • $\epsilon$ を下げていくと、実際の近似誤差は一気に下がる
  • $\epsilon$-Filtering は実用上、非常に良好な近似誤差を達成している

Assessment by varying n

f:id:takuya-a:20191109192349p:plain

  • $k = 100$ に固定して実験
  • OPT は n を増やすと計算時間は急激に増えるが、$\epsilon$-Filtering はゆっくり
  • n を 1,000 から 16,000 に増やしたとき、OPT は計算時間が 17 倍になるのに対し、$\epsilon$-Filtering は2倍ほど
  • 特筆すべきは、$\epsilon$-Filtering での $\epsilon$ を変えたときの変化は、 n を増やしてもコンスタントであること
  • 実際、$\epsilon$-Filtering の平均のフィルタ時間はリストの長さによってあまり影響を受けない
  • つまり、結果リストが非常に長い場合でも $\epsilon$-Filtering が feasible である

Speedup

  • $\epsilon$ は $\epsilon$-Pruning によってフィルタされる要素数に影響を与える
    • ここでフィルタされ、残った要素だけが OPT にかけられる

f:id:takuya-a:20191109192502p:plain
Figure 3 (top)

  • $\epsilon$-Pruning によってフィルタされた平均割合
  • 予想通り、 $\epsilon$ を減らすと、捨てられる要素は増えるが、 $\epsilon$ が 0.01 より小さくなるとほぼフラットになる
  • とくに $k$ が 100 までのとき、平均して 95% 以上の要素が $\epsilon$-Pruning でフィルタできる

f:id:takuya-a:20191109192528p:plain
Figure 3 (bottom)

  • OPT と比較したときの $\epsilon$-Filtering の速度比
  • ほとんどのパラメータの組み合わせで 10 倍以上の速度向上
  • DCG-LZ のほうが DCG よりも OPT と比較したときの速度向上が小さい
    • DCG-LZ のほうが計算コストが小さいため

4.2 Experimental Comparisons

  • $\epsilon$-Filtering と [14] で導入された 3 つの SoTA (OPT, Top$k$-OPT, Cutoff-OPT)を比較
  • Table 1 も Table 2 もメトリックは DCG-LZ(速い方)

f:id:takuya-a:20191109193032p:plain

  • $n = 16,000$(GoogleLocalRec で利用できる最大)
  • $k \in { 20, 50, 100, 200 }$
  • 以下を表記
    1. フィルタに要した平均の時間(ミリ秒)
    2. OPT との速度比(何倍速いか)
    3. 全クエリのなかで最悪の近似誤差
  • $k$ が大きくなると Top$k$-OPT のほうが強い
    • ($\epsilon$-Filtering は $k^{2}$ についている log の項(kが大きくなるとlogで大きくなる)が効いている?)

f:id:takuya-a:20191109192954p:plain

  • AmazonRel データセットは最大でクエリあたり 600,000 の結果リストがある
  • $n$ を変えながら実験したのが Table 2
  • $n \in { 50000, 100000, 200000, 500000 }$($k = 100$ で固定)
  • $n$ が増えると、 Top$k$-OPT は $\epsilon$-Filtering よりも不利
    • 理論解析での時間計算量の差が実証された形

5. Conclusion and Future Work

  • $\epsilon$-Filtering を提案
    • relevance-aware なフィルタリング問題を解くための効率的な近似アルゴリズム
    • 結果として得られる結果リストの relevance について、近似精度に対する強い保証がある
  • 提案したアルゴリズムは、与えられた近似誤差 $\epsilon$ のもと、 (1-$\epsilon$)-optimal filtering を見つけることができる
    • 得られるリストの relevance は、少なくとも最適なリストの (1-$\epsilon$) 倍
  • $\epsilon$-Filtering と SoTA の手法 3つ(OPT, Top$k$-OPT, Cutoff-OPT)を比較する評価を行った
    • 2つのパブリックデータセット (GoogleLocalRec, AmazonRel) を使った
  • 近似誤差を非常に小さく抑えながら、OPT に対して最大 2 桁の高速化
    • 実際、小さな $\epsilon$ (たとえば 0.01, 0.001)に対して、$\epsilon$-Filtering の近似誤差は常に 0 だった
    • すべてのテストクエリに対して最適な結果リストを返した
    • かつ、OPT に対して 10 倍から 147 倍高速だった
  • 今後、right-$k$-maximal elements をさらに制限したクラスについての調査を計画している
    • right-$k$-maximal elements は我々の研究に対して中心的な役割を果たしている
    • 効率的に特定できるこれらの要素のクラスが発見できると、近似アルゴリズムのさらなる高速化につながる
  • また、実世界の分散検索クエリで $\epsilon$-Filtering のパフォーマンスを評価する予定である

感想

  • Top$k$-OPT は $\epsilon$-Filtering と同等に高速ながら、十分に低い近似誤差
    • 0.5-approximation (最大で 0.5 の近似誤差)だが実験では 0.05 ~ 0.15
    • $\epsilon$-Filtering はほしい要素数 $k$ が大きいとき、効果が薄い
      • $k$ を大きくするとTop$k$-OPT のほうが速くなる(Table 1)
    • 実装も簡単そうなので実用上は Top$k$-OPT で十分かもしれない

論文メモ: Accelerated Query Processing Via Similarity Score Prediction (SIGIR 2019)

IR Reading 2019秋で標題の論文を紹介しました。 発表で使ったスライドは以下です:

speakerdeck.com

以下は、この論文を読んだときのメモです。

概要

  • 検索エンジンで top-k のクエリ処理を高速化するのが目的
  • クエリ処理中の動的な文書の pruning(枝刈り)に着目
  • 通常のアルゴリズムでは、それまでに処理した文書の top-k のスコアを保持
    • このスコアより小さいスコアの文書はスキップしてよい
    • クエリ処理中の top-k のスコアを閾値として使っている
  • この方法はロスレス、つまり正確な top-k の文書が得られる
  • 閾値の初期値は通常、文書集合のなかの最低のスコアを使う
  • この論文では、機械学習を使ってクエリの特徴量から最終的な閾値の予測をする
    • これにより、多くの文書をスキップできるようになる = 高速化できる
  • 予測した閾値が実際より高いと結果が不正確になる
    • 正確な結果を得るためには再計算が必要になる
    • 予測値が実際より低いとより多くの文書を処理しないといけない = 遅くなる

1. Introduction

  • Web 検索においてクエリ処理に多くの電気代、ハードウェアコストがかかっている
  • その効率を上げることで金銭コストと環境への負荷を減らせる
  • ほとんどの Web 検索において、ターム(単語)は文書において独立に生起し、スコアは各タームの貢献度 (contribution) の総和として計算できると仮定している
    • 少なくとも最初のフェーズでは(リランキングではもっと複雑なモデルで計算されることもある)
    • 各タームの貢献度は文書のインデキシング時に決定できる(事前計算可能)
  • k 個のスコアトップの文書をクエリへの戻り値とする
    • そのままユーザに表示してもよいし、リランクフェーズへの入力としてもよい
  • クエリ処理の効率化の方法として MaxScore や WAND が開発された
  • どちらも、クエリ処理中の top-k スコアを閾値 \theta とし、スコアがそれ以下となる文書をスキップする
  • すべての文書についてクエリ処理すると、 \theta は、その文書集合 D に対するクエリ Q の top-k スコア \Theta_k (D, Q) に収束する

f:id:takuya-a:20191028010014p:plain

Research Questions

  • RQ1
  • RQ2
    • もし前もって \Theta_k (D, Q) を推定できるなら、その事前知識によってどの程度クエリ処理を速くできるか?
  • RQ3
    • \Theta_k (D, Q) の事前知識を使って MaxScore、WAND、BMWのような手法を改良できるか?

2. Background

事前知識と関連研究

Term-Weighted Similarity Scoring

  • クエリ Q = {t_1, t_2, ..., t_q} (q 個のタームを含む)と文書 d に対しての類似度スコア (similarity) として以下の形を仮定する:
  • S(d, Q) = f_1(d) + \Sigma_{i=1}^{q} f_2(t_i, Q) \cdot C(t_i, d)
    • f_1(\cdot): 文書のみに依存する関数
      • インデキシング時に事前計算可能
    • f_2(\cdot, \cdot): タームとクエリの関数
      • 文書に依存しないのでクエリ処理時に1回だけ計算すればよい
    • C(t,d): 文書 d におけるターム t の相対的な重要度
      • クエリに依存しない
  • この形は BM25 にも当てはまる
    • f_1(\cdot) = 0 かつ f_2(\cdot, \cdot) は定数

Query Processing

  • 一般的な転置インデックスでのクエリ処理を考える
    • タームとポスティングリストが保存されている
    • ポスティングリストには文書 ID (ソート済み)の集合が入っている
    • その他、タームごとの最大スコアなどの補助的なデータを格納できるとする
  • document-at-a-time (DAAT) によるクエリ処理を想定
    • タームごとにポスティングリストを処理するのではなく、
    • 複数のポスティングリストを同時にカーソルで処理
    • すべてのカーソルを一番前にセットし、その文書のクエリ処理が終わったら後ろにずらす
    • すべてのカーソルが最後までいったら終了、top-k の文書集合を返す
  • WAND
  • BMW
    • 最新の研究では block-max WAND を可変長ブロックにした手法が提案されている
    • この研究では可変長ブロック版の block-max WAND を使う
  • Q_k
    • 各ポスティングリストにおいて、 k 番目に大きい部分スコア( C(t, d) )をインデックスに保存しておく
      • k はよく使用されるものについてだけ記録(10, 100, 1000など)
    • クエリ Q は複数のタームを含むが、上記のスコアのうち、最大のものを Q_k とする
    • Q_k閾値 \theta の安全な初期値として使える [13, 25]
      • ただし、「f_1(\cdot) = 0 かつ f_2(\cdot, \cdot) が定数」が成り立つときのみ
      • BM25 ではこれが成り立つ
    • この Q_k より良く \Theta_k を推定するのが、この研究のゴール

Machine Learning for Efficiency

  • 検索結果候補を生成するステージと、LTR 取得ステージ(LTR retrieval stage)がある
    • ほとんどの効率ベースの機械学習研究は後者にフォーカスしている
  • プロダクションの検索エンジンにおいて、LTR で効率ベースの機械学習の手法としては LambdaMART や GBRT がいまだ SOTA だと考えられている
    • それらの改良手法も多く提案されている
  • リランクされる文書数を減らすアプローチもある
    • 初期のステージでの効率改善のために ML を適用した研究は少なく、ML の予測コストが容易にそれによるベネフィットを超えてしまう
  • 近年の LTR の研究はニューラル IR にフォーカスしている
    • 効率的なエンドツーエンドの検索についての研究もあるが、効率という意味ではこの研究と競合するとは言えない

3. Exploring Potential Gains

Oracle Evaluation

  • RQ2: もし前もって \Theta_k (D, Q) を推定できるなら、その事前知識によってどの程度クエリ処理を速くできるか?
  • \Theta_k (D, Q) をクエリ処理の前に計算しておき、各枝刈りアルゴリズム閾値として渡してしまう
    • 最適な閾値が分かっている状態での、MAX パフォーマンスを計測
  • 実験条件
    • Gov2 データセット、5,000 クエリで実行時間をミリ秒単位で計測
    • 枝刈りアルゴリズムとして MaxScore, WAND, BMW の 3 つを使って比較
    • \nabla: そのスコア関数でとりうる最低のスコア(BM25なので0に設定)を \theta の初期値として実行
    • Q_k: クエリ Q において k 番目に大きい contribution (部分スコア)
    • \Theta_k (D, Q): オラクルを \theta の初期値として与えて実行

f:id:takuya-a:20191028005928p:plain

  • 実行時間の単位はミリ秒
  • ラクルを使うと \nabla よりも 30% から 50% ほどスピードアップ

Sensitivity

f:id:takuya-a:20191028010103p:plain

  • 初期値を \Theta_k の 0% から 100% まで変えながらクエリの実行時間を計測
  • \Theta_k の 75% 以下の初期値では十分なゲインを得られない
  • \Theta_k におけるスピードに匹敵するには 0.9 \Theta_k くらいの初期値でなければならない

Failure Detection

  • \Theta_k の推定値 \Theta_k が実際より大きいとき、得られる top-k の結果は正確ではなくなる
  • 計算結果が k 件になっているかどうかをチェックして、結果が正確かどうかを確認できる場合もある
  • 実際にはもっと微妙なケースがあり、ヒープには k 件の文書があるが、その最小スコアが推定値 \hat{\Theta}_k より小さい場合がある
  • このような場合、推定値が大きすぎたということなので、全体の再計算が必要になる
  • ただし、ヒープの最小のスコアを新たな初期値とできる
    • すくなくともそれ以上のスコアをもつ文書が k 個以上あることがわかっているため
    • この再計算は正確であることが保証される

Query Processing Revisited

f:id:takuya-a:20191028010138p:plain

  • L2: 閾値の予測値を \theta の初期値とする
  • L3: 優先度付きキュー(ヒープ)の最小スコア
  • L5 - L6: スコアの upper bound が \theta を超える文書だけスコア計算
  • L7 - L8: 文書のスコアがヒープの最小スコアより大きければヒープに入れる
  • L9 - L13: ヒープサイズが k 個を超えたときの処理
  • L15 - L17: この場合、正確な top-k が得られていないので再計算

4. Threashold Prediction Models

  • 複雑なモデルを使うと予測精度が上がる可能性があるが、予測が遅くなる
  • Table 1 では速い場合、top-k クエリは 5-20 msec で実行が完了するので、閾値の予測によってクエリを速くするためには、もっと短い時間で予測を完了する必要がある
    • GPU を使うと転送コストが高い
  • CPU 時間で1ミリ秒以内に予測できるシンプルなモデルを調べることにする

Algorithmic Predictor

  • \nabla が1つめのベースライン
  • Q_k を2つめのベースラインとする
    • \nabla よりは予測値として良く、決定的

Probabilistic Predictor

  • 確率的なモデルを最初のアプローチとして採用
    • 予測値 \hat{\Theta}_k の分布を生成する確率モデル
  • 学習後に分布が見られるメリットがある

f:id:takuya-a:20191028010216p:plain

  • ガウス分布のときの例
  • q は quantile(分位点)
  • 学習後の分布で、 q を決めてそれを予測値とする方法もある
    • q = 0.5 は攻めすぎ(overestimate したときのペナルティが大きいため)
    • q = 0.1 は保守的(underestimate になりがちで計算コストは高いまま)
  • 非対称な損失関数を考えることでペナルティを定式化し、その効果を織り込むことができる
    • overestimate に対して underestimate の \alpha 倍の損失を与える
  • Minimum Bayes Risk (MBR)
    • 予測分布の上で、損失の期待値が最小となるような \hat{\Theta}_k を選択できる
    • 最適値は 1/(\alpha + 1) の quantile となることが証明されている [6]
    • たとえば、 \alpha = 3 のとき 0.25 quantile (四分位点) が最適
  • 確率的なアプローチの利点
    • 損失関数がモデルから独立しているので、
      • テスト時に何回もモデルを訓練することなく、並列で予測値を取り出せる
      • クエリごとの損失が定義できる
  • 確率的なアプローチの欠点
    • 高速に予測できるようなモデルは限られている
    • モデルには Bayesian Linear Regression (BLR) を使った
    • これは解析的に(閉形式で)解が求められるので高速に計算できる
    • サンプリングのような古典的なベイズ推論では遅すぎる

Loss-Based Predictor

  • 損失関数を使った機械学習モデルも考える
    • 分布を生成できないが、与えられた損失関数に対して直接学習しようとする
  • 損失関数には非対称にした Huber loss [22] を採用
    • over-estimate に対してより大きな損失を与える

f:id:takuya-a:20191028010333p:plain

  • マルチレイヤーパーセプトロン (MLP) を採用
    • MLP-L2: 2層(隠れ層が 2)の MLP
    • MLP-L4: 4層(隠れ層が 4)の MLP
    • いずれも CPU でも効率的に計算可能
  • MLP の学習
    • 隠れ層のユニット数はすべて入力層と同じ
    • Adam で学習
    • 学習率は 0.001
    • dev set で early stopping
    • バッチ正則化
    • ドロップアウト率 0.25
  • 損失ベースのアプローチの欠点
    • 損失が訓練時にわかっている必要がある
    • 異なる損失には異なるモデルが必要
      • クエリごとに損失を変えようとしたらたくさんのモデルが必要になる
    • 損失を変えようとしたら再訓練しなければならない

Data, Features and Costs

  • モデルの学習に使ったクエリログ
    • 2006 Microsoft Query log
    • 8,073,821 クエリ
  • データセット(詳細は Section 5 で)
    • Gov2
    • ClueWeb09B
  • 特徴量
    • Table 2
    • インデックスに保存
    • 1ポスティングあたり 7.5 bits (Gov2) 6.6 bits (ClueWeb09B)
  • 学習後のモデルサイズ
    • 1.0 MB (BLR), 1.7 MB (MLP-L4), 0.9 MB (MLP-L2)
  • 学習は 30 分以内に終わった

Prediction Speed

  • 0.6 ms (MLP-L2)
  • 0.9 ms (MLP-L4)
  • 0.6 ms + 0.1 ms (BLR)
    • クエリの予測分布を得るのに 0.6 ms
    • 分位点を得るのに 0.1 ms
  • C/C++ から Python を呼ぶオーバーヘッドを含んだ実行時間
    • プロダクションでは C/C++ で書けばもっと速い

5. Experiments

Data Resources

  • Gov2
  • ClueWeb09B
    • 2009年にクロールされた 5000 万の Web 文書
  • クエリログ

Software Resources

  • Indri でインデキシング
  • recursive graph bisection で処理
  • PISA experimentation platform に与える
  • BMW は可変長ブロックのものを使い、ブロックに含まれる要素数は平均 40

Model Distribution Trade-Offs

f:id:takuya-a:20191028010421p:plain

6. Refinements

Over-Prediction Risk

  • 閾値を overestimate したとき、 Algorithm 1 では L15 - L17 で再計算が走る
  • これが重い

f:id:takuya-a:20191028010454p:plain

  • \hat{\Theta}_k が実際の値(オラクル)より大きかったときに、MaxScore, WAND, BMW でどれくらい再計算が走りうるか
  • 閾値の初期値を、オラクルより徐々に大きくしていって、各アルゴリズムが返す結果が正しい確率を調べた
    • ただし tie-breaking のために文書の順番が入れ替わるのは許す
  • データセットは ClueWeb09B、 k = 1000 で固定
  • BMW は文書をスキップする能力が高いので、overestimate に対して頑健ではない

Reducing the Re-Computation

f:id:takuya-a:20191028010523p:plain

  • クエリには q 個のタームが含まれている
  • 最大で [tex:2q - 1] のタームの組み合わせがある
    • それぞれの組み合わせごとに U_bound が計算できる
    • サブクエリと呼ぶことにする
  • いずれかのサブクエリの U_bound が \hat{\Theta}_k を超えているはず
    • 少なくとももとのクエリ(すべてのタームを含む)は超えている
  • また、いずれかのサブクエリの U_bound は h_threshold を下回っていることが予想される
    • これらのタームの組み合わせは安全に無視できる
  • この範囲 [h_threshold, \hat{\Theta}_k] の範囲に U_bound が入っているサブクエリだけ、スコアを評価すればよい
    • スコアはこれらのタームの貢献度 C(t, d) を足し合わせる
  • このサブクエリの評価では、その中のタームは AND (conjunction) クエリでよい(件数は少ない)
    • 非常に高速に処理できる
  • 改良済みのアルゴリズムは Algorithm 2

Overestimation Refinements

f:id:takuya-a:20191028010556p:plain

  • Algorithm 1 と 2 を比較
  • すべてのパーセンタイル、および quantile (0.5, 0.3, 0.1, 0.05, 0.01) で Algorithm 2 のほうが速い
    • quantile 0.5 はよりアグレッシブな(大きい)閾値
  • 最大で 22% 速くなっている
    • quantile が大きいほうがより性能差がある

f:id:takuya-a:20191028010623p:plain

  • Algorithm 1 と 2 で、再計算にかかるコストを比較
  • Algorithm 2 は再計算のときにスコア計算が必要となる文書数が明らかに少ない
    • この改良で効率的になっていることが示されている

7. Conclusion

  • ヒープの閾値が予測できることを示した (RQ1)
  • また、それらが動的枝刈りアルゴリズムのパフォーマンスを改善することを示した (RQ2)
  • アルゴリズム的な改善が可能であることも示した (RQ3)

感想

  • 損失の係数 \alpha をどうやって決めるか
    • MBR に与える \alphaMLP の Huber Loss の q はハイパーパラメータだが、再計算のペナルティはデータセット上で計測できるはずなので、直接、損失関数に組み込んでしまってもいいのではないか?
    • 損失関数の \alpha はクエリごとに変えるべきだろうか?
  • k 番目のスコアを保存しているが、 k \in {10, 100, 1000} と決め打ちであり恣意的
    • これは Q_k を初期値として使うアプローチも同様
    • パフォーマンス最適化のために k を変えるには再インデキシングが必要
  • 確率モデルベースの手法は、損失ベースのものに比べてモデルの汎用性がある
    • とはいえ、コーパスの性質が変わると再学習はしたほうがよさそう
    • 日本語と英語のコーパスで同じモデルでいいとは思えない
  • 決定的な方法( Q_k を使う)でも十分では?
    • Table 4 をみると、ベースラインからの差はそれほど大きくない
    • Algorithm 2 で多少改善するとはいえ、差分はせいぜい 20% 程度
    • 枝刈りアルゴリズムの差のほうが大きい
    • 仕組みがシンプルな Q_k のほうが取り回しやすい(機械学習いらないし)
  • もっといいモデルを作れる余地はある

参考

動的枝刈りアルゴリズムの詳細については以下の解説記事がおすすめ!

EdgeRouter設定メモ: IPv6/IPoE + DS-Liteでインターネット高速化

https://www.speedtest.net/result/7772608929.png

家庭用の LAN を IPv6 に移行したら、下り 400 - 500 Mbps、上り 500 - 600 Mbps 出るようになったので、環境や設定などを共有します。

参考:

blog.amedama.jp techlog.iij.ad.jp

環境

CLI による操作

EdgeRouter は Web ベースの GUI での設定と、CLI での設定が可能。せっかくなので CLI で設定することにした。CLI に接続するには、以下の方法がある:

  • ssh での接続
    • デフォルトで eth0 に LAN ケーブルを接続すると $ ssh ubnt@192.168.1.1 で接続できる
    • ネットワークの設定変更などで見えなくなることがある
  • シリアルコンソールでの接続
    • GNU Screen で接続できる
    • ネットワークの設定変更によらず通信できる

EdgeRouter 6P には RJ45 のシリアルコンソールがついているので、今回はシリアルコンソールで設定することにした。

PC との接続にはこのようなガジェットを使う:

【CISCO互換ケーブル】FTDI chipset USB RJ45 コンソールケーブル

【CISCO互換ケーブル】FTDI chipset USB RJ45 コンソールケーブル

ボーレートは 115200(ユーザマニュアルに書いてあった)。デバイスファイルは環境によって変わるが、たとえば /dev/tty.usbserial-AL03M04H だった場合は、以下で接続できる:

$ screen /dev/tty.usbserial-AL03M04H 115200

EdgeOS のコマンド

EdgeOS のシェルには、操作モード(プロンプトが $ )と設定モード(プロンプトが # )の2つの状態がある。 それぞれ使えるコマンドが異なるので注意。

基本コマンド

頻出コマンドは以下:

  • show
    • (操作モードのみ)いろいろなシステム情報の表示
  • configure
    • (操作モードのみ)操作モードから設定モードに入る
  • exit
    • (設定モードのみ)設定モードから操作モードに戻る
  • set
    • (設定モードのみ)システム・シェルオプションの設定
  • commit
    • (設定モードのみ) set したものをすべて反映する(再起動すると変更は失われる)
  • compare
    • (設定モードのみ) commit する前に diff を確認できる
  • save
    • (設定モードのみ) commit したものをすべてファイルシステムに書き込む(再起動しても設定の変更が残る)
  • reboot
    • (操作モードのみ)機器を再起動する
  • ping ping6
    • (操作モードのみ)機器からの疎通を確認する(それぞれ IPv4/IPv6 で接続)

なお、Tab を 1 回入力するとサブコマンドやパラメータの候補が、Tab を 2 回入力すると説明が表示される。

EdgeOS は VyOS からのフォークなので、VyOS のドキュメントも参考になる:

操作モードのコマンド一覧

ubnt@ubnt:~$
Possible completions:
  add           Add an object to a service
  clear         Clear system information
  configure     Enter configure mode
  connect       Establish a connection
  copy          Copy data
  debug         Enable debugging of specified routing protocol
  delete        Delete a file
  disconnect    Take down a connection
  generate      Generate an object
  initial-setup Enter initial configuration dialog
  no            Disable or reset operational variable
  ping          Send Internet Control Message Protocol (ICMP) echo request
  ping6         Send IPv6 Internet Control Message Protocol (ICMP) echo request
  reboot        Reboot the system
  release       Release specified variable
  rename        Re-name something.
  renew         Renew specified variable
  reset         Reset a service
  restart       Restart a service
  set           Set system or shell options
  show          Show system information
  shutdown      Shutdown the system
  telnet        Telnet to <hostname|IPv4 address>
  terminal      Control terminal behaviors
  traceroute    Track network path to <hostname|IPv4 address>
  traceroute6   Track network path to <hostname|IPv6 address>
  update        Run an update command

設定モードのコマンド一覧

ubnt@ubnt#
Possible completions:
  confirm   Confirm prior commit-confirm
  comment   Add comment to this configuration element
  commit    Commit the current set of changes
  commit-confirm
        Commit the current set of changes with 'confirm' required
  compare   Compare configuration revisions
  copy      Copy a configuration element
  delete    Delete a configuration element
  discard   Discard uncommitted changes
  edit      Edit a sub-element
  exit      Exit from this configuration level
  load      Load configuration from a file and replace running configuration
  loadkey   Load user SSH key from a file
  merge     Load configuration from a file and merge running configuration
  rename    Rename a configuration element
  rollback  Rollback to a prior config revision (requires reboot)
  run       Run an operational-mode command
  save      Save configuration to a file
  set       Set the value of a parameter or create a new element
  show      Show the configuration (default values may be suppressed)

設定情報の表示

  • show configuration
    • running configuration を表示
  • show configuration all
    • デフォルトの情報を含む running configuration を表示
  • show configuration commands
    • running configuration を表示(あとでこれをコピペすれば再現できる)

ルーティングの表示

インタフェースごとの設定情報の表示

  • show interfaces ethernet eth0
    • eth0 の設定情報の表示

物理構成

インターネット回線
└── ONU(光回線終端装置)
    └── EdgeRouter 6P
        ├── 無線 AP(ブリッジモード)
        │   └── スマートフォンなど(無線 LAN 接続)
        └── PC など(有線 LAN 接続)

今回は EdgeRouter の eth0 を WAN (アップリンク)とし、ONU に LAN ケーブルで接続した。 eth1 eth2 にはブリッジモードの無線 AP や PC などの DHCP クライアントがぶら下がる想定。

IPoE + DSLite の設定

まずは EdgeRouter から IPv6 で接続できるようにし、そのあと DS-LiteIPv4 接続(IPv4 over IPv6 トンネル)できるように設定する。

IPv6 アドレスの自動設定 (autoconf) と割当ての確認

eth0 に RA (Router Advertisement) を利用した IPv6 アドレスとルーティングの自動設定を行うには、以下のようにする。

configure
set interfaces ethernet eth0 ipv6 address autoconf
commit
exit

10分ほど待つと RA が流れてきて IPv6 アドレスが設定される。 $ show interfaces コマンドで確認できる:

ubnt@ubnt:~$ show interfaces
Codes: S - State, L - Link, u - Up, D - Down, A - Admin Down
Interface    IP Address                        S/L  Description
---------    ----------                        ---  -----------
eth0         192.168.1.1/24                    u/u
             ****:****:****:****:****:****:****:****/64
eth1         -                                 u/D
eth2         -                                 u/D
eth3         -                                 u/D
eth4         -                                 u/D
eth5         -                                 u/D
lo           -                                 A/D

IPv6 のルーティングテーブルの情報は $ show ipv6 route で確認できる:

ubnt@ubnt:~$ show ipv6 route
IPv6 Routing Table
Codes: K - kernel route, C - connected, S - static, R - RIP, O - OSPF,
       IA - OSPF inter area, E1 - OSPF external type 1,
       E2 - OSPF external type 2, N1 - OSPF NSSA external type 1,
       N2 - OSPF NSSA external type 2, B - BGP
Timers: Uptime
IP Route Table for VRF "default"
K      ::/0 [0/1024] via fe80::212:e2ff:fe86:e24c, eth0, 00:02:48
C      2409:250:8a00:d700::/64 via ::, eth0, 00:02:37
C      fe80::/64 via ::, eth0, 00:19:49

ここまでで $ ping6 2001:4860:4860::8888Google Public DNSIPv6 アドレス)が通るようになる:

ubnt@ubnt:~$ ping6 2001:4860:4860::8888
PING 2001:4860:4860::8888(2001:4860:4860::8888) 56 data bytes
64 bytes from 2001:4860:4860::8888: icmp_seq=1 ttl=58 time=4.44 ms
64 bytes from 2001:4860:4860::8888: icmp_seq=2 ttl=58 time=4.74 ms
...

ただし、 IPv4 の設定をしていないので $ ping 8.8.8.8 は通らない:

ubnt@ubnt:~$ ping 8.8.8.8
connect: Network is unreachable

DS-Lite による IP-IP トンネルの設定

local-ip には eth0IPv6 アドレス、 remote-ip には AFTR の IPv6 アドレスを設定する(IIJ の場合は transix のアドレスを設定)。

configure
set interfaces ipv6-tunnel v6tun0 encapsulation ipip6
set interfaces ipv6-tunnel v6tun0 local-ip ****:****:****:****:****:****:****:****  # 割り当てられた IPv6 アドレス
set interfaces ipv6-tunnel v6tun0 remote-ip 2404:8e01::feed:100  # transix の AFTR
set interfaces ipv6-tunnel v6tun0 mtu 1500
set interfaces ipv6-tunnel v6tun0 multicast disable
set protocols static interface-route 0.0.0.0/0 next-hop-interface v6tun0
commit
exit

これで $ ping 8.8.8.8 が通る:

ubnt@ubnt:~$ ping 8.8.8.8
PING 8.8.8.8 (8.8.8.8) 56(84) bytes of data.
64 bytes from 8.8.8.8: icmp_req=1 ttl=123 time=4.58 ms
64 bytes from 8.8.8.8: icmp_req=2 ttl=123 time=4.14 ms

ルータ再起動後でもすぐに使えるようにする

上記の設定だと、ルータを再起動後すると、IPv6 アドレスや対向ルータへのルーティングが RA として流れてくるまで 10分ほど接続できない。

設定後すぐに使いたい場合は IPv6 アドレスを設定し、対向ルータのリンクローカルアドレスを next hop に設定する。 対向ルータのリンクローカルアドレスは、 $ show ipv6 neighbors でわかる( fe80:: で始まるアドレス):

ubnt@ubnt:~$ show ipv6 neighbors
fe80::212:e2ff:fe86:e24c dev eth0 lladdr 00:12:e2:86:e2:4c router REACHABLE
2409:250:8a00:d700::fffe dev eth0 lladdr 00:12:e2:86:e2:4c router REACHABLE

reboot などですべての設定をクリアし、以下のコマンドで再設定する:

configure
set interfaces ethernet eth0 address ****:****:****:****:****:****:****:****/64  # 割り当てられた IPv6 アドレス
set interfaces ipv6-tunnel v6tun0 encapsulation ipip6
set interfaces ipv6-tunnel v6tun0 local-ip ****:****:****:****:****:****:****:****  # 割り当てられた IPv6 アドレス
set interfaces ipv6-tunnel v6tun0 remote-ip 2404:8e01::feed:100
set interfaces ipv6-tunnel v6tun0 mtu 1500
set interfaces ipv6-tunnel v6tun0 multicast disable
set protocols static interface-route 0.0.0.0/0 next-hop-interface v6tun0
set protocols static route6 ::/0 next-hop fe80::212:e2ff:fe86:e24c interface eth0  # 対向ルータのリンクローカルアドレス
commit
exit

DNS の設定

Google Public DNSを使う。

configure
set system name-server 2001:4860:4860::8888
set system name-server 2001:4860:4860::8844
commit
exit

ここまでで $ ping6 google.com $ ping google.com が通るようになる。

タイムゾーンの設定

タイムゾーンAsia/Tokyo に。

configure
set system time-zone 'Asia/Tokyo'
commit
exit

NTP の設定

NTP サーバはネットワーク的に近い ntp.nict.jp を使う。

configure
delete system ntp server
set system ntp server 'ntp.nict.jp'
commit
exit

DNS forwarding の設定

ルータを DNS フォワーダとして動作させる。

set service dns forwarding cache-size 5000
set service dns forwarding options listen-address=192.168.1.1
set service dns forwarding listen-on eth1
set service dns forwarding listen-on eth2
set service dns forwarding listen-on eth3
set service dns forwarding listen-on eth4
set service dns forwarding listen-on lo

DHCP の設定

DHCP で配布する DNS サーバの IP は、上記で設定した 192.168.1.1 (自分自身)にする。

set service dhcp-server disabled false
set service dhcp-server hostfile-update disable
set service dhcp-server shared-network-name HOME authoritative enable
set service dhcp-server shared-network-name HOME subnet 192.168.1.0/24 default-router 192.168.1.1
set service dhcp-server shared-network-name HOME subnet 192.168.1.0/24 dns-server 192.168.1.1
set service dhcp-server shared-network-name HOME subnet 192.168.1.0/24 lease 86400
set service dhcp-server shared-network-name HOME subnet 192.168.1.0/24 domain-name home
set service dhcp-server shared-network-name HOME subnet 192.168.1.0/24 start 192.168.1.64 stop 192.168.1.254

eth1 - eth4 の設定

とくに VLAN を分けたりはしないので、 eth1 - eth4 を同じブリッジ br0 に接続する。 EdgeOS で bridge を使うとハードウェアにオフロードされない(オフロードされるのは switch )が、EdgeRouter 6P には switch chip が搭載されておらず、 bridge で接続するしかない。

delete interfaces ethernet eth0 address 192.168.1.1/24
set interfaces bridge br0 address 192.168.1.1/24
set interfaces ethernet eth1 bridge-group bridge br0
set interfaces ethernet eth2 bridge-group bridge br0
set interfaces ethernet eth3 bridge-group bridge br0
set interfaces ethernet eth4 bridge-group bridge br0

全設定

ファイアウォールの設定は省略)

configure
set interfaces ethernet eth0 address ****:****:****:****:****:****:****:****/64
set interfaces ipv6-tunnel v6tun0 encapsulation ipip6
set interfaces ipv6-tunnel v6tun0 local-ip ****:****:****:****:****:****:****:****
set interfaces ipv6-tunnel v6tun0 remote-ip 2404:8e01::feed:100
set interfaces ipv6-tunnel v6tun0 mtu 1500
set interfaces ipv6-tunnel v6tun0 multicast disable
set protocols static interface-route 0.0.0.0/0 next-hop-interface v6tun0
set protocols static route6 ::/0 next-hop fe80::212:e2ff:fe86:e24c interface eth0

set system name-server 2001:4860:4860::8888
set system name-server 2001:4860:4860::8844

set system time-zone 'Asia/Tokyo'

delete system ntp server
set system ntp server 'ntp.nict.jp'

set service dns forwarding cache-size 5000
set service dns forwarding options listen-address=192.168.1.1
set service dns forwarding listen-on eth1
set service dns forwarding listen-on eth2
set service dns forwarding listen-on eth3
set service dns forwarding listen-on eth4
set service dns forwarding listen-on lo

set service dhcp-server disabled false
set service dhcp-server hostfile-update disable
set service dhcp-server shared-network-name HOME authoritative enable
set service dhcp-server shared-network-name HOME subnet 192.168.1.0/24 default-router 192.168.1.1
set service dhcp-server shared-network-name HOME subnet 192.168.1.0/24 dns-server 192.168.1.1
set service dhcp-server shared-network-name HOME subnet 192.168.1.0/24 lease 86400
set service dhcp-server shared-network-name HOME subnet 192.168.1.0/24 domain-name home
set service dhcp-server shared-network-name HOME subnet 192.168.1.0/24 start 192.168.1.64 stop 192.168.1.254

delete interfaces ethernet eth0 address 192.168.1.1/24
set interfaces bridge br0 address 192.168.1.1/24
set interfaces ethernet eth1 bridge-group bridge br0
set interfaces ethernet eth2 bridge-group bridge br0
set interfaces ethernet eth3 bridge-group bridge br0
set interfaces ethernet eth4 bridge-group bridge br0

commit
exit

ファームウェアのアップデート

ファームウェアのアップデートは、ルータがインターネットに繋がっていれば、イメージの URL を指定するだけで勝手にダウンロードしてくれてアップデートできるので簡単。

Ubiquiti Networks - Downloads から最新のファームウェアを探し、URL をコピーする(対象のファームウェアを選んだあと、 DOWNLOAD ボタンを押し、条項に同意すると URL が表示される)。

URL を指定してイメージを組み込む:

$ add system image https://dl.ubnt.com/firmwares/edgemax/v1.10.x/ER-e300.v1.10.7.5127989.tar

show system image でブートイメージが切り替わったのが確認できる:

ubnt@ubnt:~$ show system image
The system currently has the following image(s) installed:

v1.10.7.5127989.181001.1228    (default boot)
v1.9.8.5012183.170825.0258     (running image)

A reboot is needed to boot default image

reboot してからまた見てみると、 v1.10 で動いていることがわかる:

ubnt@ubnt:~$ show system image
The system currently has the following image(s) installed:

v1.10.7.5127989.181001.1228    (running image) (default boot)
v1.9.8.5012183.170825.0258

show version でも切り替わっていることが確認できる:

ubnt@ubnt:~$ show version
Version:      v1.10.7
Build ID:     5127989
Build on:     10/01/18 12:28
Copyright:    2012-2018 Ubiquiti Networks, Inc.
HW model:     EdgeRouter 6P
HW S/N:       ************
Uptime:       02:16:26 up 11 min,  1 user,  load average: 0.01, 0.10, 0.11

設定の参考にしたエントリ

ISUCON8 で予選を突破したのでまとめる

ディメンジョナルハイソサイエティぬれねずみというチーム名で ISUCON8 に出場しました。言語は Perl を選択しました。 結果は 40,867点で、13位 / 528組

技術的なことについては、すでにチームメンバーの2人が書いてくれているので、自分からは主にそれ以外のことについてまとめます。チームメンバーのブログは以下:

メンバー構成

同じ会社の同僚3人で出ました。

  • id:hitode909
    • アプリケーションエンジニア
    • Perl めっちゃ書ける、普段から業務でバリバリ使ってそう
    • 出場は3回目
  • id:shiba_yu36
    • アプリケーションエンジニア
    • Perl めっちゃ書ける
    • 初出場
  • id:takuya-a
    • アプリケーションエンジニア
    • Perl は数年書いていたけど、最近はずっと Python を書いている
    • 初出場

みんな普段は Web サービスの開発とかをやっています。全員アプリケーションエンジニア(サーバサイドもクライアントサイドも書く)で、オペレーションが専門のエンジニアはいませんでした。 自分はあとの二人と一緒に仕事をしたことはなくて、勉強会を一緒にやったりしたくらい。

予選の申込み締切直前にたまたま Slack にいて、偶然暇だったら出ましょう、って言って組みました。 当日の予定が空けられるか怪しくて、みんな出れる確率 5% くらいだねって話していたけど、意外と条件が整って全員出られました。

ジェネレータでチーム名を決めたら「ディメンジョナルハイソサイエティぬれねずみ」っていう名前になったけど、ディメンジョナルもハイソサイエティも表記揺れがあって入力が難しいので失敗でした。

事前にやった準備

  • 予選1週間前の昼休みに話し合った
    • GitHub のプライベートリポジトリを作り、その場で issue や Wiki を作っていった
      • あとでそのトピックについて会話できるように
    • 言語を決めた
      • Go を予習しておいて、問題を見て決める案もあったけど、結局事前に勉強する時間は取れなかった
      • みんな慣れていて運用知見もある Perl でいこうという結論になった
    • デプロイ方式を決めた
      • 去年参加した id:hitode909 がよかったということで rsync デプロイに決めた
  • id:shiba_yu36 が事前に素振りしたり、やることをまとめたりしてくれていた

事前にやってよかったこと

  • やることリストの整備
    • id:shiba_yu36 がメインでまとめてくれたリストが役に立った(参考
    • リスト化しておくことで安心感が生まれ、落ち着きにつながった気がする
  • rsync デプロイスクリプトを整備
    • 手元で修正したものを本番環境ですぐに試せ、高速にトライアンドエラーできた
      • git push したものを各サーバーに pull させる方式だとタイムラグがある
    • 今回はベンチマーカーもすぐに回る環境だったので、うまくはまった

予選当日にやったこと

  • コードやテーブルを眺めつつ作戦を考える
    • スキーマ定義を眺めて、テーブル間の関係を把握し、ホワイトボードに描いた
      • MySQL に入って各テーブルの件数を COUNT(*) して追記した
    • 思いついた作戦はどんどんホワイトボードに書いていく
      • とくに効きそうなものに + や ++ をつけていった
  • ペアプロ
    • 残りの二人のメンバーのほうが手が速いので、「ペアプロ役やります」って宣言した(自分はほぼコードを書かなかった)
    • 基本的には、一人が作業しているあいだ、残りの二人はペアプロ、という動き
    • ペアプロ開始時に情報共有する(手を入れようとしているエンドポイントについて、わかったことなど)
    • 実装者は安心してコードを書け、結果的にチーム全体のベロシティが最大化したと思う
    • 手を動かさない人が最低一人いることで、チームに落ち着きが生まれた気がする
  • ベンチ中は全台ぶんの dstat/htop/アクセスログ/スローログ/アプリケーションログを眺める
    • dstat で全体的なリソースの状況をみる
    • htop で各 vCPU の利用率、メモリ、スワップ、負荷の高いプロセスをみる
      • とにかく CPU とメモリが厳しいことが一瞬でわかった
    • alpアクセスログを集計
      • どのエンドポイントが遅いのかの絞り込みに役立った
    • pt-query-digest でスローログを見る
      • 今回は MySQL がテーマだったので大活躍した
    • journalctl -f | grep -v sshd でアプリケーションなどのログを眺める
      • 今回は CentOS だったので journalctl
    • まずはサーバを役割ごとに分けてワークロードを分割し、それぞれの詳細な様子をみよう、という作戦を立てられた
    • MySQL だけに負荷がかかるはずのサーバで Plack が上がってきていておかしいとかがわかった
    • ホワイトボードの常に見えるところにサーバの構成図を描いておいたのもよかった

今後 ISUCON に参加するときにやるとよさそうなこと

  • 最初のオペレーションが一段落するタイミングで状況共有タイムを入れる
    • どういうアプリケーションなのか、データ構造はどうなっているのか
  • アクセスログをみる
    • サマった数字だけじゃなくて、生ログを見るのも大事
  • 各種ログや htop などのパフォーマンスモニタはずっと見えるところに出しておく
    • ベンチ中のシステムの挙動をいろんな側面から見られるように
  • MySQL の general log をみる
    • なんかいい感じに集計したい
  • エンドポイントのルーティングのところにコメントを書く
    • なにをするエンドポイントなのか、注目ポイントなど
  • 処理系のメモリの状態を見られるようにしたい
    • Perl だと難しそう
  • Kibana を使ってアクセスログを見られるようにしてみたい
    • いい感じの ISUCON 専用ダッシュボード作ってみたい

最後に

素晴らしい問題と環境、そして手厚いサポート体制を用意してくださった ISUCON8 運営の方々に感謝いたします。ありがとうございました。 本戦でもよろしくお願いいたします!