একটি বাক্স ছাড়া শ্রোডিঞ্জারের বিড়াল: বিতরণ সিস্টেমে ঐক্যমত্য সমস্যা

তাই কল্পনা করা যাক. 5টি বিড়াল ঘরে তালাবদ্ধ, এবং মালিককে জাগানোর জন্য, তাদের সবাইকে এই বিষয়ে একমত হতে হবে, কারণ তারা কেবলমাত্র তাদের পাঁচজনের সাথে এটির উপর হেলান দিয়ে দরজা খুলতে পারে। বিড়ালদের মধ্যে একটি যদি শ্রোডিঞ্জারের বিড়াল হয় এবং অন্য বিড়ালরা তার সিদ্ধান্ত সম্পর্কে অবগত না থাকে, তাহলে প্রশ্ন ওঠে: "তারা কীভাবে এটি করতে পারে?"

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

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

আসলে, আমাদের কাছে যে গ্যারান্টি রয়েছে তা সরবরাহকারীর গ্যারান্টি। সেগুলিকে ডকুমেন্টেশনে নিম্নরূপ বর্ণনা করা হয়েছে: "এই পরিষেবাটি বেশ নির্ভরযোগ্য, এটির একটি প্রদত্ত SLA রয়েছে, চিন্তা করবেন না, সবকিছু আপনার প্রত্যাশা অনুযায়ী বিতরণ করা হবে।"

আমরা সেরাতে বিশ্বাস করার ঝোঁক, কারণ বড় কোম্পানির স্মার্ট চাচারা আমাদের আশ্বস্ত করেছেন যে সবকিছু ঠিক হয়ে যাবে। আমরা নিজেদেরকে জিজ্ঞাসা করি না: কেন, আসলে, এই সব কাজ করতে পারে? এই ধরনের সিস্টেমের সঠিক অপারেশন জন্য কোন আনুষ্ঠানিক ন্যায্যতা আছে?

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

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

পরবর্তীতে কী আলোচনা করা হবে তার হালকা চিত্র: দুই জেনারেলের সমস্যাওয়ার্ম-আপ দেখে নেওয়া যাক দুই জেনারেলের কাজ.

আমাদের দুটি সেনাবাহিনী আছে - লাল এবং সাদা। সাদা সৈন্যরা অবরুদ্ধ শহরে অবস্থান করছে। জেনারেল A1 এবং A2 এর নেতৃত্বে লাল সৈন্যরা শহরের দুই পাশে অবস্থান করছে। রেডহেডদের কাজ হ'ল সাদা শহর আক্রমণ করা এবং জয় করা। যাইহোক, প্রতিটি লাল জেনারেলের সেনাবাহিনী পৃথকভাবে সাদাদের সেনাবাহিনীর চেয়ে ছোট।

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

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

ধরুন A1 A2 তে একজন মেসেঞ্জার পাঠায় এই বার্তাটি: "আসুন আজ মধ্যরাতে আক্রমণ করি!"। জেনারেল A1 জেনারেল A2 থেকে নিশ্চিতকরণ ছাড়া আক্রমণ করতে পারে না। যদি A1 থেকে মেসেঞ্জার পৌঁছে যায়, তাহলে জেনারেল A2 বার্তার সাথে একটি নিশ্চিতকরণ পাঠায়: "হ্যাঁ, আসুন আজ সাদাগুলি পূরণ করি।" কিন্তু এখন জেনারেল A2 জানেন না যে তার বার্তাবাহক পৌঁছেছে কি না, তার কোনো গ্যারান্টি নেই যে আক্রমণটি একই সাথে হবে কিনা। এখন জেনারেল A2 আবার নিশ্চিতকরণ প্রয়োজন।

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

দুটি জেনারেলের সমস্যা হল একটি খুব সাধারণ বিতরণ করা সিস্টেমের একটি দুর্দান্ত চিত্র যেখানে অবিশ্বস্ত যোগাযোগের সাথে দুটি নোড রয়েছে। তাই আমাদের কাছে 100% গ্যারান্টি নেই যে সেগুলি সিঙ্ক্রোনাইজ করা হয়েছে৷ অনুরূপ সমস্যা সম্পর্কে শুধুমাত্র একটি বৃহত্তর স্কেলে পরে নিবন্ধে.

