수백억 개의 Redis 키 스토리지 솔루션을 구현하는 방법
- WBOY앞으로
- 2023-05-30 17:44:441122검색
1. 요구사항 배경
이 적용 시나리오는 DMP가 각 미디어 쿠키와 자체 쿠키 간의 매핑 관계를 포함하여 많은 타사 ID 데이터를 관리해야 하는 DMP의 캐시 저장 요구 사항입니다. superrid라고 함), superrid의 인구 태그, 모바일 ID의 인구 태그(주로 IDFA 및 imei) 및 일부 블랙리스트 ID, IP 및 기타 데이터가 포함되어 있습니다.
HDFS를 사용하여 수천억 개의 레코드를 오프라인으로 저장하는 것은 어렵지 않지만, DMP의 경우 밀리초 수준의 실시간 쿼리를 제공해야 합니다. 쿠키 ID 자체가 불안정하기 때문에 많은 실제 사용자의 탐색 행위로 인해 새로운 쿠키가 대량 생성될 수 있습니다. 매핑 데이터만 적시에 동기화되어 DMP 인구 태그에 도달할 수 있으며 더 높은 조회수는 얻을 수 없습니다. 예열을 통해 캐시 저장에 큰 어려움을 가져옵니다.
실제 테스트 후, 위 데이터의 경우 50억 kv 이상의 레코드를 저장하려면 1T 이상의 메모리가 필요합니다. 고가용성 다중 복사본이 필요한 경우 kv의 길이도 고르지 않습니다. 또한 위의 문제를 해결하려면 매우 큰 규모의 스토리지 솔루션이 필요한 많은 메모리 조각화가 발생합니다.
2. 어떤 종류의 데이터가 저장되나요?
사람 태그는 주로 쿠키, imei, idfa 및 해당 성별(성별), 연령(연령대), 지역(지역) 등입니다. 주로 superrid에 대한 쿠키의 미디어 매핑입니다. 다음은 데이터 저장 예시입니다.
1) PC 측 ID:
미디어 번호 - 미디어 쿠키=>supperid
supperid => , geo= >Geolocationcoding}
2) 기기측 ID:
imei 또는 idfa => PC 데이터는 key=>value와 key=>hashmap의 두 가지 유형을 저장해야 하고, 장치 데이터는
key=>hashmap 중 한 가지 유형을 저장해야 합니다.
3. 데이터 특성
- 짧은 키 짧은 값: superid는 21자리 숫자입니다. 예: 1605242015141689522, imei는 소문자 md5: 예: 2d131005dc0f37d362a5d970 94103633 ;idfa는 대문자이며 "-" md5: for 예: 51DFFC83- 9541-4411-FA4F-356927E39D04;
- 미디어 자체 쿠키의 길이는 다릅니다.
- 는 전체 데이터 양에 대한 서비스를 제공해야 하며, superrid는 수백억 개입니다.
- 매일 수십억 개의 매핑 관계가 생성됩니다.
- 더 큰 시간 내에 핫 데이터를 예측할 수 있습니다(일부 안정적인 쿠키가 남아 있음). 현재 매핑 데이터를 예측할 수 없습니다. 핫 데이터의 대부분은 새로 생성된 쿠키입니다.
4. 기존 기술 문제
1) 길이가 다르면 메모리 조각화가 쉽게 발생할 수 있습니다. 포인터의 메모리 확장률은 일반적으로 7배로 비교적 높습니다. 이는 순수 메모리 저장의 일반적인 문제입니다. 3) 쿠키의 인기는 쿠키의 행동으로 예측할 수 있지만 여전히 매일 새로운 ID가 많이 생성됩니다. 4) 공용망 환경에서는 100ms 이내 서비스가 요구되므로(국내 공용망 지연시간은 60ms 이내) 원칙적으로 모두 새롭게 업데이트됩니다. 요청이 백엔드의 콜드 데이터에 속하지 않도록 당일 매핑 및 인구 라벨이 메모리에 있어야 합니다.
5 ) 비즈니스 측면에서 원칙적으로 모든 데이터는 최소 35일 동안 보관됩니다.
6) 메모리는 여전히 상대적으로 비싸며 수백억 개의 Key 또는 심지어 수천억 개의 스토리지 솔루션이 필수적입니다!
5. 솔루션
5.1 제거 전략 매일 대량의 새로운 데이터가 데이터베이스에 입력되므로 적시에 데이터를 정리하는 것이 특히 중요합니다. 저장공간 부족 이유. 주요 방법은 핫 데이터를 찾아 보관하고 콜드 데이터를 제거하는 것입니다.
네트워크 사용자 수는 수십억 명에 도달하기에는 거리가 멀고, 이들의 ID는 시간이 지남에 따라 계속 변경되고 특정 수명을 갖습니다. 따라서 우리가 저장하는 ID는 대부분 유효하지 않습니다. 실제로 프런트 엔드 쿼리의 논리는 인간 행동과 관련된 광고 노출이므로 특정 기간(아마도 캠페인, 절반의 기간)에 ID의 액세스 동작에 어느 정도 반복성이 있을 것입니다. 한 달, 몇 달). 데이터 초기화 전 먼저 hbase를 사용해 로그 ID를 집계 및 중복 제거하고, TTL 범위(보통 35일)를 지정하여 지난 35일 동안 나타나지 않은 ID를 잘라낼 수 있도록 합니다. 또한, Redis에는 만료 시간이 35일로 설정되어 있으며, 접속하여 히트 시 키가 갱신되며, 만료 시간이 연장되며, 35일 이내에 나타나지 않는 키는 자연스럽게 제거됩니다. 이는 안정적인 쿠키나 ID에 효과적일 수 있으며 IDFA 및 imei의 경우 수명 연장 방법이 더 실용적이며 장기간 축적하면 매우 이상적인 히트를 얻을 수 있다는 것이 실제로 입증되었습니다.
5.2 확장 감소
해시 테이블 공간의 크기와 키 수에 따라 충돌률(또는 로드 비율로 측정)이 결정됩니다. 합리적인 범위 내에서는 키가 많을수록 해시 테이블이 커집니다. 공간과 소비 메모리는 당연히 커질 것입니다. 게다가 다수의 포인터 자체가 장정수(Long Integer)이기 때문에 메모리 저장 용량의 확장도 상당하다. 먼저 키 수를 줄이는 방법에 대해 이야기하겠습니다.
먼저 저장 구조를 이해해 봅시다. 다음 단계에 따르면 key1=>value1이 redis에 저장될 수 있으며 이는 우리가 기대하는 것입니다. 먼저 고정 길이 무작위 해시 md5(키) 값을 Redis 키로 사용합니다. 이를 BucketId라고 부르고, key1=>value1을 해시맵 구조에 저장하여 클라이언트가 쿼리할 때 위 프로세스를 따를 수 있도록 합니다. 해시를 계산하고 쿼리합니다. 값1.
프로세스 변경 사항은 간단히 설명됩니다: get(key1) -> hget(md5(key1), key1) to get value1.
사전 계산을 통해 BucketId 공간에서 여러 키가 충돌하도록 허용하면 하나의 BucketId 아래에 여러 키가 있다고 간주할 수 있습니다. 예를 들어 BucketId당 평균 10개의 키가 있는 경우 이론적으로 Redis 키 수를 90% 이상 줄입니다.
구체적인 구현이 조금 까다로우며, 이 방법을 사용하기 전에 용량 규모를 고려해야 합니다. 우리가 일반적으로 사용하는 md5는 32비트 hexString(16진수 문자)이고 공간은 128비트입니다. 이 크기는 우리가 저장해야 하는 양이 약 33비트이므로 이를 위한 메커니즘이 필요합니다. 계산 적절한 자릿수로 해시를 생성하고 메모리를 절약하려면 HexString 대신 모든 문자 유형(0~127 사이의 ASCII 코드)을 사용하여 채워야 하므로 Key 길이를 줄일 수 있습니다. 반으로.
다음은 구체적인 구현 방법입니다.
public static byte [] getBucketId(byte [] key, Integer bit) {
MessageDigest mdInst = MessageDigest.getInstance("MD5");
mdInst.update(key);
byte [] md = mdInst.digest();
byte [] r = new byte[(bit-1)/7 + 1];// 因为一个字节中只有7位能够表示成单字符
int a = (int) Math.pow(2, bit%7)-2;
md[r.length-1] = (byte) (md[r.length-1] & a);
System.arraycopy(md, 0, r, 0, r.length);
for(int i=0;i<r.length if r return><p> BucketId 공간의 최종 크기는 매개변수 비트에 의해 결정됩니다. 선택적 공간 크기 세트는 2의 이산 정수 거듭제곱입니다. 다음은 바이트에서 7비트만 사용할 수 있는 이유에 대한 설명입니다. 이는 Redis가 키를 저장할 때 바이트 배열이 아닌 ASCII(0~127)여야 하기 때문입니다. 수백억 개의 스토리지를 계획하고 버킷당 10kv를 공유할 계획이라면 최종 키 수인 2^30=1073741824 버킷만 필요합니다. </p>
<p><strong><em>5.3 조각화 줄이기</em></strong></p>
<p>조각화의 주된 이유는 메모리를 정렬할 수 없고 만료 및 삭제 후에 메모리를 재할당할 수 없다는 것입니다. 위에서 설명한 방법을 통해 위와 같은 방식으로 모집단 레이블과 매핑 데이터를 저장할 수 있습니다. 이 방법의 장점은 Redis 키의 길이가 동일하다는 것입니다. 또한 해시맵의 키에 대해 관련 최적화를 수행하여 쿠키 또는 deviceid의 마지막 6자리를 키로 가로채서 이론적으로 메모리 정렬을 보장할 수 있지만 충돌 가능성은 있습니다. 동일한 버킷에 동일한 접미사가 있음 매우 낮음 (ID가 거의 임의의 문자열이라고 상상해보십시오. 동일한 접미사를 가진 더 긴 문자로 구성된 무작위 ID 10개 * 버킷 샘플 수 = 충돌 예상 값 </p>
<p>또한 조각화를 줄이는 매우 낮지만 효과적인 방법이 있습니다. 슬레이브를 다시 시작한 다음 강제로 장애 조치를 수행하여 마스터와 슬레이브를 전환하는 것은 마스터의 메모리 조각 모음과 같습니다. </p>
<p>값이 크지 않을 때 메모리 조각화 및 메모리 소비를 줄일 수 있는 Google-tcmalloc 및 facebook-jemalloc 메모리 할당을 권장합니다. 어떤 사람들은 libc 값이 클수록 더 경제적이라고 측정했습니다. </p>
<p><em><strong>6. md5 해시 버킷 방식에서 주의해야 할 문제</strong></em></p>
<p>1) kv 저장 규모를 미리 계획해야 합니다. 플로팅 범위는 버킷 수의 10~15배 정도입니다. 예를 들어 I 수백억 개의 KV를 저장하려면 버킷 수를 30bit~31bit로 선택하는 것이 가장 좋습니다. 즉, 합리적인 범위(10~15배 성장) 내에서는 비즈니스 성장에 문제가 없습니다. 비즈니스가 너무 많이 성장하면 해시셋이 너무 빨리 성장하고 쿼리 시간이 늘어나며 심지어 트리거가 발생하기도 합니다. zip 목록 임계값이 증가하여 메모리가 극적으로 증가합니다. </p>
<p>2) 값이 너무 크거나 필드가 너무 많으면 적합하지 않습니다. 예를 들어 인구 레이블은 값을 한 번에 꺼내야 하기 때문입니다. 매우 작은 인코딩, 심지어 3 또는 4비트(비트)만 설치할 수 있습니다. 3) 시간을 공간으로 교환하는 일반적인 방법입니다. 우리의 비즈니스 시나리오는 일반적으로 하루에 1억~10억 수준의 매우 높은 qps를 요구하지 않으므로 CPU 임대를 합리적으로 사용하는 것도 매우 경제적입니다. 값. </p>
<p>정보 다이제스트를 사용한 후에는 키 크기가 줄어들고 길이가 제한되므로 Redis에서 키를 무작위로 생성할 수 없습니다. 내보내기가 필요한 경우 콜드 데이터로 내보내야 합니다. </p>
<p>5) 만료는 직접 구현해야 합니다. 현재 알고리즘은 쓰기 작업 중에만 소비가 증가하므로 HLEN 적중 여부를 결정하는 데 사용됩니다. 15개 이상의 항목이 있는 경우 만료된 키가 삭제되고 TTL 타임스탬프가 값의 처음 32비트에 저장됩니다. </p>
<p>6) 버킷 소비 통계가 필요합니다. Redis 쿼리가 느려지지 않도록 만료된 키를 정기적으로 정리해야 합니다. </p>
<p><em><strong>7. 테스트 결과 </strong></em></p>
<p>100억 개의 인구 라벨링 및 매핑 데이터 기록. </p>
<p>최적화 전 약 2.3T의 저장 공간이 사용되었고 조각화율은 약 2였으며 최적화 후 약 500g의 저장 공간이 사용되었으며 각 버킷의 평균 사용량은 약 4였습니다. 조각화율은 약 1.02입니다. 이는 쿼리할 때 CPU를 거의 소모하지 않습니다. </p>
<p>각 버킷의 소비는 실제로 균일하지 않고 다항식 분포를 따른다는 점도 언급해야 합니다. </p>
<p><img src="https://img.php.cn/upload/article/000/887/227/168543988688361.png" alt="수백억 개의 Redis 키 스토리지 솔루션을 구현하는 방법"></p>
<p>위 공식을 통해 버킷 소비 확률 분포를 계산할 수 있습니다. 이 공식은 버킷 소비가 당연한 것으로 간주될 수 없다는 점을 모든 사람에게 상기시키기 위한 것입니다. 일부 버킷에는 수백 개의 키가 포함될 수 있습니다. 그러나 진실은 그렇게 과장된 것이 아니다. 동전을 던졌을 때 앞면과 뒷면이라는 두 가지 가능한 결과만 있다고 상상해 보세요. 양동이가 두 개만 있는 것과 같습니다. 무한한 횟수를 던질 때마다 베르누이 실험과 동일하므로 두 양동이는 확실히 매우 균등할 것입니다. 일반화된 베르누이 실험을 많이 하고 많은 통에 직면하게 되면 확률 분포는 눈에 보이지 않는 마법과도 같습니다. 버킷의 소비 분포는 안정적인 값을 갖는 경향이 있습니다. 다음으로 구체적인 버킷 소비 분포를 살펴보겠습니다. </p>
<p>샘플링 통계를 통해</p>
<p>31bit(20억 개 이상) 버킷을 기준으로 평균 소비량은 4.18</p>
<p><img src="https://img.php.cn/upload/article/000/887/227/168543988662298.png" alt="수백억 개의 Redis 키 스토리지 솔루션을 구현하는 방법"></p>
<p>100억 개로, 1.8T의 메모리를 절약합니다. 원본 텍스트 재작성:
원래 메모리의 78%를 절약했을 뿐만 아니라 버킷 소비 지표도 예상 수익 값인 15보다 훨씬 낮았습니다. </p>
<p>나타나지 않는 버킷도 있습니다. 너무 많으면 계획이 부정확해집니다. 실제로 2^32kv를 저장하는 버킷 수는 이항 분포와 일치합니다. 존재하지 않는 버킷이 약 (수백만 개) 있습니다. 수준, 거의 영향 없음): </p>
<p>Math.pow((1 - 1.0 / Math.pow(2, 30)), Math.pow(2, 32)) * Math .pow(2, 30);</p>
<p>for 불균형한 버킷 소비 문제에 대해 너무 걱정하지 마십시오. 시간이 지남에 따라 HLEN이 15를 초과하는 버킷은 다항식 분포의 원리에 따라 감소합니다. 실험 횟수가 일정 수준에 도달하면 버킷의 분포는 균일하지만(동전은 수없이 던지기 때문에 앞면과 뒷면의 수가 같아야 함) 만료 전략을 통해 버킷 소비를 줄입니다. 실제로 각 버킷은 많은 실험을 경험했습니다. </p></r.length>위 내용은 수백억 개의 Redis 키 스토리지 솔루션을 구현하는 방법의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!