రిడెండెన్సీ ఇలా కనిపిస్తుంది

డేటా నిల్వ యొక్క విశ్వసనీయతను పెంచడానికి రిడెండెన్సీ కోడ్‌లు* కంప్యూటర్ సిస్టమ్‌లలో విస్తృతంగా ఉపయోగించబడతాయి. Yandex లో వారు అనేక ప్రాజెక్టులలో ఉపయోగిస్తారు. ఉదాహరణకు, మా అంతర్గత ఆబ్జెక్ట్ స్టోరేజ్‌లో రెప్లికేషన్‌కు బదులుగా రిడెండెన్సీ కోడ్‌లను ఉపయోగించడం వల్ల విశ్వసనీయతను కోల్పోకుండా మిలియన్ల కొద్దీ ఆదా అవుతుంది. కానీ వాటి విస్తృత ఉపయోగం ఉన్నప్పటికీ, రిడెండెన్సీ కోడ్‌లు ఎలా పనిచేస్తాయో స్పష్టమైన వివరణలు చాలా అరుదు. అర్థం చేసుకోవాలనుకునే వారు సుమారుగా క్రింది వాటిని ఎదుర్కొంటారు (నుండి వికీపీడియా):

నా పేరు వాడిమ్, Yandexలో నేను అంతర్గత వస్తువు నిల్వ MDSని అభివృద్ధి చేస్తున్నాను. ఈ వ్యాసంలో, రిడెండెన్సీ కోడ్‌ల (రీడ్-సోలమన్ మరియు LRC కోడ్‌లు) యొక్క సైద్ధాంతిక పునాదులను నేను సరళమైన పదాలలో వివరిస్తాను. సంక్లిష్టమైన గణితం మరియు అరుదైన పదాలు లేకుండా ఇది ఎలా పని చేస్తుందో నేను మీకు చెప్తాను. ముగింపులో నేను Yandex లో రిడెండెన్సీ కోడ్‌లను ఉపయోగించి ఉదాహరణలు ఇస్తాను.

నేను అనేక గణిత వివరాలను వివరంగా పరిగణించను, కానీ లోతుగా డైవ్ చేయాలనుకునే వారికి నేను లింక్‌లను అందిస్తాను. వ్యాసం గణిత శాస్త్రజ్ఞుల కోసం ఉద్దేశించినది కాదు, సమస్య యొక్క సారాంశాన్ని అర్థం చేసుకోవాలనుకునే ఇంజనీర్ల కోసం కొన్ని గణిత నిర్వచనాలు కఠినంగా ఉండకపోవచ్చని కూడా నేను గమనించాను.

* ఆంగ్ల భాషా సాహిత్యంలో, రిడెండెన్సీ కోడ్‌లను తరచుగా ఎరేజర్ కోడ్‌లు అంటారు.

1. రిడెండెన్సీ కోడ్‌ల సారాంశం

అన్ని రిడెండెన్సీ కోడ్‌ల సారాంశం చాలా సులభం: డేటాను నిల్వ చేయండి (లేదా ప్రసారం చేయండి) తద్వారా లోపాలు సంభవించినప్పుడు అది కోల్పోదు (డిస్క్ వైఫల్యాలు, డేటా బదిలీ లోపాలు మొదలైనవి).

చాలా * రిడెండెన్సీ కోడ్‌లలో, డేటా n డేటా బ్లాక్‌లుగా విభజించబడింది, దీని కోసం రిడెండెన్సీ కోడ్‌ల m బ్లాక్‌లు లెక్కించబడతాయి, ఫలితంగా మొత్తం n + m బ్లాక్‌లు ఉంటాయి. n + m బ్లాక్‌లలో కొంత భాగాన్ని మాత్రమే ఉపయోగించి n బ్లాక్‌ల డేటాను తిరిగి పొందగలిగే విధంగా రిడెండెన్సీ కోడ్‌లు రూపొందించబడ్డాయి. తరువాత, మేము బ్లాక్ రిడెండెన్సీ కోడ్‌లను మాత్రమే పరిశీలిస్తాము, అంటే డేటా బ్లాక్‌లుగా విభజించబడినవి.

