Bagaimana cara mempercepat dekompresi LZ4 di ClickHouse?

Ketika Anda menjalankan kueri di ClickHouse , Anda mungkin memperhatikan bahwa profiler sering menunjukkan fungsi LZ_decompress_fast dekat bagian atas. Apa yang sedang terjadi Pertanyaan ini membuat kami bertanya-tanya bagaimana cara memilih algoritma kompresi terbaik.

ClickHouse menyimpan data dalam bentuk terkompresi. Saat menjalankan kueri, ClickHouse mencoba melakukan sesedikit mungkin, untuk menghemat sumber daya CPU. Dalam banyak kasus, semua perhitungan yang berpotensi memakan waktu sudah dioptimalkan dengan baik, ditambah pengguna menulis kueri yang dipikirkan dengan matang. Maka yang harus dilakukan adalah melakukan dekompresi.



Jadi mengapa dekompresi LZ4 menjadi hambatan? LZ4 tampak seperti algoritma yang sangat ringan : laju dekompresi data biasanya dari 1 hingga 3 GB / s per inti prosesor, tergantung pada data. Ini jauh lebih cepat daripada subsistem disk biasa. Selain itu, kami menggunakan semua core CPU yang tersedia, dan skala dekompresi secara linear di semua core fisik.

Namun, ada dua hal yang perlu diingat. Pertama, data terkompresi dibaca dari disk, tetapi kecepatan dekompresi diberikan dalam hal jumlah data yang tidak terkompresi. Jika rasio kompresi cukup besar, hampir tidak ada yang dibaca dari disk. Tetapi akan ada banyak data yang terkompresi, dan ini secara alami mempengaruhi pemanfaatan CPU: dalam kasus LZ4, jumlah pekerjaan yang diperlukan untuk mendekompresi data hampir sebanding dengan volume data yang dikompresi itu sendiri.

Kedua, jika data di-cache, Anda mungkin tidak perlu membaca data dari disk sama sekali. Anda dapat mengandalkan cache halaman atau menggunakan cache Anda sendiri. Caching lebih efisien dalam database berorientasi kolom, karena hanya kolom yang sering digunakan yang tetap ada dalam cache. Inilah sebabnya mengapa LZ4 sering tampak menjadi hambatan dalam hal beban CPU.

Ini memunculkan dua pertanyaan lagi. Pertama, jika dekompresi memperlambat kita, apakah ada gunanya mengompresi data? Namun spekulasi ini tidak relevan dalam praktiknya. Sampai saat ini, konfigurasi ClickHouse hanya menawarkan dua opsi kompresi data - LZ4 dan Zstandard . LZ4 digunakan secara default. Beralih ke Zstandard membuat kompresi lebih kuat dan lebih lambat. Tetapi tidak ada opsi untuk sepenuhnya menonaktifkan kompresi, karena LZ4 diasumsikan memberikan kompresi minimal yang wajar yang selalu dapat digunakan. (Itulah sebabnya saya suka LZ4.)

Tetapi kemudian orang asing yang misterius muncul dalam obrolan dukungan ClickHouse internasional yang mengatakan bahwa ia memiliki subsistem disk yang sangat cepat (dengan NVMe SSD) dan dekompresi adalah satu-satunya hal yang memperlambat permintaannya, sehingga alangkah baiknya untuk dapat menyimpan data tanpa kompresi Saya menjawab bahwa kami tidak memiliki opsi ini, tetapi akan mudah untuk menambahkan. Beberapa hari kemudian, kami mendapat permintaan tarik yang menerapkan metode kompresi none . Saya meminta kontributor untuk melaporkan kembali seberapa banyak opsi ini membantu mempercepat pertanyaan. Responsnya adalah bahwa fitur baru ini ternyata tidak berguna dalam praktik, karena data yang tidak terkompresi mulai mengambil terlalu banyak ruang disk dan tidak cocok dengan drive NVMe tersebut.

Pertanyaan kedua yang muncul adalah bahwa jika ada cache, mengapa tidak menggunakannya untuk menyimpan data yang sudah didekompresi? Ini adalah kemungkinan yang layak yang akan menghilangkan kebutuhan untuk dekompresi dalam banyak kasus. ClickHouse juga memiliki cache seperti ini: cache dari blok dekompresi . Tapi sayang membuang banyak RAM untuk ini. Jadi biasanya masuk akal untuk digunakan pada kueri sekuensial kecil yang menggunakan data yang hampir sama.

Kesimpulan kami adalah selalu lebih baik menyimpan data dalam format terkompresi. Selalu tulis data ke disk dalam format terkompresi. Mengirimkan data melalui jaringan dengan kompresi, juga. Menurut pendapat saya, kompresi standar dapat dibenarkan bahkan ketika mentransfer data dalam pusat data tunggal dalam jaringan 10 GB tanpa kelebihan langganan, sementara mentransfer data yang tidak terkompresi antara pusat data tidak dapat diterima.

Mengapa LZ4?

Mengapa memilih LZ4? Tidak bisakah kita memilih sesuatu yang lebih ringan? Secara teoritis, kami bisa, dan ini adalah pemikiran yang bagus. Tapi mari kita lihat kelas algoritma yang dimiliki LZ4.

Pertama-tama, ini generik dan tidak mengadaptasi tipe data. Misalnya, jika Anda tahu sebelumnya bahwa Anda akan memiliki array bilangan bulat, Anda dapat menggunakan salah satu algoritma VarInt dan ini akan menggunakan CPU lebih efektif. Kedua, LZ4 tidak terlalu tergantung pada asumsi model data. Katakanlah Anda memiliki serangkaian nilai sensor waktu, array angka floating-point. Jika Anda memperhitungkan ini, Anda dapat menghitung delta di antara angka-angka ini dan kemudian mengompresnya dengan algoritma umum, yang akan menghasilkan rasio kompresi yang lebih tinggi.

Anda tidak akan memiliki masalah menggunakan LZ4 dengan array byte atau file apa pun. Tentu saja memang memiliki spesialisasi (lebih lanjut tentang itu nanti), dan dalam beberapa kasus penggunaannya tidak ada gunanya. Tetapi jika kita menyebutnya algoritma tujuan umum, kita akan cukup dekat dengan kebenaran. Kami harus mencatat bahwa berkat desain internal, LZ4 secara otomatis mengimplementasikan algoritma RLE sebagai kasus khusus.

