গড়, মধ্যক ও প্রচুরক

গড় শব্দটির সঙ্গে তোমরা যারা স্কুলে বিষয়টি পড়ে ফেলেছ, তারা যেমন পরিচিত, তেমনি যারা ক্রিকেট খেলা দেখো, তারাও পরিচিত। এই বইটি যখন লেখা হচ্ছে, তখন তামিম ইকবালের টেস্ট ক্রিকেটে ব্যাটিং গড় হচ্ছ 40.34 আর সাকিব আল হাসানের 40.93। এই গড় কিভাবে হিসেব করা হলো আর এর মানেই বা কী?

আমাকে যদি দুটি সংখ্যা দিয়ে এদের গড় বের করতে বলা হয়, তখন আমি সংখ্যা দুটি যোগ করে দুই দিয়ে ভাগ করবো। যেমন : 5 ও 6, এই দুটি সংখ্যার গড় হচ্ছে (5 + 6) / 2 বা 11 / 2 বা 5.5। তিনটি সংখ্যা 6, 7, 8-এর গড় হচ্ছে (6 + 7 + 8) / 3 বা 21 / 3 বা 7। তাহলে আমাকে যদি n সংখ্যক সংখ্যা দেওয়া হয়, তাহলে তাদের গড় বের করতে হলে সবগুলো সংখ্যা যোগ করে n দিয়ে ভাগ করবো। তাহলেই হয়ে গেলো।

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

def average(li):
   s = sum(li)
   n = len(li)
   return s / n

li = [1, 2, 3]
print("Average:", average(li))
li = [10, 20, 30, 40, 50, 60, 70, 80]
print("Average:", average(li))
li = [-1, 0, 1]
print("Average:", average(li))

প্রোগ্রামটি রান করলে আমরা আউটপুট পাবো এরকম :

Average: 2.0
Average: 45.0
Average: 0.0

ক্রিকেট খেলায় ব্যাটিং গড় কিভাবে বের করে? মোট রানকে ইনিংস দিয়ে ভাগ করতে হয়। তবে একটি মজার বিষয় হচ্ছে, কোনো ইনিংসে অপরাজিত থাকলে, অর্থাৎ, আউট না হলে, সেই ইনিংসকে ভাগ করার সময় গণনা করা হয় না। ধরা যাক, কোনো ব্যাটসম্যান প্রথম খেলায় করলো 50 রান, দ্বিতীয় খেলায় 100 রান (অপরাজিত), তৃতীয় খেলায় আবারো 50 রান করে আউট হলো। তাহলে তার ব্যাটিং গড় হবে, (50 + 100 + 50) / 2, বা 200 / 2 বা 100। এখানে 3 এর বদলে 2 দিয়ে ভাগ করার কারণ হচ্ছে, দ্বিতীয় খেলায় সে অপরাজিত ছিল।

এখন গড় আমাদের কী কাজে লাগে? ধরা যাক, আন্তর্জাতিক ক্রিকেট খেলায় নতুন একটি দেশের আগমন ঘটলো এবং বাংলাদেশের সঙ্গে ওই দলের খেলা। টসে হেরে ওই দল প্রথমে ব্যাটিং পেল। এখন ওদের যেই দুজন ব্যাটসম্যান ইনিংস ওপেন করতে এসেছে, ঘরোয়া লিগে একজনের ব্যাটিং গড় হচ্ছে 26 আরেকজনের হচ্ছে 41। এই তথ্য থেকে তুমি দুজন ব্যাটসম্যানের মধ্যে তুলনা করতে পারো যে, কে তুলনামূলক ভালো ব্যাটসম্যান। তবে আজকের ম্যাচে কে কত রান করবে, এটি কিন্তু ব্যাটিং গড়ের ওপর নির্ভর করে না। কারও ব্যাটিং গড় 26 মানে এই নয় যে, সে প্রতি ইনিংসে 26 রান করে। তাহলে গড় হচ্ছে কোনো কিছুর মান সম্পর্কে ধারনা করার জন্য একটি টুল মাত্র। ইংরেজিতে একে average বলে, তবে গণিতের ক্ষেত্রে mean শব্দটিই বেশি ব্যবহার করা হয়।

এখন আরেকটি উদাহরণ দেই। কোনো দেশের মানুষ কেমন ধনী বা গরিব, তা বোঝার জন্য অনেকসময় মাথাপিছু আয় ব্যবহার করা হয়। মাথাপিছু আয় মানে হচ্ছে গড় আয়। সেটি ব্যবহার করে সেই দেশের মানুষের অর্থনৈতিক অবস্থা সম্পর্কে ধারণা পাওয়া যায়। কিন্তু সেখানে যদি মানুষের আয়ের মধ্যে বৈষম্য অনেক বেশি হয়, তাহলে কিন্তু গড় ব্যবহার করে প্রকৃত ধারণা পাওয়া যাবে না। একটি উদহারণ দিয়ে বোঝাই। ধরা যাক, কোনো দেশে 10 জন মানুষ আছে। তাদের মধ্যে 2 জন প্রতি মাসে 10 হাজার টাকা আয় করে। 5 জন প্রতিমাসে 20 হাজার টাকা আয় করে। আর একজন আয় করে প্রতিমাসে 30 হাজার টাকা। বাকী দুইজন প্রতি মাসে 5 লক্ষ টাকা আয় করে। তাহলে প্রতিমাসে তাদের গড় আয় কত?

গড় আয় = (10000 + 10000 + 20000 + 20000 + 20000 + 20000 + 20000 + 30000 + 500000 + 500000) / 10 = 115000।
তার মানে গড় আয় এক লক্ষ পনের হাজার টাকা! তাহলে শুধু গড় আয় জানলে যেকেউ সেই দেশের মানুষকে ধনী ভাববে। তাই গড় ব্যবহার করে সবসময় প্রকৃত চিত্র পাওয়া যায় না। তবে এতে হতাশ হওয়ার কিছু নেই, কারণ আমাদের হাতে রয়েছে মধ্যক ও প্রচুরক।

মধ্যক

এখন ধরা যাক, তুমি কোনো ক্রিকেট দলের ম্যানেজার। তোমার দল তৈরির সময় দুই জন ব্যাটসম্যান – রবিন ও সমিত-এর মধ্যে একজনকে বেছে নিতে হবে। দুজনের মধ্যে যার ব্যাটিং গড় বেশি, তুমি তাকে দলে নিতে পারো। কিন্তু তুমি যদি আরেকটু সচেতন হও, তখন হয়ত তুমি জানতে চাইতে পারো যে, কে কতগুলো ম্যাচ খেলেছে। ধরা যাক, রবিন 50 টি ম্যাচ খেলেছে এবং তার ব্যাটিং গড় 30। আর সমিত খেলেছে 5টি ম্যাচ এবং তার ব্যাটিং গড় 38। তুমি কিন্তু বেশিরভাগ ক্ষেত্রেই রবিনকে দলে নেবে, যেহেতু সে সমিতের তুলনায় অনেক বেশি অভিজ্ঞ। কিন্তু দুইজন যদি সমান সংখ্যক ম্যাচ খেলে, তখন কি কেবল গড় হিসেব করবে? তুমি চাইলে তখন আরেক ধরনের টুল ব্যবহার করতে পারো, যার নাম মধ্যক (ইংরেজিতে বলে median)। ধরা যাক, রবিন ও সমিত – দুজনেই 10টি করে ম্যাচ খেলেছে। 10টি ম্যাচে রবিনের রান হচ্ছে 95, 88, 47, 0, 10, 1, 5, 12, 0, 3। আর সমিতের রান হচ্ছে 10, 40, 20, 37, 0, 1, 25, 35, 30, 33। রবিনের গড় রান সমিতের গড় রানের চেয়ে বেশি। তবে এখানে আমরা দেখতে পাচ্ছি, রবিন মাঝে-মধ্যে অনেক বেশি রান করে, তবে বেশিরভাগ সময়ই সে খুব একটা ভালো খেলে না। আর সমিত দুয়েকটা বাদের বাকি খেলাগুলোয় মোটামুটি রান করতে পারে। তাই শুধু গড়ের ওপর ভরসা করা আমাদের ঠিক হবে না। আমরা মধ্যক বের করবো। প্রথমে আমরা তাদের প্রতি ম্যাচের রান ছোট থেকে বড় ক্রমানুসারে সাজাবো। তাহলে রবিনের রান হবে 0, 0, 1, 3, 5, 10, 12, 47, 88, 95 আর সমিতের রান হবে 0, 1, 10, 20, 25, 30, 33, 35, 37, 40। মধ্যক বের করতে গেলে আমাদেরকে তালিকার মাঝামাঝি সংখ্যাটি নিতে হবে। মোট সংখ্যা যদি বিজোড় হয়, তাহলে মাঝামাঝি সংখ্যা হবে একটি। যেমন 11-এর ক্ষেত্রে 6 নম্বর সংখ্যাটি হচ্ছে মাঝামাঝি সংখ্যা। কারণ ওই সংখ্যার চেয়ে ছোট 5টি সংখ্যা আছে। আবার বড় সংখ্যাও আছে 5টি। কিন্তু জোড় সংখ্যার বেলায় একটি মাঝামাঝি সংখ্যা বের করা যায় না। যেমন 10টি সংখ্যার ক্ষেত্রে আমরা যদি 5 নম্বর সংখ্যাটিকে মাঝামাঝি সংখ্যা ধরি, তাহলে তার ছোটি 4টি আর তার বড় 5টি সংখ্যা থাকবে। আবার 6 নম্বর সংখ্যাকে মাঝামাঝি সংখ্যা ধরলে, তার ছোট 5টি আর বড় 4টি সংখ্যা থাকবে।

যেহেতু আমাদের 10 টি সংখ্যা, তাই আমরা 5 ও 6 নম্বর সংখ্যা দুটি নিয়ে তাদের গড় বের করবো, মানে সংখ্যা দুটি যোগ করে দুই দিয়ে ভাগ করবো। তাহলে রবিনের রানের মিডিয়ান হবে 7.5 আর সমিতের রানের মিডিয়ান হবে 27.5। এখানে আমরা মিডিয়ান ব্যবহার করে সিদ্ধান্ত নিতে পারি যে কাকে দলে নেব। কাজটি তোমরা খাতা কলমে করে ফেল, তবে আমি পাইথন ব্যবহার করে একটি প্রোগ্রাম লিখে দেখাবো।

def median(li):
   li.sort()
   count = len(li)
   if count == 0:
      return None
   if count % 2 == 1:
      mid = count // 2
      return li[mid]
   else:
      mid2 = count // 2
      mid1 = mid2 - 1
      return (li[mid1]+li[mid2])/2

robin_run = [95, 88, 47, 0, 10, 1, 5, 12, 0, 3]
shomit_run = [10, 40, 20, 37, 0, 1, 25, 35, 30, 33]

median_robin = median(robin_run)
median_shomit = median(shomit_run)

print("Median run for Robin", median_robin)
print("Median run for Shomit", median_shomit)

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

প্রচুরক

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

একটি ওয়ানডে ম্যাচে একজন বোলারের পক্ষে সর্বোচ্চ ও সর্বনিম্ন কয়টি উইকেট পাওয়া সম্ভব? উত্তর হবে, যথাক্রমে 10টি ও 0টি। 0-এর চেয়ে কম কিংবা 10-এর চেয়ে বেশি উইকেট পাওয়া সম্ভব নয়। এখন ধরা যাক, মোস্তাফিজ এখন পর্যন্ত 20টি ওয়ানডে ম্যাচে বোলিং করেছে। সেই খেলাগুলোতে সে প্রতি খেলায় যতগুলো উইকেট পেয়েছে, তা হচ্ছে : 6, 5, 6, 4, 3, 1, 3, 2, 1, 0, 5, 3, 3, 2, 2, 1, 3, 4, 3, 3। এখন আমি একটি তালিকা তৈরি করবো, যে মোস্তাফিজ 0 উইকেট পেয়েছে কতবার, 1 উইকেট পেয়েছে কতবার … এরকম।

উইকেট ম্যাচের সংখ্যা
0 1
1 3
2 3
3 7
4 2
5 2
6 2
7 0
8 0
9 0
10 0

তাহলে আমরা দেখতে পাচ্ছি, মোস্তাফিজ সবচেয়ে বেশি পেয়েছে 3 উইকেট। 20টি খেলার মধ্যে 7 টি খেলাতেই সে 3 উইকেট করে পেয়েছে। তাহলে তুমি ধরে নিতে পারো যে, আজকের খেলাতে মোস্তাফিজের 3 উইকেট পাওয়ার সম্ভাবনাই সবচেয়ে বেশি। এখানে প্রচুরক হচ্ছে 3। কারণ উইকেটের লিস্টে 3 সবচেয়ে বেশি বার আছে। আমরা এখন ওপরের হিসেবটা একটি পাইথন প্রোগ্রাম লিখে করবো।

