Cara melaksanakan Redis berpuluh bilion penyelesaian storan utama

1. Latar belakang Keperluan

Senario aplikasi ini ialah keperluan storan cache DMP perlu mengurus banyak data ID pihak ketiga, termasuk pelbagai media kuki. Hubungan pemetaan dengan kukinya sendiri (selepas ini secara kolektif dirujuk sebagai superrid) juga termasuk teg populasi superid, teg populasi ID mudah alih (terutamanya IDFA dan imei), serta beberapa ID senarai hitam, IP dan data lain.

Tidak sukar untuk menggunakan HDFS untuk menyimpan ratusan bilion rekod di luar talian, tetapi untuk DMP, ia perlu menyediakan pertanyaan masa nyata peringkat milisaat. Memandangkan ID kuki itu sendiri tidak stabil, gelagat penyemakan imbas banyak pengguna sebenar akan membawa kepada penjanaan sejumlah besar kuki baharu Hanya data pemetaan boleh disegerakkan dalam masa untuk memukul teg populasi DMP, dan hits yang lebih tinggi tidak boleh diperolehi melalui pemanasan awal , yang membawa cabaran hebat kepada storan cache.

Selepas ujian sebenar, untuk data di atas, storan konvensional lebih daripada 5 bilion kv rekod memerlukan lebih daripada 1T memori Jika ketersediaan tinggi dan berbilang salinan diperlukan, penggunaan akan menjadi besar panjang kv Ketidakkonsistenan juga akan membawa banyak pemecahan memori, yang memerlukan penyelesaian penyimpanan berskala sangat besar untuk menyelesaikan masalah di atas.

2. Apakah jenis data yang disimpan

Tag orang terutamanya cookie, imei, idfa dan jantina, umur (kumpulan umur) ), geo (wilayah), dsb.; hubungan pemetaan adalah terutamanya pemetaan kuki media kepada superid. Berikut ialah contoh storan data:

1) ID PC:

Kuki media nombor-media=>supperid

supperid => Pengekodan Segmen Umur, jantina=>Pengekodan jantina, geo=>Pengekodan geolokasi}

2) ID sisi peranti:

imei atau idfa => { age=> , gender=>Pengekodan jantina, geo=>Pengekodan geolokasi}

Jelas sekali data PC perlu menyimpan dua jenis key=>value dan key=>peta cincang, manakala data Peranti perlu disimpan satu oleh satu Hanya taip

key=>peta hash.

3. Ciri data

1. Nilai pendek kunci pendek: superid ialah nombor 21 digit: seperti 160524201512168952 imei Ia adalah huruf kecil md5: seperti 2d131005dc0f37d362a5d97094103633; > Panjang kuki media sendiri bukan 1;

2. Perlu menyediakan perkhidmatan untuk semua data, supridid ​​berpuluh bilion, pemetaan media ratusan bilion, id mudah alih berbilion;

3. Berbilion perhubungan pemetaan dijana setiap hari;

4. Data panas boleh diramalkan dalam tetingkap masa yang lebih besar (terdapat beberapa kuki stabil yang tinggal); 🎜>

Data panas tidak boleh diramalkan untuk data pemetaan semasa, dan kebanyakannya adalah kuki yang baru dijana;

6. Cabaran teknikal sedia ada

1) Panjang yang berbeza boleh menyebabkan pemecahan memori dengan mudah; adalah masalah biasa dalam storan memori tulen; 3) Walaupun kepopularan kuki boleh diramalkan oleh tingkah laku mereka, masih terdapat banyak ID yang baru dijana setiap hari (peratusannya adalah sensitif dan tidak akan didedahkan belum); 4) Disebabkan keperluan perkhidmatan dalam persekitaran rangkaian awam ( Kelewatan rangkaian awam domestik kurang daripada 60ms) dalam masa 100ms, jadi pada dasarnya, pemetaan dan label populasi yang baru dikemas kini pada hari itu perlu semua dalam ingatan, supaya tidak membiarkan permintaan jatuh ke dalam data sejuk hujung belakang; 🎜>

6) Memori masih agak mahal, dan penyelesaian storan dengan berpuluh bilion kunci atau malah ratusan bilion kunci adalah penting!

