GolangでIBLTを実装してみた

前回の記事では、IBLTの概要について記載しました。 今回はIBLTのデータ構造と実装について記載します。 なお、使った図などはこちらにスライドとしてまとめています。

データ構造

IBLTは以下のようにm個のcellを持ちます。 各cellには、count、keySum、valueSumの3フィールドがあります。

今回はkeyとvalueはint型として実装します。 cellは上記3つのフィールドを持つstructとし、IBLTをcellのsliceとして、以下のように定義します。

type cell struct {
    count, keySum, valueSum int
}

type IBLT []cell

ハッシュ関数

IBLTではBloomFilterと同じようにkey-value pairをInsert/Deleteするためcellを決定するためハッシュ関数を用います。今回の実装上は、説明用の図に合わせ、ハッシュ関数の数をk = 3としています。

メソッドの実装

前回の記事も記載しましたがIBLTでサポートされるメソッドは以下の4つです。

• (key, value)のInsert
• (key)のGet
• (key, value)のDelete
• ListEntries

それぞれ実装していきます。

Insert

まずは、Insertです。 Insertは単純で、TをIBLTとし、i = 1, ..., kのハッシュ関数に対して以下の操作を行います。

• ].count++]
• ].sumKey += key]
• ].sumValue += value]

Insert(key=5, value=10)とすると以下のようになります。

さらにInsert(key=2, value=30)を追加でInsertしてみます。

実装は以下のようになります。

func (iblt IBLT) Insert(key, value int) {
    hash := util.CalcMD5Hash(strconv.Itoa(key))
    hashA := hash[:int(len(hash)/2)]
    hashB := hash[int(len(hash)/2):]

    i64HashA, _ := strconv.ParseInt(hashA, 16, 64)
    i64HashB, _ := strconv.ParseInt(hashB, 16, 64)

    for i := 0; i < k; i++ {
        iblt[util.DoubleHashing(i64HashA, i64HashB, i, len(iblt))].count++
        iblt[util.DoubleHashing(i64HashA, i64HashB, i, len(iblt))].keySum += key
        iblt[util.DoubleHashing(i64HashA, i64HashB, i, len(iblt))].valueSum += value
    }
}

Get

次にGetです。フローチャートに表すと以下のようになります。

何パターンか例を見ていきましょう。 (key, value) = (5, 10), (2, 30)が挿入済みのIBLTに対して、Get(key=2)を行ってみます。

1つ目のハッシュ関数でcountが1かつkeySumがkeyと一致したため正しくvalue=30を返せています。

次に(key, value) = (5, 10), (2, 30)が挿入済みのIBLT(1つ前と同じ)に対して、Get(key=3)(Insertしていないkey)を行ってみます。

1つ目のハッシュ関数でcountが0となったため正しくfalseを返せています。

最後に(key, value) = (5, 10), (2, 30)が挿入済みのIBLT(前2つと同じ)に対して、Get(key=9)(Insertしていないkey)を行ってみます。

1つ目のハッシュ関数でcountが1となりましたが、keySumがkeyと一致しませんでした。 2,3つ目のハッシュ関数ではcountが2となり、k = 3個のハッシュ関数の探索が終わったため、正しくfalseを返します。

Getに関する補足

上で見たようにGetは、ハッシュ関数で特定したcellのcountが1かつkeySumがkeyと一致（一つしかInsertしていないcellでkeyが一致する）であれば、valueSumを返します。BloomFiterと同じく、いくつかのハッシュ関数が衝突したとしても一つでも衝突してない(countが0)のcellがあれば、正しくfalseを返します。

BloomFilterと異なる点としては、ハッシュ衝突が起こっても、keySumのチェックがあるため、keyが異なればfalseを返します。ただし注意が必要なのは、countが1のときにのみ正しいvalueを返してくれる点です。Insertが複数に渡って行われた場合、countが2以上のcellばかりになり、正しくInsertしたkeyであってもfalseを返します。つまり、false-negativeがあります（falseと返したが、実はkeyはInsertされている）。

false-negativeが起こる例も見てみましょう。 (key, value) = (5, 10), (2, 30), (3, 20)が挿入済みのIBLT(これまでの例より(3, 20)が多い)に対して、Get(key=2)(Insert済みのkey)を行ってみます。

1,2,3つ目のハッシュ関数のいずれでもcountが2となり、k = 3個のハッシュ関数の探索が終わったため、誤ってfalseを返します。

この辺は、原論文で言及されていないのですが、あまり嬉しくない性質ですね。

実装は以下です。

