☦️ 😯 😣 كيفية تسريع عملية تفريغ LZ4 في ClickHouse 〽️ 👊🏼 🚣🏽

عند تنفيذ الاستعلامات في ClickHouse ، يمكنك ملاحظة أن وظيفة LZ_decompress_fast في الملف الشخصي ، في أحد الأماكن الأولى ، غالبًا ما تكون مرئية. لماذا يحدث هذا؟ أصبح هذا السؤال السبب وراء الدراسة بأكملها حول اختيار أفضل خوارزمية تخفيف الضغط. أنا هنا أنشر الدراسة بأكملها ، ويمكن العثور على النسخة القصيرة في تقريري على HighLoad ++ Siberia.

يتم تخزين بيانات ClickHouse في شكل مضغوط. وأثناء تنفيذ الطلبات ، يحاول ClickHouse عدم القيام بأي شيء تقريبًا - استخدام الحد الأدنى من موارد وحدة المعالجة المركزية. يحدث أن جميع الحسابات التي قد تستغرق بعض الوقت قد تم تحسينها بالفعل بشكل جيد ، وأن الطلب مكتوب بشكل جيد من قبل المستخدم. ثم يبقى لأداء الإصدار.

والسؤال هو - لماذا يمكن أن يكون تفريغ LZ4 عنق الزجاجة؟ يبدو أن LZ4 عبارة عن خوارزمية خفيفة الوزن للغاية : يتراوح معدل الضغط ، اعتمادًا على البيانات ، من 1 إلى 3 جيجابايت / ثانية لكل كور معالج. هذا أكثر بكثير من سرعة النظام الفرعي للقرص. علاوة على ذلك ، نحن نستخدم جميع النواة المتاحة ، ومقاييس التوسيع خطيا عبر جميع النوى المادية.

ولكن هناك نقطتان يجب مراعاتهما. أولاً ، يتم قراءة البيانات المضغوطة من القرص ، ويتم إعطاء معدل الضغط في مقدار البيانات غير المضغوطة. إذا كانت نسبة الضغط كبيرة بما فيه الكفاية ، فلن تحتاج إلى قراءة أي شيء تقريبًا من الأقراص. ولكن في الوقت نفسه ، يتم إنشاء الكثير من البيانات المضغوطة ، وبالطبع ، يؤثر هذا على استهلاك وحدة المعالجة المركزية: يتناسب حجم ضغط البيانات في حالة LZ4 تقريبًا مع حجم البيانات المضغوطة نفسها.

ثانياً ، قد لا تكون قراءة البيانات من الأقراص مطلوبة على الإطلاق إذا كانت البيانات في ذاكرة التخزين المؤقت. للقيام بذلك ، يمكنك الاعتماد على ذاكرة التخزين المؤقت للصفحة أو استخدام ذاكرة التخزين المؤقت الخاصة بك. في قاعدة بيانات الأعمدة ، يكون استخدام ذاكرة التخزين المؤقت أكثر فعالية نظرًا لحقيقة أنه لا تقع جميع الأعمدة فيه ، ولكن فقط الأعمدة المستخدمة بشكل متكرر. هذا هو السبب LZ4 ، من حيث تحميل وحدة المعالجة المركزية ، وغالبا ما يكون عنق الزجاجة.

ومن هنا سؤالان آخران. إذا كان ضغط البيانات "يبطئ" ، فعندئذ ربما لا ينبغي ضغطها على الإطلاق؟ لكن في الممارسة العملية ، هذا الافتراض لا معنى له. تم مؤخرًا في ClickHouse تكوين خيارين لضغط البيانات فقط - LZ4 و Zstandard . الافتراضي هو LZ4. من خلال التحول إلى Zstandard ، يمكنك جعل الضغط أقوى وأبطأ. ولكن كان من المستحيل تعطيل الضغط تمامًا حتى وقت قريب - يعتبر LZ4 كحد أدنى معقولًا ، والذي يمكن استخدامه دائمًا. هذا هو السبب في أنني حقا أحب LZ4. :)

