Bitmap ինդեքսները Go-ում. որոնել վայրի արագությամբ

ներածություն

Ես այս զեկույցը անգլերենով ներկայացրել եմ Մոսկվայում GopherCon Russia 2019 կոնֆերանսում, իսկ ռուսերեն՝ Նիժնի Նովգորոդում կայացած հանդիպման ժամանակ: Մենք խոսում ենք bitmap ինդեքսի մասին՝ ավելի քիչ տարածված, քան B-tree-ը, բայց ոչ պակաս հետաքրքիր: Համօգտագործում ձայնագրությունը կոնֆերանսի ելույթները անգլերենով և տեքստային սղագրությունները ռուսերենով:

Մենք կնայենք, թե ինչպես է աշխատում bitmap ինդեքսը, երբ այն ավելի լավ է, երբ այն ավելի վատ է, քան մյուս ինդեքսները, և որ դեպքերում այն ​​զգալիորեն ավելի արագ է, քան դրանք; Տեսնենք, թե որ հայտնի DBMS-ներն արդեն ունեն bitmap ինդեքսներ. Փորձենք գրել մերը Go-ում: Իսկ «դեսերտի համար» մենք կօգտագործենք պատրաստի գրադարաններ՝ ստեղծելու մեր սեփական գերարագ մասնագիտացված տվյալների բազան:

Ես իսկապես հուսով եմ, որ իմ աշխատանքները օգտակար և հետաքրքիր կլինեն ձեզ համար: Գնա՛

Ներածություն

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

Բարեւ բոլորին! Երեկոյան ժամը վեցն է, և մենք բոլորս գերհոգնած ենք: Հիանալի ժամանակ է խոսելու ձանձրալի տվյալների բազայի ինդեքսի տեսության մասին, այնպես չէ՞: Մի անհանգստացեք, ես այստեղ-այնտեղ կունենամ մի քանի տող սկզբնական կոդը: 🙂

Մի կողմ թողնենք բոլոր կատակները, զեկույցը լի է ինֆորմացիայով, և մենք շատ ժամանակ չունենք: Այսպիսով, եկեք սկսենք:

Այսօր ես կխոսեմ հետևյալի մասին.

• ինչ են ինդեքսները;
• ինչ է bitmap ինդեքսը;
• որտեղ է այն օգտագործվում և որտեղ ՉԻ օգտագործվում և ինչու.
• պարզ իրականացում Go-ում և մի փոքր պայքար կոմպիլյատորի հետ;
• մի փոքր ավելի քիչ պարզ, բայց շատ ավելի արդյունավետ իրականացում Go assembler-ում;
• bitmap ինդեքսների «խնդիրներ»;
• առկա իրականացումները։

Այսպիսով, ինչ են ինդեքսները:

Ցուցանիշը տվյալների առանձին կառուցվածք է, որը մենք պահպանում և թարմացնում ենք հիմնական տվյալներից բացի: Այն օգտագործվում է որոնումն արագացնելու համար։ Առանց ինդեքսների, որոնումը կպահանջի ամբողջությամբ անցնել տվյալների միջով (գործընթաց, որը կոչվում է ամբողջական սկանավորում), և այս գործընթացն ունի գծային ալգորիթմական բարդություն: Սակայն տվյալների բազաները սովորաբար պարունակում են հսկայական քանակությամբ տվյալներ, և գծային բարդությունը չափազանց դանդաղ է: Իդեալում, մենք կստանանք լոգարիթմական կամ հաստատուն:

Սա չափազանց բարդ թեմա է, որը լցված է նրբություններով և փոխզիջումներով, բայց տվյալների բազայի մշակման և հետազոտությունների տասնամյակների ընթացքում դիտելուց հետո ես պատրաստ եմ ասել, որ կան միայն մի քանի լայնորեն օգտագործվող մոտեցումներ տվյալների բազայի ինդեքսներ ստեղծելու համար:

Առաջին մոտեցումն է հիերարխիկորեն կրճատել որոնման տարածքը՝ բաժանելով որոնման տարածքը փոքր մասերի:

Մենք սովորաբար դա անում ենք՝ օգտագործելով տարբեր տեսակի ծառեր: Օրինակ կարող է լինել ձեր առանձնասենյակում գտնվող նյութերի մեծ տուփը, որը պարունակում է նյութերի ավելի փոքր տուփեր՝ բաժանված տարբեր թեմաների: Եթե ​​ձեզ անհրաժեշտ են նյութեր, դուք հավանաբար դրանք կփնտրեք մի տուփի մեջ, որտեղ գրված է «Նյութեր», այլ ոչ թե «Թխուկներ», այնպես չէ՞:

Երկրորդ մոտեցումը ցանկալի տարրը կամ տարրերի խումբն անմիջապես ընտրելն է: Մենք դա անում ենք հեշ քարտեզներում կամ հակադարձ ինդեքսներում: Հեշ-քարտեզների օգտագործումը շատ նման է նախորդ օրինակին, բայց տուփերի տուփի փոխարեն ձեր պահարանում ունեք վերջնական իրերի մի փունջ փոքրիկ տուփեր:

