I n t r o d u c t i o n

L a r g e -s c a l e d a t a c e n t e r s y s t em s r e l y o n c o n t r o l p l a n e s e rv i c e s s u c h a s fi l e s y s t em n am e n o d e s , SDN c o n t r o l l e r s , c o o r d i n a t i o n s e r v i c e s , a n d s c h e d u l e r s . S u c h s e r v i c e s a r e o f t e n i n i t i a l l y b u i l t a s s i n g l e -s e r v e r s y s t em s t h a t s t o r e s t a t e i n l o c a l i n -m em o r y d a t a s t r u c t u r e s . P r o p e rt i e s s u c h a s d u r a b i l i t y , h i g h a v a i l a b i l i t y , a n d s c a l a b i l i t y a r e r e t r o fi t t e d b y d i s t r i b u t i n g s e r v i c e s t a t e a c r o s s m ac h i n e s . D i s t r i b u t i n g s t a t e f o r s u c h s e r v i c e s c a n b e d i ffi c u l t ; t h e i r r e q u i r em e n t f o r l o w l a t e n c y a n d h i g h r e s p o ns i v e n e s s p r e c l u d e s t h e u s e o f e x t e r n a l s t o r a g e s e r v i c e s w i t h fi x e d A P I s s u c h a s k e y -v a l u e s t o r e s , w h i l e c u s t om s o l u t i o n s c a n r e q u i r e m e l d i n g a p p l i c a t i o n c o d e w i t h a m e d l e y o f d i s t r i b u t e d p r o t o c o l s s u c h a s P a x o s [2 9 ] a n d T w o -P h a s e C omm i t ( 2 P C ) [ 2 1 ] , w h i c h a r e i n d i v i d u a l l y c om p l e x , s l o w / i n e f fi c i e n t w h e n l a y e r e d , a n d d i f fi c u l t t o m e r g e [4 0 , 6 0 ] .

A r e c e n t l y p r o p o s e d c l a s s o f d e s i g n s c e n t e r s o n t h e s h a r e d l o g a b s t r a c t i o n , f u n n e l i n g a l l u p d a t e s t h r o u g h a g l o b a l l y s h a r e d l o g t o e n a b l e f a u l t -t o l e r a n t d a t a b a s e s [ 9 -1 1 , 1 9 , 5 1 ] , m e t a d a t a a n d c o o r d i n a t i o n s e r v i c e s [ 8 , 1 2 ] , k e y -v a l u e a n d o b j e c t s t o r e s [ 3 , 4 1 , 5 7 ] , a n d fi l e s y s t em n am e s p a c e s [ 5 0 , 5 6 ] . S e r v i c e s b u i l t o v e r a s h a r e d l o g a r e s im p l e , c om p a c t l a y e r s t h a t m a p a h i g h -l e v e l A P I t o a p p e n d / r e a d o p e r a t i o n s o n t h e s h a r e d l o g , w h i c h a c t s a s t h e s o u r c e o f s t r o n g c o n s i s t e n c y , d u r a b i l i t y , f a i l u r e a t omi c i t y , a n d t r a n s a c t i o n a l i s o l a t i o n . F o r e x am p l e , a s h a r e d l o g v e r s i o n o f Z o oK e e p e r u s e s 1K l i n e s o f c o d e , a n o r d e r o f m a g n i t u d e l o w e r t h a n t h e o r i g i n a l s y s t em [ 8 ] .