wkts_list = [6, 5, 6, 4, 3, 1, 3, 2, 1, 0, 5, 3, 3, 2, 2, 1, 3, 4, 3, 3]

for item in range(11):
   print("Wicket:", item, "Count:", wkts_list.count(item))

প্রোগ্রামটি রান করলে আউটপুট আসবে এরকম :

Wicket: 0 Count: 1
Wicket: 1 Count: 3
Wicket: 2 Count: 3
Wicket: 3 Count: 7
Wicket: 4 Count: 2
Wicket: 5 Count: 2
Wicket: 6 Count: 2
Wicket: 7 Count: 0
Wicket: 8 Count: 0
Wicket: 9 Count: 0
Wicket: 10 Count: 0

যে ঘটনাটি সবচেয়ে বেশি সংখ্যক বার ঘটে, সেটিই হচ্ছে প্রচুরক। বিভিন্ন রকম মতামত জরিপ করতে প্রচুরক ব্যবহার করা হয়। যেমন ধরো, তুমি একটি নতুন মোবাইল ফোন কিনতে চাও। কিন্তু কোন ব্র্যান্ডের ফোন ভালো সেটা বুঝতে পারছ না। তখন তুমি তোমার বন্ধুদের জিজ্ঞাসা করতে পারো এবং সবচেয়ে বেশি সংখ্যক বন্ধু যেই ব্র্যান্ডের মোবাইল ফোন ব্যবহার করে বা ভালো বলে, সেই ব্র্যান্ডের ফোন কিনতে পারো।

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

বাইনারি সার্চ-এর কোড

আজকে সকালে গো (Go) প্রোগ্রামিং ল্যাঙ্গুয়েজে একটু কোডিং প্র্যাকটিস করার জন্য বাইনারি সার্চ ফাংশন লিখলাম, তারপরে ইউনিট টেস্ট লিখলাম (টেবল ড্রিভেন টেস্ট)। তো এমন সময় আমার মনে হলো লাইব্রেরি ফাংশনগুলো কিভাবে ইমপ্লিমেন্ট করা, সেটা দেখা দরকার। তো গো এর লাইব্রেরিতে যে বাইনারি সার্চ আছে, তার কোড (এবং ডকুমেন্টেশন) দেখে তো আমি মুগ্ধ!
এটা হচ্ছে গো-এর কোড:

func Search(n int, f func(int) bool) int {
    // Define f(-1) == false and f(n) == true.
    // Invariant: f(i-1) == false, f(j) == true.
    i, j := 0, n
    for i < j {
	h := i + (j-i)/2 // avoid overflow when computing h 
        if !f(h) { 
            i = h + 1 // preserves f(i-1) == false 
        } else { 
            j = h // preserves f(j) == true 
        } 
    } 
    return i
}

ওপরের কোডটুকু দেখলে আসলে পুরোপুরি বোঝা যাবে না কেন আমি এত মুগ্ধ। এই লিঙ্কে গেলে বিষয়টা আরো পরিষ্কার হবে: https://golang.org/src/sort/search.go। কোডের চেয়ে ডকুমেন্টেশন অনেক বেশি। আর এই বেশি ডকুমেন্টেশনসহ কোড হচ্ছে ১১৩ লাইন। কিন্তু বিষয় এখানেই শেষ নয়। আমার তারপরে চিন্তা আসল, আচ্ছা, এত সুন্দর কোড আর ডকুমেন্টেশন – এই কোডের টেস্ট কোড (ইউনিট টেস্ট) ওরা কিভাবে লিখল? তার জন্য চলে গেলাম এই লিঙ্কেঃ https://golang.org/src/sort/search_test.go। ১১৩ লাইনের search.go এর জন্য search_test.go তে আছে ১৬২ লাইন। এই দুইটা ফাইলের কোড এবং ডকুমেন্টেশন ঠিকমতো পড়লে শেখার আছে অনেক কিছুই।

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

void *
bsearch (register const void *key, const void *base0,
    size_t nmemb, register size_t size,
    register int (*compar)(const void *, const void *))
{
    register const char *base = (const char *) base0;
    register int lim, cmp;
    register const void *p;

    for (lim = nmemb; lim != 0; lim >>= 1) {
        p = base + (lim >> 1) * size;
        cmp = (*compar)(key, p);
        if (cmp == 0)
            return (void *)p;
        if (cmp > 0) {	/* key > p: move right */
            base = (const char *)p + size;
            lim--;
        } /* else move left */
    }
    return (NULL);
}

এই কোডটাও বেশ সুন্দর, গুছানো। ডকুমেন্টেশনও ভালো। আর পয়েন্টার দেখে ভয় পাওয়ার কারণ নাই (পয়েন্টার নিয়ে আমি কম্পিউটার প্রোগ্রামিং ২য় খণ্ড বইতে বিস্তারিত আলোচনা করেছি অনেক উদাহরণসহ)। তবে এখানে গিয়ে পুরো ফাইলটা না দেখলে এর মর্ম বোঝা যাবে না : https://github.com/gcc-mirror/gcc/blob/master/libiberty/bsearch.c

গো আর সি-এর কোড যেহেতু দেখলাম, পাইথনের কোডটাও দেখা যাক। তাই সেটাও সার্চ করে বের করে ফেললাম :

def bisect_left(a, x, lo=0, hi=None):
    """Return the index where to insert item x in list a, assuming a is sorted.

    The return value i is such that all e in a[:i] have e < x, and all e in a[i:] have e >= x.  So if x already appears in the list, a.insert(x) will
    insert just before the leftmost x already there.

    Optional args lo (default 0) and hi (default len(a)) bound the
    slice of a to be searched.
    """

    if lo < 0:
        raise ValueError('lo must be non-negative')
    if hi is None:
        hi = len(a)
    while lo < hi:
        mid = (lo+hi)//2
        if a[mid] < x: lo = mid+1
        else: hi = mid
    return lo

গো আর সি এর তুলনায় বেশ সহজ! তবে ডকুমেন্টেশন সংক্ষিপ্ত হলেও ভালো। এখানে গিয়ে পুরো কোড দেখা যাবে : https://github.com/python-git/python/blob/master/Lib/bisect.py

তারপরে ভাবলাম, আমার ব্লগের পাঠকদেরকে বিষয়টা জানানো যাক। আশা করি, বিশ্বমানের প্রোগ্রামারদের কোডের সঙ্গে পাঠকদের কিছুটা হলেও পরিচয় করিয়ে দিতে পেরেছি। কোডিং সঠিক হোক, কোড সুন্দর হোক।

হ্যাশ ফাংশন – ২

লেখকঃ বজলুর রহমান রোকন
লেখকঃ বজলুর রহমান রোকন

আগের পোস্টের সমস্যাটি হলো- দুটি ভিন্ন ভিন্ন স্ট্রিং হ্যাশ ফাংশনে দিলে যদি একই ভ্যালু পাওয়া যায় তাহলে কী হবে? উত্তরটির জন্য পুরো আর্টিক্যাল পড়তে হবে।

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

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

h1

h2

উপরের ছবি দুটি থেকে দেখতে পাচ্ছো, আদা, কলা, পেঁপে, রসুন এবং মরিচ এগুলোর হ্যাশ ভ্যালু যথাক্রমে ১,২,৩ ও ৭, ৮। সুতরাং এগুলো অ্যারের ০,১,২ ও ৬,৭ নম্বর ইন্ডেক্সে বসনো হয়েছে। কিন্তু জীবন তো আর পুষ্পশয্যা নয়। একটু পরেই এসেছে আম। আর তোমার হ্যাশ ফাংশন এর জন্যে ভ্যালু রিটার্ন করেছে ১।

সমস্যাটি নিশ্চয় বুঝতে পারছো। এই সমস্যাকে বলা হয় কলিশন (collision)। এখন তুমি যদি অ্যারের ১ নম্বর ইনডেক্সে আমের দাম রাখো, তাহলে আগের আদার দামের সাথে এটি রিপ্লেস হয়ে যাবে। এতে করে তুমি যদি পরবর্তীতে আদার দাম দাও, তোমার হ্যাশটেবিল আমের দাম দিয়ে দিবে যা হওয়া উচিৎ নয়।

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

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

তবে এতেও একটি সমস্যা আছে। তোমার মুদির দোকানের সবগুলো পণ্য যদি একটি নির্দিষ্ট বর্ণ দিয়ে শুরু হয় তাহলে প্রথম স্লটে একটি বিশাল চেইন হবে। এক্ষেত্রে হ্যাশ টেবিল থেকে কোন পণ্যের দাম খুঁজে আনার সময় আর O(1) থাকবে না বরং সেটি হয়ে যাবে O(n)। কারণ তখন তোমাকে লিংকডলিস্ট থেকে উপাদানটি খুঁজতে হবে। লিংকডলিস্ট থেকে কোন উপাদান খুঁজে বের করতে সময় লাগে O(n)।

h3

উপরের ছবি থেকে নিশ্চয় দেখতে পাচ্ছো সমস্যাটি কোথায়? তোমার অ্যারের বাকি স্লটগুলো প্রায় খালি রয়ে গেছে।
তাহলে এখান থেকে দুটি বিষয় জানা গেলো –
১. হ্যাশ ফাংশন অনেক গুরুত্বপুর্ণ। এটি খুব সিম্পল হলে সমস্যা।
২. প্রত্যেকটি স্লটেই যদি অনেক বড় লিংকলিস্ট থাকে, তাহলে কনস্ট্যান্ট টাইম অর্থাৎ O(‌1) সময়ে তুমি উপাদান খুঁজে বের করতে পারছো না।
এখন যদি তুমি একটি ভালো হ্যাশ ফাংশন লিখতে পারো, এবং প্রত্যেক স্লটেই যাতে বিশাল লিংকডলিস্টের চেইন না হয় তা নিশ্চিত করতে পারো তাহলেই O(‌1) সময়ে হ্যাশ টেবিল থেকে ভ্যালু পড়তে পারবে।

এবার Load Factor বলে একটা টার্ম আছে, এটি নিয়ে একটু বলি তোমাদের। একটি হ্যাশটেবিলের লোড ফ্যাক্টর খুব সহজেই বের করা যায়।

Load Factor = Number of items in the hash table / Total slot in the array
তাহলে তোমার অ্যারেতে যদি স্লট হয় 10 এবং উপাদানের সংখ্যা যদি হয় ৭ তাহলে লোড ফ্যাক্টর হবে- 0.7। এটি দিয়ে একটি হ্যাশটেবলি কতগুলো স্লট ফাকা আছে তা বের করা যায়। একটি হ্যাশটেবিলের লোড ফ্যাক্টর যদি 1 হয় তাহলে এর বোঝায়, এর প্রত্যেকটি স্লটে একটি করে উপাদান রয়েছে। লোড ফ্যাক্টর একের অধিক থাকার অর্থ হলো, টেবিলের কোন স্লটে একাধিক উপাদান রয়েছে।

কনস্ট্যান্ট টাইম অর্থাৎ O(1) সময়ে কোন উপাদান খুঁজে পাওয়া নিশ্চিত করতে চাইলে লোড ফ্যাক্টর সবসময় একের নিচে রাখতে হবে। এটি করার জন্যে যখনই লোড ফ্যাক্টর ১ এর বেশি হবে তখনই টেবিলকে রিসাইজ করে আবার প্রত্যেকটি উপাদানের হ্যাশ ক্যালকুলেট করে বিভিন্ন স্লটে বসাতে হবে। এই অপারেশনটি মোটামুটি এক্সপেনসিভ। তবে তুমি কনস্ট্যান্ট টাইম উপাদানগুলো খুঁজে পাচ্ছো টেবিলের সাইজ যতোই হোক না কেনো।

তাহলে উপরের আলোচনা থেকে নিশ্চয় বুঝতে পারছো যে, যদিও কনস্ট্যান্ট টাইমে আমরা উপাদান খুঁজে বের করতে চাচ্ছি, কিন্তু সবসময় তা সম্ভব নয়। তবে best case এটি অবশ্যই O(1) হবে এবং worst case-এ এটি O(n) হতে পারে।

হ্যাশ ফাংশন ১

bazlur_pic
লেখকঃ বজলুর রহমান রোকন।

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

