نمایه های بیت مپ در Go: جستجو با سرعت بسیار زیاد

سخنرانی افتتاحیه

من این گزارش را به زبان انگلیسی در کنفرانس GopherCon Russia 2019 در مسکو و به زبان روسی در جلسه ای در نیژنی نووگورود ارائه کردم. ما در مورد یک شاخص بیت مپ صحبت می کنیم - کمتر از B-tree رایج است، اما جالب نیست. اشتراک گذاری ضبط کردن سخنرانی در کنفرانس به زبان انگلیسی و متن رونوشت به زبان روسی.

ما به نحوه عملکرد یک نمایه بیت مپ، زمانی که بهتر است، زمانی که از سایر شاخص ها بدتر است و در چه مواردی به طور قابل توجهی سریعتر از آنها است، نگاه خواهیم کرد. بیایید ببینیم کدام DBMS های محبوب از قبل دارای نمایه های بیت مپ هستند. بیایید سعی کنیم خودمان را در Go بنویسیم. و "برای دسر" از کتابخانه های آماده برای ایجاد پایگاه داده تخصصی فوق سریع خود استفاده خواهیم کرد.

واقعا امیدوارم کارهایم برای شما مفید و جالب باشد. برو!

معرفی

http://bit.ly/bitmapindexes
https://github.com/mkevac/gopherconrussia2019

سلام به همه! ساعت شش عصر است و همه ما فوق العاده خسته ایم. زمان خوبی برای صحبت در مورد تئوری فهرست پایگاه داده خسته کننده است، درست است؟ نگران نباشید، من چند خط کد منبع اینجا و آنجا خواهم داشت. 🙂

همه شوخی‌ها به کنار، گزارش پر از اطلاعات است و زمان زیادی نداریم. پس بیایید شروع کنیم.

امروز در مورد موارد زیر صحبت خواهم کرد:

• شاخص ها چیست
• نمایه بیت مپ چیست.
• کجا استفاده می شود و کجا استفاده نمی شود و چرا.
• پیاده سازی ساده در Go و کمی مبارزه با کامپایلر.
• اجرای کمی ساده تر، اما بسیار پربارتر در اسمبلر Go.
• "مشکلات" نمایه های بیت مپ.
• پیاده سازی های موجود

پس شاخص ها چیست؟

ایندکس یک ساختار داده جداگانه است که ما علاوه بر داده های اصلی آن را نگهداری و به روز می کنیم. برای سرعت بخشیدن به جستجو استفاده می شود. بدون فهرست، جستجو مستلزم مرور کامل داده ها است (فرآیندی به نام اسکن کامل)، و این فرآیند دارای پیچیدگی الگوریتمی خطی است. اما پایگاه داده ها معمولاً حاوی مقادیر زیادی داده هستند و پیچیدگی خطی بسیار کند است. در حالت ایده آل، یک لگاریتمی یا ثابت دریافت می کنیم.

این یک موضوع بسیار پیچیده است، پر از ظرافت‌ها و معاوضه‌ها، اما پس از نگاهی به دهه‌ها توسعه و تحقیق پایگاه داده، مایلم بگویم که تنها چند رویکرد پرکاربرد برای ایجاد نمایه‌های پایگاه داده وجود دارد.

اولین رویکرد کاهش سلسله مراتبی فضای جستجو، تقسیم فضای جستجو به بخش های کوچکتر است.

ما معمولا این کار را با استفاده از انواع درختان انجام می دهیم. یک مثال می تواند جعبه بزرگی از مواد در کمد شما باشد که حاوی جعبه های کوچکتری از مواد است که به موضوعات مختلف تقسیم شده اند. اگر به مواد نیاز دارید، احتمالاً به دنبال آنها در جعبه‌ای می‌گردید که روی آن «مواد» نوشته شده است تا «کوکی‌ها»، درست است؟

رویکرد دوم این است که بلافاصله عنصر یا گروهی از عناصر مورد نظر را انتخاب کنید. ما این کار را در نقشه های هش یا نمایه های معکوس انجام می دهیم. استفاده از نقشه های هش بسیار شبیه به مثال قبلی است، اما به جای جعبه جعبه، یک دسته جعبه کوچک از آیتم های نهایی را در کمد خود دارید.

رویکرد سوم حذف نیاز به جستجو است. ما این کار را با استفاده از فیلترهای بلوم یا فیلترهای فاخته انجام می دهیم. اولین ها فوراً پاسخ می دهند و شما را از جستجو کردن نجات می دهند.

