பணிநீக்கம் இப்படித்தான் தெரிகிறது

தரவு சேமிப்பகத்தின் நம்பகத்தன்மையை அதிகரிக்க கணினி அமைப்புகளில் பணிநீக்கம் குறியீடுகள்* பரவலாகப் பயன்படுத்தப்படுகின்றன. Yandex இல் அவை பல திட்டங்களில் பயன்படுத்தப்படுகின்றன. எடுத்துக்காட்டாக, எங்கள் அகப்பொருள் சேமிப்பகத்தில் நகலெடுப்பதற்குப் பதிலாக பணிநீக்கக் குறியீடுகளைப் பயன்படுத்துவது நம்பகத்தன்மையை இழக்காமல் மில்லியன் கணக்கானவற்றைச் சேமிக்கிறது. ஆனால் அவற்றின் பரவலான பயன்பாடு இருந்தபோதிலும், பணிநீக்கக் குறியீடுகள் எவ்வாறு செயல்படுகின்றன என்பதற்கான தெளிவான விளக்கங்கள் மிகவும் அரிதானவை. புரிந்து கொள்ள விரும்புவோர் தோராயமாக பின்வருவனவற்றை எதிர்கொள்கின்றனர் (இருந்து விக்கிப்பீடியா):

எனது பெயர் வாடிம், யாண்டெக்ஸில் நான் உள் பொருள் சேமிப்பக MDS ஐ உருவாக்குகிறேன். இந்தக் கட்டுரையில், பணிநீக்கக் குறியீடுகளின் (ரீட்-சாலமன் மற்றும் எல்ஆர்சி குறியீடுகள்) கோட்பாட்டு அடிப்படைகளை எளிய வார்த்தைகளில் விவரிக்கிறேன். சிக்கலான கணிதம் மற்றும் அரிதான சொற்கள் இல்லாமல் இது எவ்வாறு செயல்படுகிறது என்பதை நான் உங்களுக்கு சொல்கிறேன். முடிவில், Yandex இல் பணிநீக்கக் குறியீடுகளைப் பயன்படுத்துவதற்கான எடுத்துக்காட்டுகளைத் தருகிறேன்.

நான் பல கணித விவரங்களை விரிவாகக் கருத்தில் கொள்ள மாட்டேன், ஆனால் ஆழமாக டைவ் செய்ய விரும்புவோருக்கு இணைப்புகளை வழங்குவேன். கட்டுரை கணிதவியலாளர்களுக்கானது அல்ல, ஆனால் சிக்கலின் சாராம்சத்தைப் புரிந்துகொள்ள விரும்பும் பொறியாளர்களுக்கானது என்பதால், சில கணித வரையறைகள் கண்டிப்பாக இருக்காது என்பதையும் நான் கவனிக்கிறேன்.

* ஆங்கில மொழி இலக்கியத்தில், பணிநீக்கக் குறியீடுகள் பெரும்பாலும் அழித்தல் குறியீடுகள் என்று அழைக்கப்படுகின்றன.

1. பணிநீக்கக் குறியீடுகளின் சாராம்சம்

அனைத்து பணிநீக்கக் குறியீடுகளின் சாராம்சம் மிகவும் எளிமையானது: பிழைகள் ஏற்படும் போது (வட்டு தோல்விகள், தரவு பரிமாற்ற பிழைகள் போன்றவை) தொலைந்து போகாதவாறு தரவைச் சேமிக்கவும் (அல்லது அனுப்பவும்).

பெரும்பாலான* பணிநீக்கக் குறியீடுகளில், தரவு n தரவுத் தொகுதிகளாகப் பிரிக்கப்பட்டுள்ளது, அதற்காக m தொகுதிகள் பணிநீக்கக் குறியீடுகள் கணக்கிடப்படுகின்றன, இதன் விளைவாக மொத்தம் n + m தொகுதிகள் கிடைக்கும். பணிநீக்கம் குறியீடுகள் n + m தொகுதிகளின் ஒரு பகுதியை மட்டுமே பயன்படுத்தி தரவுகளின் n தொகுதிகளை மீட்டெடுக்கும் வகையில் உருவாக்கப்படுகின்றன. அடுத்து, தொகுதி பணிநீக்கக் குறியீடுகளை மட்டுமே கருத்தில் கொள்வோம், அதாவது தரவு தொகுதிகளாகப் பிரிக்கப்பட்டவை.