খাতাতে যদি নামগুলো বর্ণানুক্রমে রাখা না থাকে, তাহলে তোমার প্রতিবার খুঁজে বের করতে অনেক সময় লাগে। অ্যালগরিমদ ক্লাসে নিশ্চয় শিখেছো যে এক্ষেত্রে খুঁজে বের করার সময় O(n) । তবে নামগুলো যদি বর্ণানুক্রমে রাখা থাকে তাহলে বাইনারি সার্চ ব্যবহার করা যায় আর তখন সময় লাগবে O(log n)। তুমি নিশ্চয় জানো যে O(n) চেয়ে O(log n) কম সময় লাগে।

img1

যদিও O(log n) কম সময় লাগছে, তবুও কিছুটা সময় লাগছে। সবচেয়ে ভাল হতো যদি কোন সময়ই না লাগতো। তুমি সবগুলো পণ্যের নাম এবং দাম মুখস্থ করে ফেলতে পারতে এবং ক্রেতা কোন পণ্যের নাম বলার সঙ্গে সঙ্গেই তুমি দাম বলে দিতে পারতে।

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

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

মনে করো, তোমার ১০ সাইজের একটি অ্যারে রয়েছে। এখন, ধরো, পেঁপের দাম ২০ টাকা। পেঁপে নামটি যদি হ্যাশ ফাংশনে দাও, তাহলে এটি যদি ৪ রিটার্ন করে, তাহলে অ্যারের চতুর্থ নম্বর ইনডেক্সে পেঁপের দামর রেখে দেবে। এভাবে আদার নাম হ্যাশ ফাংশনে দিলে যদি ৩ রিটার্ন করে, তাহলে তাকে তিন নম্বর ইনডেক্সে রেখে দিলে। এভাবে কলা, মরিচ ইত্যাদি রেখে দিলে। এখন যখন তোমার এগুলো দাম জানার দরকার হয়, তাহলে চট করে হ্যাশ ফাংশনে নামটি দিয়ে তার ইনডেক্সটি বের করে নিলে। অ্যারতে ইনডেক্স জানলে ভ্যালু পড়ে আনা খুব সহজ। অ্যারে থেকে ভ্যালু পরে আনার সময় আসলে O(1) ।
img2

img3
হ্যাশ টেবিল

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

উপরের যে উদাহরণটি দিয়েছি তাতে একটি সমস্যা রয়েছে। সেটি নিয়ে পরবর্তীতে আলোচনা করবো। তবে সমস্যাটি তুমি চিন্তা করে যদি খুঁজে বের করতে পারো তাহলে নিচে কমেন্ট করে জানাও।

পরের পর্বঃ হ্যাশ ফাংশন ২।

পাদটিকা: বাইনারি সার্চের টাইম কমপ্লেক্সিটি কিভাবে O(log n) হলো, সেটা না বুঝলে দ্বিমিকের ডিসক্রিট ম্যাথমেটিক্স কোর্সের তৃতীয় ইউনিটের লেকচার দেখে নাও।

ডাটাবেজ ট্রানজেকশন ও এসিড

রিলেশনাল ডাটাবেজের খুব মৌলিক একটি বিষয় হচ্ছে ডাটাবেজ ট্রানজেকশন। আর ডাটাবেজ ট্রানজেকশনের একটি গুরুত্বপূর্ণ বিষয় হচ্ছে এসিড প্রোপার্টি। আজকের লেখায় এই বিষয়ে আলোচনা করবো।

মনে করি জনি, রবিন, জামাল আর কামাল নামে চার বন্ধুর একই ব্যাংকে একাউন্ট আছে। ওই ব্যাংকের ডাটাবেজে Account নামে একটি টেবিল আছে এবং নিচে আমরা সেই Account টেবিলের ডাটা দেখতে পাচ্ছি –

Account No Account Name Balance
100-01 Jony 15000
100-02 Robin 5000
100-03 Kamal 10000
100-04 Jamal 1200

এবার আমরা নিচের ঘটনাগুলি লক্ষ করি –

  • জনি তার একাউন্ট থেকে ১০০০ টাকা তুলে নিল (Cash Withdraw)
  • একজন রবিনের একাউন্টে ৫০০ টাকা জমা দিল (Cash Deposit)
  • কামাল তার একাউন্ট থেকে ২০০০ টাকা জামালের একাউন্টে পাঠাল (Fund Transfer)
  • জামাল তার একাউন্টে কত টাকা আছে তা জানতে চাইল (Balance Enquiry)

উপরের প্রথম তিনটি ঘটনা Account টেবিলের Balance কলামের ডাটা পরিবর্তন করবে এবং শেষের ঘটনাটি Balance কলামের ডাটা পড়বে। আর রিলেশনাল ডাটাবেজ ম্যানেজমেন্ট সিস্টেমের (RDBMS) পরিপ্রেক্ষিতে এ ধরনের ঘটনাগুলিকে আমরা ডাটাবেজ ট্রানজেকশন (Database Transaction or Transaction) বা ট্রানজেকশন বলি। একটি ডাটাবেজ ট্রানজেকশনে এক বা একাধিক কাজ/ধাপ থাকতে পারে। যেমন, যখন কামাল তার একাউন্ট থেকে ২০০০ টাকা জামালের একাউন্টে পাঠাল তখন দুটি কাজ হবে প্রথমে কামালের একাউন্ট থেকে ২০০০ টাকা কমাতে হবে এবং তারপরে জামালের একাউন্টে ২০০০ টাকা বাড়াতে হবে। প্রতিটি ট্রানজেকশন হয় সফল ভাবে সম্পূর্ণ বা কমিট (Commit) হবে নয়তো রোলব্যাক (Rollback) বা ট্রানজেকশনের পূর্বের অবস্থায় ফেরত যাবে। একটি ট্রানজেকশন ডাটাতে যে পরিবর্তন করে সেই পরিবর্তিত ডাটা ডাটাবেজে স্থায়ী ভাবে রেখে দেয়াকে কমিট (Commit) বলে। আর রোলব্যাক (Rollback) হল ট্রানজেকশনের ফলে ডাটাতে যে পরিবর্তন হয়েছে সেগুলোকে বাদ দিয়ে ডাটাকে ট্রানজেকশন শুরুর পূর্বের অবস্থায় ফিরিয়ে নেয়া। উদাহরণস্বরূপ, আমরা আবার কামালের একাউন্ট থেকে ২০০০ টাকা জামালের একাউন্টে পাঠানর ট্রানজেকশনটি বিশ্লেষণ করি। আমরা জানি এই ট্রানজেকশনে দুটি কাজ করতে হবে। মনে করি প্রথম কাজটি সফল হল অর্থাৎ কামালের একাউন্ট থেকে ২০০০ টাকা কমানো হল, তাহলে কামালের একাউন্টে থাকবে ৮০০০ টাকা (ট্রানজেকশন শুরুর আগে কামালের একাউন্টে ১০০০০ টাকা ছিল)। কিন্তু কোনো কারণে দ্বিতীয় কাজটি মানে জামালের একাউন্টে ২০০০ টাকা বাড়ানো গেল না। সুতরাং এই ট্রানজেকশনটিকে রোলব্যাক করতে হবে এবং রোলব্যাক করার পরে কামালের একাউন্টে আবার ১০০০০ টাকা হয়ে যাবে।

ডাটাবেজ ট্রানজেকশন বা ট্রানজেকশনের নিম্নোক্ত চারটি বৈশিষ্ট্য/ধর্ম আছে –

  • Atomicity (এটমিসিটি)
  • Consistency (কন্সিসটেনসি)
  • Isolation (আইসোলেশন)
  • Durability (ডিউরাবিলিটি)

আর এই চারটি বৈশিষ্ট্যের প্রথম অক্ষর গুলো দিয়ে অর্থাৎ A, C, I এবং D নিয়ে আমরা বলি এসিড (ACID)। ডাটাবেজ ম্যানেজমেন্ট সিস্টেম নিজেই ট্রানজেকশনের এই বৈশিষ্ট্যগুলি পরিচালনা করে এবং অ্যাপ্লিকেশন ডেভেলপারদের আশ্বস্ত করে যে প্রতিটি ট্রানজেকশন সেগুলো মেনে চলবে।

আমারা এই চারটি বৈশিষ্ট্য উদাহরনের মাধ্যমে বোঝার চেষ্টা করি –

Atomicity – ডাটাবেজ ট্রানজেকশনের এই গুনটি নিশ্চিত করে যে, হয় একটি ট্রানজেকশনের সবগুলি ধাপ সফল হবে অথবা কোনটিই হবে না। যেমন, মনে করি, জনি তার বন্ধু রবিনকে ১,০০০ টাকা দিতে চায়। এখন জনির ব্যাংক একাউন্টে ১০,০০০ টাকা আছে আর রবিনের একাউন্টে ৪,০০০ টাকা আছে। তাহলে আমাদেরকে একটি ডাটাবেজ ট্রানজেকশন করতে হবে এবং এই ট্রানজেকশনে আমাদের দুটি কাজ/ধাপ সম্পন্ন করেতে হবে। প্রথমে জনির একাউন্ট থেকে ১,০০০ টাকা কেটে নিতে হবে এবং তারপরে রবিনের একাউন্টে সেই ১,০০০ টাকা যোগ করতে হবে। আমারা এই ট্রানজেকশনটিকে সফল বলব যদি দুটি কাজই সম্পূর্ণ হয়। আর ট্রানজেকশনটি সফল/কমিট (Commit) হলে জনির একাউন্টে থাকবে ৯,০০০ টাকা এবং রবিনের একাউন্টে হবে ৫,০০০ টাকা। এখন যদি কোনও কারণে জনির একাউন্ট থেকে টাকা কেটে নেওয়ার পরে তা রবিনের একাউন্টে যোগ করতে না পারি তাহলে আমাদের ট্রানজেকশনটি সফল/কমিট হবে না। আর ট্রানজেকশনটি সফল না হলে জনির ব্যাংক একাউন্টে ১০,০০০ টাকা এবং রবিনের একাউন্টে ৪,০০০ টাকাই থাকবে অর্থাৎ ট্রানজেকশনটি রোলব্যাক (Rollback) হবে। ডাটাবেজ ট্রানজেকশনের এটমিসিটি বৈশিষ্ট্যটি এই বিষয়টির নিশ্চয়তা দান করে।

Consistency – কন্সিসটেনসি এর বাংলা অর্থ সামঞ্জস্য বা সঙ্গতি অথবা মিল। রিলেশনাল ডাটাবেজ ম্যানেজমেন্ট সিস্টেমে কন্সিসটেনসি দ্বারা আমরা বুঝি যে প্রতিটি ডাটাবেজ ট্রানজেকশনকে ডাটাবেজে নির্ধারিত নিয়মের (Database Constraint) সাথে সামঞ্জস্য রেখে ডাটা পরিবর্তন বা নতুন ডাটা যোগ করতে হবে। আমারা নানাবিধ উপায়ে ডাটাবেজ ট্রানজেকশনের উপরে বাধ্যবাধকতা বা নিয়ম (Database Constraint) নির্ধারণ করতে পারি। যেমন, প্রাইমারি কি (primary key), ফরেন কি (foreign key), ট্রিগার (trigger), ইত্যাদি দ্বারা আমরা ট্রানজেকশনের উপরে বাধ্যবাধকতা বা নিয়ম আরোপ করতে পারি। মনে করি আমাদের একটি Student টেবিল আছে এবং studentId হল এই টেবিলের প্রাইমারি কি। আমরা যখন নতুন একজন স্টুডেন্টের ডাটা যোগ (data insert) করতে যাব তখন ডাটাবেজ পরীক্ষা করে দেখবে যে প্রাইমারি কি নিয়মটি মানা হচ্ছে কিনা। নিচের ছবিতে বিষয়টি দেখানো হল –

studentId name
101 John এই ডাটাটি সফল ভাবে যোগ হবে কারন ডাটাবেজ পরীক্ষা করে দেখবে যে 101 দিয়ে আর কোনও স্টুডেন্ট নেই।
102 Simon এই ডাটাটিও সফল ভাবে যোগ হবে কারন ডাটাবেজ পরীক্ষা করে দেখবে যে 102 দিয়ে আর কোনও স্টুডেন্ট নেই।
101 Jack এই ডাটা আমরা যোগ করতে পারবনা কারন ডাটাবেজ পরীক্ষা করে দেখবে যে 101 দিয়ে আগে থেকেই একজন স্টুডেন্ট আছে। অর্থাৎ এই ডাটাবেজ ট্রানজেকশনটি ডাটাবেজে নির্ধারিত প্রাইমারি কি এর নিয়ম অনুযায়ী সফল হবে না।

এভাবেই ডাটাবেজে নির্ধারিত নিয়মগুলো (Database Constraint) প্রতিটি ট্রানজেকশনের সময় পরীক্ষা করে দেখে যেন ট্রানজেকশনটি নিয়মের ব্যত্তয় না ঘটিয়ে সম্পূর্ণ হয়।

