이 게시물은 제 생각에 세계에서 가장 흥미로운 두 가지, 즉 확률적 데이터 구조와 Redis 모듈에 관한 것입니다. 하나 또는 다른 것에 대해 들어 본 적이 있다면 내 열정에 확실히 공감할 수 있지만 지구상에서 가장 멋진 내용을 따라 잡고 싶다면 계속 읽으십시오.
이 진술부터 시작하겠습니다. 대기 시간이 짧은 대규모 데이터 처리는 어렵습니다. 관련된 데이터의 양과 속도로 인해 실시간 분석이 매우 까다로울 수 있습니다. Redis는 고성능과 다용성으로 인해 일반적으로 이러한 문제를 해결하는 데 사용됩니다. 밀리초 미만의 대기 시간으로 여러 형태의 데이터를 저장, 조작 및 제공하는 기능은 온라인 계산이 필요한 많은 경우에 이상적인 데이터 컨테이너가 됩니다.
그러나 모든 것은 상대적이고 정확한 실시간 분석이 현실적으로 불가능할 정도로 극단적인 척도가 있다. 복잡한 문제는 커질수록 더 어려워지지만, 우리는 단순한 문제가 같은 규칙을 따른다는 사실을 잊어버리는 경향이 있습니다. 데이터가 너무 크거나, 너무 빠르거나, 처리할 리소스가 충분하지 않으면 숫자를 더하는 것과 같은 기본적인 작업도 기념비적인 작업이 될 수 있습니다. 리소스는 항상 유한하고 비용이 많이 들지만 데이터는 아무나 할 수 없는 일처럼 계속해서 증가하고 있습니다.
카운트민 스케치란 무엇인가요?
Count-min 스케치(CM 스케치라고도 함)는 작동 방식과 더 중요한 사용 방법을 이해하면 매우 유용한 확률적 데이터 구조입니다.
다행히도 CM 스케치의 간단한 특성은 초보자가 비교적 쉽게 이해할 수 있도록 합니다(많은 친구들이 이 Top-K 블로그를 따라하지 못한 것으로 나타났습니다).
CM 스케치는 몇 년 동안 Redis 모듈이었으며 최근 RedisBloom 모듈 v2.0의 일부로 다시 작성되었습니다. 하지만 CM 스케치에 대해 알아보기 전에 any를 사용하는 이유를 이해하는 것이 중요합니다. 확률 데이터 구조. 속도, 공간 및 정확도의 삼각형에서 확률적 데이터 구조는 공간을 확보하기 위해 약간의 정확도를 희생합니다(잠재적으로 많은 공간). ! 속도에 미치는 영향은 알고리즘 및 설정 크기에 따라 다릅니다.
- 정확도 :정의에 따라 데이터의 일부만 유지하고 저장소에서 충돌을 허용하면 정확도가 떨어집니다. 그러나 사용 사례에 따라 최대 오류율을 설정할 수 있습니다.
- 메모리 공간 :수십억 건의 이벤트가 기록되는 빅 데이터의 세계에서 일부 데이터만 저장하면 저장 공간 요구 사항과 비용을 크게 줄일 수 있습니다.
- 속도 :특정 기존 데이터 구조는 상대적으로 비효율적으로 작동하여 응답 시간이 느려집니다. (예를 들어 Sorted Set은 모든 요소의 순서를 유지하지만 상위 요소에만 관심이 있을 수 있습니다. 확률 알고리즘은 일부 목록만 유지하므로 더 효율적이고 종종 쿼리에 훨씬 빠르게 응답할 수 있습니다.
올바른 확률적 데이터 구조를 사용하면 정확도를 낮추는 대신 데이터 세트에 정보의 일부만 유지할 수 있습니다. 물론 많은 경우(예:은행 계좌) 정확도가 떨어지는 것은 용납할 수 없습니다. 그러나 웹사이트 사용자에게 영화를 추천하거나 광고를 표시하는 경우 비교적 드문 실수로 인한 비용이 낮고 공간 절약이 상당할 수 있습니다.
기본적으로 CM 스케치는 데이터 세트의 모든 항목 수를 여러 카운터 배열로 집계하여 작동합니다. 쿼리 시 모든 배열의 항목 최소 개수를 반환하여 충돌로 인한 개수 팽창을 최소화합니다. 출현율이나 점수가 낮은 항목("마우스 흐름")은 오류율 미만입니다. , 따라서 실제 개수에 대한 모든 데이터가 손실되고 노이즈로 처리됩니다. 출현율이나 점수가 높은 항목("코끼리 흐름")의 경우 수신된 개수를 사용하면 됩니다. CM 스케치의 크기가 일정하고 무한한 아이템에 사용할 수 있다는 점을 고려할 때 저장 공간을 크게 절약할 수 있는 가능성을 볼 수 있습니다.
배경으로, 스케치는 데이터 구조의 클래스와 그에 수반되는 알고리즘입니다. 상수 또는 준선형 공간을 사용하는 동안 데이터에 대한 질문에 답하기 위해 데이터의 특성을 캡처합니다. CM 스케치는 Graham Cormode와 S. Muthu Muthukrishnan이 “이라는 2005년 논문에서 설명했습니다. 개선된 데이터 스트림 요약:Count-Min Sketch 및 해당 응용 프로그램.”
카운트-민 스케치:무엇과 어떻게
CM 스케치는 기본 사용 사례를 지원하기 위해 여러 카운터 어레이를 사용합니다. 배열의 수를 "깊이"라고 하고 각 배열의 카운터 수를 "너비"라고 합시다.
항목을 받을 때마다 해시 함수(단어, 문장, 숫자 또는 이진 요소를 집합/배열의 위치 또는 지문으로 사용할 수 있는 숫자로 변환)를 사용하여 계산합니다. 항목의 위치를 확인하고 각 배열에 대해 해당 카운터를 늘립니다. 연관된 각 카운터는 항목의 실제 값과 같거나 더 높은 값을 갖습니다. 조회할 때 동일한 해시 함수를 가진 모든 배열을 살펴보고 항목과 관련된 카운터를 가져옵니다. 그런 다음 값이 부풀려졌거나 같으므로 발생한 최소값을 반환합니다.
많은 항목이 대부분의 카운터에 기여한다는 것을 알고 있지만 자연 충돌(다른 항목이 동일한 위치를 수신하는 경우) 때문에 원하는 오류율 내에서 '노이즈'를 허용합니다.
Count-min 스케치 예시
수학에 따르면 깊이가 10이고 너비가 2,000일 때 오류가 없을 확률은 99.9%이고 오류율은 0.1%입니다. (이것은 고유 항목이 아닌 총 증가분의 백분율입니다.)
실제 숫자로 말하자면, 100만 개의 고유한 항목을 추가하면 평균적으로 각 항목에 500(1M/2K)의 가치가 부여됩니다. 과도하지 않은 것처럼 보이지만 이는 100만 항목에 1,000인 오류율 0.1%에 잘 맞습니다.
마찬가지로, 10마리의 코끼리가 각각 10,000번 나타난다면 모든 세트의 값은 10,000개 이상이 됩니다. 우리가 미래에 그것들을 셀 때마다, 우리는 우리 앞에 코끼리를 보게 될 것입니다. 다른 모든 숫자(즉, 실제 카운트가 1인 모든 마우스)의 경우, 이러한 일이 일어날 확률이 희박하고 다음과 같은 경우 더 줄어들기 때문에 모든 세트에서 코끼리와 충돌할 가능성이 없습니다(CM 스케치는 최소 카운트만 고려하기 때문에). CM 스케치를 초기화하면서 깊이를 늘립니다.
Count-min Sketch의 장점은 무엇인가요?
이제 CM 스케치의 동작을 이해했으므로 이 작은 짐승으로 무엇을 할 수 있습니까? 다음은 몇 가지 일반적인 사용 사례입니다.
- 두 숫자를 쿼리하고 숫자를 비교합니다.
- 수신 항목의 비율을 설정합니다(예:1%). 항목의 최소 개수가 총 개수의 1%보다 높을 때마다 true를 반환합니다. 예를 들어 온라인 게임의 최고 플레이어를 결정하는 데 사용할 수 있습니다.
- CM 스케치에 최소 힙을 추가하고 Top-K 데이터 구조를 만듭니다. 항목을 늘릴 때마다 새로운 최소 수가 힙의 최소값보다 높은지 확인하고 그에 따라 업데이트합니다. 시간이 지남에 따라 점차적으로 소멸되는 RedisBloom의 Top-K 모듈과 달리 CM 스케치는 절대 잊지 않기 때문에 동작이 HeavyKeeper와 약간 다릅니다. 기반 Top-K.
RedisBloom에서 CM 스케치용 API는 간단하고 쉽습니다.
- CM 스케치 데이터 구조를 초기화하려면:INITBYDIM {키 } {너비 } {깊이 } 또는 CMS.INITBYPROB {키 } {오류 } {확률 }
- 항목의 카운터를 늘리려면:CMS.INCRBY {키 } {항목 } {증가 }
- 항목 카운터에서 찾은 최소 개수를 얻으려면:CMS.QUERY {key } {항목 }
이 게시물 상단에 애니메이션 예제를 만드는 데 다음 명령이 사용되었습니다.
보시다시피 'Redis'의 값은 3이 아닌 4입니다. 이 동작은 CM 스케치에서 항목의 개수가 부풀려질 가능성이 있기 때문에 예상되는 동작입니다.
간략한 사업
소프트웨어 엔지니어링은 모두 절충점을 만드는 것이므로 비용 효율적인 방식으로 이러한 문제를 해결하기 위한 일반적인 접근 방식은 효율성을 위해 정확성을 포기하는 것입니다. 이 접근 방식은 Redis의 HyperLogLog 구현으로 예시됩니다. HyperLogLog는 설정된 카디널리티에 대한 쿼리에 대한 답변을 효율적으로 제공하도록 설계된 데이터 구조입니다. HyperLogLog는 실제 예술 작품과 마찬가지로 주제의 근사치를 통해 정보를 전달하는 "스케치"라는 데이터 구조 제품군의 구성원입니다.
넓은 의미에서 스케치는 데이터 자체를 실제로 저장하지 않고 데이터에 대한 질문에 대한 답변인 데이터의 특성을 캡처하는 데이터 구조(및 그에 수반되는 알고리즘)입니다. 공식적으로 설명하면 스케치는 선형 점근적 계산 복잡성을 가지므로 계산 능력 및/또는 저장 공간이 덜 필요하기 때문에 유용합니다. 그러나 무료 점심은 없으며 효율성의 이득은 답변의 정확성에 의해 상쇄됩니다. 그러나 많은 경우에 오류는 임계값 미만으로 유지될 수 있는 한 허용됩니다. 좋은 데이터 스케치는 오류를 쉽게 인정하는 스케치이며, 실제로 많은 스케치가 오류(또는 해당 오류의 확률)를 매개변수화하여 사용자가 정의할 수 있도록 합니다.
좋은 스케치는 효율적이고 오류 확률이 제한되어 있지만 우수한 스케치는 병렬로 계산할 수 있는 스케치입니다. 병렬화 가능한 스케치는 데이터의 일부에 대해 독립적으로 준비할 수 있고 해당 부분을 의미 있고 일관된 집계로 결합할 수 있는 스케치입니다. 훌륭한 스케치의 각 부분은 다른 위치 및/또는 시간에서 계산될 수 있기 때문에 병렬 처리를 사용하면 확장 문제를 해결하기 위해 간단한 분할 정복 접근 방식을 적용할 수 있습니다.
자주 발생하는 문제
앞서 언급한 HyperLogLog는 훌륭한 스케치이지만 특정 유형의 질문에 답하는 데에만 적합합니다. 또 다른 귀중한 도구는 G. Cormode 및 S. Muthukrishnan의 "개선된 데이터 스트림 요약:Count-Min 스케치 및 해당 응용 프로그램"에 설명된 대로 Count Min Sketch(CMS)입니다. 이 독창적인 장치는 많은 분석 프로세스에서 공통 구성 요소인 샘플의 빈도에 대한 답을 제공하기 위해 고안되었습니다.
충분한 시간과 자원이 주어지면 샘플의 빈도를 계산하는 것은 간단한 프로세스입니다. 각 샘플(본 것)에 대한 관찰 횟수(본 횟수)를 유지한 다음 이를 총 관찰 횟수로 나누어 해당 샘플의 빈도를 얻으면 됩니다. 그러나 대기 시간이 짧은 대규모 데이터 처리의 맥락을 고려할 때 시간이나 리소스가 충분하지 않습니다. 응답은 규모에 관계없이 데이터가 유입되는 즉시 제공되어야 하며 샘플링 공간의 크기 때문에 각 샘플에 대한 카운터를 유지하는 것이 불가능합니다.
따라서 각 샘플을 정확하게 추적하는 대신 빈도를 추정해 볼 수 있습니다. 이에 대한 한 가지 방법은 관찰을 무작위로 샘플링하고 샘플이 일반적으로 전체의 속성을 반영하기를 바라는 것입니다. 이 접근 방식의 문제는 진정한 무작위성을 보장하는 것이 어려운 작업이므로 무작위 샘플링의 성공은 선택 프로세스 및/또는 데이터 자체의 속성에 의해 제한될 수 있다는 것입니다. 이것이 바로 CMS가 접근 방식이 근본적으로 달라서 처음에는 훌륭한 스케치의 반대처럼 보일 수 있는 이유입니다. CMS는 각각의 모든 관찰을 기록할 뿐만 아니라 각 관찰을 여러 카운터에 기록합니다!
물론 반전도 있고 단순한 만큼 영리하다. 원본 논문(및 "Approximating Data with the Count-Min Data Structure"라는 더 가벼운 버전)은 설명을 잘 하지만 어쨌든 요약하려고 합니다. CMS의 영리함은 샘플을 저장하는 방식에 있습니다. 각 고유 샘플을 독립적으로 추적하는 대신 해시 값을 사용합니다. 샘플의 해시 값은 카운터의 일정한 크기(문서에서 d로 매개변수화됨) 배열에 대한 인덱스로 사용됩니다. 여러(매개변수 w) 다른 해시 함수와 해당 배열을 사용하여 스케치는 샘플에 대한 모든 관련 카운터에서 최소값을 선택하여 구조를 쿼리하는 동안 발견된 해시 충돌을 처리합니다.
예제가 필요하므로 데이터 구조의 내부 작동을 설명하기 위해 간단한 스케치를 만들어 보겠습니다. 스케치를 단순하게 유지하기 위해 작은 매개변수 값을 사용합니다. w를 3으로 설정합니다. 즉, 각각 h1, h2 및 h3으로 표시된 3개의 해시 함수를 사용하고 d를 4로 지정합니다. 스케치의 카운터를 저장하기 위해 총 12개의 3×4 배열을 사용합니다. 0으로 초기화된 요소.
이제 스케치에 샘플을 추가할 때 어떤 일이 발생하는지 조사할 수 있습니다. 샘플이 하나씩 도착하고 s1로 표시된 첫 번째 샘플의 해시가 h1(s1) =1, h2(s1) =2 및 h3(s1) =3이라고 가정해 보겠습니다. 스케치에 s1을 기록하려면 '는 관련 인덱스에서 각 해시 함수의 카운터를 1씩 증가시킵니다. 다음 표는 배열의 초기 및 현재 상태를 보여줍니다.
스케치에 샘플이 하나만 있지만 이미 효과적으로 쿼리할 수 있습니다. 샘플에 대한 관측값의 수는 모든 카운터의 최소값이므로 s1의 경우 다음과 같이 얻습니다.
min(array[1][h1(s1)], array[2][h2(s1)], array[3][h3(s1)]) = 스케치는 또한 아직 추가되지 않은 샘플에 대한 질문에 답변합니다. h1 (s2 ) =4, h2 (s2 ) =4, h3 (s2 ) =4, s2 쿼리 결과는 0을 반환합니다. 계속해서 s2를 추가해 보겠습니다. 그리고 s3 (h1 (s3 ) =1, h2 (s3 ) =1, h3 (s3 ) =1) 스케치에 다음을 생성합니다.
min(array[1][1], array[2][2], array[3][3]) =
min(1,1,1) = 1
우리가 고안한 예에서 거의 모든 샘플의 해시는 고유 카운터에 매핑되지만 한 가지 예외는 h1(s1)과 h1(s3)의 충돌입니다. 두 해시가 동일하기 때문에 h1의 첫 번째 카운터는 이제 값 2를 유지합니다. 스케치가 모든 카운터의 최소값을 선택하기 때문에 s1 및 s3에 대한 쿼리는 여전히 1의 올바른 결과를 반환합니다. 그러나 결국 충분한 충돌이 발생하면 발생하면 쿼리 결과가 덜 정확해집니다.
CMS의 두 매개변수인 w와 d는 공간/시간 요구 사항과 오류 확률 및 최대값을 결정합니다. 스케치를 초기화하는 보다 직관적인 방법은 오류의 확률과 상한선을 제공하여 w 및 d에 필요한 값을 도출할 수 있도록 하는 것입니다. 동일한 매개변수와 해시 함수를 사용하여 구성하는 한 여러 하위 스케치를 배열의 합으로 간단하게 병합할 수 있으므로 병렬화가 가능합니다.
Count-min 스케치에 대한 몇 가지 관찰
Count Min Sketch의 효율성은 요구 사항을 검토하여 입증할 수 있습니다. CMS의 공간 복잡도는 w, d 및 사용하는 카운터 너비의 곱입니다. 예를 들어, 0.01%의 확률에서 0.01%의 오류율을 갖는 스케치는 10개의 해시 함수와 2000개의 카운터 배열을 사용하여 생성됩니다. 16비트 카운터를 사용한다고 가정하면 결과 스케치 데이터 구조의 전체 메모리 요구 사항은 40KB로 클럭됩니다(총 관찰 수와 몇 개의 포인터를 저장하려면 몇 바이트가 추가로 필요합니다). 스케치의 다른 계산 측면도 마찬가지로 만족스럽습니다. 해시 함수는 생성 및 계산이 저렴하기 때문에 읽기 또는 쓰기를 위해 데이터 구조에 액세스하는 것도 일정한 시간에 수행되기 때문입니다.
CMS에는 더 많은 것이 있습니다. 스케치의 저자는 또한 다른 유사한 질문에 답하기 위해 스케치가 어떻게 사용될 수 있는지 보여주었습니다. 여기에는 백분위수 추정 및 헤비히터(빈번한 항목) 식별이 포함되지만 이 게시물의 범위를 벗어납니다.
CMS는 확실히 훌륭한 스케치이지만 완벽을 달성하는 데 방해가 되는 요소가 적어도 두 가지 있습니다. CMS에 대한 나의 첫 번째 유보 사항은 편향되어 적은 수의 관찰로 샘플의 빈도를 과대평가할 수 있다는 것입니다. CMS의 편견은 잘 알려져 있으며 몇 가지 개선 사항이 제안되었습니다. 가장 최근의 것은 Count Min Log Sketch(G. Pitel 및 G. Fouquier의 "대략적인 카운터로 대략적으로 계산")로, 기본적으로 CMS의 선형 레지스터를 로그 레지스터로 대체하여 상대적 오류를 줄이고 너비를 늘리지 않고도 더 많은 수를 허용합니다. 카운터 레지스터 수.
위의 예약은 모든 사람이 공유하지만(비록 데이터 구조를 이해하는 사람들만), 제 두 번째 예약은 Redis 커뮤니티 전용입니다. 설명하기 위해 Redis 모듈을 소개해야 합니다.
Redis 모듈
Redis 모듈은 올해 초 RedisConf에서 antirez에 의해 공개되었으며 말 그대로 세상을 뒤집어 놓았습니다. 서버에서 로드할 수 있는 동적 라이브러리에 불과한 모듈을 사용하면 Redis 사용자가 Redis 자체보다 빠르게 이동하고 이전에는 꿈도 꾸지 못한 곳으로 이동할 수 있습니다. 이 게시물은 모듈이 무엇인지 또는 모듈을 만드는 방법에 대한 소개가 아니지만 이 게시물과 웹 세미나도 마찬가지입니다.
내가 Count Min Sketch Redis 모듈을 작성하고 싶었던 이유는 극도의 유용성 외에도 여러 가지가 있습니다. 그 중 일부는 학습 경험이었고 일부는 모듈 API에 대한 평가였습니다. 그러나 대부분은 새로운 데이터 구조를 Redis로 모델링하는 것이 매우 재미있었습니다. 이 모듈은 스케치에 관찰을 추가하고 쿼리하고 여러 스케치를 하나로 병합하기 위한 Redis 인터페이스를 제공합니다.
이 모듈은 스케치의 데이터를 Redis String에 저장하고 DMA(직접 메모리 액세스)를 사용하여 키 내용을 내부 데이터 구조에 매핑합니다. 아직 완전한 성능 벤치마크를 수행하지는 않았지만 로컬에서 테스트한 첫 인상은 핵심 Redis 명령만큼 성능이 좋다는 것입니다. 다른 모듈과 마찬가지로 countminsketch는 오픈 소스이므로 사용해 보고 해킹하는 것이 좋습니다.
서명하기 전에 약속을 지키고 CMS에 대한 Redis 관련 예약을 공유하고 싶습니다. 다른 스케치 및 데이터 구조에도 적용되는 문제는 CMS가 CMS를 사용하기 전에 설정/초기화/생성하도록 요구한다는 것입니다. CMS 매개변수 설정과 같은 필수 초기화 단계를 요구하면 Redis의 기본 패턴 중 하나가 깨집니다. 데이터 구조는 주문형으로 생성할 수 있으므로 사용 전에 명시적으로 선언할 필요가 없습니다. 모듈을 좀 더 Redis-ish로 보이게 하고 해당 패턴 방지를 해결하기 위해 모듈은 새 스케치가 암시적으로 암시될 때 기본 매개변수 값을 사용하지만(즉, 존재하지 않는 키에 CMS.ADD 명령 사용) 새 스케치를 생성할 수도 있습니다. 주어진 매개변수가 있는 빈 스케치.
확률적 데이터 구조 또는 스케치는 효율적이고 충분히 정확한 방식으로 빅 데이터의 증가와 대기 시간 예산의 축소를 따라잡을 수 있는 놀라운 도구입니다. 이 게시물에서 언급한 두 가지 스케치와 Bloom Filter 및 T-digest와 같은 다른 스케치는 현대 데이터 상인의 무기고에서 빠르게 없어서는 안될 도구가 되고 있습니다. 모듈을 사용하면 기본 속도로 작동하고 데이터에 대한 로컬 액세스 권한이 있는 사용자 지정 데이터 유형 및 명령으로 Redis를 확장할 수 있습니다. 가능성은 무한하며 불가능한 것은 없습니다.
Redis 모듈과 개발 방법에 대해 자세히 알고 싶으십니까? Redis에 대해 논의하거나 추가하고 싶은 데이터 구조가 확률적이든 아니든 간에? 내 Twitter 계정이나 이메일을 통해 무엇이든 자유롭게 연락하세요.