ধাপ ৩ - ডিজাইনের গভীর বিশ্লেষণ (Design deep dive)

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

ডেটা মডেল (Data model)

উচ্চ-স্তরের ডিজাইনে, সবকিছু একটি হ্যাশ টেবিলে সংরক্ষণ করা হয়েছে। এটি একটি ভালো শুরুর বিন্দু; তবে, বাস্তব-বিশ্বের সিস্টেমগুলোর জন্য এই পদ্ধতিটি সম্ভব নয় কারণ মেমরি রিসোর্স সীমিত এবং ব্যয়বহুল। একটি ভালো বিকল্প হলো একটি রিলেশনাল ডাটাবেসে <shortURL, longURL> ম্যাপিং সংরক্ষণ করা। চিত্র ৪ একটি সাধারণ ডাটাবেস টেবিল ডিজাইন দেখায়। টেবিলটির সরলীকৃত সংস্করণে ৩টি কলাম রয়েছে: id, shortURL, longURL।

[চিত্র ৪-এর বর্ণনা: ছবিটি একটি সরলীকৃত রিলেশনাল ডাটাবেস টেবিল স্কিমা উপস্থাপন করে, সম্ভবত একটি URL শর্টনিং সার্ভিসের জন্য। টেবিলটির নাম ‘url’ এবং এতে তিনটি কলাম রয়েছে। প্রথম কলামটি, যার লেবেল ‘PK’ (Primary Key), নির্দেশ করে যে ‘id’ কলামটি প্রতিটি সারির জন্য অনন্য শনাক্তকারী হিসাবে কাজ করে। ‘id’ কলামটি নিজেই সম্ভবত প্রতিটি শর্ট করা URL এন্ট্রির প্রতিনিধিত্বকারী একটি অনন্য পূর্ণসংখ্যা ধারণ করে। দ্বিতীয় কলাম, ‘shortURL’, শর্ট করা URL স্ট্রিং সংরক্ষণ করে, এবং তৃতীয় কলাম, ‘longURL’, সংশ্লিষ্ট মূল, দীর্ঘ URL স্ট্রিং সংরক্ষণ করে। কলামগুলোর মধ্যে কোনো তথ্য প্রবাহ নেই; বরং, প্রতিটি সারি একটি শর্ট URL এবং এর দীর্ঘ URL প্রতিপক্ষের মধ্যে একটি একক ম্যাপিং নির্দেশ করে। টেবিলের কাঠামোটি নির্দেশ করে যে একটি shortURL দেওয়া থাকলে, দক্ষ লুকআপগুলোর জন্য প্রাইমারি কী হিসাবে ‘id’ ব্যবহার করে সংশ্লিষ্ট longURL এবং এর বিপরীতটি পুনরুদ্ধার করা যায়।] চিত্র ৪

হ্যাশ ফাংশন (Hash function)

হ্যাশ ফাংশন একটি বড় URL কে একটি শর্ট URL-এ হ্যাশ করতে ব্যবহৃত হয়, যাকে hashValue-ও বলা হয়।

হ্যাশ ভ্যালুর দৈর্ঘ্য (Hash value length)

hashValue [0-9, a-z, A-Z] থেকে ক্যারেক্টার নিয়ে গঠিত, যাতে ১০ + ২৬ + ২৬ = ৬২টি সম্ভাব্য ক্যারেক্টার রয়েছে। hashValue-এর দৈর্ঘ্য বের করতে, ক্ষুদ্রতম n খুঁজে বের করুন যাতে 62^n ≥ 365 বিলিয়ন হয়। খসড়া অনুমানের ওপর ভিত্তি করে সিস্টেমটিকে অবশ্যই ৩৬৫ বিলিয়ন URL পর্যন্ত সমর্থন করতে হবে। টেবিল ১ hashValue-এর দৈর্ঘ্য এবং এটি সমর্থন করতে পারে এমন URL-এর সর্বোচ্চ সংখ্যা দেখায়।

টেবিল ১

যখন n = 7, 62 ^ n = ~3.5 ট্রিলিয়ন, 3.5 ট্রিলিয়ন 365 বিলিয়ন URL ধারণ করার জন্য যথেষ্টের বেশি, তাই hashValue-এর দৈর্ঘ্য হলো ৭।