لكن في الآونة الأخيرة ، ظهر شخص غريب غامض في دردشة الدردشة ClickHouse الناطقة بالإنجليزية ، والذي قال إنه لديه نظام فرعي سريع للغاية للقرص (NVMe SSD) وكل شيء يعتمد على الضغط - سيكون من الرائع أن تكون قادرًا على إيقاف تشغيله. أجبته أنه لا يوجد مثل هذا الاحتمال ، لكن من السهل إضافته. بعد بضعة أيام تلقينا طلب تجمع ، والذي ينفذ طريقة الضغط none . لقد طلبت النتائج - إلى أي مدى ساعد هذا الأمر ، ومدى سرعة الطلبات. قال الشخص إن هذه الميزة الجديدة تحولت إلى فائدة من الناحية العملية ، حيث بدأت البيانات بدون ضغط في شغل مساحة كبيرة جدًا.

السؤال الثاني الذي يطرح نفسه هو: إذا كان هناك ذاكرة تخزين مؤقت ، فلماذا لا تخزن البيانات غير المضغوطة بالفعل فيه؟ هذا مسموح به - في كثير من الحالات سيكون من الممكن التخلص من الحاجة إلى إزالة الضغط. وفي ClickHouse يوجد ذاكرة تخزين مؤقت مثل ذاكرة التخزين المؤقت للكتل الموسعة . لكن من المؤسف أن تنفق الكثير من ذاكرة الوصول العشوائي عليها بسبب كفاءتها المنخفضة. يبرر نفسه فقط على الطلبات الصغيرة المتتالية التي تستخدم نفس البيانات تقريبًا.

اعتبارات عامة: يجب ضغط البيانات ، ويفضل دائمًا. احرقها دائمًا على قرص مضغوط. نقل عبر الشبكة أيضا مع الضغط. في رأيي ، يجب اعتبار الضغط الافتراضي مبررًا حتى عند النقل إلى شبكة ذات 10 غيغابت دون زيادة الاشتراك في مركز البيانات ، ونقل البيانات دون ضغط بين مراكز البيانات غير مقبول عمومًا.

لماذا LZ4؟

لماذا يتم استخدام LZ4؟ هل من الممكن اختيار شيء أسهل؟ من حيث المبدأ ، هذا ممكن ، وهو حق ومفيد. ولكن دعونا أولاً نلقي نظرة على فئة الخوارزميات التي تنتمي إليها LZ4.

أولاً ، لا يعتمد على نوع البيانات. على سبيل المثال ، إذا كنت تعلم مقدمًا أنه سيكون لديك مجموعة من الأعداد الصحيحة ، فيمكنك استخدام أحد المتغيرات العديدة لخوارزمية VarInt - سيكون أكثر فعالية على وحدة المعالجة المركزية. ثانياً ، لا يعتمد LZ4 كثيرًا على الافتراضات المطلوبة في نموذج البيانات. افترض أن لديك سلسلة زمنية مطلوبة من قراءات المستشعر - صفيف به أرقام من النوع float. بعد ذلك ، يمكنك حساب الدلتا ثم الضغط أكثر ، وسيكون ذلك أكثر فعالية من حيث نسبة الضغط.

هذا هو ، LZ4 يمكن استخدامها دون مشاكل لأي صفائف بايت - لأية ملفات. بالطبع ، لديه تخصصه الخاص (أكثر في ذلك أدناه) ، وفي بعض الحالات يكون استخدامه بلا معنى. ولكن إذا أسميتها خوارزمية للأغراض العامة ، فسيكون هذا خطأ بسيطًا. ولاحظ أنه بفضل الجهاز الداخلي ، يقوم LZ4 تلقائيًا بتنفيذ خوارزمية RLE كحالة خاصة.

