লেখক: Ehud Tamir
এক সফটওয়্যার ডেভেলপার হিসেবে আমার জন্য সবচেয়ে বড় চ্যালেঞ্জগুলোর একটি হলো অন্যের কোড পড়া। এই পোস্টে, আমি একটি আকর্ষণীয় C কোডের টুকরো পড়েছি যা আমি জানতাম না, এবং আমি সেটি আপনাদের सामने উপস্থাপন করতে যাচ্ছি। যে কোডটি আমি আলোচনা করব সেটি Redis ডাটাবেসের অংশ, এবং এটি এখানে পাওয়া যায়।
Redis একটি কি-ভ্যালু ডাটাবেস। ডাটাবেসের প্রতিটি এন্ট্রি একটি কি থেকে একটি ভ্যালুতে ম্যাপিং। ভ্যালুগুলোর একাধিক টাইপ হতে পারে। আছে ইন্টিজার, লিস্টস, হ্যাশ টেবিলস এবং আরও। পর্দার পিছনে, ডাটাবেসটি নিজেও একটি হ্যাশ টেবিল। এই পোস্টে, আমরা Redis-এ SCAR কমান্ড এক্সপ্লোর করব।
By © User:Colin / Wikimedia Commons, CC BY-SA 4.0
Redis SCAN
SCAN একটি কার্সর-বেসড ইটারেশন কমান্ড, যা একটি ক্লায়েন্টকে একটি টেবিলের সব এলিমেন্টের ওপর ইটারেট করতে দেয়। এই কার্সর-বেসড স্ক্যানার প্রতিটি কল একটি ইন্টিজার কার্সর এক্সেপ্ট করে, এবং রিটার্ন করে একটি ব্যাচ অফ আইটেমস এবং কার্সর ভ্যালু যেটি পরবর্তী SCAN কলের জন্য ব্যবহার করা হবে। ইনিশিয়াল কার্সর ভ্যালু ০, এবং যখন SCAN ০ রিটার্ন করে নেক্সট কার্সর ভ্যালু হিসেবে, এর মানে স্ক্যান সম্পন্ন হয়েছে এবং সব এলিমেন্ট ক্লায়েন্ট দ্বারা দেখা হয়েছে।
SCAN কমান্ডের কিছু আকর্ষণীয় প্রপার্টি রয়েছে:
- এটি গ্যারান্টি দেয় যে টেবিলে উপস্থিত সব আইটেম কমপক্ষে একবার রিটার্ন হবে।
- এটি স্টেটলেস। টেবিল তার এক্টিভ স্ক্যানাররা সম্পর্কে কোনো ডেটা সংরক্ষণ করে না। এর মানে স্ক্যানগুলো ডাটাবেস লক করে না।
- এটি টেবিল রিসাইজিং-এ রেজিলিয়েন্ট। O(1) অ্যাক্সেস টাইম মেইনটেইন করতে, হ্যাশ টেবিলস একটি নির্দিষ্ট লোড ফ্যাক্টর সাস্টেইন করে। লোড ফ্যাক্টর মাপে একটি টেবিল কতটুকু "ফুল" একটি প্রদত্ত সময়ে। যখন লোড ফ্যাক্টর খুব বড় বা খুব ছোট হয়, টেবিলটি রিসাইজ করা হয়। SCAN তার গ্যারান্টি মেইনটেইন করবে এমনকি যদি টেবিল রিসাইজ হচ্ছে তখন কল করা হয়।
ইমপ্লিমেন্টেশন
SCAN ইমপ্লিমেন্টেড আছে dict.c-এ, dictScan() ফাংশনে। এটি ফাংশনের সিগনেচার এবং এডিশনাল হাউসকিপিং:
unsigned long dictScan(dict *d, unsigned long v, dictScanFunction *fn, dictScanBucketFunction* bucketfn, void *privdata) {
dictht *t0, *t1;
const dictEntry *de, *next;
unsigned long m0, m1;
if (dictSize(d) == 0) return 0;
// ...দ্রষ্টব্য জিনিসগুলো:
- ফাংশনটি ৫টি প্যারামিটার এক্সেপ্ট করে:
dict *d, স্ক্যান করা ডিকশনারি,unsigned long v, কার্সর, এবং ৩টি অন্যান্য প্যারামিটার যেগুলো আমরা পরে আলোচনা করব। - ফাংশনটি রিটার্ন করে কার্সর ভ্যালু যেটি এই ফাংশনের পরবর্তী কলের জন্য ব্যবহার হবে। যদি ফাংশন ০ রিটার্ন করে, এর মানে স্ক্যান সম্পন্ন।
if (dictSize(d) == 0) return 0;। যখন ডিকশনারি খালি, ফাংশন ০ রিটার্ন করে স্ক্যান সম্পন্ন বোঝাতে।
১. নরমাল স্ক্যানিং
নিচের কোড এলিমেন্টের একটি বन्च স্ক্যান করে:
if (!dictIsRehashing(d)) {
t0 = &(d->ht[0]);
m0 = t0->sizemask;
/* Emit entries at cursor */
if (bucketfn) bucketfn(privdata, &t0->table[v & m0]);
de = t0->table[v & m0];
while (de) {
next = de->next;
fn(privdata, de);
de = next;
}
/* Set unmasked bits so incrementing the reversed cursor
* operates on the masked bits */
v |= ~m0;
/* Increment the reverse cursor */
v = rev(v);
v++;
v = rev(v);
} else {
// ...এটি ধাপে ধাপে যাই। প্রথম লাইনটি থেকে শুরু করি:
if (!dictIsRehashing(d)) {
t0 = &(d->ht[0]);
m0 = t0->sizemask;Rehashing হলো একটি টেবিল রিসাইজ হওয়ার পর এলিমেন্টগুলো টেবিল জুড়ে সমানভাবে ছড়িয়ে দেওয়ার প্রসেস। dict.c হ্যাশ টেবিল ইনক্রিমেন্টালি rehash করে, যার মানে এটি পুরো টেবিল একসাথে rehash করে না, বরং কয়েকটু করে। টেবিলের ওপর করা যেকোনো অপারেশন, যেন অ্যাড, ডিলিট, ফাইন্ড, একটি rehash স্টেপও পারফর্ম করে। এটি rehashing-এর সময় টেবিলকে অপারেশনগুলোর জন্য উপলব্ধ রাখতে অনুমতি দেয়। Rehashing কীভাবে ইমপ্লিমেন্টেড সেটির কারণে, ফাংশনটি rehashing-এর সময় ভিন্নভাবে কাজ করে। আমরা শুরু করব না rehashing হচ্ছে তখন কী হয় সেটি দেখতে।
হ্যাশ টেবিলের একটি পয়েন্টার লোকাল ভেরিয়েবল t0-এ সংরক্ষিত হয়, এবং এর সাইজ মাস্ক m0-এ সংরক্ষিত হয়। সাইজ মাস্ক: dict.c হ্যাশ টেবিলস সবসময় আকারে 2^n। একটি প্রদত্ত টেবিল সাইজের জন্য, সাইজ মাস্ক হলো 2^n-1, যা একটি বাইনারি নম্বর যার n লিস্ট সিগনিফিক্যান্ট বিটস ১ সেট করা। উদাহরণস্বরূপ, n=4 জন্য; 2^n-1 = 00001111। একটি প্রদত্ত কির জন্য, হ্যাশ টেবিলে তার লোকেশন হবে কির hash-এর শেষ n বিট। আমরা এটিকে একটু পরে একশনে দেখব।
dict.c হ্যাশ টেবিল ওপেন অ্যাড্রেসিং ব্যবহার করে। টেবিলের প্রতিটি এন্ট্রি কনফ্লিক্টিং হ্যাশ ভ্যালু دار এলিমেন্টের একটি লিংকড-লিস্ট। এটিকে একটি বাকেট বলা হয়। এই পরবর্তী অংশে, একটি বাকেট এলিমেন্ট স্ক্যান করা হয়:
/* Emit entries at cursor */
if (bucketfn) bucketfn(privdata, &t0->table[v & m0]);
de = t0->table[v & m0];
while (de) {
next = de->next;
fn(privdata, de);
de = next;
}সাইজ মাস্ক-র ব্যবহার লক্ষ্য করুন: t0->table[v & m0]। v টেবিলের ইনডেক্সেবল রেঞ্জের বাইরে হতে পারে। v & m0 সাইজ মাস্ক ব্যবহার করে v-এর শুধু লাস্ট n ডিজিট রাখে, এবং টেবিলে একটি ভ্যালিড ইনডেক্স ইয়িল্ড করে।
আপনি ইতিমধ্যে অনুমান করতে পারেন bucketfn কেন। bucketfn কলার দ্বারা প্রদত্ত এবং এলিমেন্টের প্রতিটি বাকেটে অ্যাপ্লাই করা হয়। এটিকে privdata-ও পাস করা হয়, যেটি অ্যারবিট্রারি ডেটা যা dictScan()-এ কলার দ্বারা পাস করা হয়েছে। একই ফ্যাশনে, fn সব এন্ট্রিতে একে এক করে অ্যাপ্লাই করা হয়। লক্ষ্য করুন যে একটি বাকেট খালি হতে পারে, এই কেসে এর ভ্যালু NULL।
ঠিক আছে, আমরা একটি বাকেট এলিমেন্টের ওপর ইটারেট করলাম। এরপর কী? আমরা পরবর্তী কলের জন্য কার্সর ভ্যালু রিটার্ন করব dictScan()। এটি করা হয় বর্তমান কার্সর v ইনক্রিমেন্ট করে, কিন্তু একটি টুইস্ট দিয়ে! কার্সরটি প্রথম রিভার্স হয়, তারপর ইনক্রিমেন্ট হয়, এবং তারপর আবার রিভার্স হয়:
/* Set unmasked bits so incrementing the reversed cursor
* operates on the masked bits */
v |= ~m0;
/* Increment the reverse cursor */
v = rev(v);
v++;
v = rev(v);প্রথমে, v |= ~m0 v-এ নন-মাস্কড বিটসকে ১ সেট করে। এর ইফেক্ট হলো যখন v রিভার্স এবং ইনক্রিমেন্ট হয়, এই বিটসই ইফেক্টিভলি ইগনোর করা হবে। তারপর, v রিভার্স হয়, ইনক্রিমেন্ট হয়, এবং আবার রিভার্স হয়। একটি উদাহরণ দেখি:
Table size = 16 (n = 4, m0 = 16-1 = 00001111)
v = 00001000 (Current cursor)
v |= ~m0; // v == 11111000 (~m0 = 11110000)
v = rev(v); // v == 00011111
v++; // v == 00100000
v = rev(v); // v == 00000100এই বিট-ম্যাজিকের পর, v রিটার্ন করা হয়।
কার্সরটি কেন রিভার্স করা হয় ইনক্রিমেন্ট করার আগে? টেবিলটি ইটারেশনের মাঝপথে বড় হতে পারে। এটি গ্যারান্টি দেয় কার্সরটি ভ্যালিড থাকে। যখন টেবিল বড় হয়, এডিশনাল বিটস এর সাইজ মাস্কে বাম পাশ থেকে যোগ হয়। রিভার্সড নম্বর ইনক্রিমেন্ট করে, আমরা ছোট টেবিলের ইন্ডেক্সগুলো বড় টেবিলে এক্সপ্যান্ড করতে পারি।
উদাহরণস্বরূপ: ধরি পুরনো টেবিলের সাইজ ছিল ১৬ (সাইজ মাস্ক 00001111) এবং কার্সর ছিল 00001000। যখন টেবিল ৩২ এলিমেন্টে বড় হয় এর সাইজ মাস্ক হবে 00011111। পুরনো টেবিলের 00001000 স্লটে থাকা সব এলিমেন্ট নতুন টেবিলে হয় 00001000 অথবা 00011000-এ ম্যাপ হবে। এই কার্সরগুলো ছোট এবং বড় দুটো টেবিলই কে কম্প্যাটিবল!
২. টেবিল rehashing-এর সময় স্ক্যানিং
শেষ পার্ট যা আমাদের বুঝতে হবে সেটি হলো স্ক্যানটি rehashing-এর সময় কীভাবে কাজ করে। ইনক্রিমেন্টাল rehashing dict.c-এ ইমপ্লিমেন্ট করা হয়েছে একসাথে দুটি এক্টিভ টেবিল রেখে। একটি সেকেন্ড টেবিল তৈরি হয় যখন হ্যাশ টেবিল রিসাইজ হয়। নতুন আইটেমগুলো নতুন টেবিলে যোগ হয়। প্রতিটি rehash স্টেপে পুরনো টেবিল থেকে এলিমেন্টগুলো নতুন টেবিলে মুভ করা হয়। যখন পুরনো টেবিল খালি হয়ে যায় সেটি রিমুভ করা হয়।
একটি স্ক্যান পারফর্ম করার সময়, পুরনো এবং নতুন উভয় টেবিল স্ক্যান করা হয় এলিমেন্টের জন্য, ছোট টেবিল থেকে শুরু করে। ছোট টেবিলের আইটেমগুলো স্ক্যান হওয়ার পর, কমপ্লিমেন্টিং আইটেমস বড় টেবিল থেকে স্ক্যান করা হয়। এইভাবে কার্সর v দ্বারা কভার করা সব এলিমেন্ট স্ক্যান হয়। দেখি কীভাবে দেখে। এটি পুরো কোড স্নিপেট, আমরা নিচে ব্রেক ডাউন করব:
} else {
// dictIsRehashing(d)
t0 = &d->ht[0];
t1 = &d->ht[1];
/* Make sure t0 is the smaller and t1 is the bigger table */
if (t0->size > t1->size) {
t0 = &d->ht[1];
t1 = &d->ht[0];
}
m0 = t0->sizemask;
m1 = t1->sizemask;
/* Emit entries at cursor */
if (bucketfn) bucketfn(privdata, &t0->table[v & m0]);
de = t0->table[v & m0];
while (de) {
next = de->next;
fn(privdata, de);
de = next;
}
/* Iterate over indices in larger table that are the expansion
* of the index pointed to by the cursor in the smaller table */
do {
/* Emit entries at cursor */
if (bucketfn) bucketfn(privdata, &t1->table[v & m1]);
de = t1->table[v & m1];
while (de) {
next = de->next;
fn(privdata, de);
de = next;
}
/* Increment the reverse cursor not covered by the smaller mask.*/
v |= ~m1;
v = rev(v);
v++;
v = rev(v);
/* Continue while bits covered by mask difference is non-zero */
} while (v & (m0 ^ m1));
}প্রথমে সব, t0 এবং t1 ব্যবহার করা হয় ছোট এবং বড় টেবিল সংরক্ষণ করতে যথাক্রমে, m0 এবং m1 সাইজ মাস্ক দুটোর জন্য। তারপর ছোট টেবিল স্ক্যান করা হয়, ঠিক যেমন আমরা আগে দেখেছিলাম।
পরবর্তী, কার্সরটি ব্যবহার করা হয় বড় টেবিলে ইনডেক্স করতে, বড় সাইজ মাস্ক m1 ব্যবহার করে: de = t1->table[v & m1]। ইনার লুপে, কার্সরটি ইনক্রিমেন্ট করা হয় ছোট টেবিলের বাকেট দ্বারা কভার করা রেঞ্জের সব এক্সপ্যানশন কভার করতে।
উদাহরণস্বরূপ, যদি ছোট টেবিলে বাকেটের ইনডেক্স ছিল 0100, এবং বড় টেবিল দ্বিগুণ বড়, এই লুপে কভার করা ইন্ডেক্সগুলো হবে 00100 এবং 10100। do-while-এর কন্ডিশন কার্সরকে ছোট টেবিলের বাকেট দ্বারা কভার করা রেঞ্জের বাইরে ইনক্রিমেন্ট হতে বাধা দেয়: while (v & (m0 ^ m1));। এটিকে আপনার বুঝতে ছাড়ছি :)
এটি ছিল পুরো হ্যাশ টেবিল স্ক্যান ফাংশন। একমাত্র অনুপস্থিত পিস হলো rev(v) ইমপ্লিমেন্টেশন, যেটি একটি জেনারেল ফাংশন একটি নম্বরের বিটস রিভার্স করতে। dict.c-এ ব্যবহৃত ইমপ্লিমেন্টেশন নির্দিষ্টভাবে আকর্ষণীয় কারণ এটি O(log n) রানিং টাইম অর্জন করে। আমি এটি ভবিষ্যতে একটি পোস্টে কভার করতে পারি।
পড়ার জন্য ধন্যবাদ! Dvir Volk-এর ইনস্পিরেশন এবং সাপোর্টের জন্য অনেক ধন্যবাদ! Jason Li-এর ফিডব্যাকের জন্য ধন্যবাদ যা পোস্টে একটি এরর কোরেক্ট করতে সাহায্য করল।