U n f o r t u n a t e l y , t h e s im p l i c i t y o f a s h a r e d l o g r e q u i r e s im p o s i n g a s y s t em -w i d e t o t a l o r d e r t h a t i se x p e n s i v e , o f t e nim p o s s i b l e , a n d t y p i c a l l y u n n e c e s s a r y . P r e v i o u s w o r k s h o w e d t h a t a c e n t r a l i z e d , o f f -p a t h s e q u e n c e r c a n m a k e s u c h a t o t a l o r d e r f e a s i b l e a t i n t e rm e d i a t e s c a l e ( e . g . , a sm a l l c l u s t e r o f t e n s o f m a c h i n e s ) [ 7 , 8 ] . H o we v e r , a t l a r g e r s c a l e -i n t h e d im e n s i o n s o f s y s t em s i z e , t h r o u g h p u t , a n d n e tw o r k b a n dw i d t h / l a t e n c y -im p o s i n g a t o t a l o r d e r b e c om e s e x p e n s i v e : o r d e r i n g a l l u p d a t e s v i a a s e q u e n c e r l im i t s t h r o u g h p u t a n d s l o w s d o w n o p e r a t i o n s i f m a c h i n e s a r e s c a t t e r e d a c r o s s t h e n e tw o r k . I n a d d it i o n , f o r d e p l o ym e n t s t h a t s p a n g e o g r a p h i c a l r e g i o n s , a t o t a l o r d e r m a y b e im p o s s i b l e : a n e tw o r k p a r t i t i o n c a n c u t o f f c l i e n t s f r om t h e s e q u e n c e r o r a r e q u i r e d q u o r um o f t h e s e r v e r s im p l em e n t i n g t h e l o g . O n t h e fl i p s i d e , a t o t a l o r d e r i s o f t e n u n n e c e s s a r y : u p d a t e s t o d i s j o i n t d a t a ( e . g . , d i f f e r e n t k e y s i n a m a p ) d o n o t n e e d t o b e o r d e r e d , w h i l e u p d a t e s t h a t t o u c h t h e s am e d a t a m a y c omm u t e b e c a u s e t h e a p p l i c a t i o n r e q u i r e s w e a k c o n s i s t e n c y g u a ra n t e e s ( e . g . , c a u s a l c o n s i s t e n c y [ 5 ] ) . I n t h i s p a p e r , w e e x p l o r e t h e f o l l o w i n g q u e s t i o n :c a n w e p r o v i d e t h e s im -F i g u r e 1 :I n t h e F u z z y L o g , e a c h c o l o r c o n t a i n s u p d a t e s t o a d a t a s h a r d , w h i l e e a c h c h a i n c o n t a i n s u p d a t e s f r om a g e o g r a p h i c a l r e g i o n . ) . T h e F u z z y L o g m a t e r i a l i z e s a h a p p e n s -a f t e r r e l a t i o n b e tw e e n u p d a t e s : a n e d g e f r omA t o Bm e a n s t h a tAm u s t e x e c u t e a f t e rB . T h e F u z z y L o g c a p t u r e s tw o s o u r c e s o f p a r t i a l o r d e r i n g i n d i s t r i b u t e d s y s t em s : d a t a s h a r d i n g a n d g e o -r e p l i c a t i o n . I n t e r n a l l y , n o d e s i n t h e F u z z y L o g a r e o r g a n i z e d i n t o c o l o r s , w h e r e e a c h c o l o r c o n t a i n s u p d a t e s t o a s i n g l e a p p l i c a t i o n -l e v e l d a t a s h a r d . A c o l o r i s a s e t o f i n d ep e n d e n t , t o t a l l y o r d e r e dc h a i n s , w h e r e e a c h c h a i n c o nt a i n s u p d a t e s o r i g i n a t i n g i n a s i n g l e g e o g r a p h i c a l r e g i o n . C h a i n s w i t h i n a c o l o r a r e c o n n e c t e d b y c r o s s -l i n k s t h a t r e p r e s e n t u p d a t e c a u s a l i t y . T h e e n t i r e D A G -c o n s i s t i n g o f m u l t i p l e c o l o r s ( o n e p e r s h a r d ) a n d c h a i n s w i t h i n e a c h c o l o r ( o n e p e r r e g i o n ) -i s f u l l y r e p l i c a t e d a t e v e r y r eg i o n a n d l a z i l y s y n c h r o n i z e d , s o t h a t e a c h r e g i o n h a s t h e l a t e s t c o p y o f i t s o w n c h a i n , b u t s om e s t a l e p r e fi x o f t h e c h a i n s o f o t h e r r e g i o n s . A p p l i c a t i o n s b u i l t o v e r t h e F u z z y L o g A P I a r e n e a r l y a s s im p l e a s c o n v e n t i o n a l s h a r e d l o g s y s t em s . A s s h o w n i n F i g u r e 1 , F u z z y L o g c l i e n t s a r e a p p l i c a t i o n s e r v e r s t h a t m a i n t a i n i n -m em o r y c o p i e s o r v i e w s o f s h a r e d o b j e c t s . T o p e r f o rm a n o p e r a t i o n o n a n o b j e c t , t h e a p p l i c a t i o n a p p e n d s a n e n t r y t o t h e F u z z y L o g d e s c r i b i n g t h e m u t at i o n ; i t t h e n p l a y s f o rw a r d t h e F u z z y L o g , r e t r i e v i n g n e w e n t r i e s f r om o t h e r c l i e n t s a n d a p p l y i n g t h em t o i t s l oc a l v i e w , u n t i l i t e n c o u n t e r s a n d e x e c u t e s t h e a p p e n d e d e n t r y . T h e l o c a l v i e w s o n t h e a p p l i c a t i o n s e r v e r s c o n s t it u t e s o f t s t a t e t h a t c a n b e r e c o n s t r u c t e d b y r e p l a y i n g t h e F u z z y L o g . A F u z z y L o g a p p l i c a t i o n t h a t u s e s o n l y a s i ng l e c o l o r f o r i t s u p d a t e s a n d r u n s w i t h i n a s i n g l e r e g i o n i s i d e n t i c a l t o i t s s h a r e d l o g c o u n t e r p a r t ; W e a r g u e t h a t t h i s a b s t r a c t i o n i s u s e f u l( § 4 ) , d es c r i b i n g a n d e v a l u a t i n g a p p l i c a t i o n d e s i g n s t h a t o b t a i n t h e s im p l i c i t y o f t h e s h a r e d l o g a p p r o a c h w h i l e s c a l i n g l i n e a r l y w i t h a t om i c i t y , o b t a i n i n g w e a k e r c o n s i s t e n c y , a n d t o l e r a t i n g n e tw o r k p a r t i t i o n s . W e s h o w t h a t t h e a bs t r a c t i o n i s p r a c t i c a l l y f e a s i b l e( § 5 ) , d e s c r i b i n g a n d e v a lu a t i n g a s c a l a b l e , f a u l t -t o l e r a n t im p l em e n t a t i o n c a l l e d D a p p l e . S p e c i fi c a l l y , t h e s h a r e d l o g i s t h e s o u r c e o f c o n s i s t e n c y : c l i e n t s im p l em e n t s t a t e m a c h i n e r e p l i c a t i o n [ 4 6 ] b y f u nn e l i n g w r i t e s t h r o u g h t h e s h a r e d l o g a n d s y n c h r o n i z i n g t h e i r v i e w s w i t h i t o n r e a d s . T h e s h a r e d l o g a l s o p r o v i d e s d u r a b i l i t y : c l i e n t s c a n r e c o v e r v i e w s a f t e r c r a s h e s s im p l y b y r e p l a y i n g t h e s h a r e d l o g . I t a c t s a s a s o u r c e o f f a i l u r e a t om i c i t y a n d i s o l a t i o n f o r t r a n s a c t i o n s : t h e s h a r e d l o g i s l i t e r a l l y t h e s e r i a l i z a b l e o r d e r o f t r a n s a c t i o n s . T o t a l o r d e r i n g i s e x p e n s i v e . T h e t r a d i t i o n a l w a y t o im p o s e a t o t a l o r d e r i s v i a a l e a d e r t h a t r e c e i v e s u pd a t e s f r om c l i e n t s a n d s e q u e n c e s t h em ; h o w e v e r , t h i s l im i t s t h e t h r o u g h p u t o f t h e s y s t em a t t h e I /O b a n dw i d t h o f a s i n g l e m a c h i n e [1 6 ] . CO R FU [ 7 ] u s e s a n o f f -p a t h s e q u e n c e r -i n s t e a d o f a l e a d e r -t h a t i s s u e s t o k e n s o r c o n t i g u o u s p o s i t i o n s i n a n a d d r e s s s p a c e t o c l i e n t s . T o a p p e n d d a t a , a c l i e n t fi r s t o b t a i n s a t o k e n f r om t h e s e q u e n c e r -e f f e c t i v e l y r e s e r v i n g a n a d d r e s s i n t h e a d d r e s s s p a c e -a n d t h e n w r i t e s t h e p a y l o a d d ir e c t l y t o a s t r i p e o f s t o r a g e s e r v e r s r e s p o n s i b l e f o r s t o ri n g t h a t a d d r e s s . T h i s a l l o w s c l i e n t s t o t o t a l l y o r d e r u p d a t e s t o a c l u s t e r o f s t o r a g e s e r v e r s w i t h o u t p u s h i n g a l l I /O t h r o u g h a s i n g l e m a c h i n e ; i n s t e a d , t h e a g g r e g a t e t h r o u g h p u t o f t h e s y s t em i s l im i t e d b y t h e s p e e d a t w h i c h t h e s e q u e n c e r c a n u p d a t e a c o u n t e r a n d h a n d o u t t o k e n s ( r o u g h l y 6 0 0K o p s / s e c i n CO R FU [ 8 ] ) . T o l e v e r a g e t h e t o t a l o r d e r w i t h o u t r e q u i r i n g a l l c l i e n t s t o p l a y b a c k e ve r y e n t r y , r u n t im e s b u i l t o v e r CO R FU s u c h a s T a n g o [ 8 ] a n d v C o r f u [ 5 7 ] s u p p o r t s e l e c t i v e p l a y b a c k v i a s t r e am s a n d m a t e r i a l i z e d s t r e am s , r e s p e c t i v e l y . T h i s r e q u i r e s s eq u e n c e r s t a t e t o b e m o r e c om p l e x t h a n a s i n g l e c o u n t e r ( e . g . , p e r -s t r e am b a c k p o i n t e r s [ 8 ] o r a d d i t i o n a l s t r e ams p e c i fi c c o u n t e r s [ 5 7 ] ) .