Երրորդ մոտեցումը որոնման անհրաժեշտությունը վերացնելն է։ Մենք դա անում ենք Bloom ֆիլտրերի կամ կուկու ֆիլտրերի միջոցով: Առաջինները պատասխան են տալիս ակնթարթորեն՝ փրկելով ձեզ փնտրտուքից:

Վերջին մոտեցումն այն է, որ լիովին օգտագործենք այն ամբողջ ուժը, որը մեզ տալիս է ժամանակակից սարքավորումները: Սա հենց այն է, ինչ մենք անում ենք bitmap ինդեքսներում: Այո, դրանք օգտագործելիս երբեմն անհրաժեշտ է անցնել ամբողջ ինդեքսը, բայց մենք դա անում ենք գերարդյունավետ:

Ինչպես ասացի, տվյալների բազայի ինդեքսների թեման ընդարձակ է և լի փոխզիջումներով: Սա նշանակում է, որ երբեմն մենք կարող ենք օգտագործել մի քանի մոտեցումներ միաժամանակ. եթե մեզ անհրաժեշտ է ավելի արագացնել որոնումը, կամ եթե մեզ անհրաժեշտ է ծածկել որոնման բոլոր հնարավոր տեսակները:

Այսօր ես կխոսեմ դրանցից ամենաքիչ հայտնի մոտեցման՝ bitmap ինդեքսների մասին։

Ո՞վ եմ ես, որ խոսեմ այս թեմայով:

Ես աշխատում եմ որպես թիմի ղեկավար Badoo-ում (գուցե դուք ավելի ծանոթ եք մեր մյուս արտադրանքին՝ Bumble-ին): Մենք արդեն ունենք ավելի քան 400 միլիոն օգտատեր ամբողջ աշխարհում և բազմաթիվ գործառույթներ, որոնք ընտրում են նրանց համար լավագույն համընկնում: Մենք դա անում ենք՝ օգտագործելով հատուկ ծառայություններ, ներառյալ bitmap ինդեքսները:

Այսպիսով, ինչ է bitmap ինդեքսը:

Bitmap ինդեքսները, ինչպես ենթադրում է անունը, օգտագործում են bitmap կամ bitsets որոնման ինդեքսը իրականացնելու համար: Թռչնի հայացքից այս ինդեքսը բաղկացած է մեկ կամ մի քանի նման բիթքարտեզներից, որոնք ներկայացնում են ցանկացած էություն (օրինակ՝ մարդիկ) և դրանց հատկությունները կամ պարամետրերը (տարիքը, աչքերի գույնը և այլն), և ալգորիթմը, որն օգտագործում է բիթային գործողություններ (AND, OR, NOT): ) որոնման հարցումին պատասխանելու համար։

Մեզ ասվում է, որ bitmap ինդեքսները լավագույնս համապատասխանում են և շատ արդյունավետ են այն դեպքերի համար, երբ կան որոնումներ, որոնք միավորում են հարցումները ցածր կարդինալության բազմաթիվ սյունակներում (կարծում ենք՝ «աչքի գույնը» կամ «ամուսնական կարգավիճակը» ընդդեմ «քաղաքի կենտրոնից հեռավորությունը»): Բայց ես ավելի ուշ ցույց կտամ, որ դրանք լավ են աշխատում նաև բարձր կարդինալության սյունակների համար:

Եկեք նայենք bitmap ինդեքսի ամենապարզ օրինակին:

Պատկերացրեք, որ մենք ունենք մոսկովյան ռեստորանների ցուցակ, որոնք ունեն հետևյալ երկուական հատկությունները.

• մետրոյի մոտ;
• կա մասնավոր ավտոկայանատեղի;
• ունի պատշգամբ (ունի պատշգամբ);
• կարող եք սեղան պատվիրել (ընդունում է վերապահումներ);
• հարմար է բուսակերների համար (vegan friendly);
• թանկ (թանկ):

Եկեք յուրաքանչյուր ռեստորանի տանք 0-ից սկսած հաջորդական համարը և հատկացնենք հիշողություն 6 բիթքարտեզի համար (մեկը յուրաքանչյուր հատկանիշի համար): Այնուհետև մենք կհամալրենք այս բիթքարտեզները՝ կախված նրանից, թե ռեստորանը ունի այս հատկությունը, թե ոչ: Եթե ​​ռեստորանը 4-ն ունի պատշգամբ, ապա «ունի պատշգամբ» քարտեզի թիվ 4 բիթը կդրվի 1-ի (եթե պատշգամբ չկա, ապա 0-ի):

Այժմ մենք ունենք հնարավոր ամենապարզ bitmap ինդեքսը, և մենք կարող ենք այն օգտագործել՝ պատասխանելու այնպիսի հարցումներին, ինչպիսիք են.

• «Ցույց տուր ինձ բուսակերների համար հարմար ռեստորաններ»;
• «Ցույց տվեք ինձ պատշգամբով էժան ռեստորաններ, որտեղ կարող եք սեղան պատվիրել»։

