프로그래머 수선 의 길 - 우아 하고 빠 른 통계 천만 레벨 uv (댓 글 배달 책)

정의.
PV 는 page view 의 줄 임 말, 즉 페이지 조회 수 로 보통 인터넷 뉴스 채널 이나 사이트, 심지어 인터넷 뉴스 를 평가 하 는 주요 지표 이다.웹 페이지 조회 수 는 웹 사이트 의 트 래 픽 을 평가 하 는 데 가장 자주 사용 되 는 지표 중 하나 로 PV 라 고 약칭 한다.
UV 는 유 니 크 방문 자의 약자 로 인터넷 을 통 해 이 웹 페이지 를 방문 하고 방문 하 는 자연인 을 말한다.
상기 개념 을 통 해 알 수 있 듯 이 pv 는 비교적 좋 은 디자인 이다. 사이트 에 방문 할 때마다 pv 가 증가 하지만 uv 가 반드시 증가 하 는 것 은 아니다. uv 는 본질 적 으로 특정한 기준 에 따라 분 류 된 자연인 을 기록 하 는데 이 기준 은 우리 가 스스로 정의 할 수 있다. 예 를 들 어 같은 IP 의 방문 자 를 같은 UV 로 정의 할 수 있다.이것 도 가장 흔히 볼 수 있 는 uv 정의 중 하나 이 고 쿠키 에 따라 정의 하 는 등 도 있다.pv 든 uv 든 모두 시간 대가 필요 합 니 다. 평소에 우리 가 말 하 는 pv, uv 수량 은 모두 24 시간 이내 (자연 일) 의 데 이 터 를 말 합 니 다.
pv 는 uv 에 비해 기술적 으로 비교적 쉽다. 오늘 우 리 는 uv 의 통 계 를 말 해 보 자. 왜 uv 의 통 계 는 상대 적 으로 어렵다 고 말 하 는 것 일 까? uv 는 같은 기준 에서 자연인 의 무 게 를 제거 하 는 것 과 관련 되 기 때문이다. 특히 uv 천만 등급 의 사 이 트 는 좋 은 uv 통계 시스템 을 설계 하 는 것 이 생각 보다 쉽 지 않 을 것 이다.
그러면 우 리 는 자연 일 을 시간 대 로 하 는 uv 통계 시스템 을 설계 합 니 다. 한 자연인 (uv) 의 정 의 는 같은 소스 IP (물론 다른 기준 도 사용자 정의 할 수 있 습 니 다) 이 고 데이터 등급 은 매일 천만 uv 의 급 으로 가정 합 니 다.
주의: 오늘 우리 가 토론 하 는 중점 은 자연인 정의 정 보 를 얻 은 후에 uv 통계 시스템 을 어떻게 설계 하 느 냐 하 는 것 입 니 다. 자연인 의 정 의 를 어떻게 얻 느 냐 가 아 닙 니 다.uv 시스템 의 디자인 은 상상 만큼 간단 하지 않다. 왜냐하면 uv 는 사이트 의 마 케 팅 전략 에 따라 순간 적 인 트 래 픽 이 발생 할 수 있 기 때문이다. 예 를 들 어 사이트 에서 스톱워치 행 사 를 개최 했다.
DB 기반 프로젝트
서버 프로 그래 밍 에는 시계 가 해결 되 지 않 는 기능 이 하나 도 없고, 있 으 면 시계 두 개, 시계 세 개 라 는 명언 이 있다.하나의 uv 통계 시스템 은 확실히 데이터 베 이 스 를 바탕 으로 실현 할 수 있 고 복잡 하지 않다. uv 통계 의 기록 표 는 다음 과 같다 (아래 표 디자인 이 합 리 적 인지 너무 고민 하지 마라).
필드
유형
묘사 하 다.
IP
varchar(30)
클 라 이언 트 원본 ip
DayID
int
시간의 약자
기타 필드
int
기타 필드 설명
서버 에 요청 이 도착 하면 서버 는 데이터베이스 에 현재 IP 와 현재 시간의 접근 기록 이 있 는 지 한 번 씩 조회 해 야 합 니 다. 있 으 면 같은 uv 임 을 설명 하고 없 으 면 새로운 uv 기록 임 을 설명 하 며 데이터 베 이 스 를 삽입 합 니 다.물론 위의 두 단계 도 하나의 sql 문장 에 쓸 수 있 습 니 다.

if exists( select 1 from table where ip='ip' and dayid=dayid )
　　Begin
　　　　return 0
　　End
else
　　Begin
 　　　 insert into table .......
　　End

