giantneco’s blog

技術メモ

ScalaMatsuri 2018 に参加してきた (2日目)

今年で参加4回目のイベント。 それほど Scala は書いていないが、関数型言語、DDDあたりの話を聞きに行っている。

今回は 3 日間の開催で、1 日目はトレーニングデー、2 日目は普通のセッション形式、3 日目はアンカンファレンス形式になっている。 1 日目は不参加(あるのに気付いてなかった)で 2, 3 日目に参加した。

以下は 2 日目のメモ、ただし後から調べたこともちょっと入っている。

Why Composability matters @gakuzzzz

http://gakuzzzz.github.io/slides/why_composability_matters/

Scala と他の言語を分けるのは Composability。 Composability は同じ概念の異なる要素を特定の方法で組み合わせて同一概念の別要素を作ること

このセッションでの定義として、「Composability が高い」という場合は合成する手段が多いということを指す。

では、なぜ「Composability が高い」と嬉しいかというと、分割統治をするのに複数の手段があるということになるから。

Functional Performance @mjpt777 Martin Thompson

関数型言語の向けのパフォーマンスの話。とはあったが関数型言語でなくても通じる話だと思う。 メモリあたりの低レイヤの話から、関数型言語向けのデータ構造の話まで出てくる。

資料に出ていた Unified Reservation Station が気になって調べたが、これは命令のアウトオブオーダー実行のための仕組みで、キューに溜まった命令に対して必要なオペランドが揃ったら実行される。 1GB の long 配列の和を Haswell 上で計算する例に出されているが、 周波数を3GHzとして、1サイクルは0.3 nsで、マニュアルをみると 256bit のロード・ストアは 1 サイクルで済むように書いてあるので、 うまくキャッシュに乗っていればベンチマーク結果にある 0.83 ns/op というのもすごく有り得そうな数字に見えてくる。

パフォーマンスのための式としてM/D/1の待ち行列式と、Universal Scalability Law が紹介されている。

M/D/1 の待ち行列{ \displaystyle
\begin{align}
r = \frac{s(2 - \rho)}{2(1-\rho)}
\end{align}
}

USL { \displaystyle
\begin{align}
C(N) = N/1 + \alpha (N - 1) + \beta N (N - 1)
\end{align}
} 個人的にはアムダールの法則をよく使うが、コヒーレンシを考える必要がある場合はこっちのほうが適当か。

CRDTs

モダンな分散環境ではメッセージのやり取りに TCP より UDP の方が向いている。 ただし UDP によるメッセージングだと順序の保証がないので、データ構造も良く考える必要がある 関数型言語が使うデータ構造だと skip list, tree, scoreboard があるが、実装としてはポインタの参照地獄になってしまう。 Immutability のため、また Concurrent Tree Update をしようとすると Path Copy をすることになってパフォーマンスが問題になる。またガベージコレクションも大変になる。

そこで CRDTs = Conflict-Free Replicated Data Type

CRDTs は時間効率、空間効率ともによいデータ構造 CRDTs には 2 種類あり、オペレーションをコピーする CmRDT = Commputative Replicated Data Types とステートをコピーする CvRDT = Convergent Replicated Data Types

CmRDT * オペレーションを複製 * オペレーションは可換 * オペレーションはべき等でない

CvRDT * ステートを複製 * ステートアップデートは単純増加 * つまり追記のみで、削除には特別な操作が必要 * マージ処理は結合的,可換,べき等

Aeron の Log Buffer が上記の CRDT になっているらしく、オペレーションが中断した場合なども

Publishers, Senders, Receivers, Subscribers が単調増加だけするカウンタを持っていてる。 ステートを持つのは悪かもしれないが、単調増加だけする場合は許容できる。

Monad Transformaers Down to Earth , Gabriele Petronella

モナド変換子の話。モナド変換子自体は前から知っていたが説明が抜群にうまかった。見習いたい。

型クラスが入れ子になっているときは Monad の flatmap を使う。

flatpmap: F[F[A]] -> F[A]

なら異なる型クラスで包まれていたら?モナド同士は合成できないので困ったことになる。

F[G[A]]

こういう場合に使うのがモナド変換子で、合成の代わりに変換をする。

F[G[A]] -> GT[F[_], A]

モナド変換子はモナド名+Tという名前にする(Option モナドならモナド変換子は OptionTになる)

実用的な圏論入門 @DanielaSfregola

圏論のハンズオン。途中から別のセッションを聞きに行った。 かなり初心者向けで、手を動かしながら聞けるのでわかりやすい。

Building Distributed System with Akka @anildigital , Anil Wadghule

分散システムと Akka の話。

  • 背景
    • size of internet growing
    • concurrent connections, big data, respoinse time
    • high require
    • reactive prinsiples
  • Distrubuited system をスケールさせるには
    • 読み込みの複製
      • 複雑、一貫性に問題
    • シャーディング
      • これも複雑、データモデルに制限
    • Consistent Hasing
  • CAP 定理
  • Distributed computation strategy
    • fault tolerant system
    • Resilence
  • Akka
    • Actor model on JVM
    • 方針として「Let it crash」
      • Normal flow and Fault recovery flow

Scalaらしいオブジェクト指向プログラミング @tototoshi

Scala でのオブジェクト指向プログラミング Tips。 Scala には合成の方法が複数があるが、それぞれ長所・短所がある。

ScalaJava に対して Immutability と Composability へのサポートが多くて、 Case クラスや、 trait を使える。

  • Case Class
    • 代数的データ型として使える
  • trait
    • Java の interface に相当。 mixin や cake pattern に使える
  • object

DI についても Scala では次のような手法がある * コンストラクタインジェクション * コンストラクタで渡すパターン * Cake Pattern * with句でtraitを渡していくパターン * 関数型プログラミングスタイルなら Reader Monad, Free Monad + tagless final

Extensible Effects in Dotty @halcat0x15a

Dottyの新機能と、Dotty で使えるようになる Extensible Effects の話。 この日のセッションのうち一番話が難しかった。 正直このあたりの話はあまり理解できているとは言いがたいので、手を動かして確認したい。

Dotty は Scala の新しいコンパイラで DOT = Dependent Objectt Types という理論に基づいている。その新機能のひとつに Extensible Effects で使う Open Union がある。

Extensible Effects は複数の操作?を効率的に合成してくれるもので、モナド変換子をネストして使った場合にパフォーマンスが落ちる問題を解決してくれる。

この Extensible Effects に至るまでの話が複雑で、まず Free Monad が出てくる。 Free Monad は Functor を Monad にしてくれるが、Functor にしか適用できない。 これに対して Coyoneda を使って Functor 以外にも適用できるようにしたのが Freer Monad。 ただし Freer Monad は flatMap を複数回適用するため重いという問題がある。 これを解決するために Type-Aligned Queue というものを使って、 早くしたのが Fast Freer Monad。 で、Open Union に Fast Freer Monad を適用したものが Extensible Effects であるらしい。

話の流れだけはなんとなく把握したが、実際どういうことをしているのかがわかっていない。