Redis

읽고 쓰는게 기존 RDBMS와 비교해서 월등하게 빠르다.

이것은 누구나 인정하는 Redis의 가장 큰 장점입니다. 그리고 두 번째 장점은 랭킹 구현을 쉽게 할 수 있는 데이터모델을 지원한다는 것입니다. 쉽게 저장하고 불러올 수 있는 랭킹을 직접 구현하기는 매우 어려운데, Redis는 설치만 하면 바로 랭킹 모델로 저장하고 보여줄 수 있습니다.

Redis는 출시한 지 5년도 안되서 전세계에서 가장 많이 사용하는 데이터베이스 10위 안에 들었고, 꾸준히 사용량이 늘고 있습니다.

지금은 대규모 백엔드 시스템에서 Redis와 같은 메모리DB는 거의 필수적으로 사용되고 있습니다. 대규모 시스템에서 콘텐츠를 실시간으로 제공해 줄 수 있는 DB를 빠르게 구축할 때 Redis보다 좋은 대안은 사실 없다고 생각합니다.

2009년 이탈리아의 ‘살바토르 산필리포’는 Mysql로 통계 작업을 하던중 너무 느려서 Redis를 개발했다고 합니다. (출처: 위키백과 https://ko.wikipedia.org/wiki/%EB%A0%88%EB%94%94%EC%8A%A4) 빠른 서버를 만든다는 목표에 집중해서 고정관념을 깨고 접근했기 때문에 Redis와 같은 결과물을 얻었던 건 아닐까 생각해봅니다.

지금까지 10년 넘게 창시자이자 레디스 프로젝트의 BDFL (Benevolent Dictator for Life) 이었던 살바토르는 며칠 전에 BDFL자리에서 물러난다고 했습니다. 이제 Redis가 어떤 방향으로 발전할 지 궁금해지네요.

구글에서 ‘Redis’라고 검색해보면 데이터모델 소개와 사용법에 관해서 엄청나게 많은 자료를 볼 수 있으니, Redis에 관한 소개는 여기까지 하겠습니다.

HyperLogLog

메모리와 시간 비용을 획기적으로 줄일 수 있는 알고리즘

HyperLogLog는 2007년 Philippe Flajolet가 발표한 알고리즘입니다. HyperLogLog라는 이름은 이전 알고리즘인 Loglog Counting을 발전시켰기 때문에 Hyper를 붙친것입니다. (출처: redisgate http://redisgate.kr/redis/command/hyperloglog.php)

하루에 접속하는 사용자 수가 100만명이라고 하면, 100만명을 추려내기 위해 엄청난 크기의 데이터를 분석해서 정확히 100만명을 얻을 수도 있습니다. 정확한 값이 필요한 계산이라면 시간과 비용이 많이 들더라도 중복된 값을 제거하고 모두 카운팅을 해야 합니다.

하지만 저는 101만명인지 99만300명인지 이 정도 정확한 숫자는 필요없고, 어느정도 신뢰할 만한 범위의 100만이라는 숫자를 알고 싶습니다. 이렇게 어느정도 오차를 허용하는 카운팅을 할 때 메모리와 시간 비용을 획기적으로 줄일 수 있는 알고리즘이 HyperLogLog입니다. 카운팅에 필요한 리소스를 몇 천분의 일 정도로 줄이는 건 일도 아닙니다.

이 알고리즘의 핵심은 비트 패턴 분석을 기반으로 확률을 추정한다는 겁니다. 예를들어 8자리 2진수 00000000 ~ 11111111 중에 하나를 랜덤으로 받는다고 해보죠. 첫 숫자로 00110100을 받았습니다. 이렇게 반복해서 계속 숫자를 받습니다. 앞자리 1~2개 비트가 연속으로 0일 확률은 높지만 5개 이상 연속일 확률은 낮습니다. 5개 이상 연속된 0를 받았다는 건 그 희귀한 비트 패턴이 나올만큼 많은 수를 받았을 확률이 높습니다.

다른 예로 로또복권을 매주 사는 사람들에게 로또 5등에 당첨된 적이 몇 번이나 있는지 설문조사를 한다고 가정해 봅니다. 누군가의 계산에 의하면 5등 당첨확률은 약 1/44 라고 합니다.

당첨 횟수로 구매횟수를 추정할 수 있지 않을까요? 그런데 엄청나게 운좋은 사람들을 처음에 많이 만나서 실제로 사람들이 50개 밖에 안 샀는데 2000개 쯤 샀다고 잘못 추정할 수도 있습니다. 이런 문제점을 해결을 위해 사람들을 그룹으로 나눠서 평균을 분산시켜 계산합니다.

보다 자세한 내용은 https://d2.naver.com/helloworld/711301 를 참고하시면 많은 도움을 받으실 수 있습니다.

Redis에서 이 알고리즘을 사용하면 숫자가 백만이든 천만이든 상관없이 12kb의 용량만 사용하고 약 0.81% 오차로 근사값을 얻을 수 있습니다. 조회 속도는 물론 빠르고요. 하지만 데이터를 저장하지 않고 카운트하기만 합니다.

최근 HyperLogLog 알고리즘의 개선된 버전도 나왔다는 얘기를 들었습니다. 다음 포스팅에서는 개선된 버전의 확률 추정 원리에 대해서 설명하는 글을 쓰도록 하겠습니다.

감사합니다.