3. LevelDB 소스 코드 분석의 기초 부품 - Bloom Filter, Murmur Hash, CRC 32
3.1.1 기본 개념
부 릉 필터 (영어: Bloom Filter) 는 1970 년 부 릉 이 제기 한 것 이다.하나의 요소 가 집합 에 들 어 갈 때 K 개의 해시 함 수 를 통 해 이 요 소 를 하나의 배열 의 K 점 으로 매 핑 하여 1 로 설정 합 니 다.검색 할 때 우 리 는 이 점 들 이 모두 1 인지 아 닌 지 를 보면 집합 에 그것 이 있 는 지 알 수 있다. 만약 에 이 점 들 이 0 이 있다 면 검 사 된 요 소 는 반드시 없 을 것 이다.모두 1 이 라면, 검 사 된 원소 가 있 을 가능성 이 높다.
다른 데이터 구조 에 비해 부 릉 필 터 는 공간 과 시간 면 에서 큰 장점 을 가진다.부 릉 필터 저장 공간 과 삽입 / 조회 시간 은 상수 O (k) 입 니 다.
그러나 부 릉 필터 의 단점 은 장점 만큼 뚜렷 하고 오 산 률 도 그 중 하나 다.저 장 된 요소 의 수량 이 증가 함 에 따라 오산 율 이 증가한다.그러나 원소 의 수량 이 너무 적 으 면 산열 표를 사용 하면 충분 하 다.또한, 일반적으로 브 론 필터 에서 요 소 를 삭제 할 수 없습니다. 지정 한 position 에 key 에 의 해 매 핑 되 었 는 지 알 수 없 기 때 문 입 니 다.
만약 에 Hash 함수 가 등 확률 조건 으로 Bit Array 중의 한 분 을 선택 하고 설정 하면 m 는 이 배열 의 크기 이 고 n 은 데이터 갯 수 이 며 k 는 Hash 함수 의 갯 수 이다. 주어진 m, n 에 대해 Hash 함수 갯 수 k 를 어떻게 선택 하 는 지 다음 과 같은 공식 으로 확인한다. k = ln2 * m / n = 0.7 * m / n.이때 오보 율 은: 2 ^ - k = 0.6185 ^ m / n 이다.m / n = 10 시 오보 율 은 약 0.8% 이다.자세 한 증명 은 블 룸 필터 (Bloom Filter) 를 참조 하 십시오.
3.1.2 LevelDB 버 전 구현
LevelDB 는 Bloom filter 를 내 장 된 필터 로 사용 할 수 있 으 며, 핵심 알고리즘 코드 는 Bloom. cc 에 있 습 니 다.
3.1.2.1 K 값 선택
앞에서 설명 한 바 와 같이 최 적 k 값 은 0.7m / n 이 고 leveldb 에서 기본적으로 일치 합 니 다.
class BloomFilterPolicy : public FilterPolicy
{
private:
size_t bits_per_key_;
size_t k_;
public:
explicit BloomFilterPolicy(int bits_per_key)
: bits_per_key_(bits_per_key)
{
// We intentionally round down to reduce probing cost a little bit
k_ = static_cast(bits_per_key * 0.69); // 0.69 =~ ln(2)
if (k_ < 1)
k_ = 1;
if (k_ > 30)
k_ = 30;
}
......
};
LevelDB 는 m / n 을 bits 라 고 명명 합 니 다.per_key, 조금 다른 것 은 leveldb 의 k 값 을 아래로 조정 하 는 것 입 니 다.충돌 을 감지 하 는 데 걸 리 는 시간 을 줄 이기 위 한 것 이 라 고 저 자 는 설명 하지만, 이렇게 오보 율 을 높 여 전체적인 성능 은 비 하향 조정 후 보다 나 빠 야 한다.
K 가치 수치 범 위 는 1 - 30 이 고 저자 추천 치 는 10 (테스트 프로그램 참조) 이 며 이때 오보 율 은 1% (약 0.8%) 보다 적다.
3.1.2 부 릉 삽입
부 릉 비트 그룹 구축 논 리 는 다음 과 같다.
class BloomFilterPolicy : public FilterPolicy
{
......
virtual void CreateFilter(const Slice *keys, int n, std::string *dst) const
{
// (n * m /n = m)
// Compute bloom filter size (in both bits and bytes)
size_t bits = n * bits_per_key_;
// For small n, we can see a very high false positive rate. Fix it
// by enforcing a minimum bloom filter length.
if (bits < 64)
bits = 64;
size_t bytes = (bits + 7) / 8;
bits = bytes * 8;
//
const size_t init_size = dst->size();
dst->resize(init_size + bytes, 0);
// K
dst->push_back(static_cast(k_)); // Remember # of probes in filter
char *array = &(*dst)[init_size];
// key hash key 1
for (int i = 0; i < n; i++)
{
// double hashing K position K hash
// Use double-hashing to generate a sequence of hash values.
// See analysis in [Kirsch,Mitzenmacher 2006].
uint32_t h = BloomHash(keys[i]);
const uint32_t delta = (h >> 17) | (h << 15); // Rotate right 17 bits
for (size_t j = 0; j < k_; j++)
{
const uint32_t bitpos = h % bits;
array[bitpos / 8] |= (1 << (bitpos % 8));
h += delta;
}
}
}
......
}
LevelDB 의 부 릉 비트 그룹 은 미리 설 정 된 것 이 아니 라 동적 으로 생 성 된 것 이다.일부 key 값 에 대해 부 릉 비트 그룹 을 설정 하여 오보 율 이 예상 안에 있 음 을 보증 합 니 다.또한, 비트 그룹 은 std: string 을 빌 렸 고, 비트 그룹 은 마지막 으로 이 부 릉 비트 그룹 을 생 성 할 때 사용 하 는 K 값 을 추가 로 저장 했다.
그런데 이상 한 게 있어 요. 프로그램 이 resize 에 이 어 push 를 한 번 했 어 요.back, 이것 은 추가 적 인 메모리 분배, 복사 동작 을 초래 할 수 있 습 니 다. leveldb 와 같은 성능 에 대한 극 치 를 추구 하 는 프로그램 은 테스트 프로그램 을 보지 말 아야 합 니 다.
#include
#include
int main()
{
std::string name;
name = "hello";
name.resize(63,100);
std::cout << name.capacity() << std::endl;
name.push_back((char)97);
std::cout << name.capacity() << std::endl;
std::cout << "Hello, " << name << "!
";
}
g + + - O2 명령 으로 프로그램 결 과 를 컴 파일 하고 실행 합 니 다.
desmondwangdeMacBook-Pro:demo desmondwang$ g++ -O2 a.cpp
desmondwangdeMacBook-Pro:demo desmondwang$ ./a.out
63
127
Hello, hellodddddddddddddddddddddddddddddddddddddddddddddddddddddddddda!
마지막 으로 LevelDB 는 K 개의 hash 알고리즘 을 사용 하여 position 를 계산 하지 않 고 double hashing 을 사용 합 니 다. 공식 은 다음 과 같 습 니 다. h (i, k) = (h1 (k) + i * 8727 ° h2 (k) mod | T |.LevelDB 에서 h1 (k) 은 hash 알고리즘 에 따라 계 산 된 결과 이 고 h2 (k) 는 dela = (h > 17) | (h < < 15) 입 니 다.
3.1.2.3 부 릉 여과
부 릉 여과 계산 논 리 는 다음 과 같다.
class BloomFilterPolicy : public FilterPolicy
{
......
virtual bool KeyMayMatch(const Slice &key, const Slice &bloom_filter) const
{
const size_t len = bloom_filter.size();
if (len < 2)
return false;
const char *array = bloom_filter.data();
const size_t bits = (len - 1) * 8;
// K
// Use the encoded k so that we can read filters generated by
// bloom filters created using different parameters.
const size_t k = array[len - 1];
if (k > 30)
{
// Reserved for potentially new encodings for short bloom filters.
// Consider it a match.
return true;
}
//
uint32_t h = BloomHash(key);
const uint32_t delta = (h >> 17) | (h << 15); // Rotate right 17 bits
for (size_t j = 0; j < k; j++)
{
const uint32_t bitpos = h % bits;
if ((array[bitpos / 8] & (1 << (bitpos % 8))) == 0)
return false;
h += delta;
}
return true;
}
......
};
실현 논 리 는 매우 간단 하 다. 먼저 K 값 을 꺼 낸 다음 에 부 릉 비트 그룹 을 구축 하 는 것 과 같은 방식 으로 지 정 된 비트 그룹 이 1 인지 아 닌 지 를 판단 한다. 만약 모두 1 이면 이 값 이 존재 한다 고 인정 하고 그렇지 않 으 면 존재 하지 않 는 다 고 판단 한다.
3.2 Murmur Hash
부 릉 여과 에 사용 되 는 Hash 알고리즘 (BloomHash) 은 최종 적 으로 hash. cc 의 Hash 함 수 를 호출 합 니 다. 저자 에 따 르 면 이것 은 Murmur hash 의 변종 입 니 다.Murmur hash 에 대한 설명 은 다음 과 같 습 니 다.
MurmurHash 는 비 암호 화 형 해시 함수 로 일반적인 해시 검색 작업 에 적용 된다.
오 스 틴 애플 비 는 2008 년 발명 해 여러 변종 이 생 겨 공유 분야 (Public domain) 에 발표 됐다.다른 유행 하 는 해시 함수 에 비해 규칙 성 이 강 한 key, MurmurHash 의 무 작위 분포 특징 이 좋 습 니 다.
코드 구현 은 다음 과 같 습 니 다.
uint32_t Hash(const char *data, size_t n, uint32_t seed)
{
// Similar to murmur hash
const uint32_t m = 0xc6a4a793;
const uint32_t r = 24;
const char *limit = data + n;
uint32_t h = seed ^ (n * m);
// Pick up four bytes at a time
while (data + 4 <= limit)
{
uint32_t w = DecodeFixed32(data);
data += 4;
h += w;
h *= m;
h ^= (h >> 16);
}
// Pick up remaining bytes
switch (limit - data)
{
case 3:
h += static_cast(data[2]) << 16;
FALLTHROUGH_INTENDED;
case 2:
h += static_cast(data[1]) << 8;
FALLTHROUGH_INTENDED;
case 1:
h += static_cast(data[0]);
h *= m;
h ^= (h >> r);
break;
}
return h;
}
직관 적 으로 볼 때 코드 는 Murmur hash 보다 더욱 간결 합 니 다. 저 는 hash 알고리즘 에 대해 깊이 연구 하지 않 았 고 이곳 의 각종 우열 은 잠시 생략 할 수 밖 에 없습니다.
3.3 CRC32
CRC (Cyclic Redundancy Check) 중국어 이름 은 순환 중복 검사 로 데이터 저장 과 데이터 통신 분야 에서 데이터 의 정확성 을 확보 하기 위해 오류 검출 수단 을 사용한다.LevelDB 는 스스로 CRC 32 알고리즘 을 실 현 했 습 니 다. 핵심 코드 는 다음 과 같 습 니 다.
uint32_t Extend(uint32_t crc, const char *buf, size_t size)
{
static bool accelerate = CanAccelerateCRC32C();
if (accelerate)
{
return port::AcceleratedCRC32C(crc, buf, size);
}
const uint8_t *p = reinterpret_cast(buf);
const uint8_t *e = p + size;
uint32_t l = crc ^ 0xffffffffu;
#define STEP1 \
do \
{ \
int c = (l & 0xff) ^ *p++; \
l = table0_[c] ^ (l >> 8); \
} while (0)
#define STEP4 \
do \
{ \
uint32_t c = l ^ LE_LOAD32(p); \
p += 4; \
l = table3_[c & 0xff] ^ \
table2_[(c >> 8) & 0xff] ^ \
table1_[(c >> 16) & 0xff] ^ \
table0_[c >> 24]; \
} while (0)
// Point x at first 4-byte aligned byte in string. This might be
// just past the end of the string.
const uintptr_t pval = reinterpret_cast(p);
const uint8_t *x = reinterpret_cast(((pval + 3) >> 2) << 2);
if (x <= e)
{
// Process bytes until finished or p is 4-byte aligned
while (p != x)
{
STEP1;
}
}
// Process bytes 16 at a time
while ((e - p) >= 16)
{
STEP4;
STEP4;
STEP4;
STEP4;
}
// Process bytes 4 at a time
while ((e - p) >= 4)
{
STEP4;
}
// Process the last few bytes
while (p != e)
{
STEP1;
}
#undef STEP4
#undef STEP1
return l ^ 0xffffffffu;
}
CRC 32 인터넷 에 완전한 알고리즘 설명 이 있 는데 본 고 는 다음 과 같은 몇 가 지 를 설명 한다.
3.4 총화
블 론 필 터 는 LevelDB 1.2 버 전에 새로 추 가 된 특성 으로 LevelDB 의 성능 을 더욱 향상 시 키 는 데 목적 이 있다.
전재 하 시 려 면 명시 해 주 십시오: [안 거 사 를 따 르 겠 습 니 다]http://www.jianshu.com/p/366d6563fba8
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