Namun, pertanyaan yang lebih penting adalah apakah LZ4 adalah algoritma yang paling optimal dari kelas ini dalam hal kecepatan dan kekuatan kompresi secara keseluruhan. Algoritma optimal disebut perbatasan Pareto, yang berarti bahwa tidak ada algoritma lain yang secara definitif lebih baik dalam satu cara dan tidak lebih buruk dengan cara lain (dan pada berbagai set data, juga). Beberapa algoritma lebih cepat tetapi menghasilkan rasio kompresi yang lebih kecil, sementara yang lain memiliki kompresi yang lebih kuat tetapi lebih lambat untuk kompres atau dekompresi.

Sejujurnya, LZ4 sebenarnya bukan perbatasan Pareto - ada beberapa opsi yang tersedia yang sedikit lebih baik. Misalnya, lihat LZTURBO dari pengembang berjuluk powturbo . Tidak ada keraguan tentang keandalan hasil, berkat komunitas encode.ru (forum terbesar dan mungkin satu-satunya pada kompresi data). Sayangnya, pengembang tidak mendistribusikan kode sumber atau binari; mereka hanya tersedia untuk sejumlah kecil orang untuk pengujian, atau untuk banyak uang (meskipun sepertinya belum ada yang membayarnya). Lihat juga Lizard (sebelumnya LZ5) dan Density . Mereka mungkin bekerja sedikit lebih baik daripada LZ4 ketika Anda memilih level kompresi tertentu. Pilihan lain yang sangat menarik adalah LZSSE . Tetapi selesaikan membaca artikel ini sebelum Anda memeriksanya.

Cara kerja lz4

Mari kita lihat bagaimana LZ4 bekerja secara umum. Ini adalah salah satu implementasi dari algoritma LZ77. L dan Z mewakili nama pengembang (Lempel dan Ziv), dan 77 untuk tahun 1977 ketika algoritme diterbitkan. Ini memiliki banyak implementasi lain: QuickLZ, FastLZ, BriefLZ, LZF, LZO, dan gzip dan zip jika level kompresi rendah digunakan.

Blok data yang dikompres menggunakan LZ4 berisi urutan entri (perintah atau instruksi) dari dua jenis:

1. Literal: "Ambil N byte berikut apa adanya dan salin ke hasilnya".
2. Cocok: "Ambil N byte dari hasil dekompresi mulai dari nilai offset relatif terhadap posisi saat ini".

Contoh Sebelum kompresi:

 Hello world Hello 

Setelah kompresi:

 literals 12 "Hello world " match 5 12 

Jika kita mengambil blok terkompresi dan mengulangi kursor saat menjalankan perintah ini, kita akan mendapatkan data asli yang tidak terkompresi sebagai hasilnya.

Jadi itu pada dasarnya bagaimana data di-decompress. Ide dasarnya jelas: untuk melakukan kompresi, algoritma mengkodekan urutan byte berulang menggunakan kecocokan.

Beberapa karakteristik juga jelas. Algoritma byte-oriented ini tidak membedah byte individu; itu hanya menyalin secara keseluruhan. Inilah perbedaan dari pengodean entropi. Sebagai contoh, zstd adalah kombinasi dari LZ77 dan pengkodean entropi.

Perhatikan bahwa ukuran blok terkompresi tidak boleh terlalu besar. Ukuran dipilih untuk menghindari pemborosan banyak RAM selama dekompresi, untuk menghindari memperlambat akses acak terlalu banyak dalam file terkompresi (yang terdiri dari sejumlah besar blok terkompresi), dan kadang-kadang demikian blok akan muat dalam cache CPU. Misalnya, Anda dapat memilih 64 KB sehingga buffer untuk data terkompresi dan tidak terkompresi akan muat dalam cache L2 dengan setengah masih gratis.

Jika kita perlu mengompres file yang lebih besar, kita dapat menggabungkan blok terkompresi. Ini juga nyaman untuk menyimpan data tambahan (seperti checksum) dengan setiap blok terkompresi.

Offset maksimum untuk pertandingan terbatas. Dalam LZ4, batasnya adalah 64 kilobyte. Jumlah ini disebut jendela geser. Ini berarti bahwa kecocokan dapat ditemukan di jendela 64 kilobyte sebelum kursor, yang meluncur dengan kursor saat bergerak maju.

Sekarang mari kita lihat bagaimana mengompres data, atau, dengan kata lain, bagaimana menemukan urutan yang cocok dalam suatu file. Anda selalu dapat menggunakan trif sufiks (hebat jika Anda pernah mendengar hal ini). Ada metode yang menjamin bahwa pencocokan terpanjang terletak di byte sebelumnya setelah kompresi. Ini disebut penguraian optimal dan hampir memberikan rasio kompresi terbaik untuk blok kompresi format tetap. Tetapi ada pendekatan yang lebih baik, seperti menemukan pasangan yang cukup baik yang belum tentu terpanjang. Cara paling efisien untuk menemukannya adalah menggunakan tabel hash.

Untuk melakukan ini, kita lakukan iterasi kursor melalui blok data asli dan ambil beberapa byte setelah kursor (misalkan 4 byte). Kami hash mereka dan menempatkan offset dari awal blok (di mana 4 byte diambil dari) ke dalam tabel hash. Nilai 4 disebut "min-match" - menggunakan tabel hash ini, kita dapat menemukan kecocokan setidaknya 4 byte.

Jika kita melihat tabel hash dan sudah memiliki catatan yang cocok, dan offset tidak melebihi jendela geser, kita periksa untuk melihat berapa banyak byte yang cocok setelah 4 byte tersebut. Mungkin ada lebih banyak pertandingan. Mungkin juga ada tabrakan di tabel hash dan tidak ada yang cocok, tapi ini bukan masalah besar. Anda bisa mengganti nilai di tabel hash dengan yang baru. Tabrakan di tabel hash hanya akan menyebabkan rasio kompresi yang lebih rendah, karena akan ada lebih sedikit kecocokan. Omong-omong, jenis tabel hash ini (dengan ukuran tetap dan tidak ada resolusi tabrakan) disebut "tabel cache". Nama ini masuk akal karena jika terjadi tabrakan, tabel cache hanya lupa tentang entri lama.