Isolation – আইসোলেশনের আভিধানিক অর্থ হল বিচ্ছিন্নতা। আর এই বৈশিষ্ট্যটি নিশ্চিত করে যে একাধিক ট্রানজেকশন নিরাপদে এবং স্বাধীনভাবে কোনরূপ সংঘর্ষ ছাড়া একই সময়ে সম্পূর্ণ হতে পারে, কিন্তু এটা কোন ট্রানজেকশনটি আগে হবে আর কোনটি পরে হবে অর্থাৎ ক্রম (order) নিশ্চিত করে না। উদাহরণস্বরূপ, মনে করি রনির একাউন্টে ১৫,০০০ টাকা আছে। রনি তার দুই বন্ধু কামাল এবং জামাল কে যথাক্রমে ৩,০০০ ও ২,০০০ টাকার দুটি চেক দিল। কামাল এবং জামাল একসাথে ব্যাংকে গেল টাকা তোলার জন্য। তারা দুজন ব্যাংকের দুজন অপারেটরের কাছে একই সময়ে চেক দুটি জমা দিল। এখানে একই সাথে দুটি ট্রানজেকশন হবে, কিন্তু যেহেতু একই একাউন্ট থেকে টাকা তোলা হবে তাই যে কোনও একটি ট্রানজেকশন আগে হবে এবং অন্যটিকে অপেক্ষা করতে হবে। ধরে নেই জামালের ট্রানজেকশনটি আগে শুরু হল তাই কামালের ট্রানজেকশনটি অপেক্ষা করবে। জামালের ট্রানজেকশনটি সম্পূর্ণ হলে কামালের ট্রানজেকশনটি শুরু হবে। অর্থাৎ জামালের ট্রানজেকশনটি যখন শুরু হবে তখন রনির একাউন্টে আছে ১৫,০০০ টাকা আর ট্রানজেকশনটি শেষ হবার পরে রনির একাউন্টে ১৩,০০০ টাকা থাকবে। আর কামালের ট্রানজেকশনটি যখন শুরু হবে তখন রনির একাউন্টে আছে ১৩,০০০ টাকা আর ট্রানজেকশনটি শেষ হবার পরে রনির একাউন্টে ১০,০০০ টাকা থাকবে। যেহেতু দুটি ট্রানজেকশনই একই ডাটার (রনির একাউন্ট) উপর নির্ভরশীল তাই একটিকে অন্যটি শেষ হবার জন্য অপেক্ষা করতে হচ্ছে। যদি এভাবে না হত তাহলে যে ডাটার উপর ট্রানজেকশনগুলি নির্ভরশীল সেই ডাটা একটা সামঞ্জস্যহীন (inconsistent) অবস্থায় চলে যাবে। আর ডাটা যেন কোনও ভাবেই সামঞ্জস্যহীন না হয় সে জন্যই ট্রানজেকশন আইসোলেশন প্রয়োজন।

ডাটাবেজে চারটি আইসোলেশন লেভেল আছে –

  1. Read Uncommitted
  2. Read Committed
  3. Repeatable Read
  4. Serializable

Read Uncommitted হল আইসোলেশনের সর্বনিম্ন লেভেল আর Serializable হচ্ছে সর্বোচ্চ লেভেল। এই আইসোলেশন লেভেলগুলির কিছু সমস্যা আছে যথা, Dirty Reads, Non Repeatable Reads এবং Phantom। নিচে এগুলোর বর্ণনা দেয়া হল –

Dirty Read – একটি ট্রানজেকশন অন্য ট্রানজেকশনের দ্বারা পরিবর্তিত ডাটা যা কমিট (commit) হয়নি সেগুলো পড়তে পারাকেই ডারটি রিড বলে। উদাহরণ স্বরূপ, মনে করি একজন ক্রেতা একটি কেনাকাটার সাইট থেকে কোনও একটি পণ্য ২৮০ টি কিনতে চাইল, এখন তার জন্য ট্রানজেকশন A শুরু হল। ট্রানজেকশন A প্রথমে দেখবে যে ঐ পণ্যের ২৮০ টি স্টকে আছে কিনা। ধরে নেই সাইটের ডাটাবেজে Product_Inventory নামে একটি টেবিল আছে যাতে পণ্যের পরিমান আছে। তো ট্রানজেকশন A সেই Product_Inventory টেবিল থেকে পেল যে তার ইউজার যে পণ্যটি কিনতে চায় তা ৫০০ টি আছে। সুতরাং ট্রানজেকশন A এই অর্ডারটিকে কনফার্ম করল এবং Product_Inventory টেবিলে ঐ পণ্যটির পরিমান ৫০০ থেকে কমিয়ে ২২০ করে দিল। কিন্তু ট্রানজেকশন A এখনও কমিট হয়নি। একই সময়ে আরও একজন ঐ একই সাইট থেকে ঠিক ঐ পণ্যটি ৪০০ টি কিনতে চাইল। ধরে নেই পরের ক্রেতার জন্য ট্রানজেকশন B শুরু হল। ট্রানজেকশন B দেখল যে ঐ পণ্যটি মাত্র ২২০ টি আছে, তাই সে ক্রেতাকে জানাল যে তার অর্ডারটি নেয়া যাচ্ছে না। এরই মধ্যে আবার ট্রানজেকশন A এর যে ক্রেতা সে অর্ডারটি বাতিল করে দিল, তার ফলে ট্রানজেকশন A রোলব্যাক হয়ে গেল। অর্থাৎ Product_Inventory টেবিলে ঐ পণ্যটির পরিমান আবার ৫০০ হয়ে গেল। তার মানে এখানে ট্রানজেকশন B এমন একটি ডাটা পেয়েছিল যা আসলে কমিট হয়নি আর এটাকেই Dirty Read বলে।

Non Repeatable Read – একটি ট্রানজেকশন যদি একই ডাটা দুবার পড়ে আর দুবার দুটি আলাদা ভ্যালু পায় তাকে Non Repeatable Read বলে। যেমন, মনে করি রবিন একটি কেনাকাটার সাইট থেকে কোনও একটি পণ্য ৩০০ টি কিনতে চাইল, এখন তার জন্য ট্রানজেকশন A শুরু হল। ট্রানজেকশন A প্রথমে দেখবে যে ঐ পণ্যের ৩০০ টি স্টকে আছে কিনা। ধরে নেই সাইটের ডাটাবেজে Product_Inventory নামে একটি টেবিল আছে যাতে পণ্যের পরিমান আছে। তো ট্রানজেকশন A সেই Product_Inventory টেবিল থেকে পেল যে রবিন যে পণ্যটি কিনতে চায় তা ৫০০ টি আছে। একই সময়ে জামাল ঐ একই সাইট থেকে ঠিক ঐ পণ্যটি ২৫০ টি কিনতে চাইল। ধরে নেই জামালের জন্য ট্রানজেকশন B শুরু হল এবং এই ট্রানজেকশনটি Product_Inventory টেবিল থেকে পেল যে ঐ পণ্যের ৫০০ টি স্টকে আছে। এদিকে রবিন তার অর্ডারটিকে কনফার্ম করল তার ফলে ট্রানজেকশন A পণ্যটির পরিমান ৫০০ থাকে কমিয়ে ২০০ করে দিল এবং ট্রানজেকশন A কমিট হয়ে গেল। ওদিকে জামাল তার অর্ডারে একটু পরিবর্তন করল, সে ঐ পণ্যটি বাদ দিয়ে অন্য একটি পণ্য ২৫০ টি কিনতে চাইল। ফলে ট্রানজেকশন B আবার Product_Inventory টেবিল থেকে খুঁজে পেল যে এই পরে অর্ডার দেয়া পণ্যটি মাত্র ১০০ টি রয়েছে। তাই ট্রানজেকশন B জামালকে জানাল যে পরে অর্ডার দেয়া পণ্যটি স্টকে ২৫০ টি নেই, জামাল আবার প্রথমে অর্ডার দেয়া পণ্যটি নিতে চাইল। এবার ট্রানজেকশন B Product_Inventory টেবিল থেকে দেখল যে এই পণ্যের আর ২০০ টি অবশিষ্ট আছে এবং অর্ডারটি নেয়া যাচ্ছে না। অর্থাৎ ট্রানজেকশন B একই ডাটা দুবার পড়ে দুটি ভিন্ন ভ্যালু (পণ্যের দুটি ভিন্ন পরিমান) পেল। ট্রানজেকশন B যে সমস্যাটির মুখে পড়েছে তাকে Non Repeatable Read বলে।

Phantom – মনে করি কেনাকাটার সাইটের ডাটাবেজে Order নামে একটি টেবিল আছে এবং এই টেবিলে সব অর্ডারের ডাটা আছে। এখন একজন জানতে চাইল মোট কতগুলো অর্ডার হয়েছে। তো একটি ট্রানজেকশন A শুরু হল যা কিনা Order টেবিল থেকে মোট কতটি অর্ডার হয়েছে তা বের করবে। এদিকে একই সময়ে অন্য একটি ট্রানজেকশন B নতুন একটি ডাটা Order টেবিলে যোগ করল। এখন যদি ট্রানজেকশন A আবার Order টেবিল থেকে মোট কতটি অর্ডার হয়েছে তা বের করে তাহলে ভিন্ন ভ্যালু পাবে। এই ধরনের ঘটনাকে Phantom বলে। Non Repeatable Read এর সাথে Phantom এর পার্থক্য হচ্ছে এখানে ডাটা ভিন্ন হচ্ছে নতুন ডাটা যোগ করার ফলে বা ডাটা মুছে ফেলার কারণে (insert or delete)।

নিচের টেবিলে কোন আইসোলেশন লেভেলে কোন অসুবিধা গুলো হয় বা হয় না তা দেখানো হল –

Isolation Level Dirty Read Non Repeatable Read Phantom
Read Uncommitted হয় হয় হয়
Read Committed হয় না হয় হয়
Repeatable Read হয় না হয় না হয়
Serializable হয় না হয় না হয় না

Durability – ডিউরাবিলিটি শব্দের মানে স্থায়িত্ব। ডাটাবেজ ট্রানজেকশনের এই ধর্মটি নিশ্চিত করে যে, যখন একটি ট্রানজেকশন সফল হয় তখন তার ফলে যে ডাটা পরিবর্তন হয় তা যেন স্থায়ীভাবে ডাটাবেজে থেকে যায়। এর অর্থ হল, সব ধরনের অঘটন/দুর্ঘটনা সত্ত্বেও (System Failure/System Crash) বা সিস্টেম রিস্টার্ট (System Restart) হলেও সফল ট্রানজেকশনের দ্বারা ডাটাতে যে পরিবর্তন হয়ছে তা স্থায়ী ভাবে ডাটাবেজে সংরক্ষিত থাকবে। যেমন, মনে করি আমাদের একটি বাসের টিকেট বুকিং সিস্টেম আছে। এই বুকিং সিস্টেমে রবিন একটি টিকেট বুকিং দিল এবং তার বুকিংটি সফল হল, আর এরপরেই এই বুকিং সিস্টেমটি বৈদ্যুতিক গোলযোগের (Power Failure) কারণে (System Crash) ক্র্যাশ করল। কিন্তু যেহেতু রবিনের বুকিংটি সফল হয়েছিল তাই বুকিং সিস্টেমটি পুনরায় চালু হবার পরে তার করা বুকিংটি ডাটাবেজে পাওয়া যাবে।

আশা করি লেখাটি ডাটাবেজ ট্রানজেকশন ও এসিড সম্বন্ধে বুঝতে সাহায্য করবে।

লেখকঃ মোঃ শফিউজ্জামান রাজিব, ডাটাবেজ ও বিগ ডাটা প্রফেশনাল।

ইউক্লিডিয়ান অ্যালগরিদম

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

ইউক্লিডের অ্যালগোরিদম বা গ.সা.গু নির্ণয়ের অ্যালগোরিদমটি নিম্নরূপঃ

Untitled

অ্যালগরিদম দেখে ঘাবড়ানোর কিছু নেই। আমরা অ্যালগরিদমটি বুঝতে চেষ্টা করি।

