Box and Whisker

Optimize the World

해시 기반 샘플링

해시함수를 이용하여 데이터 스트림에서 실시간 샘플링을 수행하는 방법을 소개하고자 한다.

문제 상황

시간, 사용자 ID, 이벤트 종류 세 개의 필드로 구성된 로그 파일이 있다고 가정하자. 이벤트 종류에는 “로그인”과 “로그아웃”만 있다. 다음은 예시:

2014-01-01,00:00:00.000,alan,login
2014-01-01,00:00:00.300,brad,login
2014-01-01,00:00:02.600,alan,logout
2014-01-01,00:01:00.000,alan,login
2014-01-01,00:00:04.000,cate,login
2014-01-01,00:01:05.000,alan,logout
...

이 로그를 분석하여 평균 세션 길이를 구해야 한다고 치자.

세션 길이는 각 사용자에 대하여 login, logout 짝을 찾고 둘 사이의 시간 차이를 계산하여 구할 수 있다. 예를 들어 위 예시에서 alan은 두 번 시스템에 접속했고 세션의 길이는 각각 2.6초와 5.0초이다.

로그 파일이 너무 커서 전체의 0.01%만 샘플링하여 평균 세션 길이를 계산하고 싶으면 어떻게 해야할까?

head, tail?

유닉스 계열 시스템에는 head 또는 tail 명령이 있어서 큰 파일의 앞부분 혹은 뒷부분에서 원하는 정도만 잘라낼 수 있다. 예를 들어 다음 명령을 통해 전체 로그의 0.01%만 샘플링하여 sample.log 파일을 만들어낼 수 있다:

> wc -l original.log
1758375485
> tail -n 175837 original.log > sample.log

하지만 이렇게 하면 특정 시간대의 데이터만 취해질테니 대표성이 없는(치우친) 샘플을 얻게 될 가능성이 크다.

임의 추출

다른 방법으로는 임의 추출(random sampling)을 생각해볼 수 있다.

> cat original.log | python -c 'import sys, random; [sys.stdout.write(line) for line in sys.stdin if random.random() < 0.0001]' > sample.log

이 방법은 0에서 1 사이의 유니폼 의사난수(uniform pseudo-random numbers)를 발생시켜서 해당 값이 0.0001보다 작은 경우(즉 0.01%의 확률) 해당 라인을 선택하는 방식으로 임의 추출을 수행한다. 따라서 head나 tail과 달리 편향이 발생하지 않는다.

하지만 문제는 이렇게 추출을 하면 login 이벤트는 추출되고 logout 이벤트는 추출되지 않거나, 반대로 logout 이벤트만 추출되거나 하는 문제가 발생한다. 예를 들어 위 로그에 대하여 임의 추출한 결과가 아래와 같다면(alan의 로그인/로그아웃 기록이 일부 사라졌다) alan의 평균 세션 길이는 1분 5초로 늘어난다. 하지만 전수 데이터로 계산할 경우 3.8초((2.6 + 5.0) / 2 == 3.8)이다:

2014-01-01,00:00:00.000,alan,login
2014-01-01,00:00:00.300,brad,login
2014-01-01,00:00:04.000,cate,login
2014-01-01,00:01:05.000,alan,logout
...

있던 이벤트가 사라지는 일은 있어도 없던 이벤트가 추가되는 일은 없기 때문에 편향은 항상 세션 길이가 길어지는 방향으로만 발생할 수 밖에 없다. 따라서 임의 추출을 사용해서는 모수를 정확하게 추정하기 어려운 상황이다.

사용자 단위로 마킹하기

이 문제를 없애는 가장 좋은 방법은 사용자 아이디를 단위로 임의 추출을 하는 것이다. 로그 파일에 담겨있는 모든 사용자 아이디를 나열한 후 이 중 0.01%의 아이디만 임의 추출하여 샘플링 대상으로 어딘가에 기록해놓고, 로그 파일을 다시 훑으면서 해당 사용자 아이디의 로그들만 추출을 하면 대체로 0.01%의 로그를 추출할 수 있다.

하지만 이 방법에도 몇 가지 문제가 있다.

우선, 전체 로그 파일을 두 번 훑어야 하기 때문에 비효율적이다. 둘째, 로그 파일이 있는 경우가 아니라 실시간으로 로그 스트림이 들어오는 경우라면 사용자 아이디가 계속 추가되거나 기존 사용자 중 접속을 안하는 사용자가 생길 수 있기 때문에 지속적으로 사용자 아이디 목록을 갱신해주어야 한다.

해시 기반 샘플링

이제 드디어 결론 혹은 본론.

[RFC 5475] Sampling and Filtering Techniques for IP Packet Selection에서 제안하는 해시 기반 샘플링 방식이 이 문제에 대한 좋은 해법이다.

로그에서 사용자 아이디 필드를 해시(hash)하여 숫자로 만들고, 해당 숫자가 지정한 값보다 작으면 선택을 하는 방식(이를 해시 기반 샘플링이라고 부른다)을 사용하는 것이다:

이 방식이 잘 작동하려면 입력값(domain)을 최대한 난잡하게 섞어내는 해시 함수가 필요한데, SpookyHash나 xxHash 같은 것이 이 용도로 쓰기게 적절하다. (단 입력값이 짧을 때 SpookyHash는 xxHash에 비해 쇄도 효과(avalanche effect)가 떨어지는 단점이 있다.)

csample을 설치하고 아래와 같이 사용하면 된다:

> pip install csample
> cat original.log | csample -r 0.0001 -c 2 > sample.log

-r 0.0001은 샘플링 비율 0.0001%를 뜻하고, -c 2는 사용자 아이디가 담겨있는 세번째 칼럼(인덱스는 0에서 시작하므로)을 기준으로 해싱을 하라는 뜻이다.

빅데이터와 샘플링

새로 유행하는 지식이나 도구를 쫓다보면 전에 유익하게 활용해왔던 지식이나 도구들을 잊는 경향이 있는 것 같다. 많은 양의 데이터를 빠르게 처리할 수 있는 빅데이터 기술이 유행하면서 쉽게 간과하게 되는 것 중 하나가 샘플링이 아닌가 싶다.

하지만 데이터의 양이 많아질수록 샘플링의 가치가 커진다는 점을 생각해보면 참 재미있는 아이러니이다. 개인 홈페이지의 로그 데이터를 10% 샘플링한 데이터와 아마존 같은 사이트의 로그 데이터를 1% 샘플링한 데이터로 통계량을 구했을 때, 후자가 모수를 더 정확하게 추정할 수 있다는 얘기다.