Ինչպե՞ս: Եկեք նայենք: Առաջին խնդրանքը շատ պարզ է. Մեզ անհրաժեշտ է միայն վերցնել «բուսակերների համար հարմար» բիթքարտեզը և այն վերածել ռեստորանների ցանկի, որոնց բիթերը բացահայտված են:


Երկրորդ խնդրանքը մի փոքր ավելի բարդ է. Մենք պետք է օգտագործենք NOT bitmap-ը «թանկ» bitmap-ի վրա, որպեսզի ստանանք էժան ռեստորանների ցուցակը, այնուհետև AND այն «կարո՞ղ եմ սեղան պատվիրել» bitmap-ով և AND-ի արդյունքը՝ « There is a veranda» bitmap-ով: Ստացված bitmap-ը կպարունակի մեր բոլոր չափանիշներին համապատասխանող հաստատությունների ցանկ: Այս օրինակում սա միայն Յունոստ ռեստորանն է:


Շատ տեսություններ կան, բայց մի անհանգստացեք, մենք շատ շուտով կտեսնենք կոդը:

Որտե՞ղ են օգտագործվում bitmap ինդեքսները:

Եթե ​​Google-ում եք bitmap ինդեքսներ, ապա պատասխանների 90%-ը այս կամ այն ​​կերպ կապված կլինի Oracle DB-ի հետ։ Բայց մյուս DBMS-ները, հավանաբար, նույնպես աջակցում են նման հիանալի բանի, չէ՞: Իրականում ոչ:

Անցնենք հիմնական կասկածյալների ցանկը։

