ներածություն
Ես այս զեկույցը անգլերենով ներկայացրել եմ Մոսկվայում GopherCon Russia 2019 կոնֆերանսում, իսկ ռուսերեն՝ Նիժնի Նովգորոդում կայացած հանդիպման ժամանակ: Մենք խոսում ենք bitmap ինդեքսի մասին՝ ավելի քիչ տարածված, քան B-tree-ը, բայց ոչ պակաս հետաքրքիր: Համօգտագործում
Մենք կնայենք, թե ինչպես է աշխատում bitmap ինդեքսը, երբ այն ավելի լավ է, երբ այն ավելի վատ է, քան մյուս ինդեքսները, և որ դեպքերում այն զգալիորեն ավելի արագ է, քան դրանք; Տեսնենք, թե որ հայտնի DBMS-ներն արդեն ունեն bitmap ինդեքսներ. Փորձենք գրել մերը Go-ում: Իսկ «դեսերտի համար» մենք կօգտագործենք պատրաստի գրադարաններ՝ ստեղծելու մեր սեփական գերարագ մասնագիտացված տվյալների բազան:
Ես իսկապես հուսով եմ, որ իմ աշխատանքները օգտակար և հետաքրքիր կլինեն ձեզ համար: Գնա՛
Ներածություն
Բարեւ բոլորին! Երեկոյան ժամը վեցն է, և մենք բոլորս գերհոգնած ենք: Հիանալի ժամանակ է խոսելու ձանձրալի տվյալների բազայի ինդեքսի տեսության մասին, այնպես չէ՞: Մի անհանգստացեք, ես այստեղ-այնտեղ կունենամ մի քանի տող սկզբնական կոդը: 🙂
Մի կողմ թողնենք բոլոր կատակները, զեկույցը լի է ինֆորմացիայով, և մենք շատ ժամանակ չունենք: Այսպիսով, եկեք սկսենք:
Այսօր ես կխոսեմ հետևյալի մասին.
- ինչ են ինդեքսները;
- ինչ է 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 ինդեքսներին, բայց կա առաջարկ, որն առաջարկում է ավելացնել այս տարբերակը (
PostgreSQL-ը չի աջակցում bitmap ինդեքսներին, բայց օգտագործում է պարզ բիթքարտեզներ և բիթային գործողություններ՝ որոնման արդյունքները մի քանի այլ ինդեքսների մեջ համատեղելու համար:
Tarantool-ն ունի bitset ինդեքսներ և աջակցում է դրանց վրա պարզ որոնումներ:
Redis-ն ունի պարզ բիտ դաշտեր
MongoDB-ն դեռ չի աջակցում bitmap ինդեքսներին, բայց կա նաև առաջարկ, որն առաջարկում է ավելացնել այս տարբերակը
Elasticsearch-ը ներսում օգտագործում է բիթքարտեզներ
- Բայց մեր տանը նոր հարեւան է հայտնվել՝ Փիլոսան։ Սա 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-ի (միջանկյալ ներկայացման լեզու) կամ միջանկյալ լեզվի. այն գործնականում անկախ հարթակից է: Ռոբ Պայքը հիանալի ելույթ ունեցավ
Բացի այդ, 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