அனைத்து n பிளாக் தரவுகளையும் மீட்டெடுக்க, உங்களிடம் குறைந்தபட்சம் n + m தொகுதிகள் இருக்க வேண்டும், ஏனெனில் n-1 தொகுதியை மட்டும் வைத்து n தொகுதிகளைப் பெற முடியாது (இந்த விஷயத்தில், நீங்கள் 1 தொகுதியை “மெல்லியதில் இருந்து எடுக்க வேண்டும். காற்று"). எல்லா தரவையும் மீட்டெடுக்க n + m தொகுதிகளின் n சீரற்ற தொகுதிகள் போதுமானதா? இது பணிநீக்கக் குறியீடுகளின் வகையைச் சார்ந்தது, உதாரணமாக, Reed-Solomon குறியீடுகள் தன்னிச்சையான n தொகுதிகளைப் பயன்படுத்தி எல்லா தரவையும் மீட்டெடுக்க உங்களை அனுமதிக்கின்றன, ஆனால் LRC பணிநீக்கக் குறியீடுகள் எப்போதும் இல்லை.

தரவு சேமிப்பு

தரவு சேமிப்பக அமைப்புகளில், ஒரு விதியாக, தரவுத் தொகுதிகள் மற்றும் பணிநீக்கம் குறியீடு தொகுதிகள் ஒவ்வொன்றும் தனி வட்டில் எழுதப்படுகின்றன. பின்னர், ஒரு தன்னிச்சையான வட்டு தோல்வியுற்றால், அசல் தரவை மீட்டெடுக்கலாம் மற்றும் படிக்கலாம். ஒரே நேரத்தில் பல வட்டுகள் செயலிழந்தாலும் தரவை மீட்டெடுக்க முடியும்.

தரவு பரிமாற்றம்

நம்பகத்தன்மையற்ற நெட்வொர்க்கில் தரவை நம்பகத்தன்மையுடன் அனுப்ப, பணிநீக்கக் குறியீடுகள் பயன்படுத்தப்படலாம். அனுப்பப்பட்ட தரவு தொகுதிகளாக பிரிக்கப்பட்டுள்ளது, மேலும் பணிநீக்க குறியீடுகள் அவற்றிற்கு கணக்கிடப்படுகின்றன. தரவுத் தொகுதிகள் மற்றும் பணிநீக்கக் குறியீடு தொகுதிகள் ஆகிய இரண்டும் பிணையத்தில் அனுப்பப்படுகின்றன. தன்னிச்சையான தொகுதிகளில் பிழைகள் ஏற்பட்டால் (குறிப்பிட்ட எண்ணிக்கையிலான தொகுதிகள் வரை), தரவு பிழையின்றி பிணையத்தில் அனுப்பப்படும். உதாரணமாக, ரீட்-சாலமன் குறியீடுகள் ஆப்டிகல் கம்யூனிகேஷன் லைன்கள் மற்றும் செயற்கைக்கோள் தகவல்தொடர்புகளில் தரவை அனுப்ப பயன்படுகிறது.

* ஈத்தர்நெட் நெட்வொர்க்குகளில் தரவு பரிமாற்றத்திற்கு பரவலாகப் பயன்படுத்தப்படும் ஹேமிங் குறியீடுகள் மற்றும் CRC குறியீடுகள் போன்ற தொகுதிகளாக தரவு பிரிக்கப்படாத பணிநீக்கக் குறியீடுகளும் உள்ளன. இவை பிழை-திருத்தும் குறியீட்டிற்கான குறியீடுகள், அவை பிழைகளைக் கண்டறிய வடிவமைக்கப்பட்டுள்ளன, அவற்றைச் சரிசெய்வதற்காக அல்ல (ஹேமிங் குறியீடு பிழைகளை ஓரளவு திருத்த அனுமதிக்கிறது).

2. ரீட்-சாலமன் குறியீடுகள்

ரீட்-சாலமன் குறியீடுகள் மிகவும் பரவலாகப் பயன்படுத்தப்படும் பணிநீக்கக் குறியீடுகளில் ஒன்றாகும், இது 1960 களில் கண்டுபிடிக்கப்பட்டது மற்றும் 1980 களில் காம்பாக்ட் டிஸ்க்குகளின் வெகுஜன உற்பத்திக்காக முதன்முதலில் பரவலாகப் பயன்படுத்தப்பட்டது.

Reed-Solomon குறியீடுகளைப் புரிந்துகொள்வதற்கு இரண்டு முக்கிய கேள்விகள் உள்ளன: 1) பணிநீக்கக் குறியீடுகளின் தொகுதிகளை எவ்வாறு உருவாக்குவது; 2) பணிநீக்க குறியீடு தொகுதிகளைப் பயன்படுத்தி தரவை எவ்வாறு மீட்டெடுப்பது. அவற்றுக்கு விடை தேடுவோம்.
எளிமைக்காக, மேலும் n=6 மற்றும் m=4 என்று வைத்துக்கொள்வோம். மற்ற திட்டங்கள் ஒப்புமை மூலம் கருதப்படுகின்றன.