আমরা একটি URL শর্টনারের জন্য দুই ধরনের হ্যাশ ফাংশন অন্বেষণ করব। প্রথমটি হলো “হ্যাশ + কোলিশন রেজোলিউশন (hash + collision resolution)”, এবং দ্বিতীয়টি হলো “বেস ৬২ কনভার্সন (base 62 conversion)।” আসুন সেগুলো একে একে দেখি।

হ্যাশ + কোলিশন রেজোলিউশন (Hash + collision resolution)

একটি বড় URL শর্ট করতে, আমাদের একটি হ্যাশ ফাংশন বাস্তবায়ন করা উচিত যা একটি বড় URL কে ৭-ক্যারেক্টারের একটি স্ট্রিংয়ে হ্যাশ করে। একটি সহজবোধ্য সমাধান হলো CRC32, MD5, বা SHA-1 এর মতো সুপরিচিত হ্যাশ ফাংশন ব্যবহার করা। নিচের টেবিলটি এই URL-এ বিভিন্ন হ্যাশ ফাংশন প্রয়োগ করার পরে হ্যাশ ফলাফলগুলোর তুলনা দেখায়: https://en.wikipedia.org/wiki/Systems_design

টেবিল ২

টেবিল ২-এ দেখানো হয়েছে, সবচেয়ে ছোট হ্যাশ ভ্যালুটিও (CRC32 থেকে) অনেক বড় (৭ ক্যারেক্টারের বেশি)। আমরা কীভাবে এটিকে ছোট করতে পারি?

প্রথম পদ্ধতিটি হলো একটি হ্যাশ ভ্যালুর প্রথম ৭টি ক্যারেক্টার সংগ্রহ করা; তবে, এই পদ্ধতিটি হ্যাশ কোলিশনের (hash collisions) দিকে নিয়ে যেতে পারে। হ্যাশ কোলিশন সমাধান করতে, আমরা আর কোনো কোলিশন আবিষ্কৃত না হওয়া পর্যন্ত রিকার্সিভলি একটি নতুন পূর্বনির্ধারিত স্ট্রিং যুক্ত করতে পারি। এই প্রক্রিয়াটি চিত্র ৫-এ ব্যাখ্যা করা হয়েছে।

[চিত্র ৫-এর বর্ণনা: ছবিটি URL শর্টনিং প্রক্রিয়া চিত্রিত করে এমন একটি ফ্লোচার্ট উপস্থাপন করে। এটি একটি সবুজ বৃত্ত দিয়ে শুরু হয় যার লেবেল ‘start,’ যা প্রক্রিয়াটি শুরু করে। একটি তীর চিহ্ন ‘input: longURL’ লেবেলযুক্ত একটি হালকা নীল আয়তক্ষেত্রের দিকে নিয়ে যায়, যা একটি বড় URL-এর ইনপুট নির্দেশ করে। এই বড় URL তারপর ‘hash function’ লেবেলযুক্ত একটি হালকা নীল আয়তক্ষেত্রে প্রবাহিত হয়, যেখানে একটি শর্ট করা URL তৈরি করতে একটি হ্যাশিং অ্যালগরিদম প্রয়োগ করা হয়। আউটপুট, ‘shortURL,’ অন্য একটি হালকা নীল আয়তক্ষেত্রে দেখানো হয়েছে। এই shortURL তারপর ‘exist in DB?’ লেবেলযুক্ত একটি হীরক-আকৃতির সিদ্ধান্ত নোডে প্রবেশ করে, যা পরীক্ষা করে যে shortURL টি ইতিমধ্যে একটি ডাটাবেসে (DB) আছে কিনা। যদি ‘হ্যাঁ’ (একটি কোলিশন) হয়, তবে একটি তীর চিহ্ন ‘longURL + predefi..’ লেবেলযুক্ত একটি হালকা নীল আয়তক্ষেত্রের দিকে নির্দেশ করে, যা নির্দেশ করে যে প্রক্রিয়াটিতে longURL-এ একটি পূর্বনির্ধারিত স্ট্রিং যুক্ত করা এবং হ্যাশিং প্রক্রিয়াটি পুনরাবৃত্তি করা জড়িত থাকতে পারে। যদি ‘না’ হয়, তবে একটি তীর চিহ্ন ‘save to DB’ লেবেলযুক্ত একটি হালকা নীল আয়তক্ষেত্রের দিকে নিয়ে যায়, যেখানে shortURL এবং এর সংশ্লিষ্ট longURL ডাটাবেসে সংরক্ষণ করা হয়। পরিশেষে, একটি তীর চিহ্ন ‘save to DB’ থেকে একটি সবুজ বৃত্ত ‘end’-এর দিকে নিয়ে যায়, যা প্রক্রিয়ার সমাপ্তি নির্দেশ করে। তীর চিহ্নগুলো সিস্টেম জুড়ে ডেটা এবং নিয়ন্ত্রণের প্রবাহ নির্দেশ করে।] চিত্র ৫

