গো-তে বিটম্যাপ সূচী: বন্য গতিতে অনুসন্ধান করুন

ভূমিকা

আমি মস্কোতে GopherCon Russia 2019 সম্মেলনে ইংরেজিতে এবং Nizhny Novgorod-এ একটি মিটআপে রাশিয়ান ভাষায় এই প্রতিবেদনটি দিয়েছিলাম। আমরা একটি বিটম্যাপ সূচক সম্পর্কে কথা বলছি - বি-ট্রির চেয়ে কম সাধারণ, কিন্তু কম আকর্ষণীয় নয়। শেয়ারিং রেকর্ডিং সম্মেলনে বক্তৃতা ইংরেজিতে এবং পাঠ্য প্রতিলিপি রাশিয়ান ভাষায়।

আমরা দেখব কিভাবে একটি বিটম্যাপ সূচক কাজ করে, কখন এটি ভাল হয়, কখন এটি অন্যান্য সূচকের চেয়ে খারাপ হয় এবং কোন ক্ষেত্রে এটি তাদের তুলনায় উল্লেখযোগ্যভাবে দ্রুত হয়; দেখা যাক কোন জনপ্রিয় DBMS-এর ইতিমধ্যেই বিটম্যাপ সূচক রয়েছে; আসুন Go-তে আমাদের নিজস্ব লেখার চেষ্টা করি। এবং "ডেজার্টের জন্য" আমরা আমাদের নিজস্ব সুপার-ফাস্ট বিশেষায়িত ডাটাবেস তৈরি করতে রেডিমেড লাইব্রেরি ব্যবহার করব।

আমি সত্যিই আশা করি যে আমার কাজগুলি আপনার জন্য দরকারী এবং আকর্ষণীয় হবে। যাওয়া!

ভূমিকা

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

হাই সব! সন্ধ্যা ছয়টা বাজে এবং আমরা সবাই খুব ক্লান্ত। বিরক্তিকর ডাটাবেস সূচক তত্ত্ব সম্পর্কে কথা বলার জন্য দুর্দান্ত সময়, তাই না? চিন্তা করবেন না, আমার কাছে এখানে এবং সেখানে সোর্স কোডের কয়েকটি লাইন থাকবে। 🙂

সমস্ত কৌতুক একপাশে, প্রতিবেদনটি তথ্যে পূর্ণ, এবং আমাদের কাছে খুব বেশি সময় নেই। চল শুরু করা যাক.

আজ আমি নিম্নলিখিত বিষয়ে কথা বলব:

• সূচক কি;
• একটি বিটম্যাপ সূচক কি;
• কোথায় এটি ব্যবহার করা হয় এবং কোথায় এটি ব্যবহার করা হয় না এবং কেন;
• Go-তে সহজ বাস্তবায়ন এবং কম্পাইলারের সাথে একটু লড়াই;
• সামান্য কম সহজ, কিন্তু গো অ্যাসেম্বলারে অনেক বেশি উত্পাদনশীল বাস্তবায়ন;
• বিটম্যাপ ইনডেক্সের "সমস্যা";
• বিদ্যমান বাস্তবায়ন।

তাই সূচক কি?

ইনডেক্স হল একটি পৃথক ডেটা স্ট্রাকচার যা আমরা প্রধান ডেটা ছাড়াও বজায় রাখি এবং আপডেট করি। এটি অনুসন্ধানের গতি বাড়াতে ব্যবহৃত হয়। সূচী ব্যতীত, অনুসন্ধানের জন্য সম্পূর্ণরূপে ডেটার মধ্য দিয়ে যেতে হবে (একটি প্রক্রিয়া যাকে পূর্ণ স্ক্যান বলা হয়), এবং এই প্রক্রিয়াটির রৈখিক অ্যালগরিদমিক জটিলতা রয়েছে। কিন্তু ডেটাবেসে সাধারণত বিপুল পরিমাণ ডেটা থাকে এবং রৈখিক জটিলতা খুব ধীর। আদর্শভাবে, আমরা লগারিদমিক বা ধ্রুবক পাব।

এটি একটি অত্যন্ত জটিল বিষয়, সূক্ষ্মতা এবং ট্রেড-অফ দিয়ে ভরা, কিন্তু কয়েক দশকের ডাটাবেস উন্নয়ন এবং গবেষণা দেখার পর, আমি বলতে ইচ্ছুক যে ডাটাবেস সূচী তৈরির জন্য শুধুমাত্র কয়েকটি বহুল ব্যবহৃত পন্থা রয়েছে।

প্রথম পন্থা হল অনুসন্ধান স্থানকে অনুক্রমিকভাবে হ্রাস করা, অনুসন্ধান স্থানটিকে ছোট অংশে ভাগ করা।

আমরা সাধারণত বিভিন্ন ধরণের গাছ ব্যবহার করে এটি করি। একটি উদাহরণ হল আপনার পায়খানার উপকরণের একটি বড় বাক্স যাতে বিভিন্ন বিষয়ে বিভক্ত উপকরণের ছোট বাক্স রয়েছে। আপনার যদি উপকরণের প্রয়োজন হয়, আপনি সম্ভবত সেগুলিকে "কুকিজ" বলার পরিবর্তে "উপাদান" বলে একটি বাক্সে সন্ধান করবেন, তাই না?

দ্বিতীয় পদ্ধতি হল অবিলম্বে পছন্দসই উপাদান বা উপাদানের গোষ্ঠী নির্বাচন করা। আমরা হ্যাশ ম্যাপ বা বিপরীত সূচকে এটি করি। হ্যাশ ম্যাপ ব্যবহার করা আগের উদাহরণের মতোই, তবে বাক্সের বাক্সের পরিবর্তে, আপনার পায়খানায় চূড়ান্ত আইটেমগুলির একগুচ্ছ ছোট বাক্স রয়েছে।

তৃতীয় পদ্ধতি হল অনুসন্ধানের প্রয়োজনীয়তা দূর করা। আমরা ব্লুম ফিল্টার বা কোকিল ফিল্টার ব্যবহার করে এটি করি। প্রথমটি অবিলম্বে একটি উত্তর দেয়, আপনাকে অনুসন্ধান করা থেকে বাঁচায়৷