பணிநீக்க குறியீடு தொகுதிகளை எவ்வாறு உருவாக்குவது

பணிநீக்கக் குறியீடுகளின் ஒவ்வொரு தொகுதியும் மற்றவற்றிலிருந்து சுயாதீனமாக கணக்கிடப்படுகிறது. ஒவ்வொரு தொகுதியையும் கணக்கிட அனைத்து n தரவுத் தொகுதிகளும் பயன்படுத்தப்படுகின்றன. கீழேயுள்ள வரைபடத்தில், X1-X6 தரவுத் தொகுதிகள், P1-P4 என்பது பணிநீக்கக் குறியீடு தொகுதிகள்.

எல்லா தரவுத் தொகுதிகளும் ஒரே அளவில் இருக்க வேண்டும், மேலும் சீரமைக்க பூஜ்ஜிய பிட்களைப் பயன்படுத்தலாம். இதன் விளைவாக வரும் பணிநீக்கக் குறியீடு தொகுதிகள் தரவுத் தொகுதிகளின் அளவிலேயே இருக்கும். அனைத்து தரவுத் தொகுதிகளும் சொற்களாகப் பிரிக்கப்பட்டுள்ளன (எடுத்துக்காட்டாக, 16 பிட்கள்). டேட்டா பிளாக்குகளை கே வார்த்தைகளாகப் பிரிக்கிறோம் என்று வைத்துக் கொள்வோம். பின்னர் அனைத்து பணிநீக்கக் குறியீடுகளும் k சொற்களாகப் பிரிக்கப்படும்.

ஒவ்வொரு பணிநீக்கம் தொகுதியின் i-வது வார்த்தையை எண்ண, எல்லா தரவுத் தொகுதிகளின் i-வது வார்த்தைகளும் பயன்படுத்தப்படும். அவை பின்வரும் சூத்திரத்தின்படி கணக்கிடப்படும்:

இங்கே மதிப்புகள் x என்பது தரவுத் தொகுதிகளின் சொற்கள், p என்பது பணிநீக்கக் குறியீடு தொகுதிகளின் சொற்கள், அனைத்து ஆல்பா, பீட்டா, காமா மற்றும் டெல்டா ஆகியவை சிறப்பாகத் தேர்ந்தெடுக்கப்பட்ட எண்கள், அவை அனைத்திற்கும் ஒரே மாதிரியாக இருக்கும். இந்த மதிப்புகள் அனைத்தும் சாதாரண எண்கள் அல்ல, ஆனால் கலோயிஸ் புலத்தின் கூறுகள் என்று இப்போதே சொல்ல வேண்டும்; செயல்பாடுகள் +, -, *, / என்பது நம் அனைவருக்கும் தெரிந்த செயல்பாடுகள் அல்ல, ஆனால் கலோயிஸின் கூறுகளில் அறிமுகப்படுத்தப்பட்ட சிறப்பு செயல்பாடுகள் களம்.

கலோயிஸ் புலங்கள் ஏன் தேவைப்படுகின்றன?

எல்லாம் எளிமையானது என்று தோன்றுகிறது: நாங்கள் தரவை தொகுதிகளாகவும், தொகுதிகளை சொற்களாகவும் பிரிக்கிறோம், தரவுத் தொகுதிகளின் சொற்களைப் பயன்படுத்தி பணிநீக்க குறியீடு தொகுதிகளின் சொற்களை எண்ணுகிறோம் - பணிநீக்க குறியீடு தொகுதிகளைப் பெறுகிறோம். பொதுவாக இது எவ்வாறு செயல்படுகிறது, ஆனால் பிசாசு விவரங்களில் உள்ளது:

1. மேலே குறிப்பிட்டுள்ளபடி, வார்த்தை அளவு நிலையானது, எங்கள் எடுத்துக்காட்டில் 16 பிட்கள். ரீட்-சாலமன் குறியீடுகளுக்கு மேலே உள்ள சூத்திரங்கள், சாதாரண முழு எண்களைப் பயன்படுத்தும் போது, ​​p கணக்கீட்டின் முடிவு சரியான அளவிலான வார்த்தையைப் பயன்படுத்தி குறிப்பிடப்படாமல் இருக்கலாம்.
2. தரவை மீட்டெடுக்கும்போது, ​​மேலே உள்ள சூத்திரங்கள், தரவை மீட்டெடுப்பதற்குத் தீர்க்கப்பட வேண்டிய சமன்பாடுகளின் அமைப்பாகக் கருதப்படும். தீர்வு செயல்பாட்டின் போது, ​​முழு எண்களை ஒன்றோடொன்று பிரிப்பது அவசியமாக இருக்கலாம், இதன் விளைவாக கணினி நினைவகத்தில் துல்லியமாக குறிப்பிட முடியாத ஒரு உண்மையான எண்.