5. Penyelesaian

5.1 Strategi Penghapusan

Setiap hari Terdapat banyak data baharu yang memasuki pangkalan data, jadi ia menjadi sangat penting untuk membersihkan data tepat pada masanya, yang merupakan punca utama kekurangan storan. Kaedah utama adalah untuk menemui dan mengekalkan data panas dan menghapuskan data sejuk. Jumlah pengguna rangkaian jauh daripada mencecah berbilion-bilion, dan ID mereka akan terus berubah dari semasa ke semasa dan mempunyai jangka hayat tertentu. Jadi sebahagian besar id yang kami simpan sebenarnya tidak sah. Sebenarnya, logik pertanyaan bahagian hadapan ialah pendedahan pengiklanan, yang berkaitan dengan tingkah laku manusia, jadi akan terdapat tahap kebolehulangan tertentu dalam tingkah laku capaian ID dalam tetingkap masa tertentu (mungkin kempen, setengah bulan, beberapa bulan).

Sebelum pemulaan data, kami mula-mula menggunakan hbase untuk mengagregat dan menyahduplikasi ID log, dan menggambarkan julat TTL, biasanya 35 hari, supaya ID yang tidak muncul dalam tempoh 35 hari yang lalu boleh dipotong. Selain itu, masa tamat tempoh ditetapkan dalam Redis kepada 35 hari Apabila diakses dan ditekan, kunci akan diperbaharui, masa tamat tempoh akan dilanjutkan dan yang tidak muncul dalam masa 35 hari akan dihapuskan secara semula jadi. Ini boleh berkesan untuk kuki atau ID yang stabil Ia sebenarnya telah terbukti bahawa kaedah lanjutan hayat lebih praktikal untuk IDFA dan imei, dan pengumpulan jangka panjang boleh mencapai hits yang sangat ideal.

5.2 Kurangkan kembung

Saiz ruang jadual Hash dan bilangan Kekunci menentukan kadar konflik (atau diukur dengan faktor beban ), tidak kira betapa munasabahnya Dalam julat, lebih banyak kunci, lebih besar ruang jadual cincang, dan memori yang digunakan secara semula jadi akan menjadi besar. Di samping itu, sebilangan besar penunjuk itu sendiri adalah integer panjang, jadi pengembangan storan memori adalah agak besar. Mari kita bincangkan dahulu tentang cara mengurangkan bilangan kunci.

Mari kita fahami struktur storan dahulu. Mengikut langkah berikut, key1=>value1 boleh disimpan dalam redis, yang kami jangkakan. Mula-mula gunakan nilai hash md5 (kunci) rawak panjang tetap sebagai kunci redis, yang kami panggil BucketId, dan simpan key1=>value1 dalam struktur peta cincang, supaya pelanggan boleh mengikuti proses di atas apabila membuat pertanyaan Kira cincang dan pertanyaan nilai1.

Perubahan proses diterangkan secara ringkas sebagai: get(key1) -> hget(md5(key1), key1) untuk mendapatkan nilai1.

Jika kami membenarkan banyak kunci berlanggar dalam ruang BucketId melalui pra-pengiraan, maka ia boleh dianggap bahawa terdapat berbilang kunci di bawah satu BucketId. Sebagai contoh, jika terdapat purata 10 kunci setiap BucketId, secara teorinya kami akan mengurangkan bilangan kunci redis lebih daripada 90%.

Agak menyusahkan untuk dilaksanakan, dan anda perlu memikirkan kapasiti sebelum menggunakan kaedah ini. Md5 yang biasa kami gunakan ialah 32-bit hexString (aksara heksadesimal), dan ruangnya adalah 128 bit Magnitud ini terlalu besar mengira Untuk menjana cincang dengan bilangan digit yang sesuai, dan untuk menjimatkan memori, kita perlu menggunakan semua jenis aksara (kod ASCII antara 0 dan 127) untuk mengisi dan bukannya HexString, supaya panjang Kunci boleh dipendekkan kepada separuh.

