はじめに
gRPCの実装を読んで得た知見を複数のブログとして、まとめていく。
以下、特にことわりがなければ、gRPCとは、https://github.com/grpc/grpc-go を指すものとする。
が、基本的に他言語も同じような挙動をするのではとは思われる1。
初回はHPACKについて書く2。
HPACKは非常に小さな仕様であり、rfcも十分に読める量である（後半4割くらいは例である）
また、
https://qiita.com/0xfffffff7/items/39b944e3845ab3776b63
に非常にわかりやすくまとめてあるのでオススメである。
ここでは、それらを読んでいてもわかりづらい部分や実装をよんでなるほどと思った部分だけを書くことにする。
全体としてはまとまりがない感じであるが、rfcだけ読んで実装を読んだことない人には参考になる部分もあると思う。
動的テーブルのname/valueのエントリー
rfcちゃんとよめばわかることではあるんですが、テーブルのname/valueの扱い、indexが地味に分かりにくい。
例えば、1番最初のリクエストとして、hogeというnameでXというvalueのヘッダーを最初に送るとする。
hogeなんてものは当然静的tableに登録されていないので、hoge、Xともにリテラルでエンコードされ、動的テーブルにエントリーとして追加される。index=1始まりで動的テーブルは静的テーブルに続く。静的テーブルはエントリーは61個固定なので、index=62に(hoge、X)が登録されることになる。
その後、hogeというnameでYというvalueのヘッダーを送るとする。
nameはindex=62、valueはYとしてリテラルでエンコードされ、動的テーブルに(hoge、Y)としてindex=62に登録される。ここで重要なのは送りたいvalueYとは異なるものの、nameであるhogeは同じなのでhogeのエンコードとして、(hoge、X)のエントリーを利用し、indexでエンコードできるということである。また、「index=62に登録される」と書いたのは誤りではない。HPACKでは新しいエントリーが若い番号をもつと規定されている。
最後に、hogeというnameでXというvalueのヘッダーを送るとする。
動的テーブルに(hoge、X)がindex=63に登録されてあるので、name,valueともにindexを利用可能である。index=63がエンコードされ、リテラル表現が利用されることはない。
このあたりは実装をよんでしまったほうが言葉で説明するより早いかもしれない。
インデックス更新を伴わない(without Indexing)リテラルヘッダフィールドはいつ使うのか
ざっとrfcを読む限り、いつ使うべきか指針がない。
goの実装としては、
https://github.com/golang/net/blob/abc453219eb586afb3fc1742e8c685c28b9f7eea/http2/hpack/encode.go#L134-L136
https://github.com/golang/net/blob/abc453219eb586afb3fc1742e8c685c28b9f7eea/http2/hpack/encode.go#L227-L240
のあたりにあるが、
エントリー単体がテーブル全体のバイト合計制限より大きい場合
のみに「インデックス更新を伴わないリテラルヘッダフィールド」が利用される。そりゃあそうだろと感じで、実質このエンコードが使われることはほぼないという理解で問題ないだろう。ちなみに変更可能だが、デフォルトの上限は4096バイトである。
インデックスされない(never Indexing)リテラルヘッダフィールドはいつ使うのか
rfcに以下の記載があるようにsecurityと関連があるようだ。
Since HPACK doesn't protect against guessing an entire header field value, short or low-entropy values are more readily recovered by an adversary. Therefore, an encoder might choose not to index values with low entropy.
An encoder might also choose not to index values for header fields that are considered to be highly valuable or sensitive to recovery, such as the Cookie or Authorization header fields.
後者は、CookieやAuthorizationヘッダのようなセキュアなものを保持し続けたくないだろということで理解はできる。
前者を説明するにあたって、CRIMEに触れる。CRIMEはデータの中身が全く分からなくても圧縮対象のデータを少しずつ変化させ、圧縮率をみることでcookieなどの情報を取得する攻撃手法でTLSやSPDYの圧縮にはCRIMEに対して、脆弱性があり、現在あまり使われていない。HPACKはその解決を念頭に設計されているため、基本的には問題ないが、(少しずつではなく)ヘッダーのValue全体を推測することは依然可能である。おそらく、そのような理由からヘッダー値が短い文字や頻度が高い場合はindexを避けるべきという主張と理解した。が、実際そこまで考慮をする必要があるかは疑問ではある。
実装では、HeaderField定義にSensitiveがあるのでHPACKライブラリ利用者が指定できるようになっている。
type HeaderField struct {
Name, Value string
// Sensitive means that this header field should never be
// indexed.
Sensitive bool
}
gRPCでどのような場合に指定しているのかと調べたが、内部的に指定していることもなく、gRPC利用者が指定することもできない。
rfcの想定とは異なる気がするが、「署名のvalueなどエントリに保存する意味が全く意味がないし容量が大きい」場合にSensitiveを指定したいと思った。
例えば、リクエストに必ず、Signatureという名前でvalueにbase64(shaHMAC-SHA256(body))を指定する必要がある場合を想定する。
rfcに「エントリーのサイズはnameのバイト数+valueのバイト数+32バイト3」と規定されており、9+44+32=85バイトとなる。
デフォルトの4096バイトがテーブルの合計エントリ上限であるとすると、約50リクエストで動的テーブルがrefreshされてしまう。再利用されることはないSignatureのvalueのためにそうなるのはもったいない気がする。
と書いたところでとても気になってきたので、以下issueを投げてみた。おそらく何らかの理由があるのだろう。
https://github.com/grpc/grpc-go/issues/4520
動的テーブルは本当に常にsyncできているのか
例えばクライアントがあるヘッダを送ろうとし、動的テーブルにあると判断したindexとサーバがそのindexを元に動的テーブルから引いた値は常に必ず同じになっているのだろうかということである。
答えは当然YESなのだが、rfcだけではどのように保証しているのかわからなかった。
まず一つ目の疑問は
クライアントとサーバ両方が同時に動的テーブルにエントリーを追加したときにindexはずれないか
である。クライアントがindex=62に(hoge、X)を追加するのと同時にサーバがindex=62に(piyo、Y)を追加した場合、indexがずれそうである。
実装は読むとこの懸念は完全に見当違いであることがわかった。そもそもそれらは動的テーブルを共有していない。
以下の1,2の動的テーブルは全く別物として管理される。client/serverそれぞれに二つ動的テーブルがメモリに存在する。
- clientのencoder -> serverのdecoder
- clientのdecoder <- serverのencoder
1であれば、「clientからserverに更新がレプリケーションされる」という表現だと理解しやすいと思う。
clientがencodeする状況を今後想定する。
二つ目の疑問は
clientがencode後serverがdecodeするまでに何らかのエラーが起きた場合はどうなるか
である。そのままエラーを無視するとclientにのみ存在するエントリーが存在し、indexがずれる。
こちらは、gRPC側の実装にて問題ないことが担保されている。
client側で動的テーブル更新後に失敗することを想定する。l.hEnc.WriteFieldにてencodeおよび動的テーブルに追加しており、その後、l.framer.fr.WriteHeadersにて実際にサーバ送信しているが、そこで失敗したとする。ここでエラーをreturnし、connectionがcloseされるする。
server側でdecodeが失敗することを想定する。writeが内部でdecodeをしている。ここでストリームのエラーではなくコネクションのエラーと判断され、connectionがcloseされる。
要するに、どこかしらでエラーが起きた場合、必ずコネクションがcloseされ、動的テーブルもリフレッシュされるのである。
なお、上記は、「clientがencode後serverがdecodeする」方向であったが、「serverがencode後clientがdecodeする」方向でも同様のことが言える。
常にハフマンエンコードされるわけではない
HPACKでハフマン符号が利用されているのは有名だ。
ハフマン符号と聞くと「頻度を元に木を構成していって符号化する」というプロセスを思い浮かべがちだが、符号化自体は事前に巨大なサンプルデータをもとにされており、rfcにも記載がある。
5bit~30bitであることがわかる。asciiが8bitなので当然asciiの方が逆に効率が良いという場合もある。goの実装では以下で必要なbit数を比較して符号化すべきかを判断している。
https://github.com/golang/net/blob/abc453219eb586afb3fc1742e8c685c28b9f7eea/http2/hpack/encode.go#L213-L224
ハフマンでのデコードの工夫
もはやHPACKとはそんなに関係がなく、ハフマンにてデコードする際の実装の工夫でアルゴリズムの話だが、初見だと何をしているかわからず最終的には感心した部分なので触れておく。
最初に触れておくとハフマンのエンコードはとても簡単である。事前に符号化されているのでそのbit列を連結するだけである。
デコードはどうするか。普通に一番最初に思いつくのは、ハフマン符号に対応する２分木を構成しておき、デコード対象のバイト列を入力として、２分木のleafにたどり着いたらそれが対象となる文字と判断できる。そのあとはまたrootに戻り同じ操作をすればいい。
最適化としてすぐに思いつくのは256分木にするという手法である。1byteずつrootから下っていけるので、多くて4stepでデコードできることになる。
goの実装はこの手法なのだが、？となった実装が以下の部分である。
https://github.com/golang/net/blob/abc453219eb586afb3fc1742e8c685c28b9f7eea/http2/hpack/huffman.go#L159-L162
これを文字で説明するより図を見た方が良いので以下を見て欲しい。
256分木だとわかりづらいので4分木にしている。また符号化は適当である。
このように4分木にする場合には重複する要素がでてくる場合がある。これはデコードするためには必要な考慮であり、上記のコードはまさにこの考慮をしている。
-
例えば、https://grpc.io/blog/grpc-go-perf-improvements/ 等のブログを参照する限り、言語を横断してコミュニティはコミュニケーションしているようである。 ↩
-
正確には、HPACK自体はgRPCの仕様ではなく、一つ下のレイヤーのHTTP2の仕様である。Go実装でもHPACK実装は、https://github.com/golang/net/tree/master/http2/hpack にあり、https://github.com/grpc/grpc-go ではそれらを利用している。 ↩
-
この32バイトについてrfcに「The additional 32 octets account for an estimated overhead associated with an entry. For example, an entry structure using two 64-bit pointers to reference the name and the value of the entry and two 64-bit integers for counting the number of references to the name and value would have 32 octets of overhead.」とある。 ↩