سؤال آخر: هل LZ4 هو الخوارزمية المثلى لهذه الفئة من أجل الجمع بين السرعة وقوة الضغط؟ تسمى هذه الخوارزميات باريتو الحدودي - وهذا يعني أنه لا توجد خوارزمية أخرى أفضل بشكل صارم في مؤشر واحد وليس أسوأ في غيرها (وحتى في مجموعة واسعة من مجموعات البيانات). هناك خوارزميات أسرع ، ولكنها تعطي نسبة ضغط أقل ، وتلك التي تضغط أكثر ، ولكن في نفس الوقت أبطأ أو ضغط أبطأ.

في الواقع ، فإن LZ4 ليس حدودًا باريتو. هناك خيارات أفضل قليلاً. على سبيل المثال ، هذا هو LZTURBO من powturbo معين. ليس هناك شك في موثوقية النتائج بفضل المجتمع على encode.ru (وهو أكبر منتدى تقريبًا والضغط الوحيد لضغط البيانات). لكن المطور لا يوزع الكود المصدري أو الثنائيات ، لكنه يعطيهم فقط لدائرة محدودة من الناس للاختبار أو مقابل الكثير من المال (مثلما لم يدفع أي شخص حتى الآن). يستحق أيضًا الانتباه إلى السحلية (LZ5 سابقًا) والكثافة . يمكنهم العمل بشكل أفضل قليلاً من LZ4 عند اختيار مستوى ضغط. انتبه أيضًا إلى LZSSE - شيء مثير جدًا للاهتمام. ومع ذلك ، من الأفضل أن ننظر إليه بعد قراءة هذا المقال.

كيف يعمل LZ4؟

دعونا ننظر في كيفية عمل LZ4 بشكل عام. هذا أحد تطبيقات خوارزمية LZ77: يشير L و Z إلى أسماء المؤلفين (Lempel و Ziv) ، و 77 - في عام 1977 ، عندما تم نشر الخوارزمية. لديها العديد من التطبيقات الأخرى: QuickLZ ، FastLZ ، BriefLZ ، LZF ، LZO ، وكذلك gzip و zip عند استخدام مستويات ضغط منخفضة.

تحتوي كتلة البيانات المضغوطة باستخدام LZ4 على سلسلة من السجلات (الأوامر والتعليمات) من نوعين:

حرفي: "خذ البايتات N التالية كما هي وانسخها إلى النتيجة."
المطابقة (المطابقة): "خذ N بايت التي تم فك ضغطها بالفعل بواسطة إزاحة الإزاحة من الموضع الحالي."

مثال قبل الضغط:
Hello world Hello

بعد الضغط:
literals 12 "Hello world " match 5 12

إذا أخذنا كتلة مضغوطة وذهبنا إليها من خلال المؤشر ، وتنفيذ هذه الأوامر ، فسنحصل على البيانات الأولية غير المضغوطة كنتيجة لذلك.

نظرنا تقريبًا في كيفية فك ضغط البيانات. النقطة واضحة أيضًا: لإجراء الضغط ، تقوم الخوارزمية بتشفير تكرار تسلسل البايت باستخدام التطابقات.

واضح وبعض الخصائص. هذه الخوارزمية موجهة نحو البايت - فهي لا تشريح البايتات الفردية ، ولكنها تنسخها بالكامل. هنا يكمن الفرق ، على سبيل المثال ، من الترميز الانتروبيا. على سبيل المثال ، zstd هو تكوين LZ77 وترميز إنتروبي.

لاحظ أنه لا يتم اختيار حجم الكتلة المضغوطة كبيرًا جدًا بحيث لا تنفق الكثير من ذاكرة الوصول العشوائي أثناء التفريغ ؛ حتى لا تبطئ الوصول العشوائي في ملف مضغوط (والذي يتكون من العديد من الكتل المضغوطة) ؛ وفي بعض الأحيان بحيث يناسب الكتلة في بعض ذاكرة التخزين المؤقت وحدة المعالجة المركزية. على سبيل المثال ، يمكنك اختيار 64 كيلو بايت - لذلك ستوضع المخازن المؤقتة للبيانات المضغوطة وغير المضغوطة في ذاكرة التخزين المؤقت L2 وسيظل النصف.