এই পদ্ধতিটি কোলিশন দূর করতে পারে; তবে, প্রতিটি রিকোয়েস্টের জন্য একটি shortURL ডাটাবেসে আছে কিনা তা পরীক্ষা করতে ডাটাবেসে কুয়েরি করা ব্যয়বহুল। ব্লুম ফিল্টার (bloom filters) [2] নামক একটি কৌশল পারফরম্যান্স উন্নত করতে পারে। একটি ব্লুম ফিল্টার হলো একটি স্পেস-এফিসিয়েন্ট (space-efficient) প্রোব্যাবিলিস্টিক কৌশল যা পরীক্ষা করে কোনো একটি উপাদান একটি সেটের সদস্য কিনা। আরও বিস্তারিত জানতে রেফারেন্স ম্যাটেরিয়াল [2] দেখুন।

বেস ৬২ কনভার্সন (Base 62 conversion)

বেস কনভার্সন হলো URL শর্টনারগুলোর জন্য সাধারণত ব্যবহৃত আরেকটি পদ্ধতি। বেস কনভার্সন তাদের বিভিন্ন সংখ্যা উপস্থাপনা সিস্টেমের মধ্যে একই সংখ্যাকে রূপান্তর করতে সাহায্য করে। বেস ৬২ কনভার্সন ব্যবহার করা হয় কারণ hashValue-এর জন্য ৬২টি সম্ভাব্য ক্যারেক্টার রয়েছে। রূপান্তরটি কীভাবে কাজ করে তা ব্যাখ্যা করতে একটি উদাহরণ ব্যবহার করি: 1115710 কে বেস ৬২ উপস্থাপনায় রূপান্তর করা (1115710 একটি বেস ১০ সিস্টেমে 11157 কে নির্দেশ করে)।

এর নাম থেকেই বোঝা যায়, বেস ৬২ হলো এনকোডিংয়ের জন্য ৬২টি ক্যারেক্টার ব্যবহার করার একটি উপায়। ম্যাপিংগুলো হলো: 0-0, …, 9-9, 10-a, 11-b, …, 35-z, 36-A, …, 61-Z, যেখানে ‘a’ মানে 10, ‘Z’ মানে 61, ইত্যাদি।

1115710 = 2 x 62^2 + 55 x 62^1 + 59 x 62^0 = [2, 55, 59] -> বেস ৬২ উপস্থাপনায় [2, T, X]। চিত্র ৬ কথোপকথন প্রক্রিয়াটি দেখায়।

[চিত্র ৬-এর বর্ণনা: ছবিটি একটি দশমিক সংখ্যাকে (11157) তার বেস-৬২ উপস্থাপনায় রূপান্তর চিত্রিত করে এমন একটি ডায়াগ্রাম উপস্থাপন করে। বাম দিকে একটি পুনরাবৃত্তি ভাগ প্রক্রিয়া দেখানো হয়েছে। সংখ্যা 11157 কে বারবার 62 দ্বারা ভাগ করা হয়, ডানদিকে ভাগশেষগুলো দেখানো হয় (59, 55, এবং 2)। প্রতিটি ভাগের ভাগফল পরবর্তী ধাপে ভাজ্য হয়ে যায় (11157/62 = 179 ভাগশেষ 59; 179/62 = 2 ভাগশেষ 55; 2/62 = 0 ভাগশেষ 2)। ভাগশেষগুলো বেস-৬২ উপস্থাপনা গঠ করতে বিপরীত ক্রমে তালিকাভুক্ত করা হয় (‘X T 2’), যেখানে ‘X’ 59 এবং ‘T’ 55 নির্দেশ করে। চূড়ান্ত ভাগশেষ হলো 0, যা রূপান্তরের সমাপ্তি নির্দেশ করে। ডায়াগ্রামটি দৃশ্যত প্রতিটি ভাগের ধাপকে একটি রেখা দিয়ে সংযুক্ত করে, প্রাথমিক দশমিক সংখ্যা থেকে এর বেস-৬২ সমতুল্যে গণনার প্রবাহ দেখায়।] চিত্র ৬