데이터 베 이 스 를 기반 으로 하 는 모든 해결 방안 은 데이터 양 이 많은 상황 에서 병목 이 생기 기 쉽다.매일 천만 등급 의 uv 통계 에 직면 하여 데이터 베 이 스 를 바탕 으로 하 는 이런 방안 이 가장 좋 은 것 이 아 닐 수도 있다.
최적화 방안
모든 시스템 의 설계 에 직면 하여 우 리 는 반드시 마음 을 가 라 앉 히 고 구체 적 인 업 무 를 생각해 야 한다.uv 통계 에 대해 이 업 무 는 몇 가지 특징 이 있다.

매번 요청 할 때마다 같은 uv 기록 이 있 는 지 판단 해 야 한다

지속 화 uv 데이터 가 정상 적 인 업무 에 영향 을 주지 못 함

uv 데이터 의 정확성 은 어느 정도 의 오 차 를 참 을 수 있다

해시 시계
데이터 베 이 스 를 바탕 으로 하 는 방안 에서 빅 데 이 터 량 의 상황 에서 성능 의 병목 이 발생 하 는 원인 중 하 나 는 바로 같은 기록 이 존재 하 는 지 판단 하 는 것 이다. 그래서 이 시스템 을 최적화 하려 면 반드시 이 절 차 를 최적화 해 야 한다.요리 의 이전 글 에 따 르 면 이 문 제 를 해결 할 수 있 는 데이터 구 조 를 생각 할 수 있 습 니까? 네, 바로 하 쉬 표 입 니 다.해시 표 는 key 에 따라 value 를 찾 는 시간 복잡 도 는 O (1) 상수 단계 로 같은 기록 을 찾 는 작업 병목 을 완벽 하 게 해결 할 수 있 습 니 다.아마도 uv 데이터 양 이 비교적 적 을 때 해시 표 는 좋 은 선택 일 것 이다. 그러나 천만 단계 의 uv 데이터 양, 해시 표 의 해시 충돌 과 확장, 그리고 해시 표 가 사용 하 는 메모리 가 좋 은 선택 이 아 닐 것 이다.만약 에 해시 표 의 모든 key 와 value 가 10 바이트 를 차지한다 고 가정 하면 1 천만 의 uv 데 이 터 는 약 100 M 을 차지한다. 현대 컴퓨터 에 있어 100 M 은 크 지 않 지만 더 좋 은 방안 이 있 습 니까?
해시 테이블 최적화
해시 표 의 방안 에 따 르 면 천만 급 데 이 터 량 의 경우 겨우 대처 할 수 밖 에 없다. 10 억 원 의 데 이 터 량 이 라면?그럼 10 억 급 데이터 의 uv 통 계 를 해결 할 수 있 는 더 좋 은 방법 이 있 을까요?여기 서 지구 화 데 이 터 를 버 립 니 다. 데이터 베 이 스 를 지속 적 으로 디자인 하 는 분 표 라 이브 러 리 등 최적화 전략 이 있 기 때문에 나중에 다시 이야기 하 겠 습 니 다.10 억 급 uv 에 어떤 기록 이 있 는 지 빨리 판단 할 수 있 는 더 좋 은 방법 은 없 을 까?사용 하 는 메모 리 를 최대한 줄 이기 위해 서 는 bit 형식의 배열 을 미리 할당 할 수 있 습 니 다. 배열 의 크기 는 통계 의 최대 데이터 수량의 배수 입 니 다. 이 배 수 는 사용자 정의 로 조정 할 수 있 습 니 다.현재 시스템 의 uv 최대 데 이 터 량 이 1 천만 이 라 고 가정 하면 시스템 은 길이 가 5 천만 인 bit 배열 을 미리 배정 할 수 있 고 bit 가 사용 하 는 메모리 가 가장 적 으 며 한 자리 만 차지 할 수 있 습 니 다.해시 충돌 이 비교적 작은 해시 함수 에 따라 모든 데이터 의 해시 값 을 계산 하고 bit 배열 에 해당 하 는 해시 값 위 치 를 1 로 설정 합 니 다.해시 함수 가 모두 충돌 하기 때문에 서로 다른 데이터 에 똑 같은 해시 값 이 나타 나 고 오심 이 발생 할 수 있 습 니 다. 그러나 우 리 는 여러 개의 서로 다른 해시 함수 로 같은 데 이 터 를 계산 하여 서로 다른 해시 값 을 만 들 수 있 습 니 다. 또한 이 여러 개의 해시 값 의 배열 위 치 를 모두 1 로 설정 하여 오심 율 을 크게 줄 일 수 있 습 니 다.방금 새로 만 든 배열 이 최대 데이터 의 배수 인 것 도 충돌 을 줄 이기 위 한 방식 이다 (용량 이 클 수록 충돌 이 적다).1 천만 uv 데이터 헤비급, 5 천만 bit 배열 이 메모 리 를 몇 십 M 밖 에 차지 하지 않 을 뿐 하 쉬 표 보다 훨씬 작 고 10 억 단계 에서 메모리 점용 차 이 는 더욱 클 것 이다.
다음은 코드 예제 입 니 다.

 class BloomFilter
    {
        BitArray container = null;
      public BloomFilter(int length)
        {
            container = new BitArray(length);
        }

        public void Set(string key)
        {
            var h1 = Hash1(key);
            var h2 = Hash2(key);
            var h3 = Hash3(key);
            var h4 = Hash4(key);
            container[h1] = true;
            container[h2] = true;
            container[h3] = true;
            container[h4] = true;
            
        }
        public bool Get(string key)
        {
            var h1 = Hash1(key);
            var h2 = Hash2(key);
            var h3 = Hash3(key);
            var h4 = Hash4(key);

            return container[h1] && container[h2] && container[h3] && container[h4];
        }

        //      1
         int Hash1(string key)
        {
            int hash = 5381;
            int i;
            int count;
            char[] bitarray = key.ToCharArray();
            count = bitarray.Length;
            while (count > 0)
            {
                hash += (hash << 5) + (bitarray[bitarray.Length - count]);
                count--;
            }
            return (hash & 0x7FFFFFFF) % container.Length;

        }
         int Hash2(string key)
        {
            int seed = 131; // 31 131 1313 13131 131313 etc..
            int hash = 0;
            int count;
            char[] bitarray = (key+"key2").ToCharArray();
            count = bitarray.Length;
            while (count > 0)
            {
                hash = hash * seed + (bitarray[bitarray.Length - count]);
                count--;
            }

            return (hash & 0x7FFFFFFF)% container.Length;
        }
         int Hash3(string key)
        {
            int hash = 0;
            int i;
            int count;
            char[] bitarray = (key + "keykey3").ToCharArray();
            count = bitarray.Length;
            for (i = 0; i < count; i++)
            {
                if ((i & 1) == 0)
                {
                    hash ^= ((hash << 7) ^ (bitarray[i]) ^ (hash >> 3));
                }
                else
                {
                    hash ^= (~((hash << 11) ^ (bitarray[i]) ^ (hash >> 5)));
                }
                count--;
            }

            return (hash & 0x7FFFFFFF) % container.Length;

        }
        int Hash4(string key)
        {
            int hash = 5381;
            int i;
            int count;
            char[] bitarray = (key + "keykeyke4").ToCharArray();
            count = bitarray.Length;
            while (count > 0)
            {
                hash += (hash << 5) + (bitarray[bitarray.Length - count]);
                count--;
            }
            return (hash & 0x7FFFFFFF) % container.Length;
        }
    }

