Bitmap ინდექსები Go-ში: ძიება ველური სიჩქარით

შესავალი

ეს მოხსენება ინგლისურად გავეცი GopherCon Russia 2019 კონფერენციაზე მოსკოვში და რუსულ ენაზე ნიჟნი ნოვგოროდში გამართულ შეხვედრაზე. საუბარია ბიტმაპ ინდექსზე - B-ხეზე ნაკლებად გავრცელებული, მაგრამ არანაკლებ საინტერესო. გაზიარება ჩანაწერი კონფერენციაზე გამოსვლები ინგლისურად და ტექსტის ტრანსკრიპტები რუსულ ენაზე.

ჩვენ შევხედავთ, როგორ მუშაობს ბიტმაპ ინდექსი, როდის არის უკეთესი, როდის არის უარესი სხვა ინდექსებზე და რა შემთხვევაში არის მათზე საგრძნობლად სწრაფი; ვნახოთ რომელ პოპულარულ DBMS-ებს აქვთ უკვე ბიტმაპის ინდექსები; შევეცადოთ დავწეროთ საკუთარი Go-ში. და "დესერტად" ჩვენ გამოვიყენებთ მზა ბიბლიოთეკებს, რომ შევქმნათ ჩვენი სუპერ სწრაფი სპეციალიზებული მონაცემთა ბაზა.

დიდი იმედი მაქვს, რომ ჩემი ნამუშევრები თქვენთვის სასარგებლო და საინტერესო იქნება. წადი!

შესავალი

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

Სალამი ყველას! საღამოს ექვსი საათია და ყველა ძალიან დაღლილები ვართ. კარგი დროა ვისაუბროთ მოსაწყენ მონაცემთა ბაზის ინდექსის თეორიაზე, არა? არ ინერვიულო, მე მექნება წყაროს კოდის რამდენიმე სტრიქონი აქა-იქ. 🙂

ყველა ხუმრობის გარდა, მოხსენება სავსეა ინფორმაციებით და ბევრი დრო არ გვაქვს. ასე რომ, დავიწყოთ.

დღეს მე ვისაუბრებ შემდეგზე:

• რა არის ინდექსები;
• რა არის bitmap ინდექსი;
• სად გამოიყენება და სად არ გამოიყენება და რატომ;
• მარტივი დანერგვა Go-ში და მცირე ბრძოლა შემდგენელთან;
• ოდნავ ნაკლებად მარტივი, მაგრამ ბევრად უფრო პროდუქტიული განხორციელება Go ასამბლერში;
• ბიტმაპ ინდექსების „პრობლემები“;
• არსებული განხორციელებები.

რა არის ინდექსები?

ინდექსი არის ცალკე მონაცემთა სტრუქტურა, რომელსაც ჩვენ ვინახავთ და ვაახლებთ ძირითად მონაცემებთან ერთად. იგი გამოიყენება ძიების დასაჩქარებლად. ინდექსების გარეშე, ძიება მოითხოვს მონაცემთა სრულად გავლას (პროცესი, რომელსაც ეწოდება სრული სკანირება) და ამ პროცესს აქვს ხაზოვანი ალგორითმული სირთულე. მაგრამ მონაცემთა ბაზები ჩვეულებრივ შეიცავს უზარმაზარ რაოდენობას და ხაზოვანი სირთულე ძალიან ნელია. იდეალურ შემთხვევაში, ჩვენ მივიღებთ ლოგარითმულ ან მუდმივ ერთს.

ეს უაღრესად რთული თემაა, სავსეა დახვეწილებითა და კომპეტენციებით, მაგრამ მონაცემთა ბაზის შემუშავებისა და კვლევის ათწლეულების შემდეგ, მე მზად ვარ ვთქვა, რომ არსებობს მხოლოდ რამდენიმე ფართოდ გამოყენებული მიდგომა მონაცემთა ბაზის ინდექსების შესაქმნელად.

პირველი მიდგომა არის საძიებო სივრცის იერარქიულად შემცირება, საძიებო სივრცის მცირე ნაწილებად დაყოფა.

ჩვენ ამას ჩვეულებრივ ვაკეთებთ სხვადასხვა ტიპის ხეების გამოყენებით. ამის მაგალითი იქნება მასალების დიდი ყუთი თქვენს კარადაში, რომელიც შეიცავს სხვადასხვა თემებად დაყოფილ მასალების პატარა ყუთებს. თუ მასალები გჭირდებათ, თქვენ ალბათ მოძებნით მათ ყუთში, სადაც წერია „მასალები“ ​​და არა „ქუქიები“, არა?

მეორე მიდგომა არის სასურველი ელემენტის ან ელემენტების ჯგუფის დაუყოვნებლივ შერჩევა. ჩვენ ამას ვაკეთებთ ჰეშ რუკებში ან საპირისპირო ინდექსებში. ჰეშის რუქების გამოყენება ძალიან ჰგავს წინა მაგალითს, მაგრამ ყუთების ყუთის ნაცვლად, თქვენს კარადაში გაქვთ ბოლო ნივთების პატარა ყუთები.

მესამე მიდგომა არის ძიების საჭიროების აღმოფხვრა. ჩვენ ამას ვაკეთებთ Bloom ფილტრების ან გუგულის ფილტრების გამოყენებით. პირველები მყისიერად გასცემენ პასუხს და გიხსნით ძიებისგან.