இந்தச் சிக்கல்கள் Reed-Solomon குறியீடுகளுக்கு முழு எண்களைப் பயன்படுத்துவதைத் தடுக்கின்றன. சிக்கலுக்கான தீர்வு அசல், அதை பின்வருமாறு விவரிக்கலாம்: தேவையான நீளத்தின் சொற்களைப் பயன்படுத்தி குறிப்பிடக்கூடிய சிறப்பு எண்களைக் கொண்டு வருவோம் (எடுத்துக்காட்டாக, 16 பிட்கள்), மற்றும் அனைத்து செயல்பாடுகளையும் செய்ததன் விளைவாக (கூடுதல் , கழித்தல், பெருக்கல், வகுத்தல்) தேவையான நீளத்தின் சொற்களைப் பயன்படுத்தி கணினி நினைவகத்தில் வழங்கப்படும்.

இத்தகைய "சிறப்பு" எண்கள் நீண்ட காலமாக கணிதத்தால் ஆய்வு செய்யப்படுகின்றன; அவை புலங்கள் என்று அழைக்கப்படுகின்றன. புலம் என்பது கூட்டல், கழித்தல், பெருக்கல் மற்றும் வகுத்தல் ஆகிய செயல்பாடுகளைக் கொண்ட தனிமங்களின் தொகுப்பாகும்.

Galois* புலங்கள் என்பது புலத்தின் எந்த இரண்டு உறுப்புகளுக்கும் ஒவ்வொரு செயல்பாட்டின் (+, -, *, /) தனித்துவமான முடிவு இருக்கும் புலங்கள். கலோயிஸ் புலங்கள் 2: 2, 4, 8, 16, முதலியவற்றின் சக்திகளாக இருக்கும் எண்களுக்குக் கட்டமைக்கப்படலாம் (உண்மையில் எந்த பகா எண்ணின் சக்திகளும் p, ஆனால் நடைமுறையில் நாம் 2 இன் சக்திகளில் மட்டுமே ஆர்வமாக உள்ளோம்). எடுத்துக்காட்டாக, 16-பிட் சொற்களுக்கு, இது 65 கூறுகளைக் கொண்ட ஒரு புலமாகும், இதில் ஒவ்வொரு ஜோடிக்கும் நீங்கள் எந்த செயல்பாட்டின் முடிவையும் காணலாம் (+, -, *, /). மேலே உள்ள சமன்பாடுகளிலிருந்து x, p, alpha, beta, gamma, delta ஆகியவற்றின் மதிப்புகள் கணக்கீடுகளுக்கு Galois புலத்தின் கூறுகளாகக் கருதப்படும்.

எனவே, பொருத்தமான கணினி நிரலை எழுதுவதன் மூலம் பணிநீக்கக் குறியீடுகளின் தொகுதிகளை உருவாக்கக்கூடிய சமன்பாடுகளின் அமைப்பு எங்களிடம் உள்ளது. சமன்பாடுகளின் அதே அமைப்பைப் பயன்படுத்தி, நீங்கள் தரவு மீட்டெடுப்பைச் செய்யலாம்.

* இது ஒரு கண்டிப்பான வரையறை அல்ல, மாறாக ஒரு விளக்கம்.

தரவை எவ்வாறு மீட்டெடுப்பது

சில n + m தொகுதிகள் இல்லாதபோது மீட்டமைத்தல் தேவைப்படுகிறது. இவை தரவுத் தொகுதிகள் மற்றும் பணிநீக்கம் குறியீடு தொகுதிகள் ஆகிய இரண்டும் இருக்கலாம். தரவுத் தொகுதிகள் மற்றும்/அல்லது பணிநீக்கக் குறியீடு தொகுதிகள் இல்லாததால், மேலே உள்ள சமன்பாடுகளில் தொடர்புடைய x மற்றும்/அல்லது p மாறிகள் தெரியவில்லை என்று அர்த்தம்.

ரீட்-சாலமன் குறியீடுகளுக்கான சமன்பாடுகள் அனைத்து ஆல்பா, பீட்டா, காமா, டெல்டா மதிப்புகள் மாறிலிகளாக இருக்கும் சமன்பாடுகளின் அமைப்பாகக் காணலாம், கிடைக்கக்கூடிய தொகுதிகளுடன் தொடர்புடைய அனைத்து x மற்றும் p ஆகியவை அறியப்பட்ட மாறிகள், மீதமுள்ள x மற்றும் p தெரியவில்லை.

