এই অপ্রয়োজনীয়তা মত দেখায় কি

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

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

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

* ইংরেজি ভাষার সাহিত্যে, রিডানডেন্সি কোডগুলিকে প্রায়শই ইরেজার কোড বলা হয়।

1. রিডানডেন্সি কোডের সারমর্ম

সমস্ত রিডানডেন্সি কোডের সারমর্ম অত্যন্ত সহজ: ডেটা সঞ্চয় করুন (বা প্রেরণ করুন) যাতে ত্রুটিগুলি ঘটলে এটি হারিয়ে না যায় (ডিস্ক ব্যর্থতা, ডেটা স্থানান্তর ত্রুটি, ইত্যাদি)।

বেশির ভাগ* রিডানডেন্সি কোডে, ডেটা এন ডেটা ব্লকে বিভক্ত, যার জন্য রিডানডেন্সি কোডের m ব্লক গণনা করা হয়, যার ফলে মোট n + m ব্লক হয়। রিডানডেন্সি কোডগুলি এমনভাবে তৈরি করা হয় যাতে n + m ব্লকের একটি অংশ ব্যবহার করে ডেটার n ব্লকগুলি পুনরুদ্ধার করা যায়। এর পরে, আমরা শুধুমাত্র ব্লক রিডানডেন্সি কোডগুলি বিবেচনা করব, অর্থাৎ, যেগুলিতে ডেটা ব্লকগুলিতে বিভক্ত।

সমস্ত n ব্লক ডেটা পুনরুদ্ধার করতে, আপনার কমপক্ষে n + m ব্লক থাকতে হবে, যেহেতু আপনি শুধুমাত্র n-1 ব্লক দিয়ে n ব্লক পেতে পারবেন না (এই ক্ষেত্রে, আপনাকে পাতলা থেকে 1 ব্লক নিতে হবে বায়ু")। n + m ব্লকের র্যান্ডম ব্লকগুলি কি সমস্ত ডেটা পুনরুদ্ধার করার জন্য যথেষ্ট? এটি রিডানড্যান্সি কোডের ধরণের উপর নির্ভর করে, উদাহরণস্বরূপ, রিড-সলোমন কোডগুলি আপনাকে নির্বিচারে এন ব্লক ব্যবহার করে সমস্ত ডেটা পুনরুদ্ধার করতে দেয়, তবে LRC রিডানড্যান্সি কোডগুলি সর্বদা নয়।

তথ্য ভান্ডার

ডেটা স্টোরেজ সিস্টেমে, একটি নিয়ম হিসাবে, প্রতিটি ডেটা ব্লক এবং রিডানডেন্সি কোড ব্লক একটি পৃথক ডিস্কে লেখা হয়। তারপর, যদি একটি নির্বিচারে ডিস্ক ব্যর্থ হয়, মূল ডেটা এখনও পুনরুদ্ধার করা এবং পড়তে পারে। একই সময়ে একাধিক ডিস্ক ব্যর্থ হলেও ডেটা পুনরুদ্ধার করা যেতে পারে।

তথ্য স্থানান্তর

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

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

2. রিড-সলোমন কোড

রিড-সলোমন কোড হল বহুল ব্যবহৃত রিডানডেন্সি কোডগুলির মধ্যে একটি, যা 1960-এর দশকে উদ্ভাবিত হয়েছিল এবং 1980-এর দশকে কমপ্যাক্ট ডিস্কের ব্যাপক উত্পাদনের জন্য প্রথম ব্যাপকভাবে ব্যবহৃত হয়েছিল।

রিড-সলোমন কোড বোঝার জন্য দুটি মূল প্রশ্ন রয়েছে: 1) রিডানডেন্সি কোডের ব্লক কীভাবে তৈরি করবেন; 2) কীভাবে রিডানডেন্সি কোড ব্লক ব্যবহার করে ডেটা পুনরুদ্ধার করবেন। আসুন তাদের উত্তর খুঁজে বের করা যাক।
সরলতার জন্য, আমরা আরও অনুমান করব যে n=6 এবং m=4। অন্যান্য স্কিম সাদৃশ্য দ্বারা বিবেচনা করা হয়.

রিডানডেন্সি কোড ব্লক কিভাবে তৈরি করবেন

