Bloqueig distribuït mitjançant Redis

Hola Habr!

Avui portem a la vostra atenció la traducció d'un article complex sobre la implementació del bloqueig distribuït mitjançant Redis i us convidem a parlar sobre les perspectives de Redis com a tema. Anàlisi de l'algorisme Redlock en qüestió de Martin Kleppmann, autor del llibre "Aplicacions d'alta càrrega", donat aquí.

El bloqueig distribuït és un element primitiu molt útil que s'utilitza en molts entorns on diferents processos han de treballar en recursos compartits d'una manera mútuament excloent.

Hi ha diverses biblioteques i publicacions que descriuen com implementar DLM (Gestor de bloqueig distribuït) mitjançant Redis, però cada biblioteca té un enfocament diferent i les garanties que ofereixen són força febles en comparació amb el que es pot aconseguir amb un disseny una mica més sofisticat.

En aquest article intentarem descriure un algorisme canònic condicional que demostra com implementar el bloqueig distribuït mitjançant Redis. Parlarem d'un algorisme anomenat Redlock, implementa un gestor de bloqueig distribuït i, segons la nostra opinió, aquest algorisme és més segur que l'enfocament habitual d'una sola instància. Esperem que la comunitat l'analitzi, en faci comentaris i l'utilitzi com a punt de partida per a projectes més complexos o alternatius.

Implementació

Abans de passar a la descripció de l'algorisme, proporcionem diversos enllaços a implementacions ja fetes. Es poden utilitzar com a referència.

