あどけない話

インターネットに関する技術的な話など

Implementing graceful-close in Haskell network library

Closing connections gracefully is an old and new problem in network programming. In the HTTP/1.1 days, this did not get attention since HTTP/1.1 is a synchronous protocol. However, as Niklas Hambüchen concretely and completely explained, HTTP/2 servers should close connections gracefully. This is because HTTP/2 is an asynchronous protocol.

Unfortunately, most HTTP/2 server implementations do not close connections gracefully, hence browsers cannot display pages correctly in some situations. The first half of this article explains the problem and its solution step by step in general. The second half talks about how to implement graceful-close in Haskell network library.

Normal cases of HTTP/1.1

Roughly speaking, synchronous HTTP/1.1 can be implemented as follows:

  • Browser: the loop of writing request and reading response
  • Server: the loop of reading request and writing response

Since HTTP/1.1 uses persistent connections by default, a browser should set the Connection: close header to close the current connection.

When the server received the Connection: close header, it closes the connection by close() after sending its response. Of course, the browser knows that the connection is being closed. So, the browser reads the response until read() returns 0, which means EOF. Then, the browser closes the connection by close().

Error cases of HTTP/1.1

For security reasons, HTTP/1.1 servers close connections. The followings are typical situations:

  • Idle timer is expired
  • The number of requests reaches the limitation

In these cases, an HTTP/1.1. server calls close() resulting in generating TCP FIN.

When the browser tries to write the next request to the same connection, it would be nice to see if the connection is alive. Are there any system calls to check it? If my understanding is correct, there is no such system calls without IO. What the browser can do is just read or write the connection optimistically if it wants to reuse the connection.

The case of TCP FIN

So, what happens if the browser reads or writes the connection which has already received TCP FIN?

write() succeeds. However,since the server socket is already closed, the TCP layer of the browser received TCP FIN, which is not informed to the browser.

read() return 0, EOF, of course.

The case of TCP RST

Another intersecting question is what happens if the browser reads or writes the connection which has already received TCP RST?

write() causes SIGPIPE. If its signal handler ignores it, write() is resumed and returns EPIPE.

read() returns ECONNREST.

Recovering in HTTP/1.1

Suppose that an HTTP/1.1 server closed a connection by close() but the browser tries to send one more request. When the TCP layer of the server received the request, it sends TCP RST back to the browser. The browser tries to read the corresponding response and notices that the server resets the connection. So, the browser can make another new connection and re-send the request to the server.

In this way, recovering in HTTP/1.1 is not so difficult.

Normal cases of HTTP/2

HTTP/2 uses only one TCP connection between a browser and a server. Since HTTP/2 is asynchronous, the browser can send requests at anytime. The server can send back responses in any order. To combine a request and its corresponding response, a unique stream ID is given to the pair. In the following figure, the order of response 1 and response 2 is flipped.

To close the connection, the browser should send GOAWAY. When the HTTP/2 server received GOAWAY, the server should send back GOAWAY. Typical implementations call close() after that.

Error cases of HTTP/2

For security reasons, an HTTP/2 server itself closes a connection by sending GOAWAY. Again, typical implementations call close() after that.

It is likely that the browser sent a request asynchronously and the request reaches to the server after the socket is gone. In this case, as explained earlier, TCP RST is sent back to the browser.

Unfortunately, the TCP RST drops all data to be read in the TCP layer of the browser. This means that when the browser tries to read its response, only ECONNREST is returned. GOAWAY disappears.

GOAWAY contains the last stream ID which the server actually processed. Without receiving GOAWAY, the browser cannot tell the recovering point. In other words, the browser cannot render the target page correctly. This problem actually happens in the real world. And most HTTP/2 server implementations have this problem.

Graceful close

So, what is a solution? The masterpiece book, "UNIX Network Programming Volume 1: The Sockets Networking API (3rd Edition)", W. Richard Stevens et al. suggests the following way.

  • The server should call shutdown(SHUT_WR) to close the sending side but keep the receiving side open. Even if requests reach to the server after shutdown(), TCP RST is not generated.
  • The browser can read GOAWAY in this scenario and send back GOAWAY followed by close().
  • The server should read data until read() returns 0, EOF.
  • The server finally should call close() to deallocate the socket resource.