রিডানডেন্সি কোডের প্রতিটি ব্লক অন্যদের থেকে স্বাধীনভাবে গণনা করা হয়। সমস্ত n ডেটা ব্লক প্রতিটি ব্লক গণনা করতে ব্যবহৃত হয়। নীচের চিত্রে, X1-X6 হল ডেটা ব্লক, P1-P4 হল রিডানডেন্সি কোড ব্লক৷

সমস্ত ডেটা ব্লক একই আকারের হতে হবে এবং শূন্য বিটগুলি প্রান্তিককরণের জন্য ব্যবহার করা যেতে পারে। ফলস্বরূপ রিডানডেন্সি কোড ব্লকগুলি ডেটা ব্লকের মতো একই আকারের হবে। সমস্ত ডেটা ব্লক শব্দে বিভক্ত (উদাহরণস্বরূপ, 16 বিট)। ধরা যাক আমরা ডেটা ব্লককে k শব্দে বিভক্ত করি। তারপর রিডানডেন্সি কোডের সমস্ত ব্লকও k শব্দে ভাগ করা হবে।

প্রতিটি রিডানডেন্সি ব্লকের i-th শব্দ গণনা করতে, সমস্ত ডেটা ব্লকের i-th শব্দ ব্যবহার করা হবে। তারা নিম্নলিখিত সূত্র অনুযায়ী গণনা করা হবে:

এখানে মান হল x হল ডেটা ব্লকের শব্দ, p হল রিডানডেন্সি কোড ব্লকের শব্দ, সমস্ত আলফা, বিটা, গামা এবং ডেল্টা হল বিশেষভাবে নির্বাচিত সংখ্যা যা সকলের জন্য একই। এটা অবিলম্বে বলা উচিত যে এই সমস্ত মানগুলি সাধারণ সংখ্যা নয়, তবে গ্যালয়েস ক্ষেত্রের উপাদান; অপারেশন +, -, *, / আমাদের সবার কাছে পরিচিত অপারেশন নয়, তবে গ্যালোয়ের উপাদানগুলির উপর প্রবর্তিত বিশেষ অপারেশনগুলি ক্ষেত্র

কেন গ্যালো ক্ষেত্র প্রয়োজন?

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

1. উপরে উল্লিখিত হিসাবে, শব্দের আকার স্থির করা হয়েছে, আমাদের উদাহরণে 16 বিট। রিড-সলোমন কোডগুলির জন্য উপরের সূত্রগুলি এমন যে সাধারণ পূর্ণসংখ্যা ব্যবহার করার সময়, p গণনা করার ফলাফলটি বৈধ আকারের একটি শব্দ ব্যবহার করে উপস্থাপনযোগ্য নাও হতে পারে।
2. ডেটা পুনরুদ্ধার করার সময়, উপরের সূত্রগুলিকে সমীকরণের একটি সিস্টেম হিসাবে বিবেচনা করা হবে যা ডেটা পুনরুদ্ধার করার জন্য অবশ্যই সমাধান করতে হবে। সমাধান প্রক্রিয়া চলাকালীন, একে অপরের দ্বারা পূর্ণসংখ্যাকে ভাগ করার প্রয়োজন হতে পারে, ফলে একটি বাস্তব সংখ্যা যা কম্পিউটার মেমরিতে সঠিকভাবে উপস্থাপন করা যায় না।

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

এই জাতীয় "বিশেষ" সংখ্যাগুলি দীর্ঘকাল ধরে গণিত দ্বারা অধ্যয়ন করা হয়েছে; তাদের ক্ষেত্র বলা হয়। একটি ক্ষেত্র হল উপাদানগুলির একটি সেট যা তাদের জন্য সংজ্ঞায়িত যোগ, বিয়োগ, গুণ এবং ভাগের ক্রিয়াকলাপ সহ।

Galois* ক্ষেত্রগুলি হল এমন ক্ষেত্র যার জন্য প্রতিটি ক্রিয়াকলাপের একটি অনন্য ফলাফল রয়েছে (+, -, *, /) ক্ষেত্রের যেকোনো দুটি উপাদানের জন্য। 2: 2, 4, 8, 16, ইত্যাদির ঘাত এমন সংখ্যাগুলির জন্য গ্যালোইস ক্ষেত্রগুলি তৈরি করা যেতে পারে। উদাহরণস্বরূপ, 2-বিট শব্দের জন্য, এটি 16 উপাদান সমন্বিত একটি ক্ষেত্র, যার প্রতিটি জোড়ার জন্য আপনি যেকোনো অপারেশনের ফলাফল খুঁজে পেতে পারেন (+, -, *, /)। উপরের সমীকরণগুলি থেকে x, p, আলফা, বিটা, গামা, ডেল্টার মানগুলি গণনার জন্য গ্যালোস ক্ষেত্রের উপাদান হিসাবে বিবেচিত হবে।

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