آخرین رویکرد استفاده کامل از تمام قدرتی است که سخت افزار مدرن به ما می دهد. این دقیقاً همان کاری است که ما در نمایه های بیت مپ انجام می دهیم. بله، هنگام استفاده از آنها، گاهی اوقات نیاز داریم که کل ایندکس را مرور کنیم، اما این کار را بسیار کارآمد انجام می دهیم.

همانطور که گفتم، موضوع فهرست های پایگاه داده گسترده و پر از مصالحه است. این بدان معناست که گاهی اوقات می‌توانیم از چندین رویکرد به طور همزمان استفاده کنیم: اگر نیاز به سرعت بخشیدن به جستجوی بیشتر داریم، یا اگر نیاز داریم که همه انواع جستجوی ممکن را پوشش دهیم.

امروز من در مورد کمتر شناخته شده ترین رویکرد اینها صحبت خواهم کرد - نمایه های بیت مپ.

من کی هستم که در این موضوع صحبت کنم؟

من به عنوان سرپرست تیم در Badoo کار می کنم (شاید شما با محصول دیگر ما، Bumble بیشتر آشنا باشید). ما در حال حاضر بیش از 400 میلیون کاربر در سراسر جهان داریم و ویژگی‌های زیادی داریم که بهترین گزینه را برای آنها انتخاب می‌کنند. ما این کار را با استفاده از خدمات سفارشی، از جمله نمایه های بیت مپ انجام می دهیم.

پس شاخص بیت مپ چیست؟

نمایه‌های بیت مپ، همانطور که از نامشان پیداست، از بیت مپ یا بیت‌ست برای پیاده‌سازی فهرست جستجو استفاده می‌کنند. از دید پرنده، این شاخص شامل یک یا چند بیت مپ است که هر موجودیت (مانند افراد) و خصوصیات یا پارامترهای آنها (سن، رنگ چشم و غیره) را نشان می دهد و الگوریتمی با استفاده از عملیات بیت (AND، OR، NOT). ) برای پاسخ به پرسش جستجو.

به ما گفته شده است که نمایه‌های بیت مپ برای مواردی که جستجوهایی وجود دارد که پرس‌و‌جوها را در ستون‌های با کاردینالیتی کم ترکیب می‌کنند، مناسب‌تر و بسیار کارآمد هستند (به «رنگ چشم» یا «وضعیت تأهل» در مقابل چیزی مانند «فاصله از مرکز شهر» فکر کنید). اما بعداً نشان خواهم داد که آنها برای ستون‌های با کاردینالیته بالا نیز به خوبی کار می‌کنند.

بیایید ساده ترین مثال یک نمایه بیت مپ را بررسی کنیم.

تصور کنید که ما لیستی از رستوران‌های مسکو با ویژگی‌های باینری مانند زیر داریم:

• نزدیک مترو؛
• پارکینگ خصوصی وجود دارد.
• یک ایوان (دارای تراس) وجود دارد.
• می توانید یک میز رزرو کنید (رزرو می پذیرد)؛
• مناسب برای گیاهخواران (وگان دوستانه)؛
• گران (گران)

بیایید به هر رستوران یک شماره ترتیبی بدهیم که از 0 شروع می شود و حافظه را برای 6 بیت مپ (یکی برای هر مشخصه) اختصاص می دهیم. سپس بسته به اینکه رستوران این ویژگی را داشته باشد یا خیر، این بیت مپ ها را پر می کنیم. اگر رستوران 4 ایوان داشته باشد، بیت شماره 4 در بیت مپ "دارای ایوان" روی 1 تنظیم می شود (اگر ایوان وجود نداشته باشد، روی 0).

اکنون ساده‌ترین نمایه بیت مپ ممکن را داریم و می‌توانیم از آن برای پاسخ دادن به سؤالاتی مانند:

• "رستوران های گیاهخوار را به من نشان دهید"؛
• رستوران‌های ارزان‌قیمت با ایوان را به من نشان دهید تا بتوانید میز رزرو کنید.

چگونه؟ بیایید نگاهی بیندازیم. درخواست اول بسیار ساده است. تنها کاری که ما باید انجام دهیم این است که نقشه بیت «گیاه‌خواری دوستانه» را برداریم و آن را به فهرستی از رستوران‌هایی تبدیل کنیم که بیت‌های آن‌ها در معرض دید قرار گرفته‌اند.


