Karen
8k
2017-07-17 18:02:23.0 작성 2017-07-17 18:03:49.0 수정됨
0
1023

달달 맵싹! 양파의 개발 이야기 - HyperLogLog & T-Digest


HyperLogLog & T-Digest


가게에 손님이 몇 명 왔나 세어 본다고 하자. 문이 열릴 때마다 사진을 찍는다 하면 당연히 사장님이나 직원들 얼굴은 여러 번 보일 것이다.

그러므로 반복 빼고 몇 명이 가게에 들어 왔나 세면 이것이 distinct count 이다.


문에 앉아서 이걸 세고 있다고 하자.

10시에서 11시 사이에 50명이 들어 왔는데 distinct count 는 30명이다. 그러면 공책에 30명이라고 적는다. 


11시에서 12시 사이는? 한 명이 들어올 때마다 이전에 들어 왔던 사람인지 아닌지를 확인해야 한다.

30명 정도라고 해도 좀 걸릴 텐데, 지난 한 시간에 500명이 들어왔다면, 500명 사진과 하나하나 대조하는 건 일이 엄청나게 많아진다.


그래서 정확한 distinct count 가 아닌, 대강 짐작하는 알고리듬이 쓰이는데 우리 팀에서는 HyperLogLog 를 쓴다.

정확한 distinct count 를 얻으려면 모든 사람의 사진을 다 메모리에 로드해 놓고 반복을 없애야 하지만, 이 알고리듬을 쓰면 그런 메모리 낭비 없이 대략적으로 때려 맞추는 게 가능하다. 한 2-5% 정도 오차 나는데, 숫자가 크면 클수록 더 정확해진다.



자, 이번에는 들어오는 사람들을 키 순서대로 세운다고 하자.

100명이면 첫 번째 사람이 제일 작고, 99번째 사람은 두 번째로 크다. 80번째 사람이 키가 170 이라면, 80명은 170보다 작다는 말이 된다.

50번째 사람은 딱 중간키이고 (정확하게는 50번째와 51번째 평균이겠으나 뭐 대강 넘어가고) 이 사람을 중간값이라고 하자. 이것을 percentile 이라고 한다. 50th percentile, 99th percentile 뭐 등등.


이것 역시 대상의 숫자가 작으면 그냥 다 세워좋고 재면 되는데, 한 시간에 천 명씩 오가는 역에서 키 퍼센타일을 구하는 건 쉽지 않다. 이런 상황에서 우리 팀은 T-Digest 를 쓴다.



그런데 문제. 퍼센타일 데이터를 시간별, 성별로 적어두었다고 하자. 그런데 그걸 다 합치려면?

그러니까 10시에서 11시 사이에 들어온 사람들의 퍼센타일 데이터는 있다. 주로 초등학생들이라 중간값이 150이고 99%는 160이었다. 조금 지나서는 남자 고등학생들이 왕창 들어왔기 때문에 중간값이 167 이고 99%은 183이었다.

그럼 이 두 그룹을 합하면 99% 이 무엇일까? 160 + 183 해서 둘로 나누면 안 되겠죠. (라고 하지만 이렇게 계산하는 상도의 상실한 곳도 있어요!! 헉!!)


T-Digest 는 퍼센타일 데이터를 저장해둔 리스트를 합칠 때 K-way 소트를 쓴다. 그런데 데이터 사이즈가 너무 크니까 엄청 느렸다.

그래서 원 저자 컨택해서 이런 저런 방법을 써서 두 배로 속도 올렸다는데 그래도 역부족.

결국은 데이터 저장 방법을 바꾸기로 결정했다네.


자, 여기서 데이터 엔지니어링데이터 사이언스가 갈라진다.

데이터 만지는 사람으로서는 그 알고리듬이 제대로 된 데이터를 뱉어 내면 거기서 상관 끝이고, 데이터 엔지니어링은 그 데이터 처리가 효과적으로 될 수 있도록 시스템을 뜯어 고친다.



요약 정리.

스트리밍 데이터 처리 할 때 distinct count estimation 에는 hyperloglog.

Percentile 은 T-Digest.

데이터 처리 속도 걱정은 데이터 엔지니어링.

데이터 정확한가, 이게 무슨 의미인가는 데이터 사이언스.



by Yangpa : https://www.facebook.com/londonyangpa/posts/1867849263500552


1
0
  • 댓글 0

  • 로그인을 하시면 댓글을 등록할 수 있습니다.