إذا احتجنا إلى ضغط ملف أكبر ، فسنقوم ببساطة بتسلسل الكتل المضغوطة. في الوقت نفسه ، بجانب كل كتلة مضغوطة ، من المناسب وضع بيانات إضافية - أحجام ، تحقق من المجموع.

الإزاحة القصوى للمباراة محدودة ، بـ LZ4 - 64 كيلو بايت. تسمى هذه القيمة نافذة انزلاقية. في الواقع ، هذا يعني أنه عندما يتحرك المؤشر للأمام ، يمكن أن تكون المطابقات في نافذة من 64 كيلو بايت في الحجم إلى المؤشر ، والذي يتحرك مع المؤشر.

الآن دعونا نلقي نظرة على كيفية ضغط البيانات - بمعنى آخر ، كيفية العثور على تسلسلات مطابقة في ملف. بالطبع ، يمكنك استخدام اللاحقة trie (رائعة إذا سمعت بها). هناك خيارات يكون فيها أطول تسلسل مطابق مضمون ليكون بين البايتات السابقة في عملية الضغط. وهذا ما يسمى تحليل الأمثل ويعطي نسبة ضغط أفضل تقريبا لتنسيق كتلة مضغوطة ثابتة. ولكن هناك خيارات أكثر فاعلية - عندما نجد بعض التطابق الجيد في البيانات ، ولكن ليس بالضرورة الأطول. الطريقة الأكثر فاعلية للعثور عليه هي استخدام جدول التجزئة.

للقيام بذلك ، نذهب من خلال كتلة البيانات المصدر مع المؤشر ونأخذ بضع بايت بعد المؤشر. على سبيل المثال ، 4 بايت. قم بتجميعها ووضعها في جدول التجزئة الإزاحة من بداية الكتلة - حيث قابلت هذه البايتات الأربعة. القيمة 4 تسمى min-match - بمساعدة جدول التجزئة هذا ، يمكننا إيجاد تطابقات لا تقل عن 4 بايت.

إذا نظرنا إلى جدول التجزئة ، وكان هناك بالفعل سجل هناك ، وإذا كان الإزاحة لا يتجاوز النافذة المنزلقة ، فإننا نتحقق من عدد البايتات الإضافية التي تتطابق بعد هذه البايتات الأربعة. ربما هناك الكثير الذي يتزامن. من الممكن أيضًا أن يحدث تصادم في جدول التجزئة ولا يوجد شيء مطابق له. هذا أمر طبيعي - يمكنك ببساطة استبدال القيمة في جدول التجزئة بآخر جديد. سوف يؤدي التصادم في جدول التجزئة ببساطة إلى انخفاض نسبة الضغط نظرًا لوجود عدد أقل من التطابقات. بالمناسبة ، يسمى هذا النوع من جدول التجزئة (بحجم ثابت وبدون تصادم) جدول ذاكرة التخزين المؤقت ، جدول ذاكرة التخزين المؤقت. هذا أيضًا منطقي - في حالة حدوث تصادم ، ينسى جدول ذاكرة التخزين المؤقت السجل القديم فقط.

مهمة للقارئ اليقظ. دع البيانات تكون عبارة عن مجموعة من الأرقام مثل UInt32 بتنسيق endian الصغير ، وهو جزء من سلسلة من الأرقام الطبيعية: 0 ، 1 ، 2 ... وضح لماذا عند استخدام LZ4 ، لا يتم ضغط هذه البيانات (كمية البيانات المضغوطة لا تقل عن كمية البيانات غير المضغوطة).

كيفية تسريع الامور

لذلك ، أريد تسريع عملية تفريغ LZ4. دعونا نرى كيف تبدو دورة التفريغ. هنا هو حلقة في الكود الكاذب:

  بينما (...)
 {
     قراءة (input_pos ، literal_length ، match_length) ؛

     copy (output_pos، input_pos، literal_length)؛
     output_pos + = literal_length؛

     قراءة (input_pos ، match_offset) ؛

     نسخة (output_pos ، output_pos - match_offset ،
         match_length)؛
     output_pos + = match_length؛
 }