সুতরাং, শর্ট URL টি হলো https://tinyurl.com/2TX

দুটি পদ্ধতির তুলনা (Comparison of the two approaches)

টেবিল ৩ দুটি পদ্ধতির পার্থক্য দেখায়।

টেবিল ৩

URL শর্টনিং গভীর বিশ্লেষণ (URL shortening deep dive)

সিস্টেমের মূল অংশগুলোর একটি হিসাবে, আমরা চাই URL শর্টনিং প্রবাহটি যৌক্তিকভাবে সহজ এবং কার্যকরী হোক। আমাদের ডিজাইনে বেস ৬২ কনভার্সন ব্যবহার করা হয়েছে। প্রবাহটি প্রদর্শন করতে আমরা নিম্নলিখিত ডায়াগ্রাম (চিত্র ৭) তৈরি করেছি।

[চিত্র ৭-এর বর্ণনা: ছবিটি URL শর্টনিং প্রক্রিয়া চিত্রিত করে এমন একটি ফ্লোচার্ট উপস্থাপন করে। এটি ‘1. input: longURL’ লেবেলযুক্ত একটি আয়তক্ষেত্রাকার বাক্স দিয়ে শুরু হয়, যা একটি বড় URL-এর ইনপুট নির্দেশ করে। একটি তীর চিহ্ন এটিকে একটি হীরক-আকৃতির সিদ্ধান্ত বাক্স, ‘2. longURL in DB?’ এর সাথে সংযুক্ত করে, যা পরীক্ষা করে যে বড় URL টি ইতিমধ্যে ডাটাবেসে (DB) আছে কিনা। যদি ‘হ্যাঁ’ হয়, তবে একটি তীর চিহ্ন একটি আয়তক্ষেত্রাকার বাক্স, ‘3. return shortURL’ এর দিকে নির্দেশ করে, যা নির্দেশ করে যে সংশ্লিষ্ট শর্ট URL ফেরত দেওয়া হয়। যদি ‘না’ হয়, তবে একটি তীর চিহ্ন একটি আয়তক্ষেত্রাকার বাক্স, ‘4. Generate a ne…’ এর দিকে নিয়ে যায়, যা একটি নতুন অনন্য ID তৈরি করার পরামর্শ দেয়। এরপর একটি বাক্স follows, ‘5. Convert ID to…’, যা এই ID-টিকে একটি শর্ট URL-এ রূপান্তর করার ইঙ্গিত দেয়। পরিশেষে, একটি তীর চিহ্ন ‘6. Save ID, shor…’ এর সাথে সংযুক্ত হয়, যা ডাটাবেসে ID এবং শর্ট URL উভয়ই সংরক্ষণ করার নির্দেশ দেয়। পুরো প্রবাহটি ক্রমিক, যেখানে প্রতিটি ধাপ পূর্ববর্তীটির ওপর নির্ভরশীল, একটি বিদ্যমান শর্ট URL ফেরত দেওয়া অথবা একটি নতুন তৈরি এবং সংরক্ষণ করার মাধ্যমে শেষ হয়।] চিত্র ৭

1. longURL হলো ইনপুট।
2. সিস্টেম পরীক্ষা করে যে longURL টি ডাটাবেসে আছে কিনা।
3. যদি থাকে, তবে এর অর্থ হলো longURL টি আগে shortURL-এ রূপান্তরিত হয়েছিল। এই ক্ষেত্রে, ডাটাবেস থেকে shortURL টি নিয়ে আসুন এবং এটি ক্লায়েন্টে ফেরত দিন।
4. যদি না থাকে, তবে longURL টি নতুন। অনন্য ID জেনারেটর দ্বারা একটি নতুন অনন্য ID (প্রাইমারি কী) তৈরি করা হয়।
5. বেস ৬২ কনভার্সন ব্যবহার করে ID টিকে shortURL-এ রূপান্তর করুন।
6. ID, shortURL, এবং longURL সহ একটি নতুন ডাটাবেস সারি তৈরি করুন।

প্রবাহটিকে বোঝা সহজ করতে, আসুন একটি বাস্তব উদাহরণ দেখি। ধরে নিচ্ছি ইনপুট longURL হলো: https://en.wikipedia.org/wiki/Systems_design