ბოლო მიდგომა არის მთელი ძალის სრულად გამოყენება, რასაც თანამედროვე აპარატურა გვაძლევს. ეს არის ზუსტად ის, რასაც ჩვენ ვაკეთებთ bitmap ინდექსებში. დიახ, მათი გამოყენებისას ზოგჯერ გვჭირდება მთელი ინდექსის გავლა, მაგრამ ამას ვაკეთებთ სუპერ ეფექტურად.

როგორც ვთქვი, მონაცემთა ბაზის ინდექსების თემა ვრცელია და კომპრომისებით სავსე. ეს ნიშნავს, რომ ზოგჯერ შეგვიძლია გამოვიყენოთ რამდენიმე მიდგომა ერთდროულად: თუ ჩვენ გვჭირდება ძიების კიდევ უფრო დაჩქარება, ან თუ გვჭირდება ყველა შესაძლო ტიპის ძიების დაფარვა.

დღეს მე ვისაუბრებ მათ შორის ყველაზე ნაკლებად ცნობილ მიდგომაზე - ბიტმაპ ინდექსებზე.

ვინ ვარ მე რომ ვილაპარაკო ამ თემაზე?

მე ვმუშაობ გუნდის ლიდერად Badoo-ში (ალბათ თქვენ უფრო კარგად იცნობთ ჩვენს სხვა პროდუქტს, Bumble-ს). ჩვენ უკვე გვყავს 400 მილიონზე მეტი მომხმარებელი მთელს მსოფლიოში და ბევრი ფუნქცია, რომელიც ირჩევს მათთვის საუკეთესო შესატყვისს. ჩვენ ამას ვაკეთებთ პერსონალური სერვისების გამოყენებით, ბიტმაპ ინდექსების ჩათვლით.

რა არის ბიტმაპის ინდექსი?

Bitmap ინდექსები, როგორც სახელი გვთავაზობს, იყენებენ bitmaps ან bitsets საძიებო ინდექსის განსახორციელებლად. ჩიტის თვალთახედვით, ეს ინდექსი შედგება ერთი ან მეტი ასეთი ბიტმაპისგან, რომელიც წარმოადგენს ნებისმიერ ერთეულს (როგორიცაა ადამიანები) და მათ თვისებებსა თუ პარამეტრებს (ასაკი, თვალის ფერი და ა.შ.) და ალგორითმი, რომელიც იყენებს ბიტის ოპერაციებს (AND, OR, NOT). ) საძიებო შეკითხვაზე პასუხის გასაცემად.

ჩვენ გვითხრეს, რომ bitmap ინდექსები საუკეთესოდ შეეფერება და ძალიან ეფექტურია იმ შემთხვევებისთვის, როდესაც არის ძიებები, რომლებიც აერთიანებს შეკითხვებს ბევრ დაბალი კარდინალურობის სვეტში (იფიქრეთ „თვალის ფერი“ ან „ოჯახური მდგომარეობა“ და მსგავსი რამ „ქალაქის ცენტრიდან დაშორება“ ). მაგრამ მოგვიანებით გაჩვენებთ, რომ ისინი კარგად მუშაობენ მაღალი კარდინალურობის სვეტებისთვისაც.

მოდით შევხედოთ bitmap ინდექსის უმარტივეს მაგალითს.

წარმოიდგინეთ, რომ ჩვენ გვაქვს მოსკოვის რესტორნების სია ბინარული თვისებებით, როგორიცაა:

• მეტროსთან ახლოს;
• არის კერძო პარკინგი;
• არის ვერანდა (აქვს ტერასა);
• შეგიძლიათ დაჯავშნოთ მაგიდა (იღებს დაჯავშნას);
• ვარგისია ვეგეტარიანელებისთვის (ვეგანებისთვის მეგობრული);
• ძვირი (ძვირი).

მოდით მივცეთ თითოეულ რესტორანს მიმდევრობითი ნომერი 0-დან და გამოვყოთ მეხსიერება 6 ბიტმაპისთვის (თითოეული მახასიათებლისთვის). შემდეგ ჩვენ შევავსებთ ამ ბიტმას, იმისდა მიხედვით, აქვს თუ არა რესტორანს ეს ქონება. თუ რესტორან 4-ს აქვს ვერანდა, მაშინ ბიტი No 4 ბიტმაპში „აქვს ვერანდა“ დაყენდება 1-ზე (თუ ვერანდა არ არის, მაშინ 0-ზე).

ახლა ჩვენ გვაქვს უმარტივესი ბიტმაპის ინდექსი და შეგვიძლია გამოვიყენოთ ის, რომ ვუპასუხოთ შეკითხვებს, როგორიცაა:

• „მაჩვენე ვეგეტარიანელებისთვის განკუთვნილი რესტორნები“;
• "მაჩვენე იაფი რესტორნები ვერანდით, სადაც შეგიძლიათ დაჯავშნოთ მაგიდა."

Როგორ? მოდით შევხედოთ. პირველი მოთხოვნა ძალიან მარტივია. ყველაფერი რაც ჩვენ უნდა გავაკეთოთ არის ავიღოთ „ვეგეტარიანული მეგობრული“ ბიტმაპი და გადავაქციოთ რესტორნების სიაში, რომელთა ბიტებიც არის გამოვლენილი.