* এটি একটি কঠোর সংজ্ঞা নয়, বরং একটি বর্ণনা।

কিভাবে ডেটা পুনরুদ্ধার করবেন

যখন কিছু n + m ব্লক অনুপস্থিত থাকে তখন পুনরুদ্ধারের প্রয়োজন হয়। এগুলি ডেটা ব্লক এবং রিডানডেন্সি কোড ব্লক উভয়ই হতে পারে। ডেটা ব্লক এবং/অথবা রিডানডেন্সি কোড ব্লকের অনুপস্থিতির মানে হবে যে সংশ্লিষ্ট x এবং/অথবা p ভেরিয়েবলগুলি উপরের সমীকরণে অজানা।

রিড-সলোমন কোডগুলির সমীকরণগুলিকে সমীকরণের একটি সিস্টেম হিসাবে দেখা যেতে পারে যেখানে সমস্ত আলফা, বিটা, গামা, ডেল্টা মানগুলি ধ্রুবক, উপলব্ধ ব্লকগুলির সাথে সম্পর্কিত সমস্ত x এবং p পরিচিত চলক, এবং অবশিষ্ট x এবং p অজানা

উদাহরণস্বরূপ, ডেটা ব্লক 1, 2, 3 এবং রিডানডেন্সি কোড ব্লক 2 অনুপলব্ধ হতে দিন, তারপর i-th গোষ্ঠীর শব্দগুলির জন্য নিম্নলিখিত সমীকরণগুলির সিস্টেম থাকবে (অজানাগুলি লাল রঙে চিহ্নিত করা হয়েছে):

আমাদের কাছে 4টি অজানা সমীকরণের একটি সিস্টেম রয়েছে, যার মানে আমরা এটি সমাধান করতে এবং ডেটা পুনরুদ্ধার করতে পারি!

সমীকরণের এই সিস্টেম থেকে রিড-সলোমন কোডগুলির জন্য ডেটা পুনরুদ্ধারের বিষয়ে অনেকগুলি উপসংহার অনুসরণ করা হয় (এন ডেটা ব্লক, এম রিডানডেন্সি কোড ব্লক):

• কোনো m ব্লক বা তার কম হারিয়ে গেলে ডেটা পুনরুদ্ধার করা যেতে পারে। যদি m+1 বা ততোধিক ব্লক হারিয়ে যায়, ডেটা পুনরুদ্ধার করা যাবে না: m + 1 অজানা দিয়ে m সমীকরণের একটি সিস্টেম সমাধান করা অসম্ভব।
• এমনকি একটি ডেটা ব্লক পুনরুদ্ধার করতে, আপনাকে অবশিষ্ট ব্লকগুলির যেকোনো n ব্যবহার করতে হবে এবং আপনি যেকোন রিডানডেন্সি কোড ব্যবহার করতে পারেন।

তোমার আর কি জানার আছে

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

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

নিবন্ধের শেষে এই গুরুত্বপূর্ণ বিষয়ে সাহিত্যের উল্লেখ রয়েছে।

n এবং m এর পছন্দ

অনুশীলনে n এবং m কীভাবে চয়ন করবেন? অনুশীলনে, ডেটা স্টোরেজ সিস্টেমে, রিডানডেন্সি কোডগুলি স্থান বাঁচাতে ব্যবহার করা হয়, তাই m সবসময় n-এর চেয়ে কম বেছে নেওয়া হয়। তাদের নির্দিষ্ট মানগুলি অনেকগুলি কারণের উপর নির্ভর করে, যার মধ্যে রয়েছে:

• ডেটা স্টোরেজ নির্ভরযোগ্যতা। বড় m, ডিস্কের ব্যর্থতার সংখ্যা তত বেশি যা বেঁচে থাকতে পারে, অর্থাৎ, নির্ভরযোগ্যতা তত বেশি।
• অপ্রয়োজনীয় স্টোরেজ। m/n অনুপাত যত বেশি হবে, স্টোরেজ রিডানডেন্সি তত বেশি হবে এবং সিস্টেমটি তত বেশি ব্যয়বহুল হবে।
• প্রক্রিয়াকরণ সময় অনুরোধ. n + m যোগফল যত বড় হবে, অনুরোধের প্রতিক্রিয়ার সময় তত বেশি হবে। যেহেতু ডেটা পড়ার জন্য (পুনরুদ্ধারের সময়) বিভিন্ন ডিস্কে সংরক্ষিত n ব্লকগুলি পড়ার প্রয়োজন, তাই পড়ার সময়টি সবচেয়ে ধীরগতির ডিস্ক দ্বারা নির্ধারিত হবে।

এছাড়াও, বেশ কয়েকটি DC-তে ডেটা সংরক্ষণ করা n এবং m-এর পছন্দের উপর অতিরিক্ত বিধিনিষেধ আরোপ করে: যদি 1 DC বন্ধ থাকে, তবে ডেটা পড়ার জন্য এখনও উপলব্ধ থাকতে হবে। উদাহরণস্বরূপ, 3 DC-তে ডেটা সংরক্ষণ করার সময়, নিম্নলিখিত শর্তগুলি অবশ্যই পূরণ করতে হবে: m >= n/2, অন্যথায় 1 DC বন্ধ থাকা অবস্থায় ডেটা পড়ার জন্য অনুপলব্ধ একটি পরিস্থিতি হতে পারে।

3. LRC - স্থানীয় পুনর্গঠন কোড

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

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

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

LRC তিনটি সংখ্যা দ্বারা চিহ্নিত করা হয়: nrl, যেখানে n হল ডেটা ব্লকের সংখ্যা, r হল বিশ্বব্যাপী রিডানডেন্সি কোড ব্লকের সংখ্যা, l হল স্থানীয় রিডানডেন্সি কোড ব্লকের সংখ্যা। যখন একটি ডেটা ব্লক অনুপলব্ধ থাকে তখন ডেটা পড়ার জন্য, আপনাকে শুধুমাত্র n/l ব্লক পড়তে হবে - এটি রিড-সলোমন কোডের তুলনায় XNUMX গুণ কম।

উদাহরণস্বরূপ, LRC 6-2-2 প্রকল্পটি বিবেচনা করুন। X1–X6 — 6টি ডেটা ব্লক, P1, P2 — 2টি গ্লোবাল রিডানডেন্সি ব্লক, P3, P4 — 2টি স্থানীয় রিডানডেন্সি ব্লক৷

রিডানডেন্সি কোড ব্লক P1, P2 সব ডেটা ব্লক ব্যবহার করে গণনা করা হয়। রিডানডেন্সি কোড ব্লক P3 - ডেটা ব্লক X1-X3 ব্যবহার করে, রিডানডেন্সি কোড ব্লক P4 - ডেটা ব্লক X4-X6 ব্যবহার করে।

বাকিটা রিড-সলোমন কোডের সাদৃশ্য দ্বারা LRC-তে করা হয়। রিডানডেন্সি কোড ব্লকের শব্দ গণনার সমীকরণ হবে:

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

LRC-এর জন্য সমীকরণের সিস্টেম থেকে বেশ কয়েকটি উপসংহার অনুসরণ করে:

• যেকোনো 1 ডেটা ব্লক পুনরুদ্ধার করতে, n/l ব্লক পড়া যথেষ্ট (আমাদের উদাহরণে n/2)।
• যদি r + l ব্লক অনুপলব্ধ হয়, এবং সমস্ত ব্লক একটি গ্রুপে অন্তর্ভুক্ত করা হয়, তাহলে ডেটা পুনরুদ্ধার করা যাবে না। এটি একটি উদাহরণ দিয়ে ব্যাখ্যা করা সহজ। ব্লক X1–X3 এবং P3 অনুপলব্ধ হতে দিন: এই একই গ্রুপ থেকে r + l ব্লক, আমাদের ক্ষেত্রে 4. তারপরে আমাদের কাছে 3টি অজানা সহ 4টি সমীকরণের একটি সিস্টেম রয়েছে যা সমাধান করা যায় না।
• r + l ব্লকের অনুপলব্ধতার অন্যান্য সমস্ত ক্ষেত্রে (যখন প্রতিটি গ্রুপ থেকে কমপক্ষে একটি ব্লক পাওয়া যায়), LRC-তে ডেটা পুনরুদ্ধার করা যেতে পারে।

