Въведение
Изнесох този доклад на английски на конференцията GopherCon Russia 2019 в Москва и на руски на среща в Нижни Новгород. Говорим за растерен индекс - по-рядко срещан от B-дървото, но не по-малко интересен. Споделяне речи на конференцията на английски език и текстови преписи на руски език.
Ще разгледаме как работи растерният индекс, кога е по-добър, кога е по-лош от другите индекси и в кои случаи е значително по-бърз от тях; Нека да видим кои популярни СУБД вече имат растерни индекси; Нека се опитаме да напишем наши собствени в Go. И „за десерт“ ще използваме готови библиотеки, за да създадем собствена супер бърза специализирана база данни.
Силно се надявам, че моите произведения ще бъдат полезни и интересни за вас. Отивам!
въведение
Здравейте всички! Шест вечерта е и всички сме супер уморени. Чудесно време да поговорим за скучната теория на индекса на базата данни, нали? Не се притеснявайте, ще имам няколко реда изходен код тук и там. 🙂
Шегата настрана, докладът е пълен с информация, а ние нямаме много време. Така че да започваме.
Днес ще говоря за следното:
- какво представляват индексите;
- какво е растерен индекс;
- къде се използва и къде НЕ се използва и защо;
- проста реализация в Go и малко борба с компилатора;
- малко по-малко проста, но много по-продуктивна реализация в Go асемблер;
- “проблеми” на растерни индекси;
- съществуващи реализации.
И така, какво представляват индексите?
Индексът е отделна структура от данни, която поддържаме и актуализираме в допълнение към основните данни. Използва се за ускоряване на търсенето. Без индекси, търсенето би изисквало пълно преглеждане на данните (процес, наречен пълно сканиране), а този процес има линейна алгоритмична сложност. Но базите данни обикновено съдържат огромни количества данни и линейната сложност е твърде бавна. В идеалния случай бихме получили логаритмична или постоянна.
Това е изключително сложна тема, изпълнена с тънкости и компромиси, но след като разгледах десетилетия на разработване и изследване на бази данни, съм готов да кажа, че има само няколко широко използвани подхода за създаване на индекси на бази данни.
Първият подход е йерархично намаляване на пространството за търсене, разделяне на пространството за търсене на по-малки части.
Обикновено правим това с помощта на различни видове дървета. Пример може да бъде голяма кутия с материали в гардероба ви, която съдържа по-малки кутии с материали, разделени на различни теми. Ако имате нужда от материали, вероятно ще ги търсите в кутия с надпис „Материали“, а не такава с надпис „Бисквитки“, нали?
Вторият подход е веднага да изберете желания елемент или група от елементи. Правим това в хеш карти или обратни индекси. Използването на хеш карти е много подобно на предишния пример, но вместо кутия с кутии, имате куп малки кутии с крайни артикули в гардероба си.
Третият подход е премахване на необходимостта от търсене. Ние правим това с помощта на Bloom филтри или кукувички филтри. Първите дават отговор мигновено, като ви спестяват необходимостта да търсите.
Последният подход е да използваме пълноценно цялата мощ, която съвременният хардуер ни дава. Точно това правим в растерните индекси. Да, когато ги използваме, понякога трябва да преминем през целия индекс, но го правим супер ефективно.
Както казах, темата за индексите на бази данни е обширна и пълна с компромиси. Това означава, че понякога можем да използваме няколко подхода едновременно: ако трябва да ускорим още повече търсенето или ако трябва да покрием всички възможни видове търсене.
Днес ще говоря за най-малко познатия подход от тези - растерни индекси.
Кой съм аз, че да говоря по тази тема?
Работя като ръководител на екип в Badoo (може би сте по-запознати с другия ни продукт, Bumble). Вече имаме повече от 400 милиона потребители по целия свят и много функции, които избират най-доброто за тях. Правим това с помощта на персонализирани услуги, включително растерни индекси.
И така, какво е растерен индекс?
Растерните индекси, както подсказва името, използват растерни изображения или битови набори за реализиране на индекс за търсене. От птичи поглед този индекс се състои от едно или повече такива растерни изображения, представляващи всякакви обекти (като хора) и техните свойства или параметри (възраст, цвят на очите и т.н.), и алгоритъм, използващ битови операции (И, ИЛИ, НЕ ), за да отговорите на заявката за търсене.
Казват ни, че растерните индекси са най-подходящи и много ефективни за случаи, когато има търсения, които комбинират заявки в много колони с ниска кардиналност (помислете за „цвят на очите“ или „семейно положение“ срещу нещо като „разстояние от центъра на града“). Но по-късно ще покажа, че те работят добре и за колони с висока кардиналност.
Нека да разгледаме най-простия пример за индекс на растерно изображение.
Представете си, че имаме списък с московски ресторанти с бинарни свойства като тези:
- близо до метро;
- има собствен паркинг;
- има веранда (има тераса);
- можете да резервирате маса (приема резервации);
- подходящ за вегетарианци (vegan friendly);
- скъпо (скъпо).
Нека да дадем на всеки ресторант пореден номер, започващ от 0, и да разпределим памет за 6 растерни карти (по една за всяка характеристика). След това ще попълним тези растерни изображения в зависимост от това дали ресторантът има това свойство или не. Ако ресторант 4 има веранда, тогава бит № 4 в растерното изображение „има веранда“ ще бъде зададен на 1 (ако няма веранда, тогава на 0).
Сега имаме най-простия възможен индекс на растерно изображение и можем да го използваме, за да отговорим на заявки като:
- „Покажете ми ресторанти, подходящи за вегетарианци“;
- „Покажете ми евтини ресторанти с веранда, където можете да резервирате маса.“
как? Нека да погледнем. Първото искане е много просто. Всичко, което трябва да направим, е да вземем растерната карта „подходяща за вегетарианци“ и да я превърнем в списък с ресторанти, чиито части са изложени.
Второто искане е малко по-сложно. Трябва да използваме растерното изображение NOT върху „скъпото“ растерно изображение, за да получим списък с евтини ресторанти, след това И с растерното изображение „мога ли да резервирам маса“ и И резултата с растерното изображение „има веранда“. Получената растерна карта ще съдържа списък със заведения, които отговарят на всички наши критерии. В този пример това е само ресторант Юност.
Има много теория, но не се притеснявайте, ще видим кода много скоро.
Къде се използват растерни индекси?
Ако Google индексира растерни изображения, 90% от отговорите ще бъдат свързани с Oracle DB по един или друг начин. Но други СУБД вероятно също поддържат такова страхотно нещо, нали? Не точно.
Да преминем през списъка на основните заподозрени.
MySQL все още не поддържа растерни индекси, но има предложение, предлагащо добавянето на тази опция ().
PostgreSQL не поддържа растерни индекси, но използва прости растерни изображения и битови операции, за да комбинира резултатите от търсенето в множество други индекси.
Tarantool има bitset индекси и поддържа прости търсения в тях.
Redis има прости битови полета) без възможност да ги търсите.
MongoDB все още не поддържа растерни индекси, но също така има предложение, предлагащо тази опция да бъде добавена
Elasticsearch използва растерни изображения вътрешно).
- Но в къщата ни се появи нов съсед: Пилоза. Това е нова нерелационна база данни, написана на 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. Go асемблерът е по-скоро като IRL (междинен език за представяне) или междинен език: той е практически независим от платформата. Роб Пайк се представи отлично по тази тема преди няколко години на GopherCon в Денвър.
Освен това Go използва необичаен формат Plan 9, който се различава от общоприетите формати на AT&T и Intel.
Може да се каже, че писането на Go асемблер на ръка не е най-забавното.
Но, за щастие, вече има два инструмента на високо ниво, които ни помагат да напишем Go асемблер: PeachPy и avo. И двете помощни програми генерират Go асемблер от код от по-високо ниво, написан съответно на Python и Go.
Тези помощни програми опростяват неща като разпределение на регистри, писане на цикли и като цяло опростяват процеса на навлизане в света на асемблерното програмиране в Go.
Ще използваме avo, така че нашите програми ще бъдат почти обикновени Go програми.
Ето как изглежда най-простият пример за avo програма. Имаме функция main(), която дефинира в себе си функцията Add(), чийто смисъл е да събере две числа. Тук има помощни функции, за да получите параметри по име и да получите един от безплатните и подходящи регистри на процесора. Всяка операция на процесора има съответна функция на avo, както се вижда в ADDQ. Накрая виждаме помощна функция за съхраняване на получената стойност.
Като извикаме go generate, ще изпълним програмата на avo и в резултат ще бъдат генерирани два файла:
- add.s с получения код в Go асемблер;
- stub.go с функционални заглавки за свързване на два свята: Go и асемблер.
Сега, след като видяхме какво прави avo и как, нека да разгледаме нашите функции. Приложих както скаларна, така и векторна (SIMD) версия на функциите.
Нека първо да разгледаме скаларните версии.
Както в предишния пример, ние искаме безплатен и валиден регистър с общо предназначение, не е необходимо да изчисляваме отмествания и размери за аргументите. avo прави всичко това за нас.
Преди използвахме етикети и goto (или скокове), за да подобрим производителността и да подведем Go компилатора, но сега го правим от самото начало. Въпросът е, че циклите са понятие от по-високо ниво. В асемблера имаме само етикети и скокове.
Останалият код вече трябва да е познат и разбираем. Ние емулираме цикъл с етикети и скокове, вземаме малка част от данните от нашите два среза, комбинираме ги с битова операция (И НЕ в този случай) и след това поставяме резултата в получения срез. Всичко.
Ето как изглежда крайният асемблер код. Не трябваше да изчисляваме отмествания и размери (маркирани в зелено) или да следим използваните регистри (маркирани в червено).
Ако сравним производителността на реализацията на асемблерния език с производителността на най-добрата реализация в Go, ще видим, че тя е същата. И това е очаквано. В края на краищата не направихме нищо специално - просто възпроизведохме това, което би направил един Go компилатор.
За съжаление не можем да принудим компилатора да вгради нашите функции, написани на асемблер. Компилаторът Go в момента няма такава функция, въпреки че има заявка за добавянето й от доста време.
Ето защо е невъзможно да се извлече полза от малки функции на асемблер. Трябва или да напишем големи функции, или да използваме новия пакет math/bits, или да заобиколим асемблерния език.
Нека сега да разгледаме векторните версии на нашите функции.
За този пример реших да използвам AVX2, така че ще използваме операции, които работят върху 32-байтови парчета. Структурата на кода е много подобна на скаларната версия: зареждане на параметри, запитване за безплатен споделен регистър и т.н.
Едно нововъведение е, че по-широките векторни операции използват специални широки регистри. В случай на 32-байтови парчета, това са регистри с префикс Y. Ето защо виждате функцията YMM() в кода. Ако използвах AVX-512 с 64-битови парчета, префиксът щеше да бъде Z.
Второто нововъведение е, че реших да използвам оптимизация, наречена loop unrolling, което означава извършване на осем циклични операции ръчно, преди да скоча до началото на цикъла. Тази оптимизация намалява броя на разклоненията в кода и е ограничена от броя на наличните безплатни регистри.
Е, какво ще кажете за представянето? Тя е красива! Постигнахме ускоряване от около седем пъти в сравнение с най-доброто решение Go. Впечатляващо, нали?
Но дори това внедряване може потенциално да бъде ускорено чрез използване на AVX-512, предварително извличане или JIT (компилатор точно навреме) за планировчика на заявки. Но това със сигурност е тема за отделен доклад.
Проблеми с растерни индекси
Сега, след като вече разгледахме проста реализация на растерен индекс в Go и много по-продуктивен такъв в асемблер, нека най-накрая да поговорим за това защо растерните индекси се използват толкова рядко.
По-стари документи споменават три проблема с растерни индекси, но по-нови документи и аз твърдя, че те вече не са уместни. Няма да навлизаме дълбоко във всеки от тези проблеми, а ще ги разгледаме повърхностно.
Проблемът с високата мощност
И така, казаха ни, че растерните индекси са подходящи само за полета с ниска кардиналност, тоест такива, които имат малко стойности (например пол или цвят на очите) и причината е, че обичайното представяне на такива полета (едно бит на стойност) в случай на висока кардиналност, това ще заема твърде много място и освен това тези растерни индекси ще бъдат лошо (рядко) запълнени.
Понякога може да използваме различно представяне, като например стандартното, което използваме за представяне на числа. Но появата на алгоритми за компресиране промени всичко. През последните десетилетия учени и изследователи измислиха голям брой алгоритми за компресиране на растерни изображения. Основното им предимство е, че няма нужда да декомпресирате растерни изображения, за да извършвате битови операции - можем да извършваме битови операции директно върху компресирани растерни изображения.
Напоследък започнаха да се появяват хибридни подходи, като ревящи растерни изображения. Те използват едновременно три различни представяния за растерни изображения - самите растерни изображения, масиви и така наречените битови серии - и балансират между тях, за да увеличат максимално производителността и да намалят консумацията на памет.
Можете да намерите ревящи растерни изображения в най-популярните приложения. Вече има огромен брой реализации за голямо разнообразие от езици за програмиране, включително повече от три реализации за Go.
Друг подход, който може да ни помогне да се справим с висока кардиналност, се нарича групиране. Представете си, че имате поле, представляващо височината на човек. Височината е число с плаваща запетая, но ние, хората, не мислим за това по този начин. За нас няма разлика между височина 185,2 см и 185,3 см.
Оказва се, че можем да групираме подобни стойности в групи в рамките на 1 cm.
И ако също така знаем, че много малко хора са по-ниски от 50 см и по-високи от 250 см, тогава по същество можем да превърнем поле с безкрайна кардиналност в поле с кардиналност от около 200 стойности.
Разбира се, при необходимост можем да направим допълнително филтриране след това.
Проблем с висока честотна лента
Следващият проблем с растерните индекси е, че актуализирането им може да бъде много скъпо.
Базите данни трябва да могат да актуализират данните, докато потенциално стотици други заявки търсят данните. Имаме нужда от ключалки, за да избегнем проблеми с едновременния достъп до данни или други проблеми със споделянето. И там, където има едно голямо заключване, има проблем - спор за заключване, когато това заключване се превърне в тясно място.
Този проблем може да бъде решен или заобиколен чрез използване на шардинг или използване на индекси с версии.
Шардингът е просто и добре познато нещо. Можете да разделите индекс на растерно изображение, както бихте направили с други данни. Вместо едно голямо заключване, вие ще получите куп малки ключалки и по този начин ще се отървете от споровете за заключване.
Вторият начин за решаване на проблема е да се използват индекси с версии. Можете да имате едно копие на индекса, което използвате за търсене или четене, и едно, което използвате за писане или актуализиране. И веднъж в определен период от време (например веднъж на всеки 100 ms или 500 ms) ги дублираш и ги разменяш. Разбира се, този подход е приложим само в случаите, когато вашето приложение може да се справи с леко изоставащ индекс за търсене.
Тези два подхода могат да се използват едновременно: можете да имате сегментиран индекс с версии.
По-сложни заявки
Последният проблем с растерните индекси е, че ни се казва, че не са подходящи за по-сложни типове заявки, като например span заявки.
Наистина, ако се замислите, битовите операции като И, ИЛИ и т.н. не са много подходящи за заявки от типа „Покажете ми хотели с цени на стаите от 200 до 300 долара на нощувка.“
Наивно и много неразумно решение би било да се вземат резултатите за всяка стойност в долари и да се комбинират с побитова операция ИЛИ.
Малко по-добро решение би било използването на групиране. Например в групи от 50 долара. Това би ускорило нашия процес 50 пъти.
Но проблемът също така лесно се решава чрез използване на изглед, създаден специално за този тип заявки. В научните статии се нарича растерни изображения, кодирани в диапазон.
В това представяне ние не просто задаваме един бит за някаква стойност (например 200), но задаваме тази стойност и всичко по-високо. 200 и повече. Същото за 300: 300 и по-горе. И така нататък.
Използвайки това представяне, можем да отговорим на този вид заявка за търсене, като преминем през индекса само два пъти. Първо ще получим списък с хотели, където стаята струва по-малко или $300, а след това ще премахнем от него тези, където цената на стаята е по-малко или $199. Готов.
Ще се изненадате, но дори геозаявките са възможни с помощта на растерни индекси. Номерът е да използвате геометрично представяне, което обгражда вашата координата с геометрична фигура. Например S2 от Google. Фигурата трябва да може да бъде представена под формата на три или повече пресичащи се линии, които могат да бъдат номерирани. По този начин можем да превърнем нашата геозаявка в няколко заявки „по дължината на празнината“ (по тези номерирани редове).
Готови решения
Надявам се, че съм ви заинтересувал малко и вече имате още един полезен инструмент във вашия арсенал. Ако някога ви се наложи да направите нещо подобно, ще знаете накъде да търсите.
Въпреки това, не всеки има времето, търпението или ресурсите да създава растерни индекси от нулата. Особено по-напредналите, използващи SIMD, например.
За щастие има няколко готови решения, които да ви помогнат.
Ревящи растерни изображения
Първо, има същата ревяща библиотека с растерни изображения, за която вече говорих. Той съдържа всички необходими контейнери и битови операции, които ще ви трябват, за да направите пълноценен растерен индекс.
За съжаление, в момента нито една от реализациите на Go не използва SIMD, което означава, че реализациите на Go са по-малко производителни от реализациите на C, например.
космат
Друг продукт, който може да ви помогне, е Pilosa DBMS, която всъщност има само растерни индекси. Това е сравнително ново решение, но печели сърцата с голяма скорост.
Pilosa използва ревящи растерни изображения вътрешно и ви дава възможност да ги използвате, опростява и обяснява всички неща, за които говорих по-горе: групиране, кодирани в диапазон растерни изображения, концепцията за поле и т.н.
Нека да разгледаме набързо пример за използване на Pilosa, за да отговорите на въпрос, с който вече сте запознати.
Примерът е много подобен на това, което видяхте преди. Създаваме клиент към сървъра на Pilosa, създаваме индекс и необходимите полета, след това попълваме нашите полета с произволни данни с вероятности и накрая изпълняваме познатата заявка.
След това използваме NOT в полето "скъпо", след което пресичаме резултата (или го И) с полето "тераса" и с полето "резервации". И накрая, получаваме крайния резултат.
Наистина се надявам, че в обозримо бъдеще този нов тип индекс ще се появи и в СУБД като MySQL и PostgreSQL - растерни индекси.
Заключение
Ако все още не сте заспали, благодаря. Трябваше да засегна накратко много теми поради ограниченото време, но се надявам, че разговорът беше полезен и може би дори мотивиращ.
Добре е да знаете за растерните индекси, дори и да не ви трябват в момента. Нека те бъдат още един инструмент в кутията ви с инструменти.
Разгледахме различни трикове за ефективност за Go и неща, с които Go компилаторът все още не се справя много добре. Но това е абсолютно полезно да знае всеки програмист на Go.
Това е всичко, което исках да ти кажа. Благодаря ти!
Източник: www.habr.com