تم تصميم تنسيق LZ4 بحيث تتوافق القيم الحرفية والمطابقة في ملف مضغوط. ومن الواضح أن الحرفي يأتي دائمًا أولاً (لأنه من البداية لا يوجد مكان يمكن أن تحصل عليه المباراة). لذلك ، يتم ترميز أطوالها معًا.

في الواقع ، كل شيء أكثر تعقيدًا قليلاً. تتم قراءة بايت واحد من الملف ، ويتم أخذ حلمتين منه ، حيث يتم ترميز الأرقام من 0 إلى 15. إذا كان الرقم المقابل لا يساوي 15 ، فيُعتبر طول الحرفي والمطابقة ، على التوالي. وإذا كان الرقم 15 ، فسيكون الطول أطول ويتم ترميزه بالبايتات التالية. ثم يتم قراءة البايت التالي ، وتتم إضافة قيمته إلى الطول. علاوة على ذلك ، إذا كان يساوي 255 ، فسنستمر - نقرأ البايتة التالية بنفس الطريقة.

لاحظ أن الحد الأقصى لنسبة الضغط لتنسيق LZ4 لا يصل إلى 255. والملاحظة الثانية (عديمة الفائدة): إذا كانت بياناتك زائدة عن الحاجة ، فسيؤدي استخدام LZ4 إلى مضاعفة نسبة الضغط.

عندما نقرأ طول الحرف (ثم أيضًا طول المباراة وإزاحة المباراة) ، لإلغاء تكفيه يكفي فقط نسخ قطعتين من الذاكرة.

كيفية نسخ قطعة من الذاكرة

يبدو أنه يمكنك استخدام وظيفة memcpy ، المصممة فقط لنسخ أجزاء من الذاكرة. ولكن هذا ليس الأمثل ولا يزال غير صحيح.

لماذا يتم استخدام الدالة memcpy دون المستوى الأمثل؟ لأنها هي:

عادةً ما تكون موجودة في مكتبة libc (وعادةً ما ترتبط مكتبة libc ديناميكيًا ، وسوف يتم استدعاء memcpy بشكل غير مباشر ، عبر PLT) ،
لا يتماشى مع وسيطة الحجم غير معروفة في وقت الترجمة ،
يبذل الكثير من الجهد لمعالجة "ذيول" جزء من الذاكرة بشكل صحيح والتي لا تتعدى حجم كلمة الجهاز أو التسجيل.

النقطة الأخيرة هي الأكثر أهمية. لنفترض أننا طلبنا من وظيفة memcpy نسخ 5 بايت بالضبط. سيكون من الجيد جدًا نسخ 8 بايت في آن واحد ، باستخدام إرشادات movq لهذا الغرض.

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

ولكن بعد ذلك سنقوم بنسخ ثلاث وحدات بايت إضافية - أي ، سنكتب إلى الخارج المخزن المؤقت الذي تم نقله. لا تملك وظيفة memcpy الحق في القيام بذلك - في الواقع ، لأننا سنستبدل بعض البيانات في برنامجنا ، سيكون هناك "مرور" من الذاكرة. وإذا كتبنا على عنوان غير محاذٍ ، فيمكن وضع وحدات البايت الإضافية هذه على صفحة ذاكرة ظاهرية غير مخصصة أو على صفحة بدون وصول للكتابة. ثم نحصل على segfault (هذا جيد).

ولكن في حالتنا ، يمكننا دائمًا كتابة بايتات إضافية. يمكننا قراءة وحدات البايت الإضافية في مخزن الإدخال المؤقت طالما توجد وحدات البايت الإضافية فيه بالكامل. في ظل نفس الظروف ، يمكننا كتابة بايتات إضافية إلى المخزن المؤقت للإخراج - لأنه في التكرار التالي سنقوم بالكتابة فوقها على أي حال.