বিতরণ সিস্টেমের ধারণা প্রবর্তন

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

বার্তাগুলি কীভাবে বিশেষভাবে প্রয়োগ করা হয়, কী প্রোটোকল ব্যবহার করা হয় - এই প্রসঙ্গে আমাদের আগ্রহ নেই। এটি গুরুত্বপূর্ণ যে একটি বিতরণ করা সিস্টেমের নোডগুলি বার্তা পাঠিয়ে একে অপরের সাথে ডেটা বিনিময় করতে পারে।

সংজ্ঞাটি নিজেই খুব জটিল মনে হয় না, তবে মনে রাখবেন যে একটি বিতরণ করা সিস্টেমে অনেকগুলি বৈশিষ্ট্য রয়েছে যা আমাদের জন্য গুরুত্বপূর্ণ হবে।

বিতরণ করা সিস্টেমের বৈশিষ্ট্য

1. concurrency - সিস্টেমে একযোগে বা প্রতিযোগিতামূলক ঘটনা ঘটার সম্ভাবনা। অধিকন্তু, আমরা বিবেচনা করব যে দুটি ভিন্ন নোডে ঘটে যাওয়া ইভেন্টগুলি সম্ভাব্য সমসাময়িক যতক্ষণ না আমাদের কাছে এই ঘটনাগুলি ঘটতে পারে এমন একটি সুস্পষ্ট ক্রম নেই। এবং সাধারণত আমরা না.
2. বিশ্বব্যাপী ঘড়ি নেই. বিশ্বব্যাপী ঘড়ির অভাবের কারণে আমাদের কাছে ঘটনার সুস্পষ্ট ক্রম নেই। মানুষের সাধারণ জগতে, আমরা এই সত্যে অভ্যস্ত যে আমাদের কাছে ঘন্টা এবং সময় রয়েছে। বিতরণ সিস্টেমের ক্ষেত্রে সবকিছু পরিবর্তন হয়। এমনকি অতি-নির্ভুল পারমাণবিক ঘড়িগুলিও প্রবাহিত হয়েছে, এবং এমন পরিস্থিতি রয়েছে যেখানে আমরা বলতে পারি না যে দুটি ঘটনার মধ্যে কোনটি প্রথম ঘটেছে। অতএব, আমরা সময়ের উপর নির্ভর করতে পারি না।
3. সিস্টেম নোডের স্বাধীন ব্যর্থতা. আরেকটি সমস্যা আছে: কিছু ভুল হতে পারে কারণ আমাদের নোডগুলি চিরন্তন নয়। হার্ড ড্রাইভ ব্যর্থ হতে পারে, ক্লাউডের ভার্চুয়াল মেশিন রিবুট হতে পারে, নেটওয়ার্ক ব্লিঙ্ক হতে পারে এবং বার্তাগুলি হারিয়ে যেতে পারে। তদুপরি, এমন পরিস্থিতি রয়েছে যখন নোডগুলি কাজ করে, তবে একই সময়ে তারা সিস্টেমের বিরুদ্ধে কাজ করে। সমস্যাগুলির শেষ শ্রেণীর এমনকি একটি পৃথক নাম পেয়েছে: সমস্যা বাইজেন্টাইন জেনারেলরা. এই ধরনের সমস্যা সহ একটি বিতরণ সিস্টেমের সবচেয়ে জনপ্রিয় উদাহরণ হল ব্লকচেইন। কিন্তু আজ আমরা এই বিশেষ শ্রেণীর সমস্যা বিবেচনা করব না। আমরা এমন পরিস্থিতিতে আগ্রহী হব যেখানে শুধুমাত্র এক বা একাধিক নোড ব্যর্থ হতে পারে।
4. নোডের মধ্যে যোগাযোগ মডেল (মেসেজিং মডেল). আমরা ইতিমধ্যেই খুঁজে পেয়েছি যে নোডগুলি বার্তা আদান-প্রদানের মাধ্যমে যোগাযোগ করে। দুটি সুপরিচিত মেসেজিং মডেল রয়েছে: সিঙ্ক্রোনাস এবং অ্যাসিঙ্ক্রোনাস।

বিতরণ করা সিস্টেমে নোডের মধ্যে যোগাযোগের মডেল

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