მეორე მოთხოვნა ცოტა უფრო რთულია. ჩვენ უნდა გამოვიყენოთ NOT bitmap "ძვირიან" ბიტმაპზე, რომ მივიღოთ იაფი რესტორნების სია, შემდეგ AND ის ბიტმაპის "შემიძლია დაჯავშნო მაგიდა" და შედეგი "იქ არის ვერანდა" ბიტმაპით. შედეგად ბიტმაპი შეიცავს დაწესებულებების ჩამონათვალს, რომლებიც აკმაყოფილებენ ჩვენს ყველა კრიტერიუმს. ამ მაგალითში ეს მხოლოდ რესტორანი Yunost-ია.


ბევრი თეორიაა ჩართული, მაგრამ არ ინერვიულოთ, ჩვენ ძალიან მალე ვიხილავთ კოდს.

სად გამოიყენება bitmap ინდექსები?

თუ Google-ის ბიტმაპ ინდექსებს აწარმოებთ, პასუხების 90% ამა თუ იმ გზით Oracle DB-ს იქნება დაკავშირებული. მაგრამ სხვა DBMS ალბათ ასევე მხარს უჭერს ასეთ მაგარ რამეს, არა? Ნამდვილად არ.

მოდით გადავხედოთ მთავარ ეჭვმიტანილთა სიას.