MySQL-ը դեռ չի աջակցում bitmap ինդեքսներին, բայց կա առաջարկ, որն առաջարկում է ավելացնել այս տարբերակը (https://dev.mysql.com/worklog/task/?id=1524).

PostgreSQL-ը չի աջակցում bitmap ինդեքսներին, բայց օգտագործում է պարզ բիթքարտեզներ և բիթային գործողություններ՝ որոնման արդյունքները մի քանի այլ ինդեքսների մեջ համատեղելու համար:

Tarantool-ն ունի bitset ինդեքսներ և աջակցում է դրանց վրա պարզ որոնումներ:

Redis-ն ունի պարզ բիտ դաշտեր (https://redis.io/commands/bitfield) առանց դրանք որոնելու հնարավորության։

MongoDB-ն դեռ չի աջակցում bitmap ինդեքսներին, բայց կա նաև առաջարկ, որն առաջարկում է ավելացնել այս տարբերակը https://jira.mongodb.org/browse/SERVER-1723

Elasticsearch-ը ներսում օգտագործում է բիթքարտեզներ (https://www.elastic.co/blog/frame-of-reference-and-roaring-bitmaps).

• Բայց մեր տանը նոր հարեւան է հայտնվել՝ Փիլոսան։ Սա Go-ում գրված նոր ոչ հարաբերական տվյալների բազա է: Այն պարունակում է միայն bitmap ինդեքսներ և ամեն ինչ հիմնավորում է դրանց վրա: Մենք դրա մասին կխոսենք մի փոքր ուշ:

Իրականացում Go-ում

Բայց ինչու են bitmap ինդեքսները այդքան հազվադեպ օգտագործվում: Նախքան այս հարցին պատասխանելը, ես կցանկանայի ձեզ ցույց տալ, թե ինչպես կարելի է իրականացնել շատ պարզ bitmap ինդեքս Go-ում:

Bitmaps-ը, ըստ էության, ընդամենը տվյալների կտոր է: Go-ում եկեք դրա համար օգտագործենք բայթերի հատվածներ:

Մենք ունենք մեկ բիթքարտեզ մեկ ռեստորանի հատկանիշի համար, և bitmap-ի յուրաքանչյուր բիթ ցույց է տալիս, թե կոնկրետ ռեստորանն ունի այս հատկությունը, թե ոչ:

Մեզ անհրաժեշտ կլինի երկու օգնական գործառույթ: Մեկը կօգտագործվի մեր bitmaps-ը պատահական տվյալներով լրացնելու համար: Պատահական, բայց որոշակի հավանականությամբ, որ ռեստորանն ունի յուրաքանչյուր գույք։ Օրինակ, ես կարծում եմ, որ Մոսկվայում շատ քիչ ռեստորաններ կան, որտեղ չի կարելի սեղան պատվիրել, և ինձ թվում է, որ հաստատությունների մոտ 20%-ը հարմար է բուսակերների համար։

Երկրորդ գործառույթը կվերածի bitmap-ը ռեստորանների ցանկի:


«Ցույց տուր ինձ էժան ռեստորաններ, որոնք ունեն պատշգամբ և կարող են ամրագրումներ կատարել» հարցին պատասխանելու համար մեզ անհրաժեշտ է երկու բիթային գործողություն՝ ՈՉ և ԵՎ:

Մենք կարող ենք մի փոքր պարզեցնել մեր կոդը՝ օգտագործելով ավելի բարդ ԵՎ ՈՉ օպերատորը։

Մենք ունենք գործառույթներ այս գործողություններից յուրաքանչյուրի համար: Երկուսն էլ անցնում են շերտերով, յուրաքանչյուրից վերցնում են համապատասխան տարրերը, միացնում են մի փոքր գործողությամբ և ստացված շերտի մեջ դնում արդյունքը։

Եվ հիմա մենք կարող ենք օգտագործել մեր bitmaps-ը և գործառույթները որոնման հարցումին պատասխանելու համար:

Արդյունավետությունն այնքան էլ բարձր չէ, թեև գործառույթները շատ պարզ են, և մենք շատ գումար ենք խնայել՝ չվերադարձնելով ստացված նոր հատվածը ամեն անգամ, երբ ֆունկցիան կանչվել է:

pprof-ի հետ մի փոքր պրոֆիլավորում անելուց հետո ես նկատեցի, որ Go կոմպիլյատորին բացակայում է մեկ շատ պարզ, բայց շատ կարևոր օպտիմալացում՝ ֆունկցիայի ներդիրում:

Փաստն այն է, որ Go կոմպիլյատորը ահավոր վախենում է օղակներից, որոնք անցնում են կտորների միջով և կտրականապես հրաժարվում են նման օղակներ պարունակող գործառույթներից:

Բայց ես չեմ վախենում և կարող եմ խաբել կոմպիլյատորին՝ օգտագործելով goto-ն օղակի փոխարեն, ինչպես հին լավ ժամանակներում:

Եվ, ինչպես տեսնում եք, այժմ կոմպիլյատորը ուրախությամբ կներդնի մեր գործառույթը: Արդյունքում մեզ հաջողվում է խնայել մոտ 2 միկրովայրկյան։ Վատ չէ!

Երկրորդ շիշը հեշտ է տեսնել, եթե ուշադիր նայեք հավաքի արդյունքին: Կազմողն ավելացրել է հատվածի սահմանի ստուգում հենց մեր ամենաթեժ օղակի ներսում: Փաստն այն է, որ Go-ն անվտանգ լեզու է, կոմպիլյատորը վախենում է, որ իմ երեք արգումենտները (երեք շերտ) տարբեր չափերի են։ Ի վերջո, այդ ժամանակ կլինի այսպես կոչված բուֆերային արտահոսքի առաջացման տեսական հնարավորություն։

Եկեք հանգստացնենք կոմպիլյատորին՝ ցույց տալով, որ բոլոր հատվածները նույն չափի են: Մենք կարող ենք դա անել՝ ավելացնելով պարզ ստուգում մեր ֆունկցիայի սկզբում:

Տեսնելով դա՝ կոմպիլյատորը ուրախությամբ բաց է թողնում ստուգումը, և մենք վերջում խնայում ենք ևս 500 նանվայրկյան:

Մեծ դահիճներ

Լավ, մենք կարողացանք սեղմել որոշ կատարողականություն մեր պարզ ներդրումից, բայց այս արդյունքն իրականում շատ ավելի վատ է, քան հնարավոր է ներկայիս սարքաշարի դեպքում:

Այն ամենը, ինչ մենք անում ենք, բիթային գործողություններ են, և մեր պրոցեսորները դրանք կատարում են շատ արդյունավետ: Բայց, ցավոք, մենք մեր պրոցեսորին «սնուցում ենք» շատ փոքր աշխատանքով։ Մեր գործառույթները կատարում են գործողություններ բայթ առ բայթ հիմունքներով: Մենք կարող ենք շատ հեշտությամբ կսմթել մեր կոդը, որպեսզի աշխատի 8 բայթանոց հատվածների հետ՝ օգտագործելով UInt64 հատվածները:

Ինչպես տեսնում եք, այս փոքր փոփոխությունը ութ անգամ արագացրեց մեր ծրագիրը՝ մեծացնելով խմբաքանակի չափը ութ անգամ: Շահույթը կարելի է ասել գծային է:

Իրականացում անսամբլերում

Բայց սա դեռ վերջը չէ։ Մեր պրոցեսորները կարող են աշխատել 16, 32 և նույնիսկ 64 բայթանոց կտորներով: Նման «լայն» գործողությունները կոչվում են մեկ հրահանգի բազմակի տվյալներ (SIMD; մեկ հրահանգ, շատ տվյալներ), իսկ ծածկագրի փոխակերպման գործընթացը, որպեսզի այն օգտագործի նման գործողություններ, կոչվում է վեկտորացում:

Ցավոք սրտի, Go կոմպիլյատորը հեռու է վեկտորացման գերազանց լինելուց: Ներկայումս Go կոդի վեկտորիզացիայի միակ միջոցը այս գործողությունները ձեռքով վերցնելն ու տեղադրելն է՝ օգտագործելով Go assembler:

Գնա հավաքողը տարօրինակ գազան է: Դուք հավանաբար գիտեք, որ անսամբլի լեզուն մի բան է, որը մեծապես կապված է այն համակարգչի ճարտարապետության հետ, որի համար գրում եք, բայց Go-ում դա այդպես չէ: Go assembler-ը ավելի շատ նման է IRL-ի (միջանկյալ ներկայացման լեզու) կամ միջանկյալ լեզվի. այն գործնականում անկախ հարթակից է: Ռոբ Պայքը հիանալի ելույթ ունեցավ հաշվետվություն այս թեմայով մի քանի տարի առաջ Դենվերի GopherCon-ում:

Բացի այդ, Go-ն օգտագործում է անսովոր Plan 9 ձևաչափ, որը տարբերվում է ընդհանուր ընդունված AT&T և Intel ձևաչափերից։

Կարելի է վստահորեն ասել, որ Go assembler-ը ձեռքով գրելը ամենազվարճալի չէ:

Բայց, բարեբախտաբար, արդեն կան երկու բարձր մակարդակի գործիքներ, որոնք օգնում են մեզ գրել Go assembler՝ PeachPy և avo: Երկու կոմունալ ծառայությունները ստեղծում են Go assembler ավելի բարձր մակարդակի կոդից, որը գրված է համապատասխանաբար Python-ով և Go-ով:

Այս կոմունալ ծառայությունները պարզեցնում են այնպիսի բաներ, ինչպիսիք են գրանցման տեղաբաշխումը, գրելու հանգույցները և ընդհանուր առմամբ հեշտացնում են Go-ում հավաքների ծրագրավորման աշխարհ մտնելու գործընթացը:

Մենք կօգտագործենք avo, այնպես որ մեր ծրագրերը կլինեն գրեթե սովորական Go ծրագրեր:

Ահա թե ինչ տեսք ունի avo ծրագրի ամենապարզ օրինակը։ Մենք ունենք main() ֆունկցիա, որն իր ներսում սահմանում է Add() ֆունկցիան, որի իմաստը երկու թվեր գումարելն է։ Այստեղ կան օգնական գործառույթներ՝ ըստ անվան պարամետրեր ստանալու և անվճար և հարմար պրոցեսորային ռեգիստրներից մեկը ստանալու համար: Յուրաքանչյուր պրոցեսորի գործողություն ունի համապատասխան գործառույթ avo-ում, ինչպես երևում է ADDQ-ում: Վերջապես, մենք տեսնում ենք օգնական ֆունկցիա՝ ստացված արժեքը պահելու համար:

Կանչելով go generate՝ մենք կգործարկենք ծրագիրը avo-ում և արդյունքում կստեղծվի երկու ֆայլ.

• add.s՝ ստացված կոդով Go assembler-ում;
• stub.go ֆունկցիայի վերնագրերով երկու աշխարհները միացնելու համար՝ Go և assembler:

Այժմ, երբ մենք տեսանք, թե ինչ և ինչպես է անում avo-ն, եկեք նայենք մեր գործառույթներին: Ես իրականացրել եմ ֆունկցիաների և՛ սկալյար, և՛ վեկտորային (SIMD) տարբերակները:

Եկեք նախ նայենք սկալյար տարբերակներին:

Ինչպես նախորդ օրինակում, մենք խնդրում ենք անվճար և վավեր ընդհանուր նշանակության ռեգիստր, մենք կարիք չունենք արգումենտների համար հաշվարկել օֆսեթները և չափերը: Ավոն այս ամենն անում է մեզ համար։

Մենք նախկինում օգտագործում էինք պիտակներ և goto (կամ jumps)՝ կատարողականությունը բարելավելու և Go կոմպիլյատորին խաբելու համար, բայց հիմա մենք դա անում ենք սկզբից: Բանն այն է, որ ցիկլերը ավելի բարձր մակարդակի հասկացություն են: Ասեմբլերում մենք ունենք միայն պիտակներ և թռիչքներ:

Մնացած ծածկագիրը պետք է արդեն ծանոթ և հասկանալի լինի: Մենք ընդօրինակում ենք հանգույցը պիտակներով և թռիչքներով, վերցնում ենք տվյալների փոքր կտոր մեր երկու կտորներից, միացնում դրանք բիթային գործողությամբ (ԵՎ ՈՉ այս դեպքում) և այնուհետև արդյունքը դնում ենք ստացված հատվածի մեջ: Բոլորը.

Ահա թե ինչ տեսք ունի վերջնական assembler կոդը: Մենք ստիպված չէինք հաշվարկել հաշվանցումները և չափերը (ընդգծված կանաչով) կամ հետևել օգտագործված գրանցամատյաններին (ընդգծված կարմիրով):

Եթե ​​համեմատենք assembly լեզվի կատարողականը Go-ում լավագույն կատարման հետ, ապա կտեսնենք, որ դա նույնն է։ Եվ սա սպասելի է։ Ի վերջո, մենք ոչ մի հատուկ բան չենք արել. մենք պարզապես վերարտադրել ենք այն, ինչ կանի Go կոմպիլյատորը:

Ցավոք, մենք չենք կարող ստիպել կոմպիլյատորին ներդնել մեր գործառույթները, որոնք գրված են անսամբլի լեզվով: Go կոմպիլյատորը ներկայումս չունի նման հատկություն, չնայած բավական երկար ժամանակ է, ինչ այն ավելացնելու խնդրանք կա։

Ահա թե ինչու հնարավոր չէ որևէ օգուտ քաղել անսամբլի լեզվով փոքր գործառույթներից: Պետք է կա՛մ մեծ ֆունկցիաներ գրենք, կա՛մ օգտագործենք math/bits նոր փաթեթը, կա՛մ շրջանցենք ասեմբլերի լեզուն։

Այժմ նայենք մեր գործառույթների վեկտորային տարբերակներին:

Այս օրինակի համար ես որոշեցի օգտագործել AVX2, այնպես որ մենք կօգտագործենք գործողություններ, որոնք գործում են 32 բայթանոց հատվածների վրա: Կոդի կառուցվածքը շատ նման է սկալյար տարբերակին՝ բեռնման պարամետրեր, անվճար ընդհանուր ռեգիստր խնդրելու և այլն։

Նորարարություններից մեկն այն է, որ ավելի լայն վեկտորային գործողություններում օգտագործվում են հատուկ լայն ռեգիստրներ: 32 բայթանոց հատվածների դեպքում դրանք ռեգիստրներ են՝ Y-ով նախածանցով: Ահա թե ինչու եք կոդի մեջ տեսնում YMM() ֆունկցիան: Եթե ​​ես օգտագործեի AVX-512-ը 64-բիթանոց հատվածներով, ապա նախածանցը կլիներ Z:

Երկրորդ նորամուծությունն այն է, որ ես որոշեցի օգտագործել օպտիմիզացիա, որը կոչվում է «loop unrolling», որը նշանակում է ձեռքով կատարել ութ օղակի գործողություն՝ նախքան հանգույցի սկիզբը ցատկելը: Այս օպտիմիզացումը նվազեցնում է կոդում մասնաճյուղերի թիվը և սահմանափակվում է հասանելի անվճար գրանցումների քանակով:

Դե, իսկ կատարման մասին: Նա գեղեցիկ է! Մենք հասել ենք մոտ յոթ անգամ արագության՝ համեմատած լավագույն Go լուծման հետ: Տպավորիչ է, չէ՞:

Բայց նույնիսկ այս իրականացումը կարող է պոտենցիալ արագացվել՝ օգտագործելով AVX-512, նախնական առբերում կամ JIT (ճիշտ ժամանակին կազմող) հարցումների ժամանակացույցի համար: Բայց սա իհարկե առանձին զեկույցի թեմա է։

Bitmap ինդեքսների հետ կապված խնդիրներ

Այժմ, երբ մենք արդեն դիտարկել ենք bitmap ինդեքսի պարզ իրականացումը Go-ում և շատ ավելի արդյունավետը անսամբլի լեզվով, եկեք վերջապես խոսենք այն մասին, թե ինչու են bitmap ինդեքսներն այդքան հազվադեպ օգտագործվում:

Ավելի հին փաստաթղթերը նշում են bitmap ինդեքսների հետ կապված երեք խնդիր, բայց ավելի նոր փաստաթղթերը, և ես պնդում եմ, որ դրանք այլևս տեղին չեն: Մենք չենք խորասուզվի այս խնդիրներից յուրաքանչյուրի մեջ, այլ մակերեսորեն կնայենք դրանց:

Բարձր կարդինալության խնդիրը

Այսպիսով, մեզ ասում են, որ bitmap ինդեքսները հարմար են միայն ցածր կարդինալություն ունեցող դաշտերի համար, այսինքն՝ նրանց, որոնք ունեն քիչ արժեքներ (օրինակ՝ սեռը կամ աչքի գույնը), և պատճառն այն է, որ նման դաշտերի սովորական ներկայացումը (մեկ. բիթ մեկ արժեքի դեպքում) բարձր կարդինալության դեպքում այն ​​չափազանց շատ տեղ կզբաղեցնի, և ավելին, այս bitmap ինդեքսները վատ (հազվադեպ) կլրացվեն:


Երբեմն մենք կարող ենք օգտագործել այլ ներկայացում, ինչպիսին է ստանդարտը, որը մենք օգտագործում ենք թվերը ներկայացնելու համար: Սակայն սեղմման ալգորիթմների հայտնվելն էր, որ փոխեց ամեն ինչ: Անցած տասնամյակների ընթացքում գիտնականներն ու հետազոտողները եկել են bitmaps-ի համար սեղմման մեծ թվով ալգորիթմների: Նրանց հիմնական առավելությունն այն է, որ բիթային գործողություններ կատարելու համար bitmaps-ը ապասեղմելու կարիք չկա. մենք կարող ենք բիթային գործողություններ կատարել անմիջապես սեղմված bitmaps-ի վրա:

Վերջերս հիբրիդային մոտեցումներ են սկսել ի հայտ գալ, ինչպիսիք են մռնչացող բիթքարտեզները: Նրանք միաժամանակ օգտագործում են երեք տարբեր ներկայացումներ բիթքարտեզների համար՝ բիթքարտեզներ, զանգվածներ և այսպես կոչված բիթային գործարկումներ, և հավասարակշռում են դրանց միջև՝ առավելագույնի հասցնելու կատարումը և նվազագույնի հասցնելու հիշողության սպառումը:

Դուք կարող եք գտնել մռնչող բիթքարտեզներ ամենահայտնի հավելվածներում: Արդեն իսկ կան հսկայական թվով իրականացումներ ծրագրավորման լեզուների լայն տեսականիով, ներառյալ ավելի քան երեք իրականացում Go-ի համար:

Մեկ այլ մոտեցում, որը կարող է օգնել մեզ հաղթահարել բարձր կարդինալությունը, կոչվում է բինինգ: Պատկերացրեք, որ դուք ունեք դաշտ, որը ներկայացնում է մարդու հասակը: Բարձրությունը լողացող կետով թիվ է, բայց մենք՝ մարդիկս, այդպես չենք մտածում: Մեզ համար տարբերություն չկա 185,2 սմ և 185,3 սմ հասակի միջև։

Ստացվում է, որ մենք կարող ենք խմբավորել նմանատիպ արժեքները խմբերի 1 սմ-ի սահմաններում:

Եվ եթե մենք նաև գիտենք, որ շատ քչերն են 50 սմ-ից ցածր և 250 սմ-ից բարձր, ապա մենք կարող ենք ըստ էության անսահման կարդինալությամբ դաշտը վերածել մոտ 200 արժեքի կարդինալություն ունեցող դաշտի:

Իհարկե, անհրաժեշտության դեպքում կարող ենք հետո լրացուցիչ զտում անել։

Բարձր թողունակության խնդիր

Bitmap ինդեքսների հետ կապված հաջորդ խնդիրն այն է, որ դրանց թարմացումը կարող է շատ թանկ արժենալ:

Տվյալների բազաները պետք է կարողանան թարմացնել տվյալները, մինչ հնարավոր է հարյուրավոր այլ հարցումներ որոնեն տվյալները: Մեզ կողպեքներ են պետք՝ տվյալների միաժամանակ հասանելիության կամ փոխանակման այլ խնդիրներից խուսափելու համար: Իսկ որտեղ կա մեկ մեծ կողպեք, կա խնդիր՝ կողպեքի վիճաբանություն, երբ այս կողպեքը դառնում է խցան:

Այս խնդիրը կարող է լուծվել կամ շրջանցվել՝ օգտագործելով sharding կամ օգտագործելով տարբերակված ինդեքսներ:

Sharding-ը պարզ ու հայտնի բան է։ Դուք կարող եք բաժանել բիթքարտեզի ինդեքսը, ինչպես ցանկացած այլ տվյալ: Մեկ մեծ կողպեքի փոխարեն դուք կստանաք մի փունջ փոքր կողպեքներ և այդպիսով կազատվեք կողպեքի վեճից:

Խնդիրը լուծելու երկրորդ ճանապարհը տարբերակված ինդեքսների օգտագործումն է: Դուք կարող եք ունենալ ինդեքսի մեկ օրինակ, որն օգտագործում եք որոնման կամ կարդալու համար, և մեկը, որն օգտագործում եք գրելու կամ թարմացնելու համար: Եվ որոշակի ժամանակահատվածում մեկ անգամ (օրինակ՝ 100 ms կամ 500 ms-ն մեկ անգամ) դրանք կրկնօրինակում եք և փոխանակում: Իհարկե, այս մոտեցումը կիրառելի է միայն այն դեպքերում, երբ ձեր դիմումը կարող է կարգավորել մի փոքր ուշացած որոնման ինդեքս:

Այս երկու մոտեցումները կարող են օգտագործվել միաժամանակ. կարող եք ունենալ բեկորային տարբերակված ինդեքս:

Ավելի բարդ հարցումներ

Bitmap ինդեքսների հետ կապված վերջնական խնդիրն այն է, որ մեզ ասում են, որ դրանք այնքան էլ հարմար չեն հարցումների ավելի բարդ տեսակների համար, ինչպիսիք են span հարցումները:

Իսկապես, եթե մտածեք դրա մասին, ապա բիթային գործողությունները, ինչպիսիք են AND, OR և այլն, այնքան էլ հարմար չեն a la հարցումների համար.

Միամիտ և շատ անխոհեմ լուծում կլինի արդյունքները վերցնել յուրաքանչյուր դոլարի արժեքի համար և միավորել դրանք բիթային ԿԱՄ գործողության հետ:

Մի փոքր ավելի լավ լուծում կլինի խմբավորման օգտագործումը: Օրինակ՝ 50 դոլարանոց խմբերով։ Սա կարագացնի մեր գործընթացը 50 անգամ:

Բայց խնդիրը նույնպես հեշտությամբ լուծվում է՝ օգտագործելով հատուկ այս տեսակի հարցումների համար ստեղծված տեսքը: Գիտական ​​աշխատություններում այն ​​կոչվում է տիրույթով կոդավորված bitmaps:

Այս ներկայացման մեջ մենք ոչ միայն մեկ բիթ ենք սահմանում ինչ-որ արժեքի համար (օրինակ՝ 200), այլ սահմանում ենք այս արժեքը և ամեն ինչ ավելի բարձր: 200 և ավելի: Նույնը 300-ի համար՝ 300 և ավելի: Եվ այսպես շարունակ։

Օգտագործելով այս ներկայացումը, մենք կարող ենք պատասխանել այս տեսակի որոնման հարցումին՝ ընդամենը երկու անգամ անցնելով ինդեքսը: Սկզբում մենք կստանանք հյուրանոցների ցանկ, որտեղ սենյակն արժե ավելի քիչ կամ $300, իսկ հետո կհեռացնենք այնտեղից, որտեղ սենյակի արժեքը ավելի քիչ է կամ $199։ Պատրաստ.

Դուք կզարմանաք, բայց նույնիսկ geoqueries հնարավոր են օգտագործելով bitmap ինդեքսները: Խնդիրն այն է, որ օգտագործեք երկրաչափական պատկեր, որը շրջապատում է ձեր կոորդինատը երկրաչափական պատկերով: Օրինակ, S2-ը Google-ից: Նկարը պետք է հնարավոր լինի ներկայացնել երեք կամ ավելի հատվող գծերի տեսքով, որոնք կարող են համարակալվել: Այս կերպ մենք կարող ենք մեր աշխարհագրությունը վերածել մի քանի հարցումների «բացի երկայնքով» (այս համարակալված տողերի երկայնքով):

Պատրաստի լուծումներ

Հուսով եմ, որ ձեզ մի փոքր հետաքրքրեց, և այժմ ձեր զինանոցում ունեք ևս մեկ օգտակար գործիք: Եթե ​​ձեզ երբևէ անհրաժեշտ լինի նման բան անել, դուք կիմանաք, թե որ կողմը պետք է նայեք:

Այնուամենայնիվ, ոչ բոլորն ունեն ժամանակ, համբերություն կամ ռեսուրսներ զրոյից bitmap ինդեքսներ ստեղծելու համար: Հատկապես ավելի առաջադեմները, օրինակ՝ օգտագործելով SIMD:

Բարեբախտաբար, կան մի քանի պատրաստի լուծումներ, որոնք կօգնեն ձեզ:

Մռնչյուն բիթքարտեզներ

Նախ, կա նույն աղմկոտ bitmaps գրադարանը, որի մասին ես արդեն խոսեցի: Այն պարունակում է բոլոր անհրաժեշտ բեռնարկղերը և բիթային գործողությունները, որոնք ձեզ անհրաժեշտ կլինեն ամբողջական բիթքարտեզի ինդեքս ստեղծելու համար:

Ցավոք, այս պահին Go-ի ներդրումներից և ոչ մեկը չի օգտագործում SIMD, ինչը նշանակում է, որ Go-ի իրականացումները ավելի քիչ արդյունավետ են, քան C-ի, օրինակ:

Փիլոսա

Մեկ այլ արտադրանք, որը կարող է օգնել ձեզ, Pilosa DBMS-ն է, որն իրականում ունի միայն bitmap ինդեքսներ: Սա համեմատաբար նոր լուծում է, բայց այն մեծ արագությամբ շահում է սրտերը:

Pilosa-ն օգտագործում է աղմկոտ բիթքարտեզներ և հնարավորություն է տալիս օգտագործել դրանք, պարզեցնում և բացատրում է այն ամենը, ինչի մասին ես խոսեցի վերևում.

Եկեք արագ նայենք Pilosa-ի օգտագործման օրինակին՝ ձեզ արդեն ծանոթ հարցին պատասխանելու համար:

Օրինակը շատ նման է նախկինում տեսածին։ Մենք ստեղծում ենք հաճախորդ Pilosa սերվերում, ստեղծում ենք ինդեքս և անհրաժեշտ դաշտեր, այնուհետև մեր դաշտերը լրացնում ենք պատահական տվյալներով՝ հավանականություններով և, վերջապես, կատարում ծանոթ հարցումը:

Դրանից հետո մենք օգտագործում ենք NOT-ը «թանկ» դաշտում, ապա արդյունքը (կամ այն) հատում ենք «տեռաս» դաշտի և «վերապահումներ» դաշտի հետ։ Եվ վերջապես մենք ստանում ենք վերջնական արդյունքը։

Ես իսկապես հուսով եմ, որ տեսանելի ապագայում այս նոր տեսակի ինդեքսը կհայտնվի նաև DBMS-ներում, ինչպիսիք են MySQL և PostgreSQL - bitmap ինդեքսները:

Ամփոփում

Եթե ​​դեռ չեք քնել, շնորհակալություն։ Ստիպված եղա հակիրճ անդրադառնալ բազմաթիվ թեմաների սահմանափակ ժամանակի պատճառով, բայց հուսով եմ, որ զրույցը օգտակար էր և գուցե նույնիսկ մոտիվացնող:

Bitmap ինդեքսների մասին լավ է իմանալ, նույնիսկ եթե դրանք հիմա ձեզ հարկավոր չեն: Թող դրանք լինեն ևս մեկ գործիք ձեր գործիքատուփում:

Մենք դիտարկել ենք Go-ի կատարման տարբեր հնարքներ և այնպիսի բաներ, որոնք Go կոմպիլյատորը դեռ այնքան էլ լավ չի կառավարում: Բայց սա բացարձակապես օգտակար է իմանալ Go-ի յուրաքանչյուր ծրագրավորողի համար:

Դա այն ամենն է, ինչ ես ուզում էի ձեզ ասել: Շնորհակալություն!

Source: www.habr.com