M o t i v a t i o n

. T h e

W h i l e a n o f f -p a t h s e q u e n c e r w o r k s w e l l f o r sm a l l c l u st e r s ( e . g . , 2 0 s e r v e r s i n tw o a d j a c e n t r a c k s ) . S t a n d -a l o n e s e q u e n c e r s ( i . e . , s im p l e c o u nt e r s w i t h o u t p e r -s t r e am s t a t e ) a r e f a s t e r ; e . g . , a n RDMAb a s e d c o u n t e r r u n s a t 1 2 2M o p s / s e c ( 8 0X f a s t e r t h a n t h e n e x t h i g h e s t i n t h e l i t e r a t u r e ) [ 2 5 ] . E v e n a t t h i s s p e e d , t h e l a r g e s t c l u s t e r s u p p o r t e d a t 1 0 0 G b p s a n d a 5 1 2 -b y t e p a y l o a d w o u l d h a v e j u s t f o u r s e r v e r s . S om e a p p r o a c h e s b y p a s s t h e s e q u e n c e r t h r o u g h p u t c a p a t t h e c o s t o f i n c r e a s i n g a p p e n d l a t e n c y , e i t h e r b y a g g r e s s i v e b a t c h i n g n s i s t e n t w i t h a l i n e a r i z a b l e o r d e r ( i . e , i f a n u p d a t eBs t a r t s i n r e a l t im e a f t e r a n o t h e r u p d a t e Ac omp l e t e s , t h e nBo c c u r s a f t e rAi n t h e t o t a l o r d e r ) i s s u b j e c t t o u n a v a i l a b i l i t y d u r i n g n e tw o r k p a r t i t i o n s [ 1 4 ] . W e fi n d o u r s e l v e s a t a s e em i n g im p a s s e : a s h a r e d l o g e n a b l e s s im p l i c i t y a n d s t r o n g s em a n t i c s f o r d i s t r i b u t e d s y s t em s , b u t im p o s e s a t o t a l o r d e r t h a t i s e x p e n s i v e a n d s om e t im e s im p o s s i b l e . W e b r e a k t h i s im p a s s e w i t h a p a rt i a l l y o r d e r e d s h a r e d l o g a b s t r a c t i o n .

T h e F u z z y L o g A b s t r a c t i o n

T h e F u z z y L o g a d d r e s s e s t h e o r d e r i n g l im i t a t i o n s i n S e ct i o n 2v i a a n e x p r e s s i v e p a r t i a l o r d e r i n g A P I . T h e F u z z y -L o g ' s A P I c a p t u r e s tw o g e n e r a l p a t t e r n s v i a w h i c h a pp l i c a t i o n s p a r t i a l l y o r d e r o p e r a t i o n s . F i r s t , a p p l i c a t i o n s p a r t i t i o n t h e i r s t a t e a c r o s s l o g i c a l d a t a s h a r d s , s u c h t h a t u p d a t e s a g a i n s t d i f f e r e n t s h a r F i g u r e2s h o w s t h e F u z z y L o g A P I . A c l i e n t c r e a t e s a n i n s t a n c e o f t h e F u z z y L o g w i t h t h e n e wi n s t a n c ec a l l , s u p p l y i n g a s i n g l e c o l o r t o p l a y f o rw a r d . I t c a n p l a y n o d e s o f t h i s c o l o r w i t h t h es y n cc a l l . I t c a na p p e n d a n o d e t o a s e t o f c o l o r s . W e fi r s t d e s c r i b e t h e o p e r a t i o n o f t h e s e c a l l s i n a F u z z y L o g d e p l o ym e n t w i t h a s i n g l e c o l o r ( i . e . , a n a p p l i c a t i o n w i t h a s i n g l e d a t a s h a r d ) .

T h es y n cc a l l i s u s e d b y t h e c l i e n t t o s y n c h r o n i z e i t s s t a t e w i t h t h e F u z z y L o g .

N o t e t h a t e a c h n o d e e f f e c t i v e l y d e s c r i b e s a l i s t o f n o d e s -v i a i t s p o s i t i o n i n a t o t a l l y o r d e r e d c h a i n , a n d v i a e x p l i c i t p o i n t e r s f o r c r o s s -e d g e s -t h a t m u s t b e s e e n b ef o r e i t . F i g u r e 3s h o w s t h e c l i e n t s y n c h r o n i z i n g w i t h t h e r e g i o n i n p a n e l 1 ; t r a i l i n g b e h i n d i n p a n e l s 2 a n d 3 ; a n d s y n c h r o n i z i n g o n c e a g a i n i n p a n e l 4 . S n a p s h o t ID s r et u r n e d b y s y n cc a l l s a t d i f f e r e n t c l i e n t s c a n b e c om p a r e d t o c h e c k i f o n e s u b s um e s t h e o t h e r .

W h e n a c l i e n t a p p e n d s a n o d e t o a c o l o r w i t h a p p e n d , a n e n t r y i s i n s e r t e d i n t o t h e l o c a l r e g i o n ' s c h a i n f o r t h a t c o l o r . T h e e n t r y b e c om e s t h e n e w t a i l o f t h e c h a i n , a n d i t h a s a n e d g e i n t h e D A G p o i n t i n g t o t h e p r e v i o u s t a i l ; w e d e fi n e t h e t a i l a s t h