শেষ পন্থা হল আধুনিক হার্ডওয়্যার আমাদের যে শক্তি দেয় তার পূর্ণ ব্যবহার করা। বিটম্যাপ ইনডেক্সে আমরা ঠিক এটিই করি। হ্যাঁ, এগুলি ব্যবহার করার সময় আমাদের কখনও কখনও সম্পূর্ণ সূচকের মধ্য দিয়ে যেতে হয়, তবে আমরা এটি অত্যন্ত দক্ষতার সাথে করি।

আমি যেমন বলেছি, ডাটাবেস ইনডেক্সের বিষয় বিশাল এবং সমঝোতায় পূর্ণ। এর মানে হল যে কখনও কখনও আমরা একই সময়ে বিভিন্ন পন্থা ব্যবহার করতে পারি: যদি আমাদের আরও বেশি অনুসন্ধানের গতি বাড়ানোর প্রয়োজন হয়, অথবা যদি আমাদের সমস্ত সম্ভাব্য অনুসন্ধান প্রকারগুলিকে কভার করতে হয়।

আজ আমি এইগুলির মধ্যে সবচেয়ে কম পরিচিত পদ্ধতি সম্পর্কে কথা বলব - বিটম্যাপ ইনডেক্স।

এই বিষয়ে কথা বলার আমি কে?

আমি Badoo-তে একটি টিম লিড হিসাবে কাজ করি (সম্ভবত আপনি আমাদের অন্যান্য পণ্য, বাম্বলের সাথে আরও বেশি পরিচিত)। আমাদের ইতিমধ্যেই বিশ্বজুড়ে 400 মিলিয়নেরও বেশি ব্যবহারকারী রয়েছে এবং অনেকগুলি বৈশিষ্ট্য রয়েছে যা তাদের জন্য সেরা ম্যাচ নির্বাচন করে৷ আমরা বিটম্যাপ সূচক সহ কাস্টম পরিষেবাগুলি ব্যবহার করে এটি করি।

তাই একটি বিটম্যাপ সূচক কি?

বিটম্যাপ সূচীগুলি, নাম অনুসারে, একটি অনুসন্ধান সূচক বাস্তবায়নের জন্য বিটম্যাপ বা বিটসেটগুলি ব্যবহার করুন৷ পাখির চোখের দৃষ্টিকোণ থেকে, এই সূচকটিতে এক বা একাধিক বিটম্যাপ রয়েছে যা কোনো সত্তা (যেমন মানুষ) এবং তাদের বৈশিষ্ট্য বা পরামিতি (বয়স, চোখের রঙ, ইত্যাদি) এবং বিট অপারেশন ব্যবহার করে একটি অ্যালগরিদম (AND, OR, NOT) প্রতিনিধিত্ব করে। ) অনুসন্ধান প্রশ্নের উত্তর দিতে।

আমাদের বলা হয়েছে যে বিটম্যাপ সূচীগুলি এমন ক্ষেত্রে সবচেয়ে উপযুক্ত এবং অত্যন্ত কার্যকরী যেখানে এমন অনুসন্ধানগুলি রয়েছে যা অনেক কম কার্ডিনালিটি কলাম জুড়ে অনুসন্ধানগুলিকে একত্রিত করে (ভাবুন "চোখের রঙ" বা "বৈবাহিক অবস্থা" বনাম "শহরের কেন্দ্র থেকে দূরত্ব" এর মতো কিছু)। কিন্তু আমি পরে দেখাব যে তারা উচ্চ কার্ডিনালিটি কলামগুলির জন্যও ঠিক কাজ করে।

আসুন একটি বিটম্যাপ সূচকের সবচেয়ে সহজ উদাহরণটি দেখি।

কল্পনা করুন যে আমাদের কাছে এই ধরনের বাইনারি বৈশিষ্ট্য সহ মস্কো রেস্তোঁরাগুলির একটি তালিকা রয়েছে:

• মেট্রো কাছাকাছি;
• ব্যক্তিগত পার্কিং আছে;
• একটি বারান্দা আছে (বারান্দা আছে);
• আপনি একটি টেবিল সংরক্ষণ করতে পারেন (সংরক্ষণ গ্রহণ করে);
• নিরামিষাশীদের জন্য উপযুক্ত (ভেগান বন্ধুত্বপূর্ণ);
• ব্যয়বহুল (ব্যয়বহুল)।

আসুন প্রতিটি রেস্টুরেন্টকে 0 থেকে শুরু করে একটি সিকোয়েন্স নম্বর দিন এবং 6টি বিটম্যাপের জন্য মেমরি বরাদ্দ করুন (প্রতিটি বৈশিষ্ট্যের জন্য একটি)। রেস্তোরাঁর এই সম্পত্তি আছে কি না তার উপর নির্ভর করে আমরা তারপর এই বিটম্যাপগুলি পূরণ করব৷ যদি রেস্তোরাঁ 4-এর একটি বারান্দা থাকে, তাহলে "একটি বারান্দা আছে"-এর বিট নং 4-এ সেট করা হবে 1 (যদি কোনও বারান্দা না থাকে, তাহলে 0)।

এখন আমাদের কাছে সম্ভব সহজতম বিটম্যাপ সূচক রয়েছে এবং আমরা এটি ব্যবহার করতে পারি যেমন প্রশ্নের উত্তর দিতে:

• "আমাকে নিরামিষ-বান্ধব রেস্টুরেন্ট দেখান";
• "আমাকে বারান্দা সহ সস্তা রেস্তোরাঁ দেখান যেখানে আপনি একটি টেবিল সংরক্ষণ করতে পারেন।"

কিভাবে? চলুন দেখে নেওয়া যাক। প্রথম অনুরোধটি খুবই সহজ। আমাদের যা করতে হবে তা হল "নিরামিষাশী বন্ধুত্বপূর্ণ" বিটম্যাপটি নেওয়া এবং এটিকে রেস্তোরাঁর তালিকায় পরিণত করা যার বিটগুলি প্রকাশিত হয়েছে৷