Berikut ialah pelaksanaan khusus

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>Saiz akhir ruang BucketId ditentukan oleh bit parameter dan set pilihan saiz ruang ialah integer diskret kuasa 2. Berikut ialah penjelasan mengapa hanya 7 bit tersedia dalam bait Ini kerana apabila redis menyimpan kunci, ia perlu ASCII (0~127), bukan tatasusunan bait. Jika kami merancang berpuluh-puluh bilion storan dan merancang untuk berkongsi 10 KV setiap baldi, maka kami hanya memerlukan 2^30=1073741824 baldi, iaitu bilangan kunci terakhir. </p>
<p><strong><em>5.3 Kurangkan pemecahan </em></strong></p>
<p>Sebab utama pemecahan ialah memori tidak boleh diselaraskan dan memori tidak boleh diagihkan semula selepas tamat tempoh dan pemadaman. Melalui kaedah yang diterangkan di atas, kita boleh menyimpan label populasi dan data pemetaan dengan cara di atas Kelebihan ini ialah kekunci redis adalah sama panjang. Selain itu, kami juga telah membuat pengoptimuman yang berkaitan untuk kunci dalam peta cincang, memintas enam digit terakhir kuki atau deviceid sebagai kunci, yang juga boleh memastikan penjajaran memori Secara teori, terdapat kemungkinan konflik, tetapi kebarangkalian daripada akhiran yang sama dalam baldi yang sama Sangat rendah (Bayangkan bahawa ID ialah rentetan yang hampir rawak. Kebarangkalian 10 ID rawak yang terdiri daripada aksara yang lebih panjang dengan akhiran yang sama * bilangan sampel baldi = nilai jangkaan konflik </p>
<p>Selain itu, terdapat cara yang sangat rendah tetapi berkesan untuk mengurangkan pemecahan semula hamba, dan kemudian memaksa failover untuk menukar tuan dan hamba. </p>
<p>Syorkan peruntukan memori Google-tcmalloc dan facebook-jemalloc, yang boleh mengurangkan pemecahan memori dan penggunaan memori apabila nilainya tidak besar. Sesetengah orang telah mengukur bahawa libc lebih menjimatkan apabila nilainya besar. </p>
<p><em><strong>6 Isu yang perlu diberi perhatian dengan kaedah baldi cincang md5</strong></em></p>
<p>1) Magnitud storan kv mesti dirancang terlebih dahulu, terapung. julat adalah kira-kira sepuluh hingga lima belas kali bilangan baldi Sebagai contoh, jika saya ingin menyimpan kira-kira 10 bilion kv, sebaiknya pilih 30bit~31bit sebagai bilangan baldi. Dalam erti kata lain, tiada masalah dalam pertumbuhan perniagaan dalam julat yang munasabah (10 hingga 15 kali pertumbuhan jika perniagaan berkembang terlalu banyak kali, ia akan menyebabkan set cincang berkembang terlalu cepat, meningkatkan masa pertanyaan, malah mencetuskan). ambang senarai zip, menyebabkan Memori meningkat secara mendadak. </p>
<p>2) Sesuai untuk nilai pendek Jika nilai terlalu besar atau terdapat terlalu banyak medan, ia tidak sesuai, kerana kaedah ini mesti memerlukan nilai yang dikeluarkan pada satu masa label populasi adalah kod yang sangat kecil, walaupun hanya 3. 4 bit boleh dipasang. 3) Kaedah biasa menukar masa untuk ruang Memandangkan senario perniagaan kami tidak memerlukan qps yang sangat tinggi, yang biasanya pada tahap 100 juta hingga 1 bilion sehari, ia juga sangat menjimatkan untuk menggunakan sewa CPU yang munasabah. nilai. </p>
<p>Selepas menggunakan ringkasan maklumat, kunci tidak boleh dijana secara rawak daripada Redis kerana saiz kekunci dikecilkan dan panjangnya terhad. Jika eksport diperlukan, ia mesti dieksport dalam data sejuk. </p>
<p>5) tamat tempoh perlu dilaksanakan oleh anda sendiri Algoritma semasa adalah sangat mudah Memandangkan penggunaan hanya akan meningkat semasa operasi tulis, ia diambil mengikut perkadaran tertentu semasa operasi tulis, dan HLEN hits. digunakan untuk menentukan sama ada terdapat lebih daripada 15 entri , kunci tamat tempoh hanya akan dipadamkan apabila ia melebihi, dan cap masa TTL disimpan dalam 32 bit pertama nilai. </p>
<p>6) Perangkaan penggunaan baldi perlu dilakukan. Kekunci tamat tempoh perlu dibersihkan dengan kerap untuk memastikan pertanyaan redis tidak akan perlahan. </p>
<p><em><strong>7. Keputusan ujian</strong></em></p>
<p>10 bilion rekod label populasi dan data pemetaan. </p>
<p>Sebelum pengoptimuman, kira-kira 2.3T ruang storan telah digunakan, dan kadar pemecahan adalah kira-kira 2; selepas pengoptimuman, kira-kira 500g ruang storan telah digunakan, dan purata penggunaan setiap baldi adalah kira-kira 4 . Kadar pemecahan adalah sekitar 1.02. Ini menggunakan CPU yang sangat sedikit semasa membuat pertanyaan. </p>
<p>Perlu juga dinyatakan bahawa penggunaan setiap baldi sebenarnya tidak seragam, tetapi menepati taburan polinomial. </p>
<p><img src="https://img.php.cn/upload/article/000/887/227/168543988688361.png" alt="Cara melaksanakan Redis berpuluh bilion penyelesaian storan utama"></p>
<p>Formula di atas boleh mengira taburan kebarangkalian penggunaan baldi. Formula ini hanya untuk mengingatkan semua orang bahawa penggunaan baldi tidak boleh dipandang remeh Ada kemungkinan beberapa baldi mungkin mengandungi beratus-ratus kunci. Tetapi kebenarannya tidaklah terlalu dibesar-besarkan. Bayangkan melambung syiling dan hanya terdapat dua kemungkinan hasil: kepala dan ekor. Ia bersamaan dengan hanya mempunyai dua baldi Jika anda melontar bilangan kali yang tidak terhingga, setiap kali adalah bersamaan dengan percubaan Bernoulli, maka dua baldi itu pasti akan menjadi sangat sekata. Apabila anda melakukan banyak eksperimen Bernoulli umum dan menghadapi banyak tong, taburan kebarangkalian adalah seperti sihir halimunan yang menggantung di atas anda. Taburan penggunaan baldi akan cenderung kepada nilai yang stabil. Seterusnya, mari kita lihat taburan penggunaan baldi khusus: </p>
<p>Melalui statistik pensampelan </p>
<p>baldi 31bit (lebih daripada 2 bilion), penggunaan purata ialah 4.18</p>
<p> <img src="https://img.php.cn/upload/article/000/887/227/168543988662298.png" alt="Cara melaksanakan Redis berpuluh bilion penyelesaian storan utama"></p>
<p>10 bilion menjimatkan 1.8T memori. Teks asal ditulis semula:

Ia bukan sahaja menjimatkan 78% daripada memori asal, tetapi penunjuk penggunaan baldi juga jauh lebih rendah daripada nilai garis bawah yang dijangkakan iaitu 15. </p>
<p>Terdapat juga jumlah baldi yang tidak muncul Jika terlalu banyak, ia akan membawa kepada perancangan yang tidak tepat simpan 2^32kv, baldi yang tidak wujud adalah kira-kira Ya (tahap juta, kesan kecil): </p>
<p>Math.pow((1 - 1.0 / Math.pow(2, 30)), Math.pow( 2, 32)) * Math.pow( 2, 30);</p>
<p>Jangan terlalu risau tentang masalah penggunaan baldi yang tidak sekata Semakin masa berlalu, baldi dengan HLEN melebihi 15 akan berkurangan apabila menulis Mengikut prinsip taburan polinomial, apabila bilangan eksperimen Apabila nombor mencapai tahap tertentu, taburan baldi akan cenderung menjadi genap (jika syiling dilambung berkali-kali, bilangan kepala dan ekor harus sama. ), tetapi kami telah mengurangkan penggunaan baldi melalui strategi tamat tempoh Sebenarnya, setiap baldi telah mengalami banyak eksperimen yang berlaku. </p></r.length>

Atas ialah kandungan terperinci Cara melaksanakan Redis berpuluh bilion penyelesaian storan utama. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!