అన్ని n బ్లాక్‌ల డేటాను పునరుద్ధరించడానికి, మీరు కనీసం n + m బ్లాక్‌లను కలిగి ఉండాలి, ఎందుకంటే మీరు n-1 బ్లాక్‌ను మాత్రమే కలిగి ఉండటం ద్వారా n బ్లాక్‌లను పొందలేరు (ఈ సందర్భంలో, మీరు 1 బ్లాక్‌ను “సన్నని నుండి తీసుకోవాలి. గాలి"). మొత్తం డేటాను రికవర్ చేయడానికి n + m బ్లాక్‌ల n యాదృచ్ఛిక బ్లాక్‌లు సరిపోతాయా? ఇది రిడెండెన్సీ కోడ్‌ల రకంపై ఆధారపడి ఉంటుంది, ఉదాహరణకు, రీడ్-సోలమన్ కోడ్‌లు ఏకపక్ష n బ్లాక్‌లను ఉపయోగించి మొత్తం డేటాను పునరుద్ధరించడానికి మిమ్మల్ని అనుమతిస్తాయి, అయితే LRC రిడెండెన్సీ కోడ్‌లు ఎల్లప్పుడూ ఉండవు.

డేటా నిల్వ

డేటా నిల్వ వ్యవస్థలలో, ఒక నియమం వలె, ప్రతి డేటా బ్లాక్‌లు మరియు రిడెండెన్సీ కోడ్ బ్లాక్‌లు ప్రత్యేక డిస్క్‌కు వ్రాయబడతాయి. అప్పుడు, ఏకపక్ష డిస్క్ విఫలమైతే, అసలు డేటా ఇప్పటికీ పునరుద్ధరించబడుతుంది మరియు చదవబడుతుంది. ఒకే సమయంలో అనేక డిస్క్‌లు విఫలమైనప్పటికీ డేటాను తిరిగి పొందవచ్చు.

డేటా బదిలీ

విశ్వసనీయత లేని నెట్‌వర్క్ ద్వారా డేటాను విశ్వసనీయంగా ప్రసారం చేయడానికి రిడెండెన్సీ కోడ్‌లను ఉపయోగించవచ్చు. ప్రసారం చేయబడిన డేటా బ్లాక్‌లుగా విభజించబడింది మరియు రిడెండెన్సీ కోడ్‌లు వాటి కోసం లెక్కించబడతాయి. డేటా బ్లాక్‌లు మరియు రిడెండెన్సీ కోడ్ బ్లాక్‌లు రెండూ నెట్‌వర్క్ ద్వారా ప్రసారం చేయబడతాయి. ఏకపక్ష బ్లాక్‌లలో లోపాలు సంభవించినట్లయితే (నిర్దిష్ట సంఖ్యలో బ్లాక్‌ల వరకు), డేటా ఇప్పటికీ లోపాలు లేకుండా నెట్‌వర్క్ ద్వారా ప్రసారం చేయబడుతుంది. రీడ్-సోలమన్ కోడ్‌లు, ఉదాహరణకు, ఆప్టికల్ కమ్యూనికేషన్ లైన్‌ల ద్వారా మరియు ఉపగ్రహ కమ్యూనికేషన్‌లలో డేటాను ప్రసారం చేయడానికి ఉపయోగించబడతాయి.

* డేటాను బ్లాక్‌లుగా విభజించని రిడెండెన్సీ కోడ్‌లు కూడా ఉన్నాయి, హామింగ్ కోడ్‌లు మరియు CRC కోడ్‌లు వంటివి ఈథర్‌నెట్ నెట్‌వర్క్‌లలో డేటా ట్రాన్స్‌మిషన్ కోసం విస్తృతంగా ఉపయోగించబడతాయి. ఇవి ఎర్రర్-కరెక్టింగ్ కోడింగ్ కోసం కోడ్‌లు, అవి లోపాలను గుర్తించడానికి రూపొందించబడ్డాయి మరియు వాటిని సరిదిద్దడానికి కాదు (హామింగ్ కోడ్ లోపాల యొక్క పాక్షిక దిద్దుబాటును కూడా అనుమతిస్తుంది).

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 బిట్‌లు) పదాలను ఉపయోగించి ప్రాతినిధ్యం వహించే ప్రత్యేక సంఖ్యలతో ముందుకు రండి మరియు దానిపై అన్ని కార్యకలాపాలను నిర్వహించడం వల్ల (అదనంగా , వ్యవకలనం, గుణకారం, భాగహారం) అవసరమైన పొడవు పదాలను ఉపయోగించి కంప్యూటర్ మెమరీలో కూడా ప్రదర్శించబడుతుంది.

