Goのnet/httpでtimeout指定したときにどう制御されるのか追ってみた

はじめに

net/httpを使ったhttpリクエストでは2つの方法でtimeout管理ができます。

  • Client.Timeout 値の設定
  • Request.WithContext でcontextを食わせる

前者はtimeoutに特化した制御で、後者はより広範囲な制御です。
(contextの場合は WithTimeout だけでなく WithCancel などで実装時に任意のタイミングでcancelされうる)

で、それぞれどのように制御されるのか気になって追ったメモ。

client.Do() から処理を追う

追いかけ

あとでちゃんとまとめる

https://github.com/golang/go/blob/ff5cf4ced3f1681ec972cd954d4b476f87616fe3/src/net/http/client.go#L314-L330 の実装的に、net/httpのTransportとhttp2transport、golang.org/x/net/http2.Transportあたりの実装ではcontextのハンドリングしてるっぽいな

まとめ

  • Client.Timeoutのほうは内部的にtickerのようなものに変換されてtimeout管理される
  • contextのほうはTransporterの実装のなかで終了シグナルがハンドルされる
    • つまりRoundTripperがハンドルを実装していないとcontextの終了は検知されない
    • 自作RoundTripperやサードパーティ実装を使うときは要チェック!

感想

  • Goの標準パッケージめっちゃ読みやすい
    • client.goとかは3000行くらいあるけど、同じものに対しての記述で仕様が複雑なだけ
    • むしろ整理しようとしてファイルや階層を過度に複雑にするとそっちのほうが追いづらい
  • 差し替え可能なRoundTripper内でcontextをハンドルしてるのはすこしびっくり
    • まあでも実際にhttp requestするのはここだから納得
    • Transport以外のRoundTripper実装ではcontextがハンドルされる保証がないので、事情があって使うときは必ず確認すること

protoc-gen-gogoの成果物がかなり読みやすい件

3行まとめ

protoc-gen-gogoの成果物みてみたら、
ベタッとbytesをunmarshalするコードが書いてあって、
仕様と一緒に見たらかなり読みやすかった

きっかけ

ectdのraftコードを読んでたらたまたまprotoc-gen-gogoで生成されたコードを発見。

github.com

ちょうどprotobufの仕様とか読んだりしてたから気になってみてみた。
素朴にbytesを読んでるだけで抽象化とか特にしてないから前提知識なくても読めて、読みやすかった。

(以前 Goの実装 を読もうとしたこともあるけど、jsonやtextやwireにうまいこと変換できるような抽象化がなされていて、wireの実装だけ詳細が知りたかったのでちょっと困った)

生成

こういうproto定義を

syntax = "proto3";
package example;

message Example {
    int32 standardInt32 = 1;
    sint32 signedInt32 = 2;
    string str = 3;
}

こうする

$ protoc --gofast_out=. ex.proto

生成物の確認

かなり素朴でわかりやすい。 基本的にbyteをゴニョゴニョしてるだけなので仕様書と照らし合わせれば読める

構造体

type Example struct {
    StandardInt32        int32    `protobuf:"varint,1,opt,name=standardInt32,proto3" json:"standardInt32,omitempty"`
    SignedInt32          int32    `protobuf:"zigzag32,2,opt,name=signedInt32,proto3" json:"signedInt32,omitempty"`
    Str                  string   `protobuf:"bytes,3,opt,name=str,proto3" json:"str,omitempty"`
    XXX_NoUnkeyedLiteral struct{} `json:"-"`
    XXX_unrecognized     []byte   `json:"-"`
    XXX_sizecache        int32    `json:"-"`
}
  • wire用のタグがふられる
  • signed int はzigzag encoding使うから区別のためにzigzagってタグがふってあるぽい
  • optionalとかもふってある

marshal

func (m *Example) MarshalToSizedBuffer(dAtA []byte) (int, error) {
    i := len(dAtA)
    _ = i
    var l int
    _ = l
    if m.XXX_unrecognized != nil {
        i -= len(m.XXX_unrecognized)
        copy(dAtA[i:], m.XXX_unrecognized)
    }
    if len(m.Str) > 0 {
        i -= len(m.Str)
        copy(dAtA[i:], m.Str)
        i = encodeVarintExample(dAtA, i, uint64(len(m.Str)))
        i--
        dAtA[i] = 0x1a
    }
    if m.SignedInt32 != 0 {
        i = encodeVarintExample(dAtA, i, uint64((uint32(m.SignedInt32)<<1)^uint32((m.SignedInt32>>31))))
        i--
        dAtA[i] = 0x10
    }
    if m.StandardInt32 != 0 {
        i = encodeVarintExample(dAtA, i, uint64(m.StandardInt32))
        i--
        dAtA[i] = 0x8
    }
    return len(dAtA) - i, nil
}