• Redlock-rb (implementació per a Ruby). També hi ha forquilla Redlock-rb, que afegeix un paquet (joia) per facilitar la distribució, i no només per això.
• Redlock-py (Implementació de Python).
• Aioredlock (implementació per a Asyncio Python).
• Redlock-php (implementació per a PHP).
• PHPRedisMutex (una altra implementació per a PHP)
• cheprasov/php-redis-lock (Biblioteca PHP per a panys)
• Redsync (implementació de Go).
• Redisson (implementació per a Java).
• Redis::DistLock (implementació per a Perl).
• Redlock-cpp (implementació per a C++).
• Redlock-cs (implementació per a C#/.NET).
• RedLock.net (implementació per a C#/.NET). Amb suport per a extensions asíncrones i de bloqueig.
• Scarlet Lock (implementació per a C# .NET amb magatzem de dades configurable)
• Redlock4Net (implementació per a C# .NET)
• node-redlock (implementació per a NodeJS). Inclou suport per estendre panys.

Garanties de Seguretat i Disponibilitat

Modelarem el nostre disseny amb només tres propietats que creiem que proporcionen les garanties mínimes necessàries per utilitzar eficaçment el bloqueig distribuït.

1. Propietat de seguretat: exclusió mútua. En un moment donat, només un client pot mantenir el pany.
2. Disponibilitat Propietat A: sense bloquejos. Sempre és possible adquirir un bloqueig, fins i tot si el client que ha bloquejat el recurs falla o aterra en un segment de disc diferent.
3. Disponibilitat Propietat B: Tolerància a fallades. Mentre la majoria dels nodes de Redis estiguin en execució, els clients poden adquirir i alliberar bloquejos.

Per què la implementació basada en la recuperació d'errors no és suficient en aquest cas
Per entendre què millorarem, analitzem l'estat actual de la majoria de biblioteques de bloqueig distribuïdes basades en Redis.

La manera més senzilla de bloquejar un recurs amb Redis és crear una clau a la instància. Normalment, es crea una clau amb una vida útil limitada, això s'aconsegueix mitjançant la funció de caducitat proporcionada a Redis, de manera que tard o d'hora s'allibera aquesta clau (propietat 2 de la nostra llista). Quan el client necessita alliberar el recurs, esborra la clau.

A primera vista, aquesta solució funciona força bé, però hi ha un problema: la nostra arquitectura crea un únic punt de fallada. Què passa si la instància Redis de l'amfitrió falla? Afegim un esclau llavors! I l'utilitzarem si el presentador no està disponible. Malauradament, aquesta opció no és viable. En fer-ho, no podrem implementar correctament la propietat d'exclusió mútua que necessitem per garantir la seguretat, perquè la rèplica a Redis és asíncrona.

Òbviament, en aquest model es produeix una condició de carrera:

1. El client A adquireix un bloqueig al mestre.
2. El mestre falla abans que l'entrada de clau es transfereixi a l'esclau.
3. El seguidor és ascendit a líder.
4. El client B adquireix un bloqueig al mateix recurs que A ja ha bloquejat. INFRACCIÓ DE LA SEGURETAT!

De vegades és completament normal que en circumstàncies especials, com ara una fallada, molts clients puguin subjectar el pany al mateix temps. En aquests casos, es pot aplicar una solució basada en la replicació. En cas contrari, recomanem la solució descrita en aquest article.

Implementació correcta amb una única instància

Abans d'intentar superar les deficiències de la configuració d'una sola instància descrita anteriorment, anem a entendre com gestionar correctament aquest cas senzill, ja que aquesta solució és realment vàlida en aplicacions on una condició de carrera és acceptable de tant en tant, i també perquè el bloqueig en un una única instància serveix com a base que s'utilitza en l'algorisme distribuït descrit aquí.

Per obtenir un bloqueig, feu això:

SET resource_name my_random_value NX PX 30000

Aquesta ordre instal·la una clau només si encara no existeix (opció NX), amb un període de validesa de 30000 mil·lisegons (opció PX). La clau està configurada a "myrandomvalue" Aquest valor ha de ser únic en tots els clients i en totes les sol·licituds de bloqueig.
Bàsicament, s'utilitza un valor aleatori per alliberar el bloqueig de manera segura, amb un script que diu a Redis: només elimineu la clau si existeix i el valor emmagatzemat en ell és exactament el que s'esperava. Això s'aconsegueix mitjançant el següent script Lua:

if redis.call("get",KEYS[1]) == ARGV[1] then
    return redis.call("del",KEYS[1])
else
    return 0
end

Això és important per evitar que s'elimini un bloqueig que té un altre client. Per exemple, un client pot adquirir un bloqueig, després quedar bloquejat en alguna operació que duri més que el primer bloqueig (de manera que la clau tingui temps per caducar) i després eliminar el bloqueig que algun altre client ha col·locat.
L'ús d'un DEL simple no és segur perquè un client pot eliminar un bloqueig que té un altre client. En canvi, quan s'utilitza l'script anterior, cada bloqueig està "signat" amb una cadena aleatòria, de manera que només el client que l'ha col·locat anteriorment pot eliminar-lo.

Quina ha de ser aquesta cadena aleatòria? Suposo que hauria de ser 20 bytes de /dev/urandom, però podeu trobar maneres menys costoses de fer que la cadena sigui prou única per als vostres propòsits. Per exemple, estaria bé sembrar RC4 amb /dev/urandom i després generar-ne un flux pseudoaleatori. Una solució més senzilla implica una combinació de temps Unix en resolució de microsegons més l'ID del client; no és tan segur, però probablement està a l'alçada de la tasca en la majoria de contextos.

El temps que utilitzem com a mesura de la vida útil de la clau s'anomena "vida útil del bloqueig". Aquest valor és tant la quantitat de temps abans que el bloqueig s'alliberi automàticament com la quantitat de temps que té un client per completar una operació abans que un altre client pugui bloquejar aquest recurs, sense infringir realment les garanties d'exclusió mútua. Aquesta garantia es limita només a un període de temps determinat, que comença des del moment en què es compra el pany.

Així doncs, hem parlat d'una bona manera d'adquirir i alliberar un bloqueig. El sistema (si estem parlant d'un sistema no distribuït format per una única instància i sempre disponible) és segur. Estenem aquest concepte a un sistema distribuït, on no tenim aquestes garanties.

Algorisme Redlock

La versió distribuïda de l'algorisme suposa que tenim N mestres Redis. Aquests nodes són completament independents entre si, de manera que no fem servir la replicació ni cap altre sistema de coordinació implícit. Ja hem explicat com adquirir i alliberar de manera segura un bloqueig en una sola instància. Donem per fet que l'algorisme, quan treballa amb una sola instància, utilitzarà exactament aquest mètode. En els nostres exemples posem N a 5, que és un valor raonable. Així, haurem d'utilitzar 5 màsters Redis en diferents ordinadors o màquines virtuals per assegurar-nos que actuen en gran mesura de manera independent els uns dels altres.

Per adquirir un bloqueig, el client realitza les operacions següents:

1. Obté l'hora actual en mil·lisegons.
2. Intenta obtenir un bloqueig seqüencial en totes les N instàncies, utilitzant el mateix nom de clau i valors aleatoris en tots els casos. A l'etapa 2, quan el client configura un bloqueig per instància, el client utilitza un retard per adquirir-lo que és prou curt en comparació amb el temps després del qual el bloqueig s'allibera automàticament. Per exemple, si la durada del bloqueig és de 10 segons, el retard podria estar entre 5 i 50 mil·lisegons. Això elimina la situació en què el client podria romandre bloquejat durant molt de temps intentant arribar a un node Redis fallit: si la instància no està disponible, aleshores intentem connectar-nos a una altra instància el més aviat possible.
3. Per agafar un pany, el client calcula quant de temps ha transcorregut; Per fer-ho, resta del valor de temps real la marca de temps que es va obtenir al pas 1. Si i només si el client va poder obtenir el bloqueig a la majoria de les instàncies (almenys 3), i el temps total que va trigar a fer-ho. obtenir el bloqueig, inferior a la durada del bloqueig, es considera que el bloqueig s'ha obtingut.
4. Si s'ha adquirit un bloqueig, es considera que la durada del bloqueig és la durada original del bloqueig menys el temps transcorregut calculat al pas 3.
5. Si el client no aconsegueix el bloqueig per algun motiu (no va poder bloquejar N/2+1 instàncies o la durada del bloqueig va ser negativa), intentarà desbloquejar totes les instàncies (fins i tot aquelles que pensava que no podia bloquejar). ).

L'algorisme és asíncron?

Aquest algorisme es basa en el supòsit que, tot i que no hi ha un rellotge sincronitzat en el qual funcionin tots els processos, l'hora local de cada procés segueix fluint aproximadament al mateix ritme i l'error és petit en comparació amb el temps total després del qual es produeix el bloqueig. alliberat automàticament. Aquesta hipòtesi és molt semblant a la situació típica dels ordinadors corrents: cada ordinador té un rellotge local, i normalment podem comptar amb el fet que la diferència horària entre diferents ordinadors és petita.

En aquest punt, hem de formular amb més cura la nostra regla d'exclusió mútua: l'exclusió mútua només està garantida si el client que té el bloqueig surt durant el temps que el bloqueig és vàlid (aquest valor obtingut al pas 3), menys temps més (en total uns quants mil·lisegons per compensar la diferència de temps entre processos).

El següent article interessant explica més sobre aquests sistemes que requereixen coordinació d'intervals de temps: Arrendaments: un mecanisme eficient de tolerancia a errors per a la coherència de la memòria cau de fitxers distribuïts.

Torna-ho a provar en cas d'error

Quan un client no aconsegueix un bloqueig, ha de tornar-ho a provar després d'un retard aleatori; això es fa per desincronitzar diversos clients que intenten adquirir un bloqueig al mateix recurs al mateix temps (la qual cosa pot provocar una situació de "cervell dividit" en la qual no hi ha guanyadors). A més, com més ràpid un client intenta adquirir un bloqueig en la majoria de les instàncies de Redis, més estreta serà la finestra en què es pot produir una situació de divisió del cervell (i menor serà la necessitat de reintents). Per tant, idealment, el client hauria d'intentar enviar ordres SET a N instàncies simultàniament mitjançant multiplexació.

Val la pena subratllar aquí com d'important és que els clients que no aconsegueixen adquirir la majoria de panys alliberin els panys (parcialment) adquirits, de manera que no hagin d'esperar que la clau caduqui abans que es pugui tornar a adquirir el bloqueig del recurs. (tot i que si es produeix una fragmentació de la xarxa i el client perd el contacte amb les instàncies de Redis, haureu de pagar una penalització de disponibilitat mentre espereu que caduqui la clau).

Allibera el pany

Alliberar un bloqueig és una operació senzilla que només requereix desbloquejar totes les instàncies, independentment de si el client sembla haver bloquejat correctament una instància concreta.

Consideracions de seguretat

L'algoritme és segur? Intentem imaginar què passa en diferents escenaris.

Per començar, suposem que el client va poder obtenir un bloqueig a la majoria de casos. Cada instància contindrà una clau amb la mateixa vida útil per a totes. Tanmateix, cadascuna d'aquestes claus es va instal·lar en un moment diferent, de manera que caducaran en moments diferents. Però, si la primera clau es va instal·lar en un moment no pitjor que el T1 (el moment que triem abans de contactar amb el primer servidor), i l'última clau s'ha instal·lat en un moment no pitjor que el T2 (el moment en què es va rebre la resposta). de l'últim servidor), aleshores estem segurs que la primera clau del conjunt que caduca sobreviurà almenys MIN_VALIDITY=TTL-(T2-T1)-CLOCK_DRIFT. Totes les altres claus caducaran més tard, de manera que podem estar segurs que totes les claus seran vàlides simultàniament almenys durant aquest temps.

Durant el temps que la majoria de claus romanguin vàlides, un altre client no podrà adquirir el bloqueig, ja que les operacions N/2+1 SET NX no poden tenir èxit si ja existeixen N/2+1 claus. Per tant, un cop adquirit un pany, és impossible tornar-lo a adquirir en el mateix moment (això vulneraria la propietat d'exclusió mútua).
Tanmateix, volem assegurar-nos que diversos clients que intenten adquirir un bloqueig alhora no puguin tenir èxit al mateix temps.

Si el client ha bloquejat la majoria de les instàncies durant aproximadament o més de la durada màxima del bloqueig, considerarà el bloqueig no vàlid i desbloquejarà les instàncies. Per tant, només hem de tenir en compte el cas en què el client ha aconseguit bloquejar la majoria d'instàncies en un temps inferior a la data de caducitat. En aquest cas, pel que fa a l'argument anterior, durant el temps MIN_VALIDITY cap client hauria de poder tornar a adquirir el bloqueig. Per tant, molts clients podran bloquejar N/2+1 instàncies al mateix temps (que acaba al final de l'etapa 2) només quan el temps per bloquejar la majoria fos superior al temps TTL, cosa que fa que el bloqueig no sigui vàlid.

Podeu proporcionar una prova formal de seguretat, indicar algorismes similars existents o trobar un error a l'anterior?

Consideracions d'accessibilitat

La disponibilitat del sistema depèn de tres característiques principals:

1. Allibera automàticament els panys (a mesura que caduquen les claus): les claus estaran disponibles de nou per utilitzar-les per als panys.
2. El fet que els clients acostumen a ajudar-se mútuament eliminant els panys quan no s'ha adquirit el pany desitjat, o s'ha adquirit i el treball ha finalitzat; així que és probable que no haurem d'esperar que caduquin les claus per tornar a adquirir el pany.
3. El fet que quan un client necessita tornar a provar d'adquirir un bloqueig, espera un temps relativament més llarg que el període necessari per adquirir la majoria de bloquejos. Això redueix la probabilitat que es produeixi una situació de cervell dividit en competir pels recursos.

Tanmateix, hi ha una penalització de disponibilitat igual al TTL dels segments de xarxa, de manera que si hi ha segments contigus, la penalització pot ser indefinida. Això passa cada cop que un client adquireix un bloqueig i després esquinça un altre segment abans que pugui alliberar-lo.

En principi, donats infinits segments de xarxa contigus, un sistema pot romandre indisponible durant un període de temps infinit.

Rendiment, failover i fsync

Moltes persones utilitzen Redis perquè necessiten un alt rendiment del servidor de bloqueig pel que fa a la latència necessària per adquirir i alliberar bloquejos i el nombre d'adquisicions/alliberaments que es poden completar per segon. Per complir amb aquest requisit, hi ha una estratègia per comunicar-se amb els servidors N Redis per reduir la latència. Aquesta és una estratègia de multiplexació (o "multiplexació del pobre", on el sòcol es posa en mode no bloquejador, envia totes les ordres i llegeix les ordres més tard, assumint que el temps d'anada i tornada entre el client i cada instància és similar) .

Tanmateix, també hem de tenir en compte la consideració associada a l'emmagatzematge de dades a llarg termini si ens esforcem per crear un model amb una recuperació fiable dels errors.

Bàsicament, per aclarir el problema, suposem que configurem Redis sense emmagatzematge de dades a llarg termini. El client aconsegueix bloquejar 3 de cada 5 instàncies. Es reinicia una de les instàncies que el client ha aconseguit bloquejar, i en aquest moment hi ha 3 instàncies de nou per al mateix recurs, que podem bloquejar, i un altre client pot, al seu torn, bloquejar la instància reiniciada, violant la propietat de seguretat que assumeix l'exclusivitat dels panys.

Si activeu les dades per endavant (AOF), la situació millorarà lleugerament. Per exemple, podeu promocionar un servidor enviant l'ordre SHUTDOWN i reiniciant-lo. Com que les operacions de caducitat a Redis s'implementen semànticament de tal manera que el temps continua fluint fins i tot quan el servidor està apagat, tots els nostres requisits estan bé. Això és normal sempre que es garanteixi una parada normal. Què fer en cas de tall de llum? Si Redis està configurat per defecte, amb fsync sincronitzant-se al disc cada segon, és possible que després d'un reinici no tinguem la nostra clau. Teòricament, si volem garantir la seguretat del bloqueig durant el reinici de qualsevol instància, hauríem d'habilitar-lo fsync=always a la configuració per a l'emmagatzematge de dades a llarg termini. Això matarà completament el rendiment, fins al nivell dels sistemes CP que s'utilitzen tradicionalment per implementar de manera segura bloquejos distribuïts.

Però la situació és millor del que sembla a primera vista. En principi, la seguretat de l'algorisme es conserva perquè quan la instància es reinicia després d'un error, ja no participa en cap bloqueig que estigui actiu actualment.

Per garantir-ho, només hem d'assegurar-nos que després d'un error la instància romangui no disponible durant un període de temps que superi lleugerament el TTL màxim que fem servir. D'aquesta manera esperarem fins a la data de caducitat i alliberament automàtic de totes les claus que estaven actives en el moment de la fallada.

Amb reinicis retardats, en principi és possible aconseguir seguretat fins i tot en absència de cap persistència a llarg termini a Redis. Tingueu en compte, però, que això pot comportar una multa per violar l'accessibilitat. Per exemple, si la majoria de les instàncies fallen, el sistema no estarà disponible globalment per al TTL (i no es podrà bloquejar cap recurs durant aquest temps).

Augmentem la disponibilitat de l'algorisme: ampliem el bloqueig

Si el treball realitzat pels clients consisteix en petits passos, és possible reduir la durada del bloqueig predeterminat i implementar un mecanisme per ampliar els bloquejos. En principi, si el client està ocupat amb la informàtica i el valor de caducitat del bloqueig és perillosament baix, podeu enviar un script Lua a totes les instàncies que estenguin el TTL de la clau si la clau encara existeix i el seu valor encara és un valor aleatori obtingut quan es va adquirir el pany.

Un client només hauria de considerar que es torna a adquirir un bloqueig si ha aconseguit bloquejar la majoria de les instàncies dins del període de validesa.

És cert que tècnicament l'algoritme no canvia, de manera que s'ha de limitar el nombre màxim d'intents repetits d'adquirir bloquejos, en cas contrari es violaran les propietats d'accessibilitat.

Font: www.habr.com