Zab: High-performance broadcast for primary-backup systems

Description

Zab: High-performance broadcast for primary-backup systems Flavio P. Junqueira, Benjamin C. Reed, and Marco Serafini Yahoo! Research ffpj,breed,[e-mail] Abstract—Zab is a crash-recovery atomic broadcast algorithm scheme [5], [6], [7] to maintain the state of replica processes we designed for the ZooKeeper coordination service. ZooKeeper consistent. With ZooKeeper, a primary process receives all implements a primary-backup scheme in which a primary incoming client requests, executes them, and propagates the process executes clients operations and uses Zab to propagate the 1 resulting non-commutative, incremental state changes in thecorresponding incremental state changes to backup processes . form of transactions to the backup replicas using Zab, theDue the dependence of an incremental state change on the sequence of changes previously generated, Zab must guarantee ZooKeeper atomic broadcast protocol. Upon primary crashes, that if it delivers a given state change, then all other changes it processes execute a recovery protocol both to agree upon a depends upon must be delivered first. Since primaries may crash, common consistent state before resuming regular operation Zab must satisfy this requirement despite crashes of primaries. and to establish a new primary to broadcast state changes.

Sujets

• Informatique
• Marketing et communication

Informations

• Publié par: kyann
• Publié le: 08 mai 2013
• Nombre de lectures: 52
• Langue: English
• Poids de l'ouvrage: 1 Mo

Extrait

Zab: High-performance broadcast for primary-backup systems

Flavio P. Junqueira, Benjamin C. Reed, and Marco Serafini Yahoo! Research { fpj,breed,serafini } @yahoo-inc.com

Abstract —Zab is a crash-recovery atomic broadcast algorithm scheme [5], [6], [7] to maintain the state of replica processes we designed for the ZooKeeper coordination service. ZooKeeper a rima s receives all implements a primary-backup scheme in which a primary i c n o c n o si m st i e n n g t. cli W e i n t t h re Z q o u o e K st e s e , p e er x , ecut p esthe ry m, p a ro n c d es propagatesthe process executes clients operations and uses Zab to propagate the corresponding incremental state changes to backup processes 1 . resulting non-commutative, incremental state changes in the Due the dependence of an incremental state change on the form of transactions to the backup replicas using Zab , the sequence of changes previously generated, Zab must guarantee ZooKeeper atomic broadcast protocol. Upon primary crashes, that if it delivers a given state change, then all other changes it er roto depends upon must be delivered first. Since primaries may crash, processes execute a recov y p col both to agree upon a Zab must satisfy this requirement despite crashes of primaries. common consistent state before resuming regular operation Applications using ZooKeeper demand high-performance from e a x n e d rc t i o se es t t h a e blis i ha ar n y ew rol p e r , im a a p r r y o t c o es b s ro m a u d s c t as h t a s v t e at t e he ch s a u n p g p e o s r . t T o o f the service, and consequently, one important goal is the ability pr m of having multiple outstanding client operations at a time. a quorum of processes. As processes can crash and recover, Zab enables multiple outstanding state changes by guaranteeing ulti l that at most one primary is able to broadcast state changes t s h a e m re ep c r a o n ce b s e sm o a v y er ex ti er m c e ise m thep p ri e m p a r r i y m r a o r l i e es mu a l n ti d pl i e n ti f m ac e t s. t T h o e and have them incorporated into the state, and by using a synchronization phase while establishing a new primary. Before i d n i s s t ti a n n g c u e is v h al t u h e e w d i i t f h fe e r a e c n h t e pr s i ta m b a l r i i s e h s ed ov p e ri r m ti ar me, A we iv a e ss n o i c n i s a t tean this synchronization phase completes, a new primary does not y. g ance broadcast new state changes. Finally, Zab uses an identification value maps to at most one process. Note that our notion scheme for state changes that enables a process to easily identify of instance shares some of the properties of views of group missing changes. This feature is key for efficient recovery. Experiments and experience so far in production show that our communication [8], but it presents some key differences. With design enables an implementation that meets the performance b g r r o o a u d p c c a o st, m a m n u d n c ic o a n t fi io g n u , ra a t l i l o p n ro c c h e a s n s g es es in ha a p g p i e v n en wh vieware p a r b o l c e e t s o s requirements of our applications. Our implementation of Zab en any can achieve tens of thousands of broadcasts per second, which joins or leaves. With Zab, processes change to a new view (or is sufficient for demanding systems such as our Web-scale ort applications. f p r r o im m a a ry q i u n o st r a u n m c . e)onlywhenaprimarycrashesorlosessupp Index Terms —Fault tolerance, Distributed algorithms, Primary backup, Asynchronous consensus, Atomic broadcast stat C e ri c ti h c a a n l g t e o is th i e nc d r e e s m ig e n nta o l f w Z i a th b r i e s the obse h r e va p ti r on io that each spect to t ev us state , I. I NTRODUCTION so there is an implicit dependence on the order of the state Atomicbroadcastisacommonlyusedprimitiveindis- c ar h b a i n tr g a e r s y . o S r t d at e e r, c a h n a d n i g t e i s s c c o ri n ti s c e a q l u t e o nt g l u y ar c a a n n t n e o e t t b ha e t a a p p p r li e e fi d x i o n f a th n e y tributed computing and ZooKeeper is yet another application touseatomicbroadcast.ZooKeeperisahighly-available a st p a p t l e ie c d ha to ng t e h s e g s e er n v e i r c a e te s d ta b te y . a St g a i t v e e c n h p a r n i g m e a s r a y re ar i e de de m li p v o e t r e e n d ta a n n d d coordination service used in production Web systems such as  applying the same state change multiple times does not lead to the Yahoo! crawler for over three years. Such applications  inconsistencies as long as the application order is consistent often comprise a large number of processes and rely upon ZooKeepertoperformimportantcoordinationtasks,suchas o w n it c h e t s h e e ma d n e t l i i c v s er is y s o u r f d fi e c r i . en C t o a n n s d eq si u m en p t l l i y fi , es g t u h a e ra i n m te pl e e in m g en a t t a - t l i e o as n t . storing configuration data reliably and keeping the status of running processes. Given the reliance of large applications on  As Zab is a critical component of the ZooKeeper core, ZooKeeper, the service must be able to mask and recover from  it must perform well. Some applications of ZooKeeper en- failures.[1] t c e o n m si p v a e s l s y. a P l r a e r v g i e ou n s u s m y b st e e r m o s f h p a ro v c e e b ss e e e s n a d n e d si u g s n e ed Z t o o oK co ee or p d e i r n e a x te - ZooKeeper is a replicated service, and it requires that a  long-lived and infrequent application state changes [9], [10], majority (or more generally a quorum) of servers has not crashed for progress. Crashed servers are able to recover  [11]. We designed ZooKeeper to have high throughput and and rejoin the ensemble as with previous crash-recovery  low latency, so that applications could use it extensively on protocols[2],[3],[4].ZooKeeperusesaprimary-backup c cl o u n s n te e r ct e e n d vi n r o o d n e m s. ents:datacenterswithalargenumberofwell- 1 A preliminary description of Zab was presented as a brief announcement When designing ZooKeeper, however, we found it difficult at the 23rd International Symposium on Distributed Computing, DISC 2009. to reason about atomic broadcast in isolation. There are re-