ఇటువంటి "ప్రత్యేక" సంఖ్యలను గణితం చాలా కాలంగా అధ్యయనం చేసింది; వాటిని ఫీల్డ్‌లు అంటారు. ఫీల్డ్ అనేది వాటి కోసం నిర్వచించబడిన కూడిక, తీసివేత, గుణకారం మరియు భాగహారం యొక్క కార్యకలాపాలతో కూడిన మూలకాల సమితి.

గలోయిస్* ఫీల్డ్‌లు ఫీల్డ్‌లు, దీని కోసం ఫీల్డ్‌లోని ఏదైనా రెండు మూలకాల కోసం ప్రతి ఆపరేషన్ (+, -, *, /) ప్రత్యేక ఫలితం ఉంటుంది. గలోయిస్ ఫీల్డ్‌లు 2: 2, 4, 8, 16, మొదలైన శక్తులైన సంఖ్యల కోసం నిర్మించబడతాయి (వాస్తవానికి ఏదైనా ప్రధాన సంఖ్య p యొక్క శక్తులు, కానీ ఆచరణలో మనకు 2 శక్తులపై మాత్రమే ఆసక్తి ఉంటుంది). ఉదాహరణకు, 16-బిట్ పదాల కోసం, ఇది 65 మూలకాలను కలిగి ఉన్న ఫీల్డ్, వీటిలో ప్రతి జత కోసం మీరు ఏదైనా ఆపరేషన్ ఫలితాన్ని కనుగొనవచ్చు (+, -, *, /). పై సమీకరణాల నుండి x, p, ఆల్ఫా, బీటా, గామా, డెల్టా యొక్క విలువలు లెక్కల కోసం గాలోయిస్ ఫీల్డ్ యొక్క మూలకాలుగా పరిగణించబడతాయి.

ఈ విధంగా, మనకు తగిన కంప్యూటర్ ప్రోగ్రామ్‌ను వ్రాయడం ద్వారా రిడెండెన్సీ కోడ్‌ల బ్లాక్‌లను నిర్మించగల సమీకరణాల వ్యవస్థ ఉంది. అదే సమీకరణాల వ్యవస్థను ఉపయోగించి, మీరు డేటా రికవరీని చేయవచ్చు.

* ఇది ఖచ్చితమైన నిర్వచనం కాదు, వివరణ.

డేటాను ఎలా పునరుద్ధరించాలి

కొన్ని n + m బ్లాక్‌లు లేనప్పుడు పునరుద్ధరణ అవసరం. ఇవి డేటా బ్లాక్‌లు మరియు రిడెండెన్సీ కోడ్ బ్లాక్‌లు రెండూ కావచ్చు. డేటా బ్లాక్‌లు మరియు/లేదా రిడెండెన్సీ కోడ్ బ్లాక్‌లు లేకపోవడం అంటే సంబంధిత x మరియు/లేదా p వేరియబుల్స్ పై సమీకరణాలలో తెలియవని అర్థం.

రీడ్-సోలమన్ కోడ్‌ల సమీకరణాలను సమీకరణాల వ్యవస్థగా చూడవచ్చు, దీనిలో అన్ని ఆల్ఫా, బీటా, గామా, డెల్టా విలువలు స్థిరాంకాలు, అందుబాటులో ఉన్న బ్లాక్‌లకు సంబంధించిన అన్ని x మరియు p లు తెలిసిన వేరియబుల్స్ మరియు మిగిలిన x మరియు p. తెలియవు.

ఉదాహరణకు, డేటా బ్లాక్‌లు 1, 2, 3 మరియు రిడెండెన్సీ కోడ్ బ్లాక్ 2 అందుబాటులో ఉండనివ్వండి, ఐ-వ పదాల సమూహం కోసం క్రింది సమీకరణాల వ్యవస్థ ఉంటుంది (తెలియనివి ఎరుపు రంగులో గుర్తించబడతాయి):

మనకు 4 తెలియని వాటితో 4 సమీకరణాల వ్యవస్థ ఉంది, అంటే మనం దాన్ని పరిష్కరించవచ్చు మరియు డేటాను పునరుద్ధరించవచ్చు!

