読者です 読者をやめる 読者になる 読者になる

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

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

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

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

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

15721.courses.cs.cmu.edu

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

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

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

さらにページを良く見てみると結構いろいろな講義が上がっているようです。 今回紹介する、Database 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より大幅に少ないコア数だと普通に成立したりする気がするのでその辺は注意が必要ですね。

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