للتحليل في التحليل الروتيني الاستخدامات شركة ذات تردد عال جدا، وكيف كان لإعادة تحليل صعوبة كبيرة بسرعة في المشهد البيانات الكبيرة. في الآونة الأخيرة صالون أباتشي كيلين، Kyligence الكبير البيانات R & D المهندسين تاو تاو زائد عن سر الجميع من تحليل البيانات الكبيرة إلى الوزن التي تستخدم عادة الخوارزميات.

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

لدينا إمكانية الوصول إلى جدول البضائع، والبند USER_ID يكون عمودين في الجدول، ونحن نريد أن نسأل بضائع للأشعة فوق البنفسجية، وهو الأمر المعهود جدا لمشهد الثقيلة. يتم تخزين البيانات المتوفرة لدينا على منصات توزيع البيانات على كل عقدة في 1 و 2.

نحن نريد أن ننظر إلى مستوى تنفيذ قصة الجملة SQL المادية وراء ما سوف يحدث: وزعت أول الحوسبة إطار لبدء المهام والحصول على بيانات من كلا العقدتين، لأن المجموعة SQL حسب العمود البند، لذلك فمن الضروري من أجل هذا البند الرئيسي لمدة البيانات الخام في خلط الجدول. دعونا ننظر الاحتياجات من البيانات ما لخلط ورق اللعب: لأن مجموعة / الاختيار عن طريق هذا البند، وبالتالي فإن البند تتطلب خلط ورق اللعب. ومع ذلك، USER_ID نحتاج فقط واحدة من إحصائياتها، لا يسعنا إلا أن خلط القيمة الأصلية بالكامل USER_ID ذلك؟

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

خوارزمية بالضبط: نقطية

الأسلوب الأول هو تقديم خوارزمية إلغاء البيانات المكررة دقيقة، واستخدام الرئيسي مبدأ نقطية. نقطية Bitset المعروف أيضا، والذي يعرف أساسا مجموعة كبيرة بعض الشيء، كل عنصر منها يتوافق مع بت واحد من مجموعة. على سبيل المثال، مجموعة [2،3،5،8] نقطية المقابلة لمجموعة من [001101001]، ومجموعة من المؤشر 2 يتوافق مع مجموعة من موقف 2، 3 موقف يتوافق مع مؤشر و3، وينطبق الشيء نفسه فيما بعد، وبالتالي الحصول على مجموعة، فإننا ندعو نقطية. بديهية جدا، وعدد مجموعة 1 تعيين أصل. التتبع إلى مصدره، وهدفنا هو استخدام ذاكرة أقل لتمثيل مزيد من المعلومات، وفي أصغر وحدة المعلومات هو الكمبيوتر قليلا، واذا كنا نستطيع استخدام قليلا لتمثيل عنصر في المجموعة، مقارنة مع العناصر الأصلية، يمكنك حفظ الكثير من التخزين.

هذا هو الأكثر نقطية الأساسية، نقطية يمكننا أن نتصور وعاء، ونحن نعلم أن عدد صحيح هو 32 بت، إذا كان نقطية يمكن تخزين ما يصل إلى القيم Integer.MAX_VALUE، ثم نقطية يتطلب طول الحد الأدنى من 32. مساحة نقطية تحتلها بطول 32 بت 512 M (2 ^ 32/8/1024/1024)، أن هناك سؤالا واضحا نقطية جدا: إذا كان نقطية واحدة فقط هذا العنصر أو العناصر لديها 4000000000، انها تحتاج الى احتلال مساحة 512 M. مرة أخرى إلى المشهد اسألوا الأشعة فوق البنفسجية، وليس كل منتج سيكون لها الكثير من الوصول إلى بعض نماذج الانفجار قد يكون الوصول إلى مئات الملايين، ولكن بعض السلع الأكثر شعبية قد يكون العديد من المستخدمين لتصفح، إذا كنت تستخدم هذه نقطية، أنها تحتل مساحة نفسه كبير، وهو أمر غير مقبول بشكل واضح.

نسخة مطورة من نقطية: الهدر نقطية

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

أولا أولا، عندما الهدر نقطية هو الافتراضي التهيئة للحاويات، ودعا صفيف الحاويات. مجموعة الحاويات المناسبة لتخزين البيانات متفرق، داخلي بنية بيانات مجموعة الحاويات هو مجموعة قصيرة، ومجموعة غير منظم، من السهل العثور على. القدرة الأولية للمجموعة هي 4، والحد الأقصى للصفيف 4096. يتجاوز الحد الأقصى لعدد 4096، سيتم تحويلها إلى حاوية نقطية. لتوضيح هنا البيانات في عملية صفيف الحاوية: 0xFFFF0000 اثنين من الأرقام والاحتياجات التي سيتم تحديدها 0xFFFF0001 نقطية، 16 بت الأولى منها هي FFFF، لذلك هم نفس المفتاح، والتي يتم تخزينها في 16 بت حاوية في نفس و 16 بت هي 0 و 1 منه المخزنة على التوالي في مجموعة في مجموعة حاويات 0 و 1 يمكن أن يكون، بالمقارنة مع الحاجة لاحتلال نقطية 512M الأصلي من الذاكرة لتخزين هذين الرقمين، مثل التخزين الفعلي يستغرق سوى 2 + 4 = 6 بايت (مفتاح تمثل 2 بايت، وهما ما يمثل قيمة 4 بايت، دون النظر إلى قدرة الأولية للمجموعة).