eIt o t h e r e g i o n ' s l o c a l c h a i n ( a f t e r n o d e H) , w i t h a c r o s s -e d g e t oE , w h i c h i s t h e l a t e s t n o d e i n t h e r em o t e c h a i n s e e n b y t h e c l i e n t . T o g a r b a g e c o l l e c t t h e F u z z y L o g , c l i e n t s c a n c a l lt r i m o n a s n a p s h o t ID t o i n d i c a t e t h a t t h e n o d e s i n i t a r e n o l o n g e r r e q u i r e d ( e . g . , b e c a u s e t h e c l i e n t s t o r e d t h e c o r r e s p o n d i n g m a t e r i a l i z e d v i e w i n s om e d u r a b l e e x t e rn a l s t o r e ) . A s n a p s h o t ID c a n a l s o b e p r o v i d e d t o t h e n e wi n s t a n c ec a l l , i n w h i c h c a s e p l a y b a c k s k i p s n o d e s w i t h i n t h e s n a p s h o t ; t h i s a l l o w s a n e w c l i e n t t o j o i n t h e s y s t em w i t h o u t p l a y i n g t h e F u z z y L o g f r om t h e b e g i nn i n g . W h i l e t h e s y n ca

I n o t h e r w o r d s , tw oa p p e n do pe r a t i o n s t o t h e s am e c o l o r i s s u e d b y c l i e n t s i n d i f f e r e n t r e g i o n s a r e o n l y o r d e r e d i f t h e n o d e i n t r o d u c e d b y o n e o f t h em h a s a l r e a d y b e e n s e e n b y t h e c l i e n t i s s u i n g t h e o t h e r o n e . I n t h i s c a s e , a n e d g e e x i s t s i n t h e D A G f r om t h e s e c o n d n o d e t o t h e fi r s t o n e . T h e i n t e r n a l s t r u c t u r e o f t h e D A G e n s u r e s t h a t t h e c o p i e s a t e a c h r e g i o n c o nv e r g e e v e n t h o u g h c o n c u r r e n t u p d a t e s c a n b e a p p l i e d i n d i f f e r e n t o r d e r s t o t h em : s i n c e t h e c l i e n t s a t e a c h r e g i o n m o d i f y a d i s j o i n t p a r t o f t h e D A G ( i . e . , t h e y a p p e n d t o t h e i r o w n p e r -r e g i o n c h a i n ) , t h e r e a r e n e v e r a n y c o n fl i c t s w h e n t h e c o p i e s a r e s y n c h r o n i z e d .

O p e r a t i o n s w i t h i n a s i n g l e r e g i o n a r e s e r i a l i z a b l e . A l l a p p e n da n ds y n co p e r a t i o n s i s s u e d b y c l i e n t s w i t h i n a r e g i o n e x e c u t e i n a m a n n e r c o n s i s t e n t w i t h s om e s e r i a l e x e c u t i o n . T h i s s e r i a l i z a t i o n o r d e r i s l i n e a r i z a b l e i f t h e o p e r a t i o n s a r e t o a s i n g l e c o l o r w i t h i n t h e r e g i o n ( i . e . , o n a s i n g l e c h a i n ) ; i t d o e s n o t n e c e s s a r i l y r e s p e c t r e a l -t im e o r d e r i n g w h e na p p e n do p e r a t i o n s s p a n m u l t i p l e c o l o r s .

D i s c u s s i o n : D e s i g n i n g t h e F u z z y L o g A P I r e q u i r e d b a l a n c i n g t h e p o w e r o f t h e A P I a g a i n s t i t s s im p l i c i t y a n d t h e f e a s i b i l i t y o f im p l em e n t i n g i t .

F u z z y L o g A p p l i c a t i o n s T h i s s e c t i o n d e s c r i b e s h o w a p p l i c a t i o n s c a n u s e t h e F u z z y L o g A P I w i t h a c a s e s t u d y o f a n i n -m em o r y k e y -v a l u e s t o r a g e s e r v i c e . I n t h i s s e c t i o n , t h e t e rm

' s e r v e r ' r e f e r s e x c l u s i v e l y t o a p p l i c a t i o n s e r v e r s s t o r i n g i n -m em o r y c o p i e s o f t h e k e y -v a l u e m a p , w h i c h i n t u r n a r e F u z z y L o g c l i e n t s . W e s t a r t w i t h a s im p l e d e s i g n c a l l e d L o gM a p t h a t r u n s o v e r a s i n g l e c o l o r w i t h i n a s i ng l e r e g i o n ( i . e . , i t e f f e c t i v e l y r u n s o v e r a s i n g l e t o t a l l y o u s e t h e F u z z y L o g t o c i r c um v e n t e a c h o f t h e s e l im i t at i o n s .

r d e r e d s h a r e d l o g ) . E a c h L o gM a p s e r v e r h a s a l o c a l i nm em o r y c o p y o f t h e m a p a n d s u p p o r t sp u t / g e t / d e l e t e o p e r a t i o n s o n k e y s . T h e s e r v e r c o n t i n u o u s l y e x e c u t e s a s y n co n t h e l o g i n t h e b a c k g r o u n d a n d a p p l i e s u p d a t e s t o k e e p i t s l o c a l v i e w u p -t o -d a t e . A g e to p e r a t i o n a t t h e s e r v e r s im p l y w a i t s f o r as y n ct o c om p l e t e t h a t s t a r t e d a f t e r i t w a s i s s u e d , b e f o r e a c c e s s i n g t h e l o c a l v i e w a n d r e t u r n i n g ; t h i s e n s u r e s t h a t a n y u p d a t e s t h a t w e r e a pp e n d e d t o t h e F u z z y L o g b e f o r e t h eg e tw a s i s s u e d a r e r e fl e c t e d i n t h e l o c a l v i e w , p r o v i d i n g l i n e a r i z a b i l i t y . A p u t / d e l e t eo p e r a t i o n a p p e n d s a n o d e t o t h e F u z z y L o g d e s c r i b i n g t h e u p d a t e ; i t t h e n w a i t s f o r as y n ct o a p p l y t h e u p d a t e t o t h e l o c a l v i e w , a t w h i c h p o i n t i t r e t u r n s . T h i

. 1 S c a l i n g w i t h a t om i c i t y w i t h i n a r e g i o n

T o c omm i t , t h e s e r v e r a p p e n d s a s p e c u l a t i v e i n t e n t i o n n o d e i n t o t h e F u z z y L o g t o t h e s e t o f c o l o r s c o r r e s p o n d i n g t o t h e s h a r d s b e i n g r e a d a n d w r i t t e n . W h e n a s e r v e r e n c o u n t e r s t h e i nt e n t i o n n o d e i n t h e c o l o r i t i s p l a y i n g , i t a p p e n d s a s e co n d n o d e w i t h a y e s / n o d e c i s i o n t o t h e s e t o f c o l o r s . T o g e n e r a t e t h i s d e c i s i o n , t h e s e r v e r e x am i n e s t h e s u b -p a r t o f t h e t r a n s a c t i o n t o u c h i n g i t s o w n s h a r d a n d i n d e p e n

