خطاب الافتتاح
لقد قدمت هذا التقرير باللغة الإنجليزية في مؤتمر GopherCon روسيا 2019 في موسكو وباللغة الروسية في لقاء في نيجني نوفغورود. نحن نتحدث عن فهرس الصورة النقطية - وهو أقل شيوعًا من B-tree، ولكنه ليس أقل إثارة للاهتمام. مشاركة الكلمات في المؤتمر باللغة الإنجليزية والنصوص النصية باللغة الروسية.
سننظر في كيفية عمل فهرس الصورة النقطية، ومتى يكون أفضل، ومتى يكون أسوأ من الفهارس الأخرى، وفي أي الحالات يكون أسرع منها بشكل ملحوظ؛ دعونا نرى أي من أنظمة إدارة قواعد البيانات الشائعة لديها بالفعل فهارس للصور النقطية؛ دعونا نحاول أن نكتب ما لدينا في Go. و"للحلوى" سنستخدم المكتبات الجاهزة لإنشاء قاعدة البيانات المتخصصة فائقة السرعة الخاصة بنا.
آمل حقًا أن تكون أعمالي مفيدة ومثيرة للاهتمام بالنسبة لك. يذهب!
مقدمة
أهلاً بكم! إنها السادسة مساءً وكلنا متعبون للغاية. وقت رائع للحديث عن نظرية فهرس قاعدة البيانات المملة، أليس كذلك؟ لا تقلق، سيكون لدي سطرين من كود المصدر هنا وهناك. 🙂
وبغض النظر عن النكات، فإن التقرير مليء بالمعلومات، وليس لدينا الكثير من الوقت. اذا هيا بنا نبدأ.
اليوم سأتحدث عن ما يلي:
- ما هي الفهارس؟
- ما هو فهرس الصورة النقطية؟
- أين يتم استخدامه وأين لا يستخدم ولماذا؛
- تنفيذ بسيط في Go وقليل من الصراع مع المترجم؛
- تنفيذ أقل بساطة إلى حد ما، ولكنه أكثر إنتاجية في مجمع Go؛
- "مشاكل" فهارس الصور النقطية؛
- التنفيذ الحالي.
إذن ما هي الفهارس؟
الفهرس عبارة عن بنية بيانات منفصلة نقوم بصيانتها وتحديثها بالإضافة إلى البيانات الرئيسية. يتم استخدامه لتسريع البحث. بدون الفهارس، سيتطلب البحث المرور عبر البيانات بالكامل (عملية تسمى الفحص الكامل)، وهذه العملية لها تعقيد خوارزمي خطي. لكن قواعد البيانات تحتوي عادةً على كميات هائلة من البيانات ويكون التعقيد الخطي بطيئًا للغاية. ومن الناحية المثالية، سنحصل على قيمة لوغاريتمية أو ثابتة.
هذا موضوع معقد للغاية، ومليء بالتفاصيل الدقيقة والمقايضات، ولكن بعد النظر في عقود من تطوير قواعد البيانات والبحث، أنا على استعداد للقول أنه لا يوجد سوى عدد قليل من الأساليب المستخدمة على نطاق واسع لإنشاء فهارس قواعد البيانات.
النهج الأول هو تقليل مساحة البحث بشكل هرمي، وتقسيم مساحة البحث إلى أجزاء أصغر.
وعادة ما نقوم بذلك باستخدام أنواع مختلفة من الأشجار. على سبيل المثال، صندوق كبير من المواد في خزانتك يحتوي على صناديق أصغر من المواد مقسمة إلى مواضيع مختلفة. إذا كنت بحاجة إلى مواد، فمن المحتمل أن تبحث عنها في مربع مكتوب عليه "المواد" بدلاً من المربع المكتوب عليه "ملفات تعريف الارتباط"، أليس كذلك؟
الطريقة الثانية هي تحديد العنصر أو مجموعة العناصر المطلوبة على الفور. نحن نفعل ذلك في خرائط التجزئة أو الفهارس العكسية. استخدام خرائط التجزئة يشبه إلى حد كبير المثال السابق، ولكن بدلاً من صندوق من الصناديق، لديك مجموعة من الصناديق الصغيرة من العناصر النهائية في خزانتك.
النهج الثالث هو القضاء على الحاجة إلى البحث. نقوم بذلك باستخدام مرشحات بلوم أو مرشحات الوقواق. الأولى تعطي إجابة على الفور، مما يوفر عليك من الاضطرار إلى البحث.
النهج الأخير هو الاستفادة الكاملة من كل القوة التي توفرها لنا الأجهزة الحديثة. وهذا هو بالضبط ما نفعله في فهارس الصور النقطية. نعم، عند استخدامها، نحتاج أحيانًا إلى مراجعة الفهرس بأكمله، لكننا نفعل ذلك بكفاءة فائقة.
كما قلت، موضوع فهارس قاعدة البيانات واسع ومليء بالتسويات. وهذا يعني أنه يمكننا في بعض الأحيان استخدام عدة طرق في نفس الوقت: إذا كنا بحاجة إلى تسريع البحث بشكل أكبر، أو إذا كنا بحاجة إلى تغطية جميع أنواع البحث الممكنة.
اليوم سأتحدث عن النهج الأقل شهرة لهذه - فهارس الصور النقطية.
من أنا لأتحدث في هذا الموضوع؟
أنا أعمل كقائد فريق في Badoo (ربما تكون أكثر دراية بمنتجنا الآخر، Bumble). لدينا بالفعل أكثر من 400 مليون مستخدم حول العالم والعديد من الميزات التي تحدد أفضل تطابق لهم. نقوم بذلك باستخدام خدمات مخصصة، بما في ذلك فهارس الصور النقطية.
إذن ما هو فهرس الصورة النقطية؟
تستخدم فهارس الصور النقطية، كما يوحي الاسم، الصور النقطية أو مجموعات البت لتنفيذ فهرس البحث. من منظور علوي، يتكون هذا الفهرس من واحدة أو أكثر من الصور النقطية التي تمثل أي كيانات (مثل الأشخاص) وخصائصها أو معلماتها (العمر، ولون العين، وما إلى ذلك)، وخوارزمية تستخدم عمليات البت (AND، OR، NOT ) للإجابة على استعلام البحث.
لقد قيل لنا أن فهارس الصور النقطية هي الأنسب وذات الأداء العالي للحالات التي توجد فيها عمليات بحث تجمع بين الاستعلامات عبر العديد من الأعمدة ذات العلاقة الأساسية المنخفضة (فكر في "لون العين" أو "الحالة الاجتماعية" مقابل شيء مثل "المسافة من وسط المدينة"). لكنني سأوضح لاحقًا أنها تعمل بشكل جيد مع الأعمدة ذات العلاقة الأساسية العالية أيضًا.
دعونا نلقي نظرة على أبسط مثال لفهرس الصورة النقطية.
تخيل أن لدينا قائمة بمطاعم موسكو ذات الخصائص الثنائية مثل هذه:
- بالقرب من المترو
- يوجد موقف خاص للسيارات
- هناك شرفة (تحتوي على تراس)؛
- يمكنك حجز طاولة (يقبل الحجوزات)؛
- مناسب للنباتيين (صديق للنباتيين)؛
- باهظة الثمن (باهظة الثمن).
لنمنح كل مطعم رقمًا تسلسليًا يبدأ من 0 ونخصص الذاكرة لستة صور نقطية (واحدة لكل خاصية). سنقوم بعد ذلك بملء هذه الصور النقطية اعتمادًا على ما إذا كان المطعم يمتلك هذه الخاصية أم لا. إذا كان المطعم 6 به شرفة أرضية، فسيتم تعيين البتة رقم 4 في الصورة النقطية "يحتوي على شرفة أرضية" على 4 (إذا لم يكن هناك شرفة أرضية، فسيتم تعيينها على 1).
الآن لدينا أبسط فهرس نقطي ممكن، ويمكننا استخدامه للإجابة على استعلامات مثل:
- "أرني المطاعم الصديقة للنباتيين"؛
- "أرني مطاعم رخيصة بها شرفة حيث يمكنك حجز طاولة."
كيف؟ دعونا نلقي نظرة. الطلب الأول بسيط جداً كل ما يتعين علينا فعله هو أخذ الصورة النقطية "الصديقة للنباتيين" وتحويلها إلى قائمة بالمطاعم التي تم الكشف عن أجزاءها.
الطلب الثاني أكثر تعقيدًا بعض الشيء. نحتاج إلى استخدام الصورة النقطية NOT على الصورة النقطية "باهظة الثمن" للحصول على قائمة بالمطاعم الرخيصة، ثم نستخدمها مع الصورة النقطية "هل يمكنني حجز طاولة" والنتيجة مع الصورة النقطية "توجد شرفة أرضية". ستحتوي الصورة النقطية الناتجة على قائمة بالمؤسسات التي تستوفي جميع معاييرنا. في هذا المثال، هذا هو مطعم Yunost فقط.
هناك الكثير من النظريات المتضمنة، لكن لا تقلق، سنرى الكود قريبًا جدًا.
أين يتم استخدام فهارس الصور النقطية؟
إذا قمت بفهرسة الصور النقطية من Google، فستكون 90% من الإجابات مرتبطة بقاعدة بيانات Oracle بطريقة أو بأخرى. ولكن ربما تدعم أنظمة إدارة قواعد البيانات الأخرى أيضًا مثل هذا الشيء الرائع، أليس كذلك؟ ليس حقيقيًا.
دعونا نستعرض قائمة المشتبه بهم الرئيسيين.
لا يدعم MySQL فهارس الصور النقطية حتى الآن، ولكن هناك اقتراح يقترح إضافة هذا الخيار ().
لا يدعم PostgreSQL فهارس الصور النقطية، ولكنه يستخدم صورًا نقطية بسيطة وعمليات بت لدمج نتائج البحث عبر عدة فهارس أخرى.
يحتوي Tarantool على فهارس مجموعة البتات ويدعم عمليات البحث البسيطة عليها.
لدى Redis حقول بت بسيطة) دون القدرة على البحث عنها.
لا يدعم MongoDB بعد فهارس الصور النقطية، ولكن هناك أيضًا اقتراح يقترح إضافة هذا الخيار
يستخدم Elasticsearch الصور النقطية داخليًا).
- لكن جارًا جديدًا ظهر في منزلنا: بيلوسا. هذه قاعدة بيانات غير علائقية جديدة مكتوبة بلغة Go. فهو يحتوي فقط على فهارس الصور النقطية ويبني عليها كل شيء. سنتحدث عن ذلك بعد قليل.
التنفيذ في الذهاب
ولكن لماذا نادرًا ما يتم استخدام فهارس الصور النقطية؟ قبل الإجابة على هذا السؤال، أود أن أوضح لك كيفية تنفيذ فهرس نقطي بسيط جدًا في Go.
الصور النقطية هي في الأساس مجرد أجزاء من البيانات. في Go، دعونا نستخدم شرائح البايت لهذا الغرض.
لدينا صورة نقطية واحدة لخاصية مطعم واحد، وكل جزء في الصورة النقطية يشير إلى ما إذا كان مطعم معين لديه هذه الخاصية أم لا.
سنحتاج إلى وظيفتين مساعدتين. سيتم استخدام أحدهما لملء الصور النقطية ببيانات عشوائية. عشوائي، ولكن مع وجود احتمال معين أن المطعم لديه كل خاصية. على سبيل المثال، أعتقد أن هناك عدد قليل جدًا من المطاعم في موسكو حيث لا يمكنك حجز طاولة، ويبدو لي أن حوالي 20٪ من المؤسسات مناسبة للنباتيين.
ستقوم الوظيفة الثانية بتحويل الصورة النقطية إلى قائمة المطاعم.
للإجابة على الاستعلام "أرني المطاعم الرخيصة التي تحتوي على فناء ويمكنها إجراء الحجوزات"، نحتاج إلى عمليتين بت: NOT وAND.
يمكننا تبسيط الكود الخاص بنا قليلًا باستخدام عامل التشغيل NOT الأكثر تعقيدًا.
لدينا وظائف لكل من هذه العمليات. يمر كل منهما عبر الشرائح، ويأخذ العناصر المقابلة من كل منها، ويجمعها بعملية صغيرة ويضع النتيجة في الشريحة الناتجة.
والآن يمكننا استخدام الصور النقطية والوظائف للإجابة على استعلام البحث.
الأداء ليس مرتفعًا، على الرغم من أن الوظائف بسيطة جدًا وقد وفرنا الكثير من المال من خلال عدم إرجاع شريحة جديدة ناتجة في كل مرة يتم فيها استدعاء الوظيفة.
بعد إجراء القليل من التوصيف باستخدام pprof، لاحظت أن مترجم Go يفتقد تحسينًا واحدًا بسيطًا جدًا ولكنه مهم جدًا: تضمين الوظيفة.
الحقيقة هي أن مترجم Go يخاف بشدة من الحلقات التي تمر عبر الشرائح، ويرفض بشكل قاطع تضمين الوظائف التي تحتوي على مثل هذه الحلقات.
لكنني لست خائفًا ويمكنني خداع المترجم باستخدام goto بدلاً من حلقة، كما كان الحال في الأيام الخوالي.
وكما ترون، الآن سوف يقوم المترجم بكل سرور بتضمين وظيفتنا! ونتيجة لذلك، تمكنا من توفير حوالي 2 ميكروثانية. ليس سيئًا!
من السهل رؤية عنق الزجاجة الثاني إذا نظرت عن كثب إلى مخرجات التجميع. أضاف المترجم فحصًا لحدود الشريحة داخل الحلقة الأكثر سخونة لدينا. الحقيقة هي أن Go هي لغة آمنة، ويخشى المترجم أن تكون وسيطاتي الثلاث (ثلاث شرائح) ذات أحجام مختلفة. بعد كل شيء، سيكون هناك احتمال نظري لحدوث ما يسمى بتجاوز سعة المخزن المؤقت.
دعونا نطمئن المترجم من خلال إظهار أن جميع الشرائح بنفس الحجم. يمكننا القيام بذلك عن طريق إضافة علامة اختيار بسيطة في بداية وظيفتنا.
عند رؤية هذا، يتخطى المترجم الفحص بسعادة، وينتهي بنا الأمر بتوفير 500 نانو ثانية أخرى.
جزارات كبيرة
حسنًا، لقد تمكنا من استخلاص بعض الأداء من تطبيقنا البسيط، ولكن هذه النتيجة في الواقع أسوأ بكثير مما هو ممكن مع الأجهزة الحالية.
كل ما نقوم به هو عمليات البت الأساسية، وتقوم معالجاتنا بتنفيذها بكفاءة عالية. لكن لسوء الحظ، نقوم "بتغذية" معالجنا بقطع صغيرة جدًا من العمل. تقوم وظائفنا بتنفيذ العمليات على أساس بايت بايت. يمكننا بسهولة تعديل الكود الخاص بنا للعمل مع قطع 8 بايت باستخدام شرائح UInt64.
كما ترون، أدى هذا التغيير البسيط إلى تسريع برنامجنا ثماني مرات عن طريق زيادة حجم الدفعة ثماني مرات. يمكن القول أن الربح خطي.
التنفيذ في المجمع
ولكن هذا ليس نهاية المطاف. يمكن لمعالجاتنا العمل مع أجزاء بحجم 16 و32 وحتى 64 بايت. تسمى هذه العمليات "الواسعة" بتعليمات مفردة متعددة البيانات (SIMD؛ تعليمة واحدة، بيانات متعددة)، وعملية تحويل التعليمات البرمجية بحيث تستخدم مثل هذه العمليات تسمى التوجيه.
لسوء الحظ، مترجم Go ليس ممتازًا في التحويل. حاليًا، الطريقة الوحيدة لتوجيه كود Go هي أخذ هذه العمليات وتنفيذها يدويًا باستخدام مجمع Go.
الذهاب المجمع هو وحش غريب. من المحتمل أنك تعلم أن لغة التجميع هي شيء مرتبط بشكل كبير ببنية الكمبيوتر الذي تكتب له، ولكن هذا ليس هو الحال في Go. يشبه مجمع Go لغة IRL (لغة التمثيل الوسيطة) أو اللغة الوسيطة: فهو عمليًا مستقل عن النظام الأساسي. قدم روب بايك أداءً ممتازًا حول هذا الموضوع منذ عدة سنوات في GopherCon في دنفر.
بالإضافة إلى ذلك، يستخدم Go تنسيقًا غير عادي للخطة 9، والذي يختلف عن تنسيقات AT&T وIntel المقبولة عمومًا.
من الآمن أن نقول إن كتابة مجمع Go يدويًا ليس هو الأكثر متعة.
لكن لحسن الحظ، هناك بالفعل أداتان عاليتا المستوى تساعداننا في كتابة مُجمّع Go: PeachPy وavo. تقوم كلا الأداتين بإنشاء مجمع Go من تعليمات برمجية عالية المستوى مكتوبة بلغة Python وGo، على التوالي.
تعمل هذه الأدوات المساعدة على تبسيط أشياء مثل تخصيص التسجيل وحلقات الكتابة وتبسيط عملية الدخول إلى عالم برمجة التجميع في Go بشكل عام.
سنستخدم avo، لذا ستكون برامجنا عبارة عن برامج Go عادية تقريبًا.
هذا ما يبدو عليه أبسط مثال لبرنامج تجنب. لدينا وظيفة main()، والتي تحدد في حد ذاتها وظيفة Add()، ومعنى ذلك هو إضافة رقمين. توجد وظائف مساعدة هنا للحصول على المعلمات بالاسم والحصول على أحد سجلات المعالج المجانية والمناسبة. كل عملية للمعالج لها وظيفة مقابلة في تجنب، كما هو موضح في ADDQ. وأخيرًا، نرى وظيفة مساعدة لتخزين القيمة الناتجة.
من خلال استدعاء go generator، سنقوم بتنفيذ البرنامج على avo ونتيجة لذلك، سيتم إنشاء ملفين:
- add.s مع الكود الناتج في مجمع Go؛
- stub.go مع رؤوس الوظائف لربط العالمين: Go وassembler.
الآن بعد أن رأينا ما يفعله تجنب وكيف، دعونا نلقي نظرة على وظائفنا. لقد قمت بتنفيذ كلا الإصدارين العددي والمتجه (SIMD) للوظائف.
دعونا نلقي نظرة على الإصدارات العددية أولا.
كما في المثال السابق، نطلب سجلًا مجانيًا وصالحًا للأغراض العامة، ولا نحتاج إلى حساب الإزاحات والأحجام للوسائط. تجنب يفعل كل هذا بالنسبة لنا.
لقد اعتدنا استخدام التصنيفات وgoto (أو الانتقالات) لتحسين الأداء وخداع مترجم Go، لكننا الآن نقوم بذلك من البداية. النقطة المهمة هي أن الدورات هي مفهوم عالي المستوى. في المجمع، لدينا فقط التسميات والقفزات.
يجب أن يكون الكود المتبقي مألوفًا ومفهومًا بالفعل. نحن نحاكي حلقة تحتوي على تسميات وقفزات، ونأخذ جزءًا صغيرًا من البيانات من الشريحتين، وندمجهما بعملية صغيرة (وليس في هذه الحالة) ثم نضع النتيجة في الشريحة الناتجة. الجميع.
هذا ما يبدو عليه كود المجمع النهائي. لم يكن علينا حساب الإزاحات والأحجام (المظللة باللون الأخضر) أو تتبع السجلات المستخدمة (المظللة باللون الأحمر).
إذا قارنا أداء تنفيذ لغة التجميع بأداء أفضل تطبيق في Go، فسنرى أن الأمر نفسه. وهذا هو المتوقع. بعد كل شيء، لم نفعل أي شيء خاص - لقد قمنا فقط بإعادة إنتاج ما سيفعله مترجم Go.
لسوء الحظ، لا يمكننا إجبار المترجم على تضمين وظائفنا المكتوبة بلغة التجميع. لا يحتوي برنامج التحويل البرمجي Go حاليًا على مثل هذه الميزة، على الرغم من وجود طلب لإضافتها لبعض الوقت.
ولهذا السبب من المستحيل الحصول على أي فائدة من الوظائف الصغيرة في لغة التجميع. نحتاج إما إلى كتابة وظائف كبيرة، أو استخدام حزمة الرياضيات/البتات الجديدة، أو تجاوز لغة المجمع.
دعونا الآن نلقي نظرة على الإصدارات المتجهة لوظائفنا.
في هذا المثال، قررت استخدام AVX2، لذلك سوف نستخدم العمليات التي تعمل على قطع 32 بايت. هيكل الكود مشابه جدًا للإصدار العددي: تحميل المعلمات، وطلب تسجيل مشترك مجاني، وما إلى ذلك.
أحد الابتكارات هو أن عمليات المتجهات الأوسع تستخدم سجلات واسعة خاصة. في حالة القطع ذات 32 بايت، تكون هذه تسجيلات مسبوقة بـ Y. ولهذا السبب ترى الدالة YMM() في الكود. إذا كنت أستخدم AVX-512 مع أجزاء 64 بت، فستكون البادئة Z.
الابتكار الثاني هو أنني قررت استخدام تحسين يسمى Loop Unrolling، وهو ما يعني إجراء ثماني عمليات حلقات يدويًا قبل الانتقال إلى بداية الحلقة. يؤدي هذا التحسين إلى تقليل عدد الفروع في الكود، ويقتصر على عدد التسجيلات المجانية المتاحة.
حسنًا، ماذا عن الأداء؟ هي جميلة! لقد حققنا سرعة تبلغ حوالي سبع مرات مقارنة بأفضل حل Go. مثير للإعجاب، أليس كذلك؟
ولكن حتى هذا التنفيذ يمكن تسريعه باستخدام AVX-512 أو الجلب المسبق أو JIT (المترجم في الوقت المناسب) لجدولة الاستعلام. لكن هذا بالتأكيد موضوع لتقرير منفصل.
مشاكل مع فهارس الصورة النقطية
الآن بعد أن نظرنا بالفعل إلى تطبيق بسيط لفهرس الصورة النقطية في Go وتطبيق أكثر إنتاجية في لغة التجميع، فلنتحدث أخيرًا عن سبب ندرة استخدام فهارس الصور النقطية.
تشير الأوراق البحثية القديمة إلى ثلاث مشكلات تتعلق بفهرسات الصور النقطية، لكن الأوراق البحثية الأحدث وأنا أزعم أنها لم تعد ذات صلة. ولن نتعمق في كل واحدة من هذه المشاكل، بل سننظر إليها بشكل سطحي.
مشكلة الكاردينالية العالية
لذلك، قيل لنا أن فهارس الصور النقطية مناسبة فقط للحقول ذات العلاقة الأساسية المنخفضة، أي تلك التي تحتوي على قيم قليلة (على سبيل المثال، الجنس أو لون العين)، والسبب هو أن التمثيل المعتاد لمثل هذه الحقول (واحد بت لكل قيمة) في حالة وجود عدد كبير من العناصر، فإنها ستشغل مساحة كبيرة جدًا، علاوة على ذلك، سيتم ملء فهارس الصور النقطية هذه بشكل سيئ (نادرًا).
في بعض الأحيان قد نستخدم تمثيلاً مختلفًا، مثل التمثيل القياسي الذي نستخدمه لتمثيل الأرقام. لكن ظهور خوارزميات الضغط هو الذي غير كل شيء. على مدى العقود الماضية، توصل العلماء والباحثون إلى عدد كبير من خوارزميات ضغط الصور النقطية. ميزتها الرئيسية هي أنه ليست هناك حاجة لفك ضغط الصور النقطية لإجراء عمليات البت - يمكننا إجراء عمليات البت مباشرة على الصور النقطية المضغوطة.
في الآونة الأخيرة، بدأت الأساليب المختلطة في الظهور، مثل الصور النقطية الهادرة. إنهم يستخدمون في الوقت نفسه ثلاثة تمثيلات مختلفة للصور النقطية - الصور النقطية نفسها والمصفوفات وما يسمى بتشغيل البتات - ويوازنون بينها لتحقيق أقصى قدر من الأداء وتقليل استهلاك الذاكرة.
يمكنك العثور على صور نقطية صاخبة في التطبيقات الأكثر شيوعًا. يوجد بالفعل عدد كبير من التطبيقات لمجموعة واسعة من لغات البرمجة، بما في ذلك أكثر من ثلاثة تطبيقات لـ Go.
هناك طريقة أخرى يمكن أن تساعدنا في التعامل مع العناصر الأساسية العالية تسمى binning. تخيل أن لديك حقلًا يمثل طول الشخص. الارتفاع هو رقم النقطة العائمة، لكننا نحن البشر لا نفكر في الأمر بهذه الطريقة. بالنسبة لنا لا يوجد فرق بين الطول 185,2 سم و 185,3 سم.
اتضح أنه يمكننا تجميع القيم المتشابهة في مجموعات في حدود 1 سم.
وإذا علمنا أيضًا أن عددًا قليلًا جدًا من الأشخاص أقصر من 50 سم وأطول من 250 سم، فيمكننا بشكل أساسي تحويل حقل ذو قيمة أساسية لا نهائية إلى حقل ذو قيمة أساسية تبلغ حوالي 200 قيمة.
بالطبع، إذا لزم الأمر، يمكننا إجراء تصفية إضافية بعد ذلك.
مشكلة عرض النطاق الترددي العالي
المشكلة التالية في فهارس الصور النقطية هي أن تحديثها قد يكون مكلفًا للغاية.
يجب أن تكون قواعد البيانات قادرة على تحديث البيانات بينما تبحث مئات الاستعلامات الأخرى في البيانات. نحتاج إلى أقفال لتجنب مشاكل الوصول المتزامن للبيانات أو مشاكل المشاركة الأخرى. وحيثما يوجد قفل واحد كبير، تكون هناك مشكلة - تنافس القفل، عندما يصبح هذا القفل عنق الزجاجة.
يمكن حل هذه المشكلة أو التحايل عليها باستخدام التجزئة أو استخدام الفهارس ذات الإصدارات.
المشاركة هي شيء بسيط ومعروف. يمكنك تقسيم فهرس الصورة النقطية كما تفعل مع أي بيانات أخرى. بدلاً من قفل واحد كبير، سوف تحصل على مجموعة من الأقفال الصغيرة وبالتالي تتخلص من تنافس القفل.
الطريقة الثانية لحل المشكلة هي استخدام الفهارس ذات الإصدارات. يمكنك الحصول على نسخة واحدة من الفهرس الذي تستخدمه للبحث أو القراءة، ونسخة أخرى تستخدمها للكتابة أو التحديث. ومرة واحدة في فترة زمنية معينة (على سبيل المثال، مرة كل 100 مللي ثانية أو 500 مللي ثانية) تقوم بتكرارها وتبديلها. بالطبع، لا ينطبق هذا الأسلوب إلا في الحالات التي يستطيع فيها تطبيقك التعامل مع فهرس بحث متأخر قليلاً.
يمكن استخدام هذين الأسلوبين في وقت واحد: يمكن أن يكون لديك فهرس ذو إصدار مجزأ.
استعلامات أكثر تعقيدًا
المشكلة الأخيرة في فهارس الصور النقطية هي أنه قيل لنا إنها ليست مناسبة تمامًا لأنواع الاستعلامات الأكثر تعقيدًا، مثل الاستعلامات الممتدة.
في الواقع، إذا فكرت في الأمر، فإن عمليات البت مثل AND وOR وما إلى ذلك ليست مناسبة جدًا للاستعلامات مثل "أرني الفنادق التي تتراوح أسعار الغرف فيها بين 200 و300 دولار في الليلة".
الحل الساذج وغير الحكيم للغاية هو أخذ النتائج لكل قيمة بالدولار ودمجها مع عملية OR ذات معدل البت.
الحل الأفضل قليلاً هو استخدام التجميع. على سبيل المثال، في مجموعات من 50 دولارًا. وهذا من شأنه أن يسرع عمليتنا بمقدار 50 مرة.
ولكن يمكن أيضًا حل المشكلة بسهولة باستخدام طريقة عرض تم إنشاؤها خصيصًا لهذا النوع من الطلبات. يطلق عليها في الأبحاث العلمية اسم الصور النقطية المشفرة بالنطاق.
في هذا التمثيل، لا نقوم فقط بتعيين بت واحد لبعض القيمة (على سبيل المثال، 200)، ولكننا نحدد هذه القيمة وكل شيء أعلى. 200 وما فوق. نفس الشيء بالنسبة لـ 300: 300 وما فوق. وما إلى ذلك وهلم جرا.
باستخدام هذا التمثيل، يمكننا الإجابة على هذا النوع من استعلامات البحث عن طريق اجتياز الفهرس مرتين فقط. أولاً، سنحصل على قائمة بالفنادق التي تكون تكلفة الغرفة فيها أقل أو 300 دولار، ثم نحذف منها الفنادق التي تكون تكلفة الغرفة فيها أقل أو 199 دولارًا. مستعد.
سوف تتفاجأ، ولكن حتى عمليات البحث الجيولوجي ممكنة باستخدام فهارس الصور النقطية. الحيلة هي استخدام تمثيل هندسي يحيط بالإحداثيات الخاصة بك بشكل هندسي. على سبيل المثال، S2 من جوجل. ويجب أن يكون من الممكن تمثيل الشكل على شكل ثلاثة خطوط متقاطعة أو أكثر يمكن ترقيمها. بهذه الطريقة يمكننا تحويل Geoquery لدينا إلى عدة استعلامات "على طول الفجوة" (على طول هذه الخطوط المرقمة).
حلول جاهزة
أتمنى أن أكون قد أثارت اهتمامك قليلاً وأن يكون لديك الآن أداة مفيدة أخرى في ترسانتك. إذا كنت بحاجة إلى القيام بشيء كهذا، فستعرف الطريقة التي يجب أن تنظر بها.
ومع ذلك، ليس لدى الجميع الوقت أو الصبر أو الموارد اللازمة لإنشاء فهارس الصور النقطية من البداية. خاصة تلك الأكثر تقدمًا، مثل SIMD، على سبيل المثال.
ولحسن الحظ، هناك العديد من الحلول الجاهزة لمساعدتك.
الصور النقطية طافوا
أولاً، هناك نفس مكتبة الصور النقطية الصاخبة التي تحدثت عنها بالفعل. فهو يحتوي على كافة الحاويات وعمليات البت الضرورية التي ستحتاجها لإنشاء فهرس نقطي كامل.
لسوء الحظ، في الوقت الحالي، لا يستخدم أي من تطبيقات Go SIMD، مما يعني أن تطبيقات Go أقل أداءً من تطبيقات C، على سبيل المثال.
مشعر
منتج آخر يمكن أن يساعدك هو Pilosa DBMS، والذي، في الواقع، يحتوي فقط على فهارس الصور النقطية. وهذا حل جديد نسبيا، ولكنه يكسب القلوب بسرعة كبيرة.
يستخدم Pilosa الصور النقطية الصاخبة داخليًا ويمنحك القدرة على استخدامها، ويبسط ويشرح كل الأشياء التي تحدثت عنها أعلاه: التجميع، والصور النقطية المشفرة بالنطاق، ومفهوم الحقل، وما إلى ذلك.
دعونا نلقي نظرة سريعة على مثال لاستخدام Pilosa للإجابة على سؤال مألوف لديك بالفعل.
المثال مشابه جدًا لما رأيته من قبل. نقوم بإنشاء عميل لخادم Pilosa، وإنشاء فهرس والحقول الضرورية، ثم ملء حقولنا ببيانات عشوائية ذات احتمالات، وأخيرًا، تنفيذ الاستعلام المألوف.
بعد ذلك، نستخدم NOT في الحقل "باهظ الثمن"، ثم نتقاطع النتيجة (أو "و" مع حقل "الشرفة" ومع حقل "الحجوزات". وأخيرا نحصل على النتيجة النهائية.
آمل حقًا أن يظهر هذا النوع الجديد من الفهرس أيضًا في المستقبل المنظور في أنظمة إدارة قواعد البيانات مثل MySQL وPostgreSQL - فهارس الصور النقطية.
اختتام
إذا لم تكن قد نمت بعد، شكرا لك. كان علي أن أتطرق بإيجاز إلى العديد من المواضيع بسبب ضيق الوقت، ولكن آمل أن تكون المحادثة مفيدة وربما محفزة.
من المفيد معرفة فهارس الصور النقطية، حتى لو لم تكن بحاجة إليها الآن. دعهم يكونوا أداة أخرى في صندوق الأدوات الخاص بك.
لقد ألقينا نظرة على حيل الأداء المختلفة لـ Go والأشياء التي لم يتعامل معها مترجم Go بشكل جيد حتى الآن. لكن هذا مفيد جدًا أن يعرفه كل مبرمج Go.
هذا كل ما أردت أن أخبرك به. شكرًا لك!
المصدر: www.habr.com