এইভাবে, LRC একক ত্রুটির পরে ডেটা পুনরুদ্ধারের ক্ষেত্রে রিড-সলোমন কোডগুলিকে ছাড়িয়ে যায়৷ রিড-সলোমন কোডগুলিতে, এমনকি এক ব্লক ডেটা পুনরুদ্ধার করতে, আপনাকে n ব্লক ব্যবহার করতে হবে এবং LRC-তে, ডেটার এক ব্লক পুনরুদ্ধার করতে, n/l ব্লক ব্যবহার করা যথেষ্ট (আমাদের উদাহরণে n/2)। অন্যদিকে, LRC সর্বাধিক সংখ্যক অনুমোদিত ত্রুটির পরিপ্রেক্ষিতে রিড-সলোমন কোডের চেয়ে নিকৃষ্ট। উপরের উদাহরণগুলিতে, রিড-সলোমন কোডগুলি যে কোনও 4টি ত্রুটির জন্য ডেটা পুনরুদ্ধার করতে পারে এবং LRC-এর জন্য 2টি ত্রুটির 4টি সমন্বয় রয়েছে যখন ডেটা পুনরুদ্ধার করা যায় না।

যেটি আরও গুরুত্বপূর্ণ তা নির্দিষ্ট পরিস্থিতির উপর নির্ভর করে, তবে প্রায়শই অতিরিক্ত লোডের সঞ্চয় যা LRC প্রদান করে তা কিছুটা কম নির্ভরযোগ্য স্টোরেজের চেয়ে বেশি।

4. অন্যান্য রিডানডেন্সি কোড

রিড-সলোমন এবং এলআরসি কোড ছাড়াও, আরও অনেক রিডানডেন্সি কোড রয়েছে। বিভিন্ন রিডানডেন্সি কোড বিভিন্ন গণিত ব্যবহার করে। এখানে কিছু অন্যান্য রিডানডেন্সি কোড আছে:

• XOR অপারেটর ব্যবহার করে রিডানডেন্সি কোড। XOR অপারেশনটি n ডেটা ব্লকে সঞ্চালিত হয় এবং রিডানডেন্সি কোডের 1 ব্লক পাওয়া যায়, অর্থাৎ একটি n+1 স্কিম (n ডেটা ব্লক, 1 রিডানডেন্সি কোড)। ব্যবহার করা হয় RAID 5, যেখানে ডেটা এবং রিডানডেন্সি কোডের ব্লকগুলি অ্যারের সমস্ত ডিস্কে চক্রাকারে লেখা হয়।
• XOR অপারেশনের উপর ভিত্তি করে জোড়-বিজোড় অ্যালগরিদম। আপনাকে রিডানডেন্সি কোডের ২টি ব্লক তৈরি করতে দেয়, অর্থাৎ n+2 স্কিম।
• XOR অপারেশনের উপর ভিত্তি করে স্টার অ্যালগরিদম। আপনাকে রিডানডেন্সি কোডের ৩টি ব্লক তৈরি করতে দেয়, অর্থাৎ n+3 স্কিম।
• পিরামাইড কোডগুলি মাইক্রোসফ্টের আরেকটি রিডানডেন্সি কোড।

5. ইয়ানডেক্সে ব্যবহার করুন

ইয়ানডেক্স অবকাঠামো প্রকল্পের একটি সংখ্যা নির্ভরযোগ্য ডেটা স্টোরেজের জন্য রিডানডেন্সি কোড ব্যবহার করে। এখানে কিছু উদাহরণঃ:

• এমডিএস অভ্যন্তরীণ অবজেক্ট স্টোরেজ, যা আমি নিবন্ধের শুরুতে লিখেছিলাম।
• YT — Yandex এর MapReduce সিস্টেম।
• YDB (ইয়ানডেক্স ডেটাবেস) - নতুন এসকিউএল বিতরণ করা ডাটাবেস।

MDS LRC রিডানডেন্সি কোড, 8-2-2 স্কিম ব্যবহার করে। রিডানডেন্সি কোড সহ ডেটা 12টি ভিন্ন ডিসিতে বিভিন্ন সার্ভারে 3টি ভিন্ন ডিস্কে লেখা হয়: প্রতিটি ডিসিতে 4টি সার্ভার। এই সম্পর্কে আরও পড়ুন প্রবন্ধ.