func encodeVarintExample(dAtA []byte, offset int, v uint64) int {
    offset -= sovExample(v)
    base := offset
    for v >= 1<<7 {
        dAtA[offset] = uint8(v&0x7f | 0x80)
        v >>= 7
        offset++
    }
    dAtA[offset] = uint8(v)
    return base
}

func sovExample(x uint64) (n int) {
    return (math_bits.Len64(x|1) + 6) / 7
}
  • MarshalToSizedBuffer は渡されたbyte sliceにmarshalした結果をつめこむ。末尾からencodeしていく
  • 各フィールドのmarshalは encodeVarintExample でやってる
    • vが8バイト以上の値だったら 最上位byteが1と、vの下位7バイトを連結してdestに詰めてvを7bit右シフトする(1byte読みすすめる)
      • varintのwire typeは上位1bitが立ってるとデータが連続することを表す
    • vが7bit以下の値だったらその値を書き込んで終了
      • varintのwire typeは上位1bitが立っていないとデータ終端であることを表す
  • sovExample はxに必要なバイト数をわりだす
    • xの下位1bitを立てる(立ってないと7で割ったときに端数になるから?よくわからん)
    • 6bit足す(タグをつけるので必要。field number + wire type)
    • 7で割る(必要なbyte数を取得)

unmarshal

func (m *Example) Unmarshal(dAtA []byte) error {
    l := len(dAtA)
    iNdEx := 0
    for iNdEx < l {
        preIndex := iNdEx
        var wire uint64
        for shift := uint(0); ; shift += 7 {
            if shift >= 64 {
                return ErrIntOverflowExample
            }
            if iNdEx >= l {
                return io.ErrUnexpectedEOF
            }
            b := dAtA[iNdEx]
            iNdEx++
            wire |= uint64(b&0x7F) << shift
            if b < 0x80 {
                break
            }
        }
        fieldNum := int32(wire >> 3)
        wireType := int(wire & 0x7)
        if wireType == 4 {
            return fmt.Errorf("proto: Example: wiretype end group for non-group")
        }
        if fieldNum <= 0 {
            return fmt.Errorf("proto: Example: illegal tag %d (wire type %d)", fieldNum, wire)
        }
        switch fieldNum {
        case 1:
            if wireType != 0 {
                return fmt.Errorf("proto: wrong wireType = %d for field StandardInt32", wireType)
            }
            m.StandardInt32 = 0
            for shift := uint(0); ; shift += 7 {
                if shift >= 64 {
                    return ErrIntOverflowExample
                }
                if iNdEx >= l {
                    return io.ErrUnexpectedEOF
                }
                b := dAtA[iNdEx]
                iNdEx++
                m.StandardInt32 |= int32(b&0x7F) << shift
                if b < 0x80 {
                    break
                }
            }
        case 2:
            if wireType != 0 {
                return fmt.Errorf("proto: wrong wireType = %d for field SignedInt32", wireType)
            }
            var v int32
            for shift := uint(0); ; shift += 7 {
                if shift >= 64 {
                    return ErrIntOverflowExample
                }
                if iNdEx >= l {
                    return io.ErrUnexpectedEOF
                }
                b := dAtA[iNdEx]
                iNdEx++
                v |= int32(b&0x7F) << shift
                if b < 0x80 {
                    break
                }
            }
            v = int32((uint32(v) >> 1) ^ uint32(((v&1)<<31)>>31))
            m.SignedInt32 = v
        case 3:
            if wireType != 2 {
                return fmt.Errorf("proto: wrong wireType = %d for field Str", wireType)
            }
            var stringLen uint64
            for shift := uint(0); ; shift += 7 {
                if shift >= 64 {
                    return ErrIntOverflowExample
                }
                if iNdEx >= l {
                    return io.ErrUnexpectedEOF
                }
                b := dAtA[iNdEx]
                iNdEx++
                stringLen |= uint64(b&0x7F) << shift
                if b < 0x80 {
                    break
                }
            }
            intStringLen := int(stringLen)
            if intStringLen < 0 {
                return ErrInvalidLengthExample
            }
            postIndex := iNdEx + intStringLen
            if postIndex < 0 {
                return ErrInvalidLengthExample
            }
            if postIndex > l {
                return io.ErrUnexpectedEOF
            }
            m.Str = string(dAtA[iNdEx:postIndex])
            iNdEx = postIndex
        default:
            iNdEx = preIndex
            skippy, err := skipExample(dAtA[iNdEx:])
            if err != nil {
                return err
            }
            if (skippy < 0) || (iNdEx+skippy) < 0 {
                return ErrInvalidLengthExample
            }
            if (iNdEx + skippy) > l {
                return io.ErrUnexpectedEOF
            }
            m.XXX_unrecognized = append(m.XXX_unrecognized, dAtA[iNdEx:iNdEx+skippy]...)
            iNdEx += skippy
        }
    }

    if iNdEx > l {
        return io.ErrUnexpectedEOF
    }
    return nil
}