Tantangan bagi pembaca yang cermat. Mari kita asumsikan bahwa data adalah array angka UInt32 dalam format endian kecil yang mewakili bagian dari urutan bilangan asli: 0, 1, 2 ... Jelaskan mengapa data ini tidak dikompresi saat menggunakan LZ4 (ukuran data terkompresi) tidak ada yang lebih kecil dibandingkan dengan data yang tidak terkompresi).

Cara mempercepat semuanya

Jadi saya ingin mempercepat dekompresi LZ4. Mari kita lihat bagaimana loop dekompresi terlihat. Ini dia dalam pseudocode:

 while (...) {    read(input_pos, literal_length, match_length);    copy(output_pos, input_pos, literal_length);    output_pos += literal_length;    read(input_pos, match_offset);    copy(output_pos, output_pos - match_offset,        match_length);    output_pos += match_length; } 

Format LZ4 dirancang agar literal dan cocok berganti dalam file terkompresi. Jelas, literal selalu didahulukan (karena tidak ada tempat untuk mengambil kecocokan sejak awal). Oleh karena itu, panjangnya dikodekan bersama.

Sebenarnya sedikit lebih rumit dari itu. Satu byte dibaca dari file, dan kemudian dibagi menjadi dua nibbles (setengah-byte) yang berisi angka-angka yang dikodekan 0 hingga 15. Jika angka yang sesuai bukan 15, itu diasumsikan sebagai panjang literal dan cocok, masing-masing. Dan jika 15, panjangnya lebih panjang dan dikodekan dalam byte berikut. Kemudian byte selanjutnya dibaca, dan nilainya ditambahkan ke panjangnya. Jika sama dengan 255, hal yang sama dilakukan dengan byte berikutnya.

Perhatikan bahwa rasio kompresi maksimum untuk format LZ4 tidak mencapai 255. Dan pengamatan lain yang tidak berguna adalah bahwa jika data Anda sangat berlebihan, menggunakan LZ4 dua kali akan meningkatkan rasio kompresi.

Ketika kita membaca panjang literal (dan kemudian match match dan offset offset), hanya menyalin dua blok memori sudah cukup untuk mendekompresnya.

Cara menyalin blok memori

Tampaknya Anda hanya bisa menggunakan fungsi memcpy , yang dirancang untuk menyalin blok memori. Tetapi ini bukan pendekatan yang optimal dan tidak terlalu tepat.

Menggunakan memcpy tidak optimal karena:

1. Biasanya terletak di perpustakaan libc (dan perpustakaan libc biasanya terhubung secara dinamis, sehingga panggilan memcpy akan dilakukan secara tidak langsung melalui PLT).
2. Itu tidak diuraikan oleh kompiler jika argumen ukuran tidak diketahui pada waktu kompilasi.
3. Ini mengeluarkan banyak upaya untuk memproses sisa-sisa blok memori dengan benar yang bukan kelipatan dari panjang kata mesin atau register.

Poin terakhir adalah yang paling penting. Katakanlah kita meminta fungsi memcpy untuk menyalin tepat 5 byte. Akan sangat bagus untuk menyalin 8 byte segera, menggunakan dua instruksi movq.

Hello world Hello wo ...
^^^^^ ^^^ - src
^^^^^ ^^^ - dst

Tapi kemudian kita akan menyalin tiga byte tambahan, jadi kita akan menulis di luar batas buffer. Fungsi memcpy tidak memiliki izin untuk melakukan ini, karena bisa menimpa beberapa data dalam program kami dan menyebabkan bug menginjak-injak memori. Dan jika kami menulis ke alamat yang tidak selaras, byte tambahan ini dapat mendarat di halaman memori virtual yang tidak dialokasikan atau pada halaman tanpa akses tulis. Itu akan memberi kita kesalahan segmentasi (ini bagus).

Tetapi dalam kasus kami, kami hampir selalu dapat menulis byte tambahan. Kita dapat membaca byte tambahan di buffer input selama byte tambahan terletak sepenuhnya di dalamnya. Di bawah kondisi yang sama, kita dapat menulis byte tambahan ke buffer output, karena kita masih akan menimpa mereka pada iterasi berikutnya.