YT উভয় রিড-সলোমন কোড (স্কিম 6-3) ব্যবহার করে, যেটি প্রথম প্রয়োগ করা হয়েছিল এবং LRC রিডানডেন্সি কোড (স্কিম 12-2-2), যেখানে LRC হল পছন্দের স্টোরেজ পদ্ধতি।

YDB জোড়-বিজোড় ভিত্তিক রিডানডেন্সি কোড ব্যবহার করে (চিত্র 4-2)। ইতিমধ্যেই YDB-তে রিডানডেন্সি কোড সম্পর্কে হাইলোডে বলা হয়েছে.

বিভিন্ন রিডানডেন্সি কোড স্কিমগুলির ব্যবহার সিস্টেমের জন্য বিভিন্ন প্রয়োজনীয়তার কারণে। উদাহরণস্বরূপ, এমডিএস-এ, এলআরসি ব্যবহার করে সংরক্ষিত ডেটা একবারে 3টি ডিসিতে স্থাপন করা হয়। আমাদের জন্য এটা গুরুত্বপূর্ণ যে কোনো DC এর মধ্যে 1টি ব্যর্থ হলে ডেটা পড়ার জন্য উপলভ্য থাকে, তাই ব্লকগুলিকে অবশ্যই ডিসি জুড়ে বিতরণ করতে হবে যাতে কোনও DC অনুপলব্ধ হলে, অ্যাক্সেসযোগ্য ব্লকের সংখ্যা অনুমোদিত না হয়। 8-2-2 স্কিমে, আপনি প্রতিটি ডিসিতে 4 টি ব্লক রাখতে পারেন, তারপর যখন যে কোনও ডিসি বন্ধ করা হয়, 4 টি ব্লক অনুপলব্ধ হবে এবং ডেটা পড়া যাবে। এটিকে 3 ডিসি-তে রাখার সময় আমরা যে স্কিমটি বেছে নিই না কেন, যে কোনও ক্ষেত্রে (r + l) / n >= 0,5 হওয়া উচিত, অর্থাৎ স্টোরেজ রিডানডেন্সি কমপক্ষে 50% হবে।

YT-তে পরিস্থিতি আলাদা: প্রতিটি YT ক্লাস্টার সম্পূর্ণরূপে 1 DC-তে অবস্থিত (বিভিন্ন DC-তে বিভিন্ন ক্লাস্টার), তাই এই ধরনের কোনও সীমাবদ্ধতা নেই। 12-2-2 স্কিমটি 33% রিডানডেন্সি প্রদান করে, অর্থাৎ ডেটা স্টোর করা সস্তা, এবং এটি এমডিএস স্কিমের মতো একই সাথে 4টি ডিস্ক বিভ্রাট পর্যন্তও বেঁচে থাকতে পারে।

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

6. লিঙ্ক

1. রিড-সলোমন কোড এবং গ্যালোইস ক্ষেত্র সম্পর্কে নিবন্ধগুলির একটি সিরিজ: https://habr.com/ru/company/yadro/blog/336286/
   https://habr.com/ru/company/yadro/blog/341506/
   তারা সহজলভ্য ভাষায় গণিতকে গভীরভাবে দেখে।
2. LRC সম্পর্কে মাইক্রোসফ্ট থেকে নিবন্ধ: https://www.microsoft.com/en-us/research/wp-content/uploads/2016/02/LRC12-cheng20webpage.pdf
   অধ্যায় 2 সংক্ষিপ্তভাবে তত্ত্বটি ব্যাখ্যা করে এবং তারপর অনুশীলনে LRC এর সাথে অভিজ্ঞতা নিয়ে আলোচনা করে।
3. জোড়-বিজোড় স্কিম: https://people.eecs.berkeley.edu/~kubitron/courses/cs262a-F12/handouts/papers/p245-blaum.pdf
4. স্টার স্কিম: https://www.usenix.org/legacy/event/fast05/tech/full_papers/huang/huang.pdf
5. পিরামিড কোড: https://www.microsoft.com/en-us/research/publication/pyramid-codes-flexible-schemes-to-trade-space-for-access-efficiency-in-reliable-data-storage-systems/
6. MDS-এ রিডানডেন্সি কোড: https://habr.com/ru/company/yandex/blog/311806
7. YT-তে রিডানডেন্সি কোড: https://habr.com/ru/company/yandex/blog/311104/
8. YDB-তে রিডানডেন্সি কোড: https://www.youtube.com/watch?v=dCpfGJ35kK8

উত্স: www.habr.com