প্রথমেই দেয়া আছে একটি ফাংশন যার নাম gcd() এবং এই ফাংশনটির দুইটি প্যারামিটার a,b। এখানে, a এবং b হচ্ছে সেই দুইটি সংখ্যা আমরা যেগুলোর গসাগু বের করতে চাচ্ছি। ফাংশনটিতে প্রথমেই রয়েছে একটি while লুপ যেটি b-এর মান শূন্য না হওয়া পর্যন্ত চলবে। এখানে, একটি টেম্পোরারি ভ্যারিয়েবল t ব্যবহার করা হয়েছে। প্রথমে b-কে টেম্পোরারিতে রাখা হয়েছে। এরপর b-এর মান আপডেট হয়েছে a mod b দিয়ে। এখানে, mod হচ্ছে মডুল্যাস। অর্থাৎ, a-কে b দিয়ে ভাগ করে যেটি ভাগশেষ থাকবে সেটি হবে b-এর পরিবর্তিত মান। পরের লাইনে আছে a := t; এখানে a-এর নতুন মান হবে t-এর মান। লুপের প্রথম লাইনে আমরা t-এর মান পাচ্ছি b। তাহলে, a-এর মান হবে b-এর পুরনো মানটি (আপডেটেট মানটি নয়)। এভাবে লুপের ভিতরের কাজগুলো হতে থাকবে যতক্ষণ না b-এর মান শূন্য না হয়। লুপের কাজ শেষ হওয়ার পর ফাংশনটি a-এর মান রিটার্ন করবে, যেটি আমাদের কাঙ্ক্ষিত gcd()-এর মান বা গ.সা.গু।

একটি উদাহরণ দিলে ফাংশনটির কার্যক্রম আমাদের কাছে পরিষ্কার হবে। ধরা যাক, a= 12 এবং b = 16 , এদের গ.সা.গু বের করতে হবে। অ্যালগরিদম অনুযায়িঃ

  1. a=12 , b = 16
  2. while(b!=0) এভাবে b এর মান যতক্ষণ 0 না হবে লুপটি ততক্ষণ চলবে। অর্থাৎ লুপের ভিতরের তিনটি স্টেপ আমরা b এর মান 0 না হওয়া পর্যন্ত করবো।
  3. t = 16; b = 12%16  এখানে যেহেতু 12 কে 16 দ্বারা ভাগ করা যায় না, তাই ভাগশেষ হবে 12, সুতরাং b = 12 , a = t = 16 (যেহেতু, প্রথমেই আমরা t এর মান 16 দিয়েছি যেটি b-এর প্রাথমিক মান।)
  4. তিন নাম্বার স্টেপে আমরা a এবং b এর আপডেটেট ভ্যালু পেয়েছি। a = 16 এবং b= 12 . এখন আমাদের t = b = 12; b = a%b = 16%12 = 4; a =t = 12।
  5. এখন a = 12, b = 4 এখন t = b = 4;  b = a%b = 12%4 = 0; a = 4; এখানে আমরা b এর মান জিরো পেয়ে গেলাম তাই এই লুপটি আর execute করবে না। এটি a-এর ভ্যালু return করবে 4।

আমরা যদি এখন এটি সি প্রোগ্রামিং এর সাহায্যে কোড করি, আমাদের কোডটি হবে এমনঃ

Untitled

এই ফাংশনটির সাহায্যে খুব সহজেই গ.সা.গু নির্ণয়ের কাজটি করা যাবে। এবার দেখা যাক ইউক্লিড সাহেবের এই অ্যালগরিদমটি দিয়ে আমরা ল.সা.গু নির্ণয় করতে পারি কি না। ল.সা.গু নির্ণয় করার একটি সহজ সূত্র আছে। সূত্রটি এমনঃ

দুটি সংখ্যার ল.সা.গু = দুটি সংখ্যার গুণফল / দুটি সংখ্যার গ.সা.গু

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

লেখক : তামান্না নিশাত রিনি।

অফ-বাই-ওয়ান এরর (Off-by-one error)

“There are two hard things in Computer Science: Cache invalidation, naming things and off-by-one error”  

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

অফ বাই ওয়ান এরর কী

“অফ-বাই-ওয়ান এরর” সাধারণভাবে “অফ-বাই-ওয়ান বাগ” নামেও পরিচিত। সংক্ষেপে একে OBOE (Off By One Error ) বলা হয়ে থাকে। যখন কোন লুপের বাউন্ডারি কন্ডিশনে আমরা ভুল করি তখন এই এরর দেখা দেয়। বেশিরভাগ সময় এই এররটি হয় যখন আমরা “is less than equal” (<=) অপারেটরটি কোন তুলনা বা comparison-এর জন্য ব্যবহার করে থাকি বা যখন একটি সিকোয়েন্স শূন্য থেকে শুরু হওয়ার বদলে এক থেকে শুরু হয়।

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

অ্যারের লুপের অফ-বাই-ওয়ান এরর

ধরা যাক, আমাদের পাঁচটি উপাদানের একটি অ্যারে দেয়া আছে। আমরা যদি অ্যারের উপাদানগুলো প্রিন্ট করতে চাই তাহলে আমাদের একটি লুপ চালাতে হবে যেটি অ্যারের পাঁচটি উপাদান ঠিকঠাক প্রিন্ট করে। যদি আমরা এভাবে কোডটি লিখিঃ

Untitled

এখানে লুপটি 0 থেকে শুরু  করে 0,1,2,3,4,5 এভাবে ছয়টি iteration সম্পন্ন করছে। যেটি অ্যারে সাইজ n-কে অতিক্রম করেছে। অ্যারের ক্ষেত্রে আমরা এটিকে “অ্যারে বাউন্ড এক্সেপশন” বলে থাকি। অফ-বাই-ওয়ান এরর-এর কারণে এমনটি হয়ে থাকে।  এখানে for loop-টি n+1 সংখ্যক বার চলেছে। কিন্তু যদি আমরা লুপটির end condition-এ “<=” এর পরিবর্তে “<” ব্যবহার করি, তখন আমাদের লুপটি 0,1,2,3,4 এভাবে মোট পাঁচটি iteration সম্পন্ন করে n সংখ্যকবার চলবে।

তবে, সি++ এর ক্ষেত্রে “আউট অফ বাউন্ড এক্সেপশন” থ্রো করে না। বিগিনারদের এটি বেশ ঝামেলায় ফেলে। তখন দেখা যায়, অ্যারে সাইজ ছোট নেয়ার পরেও কোন রান টাইম এরর দেখায় না।

ফেন্সপোষ্ট এরর

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

598px-Fencepost_error.svg

প্রশ্নটির উত্তর যদি 10 বলা হয় তাহলে উত্তরটি হবে ভুল। যদি n+1 সংখ্যক পোষ্ট দিয়ে একটি বেড়া তৈরি করা হয় তাহলেই আমরা n সংখ্যক ভাগ পাবো সেই বেড়াটির। উপরের ছবিটি দিয়ে ব্যাপারটি বুঝানো হয়েছে।

 লেখক: তামান্না নিশাত রিনি।

এক ঘণ্টার পাইথন কোডিং

পাইথন হচ্ছে একটি প্রোগ্রামিং ভাষা। বর্তমান তথ্যপ্রযুক্তির দুনিয়ায় এর ব্যবহার দিন দিন বাড়ছে। প্রফেশনাল কাজের পাশাপাশি প্রোগ্রামিং শেখার জন্যও পাইথন খুবই জনপ্রিয়। পাইথন নিয়ে বিস্তারিত জানা যাবে এই লেখায়: পাইথন কী?

তো সামনে “কম্পিউটার বিজ্ঞান শিক্ষা সপ্তাহ” উদযাপনের একটি গুরুত্বপূর্ণ অংশ হচ্ছে “আওয়ার অব কোড“। সারা পৃথিবীর সাথে সাথে বাংলাদেশেও এটি বেশ ঘটা করে পালন করার উদ্যোগ নিয়েছে বিডিওএসএন, আর সাথে গত দুই বছরের মতো এবারেও আছে দ্বিমিক কম্পিউটিং। অনুষ্ঠানের বিস্তারিত জানা যাবে এই ওয়েবসাইটে : http://cseweek.bdosn.org

বেশিরভাগ মানুষই code.org ওয়েবসাইটে যেই গেমটি দেওয়া আছে, সেটি ব্যবহার করে ‘আওয়ার অব কোড’ পালন করবে। তবে সবার জন্য এটি উপভোগ্য কিংবা উপকারি না ও হতে পারে। বাংলাদেশের প্রেক্ষাপটে কেউ যদি ষষ্ঠ শ্রেণী বা তার ওপরের ক্লাসের শিক্ষার্থীদের নিয়ে এক ঘণ্টার কোডিং করতে চান, আমার পরামর্শ হবে পাইথন ভাষা ব্যবহার করে কয়েকটি প্রোগ্রাম লিখে দেখানোর।

প্রথমেই শিক্ষার্থীদের বলতে হবে, প্রোগ্রামিং কেন শিখবে। তাদের সাথে প্রোগ্রামিং ও প্রোগ্রামারদের নিয়ে গল্প করতে হবে। গল্প-স্বল্প বলা শেষ হলে শুরু করতে হবে এক ঘণ্টার পাইথন কোডিং

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

২) দ্বিতীয় কাজ হচ্ছে “Hello World” প্রোগ্রাম লেখা। এটি যে প্রোগ্রামিং সংস্কৃতির একটি অংশ, সেটি শিক্ষার্থীদের জানাতে হবে।

৩) 1 থেকে 100 পর্যন্ত সমস্ত পূর্ণসংখ্যা প্রিন্ট করার প্রোগ্রাম দেখাতে হবে। প্রথমে কেবল while লুপ ব্যবহার করে। তারপর for লুপ এবং range() ফাংশন ব্যবহার করে। লুপের ধারণা দিতে হবে। ফাংশন নিয়েও কিছু কথা বলতে হবে। তবে বেশি কথা বলে শিক্ষার্থীদের বিরক্ত করা যাবে না।

৪) এবারে লুপ নিয়ে আরো খেলাধূলা করতে হবে। 1, 3, 5, …, 99 প্রিন্ট করা ও 2, 4, 6, …, 98, 100 প্রিন্ট করার প্রোগ্রাম দেখাতে হবে। তবে এর আগে শিক্ষার্থীদের ১০-১৫ মিনিট সময় দিলে ভালো হয় যেন তারা নিজেরা কাজটি করার চেষ্টা করে। তারপর সংখ্যাগুলোকে বড় থেকে ছোট ক্রমেও প্রিন্ট করার প্রোগ্রাম দেখাতে হবে। শুধু লুপ ব্যবহার করে একবার দেখাতে হবে, তারপর range() ফাংশন ব্যবহার করে।

৫) এবারে কন্ডিশনাল লজিকের ধারণা দিতে হবে। এর জন্য আবার 1 থেকে 100 পর্যন্ত জোড়সংখ্যা ও বিজোড় সংখ্যা প্রিন্ট করার প্রোগ্রাম দেখাতে হবে।

৬) 1 থেকে 1000 এর মধ্যে সমস্ত পূর্ণবর্গ সংখ্যা (1, 4, 9, 16 …) প্রিন্ট করার প্রোগ্রাম দেখাতে হবে। প্রোগ্রামটি একাধিকভাবে লিখে দেখাতে হবে।

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

day = raw_input()
if day in ["Friday", "Saturday"]:
   print day, "is holiday"
else:
   print day, "is not a holiday"
name = raw_input()
if name in ["Rose", "Tulip", "Lily", "Daffodil"]:
   print name, "is a flower"
elif name in ["Mango", "Jackfruit", "Guava", "Papaya"]:
   print name, "is a fruit"
else:
   print "I don't know!"
while True:
   name = raw_input()
   if name == "Exit":
      break
   if name in ["Rose", "Tulip", "Lily", "Daffodil"]:
      print name, "is a flower"
   elif name in ["Mango", "Jackfruit", "Guava", "Papaya"]:
      print name, "is a fruit"
   else:
      print "I don't know!"

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

সবাইকে অংশগ্রহনের জন্য সার্টিফিকেট দিলে সবাই হয়ত উৎসাহ পাবে।

পাইথনের জন্য কিছু লিঙ্ক:
১) হুকুশ-পাকুশের প্রোগ্রামিং শিক্ষা : http://hukush-pakush.com
২) Hour of Python : https://hourofpython.com
৩) পাইথনের ওপর ফ্রি ভিডিও লেকচার: http://pyvideo.subeen.com
৪) পাইথনের ওপর বাংলায় লেখা বই : http://bit.ly/pybook (প্রোগ্রামিংয়ে একেবারে নতুনদের জন্য উপযোগি নয়)।

মেমক্যাশড

মেমক্যাশড কী? মেমক্যাশড-এর ওয়েবসাইটে লেখা আছে :

Free & open source, high-performance, distributed memory object caching system, generic in nature, but intended for use in speeding up dynamic web applications by alleviating database load.

memcached_banner75