d e n t l y ( b u t d e t e rm i n i s t i c a l l y ) v a l i d a t e s i t ( e . g . , c h e c k i n g f o r r e a d -w r i t e c o n fl i c t s w h e n p r o v i d i n g s t r i c t s e r i a l i z a b i li t y ) . A s e r v e r o n l y a p p l i e s t h e t r a n s a c t i o n t o i t s l o c a l s t a t e i f i t e n c o u n t e r s b o t h t h e o r i g i n a l i n t e n t i o n a n d a d e c i s i o n m a r k e d y e s f o r e a c h c o l o r i n v o l v e d . I n t e r e s t i n g l y , t h i s p r o t o c o l p r o v i d e s s t r i c t s e r i a l i z a b i li t y e v e n t h o u g h t h e F u z z y L o g i t s e l f i s o n l y s e r i a l i z a b l e . I n t u i t i v e l y , w i t h i n a s i n g l e c o l o r , i f a c l i e n t w a i t s a f t e r a p -p e n d i n g a n i n t e n t i o n f o r a t r a n s a c t i o nTu n t i l i t p l a y s t h e n o d e , i t i s g u a r a n t e e d t o h a v e s e e n a l l t r a n s a c t i o n s t h a t c o u l d a p p e a r b e f o r e Ti n t h e s e r i a l o r d e r . A s a r e s u l t , f ut u r e t r a n s a c t i o n s m u s t a p p e a r l a t e r i n t h e s e r i a l o r d e r , e ns u r i n g s t r i c t s e r i a l i z a b i l i t y .

. 3 T o l e r a t i n g n e tw o r k p a r t i t i o n s W h i l e C RD TM a p c a n p r o v i d e a v a i l a b i l i t y d u r i n g n e tw o r k p a r t i t i o n s , i t d o e s s o b y s a c r i fi c i n g c o n s i s t e n c y e v e n w h e n t h e r e i s n o p a r t i t i o n i n t h e

. 1 S i n g l e -c o l o r o p e r a t i o n R e c a l l t h a t e a c h F u z z y L o g c o l o r c o n s i s t s o f a s e t o f t ot a l l y o r d e r e d c h a i n s , o n e p e r r e g i o n ; e a c h r e g i o n h a s t h e l a t e s t c o p y o f i t s o w n l o c a l c h a i n , b u t a p o t e n t i a l l y s t a l e c o p y o f t h e o t h e r r e g i o n s ' c h a i n s . D a p p l e s t o r e s e a c h c h a i n o n a s i n g l e l o g , s u c h t h a t t h e o r d e r o f t h e e n t r i e s i n t h e l o g m a t c h e s t h e c h a i n o r d e r ( i . e . , i f a c h a i n c o nt a i n s a n e d g e f r om Bt o A , Ba p p e a r s imm e d i a t e l y a f t e r Ai n t h e c o r r e s p o n d i n g l o g ) . I n a d e p l o ym e n t w i t h Rr eg i o n s , e a c h r e g i o n s t o r e sRl o g s , o n e p e r c h a i n . C l i e n t s i n t h e r e g i o n a c t i v e l y w r i t e t o o n e o f t h e s e ( t h e l o c a l l o g ) , w h i l e t h e r em a i n i n g a r e a s y n c h r o n o u s l y r e p l i c a t e d f r om o t h e r r e g i o n s (w e c a l l t h e s e s h a d o w l o g s ) . E a c h s e r v e r e x p o s e s a l o w -l e v e l A P I c o n s i s t i n g o f t h r e e p r im -i t i v e s :l o g -a p p e n d , w h i c h a p p e n d s a n e n t r y t o a l o g ; l o g -s n a p s h o t , w h i c h a c c e p t s a s e t o f l o g s a n d r e t u r n s t h e i r c u r r e n t t a i l p o s i t i o n s ; a n d l o g -r e a d , w h i c h r e t u r n s t h e l o g e n t r y a t a g i v e n p o s i t i o n .

C l i e n t s im p l em e n t t h e s y n c o n a c o l o r v i a a l o g -s n a p s h o to n t h e l o g s f o r t h a t c o l o r , f o l l o w e d b y a s e q u e n c e o fl o g -r e a d s . T h e r e t u r n v a l u e o f l o g -s n a p s h o ta c t s a s a v e c t o r t im e s t am p f o r t h e c o l o r , s umm a r i z i n g t h e s e t o f n o d e s p r e s e n t f o r t h a t c o l o r i n t h e l o c a l r e g i o n ; t h i s i s e x a c t l y t h e s n a p s h o t ID r e t u r n e d b y t h e s y n cc a l l . T h e c l i e n t l i b r a r y f e t c h e s n e w n o d e s t h a t h a v e a p p e a r e d s i n c e i t s l a s ts y n cv i al o g -r e a dc a l l s . W h e n t h e a p p l i c a t i o n c a l l s a p p e n do n a c o l o r , t h e c l i e n t l i b r a r y c a l l s l o g -a p p e n do n t h e l o c a l l o g f o r t h a t c o l o r .

I t i n c l u d e s t h e v e c t o r t im e s t am p o f n o d e s s e e n t h u s f a r i n t h e n e w e n t r y ; a s a r e s u l t , e a c h a p p e n d e d e n t r y i n c l u d e s p o i n t e r s t o t h e s e t o f n o d e s i t c a u s a l l y d e p e n d s o n ( t h e s e a r e t h e c r o s s -e d g e s i n t h e F u z z y L o g D A G ) . O n as y n c , t h e c l i e n t l i b r a r y c h e c k s e a c h e n t r y i t r e a d s f o r d e p e n d e nc i e s a n d r e c u r s i v e l y f e t c h e s t h em b e f o r e d e l i v e r i n g t h em t o t h e a p p l i c a t i o n . I n t h i s m a n n e r , t h e c l i e n t e n s u r e s t h a t p l a y b a c k o f a s i n g l e c o l o r h a p p e n s i n D A G o r d e r . E a c h c h a i n s e r v e r p e r i o d i c a l l y s y n c h r o n i z e s w i t h i t s c o u n t e r p a r t s i n r em o t e r e g i o n s , u p d a t i n g t h e s h a d o w l o g s w i t h n e w e n t r i e s t h a t o r i g i n a t e d i n t h o s e r e g i o n s . T o f e t c h u p d a t e s , t h e c h a i n s e r v e r i t s e l f a c t s a s a c l i e n t t o t h e r em o t e c h a i n s e r v e r a n d u s e s as y n cc a l l ; t h i s e n s u r e s t h a t c r o s s -c h a i n d e p e n d e n c i e s a r e r e s p e c t e d w h e n i t r e c e i v e s r em o t e n o d e s . C o p i e d -o v e r e n t r i e s a r e r e fl e c t e d i n s u bs e q u e n t s y n cc a l l s b y c l i e n t s a n d p l a y e d ; n e w e n t r i e s a pp e n d e d b y t h e c l i e n t s t h e n h a v e c r o s s -e d g e s t o t h em . D a p p l e r e p l i c a t e s e a c h p a r t i t i o n v i a c h a i n r e p l i c at i o n . E a c hl o g -a p p e n d o p e r a t i o n i s p a s s e d d o w n t h e c h a i n a n d a c k n o w l e d g e d b y t h e t a i l r e p l i c a , w h i l e l o g -s n a p s h o ti s s e n t d i r e c t l y t o t h e t a i l . O n c e t h e c l i e n t o b t a i n s a s n a p s h o t , s u b s e q u e n tl o g -r e a do p e r a t i o n s c a n b e s a t i s fi e d b y a n y r e p l i c a i n t h e c h a i n . T h e c h o i c e o f r e p l i c a t i o n p r o t o c o l i s o r t h o g o n a l t o t h e s y s t em d e s i g n :