TODO あとでかく

感想

  • めっちゃ読みやすい
  • 仕様読んだときのこういうときどうするんだろう?の疑問がいくつか解決しそう
  • やっぱり仕様/実装どっちも見ることで理解度は大きく向上する
  • まだちょっとわからないところがあるのでもうちょっと読み込みたい
  • zigzag encodingについてちょっとまとめたいなと思った。今の理解は以下なので実装とかして深めたい
    • standard intは2の補数表現で表されるから、負数になると絶対値が小さくても最上位bitが立って使用bitが常に最大になる
    • zigzag encodingは2の補数表現を使わずに下位1bitの有無で正負を判断するため、絶対値が小さいときは使用bitもすくない
    • その代わり正の値nと比較すると、 1 + 2(n - 1) のbitがたつ。。つまり大体常に余計に1bitたつ。
    • uintとかならstandard intのほうがお得だよ

よくわかる bloom filter

bloom filter とは

bloom filter とは、ざっくりいうと ある集合において、低コストにある要素が存在しないことがわかる データ構造です。

どのくらいコストが低いかというと、要素の登録や存在確認がともに O(k) です(kは利用するハッシュの数)。
集合の最大要素数や、実際に登録されているデータ数に影響されずに固定時間で結果を返せます。

特徴としては

  • 登録、存在確認のコストが O(k)
  • 「存在するよ!」といってるのに探してみたら存在しない場合がある(偽陽性がある)
  • 「存在しないよ!」といったものは100%存在しない(偽陰性はない)

なので、偽陽性が許容できる場合においては高速な存在確認としてつかえます。
想定できる使い方としては、探索コストが高いデータを検索する前にbloom filterをつかう、など。

しくみ

一言でいうと単語を複数のbit列のindex値に変換して、そのindex番目のbitがすべて立ってるかチェックして、立ってれば存在している、一つでも立っていなければ存在しない!と判断させるだけです。

単語をbit列のindex値に変換するときにhashを使います。(bit列内でonにするindex値を十分に分散させるため。ここに偏りがあると偽陽性率があがる。はず。)

以下の説明では

  • bit列の長さ8
  • hashの数は1

のものを利用して説明します

(実際にはbit列の長さが小さすぎると衝突の可能性がますのでこんなに短いbit列を使うことはほぼないはずだし、hashの数は要素数やbit列長によって最適な数がもとめられるので1個であることはあまりないはず。まあ説明のための例なので細かいところは気にしないですすめる)

登録

ある単語の登録は、その単語をhash関数にかけてbit列のindex値を取得し、そのbitをたてます。

たとえば apple という文字列をhash化した結果が 5 だったとすると、bit列の5番目のbitをたてます

index 7 6 5 4 3 2 1 0
bit 0 0 1 0 0 0 0 0

存在確認

ある単語の存在確認は、その単語をhash関数にかけてbitのindex値を取得し、そのbitが立っているか確認します。

apple の存在確認をしてみます。
apple はhash化すると 5 になるのでした。
先程追加したbit列を確認すると、5番目のbitは立っているので、 apple は存在していると判断できます。

index 7 6 5 4 3 2 1 0
bit 0 0 1 0 0 0 0 0

つぎに orange の存在確認をしてみます。
orange はhash化すると 7 になりました。
このbit列から7番目の値を確認すると0です。bitが立っていないので、 orange は存在していないと判断できます。

index 7 6 5 4 3 2 1 0
bit 0 0 1 0 0 0 0 0

つぎに banana の存在確認をしてみます。
banana はhash化すると 5 になりました。
bit列から5番目の値を確認すると、bitが立っているので banana は存在していると判断されます! 実際には banana はまだ追加されていないので、これは偽陽性のパターンです。

index 7 6 5 4 3 2 1 0
bit 0 0 1 0 0 0 0 0

かんたんな実装

以下に実装を交えて説明します。実装はGo

試せるコードをplaygroundにもおいておきます
(割とtimeoutします。playgroundの機嫌が良ければ実行できます。素朴に実装してるためmd5を12回振ってるので大変なのかな...ハッシュ生成コスト的には、本来はダブルハッシュ法などをつかったほうがいいです)

play.golang.org

ある長さを持ったbit列をつくります。(ここでは例として長さは8)
Goなら以下でOK

var bits uint8

ある単語を登録するには、その単語をハッシュ化してbitのindexをとります。

bit列の長さが8なので、0~7の範囲になるようなhash関数を準備します
今回はかませるhashの数は3つとします。bit列の長さや追加する要素数によって最適なhash数はもとめることができますが、今回はそのあたりは考慮しません。