MySQL ჯერ არ უჭერს მხარს ბიტმაპ ინდექსებს, მაგრამ არსებობს წინადადება, რომელიც გვთავაზობს ამ პარამეტრის დამატებას (https://dev.mysql.com/worklog/task/?id=1524).

PostgreSQL არ უჭერს მხარს ბიტმაპ ინდექსებს, მაგრამ იყენებს მარტივ ბიტმაპებსა და ბიტ ოპერაციებს, რათა დააკავშიროს ძიების შედეგები მრავალ სხვა ინდექსში.

Tarantool-ს აქვს ბიტის ინდექსები და მხარს უჭერს მათზე მარტივ ძიებას.

Redis-ს აქვს მარტივი bitfields (https://redis.io/commands/bitfield) მათი ძებნის შესაძლებლობის გარეშე.

MongoDB ჯერ არ უჭერს მხარს ბიტმაპ ინდექსებს, მაგრამ ასევე არსებობს წინადადება, რომელიც ვარაუდობს, რომ ეს ვარიანტი დაემატოს https://jira.mongodb.org/browse/SERVER-1723

Elasticsearch იყენებს ბიტმას შიგნიდან (https://www.elastic.co/blog/frame-of-reference-and-roaring-bitmaps).

• მაგრამ ჩვენს სახლში ახალი მეზობელი გამოჩნდა: პილოსა. ეს არის Go-ში დაწერილი ახალი არარელაციური მონაცემთა ბაზა. ის შეიცავს მხოლოდ ბიტმაპ ინდექსებს და მათზეა დაფუძნებული ყველაფერს. ამაზე ცოტა მოგვიანებით ვისაუბრებთ.

განხორციელება Go-ში

მაგრამ რატომ გამოიყენება bitmap ინდექსები ასე იშვიათად? ამ კითხვაზე პასუხის გაცემამდე მინდა გაჩვენოთ, თუ როგორ უნდა დანერგოთ ძალიან მარტივი bitmap ინდექსი Go-ში.

Bitmaps არსებითად მხოლოდ მონაცემების ნაწილია. Go-ში, ამისთვის გამოვიყენოთ ბაიტის ნაჭრები.

ჩვენ გვაქვს ერთი ბიტმაპი ერთი რესტორნის მახასიათებლისთვის და ბიტმაპის თითოეული ბიტი მიუთითებს, აქვს თუ არა კონკრეტულ რესტორანს ეს თვისება.

დაგვჭირდება ორი დამხმარე ფუნქცია. ერთი გამოყენებული იქნება ჩვენი ბიტმაპების შემთხვევითი მონაცემებით შესავსებად. შემთხვევითი, მაგრამ გარკვეული ალბათობით, რომ რესტორანს აქვს თითოეული ქონება. მაგალითად, მე მჯერა, რომ მოსკოვში ძალიან ცოტაა რესტორანი, სადაც არ შეიძლება მაგიდის დაჯავშნა და მეჩვენება, რომ დაწესებულებების დაახლოებით 20% შესაფერისია ვეგეტარიანელებისთვის.

მეორე ფუნქცია გარდაქმნის ბიტმაპს რესტორნების სიაში.


კითხვაზე „მაჩვენე იაფი რესტორნები, რომლებსაც აქვთ ეზო და შეუძლიათ დაჯავშნა“ პასუხის გასაცემად, ჩვენ გვჭირდება ორი ბიტიანი ოპერაცია: NOT და AND.

ჩვენ შეგვიძლია ოდნავ გავამარტივოთ ჩვენი კოდი უფრო რთული და არა ოპერატორის გამოყენებით.

ჩვენ გვაქვს ფუნქციები თითოეული ამ ოპერაციისთვის. ორივე გადის ნაჭრებს, იღებენ თითოეულ მათგანს შესაბამის ელემენტებს, ათავსებენ მათ ბიტ ოპერაციით და ათავსებენ შედეგს მიღებულ ნაჭერში.

და ახლა ჩვენ შეგვიძლია გამოვიყენოთ ჩვენი ბიტმაპები და ფუნქციები საძიებო შეკითხვაზე პასუხის გასაცემად.

შესრულება არც თუ ისე მაღალია, მიუხედავად იმისა, რომ ფუნქციები ძალიან მარტივია და ჩვენ დავზოგეთ ბევრი ფული, რომ არ დავაბრუნოთ ახალი მიღებული ნაჭერი ყოველ ჯერზე ფუნქციის გამოძახებისას.

pprof-თან ცოტა პროფილის გაკეთების შემდეგ, შევამჩნიე, რომ Go შემდგენელს აკლია ერთი ძალიან მარტივი, მაგრამ ძალიან მნიშვნელოვანი ოპტიმიზაცია: ფუნქციის ჩასმა.

ფაქტია, რომ Go შემდგენელს საშინლად ეშინია მარყუჟების, რომლებიც გადიან ნაჭრებს და კატეგორიულ უარს ამბობს ფუნქციებზე, რომლებიც შეიცავს ასეთ მარყუჟებს.

მაგრამ მე არ მეშინია და შემიძლია მოვატყუო შემდგენელი ლუპის ნაცვლად goto-ს გამოყენებით, როგორც ძველ კარგ დღეებში.

და, როგორც ხედავთ, ახლა შემდგენელი სიამოვნებით შემოიღებს ჩვენს ფუნქციას! შედეგად, ჩვენ ვახერხებთ დაახლოებით 2 მიკროწამის დაზოგვას. Ცუდი არაა!

მეორე შეფერხება ადვილი შესამჩნევია, თუ ყურადღებით დააკვირდებით შეკრების გამომავალს. შემდგენელმა დაამატა ნაჭრის საზღვრის შემოწმება სწორედ ჩვენი ყველაზე ცხელი ციკლის შიგნით. ფაქტია, რომ Go არის უსაფრთხო ენა, შემდგენელს ეშინია, რომ ჩემი სამი არგუმენტი (სამი ნაჭერი) სხვადასხვა ზომისაა. ყოველივე ამის შემდეგ, მაშინ გაჩნდება ეგრეთ წოდებული ბუფერული გადინების წარმოქმნის თეორიული შესაძლებლობა.

მოდით დავამშვიდოთ შემდგენელი ვაჩვენოთ, რომ ყველა ნაჭერი ერთი და იგივე ზომისაა. ამის გაკეთება შეგვიძლია ჩვენი ფუნქციის დასაწყისში მარტივი შემოწმების დამატებით.

ამის შემხედვარე შემდგენელი სიამოვნებით გამოტოვებს შემოწმებას და ჩვენ საბოლოოდ დავზოგავთ კიდევ 500 ნანოწამს.

დიდი ბუჩქები

კარგი, ჩვენ მოვახერხეთ ჩვენი მარტივი იმპლემენტაციის გარკვეული შესრულების გამორთვა, მაგრამ ეს შედეგი რეალურად ბევრად უარესია, ვიდრე ეს შესაძლებელია მიმდინარე აპარატურით.

ყველაფერი, რაც ჩვენ ვაკეთებთ, არის ძირითადი ბიტის ოპერაციები და ჩვენი პროცესორები ასრულებენ მათ ძალიან ეფექტურად. მაგრამ, სამწუხაროდ, ჩვენ ჩვენს პროცესორს „ვკვებავთ“ ძალიან მცირე სამუშაოებით. ჩვენი ფუნქციები ასრულებენ ოპერაციებს ბაიტი-ბაიტი საფუძველზე. ჩვენ შეგვიძლია ძალიან მარტივად შევცვალოთ ჩვენი კოდი 8-ბაიტიან ნაწილებთან მუშაობისთვის UInt64 ნაჭრების გამოყენებით.

როგორც ხედავთ, ამ მცირე ცვლილებამ რვაჯერ დააჩქარა ჩვენი პროგრამა, რვაჯერ გაზარდა სერიის ზომა. მოგება შეიძლება ითქვას წრფივია.

დანერგვა ასამბლერში

მაგრამ ეს არ არის დასასრული. ჩვენს პროცესორებს შეუძლიათ იმუშაონ 16, 32 და თუნდაც 64 ბაიტის ნაწილებთან. ასეთ „ფართო“ ოპერაციებს უწოდებენ ერთი ინსტრუქციის მრავალ მონაცემს (SIMD; ერთი ინსტრუქცია, ბევრი მონაცემი), ხოლო კოდის ტრანსფორმაციის პროცესს ისე, რომ ის იყენებს ასეთ ოპერაციებს, ეწოდება ვექტორიზაცია.

სამწუხაროდ, Go შემდგენელი შორს არის შესანიშნავი ვექტორიზაციისგან. ამჟამად Go კოდის ვექტორიზაციის ერთადერთი გზა არის ამ ოპერაციების ხელით აღება და განთავსება Go ასამბლერის გამოყენებით.

წადი ასამბლერი უცნაური მხეცია. თქვენ ალბათ იცით, რომ ასამბლეის ენა არის ის, რაც ძლიერ არის დაკავშირებული კომპიუტერის არქიტექტურასთან, რომლისთვისაც წერთ, მაგრამ Go-ში ეს ასე არ არის. Go ასამბლერი უფრო ჰგავს IRL-ს (შუალედური წარმომადგენლობის ენას) ან შუალედურ ენას: ის პრაქტიკულად პლატფორმაზე დამოუკიდებელია. რობ პაიკმა შესანიშნავი შესრულება წარმოადგინა ანგარიში ამ თემაზე რამდენიმე წლის წინ დენვერში GopherCon-ში.

გარდა ამისა, Go იყენებს უჩვეულო Plan 9 ფორმატს, რომელიც განსხვავდება ზოგადად მიღებული AT&T და Intel ფორმატებისგან.

თამამად შეიძლება ითქვას, რომ Go ასამბლერის ხელით წერა არ არის ყველაზე სახალისო.

მაგრამ, საბედნიეროდ, უკვე არსებობს ორი მაღალი დონის ინსტრუმენტი, რომელიც გვეხმარება დავწეროთ Go assembler: PeachPy და avo. ორივე უტილიტა ქმნის Go ასამბლერს უფრო მაღალი დონის კოდიდან, რომელიც დაწერილია შესაბამისად Python და Go.

ეს საშუალებები ამარტივებს ისეთ საკითხებს, როგორიცაა რეგისტრაციის განაწილება, ჩაწერის მარყუჟები და ზოგადად ამარტივებს Go-ში ასამბლეის პროგრამირების სამყაროში მოხვედრის პროცესს.

ჩვენ გამოვიყენებთ avo-ს, ამიტომ ჩვენი პროგრამები იქნება თითქმის ჩვეულებრივი Go პროგრამები.

ასე გამოიყურება ავო პროგრამის უმარტივესი მაგალითი. ჩვენ გვაქვს main() ფუნქცია, რომელიც თავის თავში განსაზღვრავს Add() ფუნქციას, რომლის მნიშვნელობა არის ორი რიცხვის დამატება. აქ არის დამხმარე ფუნქციები, რომ მიიღოთ პარამეტრები სახელით და მიიღოთ ერთ-ერთი უფასო და შესაფერისი პროცესორის რეგისტრი. პროცესორის თითოეულ ოპერაციას აქვს შესაბამისი ფუნქცია avo-ზე, როგორც ეს ჩანს ADDQ-ში. და ბოლოს, ჩვენ ვხედავთ დამხმარე ფუნქციას მიღებული მნიშვნელობის შესანახად.

gogene-ის გამოძახებით ჩვენ შევასრულებთ პროგრამას avo-ზე და შედეგად წარმოიქმნება ორი ფაილი:

• add.s მიღებული კოდით Go ასამბლერში;
• stub.go ფუნქციის სათაურებით ორი სამყაროს დასაკავშირებლად: Go და ასამბლერი.

ახლა, როცა დავინახეთ, რას აკეთებს avo და როგორ, მოდით გადავხედოთ ჩვენს ფუნქციებს. მე განვახორციელე ფუნქციების სკალარული და ვექტორული (SIMD) ვერსიები.

ჯერ სკალარული ვერსიები გადავხედოთ.

როგორც წინა მაგალითში, ჩვენ ვითხოვთ უფასო და მოქმედი ზოგადი დანიშნულების რეესტრს, არ გვჭირდება არგუმენტების ოფსეტებისა და ზომების გამოთვლა. ავო ამ ყველაფერს ჩვენთვის აკეთებს.

ჩვენ ვიყენებდით ლეიბლებს და goto-ს (ან გადახტებს) მუშაობის გასაუმჯობესებლად და Go შემდგენელის მოსატყუებლად, მაგრამ ახლა ამას თავიდანვე ვაკეთებთ. საქმე იმაშია, რომ ციკლები უფრო მაღალი დონის კონცეფციაა. ასამბლერში გვაქვს მხოლოდ ეტიკეტები და ნახტომები.

დარჩენილი კოდი უკვე ნაცნობი და გასაგები უნდა იყოს. ჩვენ ვაბაძავთ მარყუჟს ეტიკეტებით და ნახტომებით, ვიღებთ მონაცემთა მცირე ნაწილს ჩვენი ორი ნაჭერიდან, ვაერთებთ მათ ბიტის ოპერაციით (და არა ამ შემთხვევაში) და შემდეგ ვდებთ შედეგს მიღებულ ნაჭერში. ყველა.

ასე გამოიყურება საბოლოო ასამბლერის კოდი. ჩვენ არ დაგვჭირდა ოფსეტებისა და ზომების გამოთვლა (მონიშნული მწვანეში) ან გამოყენებული რეგისტრების თვალყურის დევნება (მონიშნული წითლად).

თუ შევადარებთ ასამბლეის ენის იმპლემენტაციის შესრულებას Go-ში საუკეთესო განხორციელების შესრულებას, დავინახავთ, რომ ეს იგივეა. და ეს მოსალოდნელია. ყოველივე ამის შემდეგ, ჩვენ არაფერი განსაკუთრებული არ გაგვიკეთებია - ჩვენ უბრალოდ გავამრავლეთ ის, რასაც Go compiler გააკეთებს.

სამწუხაროდ, ჩვენ არ შეგვიძლია ვაიძულოთ შემდგენელი ჩართოს ჩვენი ფუნქციები დაწერილი ასამბლეის ენაზე. Go compiler-ს ამჟამად არ აქვს ასეთი ფუნქცია, თუმცა მისი დამატების მოთხოვნა საკმაოდ დიდი ხანია არსებობს.

ამიტომაც შეუძლებელია ასამბლეის ენაში მცირე ფუნქციებიდან რაიმე სარგებლის მიღება. ან უნდა დავწეროთ დიდი ფუნქციები, ან გამოვიყენოთ ახალი მათემატიკური/ბიტების პაკეტი, ან ასამბლერის ენის გვერდის ავლით.

მოდით ახლა გადავხედოთ ჩვენი ფუნქციების ვექტორულ ვერსიებს.

ამ მაგალითისთვის მე გადავწყვიტე გამოვიყენო AVX2, ასე რომ, ჩვენ გამოვიყენებთ ოპერაციებს, რომლებიც მოქმედებენ 32 ბაიტიან ნაწილებზე. კოდის სტრუქტურა ძალიან ჰგავს სკალარულ ვერსიას: პარამეტრების ჩატვირთვა, უფასო საერთო რეესტრის მოთხოვნა და ა.შ.

ერთი ინოვაცია არის ის, რომ ფართო ვექტორული ოპერაციები იყენებენ სპეციალურ ფართო რეგისტრებს. 32-ბაიტიანი ბლოკების შემთხვევაში, ეს არის რეგისტრები, რომლებსაც აქვთ Y პრეფიქსი. სწორედ ამიტომ ხედავთ YMM() ფუნქციას კოდში. მე რომ ვიყენებდი AVX-512 64-ბიტიან ნაწილაკებს, პრეფიქსი იქნებოდა Z.

მეორე ინოვაცია არის ის, რომ მე გადავწყვიტე გამომეყენებინა ოპტიმიზაცია სახელწოდებით loop unrolling, რაც გულისხმობს რვა მარყუჟის ოპერაციების ხელით შესრულებას მარყუჟის დასაწყისში გადასვლამდე. ეს ოპტიმიზაცია ამცირებს ფილიალების რაოდენობას კოდში და შემოიფარგლება ხელმისაწვდომი უფასო რეგისტრების რაოდენობით.

აბა, რაც შეეხება შესრულებას? Ის ლამაზია! ჩვენ მივაღწიეთ დაახლოებით შვიდჯერ სიჩქარეს საუკეთესო Go გადაწყვეტასთან შედარებით. შთამბეჭდავი, არა?

მაგრამ ეს იმპლემენტაციაც კი შეიძლება დაჩქარდეს AVX-512-ის, წინასწარ ამოღების ან JIT-ის (მხოლოდ-დროის შემდგენელის) გამოყენებით შეკითხვის გრაფიკისთვის. მაგრამ ეს, რა თქმა უნდა, ცალკე მოხსენების თემაა.

პრობლემები bitmap ინდექსებთან

ახლა, როდესაც ჩვენ უკვე განვიხილეთ bitmap ინდექსის მარტივი განხორციელება Go-ში და ბევრად უფრო პროდუქტიული ასამბლეის ენაზე, მოდით საბოლოოდ ვისაუბროთ იმაზე, თუ რატომ გამოიყენება bitmap ინდექსები ასე იშვიათად.

ძველ ნაშრომებში აღნიშნულია სამი პრობლემა bitmap ინდექსებთან დაკავშირებით, მაგრამ უფრო ახალი ნაშრომები და მე ვამტკიცებ, რომ ისინი აღარ არის აქტუალური. ჩვენ არ ჩავუღრმავდებით თითოეულ ამ პრობლემას, მაგრამ ზედაპირულად შევხედავთ მათ.

მაღალი კარდინალურობის პრობლემა

ასე რომ, ჩვენ გვეუბნებიან, რომ bitmap ინდექსები შესაფერისია მხოლოდ დაბალი კარდინალურობის მქონე ველებისთვის, ანუ მათთვის, ვისაც აქვს მცირე მნიშვნელობა (მაგალითად, სქესი ან თვალის ფერი), და მიზეზი არის ის, რომ ასეთი ველების ჩვეულებრივი წარმოდგენა (ერთი ბიტი თითო მნიშვნელობაზე) მაღალი კარდინალურობის შემთხვევაში, ის ძალიან დიდ ადგილს დაიკავებს და უფრო მეტიც, ეს ბიტმაპ ინდექსები ცუდად (იშვიათად) შეივსება.


ზოგჯერ შეიძლება გამოვიყენოთ განსხვავებული წარმოდგენა, როგორიცაა სტანდარტული, რომელსაც ვიყენებთ რიცხვების გამოსასახად. მაგრამ ეს იყო შეკუმშვის ალგორითმების გამოჩენა, რამაც შეცვალა ყველაფერი. გასული ათწლეულების განმავლობაში მეცნიერებმა და მკვლევარებმა შექმნეს შეკუმშვის ალგორითმის დიდი რაოდენობა ბიტმაფებისთვის. მათი მთავარი უპირატესობა ის არის, რომ არ არის საჭირო ბიტმაფების დეკომპრესია ბიტის ოპერაციების შესასრულებლად - ჩვენ შეგვიძლია შევასრულოთ ბიტის ოპერაციები პირდაპირ შეკუმშულ ბიტმაპებზე.

ცოტა ხნის წინ გამოჩნდა ჰიბრიდული მიდგომები, როგორიცაა მღელვარე ბიტმაპები. ისინი ერთდროულად იყენებენ სამ განსხვავებულ წარმოდგენას ბიტმაფებისთვის - თავად ბიტმასები, მასივები და ეგრეთ წოდებული ბიტის გაშვებები - და ბალანსირებენ მათ შორის, რათა მაქსიმალურად გაზარდონ შესრულება და შეამცირონ მეხსიერების მოხმარება.

თქვენ შეგიძლიათ იპოვოთ მღელვარე ბიტმასები ყველაზე პოპულარულ აპლიკაციებში. უკვე არსებობს დანერგვის დიდი რაოდენობა პროგრამირების ენების ფართო სპექტრისთვის, მათ შორის Go-სთვის სამზე მეტი განხორციელება.

კიდევ ერთი მიდგომა, რომელიც დაგვეხმარება მაღალ კარდინალურობასთან გამკლავებაში, ეწოდება ბინინგი. წარმოიდგინეთ, რომ გაქვთ ველი, რომელიც წარმოადგენს ადამიანის სიმაღლეს. სიმაღლე არის მცურავი წერტილის რიცხვი, მაგრამ ჩვენ ადამიანები ასე არ ვფიქრობთ. ჩვენთვის არ არის განსხვავება 185,2 სმ სიმაღლესა და 185,3 სმ-ს შორის.

გამოდის, რომ ჩვენ შეგვიძლია დავაჯგუფოთ მსგავსი მნიშვნელობები ჯგუფებად 1 სმ-ის ფარგლებში.

და თუ ჩვენ ასევე ვიცით, რომ ძალიან ცოტა ადამიანია 50 სმ-ზე დაბალი და 250 სმ-ზე მაღალი, მაშინ ჩვენ შეგვიძლია არსებითად გადავაქციოთ უსასრულო კარდინალურობის ველი დაახლოებით 200 მნიშვნელობის კარდინალურობის ველად.

რა თქმა უნდა, საჭიროების შემთხვევაში, ჩვენ შეგვიძლია გავაკეთოთ დამატებითი ფილტრაცია.

მაღალი გამტარუნარიანობის პრობლემა

ბიტმაპ ინდექსების შემდეგი პრობლემა არის ის, რომ მათი განახლება შეიძლება ძალიან ძვირი დაჯდეს.

მონაცემთა ბაზებს უნდა შეეძლოთ მონაცემების განახლება, სანამ პოტენციურად ასობით სხვა მოთხოვნა ეძებს მონაცემებს. ჩვენ გვჭირდება საკეტები, რათა თავიდან ავიცილოთ პრობლემები მონაცემთა ერთდროულ წვდომასთან ან სხვა გაზიარების პრობლემებთან. და სადაც არის ერთი დიდი საკეტი, არის პრობლემა - საკეტის კამათი, როდესაც ეს საკეტი ხდება ბოთლი.

ამ პრობლემის გადაჭრა ან გვერდის ავლა შესაძლებელია დაშლის ან ვერსიირებული ინდექსების გამოყენებით.

დაფქვა მარტივი და ცნობილი საქმეა. შეგიძლიათ ბიტმაპის ინდექსის განაწილება, როგორც ნებისმიერი სხვა მონაცემი. ერთი დიდი საკეტის ნაცვლად, თქვენ მიიღებთ პატარა საკეტების თაიგულს და ამით მოიშორებთ საკეტის წინააღმდეგობას.

პრობლემის გადაჭრის მეორე გზა არის ვერსიირებული ინდექსების გამოყენება. თქვენ შეგიძლიათ გქონდეთ ინდექსის ერთი ასლი, რომელსაც იყენებთ საძიებლად ან წასაკითხად, და ერთი, რომელსაც იყენებთ დასაწერად ან განახლებისთვის. და ერთხელ გარკვეული პერიოდის განმავლობაში (მაგალითად, ყოველ 100 ms ან 500 ms-ში ერთხელ) თქვენ მათ დუბლირებთ და ცვლით მათ. რა თქმა უნდა, ეს მიდგომა გამოიყენება მხოლოდ იმ შემთხვევებში, როდესაც თქვენს აპლიკაციას შეუძლია გაუმკლავდეს ოდნავ ჩამორჩენილ საძიებო ინდექსს.

ამ ორი მიდგომის გამოყენება შესაძლებელია ერთდროულად: შეგიძლიათ გქონდეთ გახეხილი ვერსიული ინდექსი.

უფრო რთული მოთხოვნები

ბიტმაპ ინდექსების საბოლოო პრობლემა არის ის, რომ გვეუბნებიან, რომ ისინი არ არიან კარგად მორგებული უფრო რთული ტიპის მოთხოვნებისთვის, როგორიცაა span queries.

მართლაც, თუ დაფიქრდებით, ბიტიანი ოპერაციები, როგორიცაა AND, OR და ა.შ. არ არის ძალიან შესაფერისი კითხვებისთვის a la "მაჩვენე სასტუმროები ნომრის ფასით 200-დან 300 დოლარამდე ღამეში".

გულუბრყვილო და ძალიან არაგონივრული გადაწყვეტა იქნება შედეგების მიღება თითოეული დოლარის ღირებულებისთვის და მათი კომბინირება ბიტიური OR ოპერაციით.

ოდნავ უკეთესი გამოსავალი იქნება დაჯგუფების გამოყენება. მაგალითად, 50 დოლარიან ჯგუფებში. ეს 50-ჯერ დააჩქარებს ჩვენს პროცესს.

მაგრამ პრობლემა ასევე ადვილად მოგვარდება სპეციალურად ამ ტიპის მოთხოვნისთვის შექმნილი ხედის გამოყენებით. სამეცნიერო ნაშრომებში მას უწოდებენ დიაპაზონის კოდირებულ ბიტმაპებს.

ამ წარმოდგენაში ჩვენ არ ვაყენებთ მხოლოდ ერთ ბიტს რაიმე მნიშვნელობისთვის (მაგალითად, 200), არამედ ვაყენებთ ამ მნიშვნელობას და ყველაფერს უფრო მაღლა. 200 და ზემოთ. იგივე 300: 300 და ზემოთ. Და ასე შემდეგ.

ამ წარმოდგენის გამოყენებით, ჩვენ შეგვიძლია ვუპასუხოთ ამ ტიპის საძიებო შეკითხვას ინდექსის მხოლოდ ორჯერ გადაკვეთით. ჯერ მივიღებთ იმ სასტუმროების ჩამონათვალს, სადაც ნომრის ღირებულება ნაკლებია ან $300, შემდეგ კი ამოვიღებთ მათ, სადაც ნომრის ღირებულება ნაკლებია ან $199. მზადაა.

გაგიკვირდებათ, მაგრამ გეოკითხვებიც კი შესაძლებელია ბიტმაპ ინდექსების გამოყენებით. ხრიკი არის გეომეტრიული გამოსახულების გამოყენება, რომელიც თქვენს კოორდინატს აკრავს გეომეტრიული ფიგურით. მაგალითად, S2 Google-ისგან. ფიგურის წარმოდგენა შესაძლებელი უნდა იყოს სამი ან მეტი გადამკვეთი ხაზის სახით, რომლებიც შეიძლება იყოს დანომრილი. ამ გზით ჩვენ შეგვიძლია გადავაქციოთ ჩვენი geoquery რამდენიმე მოთხოვნად "უფსკრულის გასწვრივ" (ამ დანომრილი ხაზების გასწვრივ).

მზა გადაწყვეტილებები

ვიმედოვნებ, რომ ცოტათი დაგაინტერესებდით და ახლა თქვენს არსენალში გაქვთ კიდევ ერთი სასარგებლო ინსტრუმენტი. თუ ოდესმე დაგჭირდებათ მსგავსი რამის გაკეთება, გეცოდინებათ, რომელ მხარეს გამოიყურებოდეთ.

თუმცა, ყველას არ აქვს დრო, მოთმინება ან რესურსი, რომ შექმნას ბიტმაპის ინდექსები ნულიდან. განსაკუთრებით უფრო მოწინავეები, მაგალითად, SIMD-ის გამოყენებით.

საბედნიეროდ, არსებობს რამდენიმე მზა გამოსავალი, რომელიც დაგეხმარებათ.

მღელვარე ბიტმაპები

ჯერ ერთი, არის იგივე მღელვარე bitmaps ბიბლიოთეკა, რომელზეც უკვე ვისაუბრე. ის შეიცავს ყველა საჭირო კონტეინერს და ბიტის ოპერაციებს, რომლებიც დაგჭირდებათ სრულფასოვანი ბიტმაპის ინდექსის შესაქმნელად.

სამწუხაროდ, ამ დროისთვის, არცერთი Go-ის იმპლემენტაცია არ იყენებს SIMD-ს, რაც ნიშნავს, რომ Go-ის იმპლემენტაციები ნაკლებად ეფექტურია, ვიდრე C-ის განხორციელება, მაგალითად.

პილოსა

კიდევ ერთი პროდუქტი, რომელიც დაგეხმარებათ არის Pilosa DBMS, რომელსაც, ფაქტობრივად, აქვს მხოლოდ ბიტმაპ ინდექსები. ეს შედარებით ახალი გამოსავალია, მაგრამ გულებს დიდი სისწრაფით იპყრობს.

Pilosa იყენებს მღელვარე bitmaps-ს შინაგანად და გაძლევთ მათი გამოყენების შესაძლებლობას, ამარტივებს და განმარტავს ყველაფერს, რაზეც ზემოთ ვისაუბრე: დაჯგუფება, დიაპაზონის კოდირებული ბიტმაპები, ველის კონცეფცია და ა.შ.

მოდით გადავხედოთ Pilosa-ს გამოყენების მაგალითს იმ კითხვაზე პასუხის გასაცემად, რომელსაც უკვე იცნობთ.

მაგალითი ძალიან ჰგავს იმას, რაც ადრე ნახე. ჩვენ ვქმნით კლიენტს Pilosa სერვერზე, ვქმნით ინდექსს და საჭირო ველებს, შემდეგ ვავსებთ ჩვენს ველებს შემთხვევითი მონაცემებით ალბათობით და ბოლოს ვასრულებთ ნაცნობ მოთხოვნას.

ამის შემდეგ ჩვენ ვიყენებთ NOT-ს „ძვირადღირებულ“ ველზე, შემდეგ ვკვეთთ შედეგს (ან მას) „ტერასის“ ველთან და „რეზერვაციების“ ველთან. და ბოლოს, მივიღებთ საბოლოო შედეგს.

დიდი იმედი მაქვს, რომ უახლოეს მომავალში ეს ახალი ტიპის ინდექსი ასევე გამოჩნდება DBMS-ებში, როგორიცაა MySQL და PostgreSQL - bitmap ინდექსები.

დასკვნა

თუ ჯერ არ ჩაგიძინია, მადლობა. მოკლედ მომიწია ბევრ თემაზე შეხება შეზღუდული დროის გამო, მაგრამ ვიმედოვნებ, რომ საუბარი სასარგებლო და შესაძლოა მოტივაციურიც იყო.

Bitmap ინდექსების შესახებ კარგია იცოდეთ, მაშინაც კი, თუ ისინი ახლა არ გჭირდებათ. დაე, ისინი იყოს კიდევ ერთი ინსტრუმენტი თქვენს ხელსაწყოთა ყუთში.

ჩვენ გადავხედეთ Go-ს შესრულების სხვადასხვა ხრიკებს და საკითხებს, რომლებსაც Go შემდგენელი ჯერ არ უმკლავდება კარგად. მაგრამ ეს აბსოლუტურად სასარგებლოა ყველა Go პროგრამისტისთვის, რომ იცოდეს.

სულ ეს იყო, რაც მინდოდა მეთქვა. Გმადლობთ!

წყარო: www.habr.com