киришүү
Мен бул докладды Москвадагы GopherCon Russia 2019 конференциясында англис тилинде жана Нижний Новгороддогу жолугушууда орус тилинде бердим. Биз битмап индекси жөнүндө сөз болуп жатат - B-даракка караганда азыраак таралган, бирок андан кем эмес кызыктуу. Бөлүшүү конференцияда сүйлөгөн сөздөрү англис тилинде жана тексттин стенограммасы орус тилинде.
Биз битмап индекси кандай иштээрин, качан жакшыраак, качан башка индекстерге караганда начарраак жана кандай учурларда алардан кыйла тезирээк экенин карап чыгабыз; Келгиле, кайсы популярдуу DBMS битмап индекстери бар экенин карап көрөлү; Go'до өзүбүздү жазганга аракет кылалы. Ал эми "десерт үчүн" биз өзүбүздүн супер-тез адистештирилген маалымат базасын түзүү үчүн даяр китепканаларды колдонобуз.
Менин эмгектерим сиздер үчүн пайдалуу жана кызыктуу болот деп чындап ишенем. Go!
тааныштыруу
Баарыңарга салам! Кечки алты, баарыбыз чарчадык. Кызыксыз маалыматтар базасынын индексинин теориясы жөнүндө сүйлөшүүгө сонун убакыт, туурабы? Кабатыр болбоңуз, менде булак-коддун эки саптары болот. 🙂
Тамашаларды кошпогондо, отчет маалыматка толгон жана биздин убактыбыз аз. Ошентип, баштайлы.
Бүгүн мен төмөндөгүлөр жөнүндө сүйлөшөм:
- индекстер деген эмне;
- битмап индекси деген эмне;
- ал кайда колдонулат жана кайда КОЛДОНУЛБАЙТ жана эмне үчүн;
- Go программасында жөнөкөй ишке ашыруу жана компилятор менен бир аз күрөш;
- бир аз жөнөкөй, бирок Go assemblerде бир топ жемиштүү ишке ашыруу;
- битмап индекстеринин "көйгөйлөрү";
- учурдагы ишке ашыруулар.
Ошентип, индекстер деген эмне?
Индекс - бул негизги маалыматтардан тышкары биз сактай турган жана жаңырткан өзүнчө маалымат структурасы. Бул издөөнү тездетүү үчүн колдонулат. Индекссиз, издөө маалыматтарды толугу менен карап чыгууну талап кылат (толук сканерлөө деп аталган процесс) жана бул процесс сызыктуу алгоритмдик татаалдыкка ээ. Бирок маалымат базалары адатта чоң көлөмдөгү маалыматтарды камтыйт жана сызыктуу татаалдык өтө жай. Идеалында, биз логарифмдик же туруктуу бирди алабыз.
Бул өтө татаал тема, майда-чүйдөсүнө чейин жана соодалашуулар менен толтурулган, бирок ондогон жылдар бою маалымат базасын иштеп чыгууну жана изилдөөнү карап чыккандан кийин, мен маалымат базасынын индекстерин түзүү үчүн кеңири колдонулган бир нече гана ыкмалар бар деп айтууга даярмын.
Биринчи ыкма издөө мейкиндигин иерархиялык түрдө кыскартуу, издөө мейкиндигин майда бөлүктөргө бөлүү.
Биз муну көбүнчө ар кандай дарактарды колдонуп жасайбыз. Мисалы, ар кандай темаларга бөлүнгөн материалдардын кичинекей кутучаларын камтыган шкафыңыздагы материалдардын чоң кутусу болот. Эгер сизге материалдар керек болсо, сиз аларды "Cookies" дегенден көрө "Материалдар" деген кутудан издейсиз, туурабы?
Экинчи ыкма - керектүү элементти же элементтер тобун дароо тандоо. Биз муну хэш карталарда же тескери индекстерде жасайбыз. Хеш карталарын колдонуу мурунку мисалга абдан окшош, бирок кутучалардын кутусунун ордуна сиздин шкафыңызда акыркы буюмдардын бир топ кичинекей кутучалары бар.
Үчүнчү ыкма - издөө зарылдыгын жок кылуу. Биз муну Блум чыпкалары же күкүк чыпкалары аркылуу жасайбыз. Биринчилери заматта жооп берип, сизди издөөдөн сактап калышат.
Акыркы ыкма — азыркы кездеги аппаратура бизге берип жаткан бардык кучту толук пайдалануу. Бул так биз битмап индекстер эмне кылат. Ооба, аларды колдонууда биз кээде бүтүндөй индексти карап чыгышыбыз керек, бирок биз муну абдан натыйжалуу жасайбыз.
Мен айткандай, маалымат базасы индекстеринин темасы кенен жана компромисстерге толгон. Бул кээде биз бир эле учурда бир нече ыкмаларды колдоно алабыз дегенди билдирет: издөөнү дагы тездетүү керек болсо, же бардык мүмкүн болгон издөө түрлөрүн камтуу керек болсо.
Бүгүн мен алардын эң аз белгилүү ыкмасы - битмап индекстери жөнүндө сүйлөшөм.
Бул темада сүйлөй турган мен киммин?
Мен Badoo компаниясында топтун жетекчиси болуп иштейм (балким, сиз биздин башка продуктубуз Бамбл менен жакшыраак тааныштырсыз). Бизде дүйнө жүзү боюнча 400 миллиондон ашык колдонуучу жана алар үчүн эң жакшы дал келген функцияларды тандап алган көптөгөн функциялар бар. Биз муну жеке кызматтарды, анын ичинде битмап индекстерин колдонуп жасайбыз.
Ошентип, битмап индекси деген эмне?
Растрлык индекстер, аты айтып тургандай, издөө индексин ишке ашыруу үчүн битмаптарды же битсеттерди колдонушат. Канаттуулардын көз карашы боюнча, бул индекс кандайдыр бир объекттерди (мисалы, адамдар) жана алардын касиеттерин же параметрлерин (курагы, көздүн түсү ж.б.) жана бит операцияларын (ЖАНА, ЖЕ, ЭМЕС) көрсөткөн бир же бир нече бит карталардан турат. ) издөө суроосуна жооп берүү үчүн.
Бизге битмап индекстери эң ылайыктуу жана көптөгөн төмөнкү кардиналдуулук мамычалар боюнча сурамдарды бириктирген издөөлөр үчүн эң ылайыктуу экенин айтышты ("көздүн түсү" же "үй-бүлөлүк абалы" менен "шаардын борборунан алыстык" сыяктуу нерселер жөнүндө ойлонуңуз). Бирок мен кийинчерээк алар жогорку кардиналдуулук мамычалар үчүн жакшы иштешерин көрсөтөм.
Битмап индексинин эң жөнөкөй мисалын карап көрөлү.
Элестеткиле, бизде экилик касиеттери бар Москва ресторандарынын тизмеси бар:
- метрого жакын;
- жеке паркинг бар;
- веранда бар (террасасы бар);
- үстөлдү ээлеп койсоңуз болот (брондоолорду кабыл алат);
- вегетарианчылар үчүн ылайыктуу (вегетариандык достук);
- кымбат (кымбат).
Келгиле, ар бир ресторанга 0дөн баштап катар номерин берели жана 6 битмапка эстутумду бөлөлү (ар бир мүнөздөмө үчүн бирден). Андан кийин биз ресторанда бул касиетке ээ же жок экенине жараша бул бит карталарын толтурабыз. Эгерде 4-ресторанда веранда болсо, анда “веранда бар” битмапындагы №4 бит 1ге коюлат (эгерде веранда жок болсо, анда 0).
Эми бизде мүмкүн болгон эң жөнөкөй битмап индекси бар жана биз аны төмөнкүдөй суроолорго жооп берүү үчүн колдоно алабыз:
- "Мага вегетариандык ресторандарды көрсөт";
- "Мага үстөлдү ээлеп ала турган верандасы бар арзан ресторандарды көрсөт."
Кантип? Келгиле, карап көрөлү. Биринчи өтүнүч абдан жөнөкөй. Бизге "вегетариандык достук" битмапты алып, аны биттери ачыкка чыккан ресторандардын тизмесине айлантуу керек.
Экинчи өтүнүч бир аз татаалыраак. Кымбат эмес ресторандардын тизмесин алуу үчүн биз "кымбат" битмапта NO битмапты колдонушубуз керек, андан кийин ЖАНА "үстөлдү ээлеп алсам болобу" битмап менен жана натыйжада "веранда бар" битмап менен. Натыйжадагы битмап биздин бардык критерийлерге жооп берген мекемелердин тизмесин камтыйт. Бул мисалда бул бир гана Юность рестораны.
Бул жерде көптөгөн теориялар бар, бирок кабатыр болбоңуз, биз кодду жакында көрөбүз.
Растрлык индекстер кайда колдонулат?
Эгер сиз Google битмап индекстерин издесеңиз, жооптордун 90% тигил же бул жол менен Oracle DB менен байланыштуу болот. Бирок, башка DBMS, балким, ошондой эле ушундай сонун нерсени колдойт, туурабы? Жок эле.
Келгиле, негизги шектүүлөрдүн тизмесин карап көрөлү.
MySQL битмап индекстерин азырынча колдобойт, бирок бул параметрди кошууну сунуш кылган Сунуш бар ().
PostgreSQL битмап индекстерин колдобойт, бирок бир нече башка индекстер боюнча издөө натыйжаларын бириктирүү үчүн жөнөкөй битмаптарды жана бит операцияларын колдонот.
Tarantool битсет индекстерине ээ жана алар боюнча жөнөкөй издөөлөрдү колдойт.
Redisдин жөнөкөй бит талаалары бар) аларды издөө мүмкүнчүлүгү жок.
MongoDB азырынча битмап индекстерин колдобойт, бирок бул опцияны кошууну сунуш кылган Сунуш дагы бар
Elasticsearch битмаптарды ички түрдө колдонот).
- Бирок биздин үйдө жаңы кошуна пайда болду: Пилоза. Бул Go тилинде жазылган жаңы реляциялык эмес маалымат базасы. Ал битмап индекстерин гана камтыйт жана бардыгын аларга негиздейт. Бул тууралуу бир аздан кийин сүйлөшөбүз.
Go'до ишке ашыруу
Бирок битмап индекстери эмне үчүн сейрек колдонулат? Бул суроого жооп берүүдөн мурун, мен сизге Go программасында өтө жөнөкөй битмап индексин кантип ишке ашырууну көрсөткүм келет.
Битмаптар - бул жөн гана маалыматтар. Go'до бул үчүн байт кесимдерин колдонолу.
Бизде бир ресторандын мүнөздөмөсү үчүн бир бит картасы бар жана битмаптагы ар бир бит белгилүү бир ресторанда бул касиетке ээ же жок экенин көрсөтүп турат.
Бизге эки жардамчы функция керек болот. Бири биздин бит карталарыбызды кокус маалыматтар менен толтуруу үчүн колдонулат. Кокустук, бирок белгилүү бир ыктымалдуулук менен ресторанда ар бир мүлк бар. Мисалы, мен Москвада үстөлдү ээлей албаган ресторандар өтө аз деп эсептейм жана мага 20%га жакыны вегетарианчыларга ылайыктуу окшойт.
Экинчи функция битмапты ресторандардын тизмесине айлантат.
"Мага короосу бар жана ээлеп коюуга мүмкүн болгон арзан ресторандарды көрсөт" деген суроого жооп берүү үчүн бизге эки биттик операция керек: ЭМЕС жана ЖАНА.
Биз татаал ЖАНА ЭМЕС операторун колдонуу менен кодубузду бир аз жөнөкөйлөштүрө алабыз.
Бул операциялардын ар бири үчүн бизде функциялар бар. Экөө тең тилкелерден өтүп, ар биринен тиешелүү элементтерди алып, бит операциясы менен бириктирип, натыйжаны пайда болгон кесимге салышат.
Эми биз издөө сурамына жооп берүү үчүн бит карталарыбызды жана функцияларыбызды колдоно алабыз.
Функциялар өтө жөнөкөй жана функция чакырылган сайын жаңы пайда болгон кесимди кайтарбай, көп акча үнөмдөгөнүнө карабастан, аткаруу анчалык деле жогору эмес.
pprof менен бир аз профилдештиргенден кийин, мен Go компиляторунда өтө жөнөкөй, бирок абдан маанилүү оптималдаштыруу жок экенин байкадым: функцияны киргизүү.
Чындыгында, Go компилятору тилкелерден өткөн циклдерден абдан коркот жана мындай циклдерди камтыган саптык функциялардан таптакыр баш тартат.
Бирок мен коркпойм жана эски күндөрдө болгондой, циклдин ордуна goto колдонуу менен компиляторду алдай алам.
Көрүнүп тургандай, эми компилятор биздин функциябызды бактылуу кылып киргизет! Натыйжада 2 микросекундга жакын убакытты үнөмдөөгө жетишебиз. Жаман эмес!
Эгер сиз монтаждын чыгышына кылдаттык менен карасаңыз, экинчи кыйынчылык оңой эле байкалат. Компилятор биздин эң ысык циклибиздин ичине кесим чектерин текшерүүнү кошту. Чынында, Go коопсуз тил, компилятор менин үч аргументим (үч кесим) ар кандай өлчөмдөгү деп коркот. Анткени, анда буфердик толуп кетүү деп аталган нерсенин пайда болушунун теориялык мүмкүнчүлүгү пайда болот.
Келгиле, компиляторду бардык кесимдердин өлчөмү бирдей экенин көрсөтүү менен ишендирели. Муну функциябыздын башында жөнөкөй чекти кошуу менен жасай алабыз.
Муну көрүп, компилятор чекти кубаныч менен өткөрүп жиберет жана биз дагы 500 наносекундду үнөмдөйбүз.
Чоң буттар
Макул, биз жөнөкөй ишке ашыруудан айрым көрсөткүчтөрдү кыскарта алдык, бирок бул жыйынтык чындыгында учурдагы аппараттык жабдыктарга караганда алда канча начар.
Биз кылган нерсе - бул негизги бит операциялары жана биздин процессорлор аларды абдан натыйжалуу аткарат. Бирок, тилекке каршы, биз процессорубузду өтө кичинекей жумуш менен "тамактандырабыз". Биздин функциялар байт-байт негизинде операцияларды аткарат. UInt8 тилкелерин колдонуп, 64 байттык бөлүктөр менен иштөө үчүн кодубузду оңой эле чыңдай алабыз.
Көрүнүп тургандай, бул кичинекей өзгөрүү партиянын көлөмүн сегиз эсеге көбөйтүү менен биздин программаны сегиз эсе тездетти. пайда сызыктуу деп айтууга болот.
Ассемблерде ишке ашыруу
Бирок бул аягы эмес. Биздин процессорлор 16, 32 жана атүгүл 64 байттык бөлүктөр менен иштей алат. Мындай “кеңири” операциялар бир нускама көп маалыматтар (SIMD; бир нускама, көп маалыматтар) деп аталат, ал эми кодду мындай операцияларды колдоно тургандай кылып өзгөртүү процесси векторизация деп аталат.
Тилекке каршы, Go компилятору векторизациялоодо эң сонун эмес. Учурда Go кодун векторизациялоонун бирден-бир жолу бул операцияларды Go ассемблери аркылуу кол менен алуу жана коюу.
Go assembler - бул кызыктай жырткыч. Сиз ассемблер тили сиз жазып жаткан компьютердин архитектурасына катуу байланышкан нерсе экенин билсеңиз керек, бирок Go'до андай эмес. Go ассемблери IRL (аралык өкүлчүлүк тили) же орто тил сыяктуу: ал иш жүзүндө платформадан көз карандысыз. Роб Пайк мыкты оюн көрсөттү Бул тема боюнча бир нече жыл мурун Денвердеги GopherCon.
Мындан тышкары, Go адаттан тыш План 9 форматын колдонот, ал жалпы кабыл алынган AT&T жана Intel форматтарынан айырмаланат.
Go assemblerди кол менен жазуу эң кызыктуу эмес деп айтууга болот.
Бирок, бактыга жараша, Go assemblerди жазууга жардам берген эки жогорку деңгээлдеги курал бар: PeachPy жана avo. Эки утилита тең Python жана Go тилдеринде жазылган жогорку деңгээлдеги коддон Go ассемблерин жаратат.
Бул утилиталар реестрди бөлүштүрүү, цикл жазуу сыяктуу нерселерди жөнөкөйлөштүрөт жана жалпысынан Go'до ассамблея программалоо дүйнөсүнө кирүү процессин жөнөкөйлөтөт.
Биз avo колдонобуз, андыктан биздин программалар дээрлик кадимки Go программалары болот.
Avo программасынын эң жөнөкөй мисалы ушундай көрүнөт. Бизде main() функциясы бар, ал өзүнүн ичинде Add() функциясын аныктайт, анын мааниси эки санды кошуу. Параметрлерди аты боюнча алуу жана акысыз жана ылайыктуу процессор регистрлеринин бирин алуу үчүн бул жерде жардамчы функциялар бар. Ар бир процессордун операциясы ADDQда көрүнүп тургандай, avoдо тиешелүү функцияга ээ. Акыр-аягы, биз пайда болгон маанини сактоо үчүн жардамчы функцияны көрөбүз.
gogener деп чакыруу менен биз программаны avoда аткарабыз жана натыйжада эки файл түзүлөт:
- Go ассемблеринде пайда болгон код менен add.s;
- stub.go эки дүйнөнү туташтыруу үчүн функциянын аталыштары менен: Go and assembler.
Эми биз avo эмне кылганын жана кантип аткарганын көргөндөн кийин, биздин функцияларды карап көрөлү. Мен функциялардын скалярдык жана вектордук (SIMD) версияларын ишке ашырдым.
Алгач скалярдык версияларды карап көрөлү.
Мурунку мисалдагыдай эле, биз акысыз жана жарактуу жалпы максаттуу реестрди сурап жатабыз, биз аргументтердин ордун жана өлчөмүн эсептөөнүн кереги жок. avo мунун баарын биз үчүн кылат.
Иштин майнаптуулугун жогорулатуу жана Go компиляторун алдоо үчүн биз энбелгилерди жана goto (же секирүү) колдончубуз, бирок азыр биз муну башынан эле жасап жатабыз. Кеп циклдер жогорку деңгээлдеги түшүнүк болуп саналат. Ассемблерде бизде этикеткалар жана секирүүлөр гана бар.
Калган код мурунтан эле тааныш жана түшүнүктүү болушу керек. Биз энбелгилери жана секирүүлөрү бар циклди туурайбыз, эки тилкебизден маалыматтын кичинекей бөлүгүн алып, аларды бир аз операция менен айкалыштырабыз (ЖАНА бул учурда ЭМЕС) анан натыйжаны пайда болгон кесимге салабыз. Баары.
Акыркы ассемблердин коду ушундай көрүнөт. Бизге офсеттерди жана өлчөмдөрдү (жашыл түс менен белгиленген) эсептеп же колдонулган регистрлерди (кызыл менен белгиленген) эсепке алуунун кереги жок болчу.
Ассемблер тилин ишке ашыруунун көрсөткүчтөрүн Goдогу эң жакшы ишке ашыруунун көрсөткүчтөрү менен салыштырсак, анын бирдей экенин көрөбүз. Жана бул күтүлүүдө. Акыры, биз өзгөчө эч нерсе кылган жокпуз - биз жөн гана Go компилятору эмне кылаарын кайра чыгардык.
Тилекке каршы, компиляторду ассемблер тилинде жазылган функцияларыбызды киргизүүгө мажбурлай албайбыз. Go компиляторунда учурда мындай функция жок, бирок бир топ убакыттан бери аны кошуу өтүнүчү бар.
Ошондуктан ассемблер тилиндеги кичинекей функциялардан эч кандай пайда алуу мүмкүн эмес. Биз чоң функцияларды жазышыбыз керек, же жаңы математика/бит пакетин колдонушубуз керек, же ассемблер тилин айланып өтүшүбүз керек.
Эми функцияларыбыздын вектордук версияларын карап көрөлү.
Бул мисал үчүн мен AVX2ди колдонууну чечтим, ошондуктан биз 32 байттык бөлүктөрдө иштеген операцияларды колдонобуз. Коддун түзүлүшү скалярдык версияга абдан окшош: параметрлерди жүктөө, акысыз бөлүшүлгөн реестрди суроо ж.б.
Жаңылыктардын бири - кеңири вектордук операцияларда атайын кеңири регистрлер колдонулат. 32 байттык бөлүктөрдө булар Y префикси бар регистрлер. Мына ошондуктан коддон YMM() функциясын көрөсүз. Эгерде мен AVX-512ди 64 биттик бөлүктөр менен колдонуп жатсам, префикс Z болмок.
Экинчи жаңылык, мен циклды ачуу деп аталган оптималдаштырууну колдонууну чечтим, бул циклдин башына өтүүдөн мурун сегиз цикл операциясын кол менен жасоону билдирет. Бул оптималдаштыруу коддогу бутактардын санын азайтат жана жеткиликтүү акысыз реестрлердин саны менен чектелет.
Ооба, аткаруу жөнүндө эмне айтууга болот? Ал сулуу! Мыкты Go чечимине салыштырмалуу биз жети эсе ылдамдыкка жетиштик. Таасирдүү, туурабы?
Бирок бул ишке ашырууну AVX-512, алдын ала жүктөө же суроо пландоочу үчүн JIT (жөн эле өз убагында компилятор) колдонуу менен тездетсе болот. Бирок бул, албетте, өзүнчө баяндама үчүн тема.
Битмап индекстери менен көйгөйлөр
Эми биз Go'до битмап индексинин жөнөкөй ишке ашырылышын жана ассемблер тилинде бир топ жемиштүү ишке ашырууну карап чыккандан кийин, келгиле, акырында битмап индекстери эмне үчүн мынчалык сейрек колдонулганы жөнүндө сүйлөшөлү.
Эски кагаздар битмап индекстери менен үч көйгөйдү айтышат, бирок жаңыраак кагаздар жана мен алар мындан ары актуалдуу эмес деп ырасташат. Биз бул көйгөйлөрдүн ар бирине тереңдеп кирбей, үстүртөн карайбыз.
Жогорку кардиналдуулук проблемасы
Ошентип, бизге битмап индекстери кардиналдуулугу төмөн талаалар үчүн гана ылайыктуу, башкача айтканда, бир аз мааниге ээ (мисалы, гендердик же көздүн түсү) жана себеби мындай талаалардын кадимки көрүнүшү (бир мааниге бит) жогорку кардиналдуулук болгон учурда, ал өтө көп орун ээлейт жана андан тышкары, бул битмап индекстери начар (сейрек) толтурулат.
Кээде биз сандарды көрсөтүү үчүн колдонгон стандарттык сыяктуу башка өкүлчүлүктү колдонушубуз мүмкүн. Бирок баарын өзгөрткөн кысуу алгоритмдеринин пайда болушу болду. Акыркы ондогон жылдар бою окумуштуулар жана изилдөөчүлөр битмаптар үчүн кысуу алгоритмдердин көп санын ойлоп табышты. Алардын негизги артыкчылыгы - биттик операцияларды аткаруу үчүн биттик карталарды ачуунун кереги жок - биз кысылган биттик карталарда бит операцияларын түздөн-түз аткара алабыз.
Акыркы убакта гибриддик ыкмалар пайда боло баштады, мисалы, битмаптар. Алар бир эле учурда битмаптар үчүн үч түрдүү өкүлчүлүктү колдонушат - битмаптардын өздөрү, массивдер жана бит иштетүүлөр деп аталган - жана алардын ортосундагы балансты максималдуу аткаруу жана эстутум керектөөсүн азайтуу үчүн.
Сиз эң популярдуу тиркемелерден ызылдаган битмаптарды таба аласыз. Ар кандай программалоо тилдери үчүн көп сандагы ишке ашыруулар, анын ичинде Go үчүн үчтөн ашык ишке ашыруулар бар.
Бизге жогорку кардиналдуулук менен күрөшүүгө жардам бере турган дагы бир ыкма биннинг деп аталат. Элестетиңиз, сизде адамдын боюн чагылдырган талаа бар. Бийиктик - бул калкыма чекиттүү сан, бирок биз адамдар аны мындай деп ойлобойбуз. Биз үчүн 185,2 см менен 185,3 см бийиктиктин айырмасы жок.
Көрсө, биз окшош баалуулуктарды 1 см аралыкта топторго топтой алабыз.
Ошондой эле, биз өтө аз адамдардын бою 50 смден кыска жана 250 смден жогору экенин билсек, анда биз чексиз кардиналдуулуктагы талааны 200гө жакын чоңдуктагы талаага айланта алабыз.
Албетте, керек болсо, кийинчерээк кошумча чыпкалоо жүргүзө алабыз.
Жогорку өткөрүү жөндөмдүүлүгү көйгөйү
Битмап индекстеринин кийинки көйгөйү, аларды жаңыртуу абдан кымбат болушу мүмкүн.
Жүздөгөн башка сурамдар маалыматтарды издеп жатканда, маалымат базалары маалыматтарды жаңырта алышы керек. Бир убакта берилиштерге жетүү же башка бөлүшүү көйгөйлөрүн болтурбоо үчүн бизге кулпулар керек. Ал эми бир чоң кулпу бар жерде көйгөй бар - кулпу талашы, бул кулпу тоскоолдукка айланат.
Бул көйгөйдү чечүүгө же сындырып же версияланган индекстерди колдонуу менен айланып өтүүгө болот.
Sharding жөнөкөй жана белгилүү нерсе. Сиз битмап индексин башка маалыматтар сыяктуу бөлсөңүз болот. Бир чоң кулпунун ордуна, сиз бир топ кичинекей кулпуларды аласыз жана ошентип кулпу талашынан арыласыз.
Маселени чечүүнүн экинчи жолу - версияланган индекстерди колдонуу. Сизде издөө же окуу үчүн колдонгон индекстин бир нускасы жана жазуу же жаңыртуу үчүн колдонсоңуз болот. Жана белгилүү бир убакыттын ичинде бир жолу (мисалы, ар 100 мс же 500 мс) сиз аларды кайталайсыз жана алмаштырасыз. Албетте, бул ыкма сиздин колдонмоңуз бир аз артта калган издөө индексин иштете алган учурларда гана колдонулат.
Бул эки ыкманы бир эле учурда колдонсо болот: сизде майдаланган версияланган индекс болушу мүмкүн.
Дагы татаал суроолор
Растрлык индекстердин акыркы көйгөйү, бизге алар суроонун татаалыраак түрлөрүнө, мисалы, аралык сурамдарына ылайыктуу эместигин айтышууда.
Чынында эле, эгер сиз ойлонуп көрсөңүз, ЖАНА, ЖЕ, ж.б. сыяктуу бит операциялары "Мага түнү 200дөн 300 долларга чейинки бөлмөлөрдүн баасы менен мейманканаларды көрсөтүңүз" деген суроолорго анча ылайыктуу эмес.
Ар бир доллардын наркы боюнча жыйынтыктарды алып, аларды бит же операциясы менен айкалыштыруу жөнөкөй жана өтө акылсыз чечим болмок.
Бир аз жакшыраак чечим топтоштурууну колдонуу болмок. Мисалы, 50 доллардан турган топтордо. Бул биздин процессти 50 эсе тездетет.
Бирок, суроо-талаптын ушул түрү үчүн атайын түзүлгөн көрүнүштү колдонуу менен көйгөй оңой чечилет. Илимий эмгектерде ал диапазондо коддолгон бит карталары деп аталат.
Бул өкүлчүлүктө биз кандайдыр бир мааниге бир бит гана койбойбуз (мисалы, 200), бирок бул маанини жана бардыгын жогору коёбуз. 200 жана андан жогору. Ошол эле 300: 300 жана андан жогору. Жана башка.
Бул өкүлчүлүктү колдонуп, биз индексти эки жолу айланып өтүү менен ушундай издөө суроосуна жооп бере алабыз. Биринчиден, биз бөлмөнүн баасы аз же 300 доллар турган мейманканалардын тизмесин алабыз, андан кийин бөлмөнүн баасы аз же 199 доллар болгон мейманканаларды алып салабыз. Даяр.
Сиз таң каласыз, бирок битмап индекстерин колдонуу менен геосуралдар да мүмкүн. Бул сиздин координатыңызды геометриялык фигура менен курчап турган геометриялык өкүлчүлүктү колдонуу. Мисалы, Google'дан S2. Фигураны номерлөө мүмкүн болгон үч же андан көп кесилишкен сызыктар түрүндө көрсөтүүгө мүмкүн болушу керек. Мына ушундай жол менен биз геоквардиябызды бир нече суроого “ажыкка” айланта алабыз (бул номерленген сызыктар боюнча).
Даяр чечимдер
Мен сени бир аз кызыктырдым деп үмүттөнөм, эми сиздин арсеналыңызда дагы бир пайдалуу курал бар. Эгер сизге ушуга окшогон нерсе керек болсо, кайсы жолду издөө керектигин билесиз.
Бирок, нөлдөн баштап битмап индекстерин түзүү үчүн ар бир адамдын убактысы, чыдамдуулугу же ресурстары боло бербейт. Айрыкча өнүккөндөр, мисалы, SIMD колдонуу.
Бактыга жараша, сизге жардам бере турган бир нече даяр чечимдер бар.
Кыйкыраган бит карталары
Биринчиден, мен айтып өткөн ошол эле битмаптар китепканасы бар. Ал толук кандуу битмап индексин жасоо үчүн зарыл болгон бардык керектүү контейнерлерди жана бит операцияларын камтыйт.
Тилекке каршы, учурда Go ишке ашырууларынын эч бири SIMD колдонбойт, бул, мисалы, Go ишке ашыруулары C ишке караганда азыраак натыйжалуу дегенди билдирет.
Pilosa
Сизге жардам бере турган дагы бир продукт - бул Pilosa DBMS, ал чындыгында растрдык индекстерге гана ээ. Бул салыштырмалуу жаңы чечим, бирок ал чоң ылдамдыкта жүрөктөрдү багындырып жатат.
Pilosa ызылдаган бит карталарын ички түрдө колдонот жана сизге аларды колдонуу мүмкүнчүлүгүн берет, мен жогоруда айткан нерселердин бардыгын жөнөкөйлөтөт жана түшүндүрөт: топтоо, диапазондо коддолгон бит карталары, талаа түшүнүгү ж.б.
Келиңиз, сизге тааныш болгон суроого жооп берүү үчүн Pilosa колдонуунун мисалын карап көрөлү.
Мисал мурда көргөн нерсеге абдан окшош. Биз Pilosa серверине кардар түзөбүз, индексти жана керектүү талааларды түзөбүз, андан кийин биздин талааларды ыктымалдыктар менен кокус маалыматтар менен толтурабыз жана акырында тааныш суроону аткарабыз.
Андан кийин, биз "кымбат" талаасында ЭМЕСти колдонобуз, андан кийин натыйжаны (же ЖАНА аны) "терраса" талаасы жана "эзервдер" талаасы менен кесебиз. Акыр-аягы, биз акыркы жыйынтыкты алабыз.
Мен чындап эле жакынкы келечекте индекстин бул жаңы түрү MySQL жана PostgreSQL сыяктуу DBMS - битмап индекстеринде да пайда болот деп үмүттөнөм.
жыйынтыктоо
Уктай элек болсоңуз рахмат. Убакыттын чектелүүлүгүнө байланыштуу көп темаларга кыскача токтолууга туура келди, бирок баяндама пайдалуу, балким мотивация болду деп үмүттөнөм.
Bitmap индекстери жөнүндө билүү жакшы, атүгүл азыр аларга кереги жок. Алар куралдар кутучаңыздагы дагы бир курал болсун.
Биз Go үчүн ар кандай аткаруу ыкмаларын жана Go компилятору азырынча жакшы иштебеген нерселерди карап чыктык. Бирок бул ар бир Go программист үчүн абдан пайдалуу.
Мен сага айткым келгени ушул эле. Рахмат!
Source: www.habr.com