예전에 회사에서 일할 때, 초당 30만건 정도 들어오는 자료의 빈도를 세서 누적 데이터를 기준으로 5분, 1시간, 1일, 1주, 1달, 1년 최다 순서로 100개 정도씩을 보여주는 루틴을 만들 일이 있었습니다. 그 때는 뭐 회사 프로젝트도 검수 기간도 다 끝나고 영 제값 못 받고 한다고 생각하는 프로젝트였기 때문에, 그냥 대충 가장 단순하게 막 구현을 했더니 오방 느려서 하드웨어빨로 버티고 있었습니다. 나중에는 각 샘플링 별로 상위 10배수를 뽑아서 나머지를 버리는 등의 튜닝을 약간 해서, 처리속도가 데이터 들어오는 것을 못 따라가는 문제를 약간 해결해야하긴 했습니다. 🙂
물론 이렇게 하면, 정확한 이산 데이터를 합해서 하기 때문에 아주 정확한 자료를 얻을 수 있다는 장점은 있지만, 통계 기간에 들어가는 샘플의 수가 워낙 많기 때문에 속도의 문제나 기간의 제한 등 여러가지 문제가 산적해 있었습니다. 특히 가장 문제는, 샘플 저장 수를 줄이기 위해서 장기간의 통계용 샘플들은 정밀도를 줄여서 5분 데이터를 모두 모아서 1시간 데이터로 만드는 등의 작업을 거치기 때문에, 업데이트가 바로바로 되지 않는 문제가 있었습니다. 그래서, 그때는 그냥 뭐 병특도 끝나가고 해서 대충 넘어 갔는데 -ㅇ-, 얼마전에 여자친구 숙제를 도와주다가, 커널에서 load average 계산하는 방법을 보고서 이것을 게시판의 “최근 뜨거운 글 100개 목록”이나, 네트워크 장비들의 “최근 다발 접속 IP 100개” 같은 통계에 쓰면 좋겠다는 생각이 들었습니다. +_+ 벌써 다른 데서는 다 쓰고 있었는지도 모르겠지만; 이렇게 되면 보통 하듯이 하루 단위로 리셋되지 않고 부드럽게 꾸준히 업데이트되기 때문에 비교적 부하를 줄이면서도 쓸만한 데이터를 얻을 수 있지 않을까 싶네요~
그래서, 그 방법이 무엇이냐!
간단히 요약해서 다음 수식으로~
커널 소스코드에서는 sys/kern/kern_synch.c 부분에 있습니다.
x가 로드이고, s가 새로 들어오는 샘플, window가 원하는 통계 기간의 샘플 수 입니다. 이렇게 하게 되면, 새로 들어오는 샘플은 1-1/exp(1/window) 의 비율로 들어가고 그 다음부터는 1/exp(1/window)가 계속 곱해져서 살짜쿵씩 사그라듭니다. 적당히 원하는 보존 기간을 지나가면 무시할 수 있을 만큼의 비율로 없어지기 때문에, 데이터 값 1개만 유지하고서도 이산형 데이터 모두를 저장하는 부담을 줄일 수 있다는 점에서 그런대로 쓸만한 방법인 것 같네요. +_+
그래서, 과연 이 놈이 진짜로는 어떻게 없어지나 그래프를 한 번 그려 봤습니다. (x 축이 축적 횟수, y축이 최종 데이터의 반영 비율, 샘플 누적 목표는 10으로 했을 때)
그래서 대략 계산해 보면, 10개까지의 데이터들의 반영 비율이 63% 정도 되고, 2배수인 20개까지의 비율의 합이 86%정도 됩니다.
정확한 데이터는 아니지만, 데이터 계산을 연속적으로 할 수 있고 연산/저장량이 많이 줄어든다는 점이 장점이겠습니다.
그런데, 커널에서는 부동소수점 연산을 피하기 때문에, 이런 계산을 좀 더 재미있는 방법으로 하고 있는데, 이것도 한 번 눈여겨 볼 만합니다. 🙂 커널 소스의 cexp라는 fixpt_t형 배열에는 exp(-1/샘플수)의 값이 미리 계산이 되어 있어서 그냥 곱하기만 하면 되게 되어있기 때문에 e 계산이나 나누기를 하지 않아도 됩니다. 그리고, 사실은 이놈이 부동소수점형이 아니라, CPU에서는 정수형으로 취급되는 고정소수점형이라는 것~ 32비트 중에서 왼쪽 21비트를 정수영역, 나머지 11비트를 소수점영역으로 쓰는데, 1<<11 * 소수 이렇게 하면 간단하게 소수점 이하라도 쉽게 변환이 되고, 덧셈 뺄셈도 생각해 보면 그냥 정수 덧셈,나눗셈 인스트럭션으로 될 것을 알 수 있습니다. 그리고, 곱셈도 가능한데 둘을 곱한 다음에 소수 영역 길이인 11비트만 오른쪽으로 시프트 해주면 고정소수점 곱하기 한 것처럼 됩니다. (물론, 손으로 써보면 쉽게 증명이 됩니다. 🙂 후배한테 자랑했더니 요새는 학교에서 이런 것도 가르쳐 준다는군요 -.-;)
뭐 하여간.. 전에 회사에서 바쁘던 와중에 검색을 할 때는 좋은 아이디어가 딱히 안 떠오르고, 검색을 해 봐도 딱히 좋은 알고리즘이 안 떠올랐는데, 계속 곱하기만 해도 줄어든다는 것을 떠올리지 못한 것은.. 아무래도 수학 공부를 안 해서일까요 -.-a 그래서 이번 학기에 공수 불끈! +_+