দ্বিতীয় অনুরোধটি একটু বেশি জটিল। সস্তা রেস্তোরাঁর একটি তালিকা পেতে আমাদের "দামি" বিটম্যাপে NOT বিটম্যাপ ব্যবহার করতে হবে, তারপর এবং "আমি কি একটি টেবিল বুক করতে পারি" বিটম্যাপ এবং এবং "একটি বারান্দা আছে" বিটম্যাপ সহ ফলাফল। ফলস্বরূপ বিটম্যাপে আমাদের সমস্ত মানদণ্ড পূরণকারী প্রতিষ্ঠানগুলির একটি তালিকা থাকবে। এই উদাহরণে, এটি শুধুমাত্র ইউনোস্ট রেস্টুরেন্ট।


অনেক তত্ত্ব জড়িত আছে, কিন্তু চিন্তা করবেন না, আমরা খুব শীঘ্রই কোডটি দেখতে পাব।

বিটম্যাপ সূচক কোথায় ব্যবহার করা হয়?

আপনি যদি Google বিটম্যাপ ইনডেক্স করেন, তাহলে 90% উত্তর কোনো না কোনোভাবে ওরাকল ডিবি-র সাথে সম্পর্কিত হবে। তবে অন্যান্য ডিবিএমএসগুলিও সম্ভবত এমন একটি দুর্দান্ত জিনিস সমর্থন করে, তাই না? আসলে তা না.

আসুন প্রধান সন্দেহভাজনদের তালিকার মাধ্যমে যান.