حاوية الثانية هي صورة نقطية الحاويات، والمبدأ هو أن أقول فوق نقطية. ومن بنية بيانات من مجموعة طويلة، مجموعة 1024 من السعة الثابتة، وصفيف مختلف الحاويات أعلاه، صفيف التوسع الحاويات هو مجموعة ديناميكية. ويستمد هذه القيمة هنا 1024: حاجة الحاويات لأن كل ما تبقى العملية بعد بيانات 16 بت، والحاجة إلى تخزين صورة نقطية 8192 بايت (2 ^ 16/8)، وقيمة طويلة تمثل 8 بايت، فإنه يحتاج ما مجموعه 1024 (8192/8) قيمة طويلة. لذلك الثابتة وعاء نقطية تأخذ الذاكرة 8 KB (1024 * 8 بايت). عندما صفيف الحاويات 4096 عندما العناصر، يحدث أيضا أن تحتل 8 ك المحتلة (4096 * 2Bytes) مساحة نقطية تساوي بالضبط إلى 8 كيلو بايت. وعندما يكون عدد العناصر التي تخزن أكثر من 4096 مرة، صفيف حجم الحاويات تزال محتلة النمو الخطي، ولكن مساحة الذاكرة نقطية الحاويات ولا ينمو، وما زالت محتلة من قبل 8 K، وذلك عندما يتجاوز صفيف الحاويات أقصى قدرة (DEFAULT_MAX_SIZE ) يتم تحويلها إلى صورة نقطية الحاويات.

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

ويسمى حاوية مشاركة تشغيل الحاويات، هذه الحاويات لتخزين بيانات متسلسلة. على سبيل المثال، من 1 إلى 100، وهو عدد 100، وهذا النوع من البيانات وتسمى البيانات المستمرة. يشير إلى جانب تشغيل تشغيل طول ترميز (RLE)، فإنه لديه جيدة ضغط البيانات المستمر. المبدأ لعدد التوالي، وسجل فقط عدد الرقمية الأولي واللاحق. على سبيل المثال: ل، يتم تسجيل نحو 11، 4، 21، 1. من الواضح، ترتبط ارتباطا وثيقا الاحتلال تخزين الحاويات وتوزيع البيانات. ويتمثل الوضع الأفضل إذا تم توزيع البيانات بشكل مستمر، حتى لتخزين 65،536 العناصر، وسوف يستغرق سوى لجنتين قصيرة. أسوأ الحالات هي عندما تكون جميع البيانات ليست المرة المستمر، سوف يستغرق 128 كيلو بايت من الذاكرة.

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

في تطبيق كيلين

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

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

1) عندما تكون قيمة عمود إلى عمود آخر يحتوي تماما، في حين أن القوائم القاموس العالمية الأخرى، القاموس العالمي يمكن إعادة استخدامها في عمود آخر.

2) عندما لا يتطلب مؤشر الوزن الدقيق لعبور الزمن الجزء البلمرة، القاموس يمكن أن تستخدم بدلا من العمود الجزء (العمود يتطلب ترميز القاموس). في كيلين، الجزء يعادل مفهوم الوقت تشريح. عند تحليل القطاعات عبر لا يحدث، وهذا يمكن عمود الجزء القاموس يحل محل هذا القاموس العالمي.

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

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

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

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

HLL مبدأ خوارزمية الإدراك

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

نظريا هناك الوضع الذي كنت محظوظا جدا، وهي المرة الأولى هذه التجربة حتى رمي 20 مرة إيجابية، فإننا سوف تعتقد أنك جعلت هذه التجربة عدة مرات قبل أن تحصل على هذا السجل، وهذا سوف يؤدي إلى خطأ تقدير؛ وتحسين طريقة هي أن نسأل 10 طلاب للقيام بهذه التجربة، بحيث يمكنك مراقبة بيانات أكثر عينة، والحد من احتمال الحالة المذكورة أعلاه. هذه هي الفكرة الأساسية من خوارزمية HLL.

HLL خوارزمية تحقيق

وسيتم الحصول على HLL في جمع جميع عناصر التجزئة (قيمة التجزئة من تمثيل ثنائي، يمكن أن تفهم على أنها سلسلة من الإيجابية تسلسل عملة إرم نتيجة سلبية) وظيفة تجزئة للحصول على مجموعة من القيم التجزئة، ثم العثور على البعثرة قيمة المجموعة في المركز الأول من أحدث الحدوث. على سبيل المثال، مجموعة من ، والموقف من حدوث أول مجموعة من عناصر 1، على التوالي 2، 1، 3، هناك يمكن الحصول على قيمة أقصاها 3، وبالتالي فإن أول واحد في يظهر مجموعة أحدث موقف 3. لأن احتمال ظهور و02/01 كل موقف، حتى نتمكن من القيام الاستدلال بسيطة، وجمع ثمانية عناصر متداخلة غير.

