카산드라(cassandra)의 블룸필터 (bloom filter)

 

블룸필터의 의미와 카산드라에서 블룸필터를 어떻게 구현했는지 체크한다.

 

1. 블룸 필터 (Bloom Filter)

블룸 필터는 data 파일의 키값을 모아, 주어진 정보가 있는지 없는지 알려주는 확률 기반의 필터이다. 블룸필터 를 통해서 data가 있는지 빨리 확인할 수 있다. 상식선에서 잘 생각했을 때, 데이터가 없는데 있다는 것는 괜찮지만,  데이터가 있다고 해놓고서는 없는 것은 없다 라는 개념으로 보면 된다. 전자는 false positives, 후자는 false negatives 이다. 아래 내용이 바로 그런 예라고 보면 된다.
(false positives : 참이 아닌데, 실제로는 참이다,  false negatives : 참인데, 실제로는 거짓이다.)

(http://en.wikipedia.org/wiki/Bloom_filter 참조)

블룸 필터를 사용하면 일종의 키가 있는지 없는지에 대한 빠른 확인이 가능하다. (전문용어로 to save IO when performing a key lookup) 이렇게 함으로서 disk access를 조금이나다 적게 해서 속도를 높일 수 있다. 캐쉬는 아니지만, 캐쉬 처럼 비슷한 개념이 있다고 말할 수 있다.

블룸 필터는 두가지를 제공한다. 하나는 추가하는 add(), 하나는 존재하는지에 대한 isExist() 이다.  add() 할 때, key를 hash 알고리즘을 이용해서 여러 개의 hash 값을 나누고, 버킷이라는 저장장소에 저장한다. 그래서 isExist할때 그 버킷를 활용해서 있는지를 확인한다. 확률상 없는데, 있다고 나오지 않도록 적절하게 잡는 알고리즘이 최상의 알고리즘이라 할 수 있을 것 이다.

(http://en.wikipedia.org/wiki/Bloom_filter 참조)

 

자세한 내용은 아래 내용을 참조하면 쉽게 이해할 수 있다.

Programming Game Gen 의 블룸필터 챕터
http://mindori.egloos.com/1699170
http://blog.naver.com/PostView.nhn?blogId=cra2yboy&logNo=90122287288

 

 

2. 카산드라의 실제 소스 확인

 

카산드라 1.0.5 에서 bloom filter 를 사용하는 곳 (모두 org.apache.cassandra.io.sstable 패키지)은 다음과 같다.

- SSTable 생성시 (Index 용으로 활용) (SSTableWriter의 inner class IndexWriter)

public final BloomFilter bf; bf = BloomFilter.getFilter(keyCount, 15);

- SSTable을 읽을 때 (SSTableReader)

private Filter bf; bf = LegacyBloomFilter.getFilter(estimatedKeys, 15);

false positive 확률을 파라미터는 15 정도로 해서 잘 넘기고 있다.

BloomFilter의 getFilter() 메서드의 원형은 다음과 같다.

/** * @return The smallest BloomFilter that can provide the given false positive * probability rate for the given number of elements. * * Asserts that the given probability can be satisfied using this filter. */ public static BloomFilter getFilter(long numElements, double maxFalsePosProbability) {     assert maxFalsePosProbability <= 1.0 : "Invalid probability";     int bucketsPerElement = BloomCalculations.maxBucketsPerElement(numElements);     BloomCalculations.BloomSpecification spec = BloomCalculations.computeBloomSpec(bucketsPerElement, maxFalsePosProbability);     return new BloomFilter(spec.K, bucketsFor(numElements, spec.bucketsPerElement)); }

 

# 저장

Filter.db 파일에 블룸필터를 저장한다.  (Componen , SSTable 클래스 참조)

bloom filter를 저장할 때는 serialization하게 저장하게 되어 있다. (org.apache.cassandra.utils.BloomFilterSerializer.java)

bloom filter 의 hashcount 를 integer type으로 저장하고 그 다음에는 워드 개수(word number, bit 길이)를 저장한다. 그 다음에 page size만큼 page를 읽어와 bit 값을 저장한다.

public class BloomFilterSerializer implements ISerializer<BloomFilter> { public void serialize(BloomFilter bf, DataOutput dos) throws IOException { int bitLength = bf.bitset.getNumWords(); int pageSize = bf.bitset.getPageSize(); int pageCount = bf.bitset.getPageCount(); dos.writeInt(bf.getHashCount()); dos.writeInt(bitLength); for (int p = 0; p < pageCount; p++) { long[] bits = bf.bitset.getPage(p); for (int i = 0; i < pageSize && bitLength-- > 0; i++) dos.writeLong(bits[i]); } } … }

 

 

# Filter

Bloom Filter는 org.apache.cassandra.utils.Filter 추상 클래스를 상속받았다.

package org.apache.cassandra.utils; public abstract class Filter { int hashCount; int getHashCount() { return hashCount; } public abstract void add(ByteBuffer key); public abstract boolean isPresent(ByteBuffer key); }

 

# BloomFilter

org.apache.cassandra.utils.BloomFilter.java 이다.

abstract 메서드를 상속받은 두개의 메소드의 구현은 아래와 같다. 
제일 중요한 것은 확률적으로 잘 분산시킬 수 있는 알고리즘인데, 일반적으로는 SHA 기반의 알고리즘을 사용하여 난수를 만들어내는 데, 카산드라는 “Less Hashing, Same Performance: Building a Better Bloom Filter” (http://www.eecs.harvard.edu/~kirsch/pubs/bbbf/esa06.pdf) 과 MurMurHash(http://murmurhash.googlepages.com/)를 이용하고 있다. 

SHA보다 빠르고, 적당하게 잘 분산시킬 수(good collision resistance)  있다. hashcount와 주어진  key, OpenBit 길이(디폴트는 20개)로 만들어진 세트(hash bucket)에서 long [] 타입의 정보를 읽는다.

add 일  경우에는 fastGet를

public void add(ByteBuffer key) {     for (long bucketIndex : getHashBuckets(key))     {     bitset.fastSet(bucketIndex);     } } public boolean isPresent(ByteBuffer key) {     for (long bucketIndex : getHashBuckets(key))     {         if (!bitset.fastGet(bucketIndex))         {             return false;         }     }      return true; } private long[] getHashBuckets(ByteBuffer key) {     return BloomFilter.getHashBuckets(key, hashCount, bitset.size()); }     // Murmur is faster than an SHA-based approach and provides as-good collision     // resistance.  The combinatorial generation approach described in     // http://www.eecs.harvard.edu/~kirsch/pubs/bbbf/esa06.pdf     // does prove to work in actual tests, and is obviously faster     // than performing further iterations of murmur.     static long[] getHashBuckets(ByteBuffer b, int hashCount, long max)     {         long[] result = new long[hashCount];         long hash1 = MurmurHash.hash64(b, b.position(), b.remaining(), 0L);         long hash2 = MurmurHash.hash64(b, b.position(), b.remaining(), hash1);         for (int i = 0; i < hashCount; ++i)         {             result[i] = Math.abs((hash1 + (long)i * hash2) % max);         }         return result;     } /** Sets the bit at the specified index. * The index should be less than the OpenBitSet size. */ public void fastSet(long index) {    int wordNum = (int)(index >> 6);    int bit = (int)index & 0x3f;    long bitmask = 1L << bit;    bits[ wordNum / PAGE_SIZE ][ wordNum % PAGE_SIZE ] |= bitmask; } /** Returns true or false for the specified bit index.   * The index should be less than the OpenBitSet size.   */ public boolean fastGet(long index) {    int i = (int)(index >> 6);               // div 64    int bit = (int)index & 0x3f;           // mod 64    long bitmask = 1L << bit;    // TODO perfectionist one can implement this using bit operations    return (bits[i / PAGE_SIZE][i % PAGE_SIZE ] & bitmask) != 0; }

 

MurmurHash 클래스를 살펴본다. 이 클래스를 살펴보기 전에 성능을 봐야 하는데. intel core 2 duo 2.4 서버를 기준으로 했을 때, 초당 처리율을 최고를 자랑한다. 

Excellent performance - measured on an Intel Core 2 Duo @ 2.4 ghz

OneAtATime - 354.163715 mb/sec
FNV - 443.668038 mb/sec
SuperFastHash - 985.335173 mb/sec
lookup3 - 988.080652 mb/sec
MurmurHash 1.0 - 1363.293480 mb/sec
MurmurHash 2.0 - 2056.885653 mb/sec

 

/** * This is a very fast, non-cryptographic hash suitable for general hash-based * lookup. See http://murmurhash.googlepages.com/ for more details. * * <p> * The C version of MurmurHash 2.0 found at that site was ported to Java by * Andrzej Bialecki (ab at getopt org). * </p> */ public class MurmurHash {     public static long hash64(ByteBuffer key, int offset, int length, long seed)     {         long m64 = 0xc6a4a7935bd1e995L;         int r64 = 47;         long h64 = (seed & 0xffffffffL) ^ (m64 * length);         int lenLongs = length >> 3;         for (int i = 0; i < lenLongs; ++i)         {             int i_8 = i << 3;             long k64 =  ((long)  key.get(offset+i_8+0) & 0xff)      + (((long) key.get(offset+i_8+1) & 0xff)<<8)  +                         (((long) key.get(offset+i_8+2) & 0xff)<<16) + (((long) key.get(offset+i_8+3) & 0xff)<<24) +                         (((long) key.get(offset+i_8+4) & 0xff)<<32) + (((long) key.get(offset+i_8+5) & 0xff)<<40) +                         (((long) key.get(offset+i_8+6) & 0xff)<<48) + (((long) key.get(offset+i_8+7) & 0xff)<<56);                        k64 *= m64;             k64 ^= k64 >>> r64;             k64 *= m64;             h64 ^= k64;             h64 *= m64;         }         int rem = length & 0x7;         switch (rem)         {         case 0:             break;         case 7:             h64 ^= (long) key.get(offset + length - rem + 6) << 48;         case 6:             h64 ^= (long) key.get(offset + length - rem + 5) << 40;         case 5:             h64 ^= (long) key.get(offset + length - rem + 4) << 32;         case 4:             h64 ^= (long) key.get(offset + length - rem + 3) << 24;         case 3:             h64 ^= (long) key.get(offset + length - rem + 2) << 16;         case 2:             h64 ^= (long) key.get(offset + length - rem + 1) << 8;         case 1:             h64 ^= (long) key.get(offset + length - rem);             h64 *= m64;         }         h64 ^= h64 >>> r64;         h64 *= m64;         h64 ^= h64 >>> r64;         return h64;     } }