অ্যাসিঙ্ক্রোনাস মডেল - অ্যাসিঙ্ক্রোনাস মডেলগুলিতে, আমরা ধরে নিই যে অপেক্ষার সময় সীমিত, তবে কোনও সময় ডেল্টা নেই যার পরে এটি নিশ্চিত করা যেতে পারে যে নোডটি ব্যর্থ হয়েছে। সেগুলো. একটি নোড থেকে একটি বার্তার জন্য অপেক্ষার সময় নির্বিচারে দীর্ঘ হতে পারে। এটি একটি গুরুত্বপূর্ণ সংজ্ঞা, এবং আমরা এটি সম্পর্কে আরও কথা বলব।

বিতরণ ব্যবস্থায় ঐক্যমতের ধারণা

ঐক্যমতের ধারণাকে আনুষ্ঠানিকভাবে সংজ্ঞায়িত করার আগে, এমন একটি পরিস্থিতির উদাহরণ বিবেচনা করুন যেখানে আমাদের এটি প্রয়োজন, যথা − রাজ্য মেশিন প্রতিলিপি.

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

অন্য কথায়: নোডগুলির কোনওটিই আপত্তি করেনি যে তাদের কাছে আরও আপ-টু-ডেট তথ্য রয়েছে এবং প্রস্তাবিত মানটি ভুল ছিল। নোডের মধ্যে একটি চুক্তি এবং একটি একক সঠিক গৃহীত মান সম্পর্কে চুক্তি হল একটি বিতরণ ব্যবস্থায় ঐকমত্য। পরবর্তী, আমরা অ্যালগরিদম সম্পর্কে কথা বলব যা একটি বিতরণ করা সিস্টেমকে একটি গ্যারান্টি সহ ঐকমত্যে পৌঁছানোর অনুমতি দেয়।

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

ঐকমত্য অ্যালগরিদমের বৈশিষ্ট্য

সম্মতি অ্যালগরিদমের অবশ্যই তিনটি বৈশিষ্ট্য থাকতে হবে যাতে সিস্টেমের অস্তিত্ব অব্যাহত থাকে এবং রাজ্য থেকে রাজ্যে পরিবর্তনের ক্ষেত্রে কিছু অগ্রগতি থাকে:

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

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

2. বিশুদ্ধতা - যদি সমস্ত সঠিকভাবে কাজ করা নোড একই মান অফার করে v, তাই প্রতিটি সঠিকভাবে কাজ করা নোডকে অবশ্যই এই মানটি গ্রহণ করতে হবে v.
3. পরিসমাপ্তি - সমস্ত সঠিকভাবে কাজ করা নোডগুলি অবশেষে কিছু মান (লাইভনেস প্রোপার্টি) গ্রহণ করবে, যা অ্যালগরিদমকে সিস্টেমে অগ্রগতি করতে দেয়। প্রতিটি পৃথক নোড যা সঠিকভাবে কাজ করে তাকে অবশ্যই শীঘ্র বা পরে চূড়ান্ত মান গ্রহণ করতে হবে এবং এটি নিশ্চিত করতে হবে: "আমার জন্য, এই মানটি সত্য, আমি পুরো সিস্টেমের সাথে একমত।"

ঐক্যমত অ্যালগরিদম কিভাবে কাজ করে তার একটি উদাহরণ

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

1. এটি সব একটি বিয়ের প্রস্তাব (প্রস্তাব) দিয়ে শুরু হয়। ধরুন একটি ক্লায়েন্ট "নোড 1" নামক একটি নোডের সাথে সংযোগ করে এবং একটি লেনদেন শুরু করে, নোডে একটি নতুন মান পাস করে - O৷ এখন থেকে, আমরা "নোড 1" কল করব। প্রদান. প্রস্তাবক হিসাবে "নোড 1" কে এখন পুরো সিস্টেমকে অবহিত করতে হবে যে তার কাছে নতুন ডেটা রয়েছে এবং তিনি অন্য সমস্ত নোডগুলিতে বার্তা পাঠান: "দেখুন! আমি "ও" মান পেয়েছি এবং আমি এটি লিখতে চাই! অনুগ্রহ করে নিশ্চিত করুন যে আপনি আপনার লগে "O"ও রেকর্ড করবেন৷'

   

