カーネギーメロンのDBに関する講義が面白いのでおすすめ

ここに書くことによって途中でやめられなくするメソッドです。

ハッカーニュースを眺めていたら以下のようなCS系講義動画のまとめリポジトリが流れていました。

GitHub - Developer-Y/cs-video-courses: List of Computer Science courses with video lectures.

へーっと思いながら何個かポチってみたところ以下に出くわしました。

15721.courses.cs.cmu.edu

英語が（自分にとって）聞き取りやすく、動画の品質（画質やスライドがちゃんと見えるかどうかといった部分）も良いものでかつ興味のある内容で出来ればスライドもおしゃれで・・・となるとなかなか少ないですが、これはかなり見やすいです。 スライドも概念図が頻繁に登場したりして、これだけでも聞き取れなかった部分などをかなり補完できます。

スケジュールページのVideoアイコンからページに飛んでもらえるとわかるのですが、スライドごとに動画を飛ばしたり戻したりできるのでわからなかったところはもう一回、この辺はわかるから２スライド分とばすみたいなことがやりやすいです。

http://cmudb.io/15721-s16-lect01

さらにページを良く見てみると結構いろいろな講義が上がっているようです。 今回紹介する、Database Systems 以外にも

• Seven Databases in Seven Weeks
• Parallel Computer Architecture and Programming
• Great Theoretical Ideas in Computer Science
• Introduction to Computer Systems

など色々あります。

特にSeven Databases in Seven WeeksはMemSQL, Microsoft(Hekaton), NuoDB, MongoDB, Tokutek, VoltDBのCTOやリードエンジニアが一回ずつそれぞれのDBについて紹介してくれるという非常に豪華な内容になっています。

どんな講義？

さてDatabase Systemsの話にもどります。

この講義ではsingle nodeのin-memory databaseの内部アーキテクチャについて扱います。（分散DBについては対象外） classicalなDBMSについては扱わずstate-of-the-artなトピックについて扱うとのことです。（classicalなやつが軽視されているわけではなく、別の講義などで学習済みであることを想定しているっぽいです。）

具体的には、以下のようなトピックがあります。

• Concurrency Control
• Indexing
• Storage Models, Compression
• Join Algorithms
• Logging & Recovery Methods
• Query Optimization, Execution, Compilation
• New Storage Hardware

より詳細には以下にまとまっています。 Schedule - CMU 15-721 :: Database Systems (Spring 2016)

内容としてはin-memory DBって既存のDBにキャッシュを詰みまくるのとどう違うの？という疑問に直球で答えを返せるようなイメージでしょうか。 ディスク中心のDBでは如何にディスク I/Oを避けるかが主要な関心事になっていますが、in-memoryではデータアクセスコストが（ディスクアクセスと比べれば）かなり低くなるのでボトルネックが変化します。 既存のアーキテクチャはdisk I/Oを避けるのに特化した構成になっているため、in-memoryの速さを活かすためには新たなボトルネックに合わせたin-memoryを前提としたアーキテクチャが必要になります。 この講義では、そのようなアーキテクチャについて一つ一つ学んでいく形になります。

例えば、 ディスク指向のDBではデータアクセスの際、 ディスクアドレスを計算 => buffer pool managerにキャッシュがメモリにあるか問い合わせる 、といった処理が入りますが、in-memoryを前提にすればこの処理はカットできる。とかロックをかけること自体がネックになるのでCASを使ったものにしたりロックの粒度を荒くしてときにはDB全体でロックをかけるといったことも行われる。（そうすると、全体が逐次実行になる。その結果CPUキャッシュが効くようになる！すごい！）といったことなどが挙げられます。

また、この講義では指定された論文を読んでまとめを提出したりコードを書く課題などがあります。 論文リストはスケジュールに載っています。 リスト内には2015年発表のものなど、かなり新しめの論文などが含まれているため読んでいても知ってるモダンなDBの中身について書いてあったり、あるいは全く知らなかった新しいDBについて知ることが出来ます。割とこっちが面白いというか、最近のとりあえずこれ抑えようリストが上がっているのは非常に助かっています。

で、どうなの？

こういう意識高いやつ何回か挑戦しつつ結局二回目くらいまで聞いて挫折しているんですが、現在のところ5回目くらいまで聞けているので結構良いんじゃないかと思っています。 どちらかというと動画を見るよりかは論文を読むのを中心に進めています。

読んだものを簡単に紹介します。（内容のサマリというよりかは、メモ書きに近いです）

M. Stonebraker, et al., What Goes Around Comes Around, in Readings in Database Systems, 4th Edition, 2006 (Optional)