테스트 프로그램:

 BloomFilter bf = new BloomFilter(200000000);
            int exsitNumber = 0;
            int noExsitNumber = 0;

            for (int i=0;i < 10000000; i++)
            {
                string key = $"ip_{i}";
                var isExsit= bf.Get(key);
                if (isExsit)
                {
                    exsitNumber += 1;
                }
                else
                {
                    bf.Set(key);
                    noExsitNumber += 1;
                }
            }
            Console.WriteLine($"        ：{exsitNumber}");
            Console.WriteLine($"         ：{noExsitNumber}");

테스트 결과:

        ：7017
         ：9992983

메모리 40M 을 차지 하고 오심 율 이 1000 분 의 1 도 안 되 며 이 업무 장면 에서 받 아들 일 수 있 는 범위 안에 있 습 니 다.진정한 업무 에서 시스템 은 시작 초기 에 이렇게 큰 bit 배열 을 배정 하지 않 고 충돌 이 증가 함 에 따라 일정한 용량 으로 확대 된다.
비동기 최적화
데이터 가 이미 존재 하 는 지 여 부 를 판단 하여 해결 한 후에 다음 단 계 는 데 이 터 를 DB 로 지속 시 키 는 것 입 니 다. 데이터 양 이 많 거나 순간 데이터 양 이 많 으 면 관계 형 데이터 베 이 스 를 직접 삽입 하 는 대신 mq 또는 읽 기와 쓰기 IO 가 비교적 큰 NOSql 을 사용 하 는 것 을 고려 할 수 있 습 니 다.
생각 이 바 뀌 면 전체적인 uv 절차 도 비동기 화 할 수 있 고 이렇게 하 는 것 도 추천 합 니 다.
클릭 하여 관심 추가, 기술 서 를 보 내 드 립 니 다.