2. পরবর্তী পর্যায়ে প্রস্তাবিত মান (ভোটিং) জন্য ভোট দেওয়া হয়। এটি কিসের জন্যে? এটি ঘটতে পারে যে অন্যান্য নোডগুলি আরও সাম্প্রতিক তথ্য পেয়েছে এবং তাদের কাছে একই লেনদেনের ডেটা রয়েছে৷

   
   
   যখন নোড "নোড 1" তার প্রোপাস পাঠায়, তখন অন্যান্য নোডগুলি এই ইভেন্টের ডেটার জন্য তাদের লগগুলি পরীক্ষা করে। যদি কোনও বিরোধ না থাকে, নোডগুলি ঘোষণা করে: "হ্যাঁ, এই ইভেন্টের জন্য আমার কাছে অন্য কোনও ডেটা নেই৷ 'O' মান হল সবচেয়ে আপ-টু-ডেট তথ্য যা আমরা প্রাপ্য।"

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

   ভোটের পর্যায়ে, নোডগুলি একটি সিদ্ধান্তে আসে: হয় তারা সবাই একই মান গ্রহণ করে, বা তাদের মধ্যে একজন বিপক্ষে ভোট দেয়, এটি বোঝায় যে তার কাছে আরও সাম্প্রতিক ডেটা রয়েছে।

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

   

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

সুতরাং, একটি সাধারণ ক্ষেত্রে ঐকমত্য অ্যালগরিদম চারটি ধাপ নিয়ে গঠিত: প্রস্তাব, ভোট (ভোট), গ্রহণ (স্বীকার), স্বীকৃতি নিশ্চিতকরণ (স্বীকৃত)।

যদি কিছু ধাপে আমরা চুক্তিতে পৌঁছাতে না পারি, তাহলে প্রস্তাবিত মান নিশ্চিত করতে অস্বীকারকারী নোডগুলি দ্বারা প্রদত্ত তথ্য বিবেচনা করে অ্যালগরিদমটি পুনরায় চালু করা হয়।

অ্যাসিঙ্ক্রোনাস সিস্টেমে একমত অ্যালগরিদম

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

এখন যেহেতু আমরা জানি যে নীতিগতভাবে ঐক্যমত্য অ্যালগরিদম কীভাবে কাজ করে, প্রশ্ন হল সেই সমস্ত অনুসন্ধিৎসু পাঠকদের জন্য যারা এই পয়েন্টে পৌঁছেছেন: একটি অ্যাসিঙ্ক্রোনাস মেসেজ মডেল সহ N নোডগুলির একটি সিস্টেমে কতগুলি নোড নেমে যেতে পারে যাতে সিস্টেমটি এখনও ঐক্যমতে পৌঁছাতে পারে ?

স্পয়লার পিছনে সঠিক উত্তর এবং যুক্তি.সঠিক উত্তর হল: 0. যদি একটি অ্যাসিঙ্ক্রোনাস সিস্টেমের একটি নোডও নিচে চলে যায়, তাহলে সিস্টেমটি ঐকমত্যে পৌঁছাতে সক্ষম হবে না। এই বিবৃতিটি সুপরিচিত এফএলপি উপপাদ্যে প্রমাণিত (1985, ফিশার, লিঞ্চ, প্যাটারসন, নিবন্ধের শেষে মূলটির সাথে লিঙ্ক): "অন্তত একটি নোড ব্যর্থ হলে একটি বিতরণকৃত ঐক্যমত্যে পৌঁছানোর অসম্ভবতা।"

বন্ধুরা, তাহলে আমাদের একটি সমস্যা আছে, আমরা এই সত্যে অভ্যস্ত যে সবকিছুই আমাদের সাথে অ্যাসিঙ্ক্রোনাস। এবং এখানে এটা. কীভাবে বাঁচতে হবে?

আমরা শুধু তত্ত্ব নিয়ে কথা বলেছি, গণিতের কথা বলেছি। "ঐক্যমত্যে পৌঁছানো যায় না" এর অর্থ কী, গাণিতিক ভাষা থেকে আমাদের - প্রকৌশলে অনুবাদ করা? এর মানে হল "সর্বদা অর্জন করা যায় না", অর্থাৎ এমন একটি ক্ষেত্রে রয়েছে যেখানে ঐক্যমত অর্জন করা যায় না। এবং এই মামলা কি?

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

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