ఈ సమీకరణాల వ్యవస్థ నుండి రీడ్-సోలమన్ కోడ్‌ల (n డేటా బ్లాక్‌లు, m రిడెండెన్సీ కోడ్ బ్లాక్‌లు) కోసం డేటా రికవరీ గురించి అనేక ముగింపులు అనుసరించబడతాయి:

• ఏదైనా m బ్లాక్‌లు లేదా అంతకంటే తక్కువ పోయినట్లయితే డేటాను తిరిగి పొందవచ్చు. m+1 లేదా అంతకంటే ఎక్కువ బ్లాక్‌లు పోయినట్లయితే, డేటా పునరుద్ధరించబడదు: m + 1 తెలియని వాటితో m సమీకరణాల వ్యవస్థను పరిష్కరించడం అసాధ్యం.
• ఒక డేటా బ్లాక్‌ని కూడా పునరుద్ధరించడానికి, మీరు మిగిలిన బ్లాక్‌లలో ఏదైనా nని ఉపయోగించాలి మరియు మీరు రిడెండెన్సీ కోడ్‌లలో దేనినైనా ఉపయోగించవచ్చు.

ఇంకా ఏమి తెలుసుకోవాలి

పై వివరణలో, గణితాన్ని లోతుగా పరిగణలోకి తీసుకోవాల్సిన అనేక ముఖ్యమైన సమస్యలను నేను నివారించాను. ముఖ్యంగా, నేను ఈ క్రింది వాటి గురించి ఏమీ చెప్పడం లేదు:

• రీడ్-సోలమన్ కోడ్‌ల కోసం సమీకరణాల వ్యవస్థ తప్పనిసరిగా ఏదైనా తెలియని వాటి కలయిక కోసం (ప్రత్యేకమైన) పరిష్కారాన్ని కలిగి ఉండాలి (m తెలియని వాటి కంటే ఎక్కువ కాదు). ఈ అవసరం ఆధారంగా, ఆల్ఫా, బీటా, గామా మరియు డెల్టా విలువలు ఎంపిక చేయబడతాయి.
• సమీకరణాల వ్యవస్థ తప్పనిసరిగా స్వయంచాలకంగా నిర్మించబడాలి (ఏ బ్లాక్‌లు అందుబాటులో లేవు అనేదానిపై ఆధారపడి) మరియు పరిష్కరించబడతాయి.
• మేము గాలోయిస్ ఫీల్డ్‌ను రూపొందించాలి: ఇచ్చిన పద పరిమాణం కోసం, ఏదైనా రెండు మూలకాల కోసం ఏదైనా ఆపరేషన్ (+, -, *, /) ఫలితాన్ని కనుగొనగలగాలి.

వ్యాసం చివరిలో ఈ ముఖ్యమైన సమస్యలపై సాహిత్యానికి సంబంధించిన సూచనలు ఉన్నాయి.

n మరియు m ఎంపిక

ఆచరణలో n మరియు m లను ఎలా ఎంచుకోవాలి? ఆచరణలో, డేటా నిల్వ వ్యవస్థలలో, రిడెండెన్సీ కోడ్‌లు స్థలాన్ని ఆదా చేయడానికి ఉపయోగించబడతాయి, కాబట్టి m ఎల్లప్పుడూ n కంటే తక్కువగా ఎంపిక చేయబడుతుంది. వాటి నిర్దిష్ట విలువలు అనేక అంశాలపై ఆధారపడి ఉంటాయి, వీటిలో:

• డేటా నిల్వ యొక్క విశ్వసనీయత. పెద్ద m, మనుగడలో ఉన్న డిస్క్ వైఫల్యాల సంఖ్య ఎక్కువ, అంటే విశ్వసనీయత ఎక్కువ.
• అనవసరమైన నిల్వ. m/n నిష్పత్తి ఎక్కువగా ఉంటే, నిల్వ రిడెండెన్సీ ఎక్కువగా ఉంటుంది మరియు సిస్టమ్ మరింత ఖరీదైనదిగా ఉంటుంది.
• ప్రాసెసింగ్ సమయాన్ని అభ్యర్థించండి. మొత్తం n + m ఎంత పెద్దదైతే, అభ్యర్థనలకు ప్రతిస్పందన సమయం అంత ఎక్కువగా ఉంటుంది. డేటాను చదవడానికి (రికవరీ సమయంలో) n వేర్వేరు డిస్క్‌లలో నిల్వ చేయబడిన n బ్లాక్‌లను చదవడం అవసరం కాబట్టి, రీడ్ టైమ్ నెమ్మదైన డిస్క్ ద్వారా నిర్ణయించబడుతుంది.