எடுத்துக்காட்டாக, தரவுத் தொகுதிகள் 1, 2, 3 மற்றும் பணிநீக்கக் குறியீடு தொகுதி 2 ஆகியவை கிடைக்காமல் இருக்கட்டும், பின்னர் i-வது வார்த்தைகளின் குழுவிற்கு பின்வரும் சமன்பாடுகள் அமைப்பு இருக்கும் (தெரியாதவை சிவப்பு நிறத்தில் குறிக்கப்பட்டுள்ளன):

எங்களிடம் 4 அறியப்படாத 4 சமன்பாடுகளின் அமைப்பு உள்ளது, அதாவது அதைத் தீர்த்து தரவை மீட்டெடுக்க முடியும்!

இந்த சமன்பாடுகளின் அமைப்பிலிருந்து ரீட்-சாலமன் குறியீடுகளுக்கான தரவு மீட்டெடுப்பு பற்றி பல முடிவுகள் பின்பற்றப்படுகின்றன (n தரவுத் தொகுதிகள், m பணிநீக்கம் குறியீடு தொகுதிகள்):

• மீ தொகுதிகள் அல்லது அதற்கும் குறைவாக இருந்தால் தரவை மீட்டெடுக்கலாம். m+1 அல்லது அதற்கு மேற்பட்ட தொகுதிகள் தொலைந்துவிட்டால், தரவை மீட்டெடுக்க முடியாது: m + 1 தெரியாதவற்றுடன் m சமன்பாடுகளின் அமைப்பைத் தீர்க்க இயலாது.
• ஒரு தரவுத் தொகுதியை மீட்டெடுக்க, மீதமுள்ள தொகுதிகளில் ஏதேனும் n ஐப் பயன்படுத்த வேண்டும், மேலும் நீங்கள் பணிநீக்கக் குறியீடுகளில் ஏதேனும் ஒன்றைப் பயன்படுத்தலாம்.

உனக்கு வேறு என்ன தெரியும்

மேலே உள்ள விளக்கத்தில், கருத்தில் கொள்ள கணிதத்தில் ஆழமாக மூழ்க வேண்டிய பல முக்கியமான சிக்கல்களைத் தவிர்க்கிறேன். குறிப்பாக, பின்வருவனவற்றைப் பற்றி நான் எதுவும் கூறவில்லை:

• ரீட்-சாலமன் குறியீடுகளுக்கான சமன்பாடுகளின் அமைப்பானது, தெரியாதவற்றின் (m unknowns ஐ விட அதிகமாக இல்லை) எந்தவொரு கலவைக்கும் (தனித்துவமான) தீர்வைக் கொண்டிருக்க வேண்டும். இந்த தேவையின் அடிப்படையில், ஆல்பா, பீட்டா, காமா மற்றும் டெல்டா மதிப்புகள் தேர்ந்தெடுக்கப்படுகின்றன.
• சமன்பாடுகளின் அமைப்பு தானாகவே கட்டமைக்கப்பட வேண்டும் (எந்த தொகுதிகள் கிடைக்கவில்லை என்பதைப் பொறுத்து) மற்றும் தீர்க்கப்பட வேண்டும்.
• நாம் ஒரு கலோயிஸ் புலத்தை உருவாக்க வேண்டும்: கொடுக்கப்பட்ட சொல் அளவுக்கு, எந்த இரண்டு உறுப்புகளுக்கும் எந்த செயல்பாட்டின் முடிவையும் (+, -, *, /) கண்டறிய முடியும்.

கட்டுரையின் முடிவில் இந்த முக்கியமான பிரச்சினைகள் குறித்த இலக்கியங்கள் பற்றிய குறிப்புகள் உள்ளன.

n மற்றும் m தேர்வு

நடைமுறையில் n மற்றும் m ஐ எவ்வாறு தேர்வு செய்வது? நடைமுறையில், தரவு சேமிப்பக அமைப்புகளில், இடத்தைச் சேமிக்க பணிநீக்கம் குறியீடுகள் பயன்படுத்தப்படுகின்றன, எனவே m எப்போதும் n ஐ விட குறைவாகவே தேர்ந்தெடுக்கப்படுகிறது. அவற்றின் குறிப்பிட்ட மதிப்புகள் பல காரணிகளைப் பொறுத்தது:

• தரவு சேமிப்பகத்தின் நம்பகத்தன்மை. பெரிய மீ, அதிக எண்ணிக்கையிலான வட்டு தோல்விகள் உயிர்வாழ முடியும், அதாவது, அதிக நம்பகத்தன்மை.
• தேவையற்ற சேமிப்பு. m/n விகிதம் அதிகமாக இருந்தால், சேமிப்பக பணிநீக்கம் அதிகமாக இருக்கும், மேலும் கணினி அதிக விலை கொண்டதாக இருக்கும்.
• செயலாக்க நேரத்தைக் கோரவும். n + m எவ்வளவு அதிகமாக இருக்கிறதோ, அந்த அளவு கோரிக்கைகளுக்கான பதில் நேரம் அதிகமாக இருக்கும். தரவைப் படிக்க (மீட்பின் போது) n வெவ்வேறு வட்டுகளில் சேமிக்கப்பட்ட n தொகுதிகளைப் படிக்க வேண்டும் என்பதால், படிக்கும் நேரம் மெதுவான வட்டால் தீர்மானிக்கப்படும்.

கூடுதலாக, பல DC களில் தரவைச் சேமிப்பது n மற்றும் m இன் தேர்வுக்கு கூடுதல் கட்டுப்பாடுகளை விதிக்கிறது: 1 DC முடக்கப்பட்டிருந்தால், தரவு இன்னும் படிக்கக் கிடைக்க வேண்டும். எடுத்துக்காட்டாக, 3 DC களில் தரவைச் சேமிக்கும் போது, ​​பின்வரும் நிபந்தனையை பூர்த்தி செய்ய வேண்டும்: m >= n/2, இல்லையெனில் 1 DC அணைக்கப்படும் போது தரவு படிக்க முடியாத சூழ்நிலை ஏற்படலாம்.

3. LRC - உள்ளூர் மறுசீரமைப்பு குறியீடுகள்

Reed-Solomon குறியீடுகளைப் பயன்படுத்தி தரவை மீட்டெடுக்க, நீங்கள் n தன்னிச்சையான தரவுத் தொகுதிகளைப் பயன்படுத்த வேண்டும். விநியோகிக்கப்பட்ட தரவு சேமிப்பக அமைப்புகளுக்கு இது மிகவும் குறிப்பிடத்தக்க குறைபாடு ஆகும், ஏனெனில் ஒரு உடைந்த வட்டில் தரவை மீட்டமைக்க, நீங்கள் மற்றவற்றிலிருந்து தரவைப் படிக்க வேண்டும், வட்டுகள் மற்றும் பிணையத்தில் கூடுதல் சுமைகளை உருவாக்குகிறது.

ஒரு வட்டின் தோல்வி அல்லது அதிக சுமை காரணமாக ஒரு தொகுதி தரவு அணுக முடியாதது மிகவும் பொதுவான பிழைகள். இந்த (மிகவும் பொதுவான) வழக்கில் தரவு மீட்புக்கான அதிகப்படியான சுமையை எப்படியாவது குறைக்க முடியுமா? உங்களால் முடியும் என்று மாறிவிடும்: இந்த நோக்கத்திற்காக குறிப்பாக LRC பணிநீக்க குறியீடுகள் உள்ளன.

LRC (உள்ளூர் மறுசீரமைப்பு குறியீடுகள்) என்பது Windows Azure சேமிப்பகத்தில் பயன்படுத்த மைக்ரோசாப்ட் கண்டுபிடித்த பணிநீக்கக் குறியீடுகள். LRC இன் யோசனை முடிந்தவரை எளிமையானது: அனைத்து தரவுத் தொகுதிகளையும் இரண்டு (அல்லது அதற்கு மேற்பட்ட) குழுக்களாகப் பிரித்து, ஒவ்வொரு குழுவிற்கும் பணிநீக்கம் குறியீடு தொகுதிகளின் ஒரு பகுதியை தனித்தனியாகப் படிக்கவும். பின்னர் சில பணிநீக்கக் குறியீடு தொகுதிகள் அனைத்து தரவுத் தொகுதிகளைப் பயன்படுத்தி கணக்கிடப்படும் (எல்ஆர்சியில் அவை உலகளாவிய பணிநீக்கக் குறியீடுகள் என அழைக்கப்படுகின்றன), மேலும் சில - தரவுத் தொகுதிகளின் இரண்டு குழுக்களில் ஒன்றைப் பயன்படுத்தி (அவை உள்ளூர் பணிநீக்கக் குறியீடுகள் என அழைக்கப்படுகின்றன).

LRC மூன்று எண்களால் குறிக்கப்படுகிறது: nrl, இதில் n என்பது தரவுத் தொகுதிகளின் எண்ணிக்கை, r என்பது உலகளாவிய பணிநீக்கக் குறியீடு தொகுதிகளின் எண்ணிக்கை, l என்பது உள்ளூர் பணிநீக்கக் குறியீடு தொகுதிகளின் எண்ணிக்கை. ஒரு தரவுத் தொகுதி கிடைக்காதபோது தரவைப் படிக்க, நீங்கள் n/l தொகுதிகளை மட்டுமே படிக்க வேண்டும் - இது Reed-Solomon குறியீடுகளை விட l மடங்கு குறைவாகும்.