Optimasi ini sudah dalam implementasi asli LZ4:

 inline void copy8(UInt8 * dst, const UInt8 * src) {    memcpy(dst, src, 8); /// Note that memcpy isn't actually called here. } inline void wildCopy8(UInt8 * dst, const UInt8 * src, UInt8 * dst_end) {    do    {        copy8(dst, src);        dst += 8;        src += 8;    } while (dst < dst_end); } 

Untuk memanfaatkan optimasi ini, kita hanya perlu memastikan bahwa kita cukup jauh dari batas buffer. Ini seharusnya tidak memerlukan biaya apa pun, karena kami sudah memeriksa buffer overflow. Dan memproses beberapa byte terakhir, data "sisa", dapat dilakukan setelah loop utama.

Namun, masih ada beberapa nuansa. Menyalin terjadi dua kali dalam loop: dengan literal dan kecocokan. Namun, ketika menggunakan fungsi LZ4_decompress_fast (bukan LZ4_decompress_safe ), pemeriksaan dilakukan hanya sekali, ketika kita perlu menyalin literal. Pemeriksaan tidak dilakukan saat menyalin kecocokan, tetapi spesifikasi untuk format LZ4 memiliki kondisi yang memungkinkan Anda untuk menghindarinya:

5 byte terakhir selalu literal.
Pertandingan terakhir harus dimulai setidaknya 12 byte sebelum akhir blok.
Akibatnya, sebuah blok dengan kurang dari 13 byte tidak dapat dikompres.

Data input yang dipilih secara khusus dapat menyebabkan kerusakan memori. Jika Anda menggunakan fungsi LZ4_decompress_fast , Anda perlu perlindungan dari data yang buruk. Paling tidak, Anda harus menghitung checksum untuk data terkompresi. Jika Anda membutuhkan perlindungan dari peretas, gunakan fungsi LZ4_decompress_safe . Pilihan lain: ambil fungsi hash kriptografis sebagai checksum (meskipun ini kemungkinan akan merusak kinerja); mengalokasikan lebih banyak memori untuk buffer; mengalokasikan memori untuk buffer dengan panggilan mmap terpisah dan membuat halaman penjaga.

Ketika saya melihat kode yang menyalin 8 byte data, saya langsung bertanya-tanya mengapa tepatnya 8 byte. Anda dapat menyalin 16 byte menggunakan register SSE:

 inline void copy16(UInt8 * dst, const UInt8 * src) { #if __SSE2__    _mm_storeu_si128(reinterpret_cast<__m128i *>(dst),        _mm_loadu_si128(reinterpret_cast<const __m128i *>(src))); #else    memcpy(dst, src, 16); #endif } inline void wildCopy16(UInt8 * dst, const UInt8 * src, UInt8 * dst_end) {    do    {        copy16(dst, src);        dst += 16;        src += 16;    } while (dst < dst_end); } 

Hal yang sama berfungsi untuk menyalin 32 byte untuk AVX dan 64 byte untuk AVX-512. Selain itu, Anda dapat membuka gulungannya beberapa kali. Jika Anda pernah melihat bagaimana memcpy diimplementasikan, inilah pendekatan yang tepat digunakan. (Omong-omong, kompiler tidak akan membuka gulungan atau membuat vektor loop dalam kasus ini, karena ini akan memerlukan memasukkan cek besar.)

Mengapa implementasi LZ4 asli tidak melakukan ini? Pertama, tidak jelas apakah ini lebih baik atau lebih buruk. Keuntungan yang dihasilkan tergantung pada ukuran blok untuk disalin, jadi jika mereka semua pendek, itu akan menciptakan pekerjaan tambahan tanpa biaya. Dan kedua, itu merusak ketentuan dalam format LZ4 yang membantu menghindari cabang yang tidak perlu dalam loop internal.

Namun, kami akan tetap mengingat opsi ini untuk sementara waktu.

Menyalin rumit

Mari kita kembali ke pertanyaan apakah selalu mungkin untuk menyalin data dengan cara ini. Katakanlah kita perlu menyalin kecocokan, yaitu, mengambil sepotong memori dari buffer output yang terletak di beberapa offset di belakang kursor dan menyalinnya ke posisi kursor.

Bayangkan case sederhana ketika Anda perlu menyalin 5 byte pada offset 12:

Hello world ...........
^^^^^ - src
^^^^^ - dst

Hello world Hello wo ...
^^^^^ - src
^^^^^ - dst

Tetapi ada kasus yang lebih sulit, ketika kita perlu menyalin blok memori yang lebih panjang dari offset. Dengan kata lain, itu termasuk beberapa data yang belum ditulis ke buffer output.

Salin 10 byte pada offset 3:

abc .............
^^^^^^^^^^ - src
^^^^^^^^^^ - dst

abc abcabcabca ...
^^^^^^^^^^ - src
^^^^^^^^^^ - dst

Kami memiliki semua data selama proses kompresi, dan kecocokan tersebut dapat ditemukan. Fungsi memcpy tidak cocok untuk menyalinnya, karena itu tidak mendukung case ketika rentang blok memori tumpang tindih. Fungsi memmove juga tidak berfungsi, karena blok memori tempat data diambil belum sepenuhnya diinisialisasi. Kita perlu menyalin dengan cara yang sama seolah-olah kita menyalin byte demi byte.

 op[0] = match[0]; op[1] = match[1]; op[2] = match[2]; op[3] = match[3]; ... 

Begini cara kerjanya:

a bc a ............
^ - src
^ - dst

a b ca b ...........
^ - src
^ - dst

ab c ab c ..........
^ - src
^ - dst

abc a bc a .........
^ - src
^ - dst

abca b ca b ........
^ - src
^ - dst

Dengan kata lain, kita harus membuat urutan yang berulang. Implementasi asli LZ4 menggunakan beberapa kode yang anehnya aneh untuk melakukan ini:

 const unsigned dec32table[] = {0, 1, 2, 1, 4, 4, 4, 4}; const int dec64table[] = {0, 0, 0, -1, 0, 1, 2, 3}; const int dec64 = dec64table[offset]; op[0] = match[0]; op[1] = match[1]; op[2] = match[2]; op[3] = match[3]; match += dec32table[offset]; memcpy(op+4, match, 4); match -= dec64; 

Ini menyalin 4 byte pertama satu per satu, melompat ke depan dengan beberapa angka ajaib, menyalin 4 byte berikutnya seluruhnya, dan memindahkan kursor ke pertandingan menggunakan nomor ajaib lain. Penulis kode ( Yan Collet ) entah bagaimana lupa memberikan komentar tentang apa artinya ini. Selain itu, nama variabelnya membingungkan. Keduanya dinamai dec ... table, tetapi yang satu ditambahkan dan yang lain dikurangi. Selain itu, salah satunya tidak ditandatangani, dan yang lainnya adalah int. Namun, penulis baru-baru ini memperbaiki tempat ini dalam kode.

Begini cara kerjanya. Kami menyalin 4 byte pertama satu per satu:

abc abca .........
^^^^ - src
^^^^ - dst

Sekarang kita dapat menyalin 4 byte sekaligus:

abcabca bcab .....
^^^^ - src
^^^^ - dst

Kita dapat melanjutkan seperti biasa, menyalin 8 byte sekaligus:

abcabcabcab cabcabca .....
^^^^^^^^ - src
^^^^^^^^ - dst

Seperti yang kita ketahui dari pengalaman, terkadang cara terbaik untuk memahami kode adalah menulis ulang. Inilah yang kami temukan:

 inline void copyOverlap8(UInt8 * op, const UInt8 *& match, const size_t offset) {    /// 4 % n.    /// Or if 4 % n is zero, we use n.    /// It gives an equivalent result, but is more CPU friendly for unknown reasons.    static constexpr int shift1[] = { 0, 1, 2, 1, 4, 4, 4, 4 };    /// 8 % n - 4 % n    static constexpr int shift2[] = { 0, 0, 0, 1, 0, -1, -2, -3 };    op[0] = match[0];    op[1] = match[1];    op[2] = match[2];    op[3] = match[3];    match += shift1[offset];    memcpy(op + 4, match, 4);    match += shift2[offset]; } 

Seperti yang diharapkan, ini tidak mengubah kinerja sama sekali. Saya hanya benar-benar ingin mencoba optimasi untuk menyalin 16 byte sekaligus.

Namun, ini mempersulit "kasus khusus" dan membuatnya disebut lebih sering (kondisi offset < 16 dilakukan setidaknya sesering offset < 8 ). Menyalin rentang yang tumpang tindih dengan penyalinan 16 byte terlihat seperti ini (hanya yang awalnya ditunjukkan):

 inline void copyOverlap16(UInt8 * op, const UInt8 *& match, const size_t offset) {    /// 4 % n.    static constexpr int shift1[]        = { 0, 1, 2, 1, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4 };    /// 8 % n - 4 % n    static constexpr int shift2[]        = { 0, 0, 0, 1, 0, -1, -2, -3, -4, 4, 4, 4, 4, 4, 4, 4 };    /// 16 % n - 8 % n    static constexpr int shift3[]        = { 0, 0, 0, -1, 0, -2, 2, 1, 8, -1, -2, -3, -4, -5, -6, -7 };    op[0] = match[0];    op[1] = match[1];    op[2] = match[2];    op[3] = match[3];    match += shift1[offset];    memcpy(op + 4, match, 4);    match += shift2[offset];    memcpy(op + 8, match, 8);    match += shift3[offset]; } 

Bisakah fungsi ini diterapkan lebih efektif? Kami ingin menemukan instruksi SIMD ajaib untuk kode rumit seperti itu, karena semua yang ingin kami lakukan adalah menulis 16 byte, yang seluruhnya terdiri dari beberapa byte data input (dari 1 hingga 15). Maka mereka hanya perlu diulang dalam urutan yang benar.

Ada instruksi seperti ini yang disebut pshufb (byte shuffle dikemas) yang merupakan bagian dari SSSE3 (tiga S). Ia menerima dua register 16-byte. Salah satu register berisi data sumber. Yang lain memiliki "selector": setiap byte berisi angka dari 0 hingga 15, tergantung pada byte dari register sumber untuk mengambil hasilnya. Jika nilai byte pemilih lebih besar dari 127, byte hasil yang sesuai diisi dengan nol.

Berikut ini sebuah contoh:

  xmm0: abc .............
 xmm1: 0120120120120120

 pshufb% xmm1,% xmm0

 xmm0: abcabcabcabcabca 

Setiap byte dari hasil diisi dengan byte yang dipilih dari sumber data - inilah yang kita butuhkan! Seperti apa kode ini dalam hasilnya:

 inline void copyOverlap16Shuffle(UInt8 * op, const UInt8 *& match, const size_t offset) { #ifdef __SSSE3__    static constexpr UInt8 __attribute__((__aligned__(16))) masks[] =    {        0, 1, 2, 1, 4, 1, 4, 2, 8, 7, 6, 5, 4, 3, 2, 1, /* offset = 0, not used as mask, but for shift amount instead */        0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, /* offset = 1 */        0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1,        0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0,        0, 1, 2, 3, 0, 1, 2, 3, 0, 1, 2, 3, 0, 1, 2, 3,        0, 1, 2, 3, 4, 0, 1, 2, 3, 4, 0, 1, 2, 3, 4, 0,        0, 1, 2, 3, 4, 5, 0, 1, 2, 3, 4, 5, 0, 1, 2, 3,        0, 1, 2, 3, 4, 5, 6, 0, 1, 2, 3, 4, 5, 6, 0, 1,        0, 1, 2, 3, 4, 5, 6, 7, 0, 1, 2, 3, 4, 5, 6, 7,        0, 1, 2, 3, 4, 5, 6, 7, 8, 0, 1, 2, 3, 4, 5, 6,        0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1, 2, 3, 4, 5,        0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 0, 1, 2, 3, 4,        0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 0, 1, 2, 3,        0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 0, 1, 2,        0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 0, 1,        0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 0,    };    _mm_storeu_si128(reinterpret_cast<__m128i *>(op),        _mm_shuffle_epi8(            _mm_loadu_si128(reinterpret_cast<const __m128i *>(match)),            _mm_load_si128(reinterpret_cast<const __m128i *>(masks) + offset)));    match += masks[offset]; #else    copyOverlap16(op, match, offset); #endif } 

Di sini _mm_shuffle_epi8 adalah intrinsik , yang mengkompilasi ke instruksi CPU pshufb .

Bisakah kita melakukan operasi ini untuk lebih banyak byte sekaligus menggunakan instruksi yang lebih baru? Setelah semua, SSSE3 adalah set instruksi yang sangat lama yang telah ada sejak tahun 2006. AVX2 memiliki instruksi yang melakukan ini untuk 32 byte sekaligus, tetapi secara terpisah untuk jalur individu 16-byte. Ini disebut vektor permute bytes, daripada byte shuffle yang dikemas - kata-katanya berbeda, tetapi artinya sama. AVX-512 VBMI memiliki instruksi lain yang bekerja untuk 64 byte sekaligus, tetapi prosesor yang mendukungnya hanya muncul baru-baru ini. ARM NEON memiliki instruksi serupa yang disebut vtbl (pencarian tabel vektor), tetapi mereka hanya mengizinkan penulisan 8 byte.

Selain itu, ada versi instruksi pshufb dengan register MMX 64-bit untuk membentuk 8 byte. Ini tepat untuk mengganti versi kode yang asli. Namun, saya memutuskan untuk menggunakan opsi 16-byte sebagai gantinya (untuk alasan serius).

Pada konferensi Highload ++ Siberia, seorang peserta mendatangi saya setelah presentasi saya dan menyebutkan bahwa untuk kasus 8-byte, Anda dapat menggunakan perkalian dengan konstanta yang dipilih secara khusus (Anda juga akan memerlukan offset) - ini bahkan belum terjadi kepada saya sebelumnya!

Bagaimana menghapus pernyataan if berlebihan

Katakanlah saya ingin menggunakan varian yang menyalin 16 byte. Bagaimana saya bisa menghindari harus melakukan pemeriksaan tambahan untuk buffer overflow?

Saya memutuskan bahwa saya tidak akan melakukan pemeriksaan ini. Komentar pada fungsi akan mengatakan bahwa pengembang harus mengalokasikan blok memori untuk jumlah byte yang ditentukan lebih dari yang diperlukan, sehingga kita dapat membaca dan menulis sampah yang tidak perlu di sana. Antarmuka fungsi akan lebih sulit digunakan, tetapi ini adalah masalah yang berbeda.

Sebenarnya, bisa ada konsekuensi negatif. Katakanlah data yang kita perlu dekompresi dibentuk dari blok masing-masing 65.536 byte. Kemudian pengguna memberi kami sepotong memori yang 65.536 byte untuk data yang dikompresi. Tetapi dengan antarmuka fungsi baru, pengguna akan diminta untuk mengalokasikan blok memori yang 65.551 byte, misalnya. Kemudian pengalokasi mungkin dipaksa untuk benar-benar mengalokasikan 96 atau bahkan 128 kilobyte, tergantung pada implementasinya. Jika pengalokasi sangat buruk, itu mungkin tiba-tiba berhenti caching memori di "heap" dan mulai menggunakan mmap dan munmap setiap kali untuk alokasi memori (atau lepaskan memori menggunakan madvice ). Proses ini akan sangat lambat karena kesalahan halaman. Akibatnya, sedikit pengoptimalan ini mungkin akan memperlambat segalanya.

Apakah ada akselerasi?

Jadi saya membuat versi kode yang menggunakan tiga optimasi:

1. Menyalin 16 byte, bukan 8.
2. Menggunakan instruksi acak untuk kasus offset < 16 .
3. Menghapus satu ekstra jika.

Saya mulai menguji kode ini pada set data yang berbeda dan mendapatkan hasil yang tidak terduga.

Contoh 1:
Xeon E2650v2, data Browser Yandex, kolom AppVersion.
Referensi: 1,67 GB / detik.
16 byte, acak: 2,94 GB / detik (76% lebih cepat).

Contoh 2:
Xeon E2650v2, data Yandex Direct, kolom ShowsSumPosition.
Referensi: 2,30 GB / detik.
16 byte, acak: 1,91 GB / detik (20% lebih lambat).

Saya sangat senang pada awalnya, ketika saya melihat bahwa semuanya telah dipercepat dengan persentase yang begitu besar. Kemudian saya melihat bahwa tidak ada yang lebih cepat dengan file lain. Bahkan sedikit lebih lambat bagi beberapa dari mereka. Saya menyimpulkan bahwa hasilnya tergantung pada rasio kompresi. Semakin kompres file, semakin besar keuntungan beralih ke 16 byte. Ini terasa alami: semakin besar rasio kompresi, semakin lama panjang rata-rata fragmen untuk disalin.

Untuk menyelidiki, saya menggunakan template C ++ untuk membuat opsi kode untuk empat kasus: menggunakan potongan 8-byte atau 16-byte, dan dengan atau tanpa instruksi acak.

 template <size_t copy_amount, bool use_shuffle> void NO_INLINE decompressImpl(    const char * const source,    char * const dest,    size_t dest_size) 

Varian kode yang sepenuhnya berbeda bekerja lebih baik pada file yang berbeda, tetapi ketika menguji pada desktop versi dengan shuffle selalu menang. Pengujian pada desktop tidak nyaman karena Anda harus melakukan ini:

 sudo echo 'performance' | tee /sys/devices/system/cpu/cpu*/cpufreq/scaling_governor kill -STOP $(pidof firefox) $(pidof chromium) 

Kemudian saya pergi ke salah satu server "development" lama (dengan prosesor Xeon E5645), mengambil lebih banyak dataset, dan mendapatkan hasil yang hampir berlawanan, yang benar-benar membingungkan saya. Ternyata pilihan algoritma optimal tergantung pada model prosesor, selain rasio kompresi. Prosesor menentukan kapan waktu terbaik untuk menggunakan instruksi shuffle, serta ambang batas kapan mulai menggunakan penyalinan 16 byte.

Omong-omong, saat menguji pada server kami, masuk akal untuk melakukan ini:

 sudo kill -STOP $(pidof python) $(pidof perl) $(pgrep -u skynet) $(pidof cqudp-client) 

Kalau tidak, hasilnya akan tidak stabil. Juga waspada terhadap pembatasan termal dan pembatasan daya.

Bagaimana memilih algoritma terbaik

Jadi kami memiliki empat varian dari algoritma dan kami harus memilih yang terbaik untuk kondisi. Kita dapat membuat kumpulan data dan perangkat keras yang representatif, kemudian melakukan pengujian beban serius dan memilih metode yang rata-rata terbaik. Tetapi kami tidak memiliki dataset yang representatif. Untuk pengujian saya menggunakan sampel data dari Yandex Metrica , Yandex Direct, Yandex Browser, dan penerbangan di Amerika Serikat . Tetapi ini tidak cukup, karena ClickHouse digunakan oleh ratusan perusahaan di seluruh dunia. Dengan terlalu mengoptimalkan pada satu dataset, kami dapat menyebabkan penurunan kinerja dengan data lain dan bahkan tidak menyadarinya. Dan jika hasilnya tergantung pada model prosesor, kita harus secara eksplisit menulis kondisi dalam kode dan mengujinya pada masing-masing model (atau lihat manual referensi tentang instruksi pengaturan waktu, bagaimana menurut Anda?). Dalam kedua kasus, ini terlalu memakan waktu.

Jadi saya memutuskan untuk menggunakan metode lain, yang jelas bagi rekan-rekan yang belajar di School of Data Analysis kami: "bandit multi-bersenjata" . Intinya adalah bahwa varian dari algoritma dipilih secara acak, dan kemudian kami menggunakan statistik untuk semakin sering memilih opsi yang berkinerja lebih baik.

Kami memiliki banyak blok data yang perlu didekompresi, jadi kami membutuhkan pemanggilan fungsi independen untuk data yang terkompresi. Kita dapat memilih salah satu dari empat algoritma untuk setiap blok dan mengukur waktu pelaksanaannya. Operasi seperti ini biasanya tidak ada biaya dibandingkan dengan memproses blok data, dan di ClickHouse blok data yang tidak terkompresi setidaknya 64 KB. (Baca artikel ini tentang mengukur waktu.)

Untuk mendapatkan pemahaman yang lebih baik tentang bagaimana algoritma "bandit multi-bersenjata" bekerja, mari kita lihat dari mana nama itu berasal. Ini adalah analogi dengan mesin slot di kasino yang memiliki beberapa tuas yang dapat ditarik pemain untuk mendapatkan sejumlah uang acak. Pemain dapat menarik tuas beberapa kali dalam urutan apa pun. Setiap tuas memiliki probabilitas tetap untuk jumlah uang yang sesuai yang diberikan, tetapi pemain tidak tahu cara kerjanya dan hanya bisa mempelajarinya dari pengalaman bermain game. Begitu mereka mengetahuinya, mereka dapat memaksimalkan kemenangan mereka.

Salah satu pendekatan untuk memaksimalkan hadiah adalah dengan mengevaluasi distribusi probabilitas untuk setiap tuas pada setiap langkah berdasarkan statistik permainan dari langkah sebelumnya. Kemudian kami secara mental "memenangkan" hadiah acak untuk setiap tuas, berdasarkan distribusi yang diterima. Akhirnya, kami menarik tuas yang memiliki hasil terbaik dalam permainan mental kami. Pendekatan ini disebut Thompson Sampling.

Tapi kami memilih algoritma dekompresi. Hasilnya adalah waktu eksekusi dalam picoseconds per byte: semakin sedikit, semakin baik. Kami akan menganggap waktu eksekusi sebagai variabel acak dan mengevaluasi distribusinya menggunakan statistik matematika. Pendekatan Bayesian sering digunakan untuk tugas-tugas seperti ini, tetapi akan sulit untuk memasukkan rumus kompleks ke dalam kode C ++. Kita dapat menggunakan pendekatan parametrik dan mengatakan bahwa variabel acak milik keluarga parametrik variabel acak, dan kemudian mengevaluasi parameternya.

Bagaimana kita memilih keluarga variabel acak? Sebagai contoh, kita dapat mengasumsikan bahwa waktu eksekusi kode memiliki distribusi normal. Tapi ini benar-benar salah. Pertama, waktu eksekusi tidak boleh negatif, dan distribusi normal mengambil nilai di mana-mana di garis bilangan. Kedua, saya berasumsi bahwa waktu eksekusi akan memiliki "ekor" yang berat di ujung kanan.

Namun, ada faktor-faktor yang dapat membuat ide yang baik untuk memperkirakan distribusi normal hanya untuk keperluan Thompson Sampling (terlepas dari kenyataan bahwa distribusi variabel target tidak selalu normal). Alasan untuk ini adalah bahwa sangat mudah untuk menghitung ekspektasi matematis dan varians, dan setelah jumlah iterasi yang cukup, distribusi normal menjadi cukup sempit, tidak jauh berbeda dari distribusi yang akan kita peroleh dengan menggunakan metode lain. Jika kami tidak terlalu peduli dengan tingkat konvergensi pada langkah pertama, detail ini dapat diabaikan.

This may seem like a somewhat ignorant approach. Experience has shown us that the average time for query execution, website page loading, and so on is "garbage" that isn't worth calculating. It would be better to calculate the median, which is a robust statistic . But this is a little more difficult, and as I will show later, the described method justifies itself for practical purposes.

At first I implemented calculation of the mathematical expectation and variance, but then I decided that this is too good, and I need to simplify the code to make it "worse":

 /// For better convergence, we don't use proper estimate of stddev. /// We want to eventually separate the two algorithms even in cases /// when there is no statistical significant difference between them. double sigma() const {    return mean() / sqrt(adjustedCount()); } double sample(pcg64 & rng) const {    ...    return std::normal_distribution<>(mean(), sigma())(rng); } 

I wrote it so that the first few iterations were not taken into account, to eliminate the effect of memory latencies.

The result is a test program that can select the best algorithm for the input data, with optional modes that use the reference implementation of LZ4 or a specific version of the algorithm.

So there are six options:
— Reference (baseline): original LZ4 without our modifications.
— Variant 0: copy 8 bytes at a time without shuffle.
— Variant 1: copy 8 bytes at a time with shuffle.
— Variant 2: copy 16 bytes at a time without shuffle.
— Variant 3: copy 16 bytes at a time with shuffle.
— The "bandit" option, which selects the best of the four optimized variants.

Testing on different CPUs

If the result strongly depends on the CPU model, it would be interesting to find out exactly how it is affected. There might be an exceptionally large difference on certain CPUs.

I prepared a set of datasets from different tables in ClickHouse with real data, for a total of 256 different files each with 100 MB of uncompressed data (the number 256 was coincidental). Then I looked at the CPUs of the servers where I can run benchmarks. I found servers with the following CPUs:
— Intel® Xeon® CPU E5-2650 v2 @ 2.60GHz
— Intel® Xeon® CPU E5-2660 v4 @ 2.00GHz
— Intel® Xeon® CPU E5-2660 0 @ 2.20GHz
— Intel® Xeon® CPU E5645 @ 2.40GHz
— Intel Xeon E312xx (Sandy Bridge)
— AMD Opteron(TM) Processor 6274
— AMD Opteron(tm) Processor 6380
— Intel® Xeon® CPU E5-2683 v4 @ 2.10GHz
— Intel® Xeon® CPU E5530 @ 2.40GHz
— Intel® Xeon® CPU E5440 @ 2.83GHz
— Intel® Xeon® CPU E5-2667 v2 @ 3.30GHz

The most interesting part comes next — the processors provided by the R&D department:
— AMD EPYC 7351 16-Core Processor, a new AMD server processor.
— Cavium ThunderX2, which is AArch64, not x86. For these, my SIMD optimization needed to be reworked a bit. The server has 224 logical and 56 physical cores.

There are 13 servers in total, and each of them runs the test on 256 files in 6 variants (reference, 0, 1, 2, 3, adaptive). The test is run 10 times, alternating between the options in random order. It outputs 199,680 results that we can compare.

For example, we can compare different CPUs with each other. But we shouldn't jump to conclusions from these results, because we are only testing the LZ4 decompression algorithm on a single core (this is a very narrow case, so we only get a micro-benchmark). For example, the Cavium has the lowest performance per single core. But I tested ClickHouse on it myself, and it wins out over Xeon E5-2650 v2 on heavy queries due to the greater number of cores, even though it is missing many optimizations that are made in ClickHouse specifically for the x86.

 ┌─cpu───────────────────┬──ref─┬─adapt─┬──max─┬─best─┬─adapt_boost─┬─max_boost─┬─adapt_over_max─┐
│ E5-2667 v2 @ 3.30GHz │ 2.81 │ 3.19 │ 3.15 │ 3 │ 1.14 │ 1.12 │ 1.01 │
│ E5-2650 v2 @ 2.60GHz │ 2.5 │ 2.84 │ 2.81 │ 3 │ 1.14 │ 1.12 │ 1.01 │
│ E5-2683 v4 @ 2.10GHz │ 2.26 │ 2.63 │ 2.59 │ 3 │ 1.16 │ 1.15 │ 1.02 │
│ E5-2660 v4 @ 2.00GHz │ 2.15 │ 2.49 │ 2.46 │ 3 │ 1.16 │ 1.14 │ 1.01 │
│ AMD EPYC 7351 │ 2.03 │ 2.44 │ 2.35 │ 3 │ 1.20 │ 1.16 │ 1.04 │
│ E5-2660 0 @ 2.20GHz │ 2.13 │ 2.39 │ 2.37 │ 3 │ 1.12 │ 1.11 │ 1.01 │
│ E312xx (Sandy Bridge) │ 1.97 │ 2.2 │ 2.18 │ 3 │ 1.12 │ 1.11 │ 1.01 │
│ E5530 @ 2.40GHz │ 1.65 │ 1.93 │ 1.94 │ 3 │ 1.17 │ 1.18 │ 0.99 │
│ E5645 @ 2.40GHz │ 1.65 │ 1.92 │ 1.94 │ 3 │ 1.16 │ 1.18 │ 0.99 │
│ AMD Opteron 6380 │ 1.47 │ 1.58 │ 1.56 │ 1 │ 1.07 │ 1.06 │ 1.01 │
│ AMD Opteron 6274 │ 1.15 │ 1.35 │ 1.35 │ 1 │ 1.17 │ 1.17 │ 1 │
│ E5440 @ 2.83GHz │ 1.35 │ 1.33 │ 1.42 │ 1 │ 0.99 │ 1.05 │ 0.94 │
│ Cavium ThunderX2 │ 0.84 │ 0.87 │ 0.87 │ 0 │ 1.04 │ 1.04 │ 1 │
└───────────────────────┴──────┴───────┴──────┴──────┴─────────────┴───────────┴────────────────┘ 

• ref, adapt, max — The speed in gigabytes per second (the value that is the reverse of the arithmetic mean of time for all launches on all datasets).
• best — The number of the best algorithm among the optimized variants, from 0 to 3.
• adapt_boost — The relative advantage of the adaptive algorithm compared to the baseline.
• max_boost — The relative advantage of the best of the non-adaptive variants compared to the baseline.
• adapt_over_max — The relative advantage of the adaptive algorithm over the best non-adaptive one.

The results show that we were able to speed up decompression by 12-20% on modern x86 processors. Even on ARM we saw 4% improvement, despite the fact that we didn't optimize much for this architecture. It is also clear that on average for different datasets, the "bandit" algorithm comes out ahead of the pre-selected best variant on all processors (except for very old Intel CPUs).

Kesimpulan

In practice, the usefulness of this work is dubious. Yes, LZ4 decompression was accelerated on average by 12-20%, and on some datasets the performance more than doubled. But in general, this doesn't have much effect on query execution time. It's difficult to find real queries that gain more than a couple percent in speed.

We decided to use ZStandard level 1 instead of LZ4 on several Yandex Metrica clusters intended for executing long queries, because it is more important to save IO and disk space on cold data. Keep this in mind if you have similar workload.

We observed the greatest benefits from optimizing decompression in highly compressible data, such as columns with mostly duplicate string values. However, we have developed a separate solution specifically for this scenario that allows us to significantly speed up queries over this kind of data.

Another point to remember is that optimization of decompression speed is often limited by the format of the compressed data. LZ4 uses a very good format, but Lizard, Density and LZSSE have other formats that can work faster. Perhaps instead of trying to accelerate LZ4, it would be better to just integrate LZSSE into ClickHouse.

It's unlikely that these optimizations will be implemented in the mainstream LZ4 library: in order to use them, the library interface would have to be modified. In fact, this is often the case with improving algorithms — optimizations don't fit into old abstractions and they have to be revised. However, variable names have already been corrected in the original implementation. For instance, inc and dec tables have been corrected . In addition, about a month ago, the original implementation accelerated decompression by the same 12-15% by copying 32 bytes instead of 16, as discussed above. We tried the 32-byte option ourselves and the results were not that great, but they were still faster .

If you look at the profile at the beginning of the article, you may notice that we could have removed one extra copying operation from the page cache to userspace (either using mmap , or using O_DIRECT and userspace page cache, but both options are problematic). We also could have slightly improved the checksum calculation (CityHash128 is currently used without CRC32-C, but we could use HighwayHash, FARSH or XXH3). Acceleration of these two operations is useful for weakly compressed data, since they are performed on compressed data.

In any case, the changes have already been added to master more than a year ago, and the ideas that resulted from this research have been applied in other tasks. You can also watch the video from HighLoad++ Siberia, or view the presentation (both in Russian).