রেডিস হ্যাশ টেবিল স্ক্যান ব্যাখ্যা করা হয়েছে:মেকানিজমের ভিতরে

এহুদ তামির দ্বারা

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

Redis হল একটি মূল-মান ডাটাবেস। ডাটাবেসের প্রতিটি এন্ট্রি একটি কী থেকে একটি মান পর্যন্ত একটি ম্যাপিং। মান বিভিন্ন ধরনের হতে পারে. পূর্ণসংখ্যা, তালিকা, হ্যাশ টেবিল এবং আরো আছে. পর্দার আড়ালে, ডাটাবেস নিজেই একটি হ্যাশ টেবিল। এই পোস্টে, আমরা Redis-এ SCAN কমান্ড অন্বেষণ করব।

_By © User:Colin/ Wikimedia Commons, CC BY-SA 4.0, [https://commons.wikimedia.org/w/index.php?curid=30343877](https://commons.wikimedia.org/w/index.php?curid=30343877" rel="noopener" target="blank" title=")

Redis SCAN

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

SCAN কমান্ডের কিছু আকর্ষণীয় বৈশিষ্ট্য রয়েছে:

1. এটি গ্যারান্টি দেয় যে টেবিলে উপস্থিত সমস্ত আইটেম অন্তত একবার ফেরত দেওয়া হবে .
2. এটি রাষ্ট্রহীন . টেবিলটি তার সক্রিয় স্ক্যানার সম্পর্কে কোনো ডেটা সংরক্ষণ করে না। এর মানে এই যে স্ক্যান ডাটাবেস লক করে না।
3. এটি টেবিলের আকার পরিবর্তনের জন্য স্থিতিস্থাপক। O(1) অ্যাক্সেস সময় বজায় রাখতে, হ্যাশ টেবিল একটি নির্দিষ্ট লোড ফ্যাক্টর বজায় রাখে। লোড ফ্যাক্টর একটি নির্দিষ্ট সময়ে টেবিল কতটা "পূর্ণ" তা পরিমাপ করে। যখন লোড ফ্যাক্টর খুব বড় বা খুব ছোট হয়ে যায়, তখন টেবিলের আকার পরিবর্তন করা হয়। টেবিলের আকার পরিবর্তন করার সময় কল করলেও SCAN তার গ্যারান্টি বজায় রাখবে।

বাস্তবায়ন

স্ক্যান dictScan() ফাংশনে dict.c-এ প্রয়োগ করা হয়েছে . এটি হল ফাংশনের স্বাক্ষর এবং অতিরিক্ত হাউসকিপিং:

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;
 // ...

লক্ষণীয় বিষয়:

• ফাংশনটি 5টি প্যারামিটার গ্রহণ করে:dict *d , অভিধানটি স্ক্যান করা হবে, unsigned long v , কার্সার, এবং 3টি অন্যান্য প্যারামিটার যা আমরা পরে পাব।
• ফাংশনটি এই ফাংশনের পরবর্তী কলে কার্সারের মান প্রদান করে। যদি ফাংশনটি 0 প্রদান করে, তাহলে এর মানে হল স্ক্যান করা হয়েছে।
• if (dictSize(d) == 0) return 0; . যখন অভিধানটি খালি থাকে তখন ফাংশনটি 0 প্রদান করে যে স্ক্যান করা হয়েছে।

1. সাধারণ স্ক্যানিং

নিম্নলিখিত কোড উপাদানগুলির একটি গুচ্ছ স্ক্যান করে:

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;

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

হ্যাশ টেবিলের একটি পয়েন্টার স্থানীয় ভেরিয়েবল t0 এ সংরক্ষিত হয় , এবং এর সাইজ মাস্ক m0 এ সংরক্ষিত আছে . আকারের মুখোশ: dict.c হ্যাশ টেবিল সবসময় 2^n হয় আকারে একটি প্রদত্ত টেবিলের আকারের জন্য, মাস্ক মাস্ক হল 2^n-1 , যা তার n সহ একটি বাইনারি সংখ্যা সর্বনিম্ন-গুরুত্বপূর্ণ বিট 1 এ সেট করা হয়েছে। উদাহরণস্বরূপ, n=4; 2^n-1 = 00001111 এর জন্য . একটি প্রদত্ত কীটির জন্য, হ্যাশ টেবিলে এর অবস্থানটি হবে শেষ 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 ট্যাবলe. v & এর সূচীযোগ্য পরিসরের বাইরে হতে পারে m0 শুধুমাত্র las রাখতে সাইজ মাস্ক ব্যবহার করে t n সংখ্যা o f v, এবং সারণীতে একটি বৈধ সূচক দেয়।

আপনি হয়ত এতক্ষণে অনুমান করে ফেলেছেন কি 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-এ সমস্ত নন-মাস্কড বিট সেট করে 1. প্রভাব হল যে যখন 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 ফেরত দেওয়া হয়।

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

উদাহরণস্বরূপ:ধরা যাক পুরানো টেবিলের আকার ছিল 16 (সাইজ মাস্ক 00001111 ) এবং কার্সার ছিল 00001000 . যখন টেবিলটি 32টি উপাদানে বৃদ্ধি পাবে তখন এর আকারের মাস্ক হবে 00011111 . পূর্বে 00001000 এর সমস্ত উপাদান স্লট 00001000-এ ম্যাপ করবে অথবা 00011000 নতুন টেবিলে। এই কার্সারগুলি ছোট এবং বড় উভয় টেবিলের সাথে সামঞ্জস্যপূর্ণ!

2. টেবিল রিহ্যাশ করার সময় স্ক্যান করা হচ্ছে

শেষ অংশটি আমাদের বুঝতে হবে যে টেবিলটি রিহ্যাশ করার সময় স্ক্যানটি কীভাবে কাজ করে। ক্রমবর্ধমান রিহ্যাশিং একই সময়ে দুটি সক্রিয় টেবিল থাকার দ্বারা dict.c এ প্রয়োগ করা হয়। হ্যাশ টেবিলের আকার পরিবর্তন করা হলে একটি দ্বিতীয় টেবিল তৈরি করা হয়। নতুন আইটেম নতুন টেবিল যোগ করা হয়. প্রতিটি রিহ্যাশ ধাপে পুরানো টেবিল থেকে উপাদানগুলি নতুন টেবিলে সরানো হয়। পুরানো টেবিলটি খালি হয়ে গেলে এটি সরানো হয়৷

একটি স্ক্যান করার সময়, ছোট থেকে শুরু করে, উপাদানগুলির জন্য পুরানো এবং নতুন উভয় টেবিল স্ক্যান করা হয় টেবিল . ছোট টেবিলের আইটেমগুলি স্ক্যান করার পরে, পরিপূরক আইটেমগুলি৷ বড় টেবিল থেকে স্ক্যান করা হয়. এইভাবে কার্সার দ্বারা আচ্ছাদিত সমস্ত উপাদান 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 . করণীয় অবস্থা ছোট টেবিলের বালতি দ্বারা আচ্ছাদিত সীমার বাইরে কার্সারকে বৃদ্ধি করা থেকে বাধা দেয়:while (v & (m0 ^ m1)); . আমি এই শেষ বিট বুঝতে আপনার উপর ছেড়ে দেব :)

এটাই! আমরা সম্পূর্ণ হ্যাশ টেবিল স্ক্যান ফাংশন কভার করেছি। একমাত্র অনুপস্থিত অংশ হল rev(v) এর বাস্তবায়ন , যা একটি সংখ্যার বিটগুলিকে বিপরীত করার জন্য একটি সাধারণ ফাংশন। dict.c-এ ব্যবহৃত বাস্তবায়নটি বিশেষভাবে আকর্ষণীয় কারণ এটি একটি O(log n) চলমান সময় অর্জন করে। আমি ভবিষ্যতে একটি পোস্টে এটি কভার করতে পারি।

পড়ার জন্য ধন্যবাদ! তার অনুপ্রেরণা এবং সমর্থন জন্য Dvir Volk অনেক ধন্যবাদ! জেসন লিকে তার প্রতিক্রিয়ার জন্য ধন্যবাদ যা আমাকে পোস্টে একটি ত্রুটি সংশোধন করতে সাহায্য করেছে৷

বিনামূল্যে কোড শিখুন. freeCodeCamp-এর ওপেন সোর্স পাঠ্যক্রম 40,000-এরও বেশি লোককে ডেভেলপার হিসেবে চাকরি পেতে সাহায্য করেছে। শুরু করুন