It is not guaranteed that the browser sends back TCP FIN. So, the server should set time out to read(). One approach is the SO_RCVTIMEO socket option.

Implementations in Haskell

From here, I would like to explain how to implement graceful-close in Haskell network library.

Approach 1: the SO_RCVTIMEO socket option

After reading "UNIX Network Programming", I started with the C-language way but many features are missing in the network library.

  1. To time out reading, SO_RCVTIMEO should be supported in setSocketOption.
  2. Since SO_RCVTIMEO is effective only for blocking sockets, a function to set a non-blocking socket back to blocking is necessary.
  3. Receiving data from blocking sockets without triggering the IO manager is also needed.

I confirmed that this actually works but threw this away. To not block RTS by calling the receiving function of 3, the function should be called via safe FFI. This means that an additional native (OS) thread is consumed. Closing connections should not be that costly. All in all, blocking sockets are not the Haskell way!

Approach 2: the timeout function

Of course, a very easy way is combine the timeout function and the original recv function which may trigger the IO manager. This actually works. But again I threw this away since an additional lightweight thread is consumed in timeout.

Approach 3: the threadDelay function

I finally hit upon the idea of threadDelay. For this approach, a new receiving function is necessary. It uses non-blocking socket and does not trigger the IO manager. The algorithm is as follows:

  • loop until the time out is expired
    • reading data
    • if it returns EAGAIN, call threadDelay with a small delay value. If it returns data, breaks the loop.

The advantage of this approach is availability. This works on all platforms with both threaded and non-threaded RTS. The disadvantage is that the timing of timeout would be inaccurate.

Approach 4: callbacks of the IO/Timer manager

Michael Snoyman suggested to use a pair of callbacks for the IO and Timer managers. First, an MVar is prepared. Then the main code sets a callback to the IO manager asking to put data to the MVar when available. At the same time, the main code also sets a callback to the Timer manager asking to put a time-out signal to the MVar when the timeout is expired. The two callbacks race and the main code will accept the result of the race through the MVar.

This idea is awesome because no resource is wasted. What I was impressed is that he knows the IO/Timer managers better than me, who is one of the developers of the mangers!

Final remark

The Haskell network library version 3.1.1.0 will provide gracefulClose. For threaded-RTS on UNIX where the IO manager is available, approach 4 is taken. For Windows or non-threaded-RTS where the IO manager is not available, approach 3 is taken.

My deep thank goes to Niklas Hambüchen for pointing out this problem, discussing solutions patiently and reviewing my implementations thoroughly. I would like to thank Tamar Christina for helping the development on Windows and Michael Snoyman for suggesting approach 4.

プログラミングHaskell第2版の補足

適宜更新します。

実用的でない例題

「他の言語だと雑多になるけど、Haskellではこんなに優雅なコードになる」という例は大抵実用的ではありません。本書では、以下の例題がそれに当てはまります。

実用的なコードを知りたいなら「Haskellの神話」を読んでください。

紹介されてないデータ型

実用的なプログラムを書く際には String ではなく Text を使います。textパッケージの Data.Text モジュールで定義されています。Text はリストではありませんので、リストプログラミングでは扱えません。専用の API を使って操作します。

非負の整数を表すデータ型は Word です。Data.Wordモジュールで定義されています。8.3節の例は、Wordを使えば安全に定義できます。

newtype Nat = N Word

ちなみに、大きさが決まっている Word8Word16Word32 および Word64 も提供されています。Int も同様です。

なお、IntWordにビット操作をしたい場合は、Data.Bitsを利用します。

newtype

8.4節に、newtype でも再帰型が定義できると書いてありますが、例が載っていません。構成子が一個しかないのに、どうやって再帰するのでしょうか? 8.1節に、以下のようなわざと間違った例があります。