يمكننا أن نرى هذه المجموعة الاستدلال احتساب القيمة الأساسية بسيط هو انحراف كبير، ثم كيفية الحد من التحيز ذلك؟ كما في المثال أعلاه حيث قلت نفسه، يتم تقليل الخطأ HLL عدة مرات اختبارها. تلك هي الطريقة التي تدار بها تجارب عدة مرات ذلك؟ يؤخذ المستخدمة هنا نقطة HLL حوض يعتقد، قمنا المذكورة أعلاه مفهوم الدقة، هذا HLL (10)، ممثل من 10 المقابلة لهذا العنصر بعد قيمة التجزئة من 10 ثنائي، المقابلة لتسجيل حساب دلو، فإن دلو يكون رقما قياسيا تمثل أول يتوافق مع قيمة التجزئة لأحدث موقف دلو 1 يظهر. كما هو مبين أعلاه، فإن قيمة تجزئة قيمة التجزئة 10 بت هو 0000001001، يتم تحويلها إلى عشري 9، العدد 9 يتوافق مع الحوض، وقيمة التجزئة لحالة التواجد الأول 1 هو أول 6 بت من العدد الأصلي 9 أعداد كبيرة الحوض، بحيث يتم تحديث رقم 9 في الحوض 6. يمكن أن ينظر إلى أكثر عدد من الحوض، وارتفاع دقة HLL الخوارزمية، HLL (10) 1024 (210) برميل، HLL (16) 65536 (216) برميل. وبالمثل، فإن أكبر عدد من الدلاء، واحتلت مساحة ستكون أكبر.

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

تقييم HLL

توزيع خطأ HLL من التوزيع الطبيعي والتعقيد المكاني لها: O (م log2log2N)، N كقاعدة، m هو عدد البراميل. التحقق من ذلك هنا للجميع للتعقيد المكاني اشتقاق، لدي 264 العناصر غير المتكررة (لونغ. MAX_VALUE)، كما أعرب عن رقم ثنائي هو 64، وهذا هو أول log2 الثقيلة، ثم أول 1 على أقصى تقدير ممكن ويبدو في أول 64. 64 يتطلب ستة بت (26 = 64) يمكن تخزينها، وهو log2 الثقيلة الثاني. إذا الدقة 10، سيكون هناك 1024 برميل، والأبعد حتى مضروبا في عدد من البراميل. الحاجة إلى اجتياز كاملة من العناصر مرة أخرى، لذلك حان الوقت التعقيد هو تعقيد الوقت الخطي.

في تطبيق كيلين

 كيلين تستخدم HLL مقياس بسيط جدا من خيار في COUNT تحرير صفحة متميزة، نوع الإرجاع غير الخيارات الأخرى المختار على وجه التحديد، ونختار احتياجات مختلفة وفقا لدقتها يمكن استخدامها لحسن الحظ.

ملخص

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

Q & A

Q1: مرحبا، لطرح الأسئلة حول وزن دقيق، وأنا اختار أن يذهب غير دقيق الثقيلة، وأحيانا نسبة الخطأ الأخير هو أعلى من القيمة الموضحة على الشاشة من بعض، وهذا هو السبب؟

A1 : أولا، HLL توزيع خطأ التوزيع الطبيعي، وهذا هو القول إن هذا الخطأ في 99 من الحالات، في حين HLL للقاعدة منخفضة نسبيا، سوف يكون من الخطأ عالية. إذا الأساسي الخاص بك منخفضة نسبيا، وأوصي لاستخدام الوزن المحدد.

Q2: اريد ان اتفرج على كيلين نقطية والتي في النهاية سوف في HBase القرص داخل تبدو وكأنها؟

A2 : وحدات البايت بالطبع، يتم تخزينها في HBase في. هذه المشكلة هي في الواقع في شكل صورة نقطية المتسلسلة، يوفر الهدر نقطية التسلسل وإلغاء التسلسل لتحقيق، يمكنك أيضا كتابة الخاص بك التسلسل إلغاء التسلسل تحقيق /.

Q3: الهدر نقطية في حاوية لتحديد يدويا أنفسنا؟

A3 : لا، سوف الهدر نقطية اختيار الحاويات تلقائيا.

نبذة عن الكاتب : نبذة عن الكاتب: تاو تاو الجمع (wechatID: 245915794)، Kyligence البحوث البيانات الكبيرة ومهندس التنمية، هو المسؤول عن Kyligence حلول التخزين والاستعلام قسم الحوسبة. ID جيثب: https://github.com/aaaaaaron.

وصف الرابط : HTTPS: //mp.weixin.qq.com/s/Ur5yYiKgbzB5gv9qpK08wQ