অনুশীলনে, আমরা আংশিকভাবে সিঙ্ক্রোনাস যোগাযোগ মডেল নিয়ে কাজ করছি। আংশিক সিঙ্ক্রোনিজমকে নিম্নরূপ বোঝা যায়: সাধারণ ক্ষেত্রে, আমাদের একটি অ্যাসিঙ্ক্রোনাস মডেল রয়েছে, তবে নির্দিষ্ট সময়ের একটি নির্দিষ্ট বিন্দুর "গ্লোবাল স্ট্যাবিলাইজেশন টাইম" এর একটি নির্দিষ্ট ধারণা আনুষ্ঠানিকভাবে চালু করা হয়েছে।

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

প্যাক্সোস অ্যালগরিদম ঐকমত্য সমস্যা সমাধান করে

প্যাকসোস অ্যালগরিদমগুলির একটি পরিবার যা আংশিকভাবে সিঙ্ক্রোনাস সিস্টেমের জন্য ঐকমত্য সমস্যার সমাধান করে, শর্ত থাকে যে কিছু নোড ব্যর্থ হতে পারে। পক্সোস এর লেখক লেসলি ল্যাম্পোর্ট. তিনি 1989 সালে অ্যালগরিদমের অস্তিত্ব এবং সঠিকতার একটি আনুষ্ঠানিক প্রমাণ প্রস্তাব করেছিলেন।

কিন্তু প্রমাণটি কোনোভাবেই তুচ্ছ বলে প্রমাণিত হয়নি। প্রথম প্রকাশনাটি শুধুমাত্র 1998 সালে প্রকাশিত হয়েছিল (33 পৃষ্ঠা) অ্যালগরিদম বর্ণনা করে। যেহেতু এটি পরিণত হয়েছিল, এটি বোঝা অত্যন্ত কঠিন ছিল এবং 2001 সালে নিবন্ধটির জন্য একটি ব্যাখ্যা প্রকাশিত হয়েছিল, যা 14 পৃষ্ঠা নিয়েছিল। প্রকাশনাগুলির ভলিউমগুলি দেখানো হয়েছে যে প্রকৃতপক্ষে ঐক্যমত্যের সমস্যাটি মোটেও সহজ নয় এবং এই জাতীয় অ্যালগরিদমের পিছনে বুদ্ধিমান লোকদের একটি বিশাল কাজ রয়েছে।

এটি আকর্ষণীয় যে লেসলি ল্যাম্পোর নিজেই তার বক্তৃতায় উল্লেখ করেছেন যে দ্বিতীয় নিবন্ধ-ব্যাখ্যাটিতে একটি বিবৃতি রয়েছে, একটি লাইন (তিনি কোনটি নির্দিষ্ট করেননি), যা বিভিন্ন উপায়ে ব্যাখ্যা করা যেতে পারে। এবং এর কারণে, বিপুল সংখ্যক আধুনিক প্যাক্সোস বাস্তবায়ন বেশ সঠিকভাবে কাজ করে না।

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

Paxos এ ভূমিকা

প্যাক্সোস অ্যালগরিদমের ভূমিকার একটি ধারণা রয়েছে। তিনটি প্রধান বিবেচনা করুন (অতিরিক্ত ভূমিকা সহ পরিবর্তন আছে):

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

একটি নোড বিভিন্ন পরিস্থিতিতে বিভিন্ন ভূমিকা একত্রিত করতে পারে।

কোরামের ধারণা

আমরা একটি সিস্টেম আছে যে অনুমান N নোড এবং তাদের অধিকাংশ F নোড ব্যর্থ হতে পারে। যদি F নোড ব্যর্থ হয়, তাহলে আমাদের অন্তত থাকা উচিত 2F+1 গ্রহণকারী নোড।

এটি প্রয়োজনীয় যাতে আমরা সর্বদা, এমনকি সবচেয়ে খারাপ পরিস্থিতিতে, "ভাল", সঠিকভাবে কাজ করা নোডগুলির সংখ্যাগরিষ্ঠতা থাকে। এটাই f+1 "ভাল" নোড যা সম্মত হয়েছে, এবং চূড়ান্ত মান গ্রহণ করা হবে। অন্যথায়, এমন পরিস্থিতি হতে পারে যেখানে বিভিন্ন স্থানীয় গোষ্ঠী বিভিন্ন অর্থ গ্রহণ করবে এবং নিজেদের মধ্যে একমত হতে পারবে না। তাই ভোটে জিততে আমাদের নিরঙ্কুশ সংখ্যাগরিষ্ঠতা দরকার।