এটা না বুঝলে সমস্যা নাই। সহজ ভাষায় মেমক্যাশড হচ্ছে কি-ভ্যালু স্টোর। কি-ভ্যালু স্টোর আবার কী? জিনিসটা আসলে হ্যাশটেবল, ম্যাপ বা পাইথনের ডিকশনারি-এর মতো। প্রতিটা ডাটার একটা কি থাকবে, সেই কি দিয়ে সহজেই ডাটা একসেস করা যাবে। একটা কি দিয়ে একটা ডাটা (ভ্যালু) পাওয়া যাবে, আবার একটা ভ্যালুর জন্য একটা কি থাকবে। যেমন প্রতিটি দেশের একটি তিন অক্ষরের কোড থাকে, আমরা চাইলে সেই কোড দিয়ে দেশের নামটা জেনে নিতে পারে। এক্ষেত্রে কোড হচ্ছে কি, আর দেশের নাম হচ্ছে ভ্যালু। পাইথনে যদি আমরা একটি ডিকশনারি তৈরি করি, তাহলে এরকম হবে:
alpha_code = {“BGD”: “Bangladesh”, “AUS”: “Australia”, “DEU”: “Germany”, “SGP”: “Singapore”}
এখন print alpha_code[“BGD”] লিখলে Bangladesh প্রিন্ট হবে।

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

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

Screen Shot 2015-07-11 at 3.46.51 pm

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

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

১) পরীক্ষার্থীর রোল নাম্বার ইনপুট দেওয়া হলো।
২) রোল নাম্বারটি সার্ভার একটি কি-ভ্যালু স্টোরের মধ্যে খুঁজে দেখতে হবে রোল নাম্বারটি কি হিসেবে ব্যবহার করলে সেটির জন্য কোনো ভ্যালু তৈরি করা আছে কী না। যদি থাকে তাহলে ৫ নম্বর ধাপে যেতে হবে (এটিকে বলে ক্যাশ হিট) আর যদি না থাকে তবে ৩ নম্বর ধাপে যেতে হবে (একে বলে ক্যাশ মিস)।
৩) ডাটাবেজে কুয়েরি করে রেজাল্ট আনতে হবে।
৪) রেজাল্ট ক্যাশে (মেমোরিতে) সংরক্ষণ করতে হবে। যাতে পরবর্তি সময়ে কেউ আবার এই রোল নাম্বারের জন্য রেজাল্ট জানতে চায়, তাহলে আর ডাটাবেজে কুয়েরি করার দরকার পরবে না।
৫) ক্লায়েন্টকে রেজাল্ট রিটার্ন করতে হবে।

মেমক্যাশের মাধ্যমে কাজটি খুব সহজে করা যায়।

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

তারপর “Smarts half in client, half in server.” এখানে কিন্তু ক্লায়েন্ট এবং সার্ভার দুইটা অংশ আছে। মেমক্যাশড-এ একটা সার্ভার চলতে থাকে, সেই সার্ভার-এর মধ্যে ডাটাগুলা থাকে (আসলে সার্ভার সমস্ত ডাটা মেমরি (RAM)-এর মধ্যে রাখে)। আর ক্লায়েন্ট কী করে? ক্লায়েন্ট সিদ্ধান্ত নেয় যে এখন অমি যে ডাটা আনার জন্য সার্ভারকে কল করব, কোন কি (Key) দিয়ে কল করব?

তারপর আরেকটা মজার ব্যাপার হচ্ছে যে ক্লায়েন্ট কিন্তু একটা না, অনেকগুলা সার্ভার এর সাথেই কমিউনিকেট করতে পারে। খুব বড় অ্যাপ্লিকেশনে আমাদের অনেকগুলা সার্ভার নিয়ে কাজ করতে হয় ও লোড ব্যালেন্সিং করতে হয়। মেমক্যাশড আমাদেরকে একাধিক সার্ভারে ডাটা রাখার সুবিধা দেয়। মেমক্যাশড্ অনেকগুলা সার্ভার এ রেখে দেওয়ার সুবিধা হচ্ছে, যে “Servers are disconnected from each other”, মানে একটা সার্ভার এর সাথে আরেকটা সার্ভার এর কোন সম্পর্ক নাই। তাহলে আমাদের সুবিধা যেটা, যে আমরা যখন নতুন কোন সার্ভার যুক্ত করব তখন বাকীদের সাথে synchronization বা crosstalk বা নিজেদের মধ্যে ব্রডকাস্ট এর কোন ব্যাপার নাই। আবার যখন কোনো সার্ভার বাদ দিয়ে দিব তখন শুধু ওই সার্ভারে যে ডাটাগুলা আছে সেগুলাই শুধু ক্যাশ খুঁজে পাবে না। বাকী সার্ভার-এর ডাটা যেমন ছিল তেমনি থাকবে। আর আমরা নিজেরা কিন্তু প্রোগ্রামিং করার সময় ঠিক করে দিতে পারব না যে ডাটা কোন সার্ভার এর ক্যাশ এ থাকবে? (সেটা কোন সার্ভার এর ক্যাশ এ সেটা জানতে চাইলে আমরা telnet দিয়ে হিট করে দেখতে পারি আসলে এটা কোন ক্যাশ এ আছে, ক্যাশ এর key টা দিয়ে)।

আর সবচেয়ে বড় সুবিধা হচ্ছে O(1) এ আমরা সবকিছু নিয়ে আসতে পারি। (এটা না বুঝলে হাম্মাদ আলী স্যারের ডিসক্রিট ম্যাথ কোর্সটা করে ফেলতে হবে)।

আরেকটা হচ্ছে “Forgetting data is a feature”, আমরা ভ্যালুর এক্সপায়ার টাইম ঠিক করে দিতে পারি। সেই সময় পরে ডাটা ক্যাশ থেকে আপনাআপনি মুছে যাবে। এটা খুব গুরুত্বপূর্ণ ও সুন্দর একটা ফিচার।

তারপরের ফিচারটা হচ্ছে “Cache invalidation is trivial”। আসলে কম্পিউটার সাইন্স এ নাকি দুইটা প্রবলেম খুবই হার্ড প্রবলেম হিসেবে চিহ্নিত করা হয়। প্রথম প্রবলেম হচ্ছে naming প্রবলেম। যে আমরা কোনকিছুর নাম ঠিক করে দিতে পারি না, এটা সবসময়ই হার্ড (কঠিন) প্রবলেম। দ্বিতীয় হার্ড প্রবলেম হচ্ছে ক্যাশিং ভেলিডেশন। এটাও হার্ড প্রবলেম, মানে আমরা যখন ক্যাশটাকে ইনভেলিড করি তখন অনেক জায়গায় অনেক রকম ঝামেলার সৃষ্টি হতে পারে। তো মেমক্যাশড্ এ এই জিনিসটা অনেকটা সহজ হলেও ব্যবহার করার সময় আমাদের নিজেদের কিছু সতর্কতার প্রয়োজন। একটা ডাটা কিন্তু অনেকগুলা ক্যাশ কি-তে রাখতে পারি বিভিন্ন প্রয়োজনে। তখন আমরা যেটা করব তখন আমাদের মাথায় রাখতে হবে প্রোগ্রামিং করার সময় বা ডিজাইন করার সময় যে এখন যদি অমি একটা জিনিস আপডেট (update) করব বা বাদ দিব (invalid করব), তখন সাথে সাথে সংশ্লিষ্ট আর কোথায় কোথায় আমাদের সেই কাজটি করতে হবে। কোনো একটা জায়গায় ভুলে গেলে কিন্তু ঝামেলা হয়ে যাবে। তখন এমন হতে পারে যে ওয়েবসাইটের হোমপেজে দেখাচ্ছে তামিম ইকবাল আউট কিন্তু স্কোরবোর্ডে সেটা দেখাচ্ছে না!

মেমক্যাশড নিয়ে মুক্তসফটে অনেক বছর আগে একটি প্রেজেন্টেশন দিয়েছিলাম, সেটির ভিডিও দেখা যাবে এখানে :

আর স্লাইডগুলো পাওয়া যাবে এখানে

আর আরো জানতে হলে মেমক্যাশডের অফিশিয়াল ওয়েবসাইট-এ যেতে হবে।

মেমক্যাশডের সঠিক ব্যবহার ডেভেলাপার ও ব্যবহারকারীদের জীবনে শান্তি বয়ে আনুক।

সি দিয়ে ওয়েব সার্ভার

এসো নিজে করি : ওয়েব সার্ভার

লেখক : ওমর শেহাব

এটি একটি শিশুতোষ লেখা। যারা মাত্র সি প্রোগ্রামিং শেখা শুরু করেছে তাদের জন্য এটি লিখছি যাতে তারা সি ল্যাংগুয়েজের সামর্থ্য সম্পর্কে কিছুটা ধারণা পায়।

আজকে থেকে এগার বছর আগের কথা। আমি তখন শাবিপ্রবি কম্পিউটার বিজ্ঞান ও প্রকৌশল বিভাগে তৃতীয় বর্ষে পড়ছি। আমাদের একটা কোর্স ছিল সিএসই ৩৫০। এই কোর্সে একটি সফটওয়্যার বানাতে হত। তখন আমার শিক্ষক শাহরিয়ার ভাইয়ের কাছ থেকে সি ল্যাংগুয়েজ দিয়ে একটি ওয়েব সার্ভার বানানোর আইডিয়া পেলাম।

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