எடுத்துக்காட்டாக, 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 மிஞ்சுகிறது. Reed-Solomon குறியீடுகளில், ஒரு பிளாக் தரவை மீட்டெடுக்க, நீங்கள் n பிளாக்குகளைப் பயன்படுத்த வேண்டும், மேலும் LRC இல், ஒரு பிளாக் டேட்டாவை மீட்டெடுக்க, n/l தொகுதிகளைப் பயன்படுத்தினால் போதும் (எங்கள் எடுத்துக்காட்டில் n/2). மறுபுறம், அனுமதிக்கப்பட்ட அதிகபட்ச பிழைகளின் அடிப்படையில் ரீட்-சாலமன் குறியீடுகளை விட LRC குறைவாக உள்ளது. மேலே உள்ள எடுத்துக்காட்டுகளில், Reed-Solomon குறியீடுகள் எந்த 4 பிழைகளுக்கும் தரவை மீட்டெடுக்க முடியும், மேலும் LRC க்கு தரவை மீட்டெடுக்க முடியாதபோது 2 பிழைகளின் 4 சேர்க்கைகள் உள்ளன.

மிகவும் முக்கியமானது குறிப்பிட்ட சூழ்நிலையைப் பொறுத்தது, ஆனால் பெரும்பாலும் LRC வழங்கும் அதிகப்படியான சுமை சேமிப்பு சற்று குறைவான நம்பகமான சேமிப்பகத்தை விட அதிகமாகும்.

4. பிற பணிநீக்க குறியீடுகள்

Reed-Solomon மற்றும் LRC குறியீடுகள் தவிர, பல பணிநீக்க குறியீடுகள் உள்ளன. வெவ்வேறு பணிநீக்கக் குறியீடுகள் வெவ்வேறு கணிதத்தைப் பயன்படுத்துகின்றன. வேறு சில பணிநீக்கக் குறியீடுகள் இங்கே:

• XOR ஆபரேட்டரைப் பயன்படுத்தி பணிநீக்கம் குறியீடு. XOR செயல்பாடு n தரவுத் தொகுதிகளில் செய்யப்படுகிறது, மேலும் 1 தொகுதி பணிநீக்கக் குறியீடுகள் பெறப்படுகின்றன, அதாவது n+1 திட்டம் (n தரவுத் தொகுதிகள், 1 பணிநீக்கக் குறியீடு). இல் பயன்படுத்தப்பட்டது RAID 5, தரவுத் தொகுதிகள் மற்றும் பணிநீக்கம் குறியீடுகள் வரிசையின் அனைத்து வட்டுகளிலும் சுழற்சி முறையில் எழுதப்படும்.
• XOR செயல்பாட்டின் அடிப்படையில் இரட்டை-ஒற்றைப்படை அல்காரிதம். பணிநீக்கக் குறியீடுகளின் 2 தொகுதிகளை உருவாக்க உங்களை அனுமதிக்கிறது, அதாவது n+2 திட்டம்.
• XOR செயல்பாட்டின் அடிப்படையில் STAR அல்காரிதம். பணிநீக்கக் குறியீடுகளின் 3 தொகுதிகளை உருவாக்க உங்களை அனுமதிக்கிறது, அதாவது n+3 திட்டம்.
• பிரமிடு குறியீடுகள் மைக்ரோசாப்டின் மற்றொரு பணிநீக்க குறியீடுகள்.

5. Yandex இல் பயன்படுத்தவும்

பல Yandex உள்கட்டமைப்பு திட்டங்கள் நம்பகமான தரவு சேமிப்பிற்காக பணிநீக்க குறியீடுகளைப் பயன்படுத்துகின்றன. இங்கே சில உதாரணங்கள்:

• எம்.டி.எஸ் உள் பொருள் சேமிப்பு, கட்டுரையின் தொடக்கத்தில் நான் எழுதியது.
• YT - யாண்டெக்ஸின் வரைபடக் குறைப்பு அமைப்பு.
• YDB (Yandex DataBase) - newSQL விநியோகிக்கப்பட்ட தரவுத்தளம்.

MDS LRC பணிநீக்கக் குறியீடுகளைப் பயன்படுத்துகிறது, 8-2-2 திட்டம். பணிநீக்கக் குறியீடுகள் கொண்ட தரவு 12 வெவ்வேறு DCகளில் வெவ்வேறு சர்வர்களில் 3 வெவ்வேறு வட்டுகளுக்கு எழுதப்படுகிறது: ஒவ்வொரு DC யிலும் 4 சேவையகங்கள். இதைப் பற்றி மேலும் படிக்கவும் கட்டுரை.

