LevelDB 스터디 발표 내용 정리

학교에서 LevelDB 키 밸류 스토어에 대한 스터디가 열렸고 흥미가 생겨 이에 참여하였다.

 

 

 

https://github.com/DKU-StarLab/leveldb-study

GitHub - DKU-StarLab/leveldb-study: LevelDB Analysis, Backgrounds, Practice and Tuning

스터디 깃허브.

 

LevelDB의 각 파트들을 나눠 각자 조사와 발표를 진행하였고,

나는 블룸 필터에 관심이 생겨 해당 파트를 맡게 되었다.

 

latency

첫 발표땐 bits-per-key 값에 따른 write와 read의 처리율과 latency를 측정하였고,

그 결과 bits-per-key 값이 커질수록 false-positive가 발생할 확률이 감소하여

측정값이 균일해진다는 점을 발견하였다.

 

 

두번째 발표때엔 UFTRACE 툴을 활용하여 전체적인 code flow를 분석하고 핵심 코드 bloom.cc에 대한 설명을,

 

 

세번째 발표땐 효과적인 해싱 기법인 더블 해싱에 관해서,

그리고 네번째 발표때엔 understand 툴을 사용하여 더 상세한 code flow에 관하여 발표하였다.

 

 

 

그 다음엔 블룸 필터의 성능 개선을 위해 다양한 실험을 진행하였는데,

 

 

 

첫번째 가설은 디폴트인 10 bits-per-key를 사용할 때

수학적으로 증명된 최적의 해시 개수는 6.9개인데,

leveldb는 소숫점을 없애 6개의 해시 함수를 사용한다.

6.9는 6보다 7에 가까운 값이므로, 디폴트 10 bits에 대해

각각 6 hashes, 7hashes에 대한 성능을 측정하였다.

 

측정 결과 유의미한 성능 차이는 없었고, 0.00024라는 확률 차이는 별로 큰 차이가 없는 듯 했다.

정확히는 240번의 false positive를 줄인 것과 백만번의 해시(비트)연산을 수행하는데 필요한 overhead가 비슷했다.

 

 

그렇다면 최적의 해시 개수와 실제 사용 개수가 비슷한 9bits, 12bits를 사용한다면 

성능면에서 어떠한 차이가 있는지 측정해보았고, 결과는 다음과 같았는데

12bits + 8 hash의 경우 false positive의 발생 확률은 대폭 줄었으나 

추가적인 bloom bits 2MB와 2백만번의 해시 연산때문에  

읽기 성능은 아주 약간 좋아진 반면 쓰기 성능이 크게 떨어졌다.

 

 

 

똑같은 6 hashes에 각각 9 bits와 10 bits를 사용한 결과 예상외의 결과였는데,

오히려 읽기 성능이 떨어졌다.

최적의 해시 개수에 가까울수록 좋은 성능이 나올 것이라 예상했는데, 이는 내 실수로

최적의 해시 개수는 bits-per-key 이 정해졌을때 해당 값에 대한 최적의 개수였고,

반대로 해시 개수가 정해져있다면 bits-per-key 값은 클수록 성능이 좋아졌다.

 

 비록 성능적인 개선을 얻지는 못했지만, 다음과 같은 결론들을 얻을 수 있었다.

 

 

https://sslab.dankook.ac.kr/leveldb-wiki/

LevelDB WIKI – System Software Lab.

그리고 지금까지 조사한 내용들을 정리한 WIKI