7 алгоритма, които трябва да знаете преди следващото си интервю за системен дизайн

Стартирайте страхотно следващото си интервю за системен дизайн.

В тази публикация ще обсъдим седем концепции за проектиране на системи, които могат да се използват за решаване на проблеми с дизайна, свързани с разпределени системи. Тъй като тези концепции могат да бъдат приложени към всички видове разпределени системи, те стават много удобни по време на интервюта за проектиране на системи.

Ето списъка с понятия, които ще обсъждаме:

Merkle Tree
Последователно хеширане
Прочетете Ремонт
Протокол за клюки
Филтър за разцвет
Сърдечен пулс
CAP и PACELC теореми

Да започваме.

1. Merkle Tree

Използва се за идентифициране на несъответствия в данните между сървърите.

Заден план

Разпределените системи поддържат множество копия на данни на различни сървъри (наречени реплики) за толерантност към грешки и по-висока наличност. За да поддържа данните в синхрон между всички сървъри на реплики, системата се нуждае от ефективен механизъм за сравняване на данни между две реплики. В разпределена среда, как можем бързо да сравним две копия на набор от данни, намиращи се в две различни реплики, и да разберем точно кои части са различни?

Определение

Една реплика може да съдържа много данни. Наивното разделяне на целия диапазон за изчисляване на контролни суми за сравнение не е много осъществимо; просто има твърде много данни за прехвърляне. Вместо това можем да използваме Merkle дървета, за да сравним реплики на диапазон.

Решение

„Дървото на Merkle“ е двоично дърво от хешове, където всеки вътрешен възел е хешът на своите две деца, а всеки листен възел е хеш на част от оригиналните данни.
Сравняването на дърветата Merkle е концептуално просто:

Сравнете кореновите хешове на двете дървета.
Ако са равни, спрете.
Рекурсия на ляво и дясно дете.

В крайна сметка това означава, че репликите знаят точно кои части от обхвата са различни, но количеството обменени данни е сведено до минимум. Основното предимство на дървото Merkle е, че всеки клон на дървото може да бъде проверен независимо, без да се изисква възли да изтеглят цялото дърво или целия набор от данни. Следователно дърветата на Merkle минимизират количеството данни, които трябва да бъдат прехвърлени за синхронизация, и намаляват броя на четенията на диска.

Недостатъкът на използването на дървета на Merkle е, че много ключови диапазони могат да се променят, когато възел се присъедини или напусне, в който момент дърветата трябва да бъдат преизчислени.

Примери

За анти-ентропия и за разрешаване на конфликти във фонов режим, Dynamo на Amazon използва Merkle дървета.

Подробности: https://lnkd.in/gZpt67uU

2. Последователно хеширане

Разпределените системи използват последователно хеширане, за да разпределят данни между сървърите.

Последователното хеширане помага с две неща:

Той картографира данни към физически сървъри. Всеки път, когато системата иска да прочете или напише данни, Consistent Hashing ни казва кой сървър съхранява данните.
Той гарантира, че само малък набор от ключове се движат, когато сървърите се добавят или премахват.

Повече подробности: https://lnkd.in/dJQKjN6i

3. Прочетете Ремонт

Когато данните се репликират в множество сървъри, Read Repair се използва за изпращане на най-новата версия на данните към сървъри с по-стара версия.

Поправете остарелите данни по време на операцията за четене, тъй като в този момент можем да четем данни от множество сървъри, за да сравним и намерим сървъри с остарели данни.

Подробности: https://lnkd.in/g6kCVgvr

4. Протокол за клюки

Използва се за ефективно споделяне на информация за състоянието между сървъри.

Всеки сървър следи информация за състоянието на други сървъри в клъстера и клюкарства (т.е. споделя) тази информация с един произволен сървър всяка секунда. По този начин в крайна сметка всеки сървър научава за състоянието на всеки друг възел в клъстера.

Подробности: https://bit.ly/3D2w14j

5. Филтър за цъфтеж

Структурата на данните на филтъра Bloom показва дали даден елемент може да е в набор или определено не е. Единствените възможни грешки са фалшиви положителни резултати, т.е. търсенето на несъществуващ елемент може да даде неправилен отговор. С повече елементи във филтъра процентът на грешки се увеличава. Празният филтър на Bloom е битов масив от m бита, всички зададени на 0. Има също k различни хеш функции, всяка от които картографира зададен елемент към една от m битови позиции.

За да добавите елемент, подайте го към хеш функциите, за да получите k битови позиции, и задайте битовете на тези позиции на 1.
За да проверите дали даден елемент е в набора, подайте го на хеш функциите, за да получите k битови позиции.
Ако някой от битовете на тези позиции е 0, елементът определено не е в набора.
Ако всички са 1, тогава елементът може да е в набора.

Ето филтър Bloom с три елемента P, Q и R. Състои се от 20 бита и използва три хеш функции. Цветните стрелки сочат към битовете, към които са нанесени елементите на набора.

Филтър на Bloom, състоящ се от 20 бита.

Елементът X определено не е в набора, тъй като хешира до битова позиция, съдържаща 0.
За фиксиран процент грешки добавянето на нов елемент и тестването за членство са операции с постоянно време, а филтър с място за „n“ елемента изисква O(n) пространство .

Подробности: https://bit.ly/3TbSAsR