type Tree = (Int,[Tree])

これは newtype を使うと、正しいコードになります。

newtype Tree = Node (Int,[Tree])

一般化してみましょう。

newtype Tree a = Node (a,[Tree a])

組み合わせ関数

9.4節に突然 subsinterleaves および perms が出てきます。どういう仕組みなのか知りたい方は、珠玉のリスト・プログラミングを読んでください。初版では付録で解説していましたが、第2版にはこの付録を付けていません。

プログラミングHaskell第2版を翻訳しました

プログラミングHaskell第2版の翻訳とレビューが完了し、ラムダノートから発売されました。レビューしてくださった5名の方に、改めてお礼を申し上げたいと思います。閉じられたissueは177個ですが、複数の指摘を含むissueもあるので、大雑把に言って250箇所ぐらいは改善されたのだと思います。

初版を買ってない方や、これからHaskellに入門したい人には、手放しでお勧めできます。この記事では、初版を持っているけど、第2版を買うべきか迷っている人に、どこが変わったのか説明します。

書体

コードが数学風の書体から、ブロック体になりました。Haskellに関する論文は、数学風の書体を使う伝統があって初版で採用されていましたが、これが一番不評でした。第2版では、奇を衒らわずに普通になりましたので、安心して読めると思います。

利用するシステム

利用するシステムが、HugsからGHCになりました。初版の翻訳の際にGHCに書き換えようかと迷い、思いとどまったのを後悔していましたが、これですっきりしました。

完全な例題

初版ではパーサーのコードがそのままでは動かないという大問題がありましたが、第2版ではそんなことはありません。

章末問題

章末問題が増えました。初版ですべて問題を解いた人にも、数は多くはないですが、未知の問題が追加されています。

内容

原文の目次を比べてみましょう。

第2版 初版
1 Introduction 1 Introduction
2 First steps 2 First Steps
3 Types and classes 3 Types and Classes
4 Defining functions 4 Defining Functions
5 List comprehensions 5 List Comprehensions
6 Recursive functions 6 Recursive Functions
7 Higher-order functions 7 Higher-Order Functions
8 Declaring types and classes 10 Declaring Types and Classes
9 The countdown problem 11 The Countdown Problem
10 Interactive programming 9 Interactive Programs
11 Unbeatble tic-tac-toe
12 Monads and more
13 Monadic parsing 8 Functional Parsers + 9 Calc
14 Foldables and friends
15 Lazy evaluation 12 Lazy Evaluation
16 Reasoning about programs 13 Reasoning About Programs
17 Calculating compilers
  • 8章以降の構成が大幅に変わっています。パーサーの前にMoandを説明するので、パーサーのコードがそのまま動きます。
  • 章が4つ追加されています。MonadとFoldableには最新の状況が反映されています。詳しくは、訳者前書きを読んでください。

まとめ

前半はGHCに鞍替えしたことなどから差分が多く、後半は差分さえ取れないぐらい変わっています。

HTTP/2 server library in Haskell

I'm trying to develop QUIC in Haskell. In short, QUIC is a fast and reliable transport protocol based on UDP. You can think of it as TCP2. HTTP/2 over QUIC is now called HTTP/3.

Two level dispatchings are necessary for QUIC:

  1. Dispatching QUIC packets to connections
  2. Dispatching QUIC streams in a connection to something (perhaps to lightweight thread workers)

OS kernels are taking care of the first dispatching for TCP. But we have to implement it in a user land for QUIC. I believe that its implementation in Haskell is not so difficult.

But the second dispatching is tough. As I described in Experience Report: Developing High Performance HTTP/2 Server in Haskell and Supporting HTTP/2, I mapped an HTTP/2 stream to a worker of lightweight thread. In this architecture, some other threads are involved to control workers.

Should I reinvent the similar architecture for QUIC? My brain got befuddled.

I finally reached a conclusion: my question was raised because my HTTP/2 server was hard-coded in Warp. If I can extract it as a generic library for HTTP/2 servers, I will be able to reuse it for HTTTP/3.

