1. 要件の背景
このアプリケーション シナリオは DMP キャッシュ ストレージ要件です。DMP は、さまざまなデータを含む大量のサードパーティ ID データを管理する必要があります。独自の Cookie (以下、まとめて superrid と呼びます) とのマッピング関係には、superid の人口タグ、モバイル ID (主に IDFA と imei) の人口タグ、および一部のブラックリスト ID、IP およびその他のデータも含まれます。 。
HDFS を使用して数千億のレコードをオフラインで保存することは難しくありませんが、DMP の場合はミリ秒レベルのリアルタイム クエリを提供する必要があります。 Cookie ID自体が不安定なため、多くの実ユーザーの閲覧行動により新たなCookieが大量に生成され、DMP母集団タグにヒットするまでに同期できるのはマッピングデータのみであり、より高いヒット数が得られないこれはキャッシュ ストレージに大きな課題をもたらします。
実際にテストした結果、上記のデータの場合、50 億 kv を超えるレコードを従来のストレージに保存するには 1T 以上のメモリが必要であり、高可用性の複数のコピーが必要な場合、消費量は膨大になります。 kv の長さ 不整合によりメモリの断片化が大量に発生するため、上記の問題を解決するには非常に大規模なストレージ ソリューションが必要になります。
2. 保存されるデータの種類
person タグは主に cookie、imei、idfa とそれらに対応する性別、年齢 (年齢層) です。 )、地理 (地域) など。マッピング関係は主にメディア Cookie のスーパーイドへのマッピングです。以下はデータ保存の例です:
1) PC ID:
メディア番号-メディア cookie=>supperid
supperid => { age=>年齢セグメントコーディング、gender=>性別コーディング、geo=>地理位置情報コーディング}
2) デバイス側の ID:
imei または idfa => { age=> 年齢範囲コーディング、gender=>ジェンダーコーディング、geo=>位置情報コーディング}
明らかに、PC データは 2 種類の key=>value と key=>ハッシュマップを保存する必要がありますが、デバイス データは
key=>ハッシュマップを入力するだけです。
3. データ特性
ショートキーショート値: superid は 21 桁の数字です: 1605242015141689522 など; imei 小文字の md5: 2d131005dc0f37d362a5d97094103633 など; idfa は大文字で「-」 md5: 例: 51DFFC83-9541-4411-FA4F-356927E39D04;
メディア独自の Cookie はさまざまです。 in length;
データ全体のサービスを提供する必要があり、スーパー ID は数百億、メディア マッピングは数千億、モバイル ID は数十億;
毎日、何十億ものマッピング関係が生成されます。
ホットデータは、より大きな時間枠内で予測できます (安定した Cookie がいくつか残っています)。
現在のマッピング データからホット データを予測することは不可能であり、その多くは新しく生成された Cookie です;
4. 既存の技術的課題
1) 長さが異なるとメモリの断片化が容易に発生する可能性がある;
2) ポインタの数が多いため、メモリの拡張率が比較的高い、一般に 7 回であり、これは純粋なメモリ ストレージでよくある問題です。
3) Cookie の人気はその動作によって予測できますが、それでも毎日多くの新しく生成される ID があります (割合は機密性が高く、現時点では公開されません);
4) 公衆ネットワーク環境 (国内の公衆ネットワークの遅延は 60 ミリ秒未満) でのサービス要件により 100 ミリ秒以内であるため、原則として、新しく更新されたマッピングと人口タグはリクエストがバックエンドのコールドデータに落ちないように、その日はすべてメモリ内にある必要があります;
5) ビジネスの観点から、原則としてすべてのデータは少なくとも 35 日間保持されます
6) メモリは依然として比較的高価であり、数百億、さらには数千億のキーを備えたストレージ ソリューションが不可欠です。
5. 解決策
5.1 排除戦略
毎日データベースには大量の新しいデータが入力されるため、タイムリーにデータをクリーンアップすることが特に重要になります。これがストレージ不足の主な原因となります。主な方法は、ホット データを検出して保持し、コールド データを削除することです。
ネットワーク ユーザーの数は数十億人には遠く及ばず、ユーザーの ID は時間の経過とともに変化し続け、一定の寿命があります。したがって、私たちが保存している ID は、ほとんどの場合、実際には無効です。実際、フロントエンド クエリのロジックは広告露出であり、これは人間の行動に関連しているため、特定の時間枠での ID のアクセス行動にはある程度の再現性があります (おそらくキャンペーン、半分の期間)。数か月、数か月）。
データを初期化する前に、まず hbase を使用してログの ID を集約して重複を排除し、TTL 範囲 (通常は 35 日) を定義します。これにより、過去 35 日間に出現しなかった ID は、切り落とす。また、Redis では有効期限が 35 日に設定されており、アクセスしてヒットするとキーが更新され有効期限が延長され、35 日以内に出現しないものは自然に排除されます。これは安定したCookieやIDに対して有効であり、実際にIDFAやimeiでは延命方法の方が現実的であり、長期蓄積により非常に理想的なヒットが得られることが証明されています。
5.2 拡張の削減
ハッシュ テーブル スペースのサイズとキーの数によって、競合率が決まります (または負荷率によって測定されます)。 )、どんなに妥当な範囲内であっても、キーが多ければ多いほど、ハッシュテーブルの領域が大きくなり、消費されるメモリも当然大きくなります。また、多くのポインタ自体が長整数であるため、メモリストレージの拡張が著しくなります。まずはキーの数を減らす方法について説明します。
まずストレージ構造を理解しましょう。次の手順に従って、key1=>value1 を redis に保存できます。これは期待どおりです。まず、固定長のランダム ハッシュ md5 (キー) 値を Redis キーとして使用し (BucketId と呼びます)、key1=>value1 をハッシュマップ構造に格納します。これにより、クライアントはクエリ時に上記のプロセスに従うことができます。ハッシュとクエリを計算します。値1。
プロセスの変更は、単に get(key1) -> hget(md5(key1), key1) として value1 を取得するように記述されます。
事前計算によって BucketId 空間内で多数のキーの衝突を許可した場合、1 つの BucketId の下に複数のキーがぶら下がっていると考えることができます。たとえば、BucketId ごとに平均 10 個のキーがある場合、理論的には Redis キーの数が 90% 以上削減されます。
具体的な実装にはいくつか問題があり、この方法を使用する前に容量スケールを考慮する必要があります。私たちが普段使っている md5 は 32 ビット hexString (16 進数文字) で、その空間は 128 ビットです。この大きさは大きすぎます。保存する必要があるのは数百億、つまり約 33 ビットです。適切な桁数のハッシュを生成し、メモリを節約するには、キーの長さを短縮できるように、HexString の代わりにすべての文字タイプ (0 ～ 127 の ASCII コード) を使用して埋める必要があります。半分まで。
次は具体的な実装です
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の。ここでは、1 バイトで 7 ビットしか使用できない理由について説明します。これは、redis がキーを保存するときに、バイト配列ではなく ASCII (0 ～ 127) である必要があるためです。数百億のストレージを計画し、バケットごとに 10 KV を共有することを計画している場合、必要なバケットは 2^30=1073741824 だけです。これがキーの最終的な数です。 </p>
<p><strong><em>5.3 断片化の削減</em></strong></p>
<p>断片化の主な理由は、メモリを調整できず、期限切れや削除後にメモリを再割り当てできないことです。上記の方法により、人口ラベルとマッピング データを上記の方法で保存できます。この利点は、Redis キーの長さが等しいことです。さらに、ハッシュマップ内のキーに関連する最適化も行い、Cookie またはデバイス ID の最後の 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倍程度の範囲で、例えば100億kv程度を蓄えたい場合、バケット数は30bit～31bitを選ぶのがベストです。つまり、ビジネスが妥当な範囲（10～15倍）で成長する分には問題ありませんが、ビジネスが何倍にも成長しすぎると、ハッシュセットが急激に成長し、クエリ時間が増加し、トリガーが発生する可能性があります。 zip リストのしきい値が大きくなり、メモリが大幅に増加します。 </p>
<p>2) 短い値に適しています。値が大きすぎる場合やフィールドの数が多すぎる場合は、一度に値を取り出す必要があるため、この方法は適していません。人口ラベルは非常に小さなコードであり、わずか 3.4 ビットでもインストールできます。 3) 時間と空間を交換する典型的な方法です。私たちのビジネス シナリオでは、一般的に 1 日あたり 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>上記の式は、バケット消費の確率分布を計算できます。この式は、バケットの消費が当然のことであるとは考えられないことを皆さんに思い出させるためのものであり、一部のバケットには数百のキーが含まれている可能性があります。しかし、真実はそれほど誇張されたものではありません。コインを投げると、表と裏の 2 つの結果しか考えられないことを想像してください。これはバケットが 2 つしかないのと同じで、毎回がベルヌーイ実験に相当する回数を無限に投げると、2 つのバケットは間違いなく非常に均等になります。多くの一般化されたベルヌーイ実験を実行し、多くのバレルに直面すると、確率分布は目に見えない魔法のようにかかってきます。バケットの消費分布は安定した値になる傾向があります。次に、具体的なバケットの消費分布を見てみましょう。 </p>
<p>サンプリング統計によると、</p>
<p>31 ビット (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^30 個のバケットの場合、 2^32kv を格納、存在しないバケットは約 Yes (100 万レベル、影響はほとんどない): </p>
<p>Math.pow((1 - 1.0 / Math.pow(2, 30)), Math.pow( 2, 32)) * Math.pow( 2, 30);</p>
<p>バケットの消費が不均一になる問題については、あまり心配しないでください。時間の経過とともに、HLEN が 15 を超えるバケットは書き込み時に削減されます。多項式分布の原理によれば、実験回数が一定のレベルに達すると、バケツの分布は均等になる傾向があります（コインを何度も投げると、表と裏の数は同じになるはずです） ) ですが、有効期限戦略によりバケットの消費量を削減しました。実際、各バケットで多くの実験が行われました。 </p></r.length>以上がRedis 数百億の主要なストレージ ソリューションを実装する方法の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。
![[Web フロントエンド] Node.js クイック スタート](https://img.php.cn/upload/course/000/000/067/662b5d34ba7c0227.png)
