Прывітанне, Хабр!
Сёння мы прапануем вашай увазе пераклад складанага артыкула аб рэалізацыі размеркаваных блакіровак сродкамі Redis і прапануем пагаварыць аб перспектыўнасці Redis як тэмы. Аналіз разгляданага алгарытму Redlock ад Марціна Клепмана, аўтара кнігі "", прыведзены .
Размеркаваныя блакіроўкі - вельмі карысны прымітыў, які ўжываецца ў шматлікіх асяроддзях, дзе розныя працэсы павінны працаваць над падзялянымі рэсурсамі па прынцыпе ўзаемнага выключэння.
Існуе шэраг бібліятэк і пастоў, якія апісваюць, як рэалізаваць DLM (мэнэджар размеркаваных блакіровак) пры дапамозе Redis, але ў кожнай бібліятэцы выкарыстоўваецца ўласны падыход, і якія прадстаўляюцца пры гэтым гарантыі даволі слабыя ў параўнанні з тым, што дасягальна пры дапамозе крыху больш складанага праектавання.
У гэтым артыкуле мы паспрабуем апісаць умоўна кананічны алгарытм, які дэманструе, як рэалізаваць размеркаваныя блакіроўкі пры дапамозе Redis. Мы пагаворым аб алгарытме пад назвай Рэдлок, ён рэалізуе менеджэр размеркаваных блакіровак і, на наш погляд, гэты алгарытм бяспечней, чым звычайны падыход з адзіным інстансам. Спадзяемся, што супольнасць яго прааналізуе, дасць зваротную сувязь і стане выкарыстоўваць у якасці адпраўной кропкі для рэалізацыі больш складаных ці альтэрнатыўных праектаў.
Рэалізацыі
Перш, чым перайсці да апісання алгарытму, прывядзем некалькі спасылак на ўжо гатовыя рэалізацыі. Імі можна карыстацца для даведкі.
- (рэалізацыя для Ruby). Таксама існуе Redlock-rb, які дадае пакет (gem) для выгоды размеркавання, і не толькі для гэтага.
- (рэалізацыя для Python).
- (рэалізацыя для Asyncio Python).
- (рэалізацыя для PHP).
- (яшчэ адна рэалізацыя для PHP)
- (PHP-бібліятэка для блакіровак)
- (рэалізацыя для Go).
- (рэалізацыя для Java).
- (рэалізацыя для Perl).
- (рэалізацыя для C++).
- (рэалізацыя для C#/.NET).
- (рэалізацыя для C#/.NET). З падтрымкай пашырэнняў async і lock.
- (рэалізацыя для C# .NET з канфігуруемым сховішчам дадзеных)
- (рэалізацыя для C# .NET)
- (рэалізацыя для NodeJS). Уключае падтрымку падаўжэння блакіровак.
Гарантыі бяспекі і даступнасці
Мы збіраемся змадэляваць наш праект за ўсё з трыма ўласцівасцямі, якія, на наш погляд, даюць мінімальныя гарантыі, неабходныя для эфектыўнага выкарыстання размеркаваных блакіровак.
- Уласцівасць бяспекі: Узаемнае выключэнне. У любы момант часу толькі адзін кліент можа ўтрымліваць блакаванне.
- Уласцівасць даступнасці A: Адсутнасць узаемных блакіровак. У канчатковым выніку заўсёды можна атрымаць блакіроўку, нават калі кліент, які заблакаваў рэсурс, адмовіць ці патрапіць у іншы сегмент дыска.
- Уласцівасць даступнасці B: адмоваўстойлівасць. Пакуль большасць вузлоў Redis працуе, кліенты здольныя набываць і вызваляць блакіроўкі.
Чаму рэалізацыі, заснаванай на аднаўленні пасля адмовы, у дадзеным выпадку недастаткова
Каб зразумець, што ж мы збіраемся паляпшаць, давайце прааналізуем бягучы стан спраў, які склаўся з большасцю бібліятэк для размеркаваных блакіровак, заснаваных на Redis.
Найпросты спосаб блакаваць рэсурс пры дапамозе Redis - стварыць ключ у інстансе. Звычайна ключ ствараецца з абмежаваным часам жыцця, гэта дасягаецца пры дапамозе прадугледжанай у Redis магчымасці expires, таму рана ці позна гэты ключ вызваляецца (уласцівасць 2 у нашым спісе). Калі кліенту неабходна вызваліць рэсурс, ён выдаляе ключ.
На першы погляд гэтае рашэнне суцэль працуе, але ёсць праблема: у нашай архітэктуры ўзнікае адзіны пункт адмовы. Што здарыцца, калі адмовіць кіроўны інстанс Redis? Давайце тады дадамо кіраваны! І будзем ім карыстацца, калі кіроўны недаступны. Нажаль, такі варыянт нежыццяздольны. Зрабіўшы так, мы не зможам правільна рэалізаваць уласцівасць узаемнага выключэння, патрэбнае нам для забеспячэння бяспекі, бо рэплікацыя ў Redis асінхронная.
Відавочна, што ў такой мадэлі ўзнікае стан гонкі:
- Кліент A набывае блакаванне на кіроўным.
- Вядучы адмаўляе да таго, як запіс у ключ будзе перададзены кіраванаму.
- Кіраваны падвышаецца да кіроўнага.
- Кліент B набывае блакаванне таго ж рэсурсу, які ўжо заблакаваны A. ПАРУШЭННЕ БЯСПЕКІ!
Часам зусім нармальна, што ў асаблівых абставінах, напрыклад, пры адмове, мноства кліентаў могуць адначасова трымаць блакаванне. У такіх выпадках можна прымяніць рашэнне на аснове рэплікацыі. У іншых выпадках раім рашэнне, апісанае ў гэтым артыкуле.
Правільная рэалізацыя з адзіным інстансам
Перш, чым паспрабаваць пераадолець недахопы канфігурацыі з адзіным інстансам, апісанай вышэй, давайце разбярэмся, як правільна дзейнічаць у гэтым простым выпадку, паколькі такое рашэнне насамрэч дапушчальна ў тых прыкладаннях, дзе стан гонкі час ад часу дапушчальна, а таксама таму, што блакіроўка на адзіным інстансе служыць той асновай, што выкарыстоўваецца ў апісаным тут размеркаваным алгарытме.
Каб набыць блакаванне, зробім так:
SET resource_name my_random_value NX PX 30000
Гэтая каманда ўстанаўлівае ключ, толькі калі ён яшчэ не існуе (опцыя NX), з тэрмінам дзеяння 30000 мілісекунд (опцыя PX). Для ключа задаецца значэнне “myrandomvalue”. Гэтае значэнне павінна быць унікальным у межах усіх кліентаў і ўсіх запытаў на блакіроўку.
У прынцыпе, выпадковае значэнне выкарыстоўваецца для бяспечнага вызвалення блакавання, пры дапамозе скрыпту, які паведамляе Redis: выдаляй ключ, толькі калі ён існуе, і значэнне, захаванае ў ім - менавіта тое, што і чакалася. Гэта дасягаецца пры дапамозе наступнага скрыпту на Lua:
if redis.call("get",KEYS[1]) == ARGV[1] then
return redis.call("del",KEYS[1])
else
return 0
endГэта важна, каб не дапусціць зняцця блакіроўкі, зробленай іншым кліентам. Напрыклад, кліент можа набыць блакаванне, потым заблакавацца падчас нейкай аперацыі, якая доўжыцца даўжэй, чым тэрмін дзеяння першай блакіроўкі (так, што тэрмін дзеяння ключа паспее скончыцца), і пазней выдаліць блакаванне, якую паставіў нейкі іншы кліент.
Скарыстацца простым DEL небяспечна, паколькі кліент можа выдаліць блакіроўку, пастаўленую іншым кліентам. Наадварот, пры выкарыстанні вышэйпрыведзенага скрыпту, кожнае блакаванне "падпісана" выпадковым радком, таму выдаліць яе зможа толькі той кліент, які раней яе паставіў.
Які павінен быць гэты выпадковы радок? Мяркую, гэта павінна быць 20 байт з /dev/urandom, але можна знайсці і меней затратныя спосабы зрабіць радок досыць унікальным для тых мэт, што перад вамі стаяць. Напрыклад, будзе звычайна пасеяць RC4 з /dev/urandom, а потым згенераваць на яго аснове псеўдавыпадковы струмень. Прасцейшае рашэнне злучана з камбінацыяй часу unix у мікрасекундным дазволе плюс ID кліента; яно не гэтак бяспечна, але, мабыць, адпавядае ўзроўню задач у большасці кантэкстаў.
Час, які мы выкарыстоўваем у якасці паказчыка часу жыцця ключа, называецца "час дзеяння блакіроўкі". Гэта значэнне - адначасова тэрмін, па заканчэнні якога блакіроўка аўтаматычна вызваліцца, і час, якое ёсць у кліента на выкананне аперацыі перш, чым іншы кліент зможа, у сваю чаргу, заблакаваць гэты рэсурс, без фактычнага парушэння гарантый узаемавыключэння. Такая гарантыя абмежавана толькі вызначаным акном часу, якое пачынаецца з моманту набыцця блакавання.
Такім чынам, мы абмеркавалі добры спосаб набыцця і вызвалення блакіроўкі. Сістэма (калі гаворка ідзе аб неразмеркаванай сістэме, якая складаецца з адзінага і заўсёды даступнага інстансу) бяспечная. Давайце пашырым гэтую канцэпцыю да размеркаванай сістэмы, у якой такіх гарантый у нас няма.
Алгарытм Redlock
У размеркаванай версіі алгарытму мяркуецца, што ў нас N кіроўных Redis. Гэтыя вузлы цалкам незалежныя адзін ад аднаго, таму мы не выкарыстоўваем рэплікацыю ці любую іншую няяўную сістэму каардынацыі. Мы ўжо расказалі, як бяспечна набываць і вызваляць блакіроўку на адзіным інстансе. Мы прымаем як дадзенасць, што алгарытм пры працы з адзіным інстансам будзе выкарыстоўваць менавіта гэты метад. У нашых прыкладах мы ўсталёўваны N роўным 5, гэтае цалкам разумнае значэнне. Такім чынам, нам спатрэбіцца выкарыстоўваць 5 вядучых Redis на розных кампутарах ці віртуальных машынах, каб гарантаваць, што яны будуць дзейнічаць у асноўным незалежна сябар ад сябра.
Каб набыць блакаванне, кліент выконвае наступныя аперацыі:
- Атрымлівае гэты час у мілісекундах.
- Паслядоўна спрабуе атрымаць блакіроўку на ўсе N інстансаў, выкарыстоўваючы ва ўсіх выпадках адно і тое ж імя ключа і выпадковыя значэнні. На этапе 2, усталёўваючы блакіроўку для кожнага інстанса, кліент, каб атрымаць яе, выкарыстоўвае затрымку, якая досыць кароткая ў параўнанні з тым часам, па заканчэнні якога блакіроўка аўтаматычна здымаецца. Напрыклад, калі працягласць блакіроўкі складае 10 секунд, то затрымка можа быць у дыяпазоне ~5-50 мілісекунд. Такім чынам выключаецца сітуацыя, у якой кліент мог бы доўга заставацца заблакаваны, спрабуючы дастукацца да які адмовіў вузла Redis: калі інстанс недаступны, то мы як мага хутчэй спрабуем злучыцца з іншым інстансам.
- Каб узяць блакіроўку, кліент вылічае, колькі часу скончыўся; для гэтага ён адымае з актуальнага значэння часу тую пазнаку часу, якая была атрымана ў кроку 1. Тады і толькі тады, калі кліент змог атрымаць блакіроўку на большасці інстансаў (як мінімум 3), і агульны час, які спатрэбіўся на тое, каб атрымаць блакіроўку, менш часу дзеяння блакіроўкі, лічыцца, што атрыманне блакіроўкі адбылося.
- Калі блакіроўка была атрымана, то за тэрмін яе дзеяння прымаецца зыходнае значэнне працягласці блакавання мінус мінулы час, вылічаны ў кроку 3.
- Калі кліенту па нейкім чынніку не атрымалася атрымаць блакіроўку (альбо ён не змог заблакаваць N/2+1 інстансаў, альбо час дзеяння блакавання апынулася адмоўным), то ён паспрабуе разблакаваць усе інстансы (нават тыя, што, як лічылася, ён не мог заблакаваць).
Ці з'яўляецца алгарытм асінхронным?
Дадзены алгарытм засноўваецца на дапушчэнні, што, хоць і няма сінхранізаваных гадзін, па якіх працавалі б усе працэсы, лакальны час у кожным працэсе ўсё роўна цячэ прыкладна ў адным тэмпе, і хібнасць невялікая ў параўнанні з агульным часам, па заканчэнні якога блакіроўка аўтаматычна здымаецца. Гэтае дапушчэнне вельмі нагадвае сітуацыю, уласцівую для звычайных кампутараў: на кожным кампутары ёсць лакальныя гадзіны, і звычайна мы можам разлічваць на тое, што разбежка па часе на розных кампутарах невялікая.
На дадзеным этапе мы павінны дбайней сфармуляваць наша правіла ўзаемнага выключэння: узаемнае выключэнне гарантавана толькі пры ўмове, што кліент, які ўтрымлівае блакіроўку, завершыць працу за час, на працягу якога блакіроўка сапраўдная (гэта значэнне атрымана ў кроку 3), мінус яшчэ некаторы час (усяго некалькі мілісекунд, каб кампенсаваць разбежку па часе паміж працэсамі).
Падрабязней пра падобныя сістэмы, якія патрабуюць узгаднення разбежкі па часе, распавядае наступны цікавы артыкул: .
Паўторная спроба пры адмове
Калі кліенту не ўдалося атрымаць блакіроўку, ён павінен паспрабаваць зноў гэта зрабіць, вытрымаўшы выпадковую затрымку; гэта робіцца з мэтай рассінхранізаваць мноства кліентаў, якія адначасова спрабуюць набыць блакіроўку аднаго і таго ж рэсурсу (што можа прывесці да сітуацыі «падзеленага мозгу», у якой пераможцаў не бывае). Акрамя таго, чым хутчэй кліент спрабуе набыць блакіроўку большасці інстансаў Redis, тым ужо акно, у якое можа паўстаць сітуацыя падзеленага мозгу (і тым менш неабходнасць у паўторных спробах). Таму ў ідэале кліент павінен паспрабаваць адначасова паслаць каманды SET да N інстансаў пры дапамозе мультыплексавання.
Тут варта падкрэсліць, наколькі важна, каб кліенты, якія не змаглі набыць большасць блакіровак, вызвалілі (часткова) набытыя блакіроўкі, каб не даводзілася чакаць заканчэнні тэрміну дзеяння ключа, перш чым блакіроўка над рэсурсам зноў зможа быць набыта (праўда, калі здараецца фрагментацыя сеткі , і кліент губляе сувязь з інстанс Redis, то даводзіцца заплаціць штраф за парушэнне даступнасці, пакуль чакаецца заканчэнне тэрміну дзеяння ключа).
Вызваленне блакіроўкі
Вызваленне блакавання - простая аперацыя, якая патрабуе проста разблакаваць усе інстансы, незалежна ад таго, ці здаецца кліенту, што ён змог паспяхова заблакаваць канкрэтны інстанс.
Меркаванні наконт бяспекі
Ці небяспечны алгарытм? Давайце паспрабуем уявіць, што адбываецца ў розных сцэнарах.
Для пачатку давайце выкажам здагадку, што кліент змог атрымаць блакіроўку над большасцю інстансаў. Кожны з інстансаў будзе змяшчаць ключ з адным і тым жа часам жыцця ва ўсіх. Аднак, кожны з гэтых ключоў усталёўваўся ў свой момант, таму і тэрмін дзеяння ў іх скончыцца ў розны час. Але, калі першы ключ быў усталяваны ў момант не горш T1 (час, які мы выбіраем перад кантактам з першым серверам), а апошні ключ быў усталяваны ў момант не горш T2 (час, у які быў атрыманы водгук ад апошняга сервера), то мы упэўнены, што першы ключ у мностве, у якога скончыцца тэрмін дзеяння, праіснуе як мінімум MIN_VALIDITY=TTL-(T2-T1)-CLOCK_DRIFT. Усе астатнія ключы скончацца пазней, таму мы можам быць упэўненыя, што ўсе ключы будуць адначасова сапраўдныя на працягу як мінімум гэтага часу.
На працягу часу, калі большасць ключоў застаюцца сапраўдныя, іншы кліент не зможа набыць блакіроўку, бо N/2+1 SET NX аперацый не могуць скончыцца поспехам, калі ўжо існуе N/2+1 ключоў. Таму, калі блакіроўка была набыта, то паўторна набыць яе ў той жа момант немагчыма (гэта парушала б уласцівасць узаемнага выключэння).
Праўда, мы жадаем пераканацца, што мноства кліентаў, адначасова якія спрабуюць набыць блакіроўку, не змогуць адначасова ў гэтым атрымаць поспех.
Калі кліент заблакаваў большасць інстансаў, затраціўшы на гэты час каля або больш, чым максімальны час працягласці блакіроўкі, то палічыць блакіроўку несапраўднай і разблакуе інстансы. Таму нам даводзіцца ўлічыць толькі той выпадак, у якім кліенту ўдалося заблакаваць большасць інстансаў за час, меншы, чым тэрмін дзеяння. У дадзеным выпадку, што тычыцца вышэйпададзенага аргумента, за час MIN_VALIDITY ніводны кліент не павінен быць у стане паўторна атрымаць блакіроўку. Таму мноства кліентаў змогуць заблакаваць N/2+1 асобнікаў за адзін і той жа час (які сканчаецца ў момант завяршэння этапу 2), толькі калі час для блакавання большасці было больш, чым час TTL, што ператварае блакіроўку ў несапраўдную.
А вы зможаце прывесці фармальны доказ бяспекі, паказаць наяўныя падобныя алгарытмы, ці знайсці баг у выкладзеным?
Меркаванні з нагоды даступнасці
Даступнасць сістэмы залежыць ад трох асноўных характарыстык:
- Аўтаматычнае зняцце блакавання (паколькі тэрмін дзеяння ключоў заканчваецца): у канчатковым выніку ключы будуць даступныя зноў, каб выкарыстоўвацца для блакіровак.
- Той факт, што кліенты звычайна дапамагаюць адзін аднаму, выдаляючы блакіроўкі, калі патрэбная блакіроўка не была набыта, альбо была набыта, а праца завяршылася; таму цалкам верагодна, што нам не прыйдзецца чакаць заканчэнні ключоў, каб паўторна набыць блакаванне.
- Той факт, што, калі кліенту неабходна паўторна паспрабаваць атрымаць блакіроўку, ён чакае на працягу параўнальна даўжэйшага часу, чым перыяд, які патрабуецца для набыцця большасці блакіровак. Так змяншаецца верагоднасць узнікнення сітуацыі падзеленага мозгу пры канкурэнцыі за рэсурсы.
Аднак даводзіцца плаціць штраф за зніжэнне даступнасці, роўны часу TTL у сегментах сеткі, таму, калі маюцца бесперапынныя сегменты, то гэты штраф можа набыць нявызначаны памер. Гэта адбываецца кожны раз, калі кліент набывае блакаванне, а потым адсякаецца ў іншы сегмент перш, чым паспее яе вызваліць.
У прынцыпе, пры наяўнасці бясконцых бесперапынных сегментаў сеткі, сістэма можа заставацца недаступнай на працягу бясконцага перыяду часу.
Прадукцыйнасць, аднаўленне пасля адмовы і fsync
Многія выкарыстоўваюць Redis, паколькі патрабуецца забяспечыць высокую прадукцыйнасць сервера блакіровак, на ўзроўні затрымак, неабходных для набыцця і вызвалення блакіровак, а таксама колькасці аперацый такога набыцця/вызвалення, якія ўдаецца выканаць у секунду. Для адпаведнасці гэтаму патрабаванню існуе стратэгія камунікацыі з N сервераў Redis, каб зменшыць затрымку. Гэта стратэгія мультыплексавання (ці ж "мультыплексаванне бедняка", пры якім сокет ставіцца ў неблакіруючы рэжым, адпраўляе ўсе каманды, а счытвае каманды пазней, мяркуючы, што час абароту паміж кліентам і кожным з інстансаў з'яўляецца падобным).
Праўда, даводзіцца ўлічваць яшчэ і меркаванне, злучанае з доўгачасовым захоўваннем дадзеных, калі мы імкнемся стварыць мадэль з упэўненым аднаўленнем пасля адмоваў.
У прынцыпе, каб растлумачыць праблему, давайце выкажам здагадку, што канфігуруем Redis наогул без доўгачасовага захоўвання дадзеных. Кліент паспявае заблакаваць 3 з 5 інстансаў. Адзін з інстансаў, які кліенту ўдалося заблакаваць, перазапускаецца, і ў гэты момант зноў узнікае 3 інстансы для аднаго і таго ж рэсурсу, які мы можам заблакаваць, і іншы кліент можа, у сваю чаргу, заблакаваць перазапушчаны інстанс, парушаючы ўласцівасць бяспекі, якое мяркуе выключнасць блакіровак.
Калі ўключыць апераджальнае захаванне дадзеных (AOF), сітуацыя крыху палепшыцца. Напрыклад, можна павысіць сервер, даслаўшы каманду SHUTDOWN і перазапусціўшы яго. Паколькі аперацыі заканчэння ў Redis семантычна рэалізаваны такім чынам, што час працягвае цечу, таксама калі сервер выключаны, з усімі нашымі патрабаваннямі ўсё нармальна. Нармальна датуль, пакуль забяспечваецца штатнае адключэнне. А што рабіць пры перабоях з харчаваннем? Калі Redis сканфігураваны па змаўчанні, з сінхранізацыяй fsync на кружэлцы кожную секунду, то магчыма, што пасля перазапуску мы не далічымся нашага ключа. Тэарэтычна, калі мы жадаем гарантаваць бяспеку блакаванняў пры любым перазапуску інстанса, то павінны ўключыць fsync=always у наладах доўгачасовага захавання дадзеных. Гэта цалкам заб'е прадукцыйнасць, да ўзроўню такіх CP-сістэм, якія традыцыйна прымяняюцца для бяспечнай рэалізацыі размеркаваных блакіровак.
Але сітуацыя лепшая, чым здаецца на першы погляд. У прынцыпе, бяспека алгарытму захоўваецца, паколькі, калі інстанс перазапускаецца пасля адмовы, ён больш не ўдзельнічае ні ў адной блакіроўцы, актыўнай у сапраўдны момант.
Каб гарантаваць гэта, трэба ўсяго толькі забяспечыць, каб пасля адмовы інстанс заставаўся недаступны на працягу часу, ледзь які перавышае максімум TTL, які мы выкарыстоўваем. Так мы дачакаемся заканчэння тэрміну дзеяння і аўтаматычнага вызвалення ўсіх ключоў, якія былі актыўныя ў момант адмовы.
Выкарыстоўваючы адкладзеныя перазапускі, у прынцыпе магчыма дасягнуць бяспекі і пры адсутнасці які-небудзь доўгачасовай захоўвальнасці ў Redis. Адзначым, праўда, што гэта можа выліцца ў штраф за парушэнне даступнасці. Напрыклад, пры адмове большасці інстансаў, сістэма стане глабальна недаступная на час TTL (і ніводны рэсурс заблакаваць у гэты час будзе нельга).
Падвышаем даступнасць алгарытму: падаўжаем блакіроўку
Калі праца, выкананая кліентамі, складаецца з дробных этапаў, тое магчыма скараціць задаецца па змаўчанні час дзеяння блакавання і рэалізаваць механізм падаўжэння блакаванняў. У прынцыпе, калі кліент заняты вылічэннямі, а значэнне тэрміна дзеяння блакавання небяспечна зніжаецца, можна адправіць усім інстансам скрыпт на Lua, які падаўжае TTL ключа, калі ключ яшчэ існуе, а яго значэнне па-ранейшаму з'яўляецца выпадковым, атрыманым, калі была набыта блакіроўка.
Кліент павінен лічыць блакаванне паўторна набытай толькі ў выпадку, калі яму ўдалося заблакаваць большасць інстанс на працягу часу дзеяння.
Праўда, тэхнічна алгарытм пры гэтым не мяняецца, таму максімальная колькасць паўторных спроб набыцця блакіровак павінна быць абмежавана, інакш будуць парушацца ўласцівасці даступнасці.
Крыніца: habr.com