It took much time but the result is promising. The APIs is so beautiful and functional. This APIs even enable to calculate a checksum in a trailer for streaming response body.

I have already released the http2 library version 2.0.0 with Network.HTTP2.Server module. Warp will switch from the original implementation to this server library soon.

The APIs are inspired by WAI but are independent from it. I hope that other HTTP engines can adopt the HTTP/2 server library easily.

実践的な Haskell debugging

私的なメモ。GHCを生でインストールし、cabalのラッパーであるcabを使っている。stackはたまに使うことがある程度。

例外が起きた場所を探す

以下で例外が起きたときにスタックトレースが取れる。

% prog +RTS -xc

GHCiを使う方法もある。

ボトルネックを探す

以下で、プログラムの終了時にプロファイルが取れる。サーバの場合は、横から停止すればプロファイルが作られる。

% prog +RTS -p
% cat prog.prof

スペースリークを探す

以下で、prog.hp というファイルが作られ、ヒーププロファイルが格納される。このファイルは、プログラムが実装されている間中育っていく。プログラムを終了する必要はない。サーバの実働中もヒーププロファイルが見れるので、監視に便利。

% prog +RTS -h -L50

注意:以前の定番である -hT は、最近使えないようだ。

描画するには、macOSだと以下のようにする。

% hp2ps -c prog.hp; open prog.ps

PINNED が多ければ、 ByteString がリークしている。

ストーリー1:プロファイル機能付きのプログラムを作成する

% mkdir profile
% cd profile
% cab init
% cab install -e -p prog
% .cabal-sandbox/bin/prog +RTS -h

ストーリー2:パッケージのテストで例外が起きた場所を見付ける

% cd package
% cab init
% cab install -d -p -t
% cab conf -e -p -t
% cab build
% ./dist/build/test/test +RTS -xc

備考

手元のライブラリを利用する場合は、cab init した後に cab add package するとよい。パッケージ名とディレクトリ名が異なっていても、ちゃんと認識される。

Bringing TLS 1.3 to Haskell

Bringing TLS 1.3 to Haskell

Haskell TLS library version 1.4.1 or earlier support SSL 2.0, SSL 3.0, TLS 1.0, TLS 1.1 and TLS 1.2. Here is brief summary of their security:

  • SSL 2.0 is insecure and obsoleted by RFC 6176
  • SSL 3.0 is insecure and obsoleted by RFC 7568
  • TLS 1.0 is insecure due to lack of AEAD
  • TLS 1.1 is insecure due to lack of AEAD
  • TLS 1.2 is secure if it is used with proper parameters (using (EC)DHE and AEAD, disabling compression and renegotiation).

You may be surprised that both TLS 1.0 and TLS 1.1 are vulnerable. Actually, HTTP/2 requires TLS 1.2 with TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256 or stronger. Also, major browsers are planning to disable TLS 1.0 and 1.1 in 2020.

To make your web sites secure, you should specify good parameters to TLS 1.2. Unless you are a security expert, it would be a tough job. Any other smart solutions? Yes, here is TLS 1.3.

Standardization of TLS 1.3 was finished in August 2018 and resulted in RFC 8446. It is secure by design. It allows only (EC)DHE for key exchange and only AEAD for traffic encryption. And it also removed compression and renegotiation.

Chrome and Firefox have supported TLS 1.3 in version 70 and version 63, respectively. To know support status of other browsers, please refer to Can I use.

So, it's high time to bring TLS 1.3 to the Haskell community. We proudly announce that we have released TLS library version 1.5.0 with TLS 1.3! To use TLS 1.3 in TLS library, you should specify TLS13 to supportedVersions. For more information, please see #167 and #282.

If you are using Warp TLS, you should obtain the newest Warp TLS and build it with TLS version 1.5.0. You can check if TLS 1.3 is used with Firefox or Chrome:

  • Firefox: click the lock beside the URL bar, ">" and "More Information".
  • Chrome: use the developer tool and click "Security" tab.