అదనంగా, అనేక DCలలో డేటాను నిల్వ చేయడం n మరియు m ఎంపికపై అదనపు పరిమితులను విధిస్తుంది: 1 DC ఆఫ్ చేయబడితే, డేటా చదవడానికి ఇప్పటికీ అందుబాటులో ఉండాలి. ఉదాహరణకు, 3 DCలలో డేటాను నిల్వ చేస్తున్నప్పుడు, కింది షరతును తప్పక పాటించాలి: m >= n/2, లేకుంటే 1 DC ఆఫ్‌లో ఉన్నప్పుడు చదవడానికి డేటా అందుబాటులో లేని పరిస్థితి ఉండవచ్చు.

3. LRC - స్థానిక పునర్నిర్మాణ కోడ్‌లు

రీడ్-సోలమన్ కోడ్‌లను ఉపయోగించి డేటాను పునరుద్ధరించడానికి, మీరు n ఏకపక్ష డేటా బ్లాక్‌లను ఉపయోగించాలి. పంపిణీ చేయబడిన డేటా నిల్వ వ్యవస్థలకు ఇది చాలా ముఖ్యమైన ప్రతికూలత, ఎందుకంటే ఒక విరిగిన డిస్క్‌లో డేటాను పునరుద్ధరించడానికి, మీరు డిస్క్‌లు మరియు నెట్‌వర్క్‌పై పెద్ద అదనపు లోడ్‌ను సృష్టించి, ఇతరుల నుండి డేటాను చదవవలసి ఉంటుంది.

ఒక డిస్క్ యొక్క వైఫల్యం లేదా ఓవర్‌లోడ్ కారణంగా డేటా యొక్క ఒక బ్లాక్‌ని యాక్సెస్ చేయలేకపోవడం అత్యంత సాధారణ లోపాలు. ఈ (అత్యంత సాధారణ) సందర్భంలో డేటా రికవరీ కోసం అదనపు లోడ్‌ను ఎలాగైనా తగ్గించడం సాధ్యమేనా? మీరు వీటిని చేయగలరని తేలింది: ఈ ప్రయోజనం కోసం ప్రత్యేకంగా LRC రిడెండెన్సీ కోడ్‌లు ఉన్నాయి.