MySQL এখনও বিটম্যাপ সূচী সমর্থন করে না, তবে এই বিকল্পটি যোগ করার পরামর্শ দেওয়ার জন্য একটি প্রস্তাব রয়েছে (https://dev.mysql.com/worklog/task/?id=1524).

PostgreSQL বিটম্যাপ সূচী সমর্থন করে না, কিন্তু সাধারণ বিটম্যাপ এবং বিট অপারেশন ব্যবহার করে একাধিক অন্যান্য সূচীতে অনুসন্ধান ফলাফল একত্রিত করতে।

Tarantool-এর বিটসেট সূচী রয়েছে এবং সেগুলিতে সহজ অনুসন্ধান সমর্থন করে৷

রেডিসের সাধারণ বিটফিল্ড রয়েছে (https://redis.io/commands/bitfield) তাদের জন্য অনুসন্ধান করার ক্ষমতা ছাড়া.

MongoDB এখনও বিটম্যাপ সূচী সমর্থন করে না, কিন্তু এই বিকল্পটি যোগ করার পরামর্শ দেওয়ার জন্য একটি প্রস্তাবও রয়েছে https://jira.mongodb.org/browse/SERVER-1723

ইলাস্টিকসার্চ অভ্যন্তরীণভাবে বিটম্যাপ ব্যবহার করে (https://www.elastic.co/blog/frame-of-reference-and-roaring-bitmaps).

• কিন্তু আমাদের বাড়িতে একজন নতুন প্রতিবেশী হাজির হয়েছে: পিলোসা। এটি Go-তে লেখা একটি নতুন নন-রিলেশনাল ডাটাবেস। এটি শুধুমাত্র বিটম্যাপ সূচী ধারণ করে এবং তাদের উপর ভিত্তি করে সবকিছু। আমরা একটু পরে এটি সম্পর্কে কথা হবে.

Go এ বাস্তবায়ন

কিন্তু কেন বিটম্যাপ সূচকগুলি খুব কমই ব্যবহৃত হয়? এই প্রশ্নের উত্তর দেওয়ার আগে, আমি আপনাকে দেখাতে চাই কিভাবে গো-তে একটি খুব সাধারণ বিটম্যাপ সূচক বাস্তবায়ন করা যায়।

বিটম্যাপগুলি মূলত ডেটার টুকরো। Go এ, এর জন্য বাইট স্লাইস ব্যবহার করা যাক।

আমাদের কাছে একটি রেস্তোরাঁর বৈশিষ্ট্যের জন্য একটি বিটম্যাপ রয়েছে এবং বিটম্যাপের প্রতিটি বিট নির্দেশ করে যে একটি নির্দিষ্ট রেস্তোরাঁর এই সম্পত্তি আছে কি না।

আমাদের দুটি সহায়ক ফাংশন প্রয়োজন হবে। একটি র্যান্ডম ডেটা দিয়ে আমাদের বিটম্যাপ পূরণ করতে ব্যবহার করা হবে। র্যান্ডম, কিন্তু একটি নির্দিষ্ট সম্ভাবনা সঙ্গে যে রেস্টুরেন্ট প্রতিটি সম্পত্তি আছে. উদাহরণস্বরূপ, আমি বিশ্বাস করি যে মস্কোতে খুব কম রেস্তোরাঁ রয়েছে যেখানে আপনি একটি টেবিল সংরক্ষণ করতে পারবেন না এবং আমার কাছে মনে হচ্ছে প্রায় 20% প্রতিষ্ঠান নিরামিষাশীদের জন্য উপযুক্ত।

দ্বিতীয় ফাংশন বিটম্যাপটিকে রেস্টুরেন্টের তালিকায় রূপান্তর করবে।


"আমাকে এমন সস্তা রেস্তোরাঁ দেখান যেগুলির একটি প্যাটিও আছে এবং সংরক্ষণ করতে পারে" এই প্রশ্নের উত্তর দিতে আমাদের দুটি বিট অপারেশন প্রয়োজন: না এবং এবং৷

আমরা আরও জটিল AND NOT অপারেটর ব্যবহার করে আমাদের কোডটিকে একটু সরল করতে পারি।

আমরা এই অপারেশন প্রতিটি জন্য ফাংশন আছে. উভয়ই স্লাইসের মধ্য দিয়ে যান, প্রতিটি থেকে সংশ্লিষ্ট উপাদানগুলি নিন, তাদের একটি বিট অপারেশনের সাথে একত্রিত করুন এবং ফলাফলটি ফলস্বরূপ স্লাইসে রাখুন।

এবং এখন আমরা আমাদের বিটম্যাপ এবং ফাংশন ব্যবহার করতে পারি অনুসন্ধান প্রশ্নের উত্তর দিতে।

কার্যকারিতা এত বেশি নয়, যদিও ফাংশনগুলি খুব সহজ এবং আমরা প্রতিবার ফাংশন কল করার সময় একটি নতুন ফলস্বরূপ স্লাইস ফেরত না দিয়ে প্রচুর অর্থ সাশ্রয় করেছি।

pprof এর সাথে কিছুটা প্রোফাইলিং করার পরে, আমি লক্ষ্য করেছি যে Go কম্পাইলার একটি খুব সহজ কিন্তু খুব গুরুত্বপূর্ণ অপ্টিমাইজেশান অনুপস্থিত ছিল: ফাংশন ইনলাইনিং।

আসল বিষয়টি হ'ল গো কম্পাইলার লুপগুলিকে ভয়ঙ্করভাবে ভয় পায় যা স্লাইসের মধ্য দিয়ে যায় এবং স্পষ্টতই ইনলাইন ফাংশনগুলিকে অস্বীকার করে যাতে এই ধরনের লুপ থাকে।

কিন্তু আমি ভীত নই এবং আমি লুপের পরিবর্তে গোটো ব্যবহার করে কম্পাইলারকে বোকা বানাতে পারি, যেমন ভালো পুরনো দিনের মতো।

এবং, আপনি দেখতে পাচ্ছেন, এখন কম্পাইলার আনন্দের সাথে আমাদের ফাংশন ইনলাইন করবে! ফলস্বরূপ, আমরা প্রায় 2 মাইক্রোসেকেন্ড সংরক্ষণ করতে পারি। খারাপ না!

আপনি সমাবেশ আউটপুট ঘনিষ্ঠভাবে তাকান যদি দ্বিতীয় বাধা দেখতে সহজ. কম্পাইলার আমাদের হটেস্ট লুপের ভিতরে একটি স্লাইস বাউন্ডারি চেক যোগ করেছে। আসল বিষয়টি হল গো একটি নিরাপদ ভাষা, কম্পাইলার ভয় পায় যে আমার তিনটি আর্গুমেন্ট (তিনটি স্লাইস) বিভিন্ন আকারের। সর্বোপরি, তারপরে তথাকথিত বাফার ওভারফ্লো হওয়ার একটি তাত্ত্বিক সম্ভাবনা থাকবে।

আসুন কম্পাইলারকে এটি দেখিয়ে আশ্বস্ত করি যে সমস্ত স্লাইস একই আকারের। আমরা আমাদের ফাংশনের শুরুতে একটি সাধারণ চেক যোগ করে এটি করতে পারি।

এটি দেখে, কম্পাইলার আনন্দের সাথে চেকটি এড়িয়ে যায় এবং আমরা আরও 500 ন্যানোসেকেন্ড সংরক্ষণ করি।

বড় কসাই

ঠিক আছে, আমরা আমাদের সাধারণ বাস্তবায়নের বাইরে কিছু কার্যক্ষমতা কমাতে পেরেছি, কিন্তু এই ফলাফলটি বর্তমান হার্ডওয়্যারের সাথে সম্ভব হওয়ার চেয়ে আসলেই অনেক খারাপ।

আমরা যা করি তা হল বেসিক বিট অপারেশন, এবং আমাদের প্রসেসরগুলি খুব দক্ষতার সাথে সেগুলি সম্পাদন করে। কিন্তু, দুর্ভাগ্যবশত, আমরা আমাদের প্রসেসরকে খুব ছোট কাজের সাথে "ফিড" করি। আমাদের ফাংশনগুলি একটি বাইট-বাই-বাইটের ভিত্তিতে কাজ করে। UInt8 স্লাইস ব্যবহার করে 64-বাইট খণ্ডের সাথে কাজ করার জন্য আমরা খুব সহজেই আমাদের কোড পরিবর্তন করতে পারি।

আপনি দেখতে পাচ্ছেন, এই ছোট পরিবর্তনটি ব্যাচের আকার আট গুণ বাড়িয়ে আমাদের প্রোগ্রামকে আট গুণ বাড়িয়েছে। লাভ লিনিয়ার বলা যেতে পারে।

অ্যাসেম্বলারে বাস্তবায়ন

কিন্তু এই শেষ নয়। আমাদের প্রসেসরগুলি 16, 32 এবং এমনকি 64 বাইটের অংশগুলির সাথে কাজ করতে পারে। এই ধরনের "বিস্তৃত" ক্রিয়াকলাপগুলিকে বলা হয় একক নির্দেশ মাল্টিপল ডেটা (SIMD; এক নির্দেশ, অনেকগুলি ডেটা), এবং কোড রূপান্তর করার প্রক্রিয়া যাতে এটি এই জাতীয় ক্রিয়াকলাপগুলি ব্যবহার করে তাকে ভেক্টরাইজেশন বলা হয়।

দুর্ভাগ্যবশত, গো কম্পাইলার ভেক্টরাইজেশনে চমৎকার থেকে অনেক দূরে। বর্তমানে, গো কোড ভেক্টরাইজ করার একমাত্র উপায় হল গো অ্যাসেম্বলার ব্যবহার করে ম্যানুয়ালি এই অপারেশনগুলি নেওয়া এবং করা।

গো অ্যাসেম্বলার এক অদ্ভুত জন্তু। আপনি সম্ভবত জানেন যে অ্যাসেম্বলি ল্যাঙ্গুয়েজ এমন কিছু যা আপনি যে কম্পিউটারের জন্য লিখছেন তার আর্কিটেকচারের সাথে প্রচণ্ডভাবে আবদ্ধ, কিন্তু গো-তে তা নয়। গো অ্যাসেম্বলার অনেকটা আইআরএল (ইন্টারমিডিয়েট রিপ্রেজেন্টেশন ল্যাঙ্গুয়েজ) বা ইন্টারমিডিয়েট ল্যাঙ্গুয়েজের মতো: এটি কার্যত প্ল্যাটফর্ম স্বাধীন। রব পাইক চমৎকার পারফরম্যান্স দিয়েছেন রিপোর্ট এই বিষয়ে বেশ কয়েক বছর আগে ডেনভারের GopherCon এ।

এছাড়াও, Go একটি অস্বাভাবিক প্ল্যান 9 ফর্ম্যাট ব্যবহার করে, যা সাধারণত গৃহীত AT&T এবং Intel ফর্ম্যাটগুলির থেকে আলাদা৷

এটা বলা নিরাপদ যে হাতে গো অ্যাসেম্বলার লেখা সবচেয়ে মজাদার নয়।

কিন্তু, সৌভাগ্যবশত, ইতিমধ্যেই দুটি উচ্চ-স্তরের সরঞ্জাম রয়েছে যা আমাদের Go assembler লিখতে সাহায্য করে: PeachPy এবং avo। উভয় ইউটিলিটি যথাক্রমে পাইথন এবং গো-তে লেখা উচ্চ-স্তরের কোড থেকে Go অ্যাসেম্বলার তৈরি করে।

এই ইউটিলিটিগুলি রেজিস্টার বরাদ্দকরণ, লুপ লেখার মতো জিনিসগুলিকে সরল করে এবং সাধারণত গো-তে অ্যাসেম্বলি প্রোগ্রামিংয়ের জগতে প্রবেশের প্রক্রিয়াটিকে সহজ করে।

আমরা অ্যাভো ব্যবহার করব, তাই আমাদের প্রোগ্রামগুলি প্রায় নিয়মিত গো প্রোগ্রাম হবে।

এটি একটি avo প্রোগ্রামের সবচেয়ে সহজ উদাহরণের মত দেখায়। আমাদের একটি প্রধান() ফাংশন রয়েছে, যা নিজের মধ্যে Add() ফাংশনকে সংজ্ঞায়িত করে, যার অর্থ হল দুটি সংখ্যা যোগ করা। নাম অনুসারে প্যারামিটার পেতে এবং বিনামূল্যে এবং উপযুক্ত প্রসেসর রেজিস্টারগুলির একটি পেতে এখানে সহায়ক ফাংশন রয়েছে। প্রতিটি প্রসেসর অপারেশনের avo-তে একটি সংশ্লিষ্ট ফাংশন থাকে, যেমনটি ADDQ-তে দেখা যায়। অবশেষে, আমরা ফলিত মান সংরক্ষণ করার জন্য একটি সহায়ক ফাংশন দেখতে পাই।

go generate কল করে, আমরা avo-এ প্রোগ্রামটি চালাব এবং ফলস্বরূপ, দুটি ফাইল তৈরি হবে:

• Go অ্যাসেম্বলারে ফলে কোড সহ add.s;
• দুই জগতকে সংযুক্ত করতে ফাংশন হেডার সহ stub.go: Go and assembler.

এখন আমরা দেখেছি avo কি করে এবং কিভাবে, আসুন আমাদের ফাংশনগুলি দেখি। আমি ফাংশনগুলির স্কেলার এবং ভেক্টর (SIMD) উভয় সংস্করণই প্রয়োগ করেছি।

আসুন প্রথমে স্কেলার সংস্করণগুলি দেখি।

আগের উদাহরণের মতো, আমরা একটি বিনামূল্যের এবং বৈধ সাধারণ উদ্দেশ্য রেজিস্টারের জন্য জিজ্ঞাসা করছি, আমাদের আর্গুমেন্টের জন্য অফসেট এবং আকার গণনা করার দরকার নেই। avo আমাদের জন্য এই সব করে.

আমরা কর্মক্ষমতা উন্নত করতে এবং গো কম্পাইলারকে কৌশল করতে লেবেল এবং গোটো (বা জাম্প) ব্যবহার করতাম, কিন্তু এখন আমরা এটি শুরু থেকেই করছি। বিন্দু হল যে চক্র একটি উচ্চ স্তরের ধারণা. অ্যাসেম্বলারে, আমাদের কেবল লেবেল এবং জাম্প রয়েছে।

অবশিষ্ট কোড ইতিমধ্যে পরিচিত এবং বোধগম্য হওয়া উচিত. আমরা লেবেল এবং লাফ দিয়ে একটি লুপ অনুকরণ করি, আমাদের দুটি স্লাইস থেকে একটি ছোট টুকরো ডেটা নিন, সেগুলিকে একটি বিট অপারেশনের সাথে একত্রিত করি (এবং এই ক্ষেত্রে নয়) এবং তারপর ফলাফলটি ফলিত স্লাইসে রাখুন। সব

চূড়ান্ত অ্যাসেম্বলার কোডটি দেখতে এটিই। আমাদের অফসেট এবং আকার গণনা করতে হবে না (সবুজ রঙে হাইলাইট করা হয়েছে) বা ব্যবহৃত রেজিস্টারগুলির ট্র্যাক রাখতে হবে (লাল রঙে হাইলাইট করা হয়েছে)।

আমরা যদি গো-তে সেরা বাস্তবায়নের পারফরম্যান্সের সাথে অ্যাসেম্বলি ল্যাঙ্গুয়েজ ইমপ্লিমেন্টেশনের পারফরম্যান্সের তুলনা করি, আমরা দেখতে পাব যে এটি একই। এবং এই প্রত্যাশিত. সর্বোপরি, আমরা বিশেষ কিছু করিনি - আমরা কেবল একটি গো কম্পাইলার কী করবে তা পুনরুত্পাদন করেছি।

দুর্ভাগ্যবশত, আমরা সমাবেশের ভাষায় লিখিত আমাদের ফাংশনগুলি ইনলাইন করতে কম্পাইলারকে বাধ্য করতে পারি না। Go কম্পাইলারে বর্তমানে এমন একটি বৈশিষ্ট্য নেই, যদিও বেশ কিছুদিন ধরে এটি যুক্ত করার অনুরোধ করা হয়েছে।

এ কারণে অ্যাসেম্বলি ল্যাঙ্গুয়েজে ছোট ছোট ফাংশন থেকে কোনো সুবিধা পাওয়া অসম্ভব। আমাদের হয় বড় ফাংশন লিখতে হবে, অথবা নতুন গণিত/বিট প্যাকেজ ব্যবহার করতে হবে, অথবা অ্যাসেম্বলার ভাষা বাইপাস করতে হবে।

আসুন এখন আমাদের ফাংশনগুলির ভেক্টর সংস্করণগুলি দেখি।

এই উদাহরণের জন্য, আমি AVX2 ব্যবহার করার সিদ্ধান্ত নিয়েছি, তাই আমরা এমন অপারেশনগুলি ব্যবহার করব যা 32-বাইট খণ্ডে কাজ করে। কোডের গঠন স্কেলার সংস্করণের অনুরূপ: পরামিতি লোড করা, একটি বিনামূল্যে শেয়ার করা রেজিস্টারের জন্য জিজ্ঞাসা করা ইত্যাদি।

একটি উদ্ভাবন হল যে বৃহত্তর ভেক্টর অপারেশনগুলি বিশেষ প্রশস্ত রেজিস্টার ব্যবহার করে। 32-বাইট খণ্ডের ক্ষেত্রে, এগুলি Y এর সাথে প্রিফিক্সড রেজিস্টার। এই কারণে আপনি কোডে YMM() ফাংশন দেখতে পাচ্ছেন। আমি যদি 512-বিট খণ্ড সহ AVX-64 ব্যবহার করি, তাহলে উপসর্গটি Z হবে।

দ্বিতীয় উদ্ভাবন হল যে আমি লুপ আনরোলিং নামক একটি অপ্টিমাইজেশন ব্যবহার করার সিদ্ধান্ত নিয়েছি, যার অর্থ লুপের শুরুতে যাওয়ার আগে ম্যানুয়ালি আটটি লুপ অপারেশন করা। এই অপ্টিমাইজেশন কোডে শাখার সংখ্যা কমিয়ে দেয় এবং বিনামূল্যের রেজিস্টারের সংখ্যা দ্বারা সীমিত।

আচ্ছা, পারফরম্যান্সের কী হবে? সে সুন্দর! সেরা Go সমাধানের তুলনায় আমরা প্রায় সাত গুণ গতি অর্জন করেছি। চিত্তাকর্ষক, ডান?

কিন্তু এমনকি এই বাস্তবায়ন সম্ভাব্যভাবে AVX-512, প্রিফেচিং বা একটি JIT (জাস্ট-ইন-টাইম কম্পাইলার) ব্যবহার করে কোয়েরি শিডিউলারের জন্য ত্বরান্বিত করা যেতে পারে। তবে এটি অবশ্যই একটি পৃথক প্রতিবেদনের জন্য একটি বিষয়।

বিটম্যাপ সূচী নিয়ে সমস্যা

এখন যেহেতু আমরা ইতিমধ্যেই গো-তে একটি বিটম্যাপ সূচকের একটি সহজ বাস্তবায়ন এবং সমাবেশের ভাষায় আরও অনেক বেশি উত্পাদনশীল একটির দিকে নজর দিয়েছি, আসুন অবশেষে বিটম্যাপ সূচকগুলি কেন খুব কমই ব্যবহার করা হয় সে সম্পর্কে কথা বলা যাক।

পুরানো কাগজপত্র বিটম্যাপ সূচীগুলির সাথে তিনটি সমস্যা উল্লেখ করে, কিন্তু নতুন কাগজপত্র এবং আমি যুক্তি দিই যে সেগুলি আর প্রাসঙ্গিক নয়। আমরা এই সমস্যাগুলির প্রতিটির গভীরে ডুব দেব না, তবে তাদের উপর নজর রাখব।

উচ্চ কার্ডিনালিটির সমস্যা

সুতরাং, আমাদের বলা হয়েছে যে বিটম্যাপ সূচীগুলি শুধুমাত্র কম কার্ডিনালিটি সহ ক্ষেত্রগুলির জন্য উপযুক্ত, অর্থাৎ যেগুলির মান কম (উদাহরণস্বরূপ, লিঙ্গ বা চোখের রঙ) রয়েছে এবং এর কারণ হল এই জাতীয় ক্ষেত্রগুলির স্বাভাবিক উপস্থাপনা (একটি বিট প্রতি মান) উচ্চ কার্ডিনালিটির ক্ষেত্রে, এটি খুব বেশি জায়গা নেবে এবং তদ্ব্যতীত, এই বিটম্যাপ সূচকগুলি খারাপভাবে (কদাচিৎ) পূর্ণ হবে।


কখনও কখনও আমরা একটি ভিন্ন উপস্থাপনা ব্যবহার করতে পারি, যেমন আমরা সংখ্যার প্রতিনিধিত্ব করার জন্য যে মানকটি ব্যবহার করি। কিন্তু এটি কম্প্রেশন অ্যালগরিদমের আবির্ভাব যা সবকিছু বদলে দিয়েছে। বিগত কয়েক দশক ধরে, বিজ্ঞানী এবং গবেষকরা বিটম্যাপের জন্য প্রচুর সংখ্যক কম্প্রেশন অ্যালগরিদম নিয়ে এসেছেন। তাদের প্রধান সুবিধা হল বিট অপারেশন করার জন্য বিটম্যাপগুলিকে ডিকম্প্রেস করার প্রয়োজন নেই - আমরা কম্প্রেসড বিটম্যাপে সরাসরি বিট অপারেশন করতে পারি।

সম্প্রতি, হাইব্রিড পন্থা প্রদর্শিত হতে শুরু করেছে, যেমন গর্জনকারী বিটম্যাপ। তারা একই সাথে বিটম্যাপের জন্য তিনটি ভিন্ন উপস্থাপনা ব্যবহার করে - বিটম্যাপ নিজেই, অ্যারে এবং তথাকথিত বিট রান - এবং তাদের মধ্যে ভারসাম্য বজায় রাখতে পারফরম্যান্স সর্বোচ্চ এবং মেমরি খরচ কমিয়ে দেয়।

আপনি সবচেয়ে জনপ্রিয় অ্যাপ্লিকেশনগুলিতে গর্জনকারী বিটম্যাপগুলি খুঁজে পেতে পারেন৷ Go এর জন্য তিনটিরও বেশি বাস্তবায়ন সহ বিভিন্ন ধরণের প্রোগ্রামিং ভাষার জন্য ইতিমধ্যে বিপুল সংখ্যক বাস্তবায়ন রয়েছে।

আরেকটি পদ্ধতি যা আমাদের উচ্চ কার্ডিনালিটি মোকাবেলা করতে সাহায্য করতে পারে তা হল বিনিং। কল্পনা করুন যে আপনার একটি ক্ষেত্র রয়েছে যা একজন ব্যক্তির উচ্চতাকে প্রতিনিধিত্ব করে। উচ্চতা একটি ভাসমান বিন্দু সংখ্যা, কিন্তু আমরা মানুষ এটা ভাবে না. আমাদের জন্য 185,2 সেমি এবং 185,3 সেমি উচ্চতার মধ্যে কোন পার্থক্য নেই।

দেখা যাচ্ছে যে আমরা একই মানগুলিকে 1 সেন্টিমিটারের মধ্যে গ্রুপে ভাগ করতে পারি।

এবং যদি আমরা এটাও জানি যে খুব কম লোকই 50 সেন্টিমিটারের চেয়ে ছোট এবং 250 সেন্টিমিটারের চেয়ে লম্বা, তাহলে আমরা মূলত অসীম কার্ডিনালিটি সহ একটি ক্ষেত্রকে প্রায় 200 মানের কার্ডিনালিটি সহ একটি ক্ষেত্রে পরিণত করতে পারি।

অবশ্যই, যদি প্রয়োজন হয়, আমরা পরে অতিরিক্ত ফিল্টারিং করতে পারি।

উচ্চ ব্যান্ডউইথ সমস্যা

বিটম্যাপ সূচীগুলির সাথে পরবর্তী সমস্যাটি হ'ল তাদের আপডেট করা খুব ব্যয়বহুল হতে পারে।

ডেটাবেসগুলিকে অবশ্যই ডেটা আপডেট করতে সক্ষম হতে হবে যখন সম্ভাব্যভাবে আরও কয়েকশ প্রশ্ন ডেটা অনুসন্ধান করছে। সমসাময়িক ডেটা অ্যাক্সেস বা অন্যান্য ভাগ করে নেওয়ার সমস্যাগুলি এড়াতে আমাদের লকগুলির প্রয়োজন৷ এবং যেখানে একটি বড় তালা আছে, সেখানে একটি সমস্যা আছে - লক বিরোধ, যখন এই তালাটি একটি বাধা হয়ে দাঁড়ায়।

এই সমস্যাটি শার্ডিং ব্যবহার করে বা সংস্করণযুক্ত সূচী ব্যবহার করে সমাধান করা যেতে পারে।

শেয়ারিং একটি সহজ এবং সুপরিচিত জিনিস। আপনি একটি বিটম্যাপ সূচী শার্ড করতে পারেন যেমন আপনি অন্য কোনো ডেটা করবেন। একটি বড় লকের পরিবর্তে, আপনি একগুচ্ছ ছোট লক পাবেন এবং এইভাবে তালা সংক্রান্ত বিরোধ থেকে মুক্তি পাবেন।

সমস্যা সমাধানের দ্বিতীয় উপায় হল সংস্করণযুক্ত সূচী ব্যবহার করা। আপনার কাছে সূচির একটি কপি থাকতে পারে যা আপনি অনুসন্ধান বা পড়ার জন্য ব্যবহার করেন এবং একটি যা আপনি লেখা বা আপডেট করার জন্য ব্যবহার করেন। এবং একটি নির্দিষ্ট সময়ের মধ্যে একবার (উদাহরণস্বরূপ, প্রতি 100 ms বা 500 ms একবার) আপনি সেগুলি নকল করুন এবং সেগুলি অদলবদল করুন৷ অবশ্যই, এই পদ্ধতিটি কেবলমাত্র সেই ক্ষেত্রে প্রযোজ্য যেখানে আপনার অ্যাপ্লিকেশনটি একটি সামান্য পিছিয়ে থাকা অনুসন্ধান সূচক পরিচালনা করতে পারে৷

এই দুটি পন্থা একযোগে ব্যবহার করা যেতে পারে: আপনার একটি শার্ড সংস্করণযুক্ত সূচক থাকতে পারে।

আরও জটিল প্রশ্ন

বিটম্যাপ সূচীগুলির সাথে চূড়ান্ত সমস্যা হল যে আমাদের বলা হয় যে তারা আরও জটিল ধরণের প্রশ্নের জন্য উপযুক্ত নয়, যেমন স্প্যান কোয়েরি।

প্রকৃতপক্ষে, আপনি যদি এটি সম্পর্কে চিন্তা করেন, AND, OR, ইত্যাদির মতো বিট অপারেশনগুলি একটি la "আমাকে প্রতি রাতে 200 থেকে 300 ডলার রুমের রেট সহ হোটেল দেখান" প্রশ্নের জন্য খুব উপযুক্ত নয়৷

একটি নিষ্পাপ এবং খুব বুদ্ধিমান সমাধান হবে প্রতিটি ডলারের মূল্যের জন্য ফলাফল নেওয়া এবং একটি বিটওয়াইজ বা অপারেশনের সাথে তাদের একত্রিত করা।

একটি সামান্য ভাল সমাধান গ্রুপিং ব্যবহার করা হবে. উদাহরণস্বরূপ, 50 ডলারের গ্রুপে। এটি আমাদের প্রক্রিয়াটিকে 50 গুণ বাড়িয়ে দেবে।

কিন্তু এই ধরনের অনুরোধের জন্য বিশেষভাবে তৈরি করা একটি ভিউ ব্যবহার করে সমস্যাটি সহজেই সমাধান করা হয়। বৈজ্ঞানিক কাগজপত্রে একে রেঞ্জ-এনকোডেড বিটম্যাপ বলা হয়।

এই উপস্থাপনায়, আমরা শুধুমাত্র কিছু মানের জন্য এক বিট সেট করি না (উদাহরণস্বরূপ, 200), কিন্তু এই মান এবং সবকিছু উচ্চতর সেট করি। 200 এবং তার উপরে। 300: 300 এবং তার উপরে একই। ইত্যাদি।

এই উপস্থাপনা ব্যবহার করে, আমরা এই ধরনের অনুসন্ধান প্রশ্নের উত্তর দিতে পারি মাত্র দুবার সূচক অতিক্রম করে। প্রথমে, আমরা হোটেলগুলির একটি তালিকা পাব যেখানে রুমের দাম কম বা $300, এবং তারপর আমরা সেখান থেকে সরিয়ে দেব যেখানে রুমের দাম কম বা $199। প্রস্তুত.

আপনি বিস্মিত হবেন, কিন্তু বিটম্যাপ সূচী ব্যবহার করে জিওকোয়েরিও সম্ভব। কৌশলটি হল একটি জ্যামিতিক উপস্থাপনা ব্যবহার করা যা একটি জ্যামিতিক চিত্রের সাথে আপনার সমন্বয়কে ঘিরে থাকে। উদাহরণস্বরূপ, Google থেকে S2। চিত্রটি তিনটি বা ততোধিক ছেদকারী রেখার আকারে উপস্থাপন করা সম্ভব হওয়া উচিত যা সংখ্যাযুক্ত হতে পারে। এইভাবে আমরা আমাদের জিওকোয়েরিকে "অবস্থান বরাবর" (এই সংখ্যাযুক্ত লাইন বরাবর) বেশ কয়েকটি প্রশ্নে পরিণত করতে পারি।

প্রস্তুত সমাধান

আমি আশা করি আমি আপনাকে একটু আগ্রহী করেছি এবং এখন আপনার অস্ত্রাগারে আরেকটি দরকারী টুল আছে। আপনি যদি কখনও এই মত কিছু করার প্রয়োজন হয়, আপনি কোন উপায় তাকান জানতে পারবেন.

যাইহোক, প্রত্যেকেরই স্ক্র্যাচ থেকে বিটম্যাপ সূচী তৈরি করার জন্য সময়, ধৈর্য বা সংস্থান নেই। বিশেষ করে আরও উন্নত, যেমন SIMD ব্যবহার করে।

সৌভাগ্যবশত, আপনাকে সাহায্য করার জন্য বেশ কিছু রেডিমেড সমাধান রয়েছে।

গর্জনকারী বিটম্যাপ

প্রথমত, একই গর্জনকারী বিটম্যাপ লাইব্রেরি রয়েছে যা আমি ইতিমধ্যেই বলেছি। এটিতে সমস্ত প্রয়োজনীয় কন্টেইনার এবং বিট অপারেশন রয়েছে যা আপনাকে একটি পূর্ণাঙ্গ বিটম্যাপ সূচক তৈরি করতে হবে।

দুর্ভাগ্যবশত, এই মুহুর্তে, Go বাস্তবায়নের কোনোটিই SIMD ব্যবহার করে না, যার অর্থ হল Go বাস্তবায়নগুলি C বাস্তবায়নের তুলনায় কম পারফরম্যান্স, উদাহরণস্বরূপ।

পিলোসা

আরেকটি পণ্য যা আপনাকে সাহায্য করতে পারে তা হল Pilosa DBMS, যেটিতে, আসলে, শুধুমাত্র বিটম্যাপ সূচক রয়েছে। এটি একটি অপেক্ষাকৃত নতুন সমাধান, তবে এটি দুর্দান্ত গতিতে হৃদয় জয় করছে।

Pilosa অভ্যন্তরীণভাবে গর্জনকারী বিটম্যাপগুলি ব্যবহার করে এবং আপনাকে সেগুলি ব্যবহার করার ক্ষমতা দেয়, আমি উপরে যে সমস্ত বিষয়ে কথা বলেছি সেগুলিকে সহজ করে এবং ব্যাখ্যা করে: গ্রুপিং, রেঞ্জ-এনকোডেড বিটম্যাপ, একটি ক্ষেত্রের ধারণা ইত্যাদি।

আপনি ইতিমধ্যে পরিচিত এমন একটি প্রশ্নের উত্তর দিতে Pilosa ব্যবহার করার একটি উদাহরণ দ্রুত দেখে নেওয়া যাক।

উদাহরণটি আপনি আগে যা দেখেছেন তার অনুরূপ। আমরা Pilosa সার্ভারে একটি ক্লায়েন্ট তৈরি করি, একটি সূচক এবং প্রয়োজনীয় ক্ষেত্র তৈরি করি, তারপর সম্ভাব্যতা সহ র্যান্ডম ডেটা দিয়ে আমাদের ক্ষেত্রগুলি পূরণ করি এবং অবশেষে, পরিচিত ক্যোয়ারীটি চালাই।

এর পরে, আমরা "ব্যয়বহুল" ক্ষেত্রে নয় ব্যবহার করি, তারপর ফলাফলটিকে (বা এবং এটি) "টেরেস" ক্ষেত্র এবং "সংরক্ষণ" ক্ষেত্রের সাথে ছেদ করি। এবং অবশেষে, আমরা চূড়ান্ত ফলাফল পেতে.

আমি সত্যিই আশা করি যে অদূর ভবিষ্যতে এই নতুন ধরনের সূচকটি MySQL এবং PostgreSQL - বিটম্যাপ সূচীগুলির মতো DBMS-এও উপস্থিত হবে।

উপসংহার

আপনি যদি এখনও ঘুমিয়ে না থাকেন, ধন্যবাদ. সীমিত সময়ের কারণে আমাকে অনেক বিষয়ে সংক্ষিপ্তভাবে স্পর্শ করতে হয়েছিল, কিন্তু আমি আশা করি আলোচনাটি দরকারী এবং এমনকি অনুপ্রেরণাদায়ক ছিল।

বিটম্যাপ সূচীগুলি সম্পর্কে জানা ভাল, এমনকি যদি আপনার এই মুহূর্তে তাদের প্রয়োজন না হয়। তাদের আপনার টুলবক্সে অন্য টুল হতে দিন।

আমরা Go এর জন্য বিভিন্ন পারফরম্যান্স কৌশল দেখেছি এবং এমন জিনিসগুলি দেখেছি যা Go কম্পাইলার এখনও খুব ভালভাবে পরিচালনা করে না। তবে এটি প্রতিটি গো প্রোগ্রামারের জানার জন্য একেবারে দরকারী।

আমি আপনাকে বলতে চেয়েছিলাম যে সব. ধন্যবাদ!

উত্স: www.habr.com