প্যাক্সোস কনসেনসাস অ্যালগরিদমের সাধারণ ধারণা

প্যাক্সোস অ্যালগরিদম দুটি বৃহৎ পর্যায় অনুমান করে, যা ফলস্বরূপ প্রতিটি দুটি ধাপে বিভক্ত:

1. পর্যায় 1a: প্রস্তুত করুন. প্রস্তুতির পর্যায়ে, নেতা (প্রস্তাবক) সমস্ত নোডকে অবহিত করেন: “আমরা একটি নতুন ভোটিং পর্যায় শুরু করছি। আমরা একটি নতুন রাউন্ড আছে. এই রাউন্ডের সংখ্যা n। আমরা এখন ভোট শুরু করব।" এখন পর্যন্ত, এটি শুধুমাত্র একটি নতুন চক্রের শুরুর রিপোর্ট করে, কিন্তু নতুন মান রিপোর্ট করে না। এই পর্যায়ের কাজটি হল একটি নতুন রাউন্ড শুরু করা এবং প্রত্যেককে তার অনন্য সংখ্যা জানানো। রাউন্ড নম্বরটি গুরুত্বপূর্ণ, এটি অবশ্যই পূর্ববর্তী সমস্ত নেতাদের ভোটের সংখ্যার চেয়ে বেশি হতে হবে। যেহেতু এটি রাউন্ড নম্বরের জন্য ধন্যবাদ যে সিস্টেমের অন্যান্য নোডগুলি নেতার ডেটা কতটা তাজা তা বুঝতে পারবে। সম্ভবত অন্যান্য নোডগুলিতে ইতিমধ্যেই অনেক পরবর্তী রাউন্ড থেকে ভোটের ফলাফল রয়েছে এবং নেতাকে সহজভাবে বলবে যে তিনি সময়ের পিছনে রয়েছেন।
2. পর্যায় 1 বি: প্রতিশ্রুতি. যখন গ্রহণকারী নোডগুলি নতুন ভোটিং পর্যায়ের সংখ্যা পেয়েছে, তখন দুটি ফলাফল সম্ভব:
   • নতুন ভোটের n সংখ্যাটি আগের যেকোনও ভোটের সংখ্যার চেয়ে বেশি যেখানে গ্রহণকারী অংশগ্রহণ করেছিলেন। তারপর গ্রহণকারী নেতার কাছে একটি প্রতিশ্রুতি পাঠায় যে এটি n-এর চেয়ে কম সংখ্যার কোনো ভোটে আর অংশগ্রহণ করবে না। যদি গ্রহণকারী ইতিমধ্যেই কিছুর জন্য ভোট দিয়ে থাকে (অর্থাৎ, এটি ইতিমধ্যেই দ্বিতীয় পর্বে কিছু মান গ্রহণ করেছে), তবে এটি গৃহীত মান এবং তার প্রতিশ্রুতিতে অংশ নেওয়া ভোটের সংখ্যা যুক্ত করে।
   • অন্যথায়, যদি গ্রহণকারী ইতিমধ্যেই উচ্চ-সংখ্যার ভোট সম্পর্কে জানেন, তবে এটি কেবল প্রস্তুত পদক্ষেপকে উপেক্ষা করতে পারে এবং নেতাকে সাড়া দিতে পারে না।