هذا التحسين موجود بالفعل في تطبيق LZ4 الأصلي:

  copy8 مضمّنة copy8 (UInt8 * dst ، const UInt8 * src)
 {
     memcpy (dst، src، 8)؛  /// في الواقع ، memcpy لا يسمى هنا.
 }

 wildCopy8 مضمّنة (UInt8 * dst ، const UInt8 * src ، UInt8 * dst_end)
 {
     فعل
     {
         copy8 (dst، src)؛
         dst + = 8 ؛
         src + = 8؛
     } بينما (dst <dst_end) ؛
 }

للاستفادة من هذا التحسين ، تحتاج فقط إلى التحقق من أننا بعيدون عن حدود المخزن المؤقت. يجب أن يكون هذا مجانًا ، لأننا نتحقق بالفعل من تجاوز حدود المخزن المؤقت. ويمكن معالجة البايتات القليلة الأخيرة - "ذيل" البيانات - بعد الحلقة الرئيسية.

ومع ذلك ، لا تزال هناك بعض التفاصيل الدقيقة. هناك نسختان في الدورة - الحرفي والمباراة. ولكن عند استخدام دالة LZ4_decompress_fast (بدلاً من LZ4_decompress_safe) ، يتم إجراء التحقق مرة واحدة - عندما نحتاج إلى نسخ الحرفي. عند نسخ التطابق ، لا يتم إجراء التحقق ، ولكن في مواصفات تنسيق LZ4 ، هناك شروط تسمح بتجنبها :

البايت الخمس الأخيرة هي دائمًا حرفية
يجب أن تبدأ المطابقة الأخيرة 12 بايت على الأقل قبل نهاية الكتلة.
وبالتالي ، لا يمكن ضغط كتلة بها أقل من 13 بايت.

يمكن أن تتسبب بيانات الإدخال المحددة بشكل خاص في محرك ذاكرة. إذا كنت تستخدم وظيفة LZ4_decompress_fast ، فأنت بحاجة إلى حماية ضد البيانات السيئة. يجب أن تكون البيانات المضغوطة عبارة عن شيك على الأقل. وإذا كنت بحاجة إلى حماية ضد أحد المهاجمين ، فاستخدم الدالة LZ4_decompress_safe. خيارات أخرى: خذ وظيفة تجزئة التشفير كمجموع تحقق ، ولكن من المؤكد أنه سيقتل كل الأداء ؛ إما تخصيص المزيد من الذاكرة المخازن المؤقتة؛ إما تخصيص ذاكرة المخازن المؤقتة مع استدعاء منفصل إلى mmap وإنشاء صفحة حماية.

عندما أرى رمزًا ينسخ بيانات 8 بايت ، أطلب على الفور - لماذا بالضبط 8 بايت؟ يمكنك نسخ 16 بايت باستخدام سجلات SSE:

  نسخة مضمنة من النسخة 16 (UInt8 * dst ، const UInt8 * src)
 {
 # إذا __SSE2__
     _mm_storeu_si128 (reinterpret_cast <__ m128i *> (dst) ،
         _mm_loadu_si128 (reinterpret_cast <const __m128i *> (src))) ؛
 #else
     memcpy (dst، src، 16)؛
 #endif
 }

 wildCopy16 مضمن (UInt8 * dst ، const UInt8 * src ، UInt8 * dst_end)
 {
     فعل
     {
         copy16 (dst، src)؛
         dst + = 16 ؛
         src + = 16؛
     } بينما (dst <dst_end) ؛
 }

نسخ 32 بايت لـ AVX و 64 بايت لـ AVX-512 يعمل بشكل مشابه. بالإضافة إلى ذلك ، يمكنك توسيع الدورة عدة مرات. إذا كنت قد نظرت من أي وقت مضى في كيفية تنفيذ memcpy ، فهذا هو بالضبط النهج. (بالمناسبة ، لن يقوم المترجم في هذه الحالة بتوسيع الحلقة أو توجيهها: سيتطلب ذلك إدخال اختبارات مرهقة.)

