stub.go med funktionshuvuden f\u00f6r att f\u00f6rena de tv\u00e5 v\u00e4rldarna: Go och assembler.\n<\/li>\n<\/ul>\n\n
L\u00e5t oss f\u00f6rst titta p\u00e5 de skal\u00e4ra versionerna.
Tyv\u00e4rr kan vi inte f\u00e5 kompilatorn att inlinera v\u00e5ra funktioner skrivna i assembler. Go-kompilatorn har f\u00f6r n\u00e4rvarande inte den m\u00f6jligheten, trots att efterfr\u00e5gan p\u00e5 att l\u00e4gga till det har funnits under ganska l\u00e5ng tid.<\/p>\n
Det \u00e4r d\u00e4rf\u00f6r det \u00e4r om\u00f6jligt att f\u00e5 n\u00e5gra f\u00f6rdelar fr\u00e5n sm\u00e5 funktioner i assembler. Vi m\u00e5ste antingen skriva stora funktioner eller anv\u00e4nda det nya paketet math\/bits, eller s\u00e5 m\u00e5ste vi undvika assembler helt.<\/p>\n
L\u00e5t oss nu titta p\u00e5 de vektoriserade versionerna av v\u00e5ra funktioner.
En andra nyhet \u00e4r att jag har valt att anv\u00e4nda en optimering som kallas loop unrolling, vilket inneb\u00e4r att jag g\u00f6r \u00e5tta loopoperationer manuellt innan jag hoppar tillbaka till b\u00f6rjan av loopen. Denna optimering minskar antalet f\u00f6rgreningar i koden, och den \u00e4r begr\u00e4nsad av antalet tillg\u00e4ngliga register.
Problem med bitmap-index<\/h2>\n \nNu n\u00e4r vi har g\u00e5tt igenom en enkel implementation av bitmap-index i Go och en mycket mer prestandakraftig i assembler, l\u00e5t oss \u00e4ntligen prata om varf\u00f6r bitmap-index s\u00e5 s\u00e4llan anv\u00e4nds.
Problemet med h\u00f6g kardinalitet<\/h2>\n \nS\u00e5, vi f\u00e5r veta att bitmap-index endast \u00e4r l\u00e4mpliga f\u00f6r f\u00e4lt med l\u00e5g kardinalitet, det vill s\u00e4ga s\u00e5dana som har f\u00e5 v\u00e4rden (till exempel k\u00f6n eller \u00f6gonf\u00e4rg), och anledningen \u00e4r att den vanliga representationen av s\u00e5dana f\u00e4lt (en bit per v\u00e4rde) vid h\u00f6g kardinalitet skulle ta f\u00f6r mycket plats, och dessutom skulle dessa bitmap-index vara svagt (s\u00e4llan) fyllda.
Du kan se roaring bitmaps i m\u00e5nga popul\u00e4ra applikationer. Det finns redan ett stort antal implementationer f\u00f6r de mest olika programmeringsspr\u00e5ken, inklusive mer \u00e4n tre implementationer f\u00f6r Go.
Detta inneb\u00e4r att vi kan gruppera liknande v\u00e4rden i grupper inom 1 cm.<\/p>\n
Och om vi dessutom vet att mycket f\u00e5 m\u00e4nniskor har en h\u00f6jd l\u00e4gre \u00e4n 50 cm och h\u00f6gre \u00e4n 250 cm, kan vi i princip omvandla ett f\u00e4lt med o\u00e4ndlig kardinalitet till ett f\u00e4lt med kardinalitet p\u00e5 cirka 200 v\u00e4rden.<\/p>\n
Sj\u00e4lvklart, om s\u00e5 beh\u00f6vs kan vi g\u00f6ra ytterligare filtrering efter\u00e5t.<\/p>\n
Problemet med h\u00f6g genomstr\u00f6mning<\/h2>\n \nN\u00e4sta problem med bitmap-index \u00e4r att deras uppdatering kan vara v\u00e4ldigt kostsam.<\/p>\n
Databaser m\u00e5ste m\u00f6jligg\u00f6ra uppdateringar av data samtidigt som potentiellt hundratals andra f\u00f6rfr\u00e5gningar s\u00f6ker i dessa data. Vi beh\u00f6ver l\u00e5s f\u00f6r att undvika problem med samtidig \u00e5tkomst till data eller andra problem med delad \u00e5tkomst. Och d\u00e4r det finns ett stort l\u00e5s, finns det ett problem med lock contention, d\u00e4r detta l\u00e5s blir en flaskhals.
Sharding \u00e4r en enkel och v\u00e4lk\u00e4nd teknik. Du kan sharda bitmap-index precis som du shardar andra data. Ist\u00e4llet f\u00f6r ett stort l\u00e5s f\u00e5r du flera sm\u00e5 l\u00e5s och p\u00e5 s\u00e5 s\u00e4tt undviker du lock contention.<\/p>\n
Ett andra s\u00e4tt att l\u00f6sa problemet \u00e4r att anv\u00e4nda versionshanterade index. Du kan ha en kopia av indexet som du anv\u00e4nder f\u00f6r s\u00f6kning eller l\u00e4sning, och en f\u00f6r skrivning eller uppdatering. Och med j\u00e4mna mellanrum (till exempel var 100 ms eller 500 ms) duplicerar du dem och byter plats. Naturligtvis \u00e4r denna metod endast till\u00e4mplig n\u00e4r din applikation kan fungera med ett n\u00e5got f\u00f6rdr\u00f6jt s\u00f6kindex.<\/p>\n
Dessa tv\u00e5 metoder kan anv\u00e4ndas samtidigt: du kan ha ett shardat versionshanterat index.<\/p>\n
Mer komplexa fr\u00e5gor<\/h2>\n Det sista problemet med bitmap-index \u00e4r att de s\u00e4gs vara d\u00e5ligt l\u00e4mpade f\u00f6r mer komplexa typer av fr\u00e5gor, till exempel fr\u00e5gor \"inom intervall\".<\/p>\n
Och faktiskt, om vi t\u00e4nker efter, \u00e4r bitoperationer som AND, OR osv. inte riktigt l\u00e4mpliga f\u00f6r fr\u00e5gor som \"Visa mig hotell med priser fr\u00e5n 200 till 300 dollar per natt\".
Men problemet l\u00f6ses lika enkelt med hj\u00e4lp av en representation som skapats speciellt f\u00f6r denna typ av fr\u00e5gor. Inom vetenskapliga arbeten kallas det range-encoded bitmaps.
Genom att anv\u00e4nda denna representation kan vi svara p\u00e5 denna typ av s\u00f6kfr\u00e5ga genom att g\u00e5 igenom indexet endast tv\u00e5 g\u00e5nger. F\u00f6rst f\u00e5r vi en lista med hotell d\u00e4r rummet kostar mindre \u00e4n 300 dollar, och sedan tar vi bort de d\u00e4r rumspriserna \u00e4r l\u00e4gre \u00e4n 199 dollar. Klart.
F\u00e4rdiga l\u00f6sningar<\/h2>\n \nJag hoppas att jag har v\u00e4ckt ditt intresse lite och att du nu har ett anv\u00e4ndbart verktyg i din verktygsl\u00e5da. Om du n\u00e5gonsin beh\u00f6ver g\u00f6ra n\u00e5got liknande, vet du vilken v\u00e4g du ska titta.<\/p>\n
Men inte alla har tid, t\u00e5lamod och resurser f\u00f6r att skapa bitmap-index fr\u00e5n grunden. S\u00e4rskilt mer avancerade som anv\u00e4nder SIMD, till exempel.<\/p>\n
Lyckligtvis finns det flera f\u00e4rdiga l\u00f6sningar som kan hj\u00e4lpa dig.
Roaring bitmaps<\/h2>\n \nF\u00f6rst finns det det som kallas roaring bitmaps-biblioteket, som jag redan n\u00e4mnt. Det inneh\u00e5ller alla n\u00f6dv\u00e4ndiga containrar och bitoperationer som du beh\u00f6ver f\u00f6r att skapa ett fullst\u00e4ndigt bitmap-index.
Pilosa<\/h2>\n \nEn annan produkt som kan hj\u00e4lpa dig \u00e4r databasen Pilosa, som i grunden bara har bitmap-index. Det \u00e4r en relativt ny l\u00f6sning, men den vinner snabbt hj\u00e4rtan.
L\u00e5t oss snabbt titta p\u00e5 ett exempel p\u00e5 hur Pilosa anv\u00e4nds f\u00f6r att svara p\u00e5 en fr\u00e5ga som ni redan k\u00e4nner till.
Efter detta anv\u00e4nder vi NOT p\u00e5 f\u00e4ltet \"expensive\", sedan korsar vi resultatet (eller AND-ar) med f\u00e4ltet \"terrace\" och f\u00e4ltet \"reservations\". Och till slut f\u00e5r vi det slutgiltiga resultatet.
Slutsats<\/h2>\n \n
Det \u00e4r bra att k\u00e4nna till bitmap-index, \u00e4ven om du just nu kanske inte beh\u00f6ver dem. L\u00e5t dem vara ytterligare ett verktyg i din verktygsl\u00e5da.<\/p>\n
Vi har sett olika trick f\u00f6r att \u00f6ka prestandan f\u00f6r Go och de saker som Go-kompilatorn fortfarande inte hanterar s\u00e4rskilt bra. Och detta \u00e4r definitivt n\u00e5got varje Go-programmerare b\u00f6r veta.<\/p>\n
Det \u00e4r allt jag ville ber\u00e4tta. Tack!habr.com<\/a><\/p>","protected":false,"gt_translate_keys":[{"key":"rendered","format":"html"}]},"excerpt":{"rendered":"\u0412\u0441\u0442\u0443\u043f\u0438\u0442\u0435\u043b\u044c\u043d\u043e\u0435 \u0441\u043b\u043e\u0432\u043e \u042f \u0432\u044b\u0441\u0442\u0443\u043f\u0438\u043b \u0441 \u044d\u0442\u0438\u043c \u0434\u043e\u043a\u043b\u0430\u0434\u043e\u043c \u043d\u0430 \u0430\u043d\u0433\u043b\u0438\u0439\u0441\u043a\u043e\u043c \u044f\u0437\u044b\u043a\u0435 \u043d\u0430 \u043a\u043e\u043d\u0444\u0435\u0440\u0435\u043d\u0446\u0438\u0438 GopherCon Russia 2019 \u0432 \u041c\u043e\u0441\u043a\u0432\u0435 \u0438 \u043d\u0430 \u0440\u0443\u0441\u0441\u043a\u043e\u043c \u2014 \u043d\u0430 \u043c\u0438\u0442\u0430\u043f\u0435 \u0432 \u041d\u0438\u0436\u043d\u0435\u043c \u041d\u043e\u0432\u0433\u043e\u0440\u043e\u0434\u0435. \u0420\u0435\u0447\u044c \u0432 \u043d\u0451\u043c \u0438\u0434\u0451\u0442 \u043e bitmap-\u0438\u043d\u0434\u0435\u043a\u0441\u0435 \u2014 \u043c\u0435\u043d\u0435\u0435 \u0440\u0430\u0441\u043f\u0440\u043e\u0441\u0442\u0440\u0430\u043d\u0451\u043d\u043d\u043e\u043c, \u0447\u0435\u043c B-tree, \u043d\u043e \u043d\u0435 \u043c\u0435\u043d\u0435\u0435 \u0438\u043d\u0442\u0435\u0440\u0435\u0441\u043d\u043e\u043c. \u0414\u0435\u043b\u044e\u0441\u044c \u0437\u0430\u043f\u0438\u0441\u044c\u044e \u0432\u044b\u0441\u0442\u0443\u043f\u043b\u0435\u043d\u0438\u044f \u043d\u0430 \u043a\u043e\u043d\u0444\u0435\u0440\u0435\u043d\u0446\u0438\u0438 \u043d\u0430 \u0430\u043d\u0433\u043b\u0438\u0439\u0441\u043a\u043e\u043c \u0438 \u0442\u0435\u043a\u0441\u0442\u043e\u0432\u043e\u0439 \u0440\u0430\u0441\u0448\u0438\u0444\u0440\u043e\u0432\u043a\u043e\u0439 \u043d\u0430 \u0440\u0443\u0441\u0441\u043a\u043e\u043c. \u041c\u044b \u0440\u0430\u0441\u0441\u043c\u043e\u0442\u0440\u0438\u043c, […]<\/p>\n","protected":false,"gt_translate_keys":[{"key":"rendered","format":"html"}]},"author":1,"featured_media":25469,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[688],"tags":[],"class_list":["post-33793","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-administrirovanie"],"aioseo_notices":[],"aioseo_head":"\n\t\t\n\t
![\"Bitmap-index](\"\/wp-content\/uploads\/2019\/05\/86ef928e6741022b2c0e5885a031408a.jpeg\")