データモデリングについての35年分の歴史を辿り、そこから得られる教訓についてまとめた論文。IMS => CODASYL => Relational => ...と進んでいく中で何を学んだのか？これから同じ失敗や議論を繰り返さないためにはどうすればよいか？について書いてあります。（その分野の巨人が動かないと結局流行らないよね。とか、改良があったとしても移行する動機が薄いと普及しないよね。みたいな技術的なところ以外（そこも含めて技術？）の要因についても背景をしっかりおさえて書いてあります。

A. Pavlo, et al., What's New with NewSQL?, 2015 (Optional)

NewSQLという分野（ACID特性を諦めないでNoSQLのようなスケーラビリティを目指すDBMS）についてのまとめです。スケーラビリティを求めてEventual Consistencyでも動くコードをアプリケーションで頑張って書かなくてもDBがやってくれる方が生産性が良いってGoogle Spannerの著者も言っていたらしいです。

The authors of Spanner even remark that it is better to have their application programmers deal with performance problems due to overuse of transactions, rather than writing code to deal with the lack of transactions as one does with a NoSQL DBMS [24].

この分野ではCockroach DB, SAP HANA, VoltDBなどがありますが(本文中ではもっと紹介されています)、これらのDBがどのようなアーキテクチャになっているかそれぞれざっくり知ることが出来ます。

H. Garcia-Molina, et al., Main Memory Database Systems: An Overview, in IEEE Trans. on Knowl. and Data Eng., 1992

ディスクではなくメモリに全てのデータを格納することを前提としたDBのアーキテクチャについてまとめられています。 いい面ばかりではなく、HDDは故障しても部分的にリストアできたりできるけどメモリは全体が壊れやすい。もしハードウェアが信頼できるようになったとしてもOSが暴走したらメモリが書き換えられたりして結局DBに格納されてるデータが壊れる・・？といった懸念があるのでチェックポイント増やしたほうが良いか・・？でもそうするとチェックポイントたくさんつくるために新しくボトルネック出来てしまう・・？といった事柄についても議論されています。

上の方で書いたMMDBならロックの粒度をDB全体にしても良いっと書いてあるのはこの論文です。ロックの対象をDB全体にするとトランザクションが逐次実行になります。逐次実行になるとCPUのキャッシュが活かせる（今まではトランザクションが待ち状態になるとキャッシュが無駄になっていた）ため更に性能が見込めるかもといった内容もあり面白いです。（今までdisk I/Oと戦っていたのにいきなりCPUのキャッシュの話に・・！）

その他にもConcurreny Control, index, ロックなどあらゆる事柄の変化について解説されています。

X. Yu, et al., Staring into the Abyss: An Evaluation of Concurrency Control with One Thousand Cores, in VLDB, 2014

1000コア時代が到来した時に今のConcurrency Controlの仕組みでスケールするか検証したらダメだったので頑張ろう・・！みたいな論文。 大きく分けて2phase-commit方式とTimeStamp Ordering方式があり、それぞれの中でも異なる実装方式を比較したりしています。 コア数増えるとAtomicIntegerのCAS使うとキャッシュコヒーレンスのための命令が飛び交って遅くなってしまう。 => バッチでtimestampをまとめて発行すればいいかと思ったけど、トランザクションが失敗した時にtimestampがまとめて無効になってしまうから競合が多いと逆効果になったり。などTAoMP に書いてあるような知識が役立ちそうでした。 図10の競合が多い場合の書き込みワークロードを見るとコア数が1のときのほうがコア数500や1000のときよりスループットが高い(10万txn/s => 5万txn/sになってしまう)といったケースもあり、このようなケースでもスケールできる方式が求められていそうです。 この論文でこの方式はうまくいかないと書いてあっても現代の1000より大幅に少ないコア数だと普通に成立したりする気がするのでその辺は注意が必要ですね。

ということで割りとなんとなくですが、学んでいますという紹介というか勉強ログ的な記事でした。