درخواست دوم کمی پیچیده تر است. ما باید از بیت مپ NOT در بیت مپ "گران قیمت" استفاده کنیم تا لیستی از رستوران های ارزان قیمت را دریافت کنیم، سپس آن را با بیت مپ "آیا می توانم میز رزرو کنم" و نتیجه را با بیت مپ "ایوان وجود دارد" استفاده کنیم. بیت مپ به دست آمده شامل لیستی از مؤسسات است که تمام معیارهای ما را برآورده می کنند. در این مثال، اینجا فقط رستوران Yunost است.


تئوری های زیادی وجود دارد، اما نگران نباشید، ما به زودی کد را خواهیم دید.

ایندکس های بیت مپ کجا استفاده می شوند؟

اگر نمایه های بیت مپ را در گوگل جستجو کنید، 90 درصد پاسخ ها به یک شکل به Oracle DB مربوط می شود. اما احتمالاً سایر DBMS ها نیز چنین چیز جالبی را پشتیبانی می کنند، درست است؟ نه واقعا.

بیایید فهرست مظنونان اصلی را مرور کنیم.

MySQL هنوز از نمایه های بیت مپ پشتیبانی نمی کند، اما پیشنهادی وجود دارد که پیشنهاد می کند این گزینه را اضافه کنید (https://dev.mysql.com/worklog/task/?id=1524).

PostgreSQL از نمایه های بیت مپ پشتیبانی نمی کند، اما از بیت مپ های ساده و عملیات بیت برای ترکیب نتایج جستجو در چندین نمایه دیگر استفاده می کند.

Tarantool دارای فهرست های بیتی است و از جستجوهای ساده در آنها پشتیبانی می کند.

Redis دارای فیلدهای بیت ساده است (https://redis.io/commands/bitfield) بدون امکان جستجوی آنها.

MongoDB هنوز از نمایه های بیت مپ پشتیبانی نمی کند، اما یک پیشنهاد نیز وجود دارد که پیشنهاد می کند این گزینه اضافه شود. https://jira.mongodb.org/browse/SERVER-1723

Elasticsearch از بیت مپ به صورت داخلی استفاده می کند (https://www.elastic.co/blog/frame-of-reference-and-roaring-bitmaps).

• اما یک همسایه جدید در خانه ما ظاهر شده است: پیلوسا. این یک پایگاه داده غیر رابطه ای جدید است که در Go نوشته شده است. این فقط شامل نمایه های بیت مپ است و همه چیز را بر اساس آنها قرار می دهد. کمی بعد در مورد آن صحبت خواهیم کرد.

پیاده سازی در Go

اما چرا شاخص های بیت مپ به ندرت استفاده می شوند؟ قبل از پاسخ به این سوال، می خواهم به شما نشان دهم که چگونه یک نمایه بیت مپ بسیار ساده را در Go پیاده سازی کنید.

بیت مپ ها در اصل تنها بخش هایی از داده ها هستند. در Go، بیایید از برش‌های بایت برای این کار استفاده کنیم.

ما یک بیت مپ برای یک مشخصه رستوران داریم و هر بیت در بیت مپ نشان می دهد که آیا رستوران خاصی این ویژگی را دارد یا خیر.

ما به دو تابع کمکی نیاز داریم. یکی برای پر کردن بیت مپ های ما با داده های تصادفی استفاده می شود. تصادفی، اما با احتمال خاصی که رستوران هر ملک را دارد. به عنوان مثال، من معتقدم که رستوران های بسیار کمی در مسکو وجود دارد که نمی توان در آن میز رزرو کرد و به نظر من حدود 20٪ از موسسات برای گیاهخواران مناسب هستند.

تابع دوم بیت مپ را به لیستی از رستوران ها تبدیل می کند.


برای پاسخ به سؤال «رستوران‌های ارزان‌قیمتی که پاسیو دارند و می‌توانند رزرو کنند به من نشان بده»، به دو عملیات بیتی نیاز داریم: NOT و AND.

با استفاده از عملگر پیچیده تر AND NOT می توانیم کد خود را کمی ساده کنیم.

ما برای هر یک از این عملیات ها توابعی داریم. هر دوی آنها از طریق برش ها عبور می کنند، عناصر مربوطه را از هر کدام می گیرند، آنها را با یک عملیات بیت ترکیب می کنند و نتیجه را در برش به دست آمده قرار می دهند.

و اکنون می توانیم از بیت مپ ها و توابع خود برای پاسخ به پرس و جوی جستجو استفاده کنیم.

عملکرد چندان بالا نیست، حتی اگر توابع بسیار ساده هستند و ما با عدم برگرداندن یک برش جدید در هر بار فراخوانی تابع، پول زیادی را پس انداز کردیم.

پس از انجام کمی نمایه سازی با pprof، متوجه شدم که کامپایلر Go یک بهینه سازی بسیار ساده اما بسیار مهم را از دست داده است: تابع درونی.

واقعیت این است که کامپایلر Go به طرز وحشتناکی از حلقه هایی که از میان برش ها عبور می کنند می ترسد و به طور قاطعانه از توابع درون خطی حاوی چنین حلقه هایی خودداری می کند.

اما من نمی ترسم و می توانم کامپایلر را با استفاده از goto به جای حلقه مانند روزهای خوب قدیم فریب دهم.

و همانطور که می بینید، اکنون کامپایلر با خوشحالی تابع ما را وارد می کند! در نتیجه ما موفق به صرفه جویی در حدود 2 میکروثانیه می شویم. بد نیست!

اگر از نزدیک به خروجی مونتاژ نگاه کنید، گلوگاه دوم به راحتی قابل مشاهده است. کامپایلر یک بررسی مرز برش را درست در داغترین حلقه ما اضافه کرد. واقعیت این است که Go یک زبان امن است، کامپایلر می ترسد که سه آرگومان من (سه برش) اندازه های متفاوتی داشته باشند. پس از همه، در این صورت احتمال تئوری وقوع به اصطلاح سرریز بافر وجود خواهد داشت.

بیایید کامپایلر را با نشان دادن اینکه همه برش ها یک اندازه هستند، مطمئن کنیم. ما می توانیم این کار را با اضافه کردن یک بررسی ساده در ابتدای تابع خود انجام دهیم.

با دیدن این، کامپایلر با خوشحالی از بررسی می گذرد و در نهایت 500 نانوثانیه دیگر صرفه جویی می کنیم.

بوق های بزرگ

بسیار خوب، ما موفق شدیم کمی عملکرد را از اجرای ساده خود کم کنیم، اما این نتیجه در واقع بسیار بدتر از آن چیزی است که در سخت افزار فعلی ممکن است.

تنها کاری که ما انجام می دهیم عملیات بیت اولیه است و پردازنده های ما آنها را بسیار کارآمد انجام می دهند. اما، متأسفانه، ما پردازنده خود را با قطعات بسیار کوچک "تغذیه" می کنیم. توابع ما عملیات را بر اساس بایت به بایت انجام می دهند. ما به راحتی می‌توانیم کد خود را به گونه‌ای تنظیم کنیم که با تکه‌های 8 بایتی با استفاده از برش‌های UInt64 کار کند.

همانطور که می بینید، این تغییر کوچک با افزایش هشت برابری اندازه دسته، سرعت برنامه ما را هشت برابر کرد. می توان گفت که سود خطی است.

پیاده سازی در اسمبلر

اما این پایان کار نیست. پردازنده های ما می توانند با تکه های 16، 32 و حتی 64 بایتی کار کنند. چنین عملیات «گسترده» را داده‌های چندگانه یک دستورالعمل (SIMD؛ یک دستورالعمل، داده‌های زیاد) می‌نامند، و فرآیند تبدیل کد به طوری که از چنین عملیاتی استفاده می‌کند، بردارسازی نامیده می‌شود.

متأسفانه، کامپایلر Go در بردارسازی عالی نیست. در حال حاضر، تنها راه برای برداری کد Go، گرفتن و قرار دادن این عملیات به صورت دستی با استفاده از اسمبلر Go است.

برو اسمبلر جانور عجیبی است. احتمالاً می دانید که زبان اسمبلی چیزی است که به شدت با معماری رایانه ای که برای آن می نویسید مرتبط است، اما در Go اینطور نیست. اسمبلر Go بیشتر شبیه یک IRL (زبان نمایندگی متوسط) یا زبان متوسط ​​است: عملاً مستقل از پلتفرم است. راب پایک عملکرد عالی ارائه کرد گزارش در مورد این موضوع چندین سال پیش در GopherCon در دنور.

علاوه بر این، Go از فرمت غیرمعمول Plan 9 استفاده می کند که با فرمت های پذیرفته شده AT&T و اینتل متفاوت است.

به جرات می توان گفت که نوشتن Go assembler با دست لذت بخش ترین نیست.

اما، خوشبختانه، در حال حاضر دو ابزار سطح بالا وجود دارد که به ما در نوشتن اسمبلر Go کمک می کند: PeachPy و avo. هر دو ابزار، اسمبلر Go را از کدهای سطح بالاتری که به ترتیب در پایتون و Go نوشته شده است تولید می کنند.

این ابزارها مواردی مانند تخصیص ثبت، حلقه های نوشتن، و به طور کلی فرآیند ورود به دنیای برنامه نویسی اسمبلی در Go را ساده می کنند.

ما از avo استفاده خواهیم کرد، بنابراین برنامه های ما تقریباً برنامه های Go معمولی خواهند بود.

این همان چیزی است که ساده ترین مثال از یک برنامه avo به نظر می رسد. ما یک تابع main() داریم که درون خود تابع Add() را تعریف می کند که معنای آن جمع دو عدد است. در اینجا توابع کمکی برای دریافت پارامترها بر اساس نام و دریافت یکی از رجیسترهای پردازنده رایگان و مناسب وجود دارد. همانطور که در ADDQ مشاهده می شود، هر عملیات پردازنده یک عملکرد مربوط به avo دارد. در نهایت، یک تابع کمکی برای ذخیره مقدار به دست آمده می بینیم.

با فراخوانی gogene برنامه را روی avo اجرا می کنیم و در نتیجه دو فایل تولید می شود:

• add.s با کد به دست آمده در اسمبلر Go.
• stub.go با هدرهای تابع برای اتصال دو جهان: Go و اسمبلر.

اکنون که دیدیم avo چه کاری و چگونه انجام می دهد، اجازه دهید به عملکردهای خود نگاه کنیم. من هر دو نسخه اسکالر و برداری (SIMD) توابع را پیاده سازی کردم.

بیایید ابتدا به نسخه های اسکالر نگاه کنیم.

همانطور که در مثال قبلی، ما یک ثبت نام عمومی رایگان و معتبر درخواست می کنیم، نیازی به محاسبه افست و اندازه برای آرگومان ها نداریم. avo همه این کارها را برای ما انجام می دهد.

ما قبلاً از برچسب‌ها و goto (یا پرش) برای بهبود عملکرد و فریب کامپایلر Go استفاده می‌کردیم، اما اکنون از همان ابتدا این کار را انجام می‌دهیم. نکته این است که چرخه ها یک مفهوم سطح بالاتر هستند. در اسمبلر فقط برچسب و پرش داریم.

کد باقیمانده باید از قبل آشنا و قابل درک باشد. ما یک حلقه را با برچسب ها و پرش ها شبیه سازی می کنیم، یک قطعه کوچک از داده ها را از دو برش خود می گیریم، آنها را با یک عملیات بیت ترکیب می کنیم (و نه در این مورد) و سپس نتیجه را در برش به دست آمده قرار می دهیم. همه.

این همان چیزی است که کد اسمبلر نهایی به نظر می رسد. ما مجبور نبودیم افست ها و اندازه ها را محاسبه کنیم (با رنگ سبز برجسته شده اند) یا رجیسترهای استفاده شده را پیگیری کنیم (با رنگ قرمز برجسته شده اند).

اگر عملکرد پیاده سازی زبان اسمبلی را با عملکرد بهترین پیاده سازی در Go مقایسه کنیم، خواهیم دید که همینطور است. و این مورد انتظار است. از این گذشته، ما کار خاصی انجام ندادیم - ما فقط کارهایی را که یک کامپایلر Go انجام می‌دهد، بازتولید کردیم.

متأسفانه، ما نمی‌توانیم کامپایلر را مجبور کنیم که توابع ما را که به زبان اسمبلی نوشته شده است، درون خطی کند. کامپایلر Go در حال حاضر چنین ویژگی را ندارد، اگرچه مدت زیادی است که درخواست اضافه کردن آن وجود دارد.

به همین دلیل است که استفاده از توابع کوچک در زبان اسمبلی غیرممکن است. باید یا توابع بزرگ بنویسیم یا از بسته ریاضی/بیت جدید استفاده کنیم یا زبان اسمبلر را دور بزنیم.

اکنون به نسخه های برداری توابع خود نگاه می کنیم.

برای این مثال، من تصمیم گرفتم از AVX2 استفاده کنم، بنابراین از عملیاتی استفاده خواهیم کرد که بر روی تکه های 32 بایتی کار می کنند. ساختار کد بسیار شبیه به نسخه اسکالر است: بارگذاری پارامترها، درخواست ثبت اشتراک رایگان و غیره.

یکی از نوآوری ها این است که عملیات برداری گسترده تر از ثبات های گسترده ویژه استفاده می کند. در مورد تکه های 32 بایتی، اینها رجیسترهایی هستند که پیشوند Y دارند. به همین دلیل است که تابع YMM() را در کد می بینید. اگر من از AVX-512 با تکه های 64 بیتی استفاده می کردم، پیشوند Z خواهد بود.

نوآوری دوم این است که من تصمیم گرفتم از یک بهینه سازی به نام حلقه unrolling استفاده کنم، یعنی انجام هشت عملیات حلقه به صورت دستی قبل از پرش به ابتدای حلقه. این بهینه سازی تعداد شاخه های کد را کاهش می دهد و با تعداد ثبت های رایگان موجود محدود می شود.

خوب، عملکرد چطور؟ او زیباست! ما در مقایسه با بهترین راه حل Go به سرعتی حدود هفت برابر دست یافتیم. چشمگیر است، درست است؟

اما حتی این پیاده‌سازی نیز می‌تواند با استفاده از AVX-512، واکشی اولیه یا JIT (کامپایلر به‌موقع) برای زمان‌بندی پرس و جو تسریع شود. اما مطمئناً این موضوع برای یک گزارش جداگانه است.

مشکلات با نمایه های بیت مپ

اکنون که قبلاً به پیاده‌سازی ساده یک نمایه بیت مپ در Go و یک شاخص بسیار سازنده‌تر در زبان اسمبلی نگاه کرده‌ایم، اجازه دهید در نهایت در مورد اینکه چرا شاخص‌های بیت مپ به ندرت استفاده می‌شوند صحبت کنیم.

مقالات قدیمی تر به سه مشکل با نمایه های بیت مپ اشاره می کنند، اما مقالات جدیدتر و من استدلال می کنم که آنها دیگر مرتبط نیستند. ما عمیقاً در هر یک از این مشکلات غوطه ور نمی شویم، بلکه سطحی به آنها نگاه می کنیم.

مشکل کاردینالیته بالا

بنابراین، به ما گفته می شود که نمایه های بیت مپ فقط برای فیلدهایی با کاردینالیته کم مناسب هستند، یعنی آنهایی که مقادیر کمی دارند (مثلاً جنسیت یا رنگ چشم) و دلیل آن این است که نمایش معمول چنین فیلدهایی (یکی بیت به ازای مقدار) در صورت کاردینالیته بالا، فضای زیادی را اشغال می کند و علاوه بر این، این شاخص های بیت مپ ضعیف (به ندرت) پر می شوند.


گاهی اوقات ممکن است از یک نمایش متفاوت استفاده کنیم، مانند نمونه استانداردی که برای نمایش اعداد استفاده می کنیم. اما ظهور الگوریتم های فشرده سازی بود که همه چیز را تغییر داد. در طول دهه‌های گذشته، دانشمندان و محققان تعداد زیادی الگوریتم فشرده‌سازی برای نقشه‌های بیتی ارائه کرده‌اند. مزیت اصلی آنها این است که برای انجام عملیات بیت نیازی به فشرده سازی بیت مپ نیست - ما می توانیم عملیات بیت را مستقیماً روی بیت مپ های فشرده انجام دهیم.

اخیراً رویکردهای ترکیبی مانند بیت مپ های خروشان ظاهر شده اند. آنها به طور همزمان از سه نمایش مختلف برای بیت مپ ها استفاده می کنند - خود بیت مپ ها، آرایه ها و به اصطلاح اجرای بیت ها - و تعادل بین آنها برای به حداکثر رساندن عملکرد و به حداقل رساندن مصرف حافظه وجود دارد.

می توانید بیت مپ های خروشان را در محبوب ترین برنامه ها بیابید. در حال حاضر تعداد زیادی پیاده سازی برای طیف گسترده ای از زبان های برنامه نویسی، از جمله بیش از سه پیاده سازی برای Go وجود دارد.

روش دیگری که می تواند به ما در مقابله با کاردینالیته بالا کمک کند، binning نام دارد. تصور کنید میدانی دارید که نشان دهنده قد یک فرد است. قد یک عدد ممیز شناور است، اما ما انسان ها اینطور به آن فکر نمی کنیم. برای ما هیچ تفاوتی بین قد 185,2 سانتی متر و 185,3 سانتی متر وجود ندارد.

به نظر می رسد که می توانیم مقادیر مشابه را به گروه هایی در عرض 1 سانتی متر گروه بندی کنیم.

و اگر همچنین بدانیم که تعداد بسیار کمی از افراد کوتاه‌تر از 50 سانتی‌متر و بلندتر از 250 سانتی‌متر هستند، می‌توانیم اساساً یک میدان با کاردینالیته بی‌نهایت را به میدانی با کاردینالیتی حدود 200 مقدار تبدیل کنیم.

البته در صورت نیاز می توانیم فیلتر اضافی را بعدا انجام دهیم.

مشکل پهنای باند بالا

مشکل بعدی نمایه های بیت مپ این است که به روز رسانی آنها می تواند بسیار گران باشد.

پایگاه‌های داده باید بتوانند داده‌ها را به‌روزرسانی کنند، در حالی که به طور بالقوه صدها پرسش دیگر در حال جستجوی داده‌ها هستند. برای جلوگیری از مشکلات دسترسی همزمان به داده ها یا سایر مشکلات اشتراک گذاری، به قفل نیاز داریم. و جایی که یک قفل بزرگ وجود دارد، یک مشکل وجود دارد - بحث قفل، زمانی که این قفل تبدیل به یک گلوگاه شود.

این مشکل را می توان با استفاده از شاردینگ یا استفاده از نمایه های نسخه شده حل کرد یا دور زد.

شاردینگ یک چیز ساده و شناخته شده است. شما می توانید یک نمایه بیت مپ را مانند هر داده دیگری خرد کنید. به جای یک قفل بزرگ، یک دسته قفل کوچک دریافت خواهید کرد و بنابراین از شر کشمکش خلاص خواهید شد.

راه دوم برای حل مشکل استفاده از نمایه های نسخه شده است. می‌توانید یک کپی از فهرستی که برای جستجو یا خواندن استفاده می‌کنید و یکی برای نوشتن یا به‌روزرسانی استفاده کنید. و یک بار در یک بازه زمانی خاص (مثلاً هر 100 میلی ثانیه یا 500 میلی ثانیه یک بار) آنها را کپی می کنید و آنها را تعویض می کنید. البته، این رویکرد فقط در مواردی قابل اجرا است که برنامه شما بتواند فهرست جستجوی کمی عقب مانده را مدیریت کند.

این دو رویکرد را می توان به طور همزمان مورد استفاده قرار داد: می توانید یک نمایه نسخه خرد شده داشته باشید.

پرس و جوهای پیچیده تر

مشکل نهایی با نمایه‌های بیت مپ این است که به ما گفته می‌شود برای انواع پیچیده‌تر کوئری‌ها، مانند کوئری‌های span، مناسب نیستند.

در واقع، اگر در مورد آن فکر کنید، عملیات بیتی مانند AND، OR، و غیره برای درخواست‌های a la خیلی مناسب نیستند.

یک راه حل ساده لوحانه و بسیار غیرعاقلانه این است که نتایج را برای هر ارزش دلار گرفته و آنها را با یک عملیات OR بیتی ترکیب کنیم.

یک راه حل کمی بهتر استفاده از گروه بندی است. مثلا در گروه های 50 دلاری. این روند ما را 50 برابر سرعت می بخشد.

اما با استفاده از نمای ایجاد شده مخصوص این نوع درخواست، مشکل نیز به راحتی حل می شود. در مقالات علمی به آن bitmaps با دامنه رمزگذاری شده می گویند.

در این نمایش، ما فقط یک بیت را برای مقداری (مثلاً 200) تنظیم نمی کنیم، بلکه این مقدار و همه چیز را بالاتر از آن قرار می دهیم. 200 به بالا همینطور برای 300: 300 و بالاتر. و غیره.

با استفاده از این نمایش، می‌توانیم با دو بار پیمایش نمایه به این نوع جستجو پاسخ دهیم. ابتدا لیستی از هتل هایی که هزینه اتاق آنها کمتر یا 300 دلار است را دریافت می کنیم و سپس آنهایی را که هزینه اتاق آنها کمتر یا 199 دلار است را از آن حذف می کنیم. آماده.

شگفت زده خواهید شد، اما حتی geoqueries با استفاده از نمایه های بیت مپ امکان پذیر است. ترفند این است که از یک نمایش هندسی استفاده کنید که مختصات شما را با یک شکل هندسی احاطه کند. مثلا S2 از گوگل. شکل باید به شکل سه یا چند خط متقاطع قابل شماره گذاری باشد. به این ترتیب می‌توانیم ژئوکوئری خود را به چندین کوئری «در امتداد شکاف» (در امتداد این خطوط شماره‌دار) تبدیل کنیم.

راه حل های آماده

امیدوارم کمی به شما علاقه مند شده باشم و اکنون ابزار مفید دیگری در زرادخانه خود داشته باشید. اگر زمانی نیاز به انجام چنین کاری داشته باشید، می دانید که به کدام سمت نگاه کنید.

با این حال، همه افراد زمان، حوصله یا منابع لازم برای ایجاد نمایه های بیت مپ را از ابتدا ندارند. به خصوص موارد پیشرفته تر، برای مثال، با استفاده از SIMD.

خوشبختانه چندین راه حل آماده برای کمک به شما وجود دارد.

بیت مپ های خروشان

اولاً، همان کتابخانه بیت مپ های خروشانی وجود دارد که قبلاً در مورد آن صحبت کردم. این شامل تمام کانتینرهای لازم و عملیات بیت است که برای ایجاد یک نمایه بیت مپ کامل به آنها نیاز دارید.

متأسفانه، در حال حاضر، هیچ یک از پیاده‌سازی‌های Go از SIMD استفاده نمی‌کنند، به این معنی که اجرای Go عملکرد کمتری نسبت به پیاده‌سازی‌های C دارند.

پیلوسا

محصول دیگری که می تواند به شما کمک کند Pilosa DBMS است که در واقع فقط نمایه های بیت مپ دارد. این یک راه حل نسبتا جدید است، اما با سرعت زیادی قلب ها را به دست می آورد.

Pilosa از بیت مپ های خروشان به صورت داخلی استفاده می کند و به شما توانایی استفاده از آنها را می دهد، همه چیزهایی را که در بالا در مورد آنها صحبت کردم ساده و توضیح می دهد: گروه بندی، بیت مپ های رمزگذاری شده با محدوده، مفهوم یک فیلد و غیره.

بیایید نگاهی گذرا به مثالی از استفاده از Pilosa برای پاسخ دادن به سؤالی که قبلاً با آن آشنایی دارید بیاندازیم.

مثال بسیار شبیه چیزی است که قبلا دیدید. یک کلاینت در سرور Pilosa ایجاد می کنیم، یک فهرست و فیلدهای لازم ایجاد می کنیم، سپس فیلدهای خود را با داده های تصادفی با احتمالات پر می کنیم و در نهایت، کوئری آشنا را اجرا می کنیم.

پس از آن، از NOT در قسمت "گران قیمت" استفاده می کنیم، سپس نتیجه (یا AND آن) را با فیلد "terrace" و با قسمت "Reservations" قطع می کنیم. و در نهایت به نتیجه نهایی می رسیم.

من واقعا امیدوارم که در آینده قابل پیش بینی این نوع جدید از ایندکس در DBMS هایی مانند MySQL و PostgreSQL - نمایه های بیت مپ نیز ظاهر شود.

نتیجه

اگه هنوز نخوابیدی ممنون به دلیل زمان محدود مجبور شدم به طور خلاصه به موضوعات زیادی بپردازم، اما امیدوارم صحبت مفید و شاید انگیزه دهنده باشد.

ایندکس های بیت مپ خوب است که در مورد آنها بدانید، حتی اگر در حال حاضر به آنها نیاز ندارید. بگذارید آنها ابزار دیگری در جعبه ابزار شما باشند.

ما به ترفندهای عملکردی مختلف برای Go و مواردی که کامپایلر Go هنوز به خوبی از پس آن‌ها برنمی‌آید، نگاه کرده‌ایم. اما دانستن این موضوع برای هر برنامه نویس Go کاملاً مفید است.

این تمام چیزی است که می خواستم به شما بگویم. متشکرم!

منبع: www.habr.com