নোট: যেমন সবসময়, আমার সকল সর্বজনীন লেখা আছে আমি নিজে হাতে লিখে।
ওভারভিউ
একটি ব্লুম ফিল্টার হল একটি সম্ভাব্য ডেটা স্ট্রাকচার যা আপনাকে দ্রুত এবং সস্তায় উত্তর দিতে দেয় "এই সেটে কি কী X আছে?" হয়ো হয় "নিশ্চিতভাবে না" বা "সম্ভবত হ্যাঁ"। আপনি আপনার কাজ এবং হার্ডওয়্যারের জন্য গ্রহণযোগ্য একটি ভুল ইতিবাদ হার বেছে নিন, সেটের মধ্যে কী যোগ করুন, এবং পরে তাদের অস্তিত্ব পরীক্ষা করুন। ব্লুম ফিল্টার সেটের কার্ডিনালিটির তুলনায় কম মেমরি ব্যবহার করে এবং গণনাত্মকভাবে খুবই সস্তা। এই কারণগুলির জন্য, এটি উচ্চ কার্যক্ষমতা ডাটা সিস্টেমে ঘন ঘন ব্যবহৃত হয়। উদাহরণস্বরূপ, একটি ডাটাবেস একটি ইন-মেমরি ব্লুম ফিল্টার বজায় রাখতে পারে এবং রো খুঁজে পেতে গিয়ে আসলে ডিস্কে যাওয়ার আগে এটি পরীক্ষা করুন। এটি খুবই ধীর ডিস্ক IO-এর বিশাল পরিমাণ সঞ্চয় করে। আমরা ব্লুস্কাই ব্যাকএন্ডের অনেক জায়গায়ও এটি ব্যবহার করি। এটি আমাদেরকে ব্লুস্কাই ডাটাবেসের বিরুদ্ধে ব্লক, মিউট, লেবেল এবং আরও অন্য কিছু খুঁজতে সেকেন্ডে মিলিয়ন সংখ্যক প্রশ্ন বাঁচাতে দেয়। উদাহরণস্বরূপ, আমরা প্রায়ই প্রশ্নের উত্তর দিতে পারি "উপযোগকর্তা X কি উপযোগকর্তা Y-কে ব্লক করে?" ডাটাবেসের স্পর্শ ছাড়াই।
এখানে আমাদের কিছু ব্লুম ফিল্টার ইতিবাদ হার হারের শেষ কয়েকদিন আছে:
উপরের হলুদ রেখাটি প্রায় 1% ইতিবাদ হার দেখায়, যা মানে যে 99% সময়, আমরা আমাদের ডাটাবেসের প্রশ্ন এড়াতে পারি। এটি সাইটটি স্কেল করা এবং কম খরচে চালানোর আমাদের ক্ষমতার জন্য অপরিহার্য ছিল।
ঐতিহ্যবাহী ব্লুম ফিল্টার
একটি ব্লুম ফিল্টার হল বিটস এর একটি অ্যারে এবং k হ্যাশ ফাংশন। আপনি অ্যারের আকার এবং k আগে থেকে বেছে নিন, এবং আপনি আপনার কাজের জন্য সঠিক আকার দিতে চান যাতে নির্দিষ্ট ভুল ইতিবাদ হার পান। একটি কী যুক্ত করতে, এটি k হ্যাশ ফাংশনের মধ্য দিয়ে চালিয়ে যান এবং প্রতিটি স্থানে বিটস সেট করুন। যদি একটি কী সেটে আছে কিনা তা পরীক্ষা করতে, এটি k বার হ্যাশ করুন এবং বিট অ্যারেতে প্রতিটি ফলাফল স্থান পরীক্ষা করুন। যদি কোনও বিট শূন্য হয়, তাহলে কীটি কখনোই যোগ করা হয়নি। যদি সব বিটস 1-এ সেট করা হয়, তাহলে এটি সেটে থাকতে পারে।
ডাবল হ্যাশিং
ডিস্কে যাওয়ার চেয়ে অনেক সস্তা, তবে প্রতিটি কীজের জন্য k স্বাধীন হ্যাশ গণনা করা খুব উচ্চ কার্যক্ষমতা সিস্টেমের জন্য একটু মহামূল্য। 2008 সালে, Kirsch এবং Mitzenmacher একটি পেপার লিখেছিল যা প্রমাণ করে যে দুটি হ্যাশ আপনাকে একই আউটপুট দিতে পারে। গণিত আমার মাথার উপরে খুব বেশি, কিন্তু যদি আপনি i-তম স্থানটি (hash_1 + i*hash_2) % n হিসাবে উদ্ধৃত করেন, তাহলে ভুল ইতিবাদ হারটি কার্যকরভাবে k স্বাধীন হ্যাশ ব্যবহার করার সমান। পুহ!
bits-and-blooms/bloom যা Daniel Lemire (আমার একজন বড় অনুপ্রেরণা, আপনার উচ্চারণ করা উচিত তার বই) দ্বারা রক্ষিত একটি চমৎকার ডাবল হ্যাশ ব্লুম ফিল্টার বাস্তবায়ন যা Go-তে লিখে। এটি 128-বিট murmur3 দুই বার চালিয়ে চারটি 64-বিট মান পায়, তারপর তাদের সংযোজন করে সমস্ত k বিট স্থান উৎপাদন করে। আমরা ব্লুস্কাইতে এটি উৎপাদনে ব্যবহার করেছিলাম।
ব্লুস্কাই ব্যাকএন্ডের জন্য, আমরা প্রায়শই একটি প্রক্রিয়া শুরু হওয়ার সাথে সাথে SELECT * FROM blocks, mutes, list items, ইত্যাদি করি এবং সমস্ত আইটেমটি ব্লুম ফিল্টারে যোগ করি। একটি রিয়েল-টাইম atproto firehose ভোক্তা ব্লুম ফিল্টারে আইটেম সন্নিহিত করে (প্রক্রিয়া শুরুর সময় even), তাই যদি আপনি সতর্ক না হন তাহলে একটি গ্রীষ্মকালীন অবস্থা থাকতে পারে। bits-and-blooms লাইব্রেরির সমস্যা হল যে এটি ভেতরে থ্রেড-নিরাপদ নয়, তাই আমাদের সমস্যার সম্ভাবনা এড়াতে সমস্ত ব্লুম ফিল্টার অ্যাক্সেস একটি মিউটেক্সে লাফ দিতে হত। pprof দেখিয়েছিল যে মিউটেক্স সংঘর্ষটি প্রক্রিয়া শুরু করতে বাধা পড়ে আছে। একটি একক স্থাপনা 90 মিনিট নিয়ে গিয়েছিল পূরণভাবে সম্পূর্ণ করতে এটির ফলে! তাই আমার সহযোগী Jasmine লাইব্রেরি ফর্ক করেছিল এবং atomic-bloom তৈরি করেছিল, যা CPU নির্দেশাবলী ব্যবহার করে একই যুক্তি তৈরি করে, কিন্তু নিরাপদ এবং মিউটেক্স ছাড়া। এটি কম সংঘর্ষ এবং মিউটেক্স-ভিত্তিক পদ্ধতির চেয়ে অনেক দ্রুত ছিল। আমাদের স্থাপনা 90 মিনিট থেকে প্রায় 15 মিনিটে এসে গিয়েছিল, যা আমাদেরকে আরও দ্রুত এবং বেশি বিশ্বাসের সাথে পাঠাতে সক্ষম করেছিল। চমৎকার!
একটি হ্যাশ
আমরা আরও আগে যেতে পারি? ব্লুস্কাইয়ের জন্য, উত্তর না। সংঘর্ষই আমাদের মূল সমস্যা ছিল, হ্যাশ ফাংশনের সংখ্যা বা অন্যান্য কারক নয়, তাই Amdahl এর আইন অনুসারে আমরা কোনও অতিরিক্ত সুবিধা পাইনি...
উৎস: Hacker News · সারাংশ: HeadlinesBriefing