func (iblt IBLT) Get(key int) (bool, int) {
    hash := util.CalcMD5Hash(strconv.Itoa(key))
    hashA := hash[:int(len(hash)/2)]
    hashB := hash[int(len(hash)/2):]

    i64HashA, _ := strconv.ParseInt(hashA, 16, 64)
    i64HashB, _ := strconv.ParseInt(hashB, 16, 64)

    for i := 0; i < k; i++ {
        idx := util.DoubleHashing(i64HashA, i64HashB, i, len(iblt))
        if iblt[idx].count == 0 {
            return false, 0
        }
        if iblt[idx].count == 1 {
            if iblt[idx].keySum == key {
                return true, iblt[idx].valueSum
            }
            return false, 0
        }
    }
    return false, 0
}

Delete

DeleteはInsertの逆の手順となります。

• ].count--]
• ].sumKey -= key]
• ].sumValue -= value]

(key, value) = (5, 10), (2, 30)が挿入済みのIBLTにDelete(key=2, value=30)を行ってみます。

(key, value) = (5, 10)だけInsertした状態と一致し、正しくDeleteできています。 ここで、Insertしていないkeyに対してもDeleteが実行できることに注意してください。

実装は以下です。

func (iblt IBLT) Delete(key, value int) {
    hash := util.CalcMD5Hash(strconv.Itoa(key))
    hashA := hash[:int(len(hash)/2)]
    hashB := hash[int(len(hash)/2):]

    i64HashA, _ := strconv.ParseInt(hashA, 16, 64)
    i64HashB, _ := strconv.ParseInt(hashB, 16, 64)

    for i := 0; i < k; i++ {
        iblt[util.DoubleHashing(i64HashA, i64HashB, i, len(iblt))].count--
        iblt[util.DoubleHashing(i64HashA, i64HashB, i, len(iblt))].keySum -= key
        iblt[util.DoubleHashing(i64HashA, i64HashB, i, len(iblt))].valueSum -= value
    }
}

ListEntries

最後にListEntriesです。 ListEntriesはkey-value pairを列挙するため、以下のPairを定義します。

type Pair struct {
    key, value int
}

フローチャートは以下のようになります。

これまでと同じように例を見ていきます。 (key, value) = (5, 10), (2, 30)が挿入済みのIBLTにからPairを列挙するため、 ListEntries()を行ってみます。

cellを前から順番に見ていき、countが1となるcellが見つかれば、そのPairを列挙、削除し、また最初からcellを見ていきます。 Insert済みであった(5, 10), (2, 30)が列挙できました。

実装は以下です。

func (iblt IBLT) ListEntries() []Pair {
    var pairs []Pair
    newIblt := NewIBLT(len(iblt))
    copy(newIblt, iblt)

LABEL:
    for i := 0; i < len(newIblt); i++ {
        if newIblt[i].count == 1 {
            pairs = append(pairs,
                Pair{
                    key:   newIblt[i].keySum,
                    value: newIblt[i].valueSum,
                },
            )
            newIblt.Delete(newIblt[i].keySum, newIblt[i].valueSum)
            goto LABEL
        }
    }
    return pairs
}

最後に

false-negativeがあるので使い所を選ぶのではないかというのが所感ですが、集合一致のような列挙が必要な用途では要素をサマライズしたテーブルを渡せるIBLTは有用そうです。実際、Grapheneでは、新しいブロックに2000tx入っている前提で2.6KBに圧縮できると述べられており、同条件のCompact Blocksの10KBに比べて3倍以上の圧縮効率となります。

また、今回実装したIBLTだけでなく、BloomFilterやcounting BloomFiterの実装もGithubにあげてあります。

References

• ビットコインキャッシュの使用ブロック伝播速度を10倍にする新技術”Graphene”
• Graphene: A New Protocol for Block Propagation Using Set Reconciliation
• Invertible Bloom Lookup Tables
• O(1) Block Propagation
• ビットコインとは何か? 第4回:ビットコインの仕組み(取引承認と採掘) - Bitcoin日本語情報サイト
• BloomFilterについて調べてみた - 逆さまにした
• GolangでBloomFilterを実装してみた - 逆さまにした
• Golangでcounting BloomFilterを実装してみた - 逆さまにした
• goBloomFilter/iblt
• Bitcoin block propagation with IBLT, Part I: infographic
• Bitcoin Cashのブロック伝搬速度を10倍にするGrapheneで使われているInvertible Bloom Lookup Tables(IBLT)について調べてみた - 逆さまにした
• How IBLT Works