LRC (లోకల్ రీకన్‌స్ట్రక్షన్ కోడ్‌లు) అనేది విండోస్ అజూర్ స్టోరేజ్‌లో ఉపయోగించడం కోసం మైక్రోసాఫ్ట్ కనిపెట్టిన రిడెండెన్సీ కోడ్‌లు. LRC ఆలోచన సాధ్యమైనంత సులభం: అన్ని డేటా బ్లాక్‌లను రెండు (లేదా అంతకంటే ఎక్కువ) సమూహాలుగా విభజించండి మరియు ప్రతి సమూహం కోసం రిడెండెన్సీ కోడ్ బ్లాక్‌లలో కొంత భాగాన్ని విడిగా చదవండి. అప్పుడు కొన్ని రిడెండెన్సీ కోడ్ బ్లాక్‌లు అన్ని డేటా బ్లాక్‌లను (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 రీడ్-సోలమన్ కోడ్‌లను అధిగమిస్తుంది. రీడ్-సోలమన్ కోడ్‌లలో, ఒక బ్లాక్ డేటాను కూడా రికవర్ చేయడానికి, మీరు n బ్లాక్‌లను ఉపయోగించాలి మరియు LRCలో, ఒక బ్లాక్ డేటాను రికవర్ చేయడానికి, n/l బ్లాక్‌లను (మా ఉదాహరణలో n/2) ఉపయోగిస్తే సరిపోతుంది. మరోవైపు, అనుమతించదగిన లోపాల గరిష్ట సంఖ్య పరంగా LRC రీడ్-సోలమన్ కోడ్‌ల కంటే తక్కువ. ఎగువ ఉదాహరణలలో, రీడ్-సోలమన్ కోడ్‌లు ఏవైనా 4 ఎర్రర్‌ల కోసం డేటాను పునరుద్ధరించగలవు మరియు డేటాను పునరుద్ధరించలేనప్పుడు LRC కోసం 2 ఎర్రర్‌ల 4 కలయికలు ఉన్నాయి.

మరింత ముఖ్యమైనది నిర్దిష్ట పరిస్థితిపై ఆధారపడి ఉంటుంది, అయితే తరచుగా LRC అందించే అదనపు లోడ్‌లో పొదుపు కొంచెం తక్కువ విశ్వసనీయ నిల్వ కంటే ఎక్కువగా ఉంటుంది.

4. ఇతర రిడెండెన్సీ కోడ్‌లు

రీడ్-సోలమన్ మరియు LRC కోడ్‌లతో పాటు, అనేక ఇతర రిడెండెన్సీ కోడ్‌లు ఉన్నాయి. వేర్వేరు రిడెండెన్సీ కోడ్‌లు వేర్వేరు గణితాన్ని ఉపయోగిస్తాయి. ఇక్కడ కొన్ని ఇతర రిడెండెన్సీ కోడ్‌లు ఉన్నాయి:

• XOR ఆపరేటర్‌ని ఉపయోగించి రిడెండెన్సీ కోడ్. XOR ఆపరేషన్ n డేటా బ్లాక్‌లపై నిర్వహించబడుతుంది మరియు 1 బ్లాక్ రిడెండెన్సీ కోడ్‌లు పొందబడతాయి, అంటే n+1 స్కీమ్ (n డేటా బ్లాక్‌లు, 1 రిడెండెన్సీ కోడ్). లో ఉపయోగించారు RAID 5, ఇక్కడ డేటా బ్లాక్‌లు మరియు రిడెండెన్సీ కోడ్‌లు శ్రేణిలోని అన్ని డిస్క్‌లకు చక్రీయంగా వ్రాయబడతాయి.
• XOR ఆపరేషన్ ఆధారంగా సరి-బేసి అల్గోరిథం. 2 బ్లాక్‌ల రిడెండెన్సీ కోడ్‌లను రూపొందించడానికి మిమ్మల్ని అనుమతిస్తుంది, అంటే n+2 స్కీమ్.
• XOR ఆపరేషన్ ఆధారంగా STAR అల్గోరిథం. 3 బ్లాక్‌ల రిడెండెన్సీ కోడ్‌లను రూపొందించడానికి మిమ్మల్ని అనుమతిస్తుంది, అంటే n+3 స్కీమ్.
• పిరమిడ్ కోడ్‌లు మైక్రోసాఫ్ట్ నుండి వచ్చిన మరొక రిడెండెన్సీ కోడ్‌లు.

5. Yandex లో ఉపయోగించండి

అనేక Yandex ఇన్‌ఫ్రాస్ట్రక్చర్ ప్రాజెక్ట్‌లు విశ్వసనీయ డేటా నిల్వ కోసం రిడెండెన్సీ కోడ్‌లను ఉపయోగిస్తాయి. ఇవి కొన్ని ఉదాహరణలు:

• MDS అంతర్గత వస్తువు నిల్వ, నేను వ్యాసం ప్రారంభంలో వ్రాసాను.
• YT - Yandex యొక్క MapReduce సిస్టమ్.
• YDB (Yandex డేటాబేస్) - 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లలో 1 విఫలమైతే, డేటా చదవడానికి అందుబాటులో ఉండటం మాకు ముఖ్యం, కాబట్టి ఏదైనా DC అందుబాటులో లేనట్లయితే, యాక్సెస్ చేయలేని బ్లాక్‌ల సంఖ్య అనుమతించదగిన దానికంటే ఎక్కువగా ఉండకుండా బ్లాక్‌లను DCల మధ్య పంపిణీ చేయాలి. 8-2-2 పథకంలో, మీరు ప్రతి DCలో 4 బ్లాక్‌లను ఉంచవచ్చు, ఆపై ఏదైనా DC ఆఫ్ చేయబడినప్పుడు, 4 బ్లాక్‌లు అందుబాటులో ఉండవు మరియు డేటాను చదవవచ్చు. 3 DCలలో ఉంచేటప్పుడు మనం ఏ స్కీమ్ ఎంచుకున్నా, ఏదైనా సందర్భంలో (r + l) / n >= 0,5 ఉండాలి, అంటే నిల్వ రిడెండెన్సీ కనీసం 50% ఉంటుంది.

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. LRC గురించి Microsoft నుండి కథనం: 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