w e c o u l d e q u a l l y u s e M u l t i -P a x o s . S k e e n ' s o r i g i n a l a l g o r i t hm p r o d u c e s a s e r i a l i z a b l e o rd e r f o r o p e r a t i o n s b y m u l t i p l e c l i e n t s a c r o s s d i f f e r e n t s u b s e t s o f s e r v e r s . U n f o r t u n a t e l y , i t i s n o t t o l e r a n t t o t h e f a i l u r e o f i t s p a r t i c i p a n t s . I n o u r s e t t i n g , e a c h ' s e r v e r ' i s a r e p l i c a t e d p a r t i t i o n o f c h a i n s e r v e r s a n d c a n b e a s - s um e d t o n o t f a i l . H o w e v e r , t h e c l i e n t s i n o u r s y s t em a r e u n r e p l i c a t e d a p p l i c a t i o n s e r v e r s t h a t c a n c r a s h . W e a ss um e t h a t s u c h c l i e n t f a i l u r e s a r e i n f r e q u e n t ; t h i s p u s h e s u s t o w a r d s a p r o t o c o l t h a t i s f a s t i n

. 2 M u l t i -c o l o r o p e r a t i o n

m s ) , w h i c h t h e y o b t a i n f r om e a c h s e r v e r ( o r t h e h e a d o f t h e r e p l i c a c h a i n f o r e a c h p a r t i t i o n ) ; i f t h e l e a s e e x p i r e s , o r t h e h e a d o f t h e r e p l i c a c h a i n c h a n g e s , t h e o p e r a t i o n i s r e j e c t e d . W e n o w d e s c r i b e f a i l u r e -f r e e o p e r a t i o n . T h e f a s t p a t h c o n s i s t s o f tw o p h a s e s , a n d h a s t o e x e c u t e f r om s t a r t t o c om p l e t i o n w i t h i n t h e c o n t e x t o f a s i n g l e s e t o f l e a s e s , o n e p e r i n v o l v e d p a r t i t i o n . F o r e a s e o f e x p o s i t i o n , w e a s s um e e a c h p a r t i t i o n h a s o n e c h a i n s e r v e r r e p l i c a . I n t h e fi r s t p h a s e , a n o r i g i n c l i e n t ( i . e . , a c l i e n t o r i g i n a ti n g a m u l t i -a p p e n d ) c o n t a c t s t h e i n v o l v e d c h a i n s e r v e r s , e a c h o f w h i c h r e s p o n d s w i t h a t im e s t am p c o n s i s t i n g o f t h e v a l u e o f i t s c l o c k a u gm e n t e d w i t h a s e r v e r -s p e c i fi c u n i q u e n o n c e t o b r e a k t i e s . E a c h c h a i n s e r v e r i n s e r t s t h e m u l t i -a p p e n d o p e r a t i o n i n t o a p e n d i n g q u e u e a l o n g w i t h t h e r e t u r n e d t im e s t am p . F o r e x am p l e , i n F i g u r e 5 , o r i g i n c l i e n t C 1 c o n t a c t s S 1 , w h i c h r e s p o n d s w i t h 2 . 1 , w h e r e t h e l o c a l c l o c k v a l u e i s 2 a n d t h e u n i q u e n o n c e i s 1 . I n a d d i t i o n , t h e o r i g i n c l i e n t p r o v i d e s a W A L (w r i t e -a h e a d l o g ) e n t r y t h a t e a c h c h a i n s e r v e r s t o r e s ; t h i s i n c l u d e s t h e p a y l o a d , t h e c o l o r s i n v o l v e d , a n d t h e s e t o f l e a s e s u s e d b y t h e m u l t i -a p p e n d . O n c e t h e c l i e n t h e a r s b a c k f r om a l l t h e i n v o l v e d c h a i ns e r v e r s , i t c om p u t e s t h e m a x a c r o s s a l l r e c e i v e d t im e st am p s , a n d t r a n sm i t s t h a t b a c k t o t h e c h a i n s e r v e r s i n a s e c o n d p h a s e : t h i s m a x i s t h e t im e s t am p a s s i g n e d t o t h e m u l t i -a p p e n d a n d i s s u f fi c i e n t t o s e r i a l i z e t h e m u l t ia p p e n d s i n a r e g i o n . F o r e x am p l e , i n F i g u r e5 , c l i e n t C 1 s e n d s b a c k a m a x t im e s t am p o f 2 . 2 t o s e r v e r s S 1 a n d S 2 . W h e n a c h a i n s e r v e r r e c e i v e s t h i s m e s s a g e , i t m o v e s