3. পর্যায় 2a: গ্রহণ করুন. নেতাকে কোরাম থেকে প্রতিক্রিয়ার জন্য অপেক্ষা করতে হবে (সিস্টেমের বেশিরভাগ নোড) এবং, যদি প্রয়োজনীয় সংখ্যক প্রতিক্রিয়া পাওয়া যায়, তবে ইভেন্টগুলির বিকাশের জন্য তার কাছে দুটি বিকল্প রয়েছে:
   • কিছু গ্রহণকারী মান জমা দিয়েছেন যা তারা ইতিমধ্যে ভোট দিয়েছে। এক্ষেত্রে নেতা সর্বোচ্চ নম্বর পেয়ে ভোট থেকে মান নির্বাচন করেন। আসুন এই মানটিকে x বলি, এবং সমস্ত নোডগুলিতে এইরকম একটি বার্তা পাঠাই: "স্বীকার করুন (n, x)", যেখানে প্রথম মানটি তার নিজস্ব প্রস্তাবের ধাপ থেকে ভোটদানের নম্বর, এবং দ্বিতীয় মানটি হল সবাই যার জন্য জড়ো হয়েছিল, অর্থাৎ। মূল্য যার জন্য, আসলে, আমরা ভোট.
   • যদি গ্রহণকারীদের মধ্যে কেউ কোনো মান না পাঠায়, কিন্তু তারা কেবল এই রাউন্ডে ভোট দেওয়ার প্রতিশ্রুতি দেয়, নেতা তাদের তাদের মূল্যের জন্য ভোট দেওয়ার জন্য আমন্ত্রণ জানাতে পারেন, যার জন্য তিনি নেতা হয়েছিলেন। এর y কল করা যাক. এটি সমস্ত নোডকে ফর্মের একটি বার্তা পাঠায়: "স্বীকার করুন (n, y)", পূর্ববর্তী ফলাফলের সাথে সাদৃশ্য দ্বারা।
4. পর্যায় 2b: গৃহীত. আরও, গ্রহণকারী নোডগুলি, নেতার কাছ থেকে "স্বীকার করুন (...)" বার্তাটি পাওয়ার পরে এটির সাথে সম্মত হন (সমস্ত নোডগুলিতে নিশ্চিতকরণ পাঠান যে তারা নতুন মূল্যের সাথে একমত) শুধুমাত্র যদি তারা কিছু (অন্যান্য) প্রতিশ্রুতি না করে থাকে। নেতা রাউন্ডের সংখ্যা নিয়ে ভোটে অংশগ্রহণ করবেন n' > nঅন্যথায় তারা নিশ্চিতকরণ প্রম্পট উপেক্ষা করে।

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

এইভাবে Paxos অ্যালগরিদম কাজ করে। এই প্রতিটি পর্যায়ে অনেক সূক্ষ্মতা রয়েছে, আমরা কার্যত বিভিন্ন ধরণের ব্যর্থতা, একাধিক নেতার সমস্যা এবং আরও অনেক কিছু বিবেচনা করিনি, তবে এই নিবন্ধটির উদ্দেশ্য শুধুমাত্র পাঠককে শীর্ষ স্তরে বিতরণ করা কম্পিউটিং জগতের সাথে পরিচয় করিয়ে দেওয়া।

এটিও লক্ষণীয় যে প্যাক্সোস তার ধরণের একমাত্র নয়, অন্যান্য অ্যালগরিদম রয়েছে, উদাহরণস্বরূপ, ভেলা, কিন্তু এটি অন্য নিবন্ধের জন্য একটি বিষয়.

আরও অধ্যয়নের জন্য উপকরণ লিঙ্ক

নবাগত স্তর:

• কীভাবে বিতরণকৃত ঐক্যমত কাজ করে?, প্রীতি কাসিরেড্ডি, মিডিয়াম ব্লগ নিবন্ধ
• Paxos সহজ করা. বাস্তবিক, আদি কাঞ্চেরলা, মিডিয়াম ব্লগ নিবন্ধ
• বিকেন্দ্রীভূত চিন্তাধারাইত্তাই আব্রাহাম ব্লগ
• সিঙ্ক্রোনি, অ্যাসিঙ্ক্রোনি এবং আংশিক সিঙ্ক্রোনাইজেশন, Ittai আব্রাহাম, ব্লগ নিবন্ধ

লেসলি ল্যামপোর্ট স্তর:

• একটি ত্রুটিপূর্ণ প্রক্রিয়ার সাথে বিতরণকৃত ঐক্যমতের অসম্ভবতা (এফএলপি অসম্ভব)ফিশার, লিঞ্চ এবং প্যাটারসন, গবেষণা পত্র, 1985
• খণ্ডকালীন সংসদ, লেসলি ল্যামপোর্ট, গবেষণা পত্র, 1998
• Paxos সহজ করা, লেসলি ল্যামপোর্ট, গবেষণা পত্র, 2001

উত্স: www.habr.com