(ansible 2.1までは）ansible_managedを使うと毎回changed扱いになる可能性がある

以下の話題はansible 2.2以降では修正されています。 https://github.com/ansible/ansible/pull/18094

ansible_managed

ansibleのtemplate内で {{ ansible_managed }} とすると Ansible managed: {file} modified on %Y-%m-%d %H:%M:%S by {uid} on {host}的なおしゃれな文言を埋めてくれる機能があります。ファイルの先頭にコメントとして付けておくと既にansibleで管理されているファイルなのか、元から入っているファイルなのかわかりやすくなる効果があります。*1

ところがデフォルトで入っているこのdatetimeの部分が曲者で、ファイルの内容が変わったかどうかをチェックしていたりはせず単にファイルの修正時刻をフォーマットするだけなので、git checkoutやcloneなどの操作で容易に内容が変わってしまいます。もちろんconfファイルがchangedになるとhandlerが呼ばれてサーバーがリスタートされたりするわけでansibleの実行に無駄に時間がかかってしまいます。

http://docs.ansible.com/ansible/intro_configuration.html#ansible-managed をよく見ると書いてあることなんですが、知らなくて毎回changedになっているところがありました( ◜◡‾)

ansible.cfgの[default]にansible_managed = Ansible managed のような静的な文字列を設定すればこの問題を回避できます。

設定例

[defaults]
ansible_managed = Ansible managed file, do not edit directly

この件について調べてみると以下のissue & PRで修正済みでした。(2.2には既にこの修正が入っています）

• https://github.com/ansible/ansible/issues/17947
• https://github.com/ansible/ansible/pull/18094

議論によるとdatetime以外のuidやhostも実行環境によって変わってしまうから除去したとのことでした。とはいえ2.2以降でさらに変わるかもしれないオーラがありそうです。

ansible 2.2にあげたいという気持ちが高まるという点ではansible_managedはおすすめ機能かもしれません！（？）

*1:自分の環境だとサーバーに潜ってファイルいじったりとかはしないので気休め程度ですが、一部だけ管理抜けてる・・？みたいなことに気づきやすくなるメリットがあります。（一行目にansible_managedが入っていることを仕組み的に強制できたりはしないので、結局安心できるものではないんですが・・）

akka FSMでstateTimeoutが一度メッセージを受け取らないとスケジュールされないときはinitializeの呼び忘れかも

結論

initialize() https://github.com/akka/akka/blob/v2.4.13/akka-actor/src/main/scala/akka/actor/FSM.scala#L511-L522 をFSMのコンストラクタの最後(または適切なライフサイクルメソッド内)で呼びましょう。

ActorのreceiveTimeout

akka actorにはreceiveTimeoutという一定時間メッセージが来なかったらReceiveTimeoutメッセージを送るという便利機能があります。 これを使うと、返信が一定時間なかったらもう一度メッセージを送るといったリトライ処理が書けるようになります。

http://doc.akka.io/docs/akka/2.4/scala/actors.html#Receive_timeout

class FooActor extends Actor {
  context.setReceiveTimeout(2.seconds)

  def receive = {
    case ReceiveTimeout =>
      println("timeout")
      context.setReceiveTimeout(Duration.Undefined) // Undefinedにすると解除できる
    case x => println(x)
  }
}

FSMのstateTimeout

そしてFSMにはstateTimeoutという、その状態になってから一定時間メッセージが来なかったらタイムアウトする機能があります。

object FsmMain extends App {
  val system = ActorSystem("MyActorSystem")
  val bar = system.actorOf(Props[Bar])
}

// `initialize()`を呼び忘れているのでこのままでは動かない（後述）
class Bar extends FSM[Int, Unit] {
  startWith(0, (), timeout = Some(2.seconds)) // whenで指定したtimeoutを上書きできる

  when(0, stateTimeout = 3.seconds) {
    case Event(StateTimeout, _) =>
      println("timeout")
      stay()
    case Event(x, _) =>
      println(x)
      stay() forMax(4.seconds) // whenで指定したtimeoutを上書きできる
  }
}

また、stateTimeoutの値は when で登録する以外にも startWithの引数で startWith(state, data, timeout = Some(2.seconds)としたり、状態遷移で goto(...) forMax(3.seconds) のようにforMaxを指定することで上書きすることができます。 この機能により「リクエストを送り、最大３秒間Response待ち状態になる。タイムアウトしたらリトライを行うかリクエストに対してエラーを返す」といった処理が書きやすくなります。

なお、FSM自体もActorなので引き続き前述のsetReceiveTimeoutを利用することが出来ます。 その場合はwhenの中に case Event(ReceiveTimeout, _) => を記述すれば取得することが出来ます。（個人的には一緒に使うとややこしいことになりそうなのでやめておきたい気持ちがあるような・・・）

FSM stateTimeoutのtimer起動のタイミング

で、この機能を使うかーと思いTimeoutメッセージが届くか実際に実験をすると、FSM作成直後や再起動直後にtimerが作動しておらず、timeoutメッセージが届かない症状に出くわしました。 例えば一つ上のFsmMainとBarの例を実行すると、永久に println("timeout") を通過することはありません。この状態でstateTimeoutさせるためには一つ以上のメッセージを送る必要がありました。

timeoutのスケジュールはreceiveの中で呼ばれるmakeTransitionの中 https://github.com/akka/akka/blob/v2.4.13/akka-actor/src/main/scala/akka/actor/FSM.scala#L699-L705 で行われています。 ということは初回はmakeTransitionが呼ばれないのか・・？おかしいなー、おかしいなー、と思ったのですが、よくよく考えるとFSMのコンストラクタでinitialize()を呼び忘れていました 😨

initialize() は https://github.com/akka/akka/blob/v2.4.13/akka-actor/src/main/scala/akka/actor/FSM.scala#L511-L522 で定義されています。実装的にはほとんど makeTransitionを呼び出すだけです。 ドキュメント http://doc.akka.io/docs/akka/2.4/scala/fsm.html#A_Simple_Example にも以下のようにしっかり書いてあります。

finally starting it up using initialize, which performs the transition into the initial state and sets up timers (if required).

これを呼び出すとしっかりとtimeoutされだすようになりました。

// 修正版
class Bar extends FSM[Int, Unit] {
  startWith(0, (), timeout = Some(2.seconds))

  when(0, stateTimeout = 3.seconds) {
    case Event(StateTimeout, _) =>
      println("timeout")
      stay()
    case Event(x, _) =>
      println(x)
      stay() forMax(4.seconds)
  }

  initialize()
}

めでたしめでたし。

FSMだと状態がwhenで初めて登録されるので、登録されるまでmakeTransitionできないためこのような仕様になっている・・んでしょうか？ initialize()は忘れていても気づきにくい（特に最初はタイムアウト使って無くて後から入れる場合など）ので影響がありそうなら気をつけましょう(´･_･`)

OpenStackのUbuntuでdocker使ったらコンテナからのcurlがハングする件

dockerコンテナ上で何故かcurlが上手くつながらない問題にハマったのでメモするシリーズ。

環境

• Ubuntu 14.04.5 LTS ( on OpenStack)
• Docker version 1.11.2, build b9f10c9

症状

ホストで curl https://github.com は正常にレスポンスを受け取れるのにもかかわらず、コンテナ上で同じことを行うとレスポンスが帰ってこない(ハングする)。また極稀にレスポンスが中途半端に返ってくることがある。

原因

コンテナのMTUの値がホストのeth0と合っていなかった。( ip addr などで確認）

（暫定的な）対処法

DOCKER_OPTSに --mtu 1400 など(数字はeth0のMTUと合わせる)を加えてdockerを再起動する。

背景とか

調べてみると何個かこういう報告がありました。

• docker 1.10, 1.11 do not infer MTU from eth0; docker 1.9 does · Issue #22028 · docker/docker · GitHub
• containers in docker 1.11 does not get same MTU as host · Issue #22297 · docker/docker · GitHub

don't try to use default route MTU as container MTU by phemmer · Pull Request #18108 · docker/docker · GitHub というPRがあり、docker v1.10からはdefault route(今回はeth0)からMTUを取得するのを止めたようです。

とはいえ--mtuでMTUを固定するのはハックで、本来はPMTU discoveryを正しく設定すべきらしいです。ちゃんと設定している人がどのくらいいるのかは不明です。 https://github.com/docker/docker/issues/22297#issuecomment-214570420

ProtocolBuffersでprimitiveのデフォルト値と値が入っていないことを区別したいときにどう書くか

結論

wrappers.protoが便利

背景

protobufでは値を省略したときに、その型で定められたデフォルト値が代入されます。 例えばstringを省略すると自動的に""を指定したことになり、「値が指定されなかった」のか「空文字列を明示的に入れた」のかを区別しないように書くことが求められます。

この仕様は便利なのですが、時には区別したいケースもあります。 このとき下の方式2, 3のようなテクニックを用いて未指定とデフォルト値を区別することができます。

message Example {
    // 1. ダイレクトに定義(デフォルト値と未指定を区別できない)
    string foo = 1;

    // 2. 専用のmessageを定義
    message Bar {
        string value = 1;
    }
    Bar bar = 2;

    // 3. oneofで定義
    oneof baz_option {
        string baz = 3;
    }
}

2のmessageをがんばって定義する形式は、パラメータが増えるとどんどんmessageが増えて辛くなってしまいます。 3は少しトリッキーなのがネックです。（また値の有無を switch-case か if (getBazOptionCase == BAZ) のように確認することになるため若干記述量も増します。）

wrappers.proto

と思ったらprimitive値をラップするものが公式で存在しました。

https://github.com/google/protobuf/blob/v3.1.0/src/google/protobuf/wrappers.proto#L31-L34

// Wrappers for primitive (non-message) types. These types are useful // for embedding primitives in the google.protobuf.Any type and for places // where we need to distinguish between the absence of a primitive // typed field and its default value.

とあり、まさに値がない事とデフォルト値を指定されたことを区別することができます。（Anyに値を突っ込むのにも使えるようです。）

これはmessageを都度定義する方式をただ汎用化したものかと思っていたのですが、仕様上で特別扱いされ、 Jsonにマッピングした際にラップを無視して単に1.0や"str"のようなプリミティブな値として表現されるようです。 https://github.com/google/protobuf/blob/v3.1.0/src/google/protobuf/wrappers.proto#L50

都度メッセージを定義してしまうと "nyan": { "value": "str" } のような冗長なJsonになってしまうので、これを回避できるのは便利そうです。

仕様にもひっそりと Wrapper types という表現で特別扱いされていました。 protocol buffers - JSON MAPPING

Wrappers use the same representation in JSON as the wrapped primitive type, except that null is allowed and preserved during data conversion and transfer.

実際に動かしてみると以下のようになります。（コードは https://github.com/matsu-chara/proto_wrap にあります)

syntax = "proto3";

package example;

import "google/protobuf/wrappers.proto";

message Example {
    // 1. ダイレクトに定義(デフォルト値と未指定を区別できない)
    string foo = 1;

    // 2. 専用のmessageを定義
    message Bar {
        string value = 1;
    }
    Bar bar = 2;

    // 3. oneofで定義
    oneof baz_option {
        string baz = 3;
    }

    // 4. wrapperで定義
    google.protobuf.StringValue mofu = 4;
}

import com.google.protobuf.InvalidProtocolBufferException;
import com.google.protobuf.StringValue;
import com.google.protobuf.util.JsonFormat;
import example.Mofu.Example;

public class Main {
    public static void main(String[] args) throws InvalidProtocolBufferException {
        Example ex = Example.newBuilder()
                .setFoo("foo")
                .setBar(Example.Bar.newBuilder().setValue("bar"))
                .setBaz("baz")
                .setMofu(StringValue.newBuilder().setValue("mofu"))
                .build();

        System.out.println("instance.toString");
        System.out.println(ex.toString());
        System.out.println("json");
        System.out.println(JsonFormat.printer().print(ex));
        System.out.printf("");

        Example empty = Example.getDefaultInstance();
        // foo == ""
        System.out.println("foo isEmpty: " + empty.getFoo().isEmpty());

        // bar == null (getBar returns defaultBar if bar == null)
        System.out.println("hasBar: " + empty.hasBar());
        System.out.println("bar isEmpty: " + empty.getBar().getValue().isEmpty());

        // baz ==  BAZOPTION_NOT_SET (getBaz returns "" if BazOptionCase != Baz)
        System.out.println("bazOptionCase: " + empty.getBazOptionCase());
        System.out.println("baz isEmpty: " + empty.getBaz().isEmpty());

        // mofu == null (getMofu returns defaultMofu if mofu == null)
        System.out.println("mofu hasMofu: " + empty.hasMofu());
        System.out.println("mofu isEmpty: " + empty.getMofu().getValue().isEmpty());
    }
}

instance.toString
instance.toString
foo: "foo"
bar {
  value: "bar"
}
baz: "baz"
mofu {
  value: "mofu"
}

json
{
  "foo": "foo",
  "bar": {
    "value": "bar"
  },
  "baz": "baz",
  "mofu": "mofu"
}
foo isEmpty: true
hasBar: false
bar isEmpty: true
bazOptionCase: BAZOPTION_NOT_SET
baz isEmpty: true
mofu hasMofu: false
mofu isEmpty: true

jsonの出力ではStringWrapperにあたる部分が簡略化されていることが分かります。
emptyの取得ではhasMofuやoneofといったテクニックで値が無いことが確認できます。

このようにWrapper typesを使えば未指定とデフォルト値を区別することが簡単にできて、なおかつjson変換の際に冗長さを減らすことができます。 もちろんフィールドが増えたり使いまわされたりするならmessageを定義するのが良いこともあるので、適切に使い分ける必要があるとは思いますが、単純にwrapしたいだけであれば選択肢に入ると思います。

ただし不用意にラップすると（クラスが増えるので）ビルド時間が増えたりするといったデメリットがあったりしますし、そもそものprotobufの設計思想から若干それているような気がしなくもないので第一選択肢としてはデフォルト値を利用する戦略を取るのが望ましい気がします。