前回の記事では、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