• অনন্য ID জেনারেটর ID ফেরত দেয়: 2009215674938।
• বেস ৬২ কনভার্সন ব্যবহার করে ID টিকে shortURL-এ রূপান্তর করুন। ID (2009215674938) “zn9edcu”-তে রূপান্তরিত হয়।
• টেবিল ৪-এ দেখানো হিসাবে ID, shortURL, এবং longURL কে ডাটাবেসে সংরক্ষণ করুন।

টেবিল ৪

ডিস্ট্রিবিউটেড অনন্য ID জেনারেটরের কথা উল্লেখ করা মূল্যবান। এর প্রাথমিক কাজ হলো গ্লোবালি অনন্য ID তৈরি করা, যা shortURL তৈরির জন্য ব্যবহৃত হয়। একটি অত্যন্ত ডিস্ট্রিবিউটেড পরিবেশে, একটি অনন্য ID জেনারেটর বাস্তবায়ন করা চ্যালেঞ্জিং। সৌভাগ্যবশত, আমরা ইতিমধ্যে “ডিজাইন এ ইউনিক আইডি জেনারেটর ইন ডিস্ট্রিবিউটেড সিস্টেমস” অধ্যায়ে কয়েকটি সমাধান নিয়ে আলোচনা করেছি। আপনার স্মৃতি ঝালাই করতে আপনি সেখানে ফিরে যেতে পারেন।

URL রিডাইরেক্টিং গভীর বিশ্লেষণ (URL redirecting deep dive)

চিত্র ৮ URL রিডাইরেক্টিংয়ের বিস্তারিত ডিজাইন দেখায়। যেহেতু রাইটের চেয়ে রিড বেশি হয়, তাই পারফরম্যান্স উন্নত করতে <shortURL, longURL> ম্যাপিং একটি ক্যাশে সংরক্ষণ করা হয়।

[চিত্র ৮-এর বর্ণনা: ছবিটি একটি শর্ট করা URL-এর জন্য একজন ব্যবহারকারীর রিকোয়েস্ট এবং এর সমাধান চিত্রিত করে এমন একটি সরলীকৃত সিস্টেম আর্কিটেকচার ডায়াগ্রাম উপস্থাপন করে। একজন ব্যবহারকারী (একটি ল্যাপটপ এবং একটি মোবাইল ফোনের আইকন দ্বারা উপস্থাপিত) শর্ট করা URL ‘https://tinyurl.com/zn9edcu’-তে  একটি GET রিকোয়েস্ট (১) শুরু করেন। এই রিকোয়েস্টটি একটি লোড ব্যালেন্সার (২)-এ নির্দেশিত হয়, যা একাধিক ওয়েব সার্ভার জুড়ে ট্র্যাফিক বিতরণ করে। ওয়েব সার্ভারগুলো তারপর ব্যবহারকারীর কাছে বড় URL ‘https://en.wikipedia.org/wiki/Systems_design ’ (৫) ফেরত দেয়। ওয়েব সার্ভারগুলো ঘন ঘন অনুরোধ করা ডেটায় দ্রুত অ্যাক্সেসের জন্য একটি ক্যাশ (৩) এবং তথ্যের স্থায়ী সংরক্ষণের জন্য একটি ডাটাবেস (৪)-এর সাথে সংযুক্ত। নম্বরযুক্ত তীর চিহ্নগুলো (১-৫) রিকোয়েস্ট এবং রেসপন্সের প্রবাহ নির্দেশ করে, ব্যবহারকারী, লোড ব্যালেন্সার, ওয়েব সার্ভার, ক্যাশ এবং ডাটাবেসের মধ্যে মিথস্ক্রিয়া দেখায়।] চিত্র ৮

URL রিডাইরেক্টিংয়ের প্রবাহটি নিম্নরূপে সংক্ষেপিত করা হলো:

1. একজন ব্যবহারকারী একটি শর্ট URL লিংকে ক্লিক করেন: https://tinyurl.com/zn9edcu
2. লোড ব্যালেন্সার রিকোয়েস্টটি ওয়েব সার্ভারগুলোতে ফরওয়ার্ড করে।
3. যদি একটি shortURL ইতিমধ্যে ক্যাশে থাকে, তবে সরাসরি longURL ফেরত দিন।
4. যদি একটি shortURL ক্যাশে না থাকে, তবে ডাটাবেস থেকে longURL নিয়ে আসুন। যদি এটি ডাটাবেসে না থাকে, তবে সম্ভবত একজন ব্যবহারকারী একটি অবৈধ shortURL এন্টার করেছেন।
5. longURL টি ব্যবহারকারীর কাছে ফেরত দেওয়া হয়।