YT ரீட்-சாலமன் குறியீடுகள் (திட்டம் 6-3) இரண்டையும் பயன்படுத்துகிறது, அவை முதலில் செயல்படுத்தப்பட்டன, மற்றும் LRC பணிநீக்கக் குறியீடுகள் (திட்டம் 12-2-2), LRC என்பது விருப்பமான சேமிப்பு முறையாகும்.

YDB இரட்டைப்படை அடிப்படையிலான பணிநீக்கக் குறியீடுகளைப் பயன்படுத்துகிறது (படம் 4-2). ஏற்கனவே YDB இல் உள்ள பணிநீக்கக் குறியீடுகள் பற்றி ஹைலோடில் சொல்லப்பட்டது.

வெவ்வேறு பணிநீக்கக் குறியீடு திட்டங்களின் பயன்பாடு அமைப்புகளுக்கான வெவ்வேறு தேவைகள் காரணமாகும். எடுத்துக்காட்டாக, MDS இல், LRC ஐப் பயன்படுத்தி சேமிக்கப்பட்ட தரவு ஒரே நேரத்தில் 3 DCகளில் வைக்கப்படும். ஏதேனும் ஒரு DC தோல்வியுற்றால், தரவு தொடர்ந்து படிக்கக் கிடைக்கும் என்பது எங்களுக்கு முக்கியம், எனவே தொகுதிகள் DCகள் முழுவதும் விநியோகிக்கப்பட வேண்டும், இதனால் ஏதேனும் DC கிடைக்கவில்லை என்றால், அணுக முடியாத தொகுதிகளின் எண்ணிக்கை அனுமதிக்கப்படுவதை விட அதிகமாக இருக்காது. 1-8-2 திட்டத்தில், ஒவ்வொரு டிசியிலும் 2 பிளாக்குகளை வைக்கலாம், பின்னர் எந்த டிசியும் ஆஃப் செய்யப்பட்டால், 4 தொகுதிகள் கிடைக்காது, மேலும் தரவைப் படிக்கலாம். 4 DC களில் வைக்கும் போது நாம் எந்தத் திட்டத்தைத் தேர்வு செய்தாலும், எந்தவொரு சந்தர்ப்பத்திலும் (r + l) / n >= 3 இருக்க வேண்டும், அதாவது சேமிப்பக பணிநீக்கம் குறைந்தது 0,5% ஆக இருக்கும்.

YT இல் நிலைமை வேறுபட்டது: ஒவ்வொரு YT கிளஸ்டரும் முற்றிலும் 1 DC இல் அமைந்துள்ளது (வெவ்வேறு DC களில் வெவ்வேறு கிளஸ்டர்கள்), எனவே அத்தகைய கட்டுப்பாடு எதுவும் இல்லை. 12-2-2 திட்டம் 33% பணிநீக்கத்தை வழங்குகிறது, அதாவது தரவைச் சேமிப்பது மலிவானது, மேலும் இது MDS திட்டத்தைப் போலவே ஒரே நேரத்தில் 4 வட்டு செயலிழப்புகள் வரை உயிர்வாழ முடியும்.

தரவு சேமிப்பு மற்றும் செயலாக்க அமைப்புகளில் பணிநீக்கக் குறியீடுகளைப் பயன்படுத்துவதில் இன்னும் பல அம்சங்கள் உள்ளன: தரவு மீட்டெடுப்பின் நுணுக்கங்கள், வினவல் செயல்படுத்தும் நேரத்தில் மீட்டெடுப்பின் தாக்கம், தரவுப் பதிவின் அம்சங்கள் போன்றவை. இவை மற்றும் பிற அம்சங்களைப் பற்றி நான் தனித்தனியாகப் பேசப் போகிறேன். நடைமுறையில் பணிநீக்கம் குறியீடுகளின் பயன்பாடு, தலைப்பு சுவாரஸ்யமாக இருந்தால்.

6. இணைப்புகள்

1. ரீட்-சாலமன் குறியீடுகள் மற்றும் கலோயிஸ் புலங்கள் பற்றிய தொடர் கட்டுரைகள்: https://habr.com/ru/company/yadro/blog/336286/
   https://habr.com/ru/company/yadro/blog/341506/
   அவர்கள் அணுகக்கூடிய மொழியில் கணிதத்தை ஆழமாகப் பார்க்கிறார்கள்.
2. எல்ஆர்சி பற்றிய மைக்ரோசாஃப்ட் கட்டுரை: 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