لماذا لا يتم ذلك في تطبيق LZ4 الأصلي؟ أولاً ، ليس من الواضح ما إذا كان هذا أفضل أم أسوأ. تعتمد النتيجة على أحجام الأجزاء التي يجب نسخها. فجأة هم جميعا قصيرة والعمل الإضافي سيكون عديم الفائدة؟ وثانيا ، إنه يدمر تلك الشروط في تنسيق LZ4 والتي تسمح لك بتجنب الغداء غير الضروري في الحلقة الداخلية.

ومع ذلك ، سوف نبقي هذا الخيار في الاعتبار الآن.

نسخة صعبة

عودة إلى السؤال - هل من الممكن دائمًا نسخ البيانات بهذه الطريقة؟ افترض أننا بحاجة إلى نسخ تطابق - أي ، نسخ جزء من الذاكرة من المخزن المؤقت الإخراج الذي يتم إزاحة بعض خلف المؤشر إلى موضع هذا المؤشر.

تخيل حالة بسيطة - تحتاج إلى نسخ 5 بايت في الإزاحة 12:

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

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

ولكن هناك حالة أكثر تعقيدًا - عندما نحتاج إلى نسخ قطعة من الذاكرة طولها أكبر من الإزاحة. أي أنه يشير جزئيًا إلى البيانات التي لم تتم كتابتها بعد إلى المخزن المؤقت للإخراج.

نسخ 10 بايت في الإزاحة 3:

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

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

في عملية الضغط ، لدينا جميع البيانات ، ويمكن العثور على مثل هذه المطابقة. لا تعد وظيفة memcpy مناسبة لنسخها: فهي لا تدعم الحالة عندما تتقاطع شظايا الذاكرة. بالمناسبة ، وظيفة memmove ليست مناسبة أيضًا ، لأن جزء الذاكرة من حيث الحصول على البيانات لم يتم تهيئته بالكامل. تحتاج إلى نسخ كما لو كنا نقوم بالنسخ بواسطة البايت.

  المرجع [0] = المطابقة [0] ؛
 المرجع [1] = المطابقة [1] ؛
 المرجع [2] = المطابقة [2] ؛
 المرجع [3] = المطابقة [3] ؛
 ...

إليك كيف تعمل:

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

وهذا هو ، يجب علينا إنشاء تسلسل التكرار. في تطبيق LZ4 الأصلي ، تمت كتابة التعليمات البرمجية غير المفهومة لهذا:

  const decigned dec32table [] = {0 ، 1 ، 2 ، 1 ، 4 ، 4 ، 4 ، 4} ؛
 const int dec64table [] = {0 ، 0 ، 0 ، -1 ، 0 ، 1 ، 2 ، 3} ؛

 const int dec64 = dec64table [إزاحة] ؛
 المرجع [0] = المطابقة [0] ؛
 المرجع [1] = المطابقة [1] ؛
 المرجع [2] = المطابقة [2] ؛
 المرجع [3] = المطابقة [3] ؛
 تطابق + = dec32table [إزاحة] ؛
 memcpy (op + 4، match، 4)؛
 تطابق - = dec64 ؛

ننسخ أول بايت 4 بايت ، ننتقل بعدد سحري ، ننسخ الـ 4 بايت التالية ككل ، نحول المؤشر لتتطابق مع رقم سحري آخر. لقد نسي مؤلف الكود ( Jan Collet ) ، لسبب مثير للسخرية ، ترك تعليق على معنى هذا. بالإضافة إلى ذلك ، أسماء متغير مربكة. يسمى كلاهما dec ... table ، لكننا نضيف أحدهما ونطرح الآخر. بالإضافة إلى ذلك ، واحد آخر غير موقعة ، والآخر هو كثافة العمليات. ومع ذلك ، تجدر الإشارة إلى أنه: مؤخرًا ، قام المؤلف بتحسين هذا المكان في الكود.

وإليك كيف يعمل في الواقع. نسخ أول بايت 4 بايت:

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

الآن يمكنك نسخ 4 بايت في وقت واحد:

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