Since TLS 1.3 is a completely different protocol comparing to the older versions, I needed to write a lot of code. Olivier Chéron reviewed my code carefully and thoroughly. He also brought high-quality code to support missing features. My deep thank goes to him. I thank Vincent Hanquez and Viktor Dukhovni for enhancing crytonite and improving certification handling, respectively.

Enjoy TLS 1.3 in Haskell!

関手、Applicative、Monadの法則

Monadとは、Applicativeであるデータ構造で、(>>=)演算子を提供し、それがMonad法則を満たすものである。

正確に表現するとこうなんですが、「はぁ?」っ感じですよね。「満たすべき法則」とか言われると、まったく理解できません。でも、オススメの形に持っていくための変換規則と捉えると分かりやすいのではないかというのが、この記事の主旨です。

関手

関手法則は以下の2つです:

  • 単位元id <$> x = x
  • 合成 : f <$> (g <$> x) = (f . g) <$> x

左辺が冗長な形、右辺がオススメの形です。これはいいですよね?

Applicative

Applicative法則は以下の4つです(<*>は左結合)。

  • 単位元pure id <*> x = x
  • 準同型: pure g <*> pure x = pure (g x)
  • 交換 : x <*> pure y = pure (\g -> g y) <*> x
  • 結合 : x <*> (y <*> z) = pure (.) <*> x <*> y <*> z

アプリカティブスタイルは、

pure g <*> x1 <*> x2 <*> ... <*> xn

でした(pure g <*> の部分は g <$> と書くことが多い)。Applicative法則は、アプリカティブならすべてこの形に直せることを保証する規則なのです。例として、t <*> pure s <*> (u <*> v) を変換してみましょう。

  t <*> pure s <*> (u <*> v)
(結合)
= pure (.) <*> (t <*> pure s) <*> u <*> v
(交換)
= pure (.) <*> (pure (\g -> g s) <*> t) <*> u <*> v
(結合)
= pure (.) <*> pure (.) <*> pure (\g -> g s) <*> t <*> u <*> v
(準同型)
= pure ((.)(.)) <*> pure (\g -> g s) <*> t <*> u <*> v
(準同型)
= pure ((.)(.)(\g -> g s)) <*> t <*> u <*> v

ほらね、言った通りでしょ。

Monad

Monad法則は以下の3つです(returnpure の別名):

  • 単位元return x >>= f = f x
  • 単位元mx >>= return = mx
  • 結合  : mx >>= (\x -> (f x) >>= g) = mx >>= f >>= g

二つの単位元ですが、右辺がオススメなのは分かりますよね? 右単位元は特に有用です。do の中をいろいろ書き換えていると、知らない間に、

do ...
   y <- f x
   return y

みたいな形になっていることがあります。これは冗長なので、以下のように書けということです。

do ...
   f x

結合の法則ですが、左辺は、

do y <- do x <- mx
           f x
   g y

ですから冗長ですね。一方右辺は、

do x <- mx
   do y <- f x
      g y

という意味ですが、これは平坦化できて、

do x <- mx
   y <- f x
   g y

と書けます。

すなわち、do入れ子で書かずに、平坦な形でスッキリ書いてねという意味です。

まとめ

法則は、オススメの形式が右に書かれてないことも多いので気づきにくいのですが、「オススメの形式に書き換えてよいことが保証されているよ」と理解すれば親しみ易くなりませんか?

追記

4つのApplicative法則が満たされると、 pure f <*> x = f <$> x が自動的に満たされます。

関手の単位元を示すために、f = id を代入:

  pure f <*> x
(単位元)
= pure id <*> x
= x

関手の合成を示す:

  pure f <*> (pure g <*> x)
(結合)
= pure (.) <*> pure f <*> pure g <*> x
(準同型)
= pure ((.) f) <*> pure g <*> x
(準同型)
= pure ((.) f g) <*> x
(中置表記)
= pure (f . g) <*> x

よって、2つの関手法則は満たされるので、 pure f <*> x = f <$> x です。