t h e m u l t i -a p p e n d f r om t h e p e n d i n g q u e u e t o a d e l i v e r y q u e u e ; i t t h e n w a i t s u n t i l t h e r e i s n o o t h e r m u l t i -a p p e n d i n t h e p e n d i n g q u e u e w i t h a l o w e r r e t u r n e d t im e s t am p , o r i n t h e d e l i v e r y q u e u e w i t h a l o w e r m a x t im e s t am p ( i .

e t e s i n tw o p h a s e s . A t h i r d s t e p o f f t h e c r i t i c a l p a t h i n v o l v e s t h e c l i e n t s e n d i n g a c l e a n -u p m e s s a g e t o d e l e t e t h e p e ra p p e n d s t a t e ( t h e W A L , p l u s a s t a t u s b i t i n d i c a t i n g t h e l a s t e x e c u t e d p h a s e ) a t t h e c h a i n s e r v e r s ; t h i s i s l a z i l y e xe c u t e d a f t e r a m u l t i p l e o f t h e l e a s e t im e -o u t , a n d c a n b e p i g g y b a c k e d o n o t h e r m e s s a g e s . I f a l e a s e e x p i r e s b ef o r e t h e tw o p h a s e s a r e e x e c u t e d a t t h e c o r r e s p o n d i n g s e r v e r , o r t h e o r i g i n c l i e n t c r a s h e s , i t l e a v e s o n e o r m o r e s e r v e r s i n a w e d g e d s t a t e , w i t h t h e m u l t i -a p p e n d s t u c k i n t h e p e n d i n g q u e u e a n d b l o c k i n g n e w a p p e n d s t o t h e c o l o r s i n v o l v e d . A f t e r a t im e -o u t , t h e c h a i n s e r v e r b e g i n s r e s p o n d i n g t o n e w a p p e n d r e q u e s t s w i t h a s t u c k -e r r e r r o r m e s s a g e , a l o n g w i t h t h e W A L e n t r y o f t h e s t u c k m u l t ia p p e n d . A c l i e n t t h a t r e c e i v e s s u c h a n e r r o r m e s s a g e c a n i n i t i a t e t h e r e c o v e r y p r o t o c o l f o r t h e m u l t i -a p p e n d .

A c l i e n t r e c o v e r i n g a s t u c k m u l t i -a p p e n d ( i . e . , a r ec o v e r y c l i e n t )

p r o c e e d s i n t h r e e p h a s e s : i t f e n c e s a c t i v i t y b y t h e o r i g i n c l i e n t o r o t h e r r e c o v e r y c l i e n t s ; d e t e rm i n e s t h e w e d g e d s t a t e o f t h e s y s t em ; a n d c om p l e t e s t h e m u l t ia p p e n d . T h e f e n c i n g p h a s e i n v o l v e s a c c e s s i n g t h e l e a s e s e t o f t h e o r i g i n a l c l i e n t (w h i c h i s s t o r e d i n t h e W A L ) , i n v a l i d a t i n g i t a t t h e s e r v e r s , a n d w r i t i n g a n e w r e c o ve r y l e a s e s e t a t a d e s i g n a t e d t e s t -a n d -s e t l o c a t i o n o n o n e o f t h e c h a i n s e r v e r s . I f s om e o t h e r r e c o v e r y c l i e n t a l r e a d y s t o r e d a l e a s e s e t a t t h i s l o c a t i o n , w e w a i t f o r t h a t c l i e n t t o r e c o v e r t h e a p p e n d , f e n c i n g i t a f t e r a t im e -o u t . F e n c i n g e n s u r e s t h a t a t a n y g i v e n p o i n t , o n l y o n e c l i e n t i s a c t i v e ; t h e W

o v e t h a t t h e t e s t -a n d -s e t m e c h a n i sm e n s u r e s t h a t o n l y o n e c l i e n t i s a ct i v e l y m u t a t i n g t h e s t a t e o f t h e s y s t em a t a n y g i v e n p o i n t i n t im e . F u r t h e r , w e s h o w t h a t e a c h a p p e n d c a n b e m o d -

e l e d a s a f o u r -s t a g e s t a t e m a c h i n e ( s om e s e r v e r s i n p h a s e 1 , s om e u n i n i t i a t e d ; s om e i n p h a s e 1 , s om e i n p h a s e 2 ; s om e i n p h a s e 2 , s om e c om p l e t e d ; a l l c om p l e t e d ) . A n y r e c o v e r y c l i e n t fi n d s t h e s y s t em i n a p a r t i c u l a r s t a t e a n d a d v a n c e s i t i n a m a n n e r i d e n t i c a l t o t h e n o n -f a i l i n g c a s e . T h e r em a i n d e r o f o u r e v a l u a t i o n i s s t r u c t u r e d a s f o ll o w s : F i r s t , w e e v a l u a t e t h e d i f f e r e n c e s b e tw e e n D a p p l e a n d p r i o r s h a r e d l o g d e s i g n s ( § 6 . 1 ) . S e c o n d , w e u s e t h e M a p v a r i a n t s f r om § 4 t o s h o w t h a t D a p p l e p r o v i d e s l i n e a r s c a l i n g w i t h a t om i c i t y ( § 6 . 2 ) , w e a k e r c o n s i s t e n c y g u a ra n t e e s ( § 6 . 3 ) , a n d n e tw o r k p a r t i t i o n t o l e r a n c e ( § 6 . 4 ) . F in a l l y , w e d e s c r i b e a Z o oK e e p e r c l o n e o v e r D a p p l e ( § 6 . 5 ) .

. 1 C om p a r i s o n w i t h s h a r e d l o g s y s t em s

I n t h i s e x p e r im e n t , w e s h o w t h a t c e n t r a l i z e d s e q u e n c e r s i n e x i s t i n g s h a r e d l o g s y s t em s f u n d am e n t a l l y l im i t s c a la b i l i t y . S h a r e d l o g s y s t em s s u c h a s T a n g o [ 8 ] a n d v C o r f u [ 5 7 ] u s e a c e n t r a l i z e d s e q u e n c e r t o d e t e rm i n e a u n i q u e m o n o t o n i c s e q u e n c e n um b e r f o r e a c h a p p e n d . B a s e d o n i t s s e q u e n c e n um b e r , e a c h a p p e n d i s d e t e rm i n i s t i c a l l y r e p l i c a t e d o n a d i f f e r e n t s e t o f s e r v e r s . T h e s e q u e n c e r t h e r e f o r e b e c om e s a c e n t r a l i z e d p o i n t o f c oo r d i n a t i o n , e v e n w h e n r e q u e s t s e x e c u t e a g a i n s t d i f f e re n t a p p l i c a t i o n -l e v e l d a t a -s t r u c t u r e s o r s h a r d s . I n c o nt r a s t , D a p p l e a l l o w s a p p l i c a t i o n s t o n a t u r a l l y e x p r e s s t h e i r s h a r d i n g r e q u i r em e n t s v ) , w h i c h p a r t i t i o n s i t s s t a t e a c r o s s m u l t i p l e c o l o r s . E a c h A t om i cM a p s e r v e r i s a D a p p l e c l i e n t , a n d i s a f fi n i t i z e d w i t h a u n i q u e c o l o r ( c o r r e s p o n d i n g t o a l o g i c a l p a r t it i o n o f t h e A t om i cM a p ' s s t a t e ) . E a c h c l i e n t p e r f o rm s a c om b i n a t i o n o f s i n g l e p u t s a g a i n s t i t s l o c a l p a r t i t i o n a n d m u l t i -p u t s a g a i n s t i t s p a r t i t i o n a n d a r a n d om l y s e l e c t e d r em o t e p a r t i t i o n . F i g u r e8s h o w s t h e r e s u l t s o f t h e A t om i cM a p e xp e r im e n t . F o r d i f f e r e n t p e r c e n t a g e s o f m u l t i -p u t s i n t h e w o r k l o a d ( o n t h e x -a x i s ) , w e v a r y s y s t em s i z e a n d p l o t t h r o u g h p u t o n t h e y -a x i s . W e u s e b e tw e e n 8 a n d 1 6 c h a i n s e r v e r s i n D a p p l e ( d e p l o y e d w i t h o u t r e p l i c a t i o n s i n c e w e r a n i n t o E C 2 i n s t a n c e l im i t s ) . W e u s e 8 -b y t e k e y s a n d 8 -b y t e v a l u e s t o em u l a t e a w o r k l o a d w h e r e t h e A t om i cM a p a c t s a s a n i n d e x s t o r i n g p o i n t e r s t o a n e xt e r n a l b l o b s t o r e . K e y s f o r p u t o p e r a t i o n s a r e s e l e c t e d u n i f o rm l y a t r a n d om f r om a k e y s p a c e o f 1M k e y s .

F i g u r e 8 s h o w s t h a t u n d e r 0% m u l t i -s h a r d p u t s , t h r o u g h p u t s c a l e s l i n e a r l y f r om 1 t o 1 6 A t om i cM a p s e r v e r s . T h e t h r o u g h p u t j um p f r om 1 6 t o 3 2 s e r v e r s i s s l i g h t l y l e s s t h a n 2 x b e c a u s e w e p a c k tw o D a p p l e c l i e n t s p e r A t om i cM a p s e r v e r a t t h e 3 2 c l i e n t d a t a p o i n t ( d u e t o t h e E C 2 i n s t a n c e l im i t ) . A s t h e p e r c e n t a g e o f m u l t is h a r d p u t s i n c r e a s e s f r om 0 . 1% t o 1 0 0% , s c a l a b i l i t y a n d a b s o l u t e t h r o u g h p u t d e g r a d e g r a c e f u l l y . T h i s i s e x p e c t e d d u e t o t h e e x t r a c o s t o f e x e c u t i n g m u l t i -s h a r d p u t s ( e a c h r e q u i r e s a tw o -p h a s e m u l t i -c o l o r a p p e n d ) . I n F i g u r e 9 , w e h o s t a s i n g l e , u n p a r t i t i o n e d C RD TM a p o n fi v e a p p l i c a t i o n s e r v e r s ( i . e . , D a p p l e c l i e n t s ) ; w e l oc a t e e a c h i n a v i r t u a l r e g i o n w i t h i t s o w n D a p p l e c o p y , a l l r u n n i n g i n t h e s am e E C 2 r e g i o n . F o u r o f t h e s e s e r v e r s a r e w r i t e r s i s s u i n g p u t o p e r a t i o n s a t a c o n t r o l l e d a g g r eg a t e r a t e ( l e f t y -a x i s ) , w h i l e t h e fi f t h i s a r e a d e r i s s u i n g g e t o p e r a t i o n s o n t h e C RD TM a p . E a c h w r i t i n g s e r v e r u s e s f o u r w r i t e r p r o c e s s e s . T h e g e t s o b s e r v e s om e f r o nt i e r o f t h e u n d e r l y i n g D A G , a n d c a n t h e r e f o r e l a g b e h i n d b y a c e r t a i n n um b e r o f p u t s ( r i g h t y -a x i s ) , b u t a r e f a s t , l o c a l o p e r a t i o n s .

M i dw a y t h r o u g h t h e e x p e r im e n t , w e s p i k e t h e p u t l o a d o n t h e s y s t em ; t h i s d o e s n o t s l o w d o w n g e t o p e r a t i o n s a t t h e r e a d e r ( n o t s h o w n i n t h e g r a p h ) , b u t

i n s t e a d m a n i f e s t s a s s t a l e n e s s . o n e i s s u i n g p u t s a n d o n e i s s u i n g g e t s . W e m e a s u r e t h e l a t e n c y o f g e t s a n d p u t s ( y -a x i s ) , a g a i n s t t h e w a l l -c l o c k t im e t h e y a r e i s s u e d a t ( x -a x i s ) . T h e F u z z y L o g a b s t r a c t i o n -a n d i t s im p l em e n t a t i o n i n D a p p l e -e x t e n d s t h e s h a r e d l o g a p p r o a c h t o p a r t i a l o r d e r s , a l l o w i n g a p p l ic a t i o n s t o s c a l e l i n e a r l y w i t h o u t s a c r i fi c i n g t r a n s a c t i o n a l g u a r a n t e e s , o b t a i n a r a n g e o f c o n s i s t e n c y g u a r a n t e e s , a n d sw i t c h s e am l e s s l y b e tw e e n t h e s e g u a r a n t e e s w h e n t h e n e tw o r k p a r t i t i o n s a n d h e a l s . C r u c i a l l y , a p p l i c a t i o n s c a n a c h i e v e t h e s e c a p a b i l i t i e s i n h [ 3 ]Z l o g t r a n s a c t i o n a l k e y -v a l u e s t o r e . h t t p : / / n o a h d e s u . g i t h u b . i o / 2 0 1 6 / 0 8 / 0 2 / z l o gk v s t o r e -i n t r o . h t m l . [ 2 9 ]L AM POR T, L . T h e p a r t -t im e p a r l i am e n t . A CM T r a n s a c t i o n s o n C om p u t e r S y s t em s ( TO C S ) 1 6 ,2 ( 1 9 9 8 ) , 1 3 3 -1 6 9 . [ 6 0 ]Z HANG, I . ,S HARMA,N .K . ,S Z EK ER E S ,A . ,K R-I SHNAMUR THY , A . ,AND P OR T S, D . R . B u i l di n g c o n s i s t e n t t r a n s a c t i o n s w i t h i n c o n s i s t e n t r e p l ic a t i o n . I n A CM SO S P 2 0 1 5 .

[ 6 1 ]Z HANG,Y . ,P OW ER,R . ,Z HOU,S . ,S OVRAN,Y . , AGU I L ERA, M .K . , ANDL I , J . T r a n s a c t i o n c h a i n s : a c h i e v i n g s e r i a l i z a b i l i t y w i t h l o w l a t e n c y i n g e od i s t r i b u t e d s t o r a g e s y s t em s . I nA CM SO S P 2 0 1 3 .