, 8 :

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

, — . :

 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 equivalent result, but is better CPU friendly for unknown reason.
    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];
}

, , . , , — 16 .

« » , ( offset < 16 , offset < 8 ). () 16- :

 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];
}

? , SIMD-, 16 , ( 1 15). , , .

— pshufb ( packed shuffle bytes) SSSE3 ( S). 16- . . — «»: 0 15 — , . , 127 — .

:

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

pshufb %xmm1, %xmm0

xmm0: abcabcabcabcabca

— ! :

 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
}

_mm_shuffle_epi8 — intrinsic , pshufb .

, ? SSSE3 — , 2006 . AVX2 , 32 , 16- . packed shuffle bytes, vector permute bytes — , . AVX-512 VBMI , 64 , . ARM NEON — vtbl (vector table lookup), 8 .

, pshufb 64- MMX-, 8 . . , , 16 ( ).

Highload++ Siberia , 8 ( ) — !

if

, , 16 . ?

, . , , , . , .

, . , , , 65 536 . 65 536 . , , 65 551 . , , 96 128 — . , «» mmap ( madvice). - page faults. , .

?

, , :

16 8.
shuffle- offset < 16 .
if.

.

مثال 1:
Xeon E2650v2, ., AppVersion.
reference: 1.67 GB/sec.
16 bytes, shuffle: 2.94 GB/sec ( 76% ).

مثال 2:
Xeon E2650v2, ., ShowsSumPosition.
reference: 2.30 GB/sec.
16 bytes, shuffle: 1.91 GB/sec ( 20% ).

, . , . - , . , . — 16 . : , , .

, C++ : 8- 16- ; shuffle-.

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

, shuffle . , :

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

«» (c Xeon E5645), , . , , . , shuffle-, , 16- .

:

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

. thermal throttling power capping.

, , . , , . . , , . : ClickHouse , , . , ( — ?). .

, , . « » . , , , .

, . . - . — ClickHouse 64 . ( .)

, « », , . , , , - . . , , . .

, , . «» , . , . Thompson Sampling.

, , . — : , . . , . , C++. — , - , ; .

? , . . -, , . -, , , «» .

, , Thompson Sampling — ( , ). , , - , , . , .

, «» . , , «», . — . , , .

, , , , «»:

 /// For better convergence, we don't use proper estimate of stddev.
/// We want to eventually separate between two algorithms even in case
/// 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);
}

, — memory latencies.

, , — LZ4 .

, :
— reference (baseline): LZ4 ;
— variant 0: 8 , shuffle;
— variant 1: 8 , shuffle;
— variant 2: 16 , shuffle;
— variant 3: 16 , shuffle;
— «» , .

CPU

CPU, , . , CPU ?

ClickHouse , 256 100 ( 256 ). , CPU , . CPU:
— 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

— , R&D:
— AMD EPYC 7351 16-Core Processor — AMD.
— Cavium ThunderX2 — x86, AArch64. SIMD- . 224 56 .

13 , 256 6 (reference, 0, 1, 2, 3, adaptive), 10 , . 199 680 , .

, CPU . : LZ4 ( — ). , Cavium . ClickHouse, «» Xeon E5-2650 v2 , , ClickHouse 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 — (, ). best — , 0 3. adapt_boost — baseline. max_boost — baseline. adapt_over_max — .

, x86 12–20%. ARM 4%, , . , «» Intel.

النتائج

. , LZ4 12–20%, . . , .

, , «» , ZStandard level 1 LZ4: IO .

— , . , .

: . LZ4 , Lizard, Density LZSSE , . , LZ4 LZSSE ClickHouse.

LZ4 : . : , . . , inc- dec- . , 12–15% 32 , 16, . 32 — , .

, , page cache userspace ( mmap, O_DIRECT userspace page cache — ), - ( CityHash128 CRC32-C, HighwayHash, FARSH XXH3). , .

, master, . HighLoad++ Siberia, .

كيفية تسريع عملية تفريغ LZ4 في ClickHouse