সেই কোডটি এই লিংকে (http://bit.ly/1GEzoX7) পাওয়া যাবে। আমি ভাবলাম যারা মাত্র সি শেখা শুরু করেছে তাদের কেউ কেউ এই ব্যাপারে আগ্রহী হতে পার। আমি একটু একটু করে এই কোডের ব্যাপারগুলো ধরিয়ে দিব। একটি জিনিস মনে রাখতে হবে আমি তখনও ছাত্র ছিলাম এ কারণে কোডের মান খুব বেশি আহামরি না।

তাহলে শুরু হোক! আমি একটি একটি করে ব্লক দিব আর তার নিচে ওই ব্লক নিয়ে কথা বলব।

/*
 * Course Code 350
 *
 * A Multithreaded Tiny HTTP Server
 * Demonstrating Thread Pool Management
 * Following the Thread Pool Management
 * Outline from Unix Network Programming Vol 1
 * by W. Richard Stevens.
 *
 * Project accomplished by: Abu Mohammad Omar Shehab Uddin Ayub
 * Reg No. 2000 330 096
 * Section B
 * 3rd Year 2nd Semester
 * Dept of CSE, SUST
 *
 * Idea and guided by: Mahmud Shahriar Hussain
 * Lecturer
 * Dept of CSE, SUST
 *
 * Course Instructor: Rukhsana Tarannum Tazin
 * Lecturer
 * Dept of CSE, SUST
 */

যারা ইতিমধ্যে প্রোগ্রামিং শুরু করেছ তারা নিশ্চয়ই জান যেকোন কোডের আগে কমেন্টে এই কোডের উদ্দেশ্য ও প্রোগ্রামারের নাম দেয়া স্বাভাবিক ভদ্রতা।

#include <sys/socket.h>
#include <netinet/in.h>
#include <sys/types.h>
#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>
#include <string.h>
#include <sys/stat.h>
#include <unistd.h>

সি ল্যাংগুয়েজের নিজস্ব যে ফিচার বা সাপোর্ট আছে সেগুলো বিভিন্ন হেডার ফাইলে কোড করা থাকে। যেমন আমি পোসিক্স থ্রেড নিয়ে কাজ করতে চাই কাজেই পিথ্রেড.এইচ ফাইলটি ব্যবহার করছি।

#define MAX_CLIENT 5
#define MAX_THREAD 3
#define MAX_REQ_HEADER 10
#define MAX 10
#define MAX_LENGTH 6
#define MIME_LENGTH 20

এখানে আমি আগে থেকে কিছু জিনিস ঠিক করে নিচ্ছি। যেমন: আমি চাই এক সাথে পাঁচটির বেশি ব্রাউজার (ফায়ারফক্স, ক্রোম এগুলোকে ব্রাউজার বলে) আমার সার্ভারের পেজ ব্রাউজ করতে পারবে না কাজেই আমি MAX_CLIENT 5 দিয়েছি।

এর পর আমি আমার পছন্দ মত কিছু ডেটা স্ট্রাকচার ঠিক করে নিব।

typedef struct {
   pthread_t threadID;
   long threadCount;
}Thread;

যেমন থ্রেড সম্পর্কিত তথ্য রাখার জন্য আমি থ্রেড নামে একটি স্ট্রাকচার ব্যবহার করছি।

typedef struct {
   char hostName[100];
   char filePath[100];
}Request;

কোন ব্রাউজার থেকে যখন কেউ একটি ওয়েবপেইজ দেখার অনুরোধ সার্ভারের কাছে পাঠাবে সেই অনুরোধটিকে রিকোয়েস্ট নামে একটি স্ট্রাকচারে রাখব। এখানে কোন সার্ভার থেকে অনুরোধটি এসেছে এবং কোন ওয়েব পেজটি দেখতে চাচ্ছে এই তথ্যগুলো থাকবে।

typedef struct{
   int code;
   char date[30];
   char server[30];
   char last_modified[30];
   long content_length;
   char content_type[10];
   char file_path[80];
}Reply;

যখনই কোন ব্রাউজার ব্যবহার করে কেউ একটি পেজ দেখতে চাইবে তার জন্য ঠিকঠাক মতো জবাব তৈরি করা হবে। পেজটি থাকলে সেটি পাঠানো হবে আর না থাকলে বলা হবে পেজ নেই। এর জন্য বেশ কিছু তথ্য পাঠাতে হয়। এগুলো রিপ্লাই নামে একটি স্ট্রাকচারের মাধ্যমে গুছিয়ে পাঠানো হয়।

Thread thrdPool[MAX_THREAD];
Request request[MAX_THREAD];
Reply reply[MAX_THREAD];
int clntConnection[MAX_CLIENT], clntGet, clntPut;

এখানে আমি আমার সার্ভারের লোড নেবার সামর্থ‌্য ঠিক করে দিচ্ছি। লোড মানে সে একসাথে কয়জন ওয়েব ব্যবহারকারীর রিকোয়েস্ট সামলাতে পারবে।

thread_mutex_t clntMutex = PTHREAD_MUTEX_INITIALIZER;
pthread_mutex_t srvrMutex = PTHREAD_MUTEX_INITIALIZER;
pthread_mutex_t srvrMutex2 = PTHREAD_MUTEX_INITIALIZER;
pthread_mutex_t emitMutex2 = PTHREAD_MUTEX_INITIALIZER;
pthread_cond_t clntCondition = PTHREAD_COND_INITIALIZER;

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

static int numThreads;
void *request_handler(void *arg);
int find_method (char *req);
Request parse_request(char *rbuff);
Reply prepare_reply(int code, Request rq);
char *getMimeType(char *str);
void emit_reply(int conn, Reply rply);

একটু গুছিয়ে কাজ করার জন্য পুরো কোডটিকে আমি কিছু ফাংশনে ভাগ করেছি। এখানে সেগুলো ডিক্লেয়ার করলাম।

int main(void)
{

মেইন ফাংশন শুরু হল অর্থাৎ প্রোগ্রামের মূল অংশটি শুরু হচ্ছে।

int i, serverSockfd, clientSockfd;
int serverLen, clientLen;
struct sockaddr_in serverAddress, clientAddress, tempAddress;

কাজের সুবিধার জন্য কিছু ভ্যারিয়েবল দরকার।

//defining number of threads
 numThreads = MAX_THREAD;
// initializing queue parameters
 clntGet = clntPut = 0;

একবারে একসাথে কয়টি রিকোয়েস্ট নিয়ে কাজ করা যাবে অর্থাৎ সার্ভারের সামর্থ ঠিক করে দিচ্ছি।

//creating all the threads
for(i = 0; i < numThreads; i++)
{
    pthread_create(&thrdPool[i].threadID, NULL, &request_handler, (void *) i);
} // end of for loop

যখনই কোন রিকোয়েস্ট আসবে একটি করে থ্রেড তার দায়িত্ব নিবে। রিকোয়েস্ট আসার পরপর নতুন থ্রেড তৈরি করতে গেলে প্রোগ্রাম স্লো হয়ে যায় তাই আগেই কিছু তৈরি করে রাখি।

//creating the socket descriptor
serverSockfd = socket(AF_INET, SOCK_STREAM,0);
if(serverSockfd < 0)
{
   error("\nError opening socket");
   exit(1);
}
serverAddress.sin_family = AF_INET;
serverAddress.sin_addr.s_addr = INADDR_ANY;
serverAddress.sin_port = htons(80);
serverLen = sizeof(serverAddress);
if(bind(serverSockfd, (struct sockaddr *)&serverAddress, serverLen) < 0)
{
   printf("\nError in binding.");
   exit(1);
}

অন্য যেকোন ওয়েবসার্ভারের মত আমার সার্ভারও কম্পিউটারের ৮০ নম্বর পোর্টে কান পেতে রাখবে। এখন আমার জানা জরুরী যে ইতিমধ্যে এই পোর্ট অন্য কোন সফটওয়্যার দখল করে ফেলেছে কিনা। সাবধানের মার নাই!

listen(serverSockfd, 10);

আমি কাআআআন পেতেএএএ রইইই!

for( ; ; )
{
   fflush(stdout);
   //printf("\nWaiting for clients...");
   clientLen = sizeof(tempAddress);
   //printf("\n\nBlocked on accept()");
   clientSockfd = accept(serverSockfd, (struct sockaddr *)&clientAddress, &clientLen);
   //printf("\nAllocated client descriptor# %d", clientSockfd);
   pthread_mutex_lock(&srvrMutex);
   clntConnection[clntPut] = clientSockfd;
   if(++clntPut == MAX_CLIENT)
   clntPut = 0;

   if(clntPut == clntGet)
   {
      printf("\nCan't handle any more request...\nTerminating...");
      exit(1);
   }

   pthread_cond_signal(&clntCondition);
   pthread_mutex_unlock(&srvrMutex);
   fflush(stdout);

} // end of infinite for loop

ইনফিনিটি লুপ খুব একটা ভাল জিনিস না। এটি আরো ভাল ভাবে করতে পারা উচিৎ। এখানে আমি যখনই কোন রিকোয়েস্ট পাচ্ছি ছিটকিনি তুলে দিয়ে একটি থ্রেড ধরে এনে তাকে রিকোয়েস্টের দায়িত্ব দিয়ে দিচ্ছি। যদি দেখি যে ইতিমধ্যে অনেক রিকোয়েস্ট জমে গেছে ভদ্রভাবে না করে দিচ্ছি। তারপর আবার ছিটকিনি বা মিউটেক্স নামিয়ে দিচ্ছি।

} // end of main

মেইন ফাংশন শেষ!

কোন থ্রেড যখন একটি রিকোয়েস্ট পায় তখন রিকোয়েস্ট হ্যান্ডলার নামে একটি ফাংশনের মাধ্যমে সেটি সামলায়। এখন আমরা সেই ফাংশনটি দেখব।

void *request_handler(void *arg)
{

রিকোয়েস্ট ‌হ্যান্ডলার শুরু হল।

int connfd;
char *reqBuff;
fflush(stdout);
//printf("\nThread %d starting", (int) arg);

এক আধটু ভ্যারিয়েবল সব জায়গাতেই লাগে!

for( ; ; )
{
   pthread_mutex_lock(&clntMutex);
   //printf("\nMutex locked by thread# %d.", (int) arg);
   while(clntGet == clntPut)
   pthread_cond_wait(&clntCondition, &clntMutex);

আবারও ইনফিনিটি লুপ ব্যবহার করছি, দু:খিত! আমি এখন শেয়ারড ভ্যারিয়েবলগুলো ব্যবহার করছি কাজেই মিউটেক্স বা ছিটকিনি লাগছে।

connfd = clntConnection[clntGet];
if(++clntGet == MAX_CLIENT)
clntGet = 0;

সার্ভার ওভারলোড হয়ে যাচ্ছে কিনা সেটাও খেয়াল রাখতে হচ্ছে।

// thread operation
// printf("\nIn between mutex lock-unlock. Thread# %d, Connection# %d", (int) arg, connfd);
reqBuff = (char *) malloc (1000);
read(connfd, reqBuff, 1000);

এক একটি রিকোয়েস্টের জন্য কি পরিমাণ রেম (RAM) খরচ হবে সেগুলো ঠিক করছি।

int temp;
temp = find_method(reqBuff);

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

if(temp == 0)
{
   //printf("\nfind_method returned 0");
   request[(int)arg] = parse_request(reqBuff);
   //printf("\nHost: %s\nFile Path: %s", request[(int)arg].hostName, request[(int)arg].filePath);
   reply[(int)arg] = prepare_reply(200, request[(int)arg]);
   printf("\n\nprinting the reply structure");
   //printf("\nCode: %d\nDate: %s\nServer: %s\nlast_modified: %s\ncontent_length: %ld\ncontent type: %s\nfile path: %s",   reply[(int)arg].code, reply[(int)arg].date, reply[(int)arg].server, reply[(int)arg].last_modified, reply[(int)arg].content_length, reply[(int)arg].content_type, reply[(int)arg].file_path);
   emit_reply(connfd, reply[(int)arg]);
}

এটি গেট মেথড তাই কাজে নেমে পড়ছি।

else if(temp == 1)
{
   printf("\nfind_method returned 1");
   reply[(int)arg] = prepare_reply(501, request[(int)arg]);
   emit_reply(connfd, reply[(int)arg]);
}

এটি পুট বা অন্য কোন স্বীকৃত মেথড যার সাপোর্ট আমি দিইনি। দু:খিত!

else
{
   printf("\nfind_method returned -1");
   reply[(int)arg] = prepare_reply(400, request[(int)arg]);
   emit_reply(connfd, reply[(int)arg]);
}

আজগুবি মেথড।

pthread_mutex_unlock(&clntMutex);
//printf("\nMutex unlocked by thread# %d.", (int) arg);
thrdPool[(int) arg].threadCount++;

ছিটকিনি!

   // shahriar bhai told that closing the connection formally is not so important
   // good performance achieved @ closing it formally
   close(connfd);
}

যখনই কোন রিসোর্স ব্যবহার করব না তখনই সেটি মেমোরি থেকে সরিয়ে নিব।

} // end of request_handler function

ফাংশন শেষ!

ব্রাউজারকে ওয়েবসার্ভার যখন উত্তর পাঠায় সেই উত্তরগুলোতে কি কি তথ্য থাকবে সেটি এমিট রিপ্লাই ফাংশনটি সামলায়।

void emit_reply(int conn, Reply rply)
{

ফাংশন শুরু হল।

//pthread_mutex_lock(&emitMutex2);
if(rply.code == 200)
{

ইয়াহু! পেজটি সার্ভারে পাওয় গেছে!

char *ok_code = "HTTP/1.1 200 OK\r\n";
write(conn, ok_code, strlen(ok_code));

সুখবরের একটি কোড আছে। সেটি সেট করি।

char *date;
date = (char *)malloc(100);
strcpy(date, "Date: ");
strcat(date, rply.date);
strcat(date, "\r\n");
write(conn, date, strlen(date));

তারিখ সেট করি।

char *server;
server = (char *)malloc(100);
strcpy(server, "Server: ");
strcat(server, rply.server);
strcat(server, "\r\n");
write(conn, server, strlen(server));

কে উত্তর পাঠাচ্ছে সেটি জানাই।

char *last_modified;
last_modified = (char *)malloc(100);
strcpy(last_modified, "Last-Modified: ");
strcat(last_modified, rply.last_modified);
strcat(last_modified, "\r\n");
write(conn, last_modified, strlen(last_modified));

ওয়েবপেজটি সর্বশেষ কবে আপডেট করা হয়েছে তা জানাই।

char *content_length;
content_length = (char *)malloc(100);
strcpy(content_length, "Content-Length: ");
int decpnt, sign;
char *p;
p = (char *)malloc(20);
p = ecvt(rply.content_length, 15, &decpnt, &sign);
//printf("\nConversion-- %s %d %d", p, decpnt, sign);
 
strncat(content_length, p, decpnt);
strcat(content_length, "\r\n");
write(conn, content_length, strlen(content_length));

ওয়েবপেজ কত বাইট সেটি জানাই।

char *content_type;
content_type = (char *)malloc(100);
strcpy(content_type, "Content-Type: ");
strcat(content_type, rply.content_type);
strcat(content_type, "\r\n");
write(conn, content_type, strlen(content_type));

এটি ছবি, ভিডিও না শুধু লেখা সেই তথ্যটি জানাই।

write(conn, "\r\n", 2);
 
int b;
char c;
FILE *fp;
fp = (FILE *) malloc(sizeof(FILE));
fp = fopen(rply.file_path, "rb");
while(!feof(fp))
{
   c = getc(fp);
   if(!feof(fp))
   {
      //printf("%c", c);
      write(conn, &c, 1);
   }
}

এবার পেজটি পাঠাই।

//pthread_mutex_unlock(&emitMutex2);
return;
}

ফাংশন শেষ!

else if(rply.code == 400)
{
   char *ok_code = "HTTP/1.1 400 Bad Request\r\n";
   write(conn, ok_code, strlen(ok_code));
   
   char *date;
   date = (char *)malloc(100);
   strcpy(date, "Date: ");
   strcat(date, rply.date);
   strcat(date, "\r\n");
   write(conn, date, strlen(date));
   char *server;
   server = (char *)malloc(100);
   strcpy(server, "Server: ");
   strcat(server, rply.server);
   strcat(server, "\r\n");
   write(conn, server, strlen(server));
   write(conn, "\r\n", 2);
   
   char *error_400;
   error_400 = (char *)malloc(300);
   strcpy(error_400, "<html><head><title>Error No: 400. Bad Request.</title></head><body><h2>The server cannot parse the request.</h2><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><hr>For further info mail to shehab_sust@yahoo.com.</body><html>");
   write(conn, error_400, strlen(error_400));
}

যদি পেজটি পাওয়া না যায় তাহলে দু:সংবাদ জানিয়ে দেই।

else if(rply.code == 501)
{
   char *ok_code = "HTTP/1.1 501 Method Not Implemented\r\n";
   write(conn, ok_code, strlen(ok_code));

   char *date;
   date = (char *)malloc(100);
   strcpy(date, "Date: ");
   strcat(date, rply.date);
   strcat(date, "\r\n");
   write(conn, date, strlen(date));

   char *server;
   server = (char *)malloc(100);
   strcpy(server, "Server: ");
   strcat(server, rply.server);
   strcat(server, "\r\n");
   write(conn, server, strlen(server));
   write(conn, "\r\n", 2);

   char *error_501;
   error_501 = (char *)malloc(300);
   strcpy(error_501, "<html><head><title>Error No: 501. Method Not Implemented.</title></head><body><h2>The server only resolves the GET method.</h2><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><hr>For further info mail to shehab_sust@yahoo.com.</body><html>");
   write(conn, error_501, strlen(error_501));
}

এর মানে হল রিকোয়েস্টে কোন সমস্যা নেই কিন্তু যে মেথডে চাওয়া হয়েছে সেটির সাপোর্ট আমি এখনও দেই নি। দোষ আমারই।

else if(rply.code == 404)
{
   char *ok_code = "HTTP/1.1 404 File Not Found\r\n";
   write(conn, ok_code, strlen(ok_code));
   
   char *date;
   date = (char *)malloc(100);
   strcpy(date, "Date: ");
   strcat(date, rply.date);
   strcat(date, "\r\n");
   write(conn, date, strlen(date));

   char *server;
   server = (char *)malloc(100);
   strcpy(server, "Server: ");
   strcat(server, rply.server);
   strcat(server, "\r\n");
   write(conn, server, strlen(server));
   
   write(conn, "\r\n", 2);

   char *error_404;
   error_404 = (char *)malloc(300);
   strcpy(error_404, "<html><head><title>Error No: 404. File Not Found.</title></head><body><h2>The server could not found the requested url.</h2><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><hr>For further info mail to shehab_sust@yahoo.com.</body><html>");
   write(conn, error_404, strlen(error_404));
}

এর মানে হল ওয়েবসার্ভারে অনুরোধকৃত পেজের কোন অস্তিত্ত্বই নেই।

else if(rply.code == 403)
{
   char *ok_code = "HTTP/1.1 403 Forbidden\r\n";
   write(conn, ok_code, strlen(ok_code));

   char *date;
   date = (char *)malloc(100);
   strcpy(date, "Date: ");
   strcat(date, rply.date);
   strcat(date, "\r\n");
   write(conn, date, strlen(date));

   char *server;
   server = (char *)malloc(100);
   strcpy(server, "Server: ");
   strcat(server, rply.server);
   strcat(server, "\r\n");
   write(conn, server, strlen(server));

   write(conn, "\r\n", 2);

   char *error_403;
   error_403 = (char *)malloc(300);
   strcpy(error_403, "<html><head><title>Error No: 403. Forbidden.</title></head><body><h2>You are not authorized to access this url.</h2><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><hr>For further info mail to shehab_sust@yahoo.com.</body><html>");
 
   write(conn, error_403, strlen(error_403));
}

এর মানে হল পেজটি আছে কিন্তু দেখানো যাবেনা।

} //end of emit_reply

ফাংশন শেষ!

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

char *getMimeType(char *str)
{
   printf("\nentered mime type");
   int i;
   //defined here the file extension
   char *fileExt[MAX];
   fileExt[0] = "html";
   fileExt[1] = "htm";
   fileExt[2] = "txt";
   fileExt[3] = "gif";
   fileExt[4] = "jpg";
   fileExt[5] = "qt";

   //defined here the mime type
   char *mType[MAX];
   mType[0] = "text/html";
   mType[1] = "text/html";
   mType[2] = "text/plain";
   mType[3] = "image/gif";
   mType[4] = "image/jpeg";
   mType[5] = "video/quicktime";

   for(i = 0; i < 6; i++)
   {
      if(strcmp(str, fileExt[i]) == 0)
      {
         printf("\nmatched");
         return mType[i];
      }
   } //end of for loop
   printf("\nreturning ERROR");
   char *er = "ERROR";
   return er;
} //end of getMimetype

ফাংশনটির আইডিয়া খুব সহজ। রিকোয়েস্ট থেকে মাইমটাইপ পড়ে সে অনুযায়ী রিপ্লাইয়ের মাইমটাইপ ঠিক করে দিবে।

রিপ্লাই হিসেবে যে বাইটগুলো পাঠানো হয় সেগুলো গুছানোর জন্য প্রিপেয়ার রিপ্লাই নামে একটি ফাংশন ব্যবহার করা হয়।

Reply prepare_reply(int code, Request rq)
{

ফাংশন শুরু হল।

// extracting the file extension
char *drive, *direc, *fname, *ext;

drive = (char *) malloc (3);
direc = (char *) malloc (66);
fname = (char *) malloc (9);
ext = (char *) malloc (5);

Reply rpl;

শুরুতে মেমোরীতে কিছু জায়গা গুছিয়ে নেই।

if(code == 200)
{

এর মানে হল আমরা ওয়েবসাইট ভিজিটরকে জানাতে যাচ্ছে যে পেজটি সার্ভারে পাওয়া গেছে।

rpl.code = 200;
 
time_t lt;
lt = time(NULL);
strcpy(rpl.date, ctime(&lt));
rpl.date[strlen(rpl.date) - 1] = '\0';
 
strcpy(rpl.server, "TinyThreadedServer/0.1a");

কিছু খুচরো তথ্য গুছিয়ে নেই।

char dir[100];
getcwd(dir, 100);
//printf("\ncurrent dir is %s", dir);
//printf("\nfile path is %s", rq.filePath);
strcat(dir, "/");
strcat(dir, rq.filePath);
//printf("\nabsolute file path is %s", dir);
char *path, *p;
path = (char *) malloc (80);
p = (char *) malloc (80);
path = strtok(dir, "/");
strcpy(p, "/");
strcat(p, path);
do{
   path = strtok('\0', "/");
   if(path)
   {
      strcpy(ext, path);
      strcat(p, "/");
      strcat(p, path);
   }
} while(path);
//printf("\nthe c++ file path %s", p);

হার্ডডিস্কে কোথায় ফাইলটি আছে খুঁজে নেই।

char *e;
e = (char *)malloc(10);
e = strtok(ext, ".");
e = strtok('\0', ".");
//printf("\nfile extension is %s", e);

ফাইলের এক্সটেনশনটি জেনে নেই।

FILE *fp;
fp = (FILE *) malloc(sizeof(FILE));
if((fp = fopen(p, "r")) == NULL)
{
   printf("\nFILE NOT FOUND.\nERROR CODE 404");
   rpl.code = 404;
   return rpl;
}

ফাইলটি পড়া যায় কিনা দেখি।

struct stat buff;
stat(p, &buff);
//printf("\nSize: %ld\ntime of last modification: %s", buff.st_size, ctime(&buff.st_mtime));

strcpy(rpl.last_modified, ctime(&buff.st_mtime));
rpl.last_modified[strlen(rpl.last_modified) - 1] = '\0';

ফাইলটি সর্বশেষ কবে আপডেট করা হয়েছে সেই তথ্যটি টুকে নেই।

rpl.content_length = buff.st_size;

ফাইলের সাইজ কত সেই তথ্যটি নেই।

if(strcmp(getMimeType(e), "ERROR") == 0)
{
   rpl.code = 403;
   fclose(fp);
   return rpl;
}

ফাইলটি পড়ার পারমিশন আছে কিনা দেখি।

   strcpy(rpl.content_type, getMimeType(e));
   strcpy(rpl.file_path, p);
   fclose(fp);
}

আরো কিছু তথ্য নেই।

else if (code == 400)
{
   rpl.code = 400;

   time_t lt;
   lt = time(NULL);
   strcpy(rpl.date, ctime(&lt));
   rpl.date[strlen(rpl.date) - 1] = '\0';

   strcpy(rpl.server, "TinyThreadedServer/0.1a");
}

এর মানে হল ফাইলটি পাওয়া যায় নি।

else if (code == 501)
{
   rpl.code = 501;

   time_t lt;
   lt = time(NULL);
   strcpy(rpl.date, ctime(&lt));
   rpl.date[strlen(rpl.date) - 1] = '\0';
   
   strcpy(rpl.server, "TinyThreadedServer/0.1a");
}

এর মানে হল ফাইলটি আছে কিন্তু পড়ার পারমিশন নেই।

   return rpl;
} //end of prepare_reply

ফাংশন শেষ।

কোন ব্রাউজার যখন রিকোয়েস্ট পাঠায় তখন সেখানে অনেক ধরণের তথ্য থাকে। সেগুলো ধরে ধরে বুঝার জন্য পারস রিকোয়েস্ট ফাংশনটি ব্যবহার করা হয়।

Request parse_request(char *rbuff)
{
   char *fileName;
   char *hostName;
   int j, k, l, m, n;
   Request r;

ফাংশন শুরু হল।

fileName = (char *) malloc (100);
hostName = (char *) malloc (100);

মেমোরীতে একটু জায়গা নেই।

for(j = 5, k = 0; ;j++, k++)
{
   if(rbuff[j] == ' ') break;
   fileName[k] = rbuff[j];
} //end of for loop
fileName[k]= '\0';
//printf("\nThe valid file path is %s", fileName);
strcpy(r.filePath, fileName);

কোন ওয়েবপেজ দেখতে চায় সেটি জেনে নেই।

//finding the host
char *p;
p = strstr(rbuff, "Host: ");

for(l = 0; l < 6; l++)
{
   p++;
} //end of for loop

for(m = 0, n = 0; ; m++, n++)
{
   if(*p == '\r' || *p == '\n') break;
   hostName[n] = *p;
   p++;
} //end of for loop
hostName[n]= '\0';

fflush(stdout);
strcpy(r.hostName, hostName);

রিকোয়েস্টটি কোন কম্পিউটার থেকে এসেছে জেনে নেই।

   return r;
} // end of parse_request

ফাংশন শেষ।

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

int find_method (char *req)
{
   pthread_mutex_lock(&srvrMutex2);
   //printf("\nin the find_method function\n%s\nthe size of the request is: %d", req, strlen(req));

   char *method_list[6];
   method_list[0] = (char *) malloc (10);
   strcpy(method_list[0], "PUT");
   method_list[1] = (char *) malloc (10);
   strcpy(method_list[1], "HEAD");
   method_list[2] = (char *) malloc (10);
   strcpy(method_list[2], "POST");
   method_list[3] = (char *) malloc (10);
   strcpy(method_list[3], "DELETE");
   method_list[4] = (char *) malloc (10);
   strcpy(method_list[4], "TRACE");
   method_list[5] = (char *) malloc (10);
   strcpy(method_list[5], "CONNECT");
 
   int i, j = 0;
   char *r;
   r = (char *) malloc (10);
   for(i = 0; i < strlen(req); i++)
   {
      if(req[i] == ' ') break;
      r[i] = req[i];
   } //end of for loop
   r[i] = '\0';
   //printf("\nExtracted method is %s", r);

   if(strcmp(r, "GET") == 0)
   {
      //printf("\nit's a GET method !!!");
      pthread_mutex_unlock(&srvrMutex2);
      return 0;
   }
 
   for(i = 0; i < 7; i++)
   {
      if(strcmp(r, method_list[i]) == 0)
      {
         printf("\n%s matched with %s", r, method_list[i]);
         j = 1;
         break;
      }
   } //end of for loop

   if(j == 1)
   {
      pthread_mutex_unlock(&srvrMutex2);
      return 1;
   }
   else
   {
      pthread_mutex_unlock(&srvrMutex2);
      return -1;
   }
} // end of find_method

গেট মেথড হলে আমি আগাবো না হলে স্যরি বলে দিব।

কোড এখানেই শেষ! পড়ার জন্য ধন্যবাদ! এখন একটু মাথা খাটিয়ে বের করা আমার ওয়েব সার্ভারের সোর্স কোডের ফাইলের নাম allizom রেখেছি কেন?