func hash(s string) (idxes [3]uint8) {
    // md5結果の終端byteの上位3bitの値(0~7)をbitsのindex値として返す
    // 最終的に分散された3bit値が取れればいいので、8の剰余をとってもどちらでもよい。
    // ことなるハッシュがとりたいので適当にsaltをふる
    idxes[0] = md5.Sum([]byte(s+"1"))[15] >> 5
    idxes[1] = md5.Sum([]byte(s+"2"))[15] >> 5
    idxes[2] = md5.Sum([]byte(s+"3"))[15] >> 5
    return idxes
}

bit列に値を追加したいときは、ハッシュを使ってindexを取得し、そのindex番目のbitを立てます。
idx番目のbitをとるにはidxぶんだけ1を左シフトすればよいです。

func add(s string) {
    idxes := hash(s)
    for _, idx := range idxes {
        // idx番目のbitを立てる
        bits |= 1<<idx
    }
}

bit列の値を存在チェックしたいときも同じくハッシュを使って、index番目のbitが立っているか確認すればよいです。
すべてのindex番目のbitがたっていれば その要素は存在していると判断できます。

func exists(s string) bool {
    idxes := hash(s)
    for _, idx := range idxes {
        // idx番目のbitが立っていないケースを判定
        if 1<<idx != 1<<idx & bits {
            return false
        }
    }
    return true
}

準備はできたので、てきとうにそれらを呼び出してみましょう。
bit列に単語を登録したり、単語が存在するかbit列を確認したりしてみます。

func main() {
    add("test1")
    fmt.Printf("added bits: %b\n\n", bits)
    // 存在する
    fmt.Printf("is exists 'test1': %t\n\n", exists("test1"))
    // 存在しない
    fmt.Printf("is exists 'test2': %t\n\n", exists("test2"))
    // 存在しないのに存在すると判定している(偽陽性)
    fmt.Printf("is exists 'test12': %t\n\n", exists("test12"))
}

今までの実装にlogなどを適宜仕込みつつ実行すると以下のように出力されます

bit on: 10000000
bit on: 1
bit on: 10
added bits: 10000011

bit check: 10000000
bit check: 1
bit check: 10
is exists 'test1': true

bit check: 100000
is exists 'test2': false

bit check: 1
bit check: 10
bit check: 10000000
is exists 'test12': true

感想

  • 偽陽性を許容してぱぱっと存在確認したいときによさそう
  • いろいろと亜種がいて Scalable Bloom Filter なるものもいるようなので気になる
  • 現実世界の実装では、hashを複数回生成するのはコストがかかるのでダブルハッシュ法とかをつかうらしい
  • bit列の中身のbitが全部立つとどんな入力に対しても存在すると思い込むはずなので、偽陽性が上がりそう
    • ある程度はbitを残せるような要素数がいいのかな
    • bitが埋まってきたらhash関数の数を増やせば偽陽性は減りそう
    • そのあたりの適切なbit長/要素数/hash数まわりの関係性についてはもう少し自分の中で整理して理解を深めたい

protobuf のエンコーディング仕様ざっとよんだ感想

developers.google.com

以下感想

  • protobufのエンコーディングwireっていうバイナリエンコーディングでやってる
  • wireJSONなどど比較してフィールド名を省略してフィールド番号にすることでバイトの削減と互換のとりやすさを実現していて面白い
    • フィールド番号とtypeが同じならお互いの.protoで定義されたmessage schema間でフィールド名が違っても動作に影響はない
  • 仕様の雑メモ
    • タグのbyteの末尾3bitがtype, のこりがフィールド番号?
      • フィールド数が5bit(最大31)を超えたらどうなるかあんまよくわからん
    • 文字列はvalueの先頭1byte目に長さを持つ
      • 1byte(最大255)で表現できる長さを超えた時どうなるかはあんまよくわからん
    • 固定長のtypeのvalueは値がそのまま入る
    • 可変長バイト列のtypeは上位1bitが終端バイトかどうかの情報をもつ
    • 可変長バイト列を連結するときは順番をひっくり返して結合する
    • 可変長バイト列の場合、int64型とかをつかって負数が出たときは2の補数表現になるので必ず最上位bitが立って、絶対値が小さくても使うバイト数がめっちゃ多くなる
    • sint64(signed int)型を使うとZigZag encodingを使うので絶対値が小さいときは使うバイト数が少なくなる。負数が登場する場合はこちらがおすすめ
      • 00000001 → -1
      • 00000010 → 1
      • 00000011 → -2
      • 00000100 → 2
      • ...
      • みたいに交互に+-を行ったり来たりすることで絶対値が小さいときは負数でも使用byte数が小さくなる

などなど。細かいところはもうちょいあるけどおもしろかった。