A FAST IMPLEMENTATION OF PARALLEL SNAPSHOT
ISOLATION
UNA IMPLEMENTACIÓN RÁPIDA DE PARALLEL
SNAPSHOT ISOLATION
Bo ja A nau de Régil Basáñez
T abajo de Fin de G ado del G ado en Ingenie ía
In o má ica
Facul ad de In o má ica,
Uni e sidad Complu ense de Mad id
Junio 2020
Di ec o : Ma ia Vic o ia López López
Co-di ec o : Alexey Go sman
Con en s
Acknowledgemen s i
Abs ac
Resumen i
1. In oduc ion 1
1.1. Mo i a ion..................................... 1
1.2. Goals........................................ 2
1.3. Wo kPlan..................................... 3
1.4. Documen S uc u e ............................... 3
1.5. Sou ces and Reposi o ies . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.6. Rela edP og amCou ses ............................ 4
2. P elimina ies 5
2.1. No a ion...................................... 5
2.1.1. Objec s and Replica ion . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.1.2. T ansac ions................................ 5
2.1.3. His o ies.................................. 6
2.2. Consis encyModels................................ 6
2.2.1. ReadCommi ed(RC).......................... 7
2.2.2. Se ialisabili y (SER) . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
2.2.3. Snapsho Isola ion (SI) . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.2.4. Pa allel Snapsho Isola ion (PSI) . . . . . . . . . . . . . . . . . . . . 10
2.2.5. Non-Mono onic Snapsho Isola ion (NMSI) . . . . . . . . . . . . . . . 11
2.2.6. Anomaly Compa ison . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
3. The as PSI p o ocol 12
3.1. Consis encyGua an ees ............................. 12
3.2. O e iew and Sys em Model . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
3.3. Se e da as uc u es .............................. 14
3.4. P o ocolDesc ip ion ............................... 16
3.4.1. T ansac ion Execu ion . . . . . . . . . . . . . . . . . . . . . . . . . . 16
3.4.2. T ansac ion Te mina ion . . . . . . . . . . . . . . . . . . . . . . . . . 20
3.5. Consis ency T adeo s and Read Abo s . . . . . . . . . . . . . . . . . . . . . 23
ii
4. Implemen a ion and E alua ion 26
4.1. Implemen a ion.................................. 26
4.2. E alua ion..................................... 27
4.2.1. Pe o mance & Scalabili y Limi s . . . . . . . . . . . . . . . . . . . . 28
4.2.2. Abo Ra io................................ 31
5. Rela ed Wo k 35
6. Conclusions and Fu u e Wo k 37
6.1. Conclusions .................................... 37
6.2. Fu u eWo k.................................... 37
A. Se ialisable and Read Commi ed P o ocols 39
A.1.Se ialisabili y ................................... 39
A.2.ReadCommi ed ................................. 44
Bibliog aphy 50
iii
Acknowledgemen s
To my ad iso s Ma ia Vic o ia López López a Uni e sidad Complu ense de Mad id, and
Alexey Go sman and Manuel B a o a he IMDEA So wa e Ins i u e, o hei guidance
and suppo , and o gi ing me he oppo uni y o wo k along hem.
I also hank Ch is ophe Meiklejohn, who allowed me o wo k wi h him, and ga e me
he oppo uni y o disco e he IMDEA So wa e Ins i u e. To my colleagues a IMDEA,
hank you o gi ing me ad ice, and o o e ing a helping hand.
Finally, o my gi l iend Paula, and my amily, o hei lo e, pa ience and suppo .
i
Abs ac
Mos dis ibu ed da abase sys ems o e weak consis ency models in o de o a oid he
pe o mance penal y o coo dina ing eplicas. Ideally, dis ibu ed da abases would o e
s ong consis ency models, like se ialisabili y, since hey make i easy o e i y applica ion
in a ian s, and ee p og amme s om wo ying abou concu ency. Howe e , implemen ing
and scaling sys ems wi h s ong consis ency is di icul , since i usually equi es global
communica ion. Weak models, while easie o scale, impose on he p og amme s he need o
eason abou possible anomalies, and he need o implemen con lic esolu ion mechanisms
in applica ion code.
Recen ly p oposed consis ency models, like Pa allel Snapsho Isola ion (PSI) and Non-
Mono onic Snapsho Isola ion (NMSI), ep esen he s onges models ha s ill allow o
build scalable sys ems wi hou global communica ion. They allow compa able pe o mance
o p e ious, weake models, as well as simila abo a es. Howe e , bo h models s ill p o ide
weake gua an ees han se ialisabili y, and may p o e di icul o use in applica ions.
This wo k shows an app oach o b idge he gap be ween PSI, NMSI and s ong con-
sis ency models like se ialisabili y. I in oduces and implemen s as PSI, a consis ency
p o ocol ha allows he use o selec i ely en o ce se ialisabili y o ce ain execu ions,
while e aining he scalabili y p ope ies o weake consis ency models like PSI and NMSI.
In addi ion, i ea u es a comp ehensi e e alua ion o as PSI in compa ison wi h o he con-
sis ency p o ocols, bo h weak and s ong, showing ha as PSI o e s be e pe o mance
han se ialisabili y, while e aining he scalabili y o weake p o ocols.
Keywo ds
Consis ency models, T ansac ions, Pa allel Snapsho Isola ion, Non-Mono onic Snapsho
Isola ion, Concu ency con ol.

Resumen
La mayo ía de las bases de da os dis ibuidas o ecen modelos de consis encia débil,
con la inalidad de e i a la penalización de endimien o que supone la coo dinación de las
dis in as éplicas. Idealmen e, las bases de da os dis ibuidas o ece ían modelos de con-
sis encia ue e, como se ialisabili y, ya que acili an la e i icación de los in a ian es de
las aplicaciones, y pe mi en que los p og amado es no deban p eocupa se sob e posibles
p oblemas de concu encia. Sin emba go, implemen a sis emas escalables que con modelos
de consis encia ue e no es ácil, pues equie en el uso de comunicación global. Sin em-
ba go, aunque los modelos de consis encia más débiles pe mi en sis emas más escalables,
imponen en los p og amado es la necesidad de azona sob e posibles anomalías, así como
implemen a mecanismos de esolución de con lic os en el código de las aplicaciones.
Dos modelos de consis encia p opues os ecien emen e, Pa allel Snapsho Isola ion (PSI)
y Non-Mono onic Snapsho Isola ion (NMSI), ep esen an los modelos más ue es que pe -
mi en implemen aciones escalables sin necesidad de comunicación global. Pe mi en, a su
ez, implemen a sis emas con endimien os simila es a aquellos con modelos más débiles,
a la ez que man ienen asas de cancelación de ansacciones simila es. Aun así, ambos
modelos no log an o ece las mismas ga an ías que se ialisabili y, po lo que pueden se
di íciles de usa desde el pun o de is a de las aplicaciones.
Es e abajo p esen a una p opues a que busca aco a la dis ancia en e modelos como
PSI y NMSI y modelos ue es como se ialisabili y. Con esa inalidad, es e abajo p esen a
as PSI, un p o ocolo de consis encia que pe mi e al usua io ejecu a de mane a selec i a
ansacciones se ializables, e eniendo a su ez las p opiedades de escalabilidad p opias
de modelos de consis encia débiles como PSI o NMSI. Además, es e abajo cuen a con
una e aluación exhaus i a de as PSI, compa ándolo con o os p o ocolos de consis encia,
an o ue es como débiles. Se mues a así que as PSI log a un endimien o mayo que
se ialisabili y sin po ello enuncia a la escalabilidad de p o ocolos más débiles.
Palab as cla e
Modelos de Consis encia, T ansacciones, Pa allel Snapsho Isola ion, Non-Mono onic
Snapsho Isola ion, Con ol de Concu encia.
i
Chap e 1
In oduc ion
1.1. Mo i a ion
Mode n cloud applica ions a e cha ac e ised by being globally a ailable, and use s expec
o use he se ices p o ided by hese applica ions wi h low la ency, and in a eliable manne .
To sa is y hese equi emen s, p og amme s usually eso o dis ibu ed da abases and
s o age, ha allow o pa i ion applica ion da a and place i geog aphically close o he
use s ha need i . Fo example, a social media si e would place da a ela ed o Eu opean
use s on da a cen e s loca ed in he same egion, and he same o use s in he Uni ed
S a es. Unde his design, howe e , hose use s eques ing da a om ano he egion would
su e om high la ency, as eques s a el ac oss di e en geog aphical egions. To his
end, hese da a pa i ions a e also eplica ed ac oss di e en geog aphical egions, o ensu e
bo h low la ency o all kinds o use eques s, and aul ole ance, which allows applica ions
o ensu e a smoo h ope a ion e en i an en i e egion goes o line.
These app oaches, howe e , add signi ican complexi y o he design and implemen a ion
o applica ions and he unde lying da abases. The p esence o mul iple eplicas aises he
ques ion o how o keep hem consis en , ha is, e lec ing an uni ied e sion o he da a
hey con ain. T adi ional mechanisms o deal wi h da abase consis ency p o e ha de o im-
plemen in e icien ways in dis ibu ed da abases. Fo example, ansac ions should sa is y
a se o desi able p ope ies, commonly known as ACID: A omici y, Consis ency, Isola ion,
and Du abili y. These p ope ies allow p og amme s o eason abou concu ency as a se
o isola ed, a omic ope a ions, bu in geo-dis ibu ed scena ios i equi es he coo dina ion
o mul iple eplicas in o de o apply hei upda es.
The usual app oach o b idge hese p oblems in ol es elaxing he consis ency gua an ees
ha da abases o e p og amme s [40]. Indeed, he CAP Theo em [16,23] p o es i is
impossible o build applica ions ha con inue ope a ing in he p esence o ne wo k pa i ions
wi hou sac i icing consis ency gua an ees. Howe e , he deg ee o which hese gua an ees
can be elaxed o e s a ade-o : on he one hand, weak consis ency allows o build scalable
applica ions wi hou loss o a ailabili y, bu p o es di icul o eason abou gi en ha i
allows non-se ialisable beha iou s called anomalies, and o ces p og amme s o deal wi h
1
inconsis en da a a he applica ion le el; on he o he hand, s eng hening consis ency
gua an ees can educe pe o mance and hu applica ion a ailabili y, while being much easie
o eason abou .
Un il ecen ly, sys ems ha o e ed weak consis ency gua an ees did no p o ide ans-
ac ions (e.g. Dynamo [20]). In he ecen yea s, howe e , a la ge numbe o ansac ional
consis ency models ha e been p oposed o la ge-scale da abases [6,10,32,39]. Gi en he
p oli e a ion o di e en consis ency models, i can be ha d o choose which one is app op i-
a e o a pa icula applica ion, as i equi es he p og amme o hink abou he possible
anomalies ha can a ise du ing an execu ion and abou how hey can in e e e wi h applica-
ion logic. Ideally, one would wan o un all applica ions unde s ong consis ency models,
like se ialisabili y [15], as p og amme s only need o check ha applica ion in a ian s hold as
i ansac ions execu ed one a e he o he , wi hou wo ying abou concu ency. Un o u-
na ely, gua an eeing a se ialisable execu ion in dis ibu ed da abases is no possible wi hou
equi ing global communica ion, which inc eases la ency and limi s a ailabili y [23].
This lea es he p og amme s wi h he esponsibili y o choosing an adequa e consis ency
model o hei applica ions. Howe e , p og amme s o en lack echniques o ensu e ha
a gi en consis ency model is sa e o use o a pa icula applica ion. One way o add ess
his p oblem is o ely on he no ion o applica ion obus ness [14,22]: an applica ion
is obus agains a pa icula consis ency model i i beha es in he same way whe he
using a da abase p o iding his model o se ialisabili y. When an applica ion is obus ,
he p og amme can ake ad an age o he scalabili y p ope ies o a weak consis ency
model wi hou paying he p ice o anomalous beha iou s. P e ious wo k has ocused on
s a ic analysis o applica ions [29,34], which le p og amme s know which pa s o hei
applica ions a e suscep ible o anomalies. In hese cases, p og amme s can selec i ely un
ansac ions unde se ialisabili y: Feke e e al. [21,22] p opose se e al echniques ha allow
ansac ions execu ing unde snapsho isola ion (SI) [13] o exhibi se ialisable beha iou s,
e ec i ely making hem equi alen o ansac ions unning unde se ialisabili y.
Mos ecen ly, Be na di and Go sman [14] p oposed a way o check he obus ness o
pa allel snapsho isola ion (PSI)1[39], which elaxes he consis ency gua an ees o snapsho
isola ion o allow mo e e icien implemen a ions o dis ibu ed da abases. PSI is also he
s onges model ha is weake han SI [17], hus i is an ob ious candida e o in es iga e
i s impac on he co ec ness o applica ions. Al hough he e a e se e al implemen a ions
ha gua an ee PSI [6,33,39], none o hem we e implemen ed wi h he ocus on explo ing
he ela ion be ween PSI and applica ion obus ness.
1.2. Goals
The goal o his wo k is o help p og amme s b idge he gap be ween weak and s ong
consis ency p o ocols, wi hou sac i icing applica ion co ec ness. To ha end, as PSI is
p oposed, an implemen a ion o Pa allel Snapsho Isola ion ha allows o selec i ely en-
o ce se ialisabili y o ansac ions h ough ca e ul g ouping o da abase objec s in o en i y
1Also known as non-mono onic snapsho isola ion [6]. This is discussed in §2.2.5.
2
g oups [11]: ansac ions accessing objec s in he same g oup execu e as i hey we e un-
ning unde a sys em gua an eeing SI (ins ead o he weake PSI). Following he echniques
p oposed by Feke e e al. [22], hese ansac ions can be u he cons ained so ha hey
execu e as i unning unde se ialisabili y.
As such, he con ibu ions o his wo k a e:
A hyb id consis ency p o ocol ha allows mixing Snapsho Isola ion wi h Pa allel
Snapsho Isola ion, by elying on en i y g oups. This p o ocol allows p og amme s o
combine he scalabili y o Pa allel Snapsho Isola ion wi h he amilia i y and in u-
i i eness o well-known consis ency models like Snapsho Isola ion and se ialisabili y.
A comp ehensi e e alua ion o he p oposed p o ocol, and a compa ison agains al e -
na i e implemen a ions o bo h weak and s ong consis ency models.
An exposi ion o he d awbacks and ade-o s o he p o ocol, and a discussion o how
hei impac can be minimised.
1.3. Wo k Plan
The wo k ca ied ou o his p ojec was di ided in he ollowing phases:
Explo e p e ious con ibu ions. I ’s necessa y o ge amilia ised wi h exis ing e mi-
nology, as well as p e ious wo k and implemen a ions.
Delimi p ojec scope. A e ha ing he necessa y knowledge o ca y ou he wo k,
he limi s and speci ic con ibu ions o he wo k a e es ablished. In addi ion, he
hypo heses ha he inal implemen a ion should alida e a e p oposed.
Implemen a ion phase. A e se ing clea objec i es and miles ones, he bulk o he
implemen a ion is done. Th oughou his phase, es ing and alida ion o he so wa e
is done, bo h wi h uni es s and wi h model checking echniques.
Benchma k and alida ion. Wi h he implemen a ion comple e, ep esen a i e bench-
ma ks a e designed, as well as scena ios o alida e he pe o mance o he imple-
men a ion. The esul s a e used alida e p e ious hypo heses, and also amed in he
con ex o he exis ing li e a u e.
1.4. Documen S uc u e
The es o his documen is s uc u ed as ollows. Chap e 2p o ides an o e iew o
p e ious wo k and he s a e o he a wi h ega ds o ele an consis ency models, as well
as basic no ions ha will be used h oughou his documen . Chap e 3in oduces as PSI,
3
2.2.4. Pa allel Snapsho Isola ion (PSI)
Pa allel Snapsho Isola ion (PSI), p oposed by So an e al. [39], is a consis ency model
aimed a sol ing he scalabili y limi s o classical Snapsho Isola ion in geo- eplica ed sys-
ems. While concu en con lic ing ansac ions a e no allowed, PSI allows non-con lic ing
ansac ions o exhibi a ela i e commi o de ha a ies be ween eplicas. This means ha
PSI can p opaga e ansac ions o eplicas in causal o de , sides epping ano he scalabili y
limi o SI.
Howe e , allowing di e en commi o de s o non-con lic ing ansac ions a di e en
eplicas (o si es) makes PSI suscep ible o he Long Fo k anomaly [39]. Conside he
his o y depic ed in Figu e 2.3. I ansac ions T4and T5execu e in di e en eplicas, hey
a e allowed o obse e di e en commi o de s o T2and T3.
4(y1)
2(x1).w2(x2).c2
3(y1).w3(y3).c3
5(y3).c5
4(x2).c4
5(x1)
T2
T3
T4
T5
w1(x1).w1(y1).c1
T1
Figu e 2.3:Example o a his o y showing he Long Fo k anomaly. T ansac ion T4obse es
T1T2T3while T5obse es T1T3T2.
De ini ion 2.6 (Long Fo k).ALong Fo k occu s whene e ansac ions a e able o obse e
di e en commi o de s o p e ious non-con lic ing upda e ansac ions.
Like SI, PSI exhibi s base eshness [8]: a ansac ion Tis limi ed o ead only e sions
o objec s w i en by ansac ions ha commi ed be o e Ts a ed. In he geo- eplica ed
scena ios ha PSI is mean o add ess, his limi a ion leads o a high numbe o s ale da a
eads. Conside he example o wo si es s1and s2sepa a ed by a high la ency link: i a
ansac ion s a s in s1and subsequen ly ies o ead an objec loca ed a s2, i migh be he
case ha he e sion i is o ced o ead due o base eshness has al eady been o e w i en
by o he ansac ions. Saeida A dekani e al. [38; Theo em 4] p o e ha base eshness
equi es eplicas ha do no eplica e da a accessed by a ansac ion T o coo dina e in
o de o commi T, which esul s in lowe sys em pe o mance and limi s scalabili y. Indeed,
he o iginal implemen a ion ad anced by So an e al. communica es wi h all he eplicas
in he sys em [39].
10

2.2.5. Non-Mono onic Snapsho Isola ion (NMSI)
The Non-Mono onic Snapsho Isola ion (NMSI) consis ency model also alle ia es he
o al commi o de scalabili y p oblem in classical Snapsho Isola ion. NMSI was p oposed
by Saeida A dekani e al. [6] as an imp o emen o e he p e iously desc ibed Pa allel
Snapsho Isola ion model, by exhibi ing o wa d eshness: a ansac ion Tis allowed o
ead e sions w i en by ansac ions ha commi ed a e Ts a ed, as long as hose
eads o m a causally consis en snapsho . A ansac ion Tobse es a causally consis en
snapsho i all he e sions ead by Ta e w i en by i s di ec causal dependencies, i.e. i a
ansac ion Tipe o ms i(xj)such ha i depends on Tj, hen he e’s no such wk(xk)such
ha Tj/Tk/Ti.
In spi e o his, he se o possible anomalies p oduced by bo h Pa allel Snapsho Isola ion
and Non-Mono onic Snapsho Isola ion a e he same, as can be seen in Figu e 2.4. In
addi ion, bo h models can be p o ed o be equi alen , as shown by A. Ce one (2016, pe sonal
communica ion wi h he au ho ), wi h he only di e ence being he choice o he concu ency
con ol algo i hm.
2.2.6. Anomaly Compa ison
Figu e 2.4 summa ises he consis ency models e iewed, oge he wi h he anomalies
ha hey allow.
Anomalies Consis ency Models
SER SI PSI NMSI RC
Di y W i e x x x x x
Di y Read x x x x x
Non-Repea able Read x x x x X
Los Upda e x x x x X
W i e Skew x X X X X
Long Fo k x x X X X
Figu e 2.4:Anomaly Compa ison o Consis ency Models (x:disallowed, X:allowed).
Adap ed om Saeida A dekani e al. [6].
11
Chap e 3
The as PSI p o ocol
This chap e desc ibes as PSI, a ansac ional p o ocol ha implemen s Pa allel Snap-
sho Isola ion and allows s onge consis ency gua an ees o ansac ions accessing objec s
inside en i y g oups. The chap e begins wi h an o e iew o wha en i y g oups a e, and
by explaining he consis ency gua an ees o as PSI o ansac ions execu ing bo h wi hin
and ac oss di e en g oups. I ollows wi h a summa y o how he di e en pa icipan s o
he p o ocol in e ac wi h each o he , and wi h a desc ip ion o he di e en da a s uc-
u es in ol ed. Nex , i shows how he p o ocol is s uc u ed by going o e he execu ion
o a ansac ion. The chap e concludes wi h a discussion o he possible d awbacks o he
design.
3.1. Consis ency Gua an ees
The as PSI p o ocol conside s a sys em in which objec s a e agg ega ed in en i y
g oups [11]. An en i y g oup σis de ined as a p ope pa i ion o objec s Obj. This means
ha wo p ope ies hold: (i) ∀σ, σ0=⇒σ∩σ0=∅, and (ii) ∀x∈Obj.∃σ. x ∈σ. The i s
p ope y says ha he se s o objec s co e ed by di e en en i y g oups a e disjoin , while
he second p ope y s a es ha any objec ha exis s in he sys em is pa o an en i y
g oup.
The goal o as PSI is as ollows: ansac ions ha only access objec s inside a single
en i y g oup should sa is y Snapsho Isola ion (SI), while ansac ions ha access objec s
ac oss en i y g oups should sa is y Pa allel Snapsho Isola ion (PSI). In ui i ely, i one has
a single en i y g oup ha encompasses e e y objec , any execu ion o as PSI is equi alen
o an execu ion unde Snapsho Isola ion, he eby p ecluding he Long Fo k anomaly. Con-
e sely, i one has an en i y g oup pe objec in he sys em, hen any execu ion o as PSI is
equi alen o an execu ion unde Pa allel Snapsho Isola ion. The decision o which objec s
o place in o di e en en i y g oups is le o he p og amme , who should ake applica ion
equi emen s in o accoun .
Recall om Sec ion 2.2.3 ha ansac ions execu ing unde SI a e only pa ially o de ed,
in con as wi h se ialisabili y, whe e hey a e o ally o de ed. Howe e , he equi emen o
12
ansac ions o ake mono onic s a and commi imes amps induces a o al commi o de
o ansac ions, e en o hose ha a e no in con lic wi h each o he . In he p esence o
di e en en i y g oups, his equi emen would equi e ansac ions o communica e wi h
e e y g oup in o de o de e mine a mono onic imes amp. In as PSI, his equi emen is
elaxed so ha ansac ions ha e mul iple, independen imes amps, one pe en i y g oup.
In o de o gua an ee Pa allel Snapsho Isola ion ac oss en i y g oups, he p o ocol
inco po a es he no ion o o wa d eshness [6], which allows a ansac ion T o ead e sions
o objec s w i en by ansac ions ha commi ed a e Ts a s. The as PSI p o ocol
accomplishes his by making a ansac ion T ix i s s a imes amp a a pa icula en i y
g oup only when T eads an objec om ha g oup. This also allows a ansac ion o
acqui e s a imes amps only a he g oups i eads om, hus a oiding coo dina ion wi h
o he g oups.
The as PSI p o ocol le e ages bo h app oaches o o e i s consis ency gua an ees: a
ansac ion is able o ead om e sions w i en by la e ansac ions as long as hose
eads o m a causally consis en snapsho . When a ansac ion Tpe o ms i s i s ead
ope a ion in an en i y g oup, i ixes a snapsho ha includes all he ansac ions ha
commi ed be o e T’s ead occu ed. As Tpe o ms u he ead ope a ions on o he en i y
g oups, he snapsho s ha T ixes a e es ic ed o e sions w i en by ansac ions ha
a e no causally dependen on he ansac ions ha Tal eady included in i s p e ious
snapsho s.
3.2. O e iew and Sys em Model
The p o ocol consis s o h ee componen s: clien p ocesses ha p o ide he sys em
in e ace o managing ansac ions, se e p ocesses ha handle he indi idual ope a ions o
ansac ions, and en i y g oups—managed by a se e —which s o e indi idual da a objec s.
Gi en ha en i y g oups p ope ly di ide he ange o objec s in o disjoin pa i ions, o he
emainde o his chap e he e m pa i ion is used as a sho hand o en i y g oup.
Bo h clien and se e p ocesses a e conside ed eliable and connec ed by eliable chan-
nels1. P ocesses communica e wi h each o he using an asynch onous message-passing sys-
em. Se e p ocesses a e deno ed as a se S={s1, . . . , sN}, and clien s as C={c1, . . . , cM}.
Da a objec s a e deno ed by a se Obj, spli in o Npa i ions, each s o ed by a se e p o-
cess. In addi ion, pa i ion(x) ep esen s he index o he pa i ion he objec xbelongs
o, such ha i is managed by se e spa i ion(x). Fo simplici y, i is assumed ha se e
p ocesses only manage a single pa i ion.
Clien s p o ide he ansac ional in e ace o he p o ocol h ough he s a , ead,
w i e and commi ope a ions. T ansac ions a e in e ac i e, i.e., when a ansac ion s a s,
he clien does no know which ope a ions i will pe o m in ad ance. In as PSI, he s a
and w i e ope a ions a e local o he clien . Clien s issue ead ope a ions o se e s, which
e u n he alues and me ada a associa ed wi h he objec s he clien eques ed. Clien s
1Faul - ole ance conce ns a e o hogonal o he p oblem add essed, al hough se e al app oaches a e
discussed in Chap e 5.
13
handle w i e ope a ions locally by s o ing he upda es in a bu e , called he w i e-se o a
ansac ion. A commi ime, he clien ac s a coo dina o o a wo-phase commi p o ocol
(2PC) [15], issuing p epa e and decide ope a ions o all he pa icipa ing se e s. The
w i en alues bu e ed locally a e ansmi ed o he se e s a p epa e ime, oge he
wi h he accumula ed me ada a o he objec s ha he clien ead. The decision o commi
o abo a ansac ion is aken based on his me ada a.
Se e s handle h ee ope a ions issued by clien s: ead,p epa e and decide. When a
se e handles ead ope a ions, i o wa ds he eques o he pa i ion esponsible o he
objec being eques ed. When ecei ing a p epa e eques o a ce ain ansac ion, he
se e checks o con lic s wi h o he ansac ions wai ing o be decided, which a e s o ed
in a commi queue. I he ansac ion con ained in he clien eques does no con lic , i
is added o he queue, and he se e eplies o he clien wi h a commi o e. I , on he
o he hand, he ansac ion is ound o be con lic ing, an abo o e is sen ins ead.
Pa i ions a e esponsible o ul illing ead eques s on behal o se e s, and o main-
aining causally consis en snapsho s on behal o he clien s. Pa i ions s o e mul iple e -
sions o an objec in acco dance wi h a mul i- e sion concu ency con ol p o ocol. When
execu ing a ead eques o an objec x, a pa i ion inds and e u ns he mos ecen
causally consis en e sion o x, along wi h some me ada a o he chosen e sion.
Each pa i ion s o es mul iple e sions o an objec ep esen ed by a uple h al, idi,
whe e al is he alue o a gi en e sion, and id is a logical iden i ie o he ansac ion
ha commi ed his e sion. This logical iden i ie is ep esen ed using e sion ec o s [35].
Such a ec o consis s o Nen ies, one o each pa i ion, s o ing a non-nega i e in ege .
Each en y id[i]in he ec o can also be ep esen ed by a pai (si, k), whe e kis he ac ual
alue o he i- h en y o he ec o . These pai s a e also called do s [12]. Ve sion ec o s
a e compa ed acco ding o he ollowing ela ion, showing when one ec o co e s mo e do s
han ano he : V1 V2⇐⇒ ∀i. V1[i]≤V2[i]. In addi ion, he e exis s a join ope a ion
on ec o s, aking hei en y-wise maximum, which will be deno ed by max om now on.
The se o all e sion ec o s is deno ed by Ve Vec o , and he ec o wi h all en ies se o
0by ~
0.
3.3. Se e da a s uc u es
Each se e simain ains i e main da a s uc u es, summa ised in Figu e 3.1. This
sec ion now ollows wi h a mo e de ailed explana ion o each o hem.
Las P ep is a coun e o he numbe o upda e ansac ions ha ini ia ed hei commi
phase a a gi en se e . When a ansac ion commi s a a se e si, i ge s assigned he alue
o he coun e as a sequence numbe k, which induces he commi o de o ansac ions a si.
A ansac ion compu es i s commi ec o Vc om hese sequence numbe s, such ha he
ec o ep esen s he se o do s {(si, k)|k≤Vc[i]}which iden i y he w i es by p e ious
ansac ions whose sequence numbe a siis no highe han Vc[i].
Ve sionLog is a mapping o objec s o a lis o e sions, called he da abase. As no ed
be o e, each e sion is a uple h al,Vcommisuch ha al is a alue and Vcomm is he
14
Da a S uc u es a a se e si
Las P ep In ege The numbe o upda e ansac ions ha ied o
commi a he se e .
Ve sionLog Map[Objec ,
Se [hValue al,Ve Vec o Vcommi]]
Da abase: a mapping om objec s o lis s o pai s
o a alue and he commi ec o o he ansac-
ion ha w o e i . The lis s a e o de ed by he
i- h componen o he commi ec o s.
Commi Log Sequence[hTx T, Ve Vec o Vagg i]Log o upda e ansac ions Tcommi ed a he
se e , o de ed by Vagg [i]. He e Vagg is he
agg ega e ec o o T: he join o he commi
ec o s o all ansac ions up o Tin Commi Log.
V o al Ve Vec o The join o he commi ec o s o all ansac ions
in Commi Log.
Commi Queue Sequence[hTx,pending,W i eSe i ∪
hTx,decided,W i eSe ,Ve Vec o i]
Queue con aining in o ma ion abou upda e
ansac ions ying o commi a he se e .
Figu e 3.1:Da a s uc u es used by se e s in he p o ocol. The o de s o en ies in
Commi Log,Ve sionLog and Commi Queue a e consis en wi h he commi o de o he as-
socia ed ansac ions. Componen s o a ious uples a e selec ed using he names gi en in
he igu e.
commi ec o o he ansac ion ha w o e al. The Ve sionLog a siis o de ed by he
i- h componen o he commi ec o o each e sion, which ollows he commi o de o
ansac ions a he se e . The mos ecen en y in he lis o he objec xis deno ed by
Ve sionLog[x].las .
Commi Log is an o de ed lis ha main ains a uple hT, Vagg i o each upda e ans-
ac ion ha commi ed a a se e , such ha Tis he iden i ie o a commi ed ansac ion
and Vagg is an agg ega e ec o . The agg ega e ec o ep esen s he join o he commi
ec o s o all he ansac ions up o Tin Commi Log. En ies in he log a sia e o ally
o de ed acco ding o he i- h en y o hei agg ega e ec o s, Vagg [i], which also ollows he
commi o de o ansac ions a he se e . These agg ega e ec o s a e s o ed o e iciency,
and a e used o compu e he snapsho o a ansac ion a he se e . The agg ega e ec o
o he las commi ed ansac ion is s o ed in V o al. Ini ially, he Commi Log con ains a
single placeholde en y h_,~
0i.
Finally, Commi Queue is an o de ed queue o ansac ions ying o commi upda es a
he se e . The queue has en ies o wo ypes. An en y hT,pending,WSimeans ha Tis
success ully p epa ed o commi a si, bu he inal decision on i is no ye known; WS is he
w i e-se o he ansac ion, con aining objec - alue pai s. An en y hT,decided,WS, V i
in he queue means ha Thas been decided o commi wi h a commi ec o V, bu i s
w i es ha e no ye been added o Ve sionLog. The o de o ansac ions in Commi Queue
ollows he commi o de a he se e .
15

3.4. P o ocol Desc ip ion
The p o ocol is now desc ibed in de ail by ollowing he execu ion o a ansac ion. This
sec ion begins by desc ibing how a ansac ion is ini ialised, along wi h he mechanism o
build a causally consis en snapsho . La e , i shows he mechanism o alida e and commi
a ansac ion.
3.4.1. T ansac ion Execu ion
The as PSI p o ocol uses op imis ic concu ency con ol, ha is, he execu ion o a
ansac ion is specula i e. Clien s ead objec s om se e s and bu e w i es locally. A he
end o he execu ion, he decision whe he o commi o abo a ansac ion is aken based
on he exis ence o con lic s wi h concu en ly execu ing ansac ions. Clien s execu ing a
ansac ion main ain a ansac ion con ex including se e al pieces o da a, summa ised in
Figu e 3.2 and explained below.
In he ollowing, he s eps aken by bo h clien s and se e s o execu e T e e o he
algo i hms in Figu es 3.3 and 3.4.
Con ex o a ansac ion Ta a clien ci
T.WS W i eSe W i e-se o T.
T.HasRead Vec o [Bool]Mapping showing whe he Thas ead a gi en pa i ion.
T.Vsnap Ve Vec o Snapsho ec o : de e mines snapsho s ixed a pa i ions T
has ead om and possible causal dependencies a all o he
pa i ions.
T.Vdep Ve Vec o Dependency ec o , ep esen ing all causal dependencies de-
eloped by Tdu ing i s execu ion.
Figu e 3.2:Da a s uc u es used in he ansac ion con ex , kep by he clien s in he
p o ocol. In he able, W i eSe =Se [hObjec ,Valuei]
When a clien s a s a ansac ion T, i i s ini ialises i s con ex (line 1). When a
ansac ion Tw i es a alue o an objec x(line 3), he clien bu e s his w i e in T’s
w i e-se ,T.WS, while disca ding any p e iously w i en alue o x.
1 unc ion s a ()
2 e u n new Tx(WS =∅,HasRead =~
⊥,Vsnap =~
0,Vdep =~
0);
3 unc ion w i e(T, x, )
4T.WS ←(T.WS {hx, _i})∪ {hx, i};
Figu e 3.3:Ini ialisa ion o a ansac ion and upda e o an objec xa clien ci.
When he ansac ion Tissues a ead ope a ion on an objec x(line 5), he clien i s
checks T.WS (line 6): i Thas al eady w i en o x, he alue s o ed in he w i e-se is
16
e u ned. O he wise, and assuming ha j=pa i ion(x), he clien sends a READREQUEST
message o he se e sj o e ch he alue o he objec (line 9).
When he ansac ion T eads an objec om a pa i ion j o he i s ime, he se e
sj ixes a snapsho o e sions om which i will se e all u u e eads by T. This snapsho
is de ined by an in ege k: i will include he e sions w i en by all he ansac ions ha
commi ed a he se e wi h a sequence numbe up o k. The clien keeps his in o ma ion
in he ansac ion con ex , by s o ing kin he j- h en y o a snapsho ec o T.Vsnap, and
by ma king he cu en pa i ion as ead in T.HasRead, a boolean mapping i s j- h en y
o >i T ead an objec om sj, and ⊥o he wise. I T.HasRead[j] = >, hen he ec o
T.Vsnap is equal o he join o he commi ec o s o all ansac ions commi ed a sjwi h
a sequence numbe no highe han Vsnap[j].
5 unc ion ead(T, x)
6i hx, i ∈ T.WS hen
7 e u n ;
8j←pa i ion(x);
9send READREQUEST(x, T.Vsnap, T.HasRead) o sj;
10 wai ecei e READRETURN(m) om sj;
11 i m=abo hen
12 h ow abo ;
13 else i m=h , Vdep,Vagg i hen
14 T.HasRead[j]← >;
15 T.Vdep ←max(T.Vdep,Vdep);
16 T.Vsnap ←max(T.Vsnap,Vagg );
17 e u n ;
18 when ecei ed READREQUEST(x, Vsnap,HasRead) om cj
19 i HasRead[i] hen
20 V←Vsnap;
21 else
22 wai un il V o al[i]≥Vsnap[i];
23 ←max{ ∈Commi Log | ∀j. HasRead[j] =⇒( .Vagg [j]≤Vsnap[j])};
24 i .Vagg [i]<Vsnap[i] hen
25 send READRETURN(abo ) o cj;
26 e u n;
27 V← .Vagg ;
28 e = max{ e ∈Ve sionLog | e .Vcomm[i]≤V[i]};
29 send READRETURN( e . al, e .Vcomm, V ) o cj;
Figu e 3.4:Local and emo e ead o objec x.
Thus, he en ies in he snapsho ec o o pa i ions ha Thas no ye ead om
17
T1
T2
ij k
(a)
T3
T4
T1
T2
ij k
(b)
T3
T4
Figu e 3.5:Illus a ions o he snapsho compu a ion. Ve ical lines depic he commi
o de a he co esponding pa i ions ( op o bo om) and ho izon al lines he cu -o s o
a ious snapsho s. A ows be ween pa i ions depic causal dependencies.
delimi all he possible causal dependencies Tmay de elop a hese pa i ions.
Bo h T.Vsnap and T.HasRead a e supplied by he clien when issuing a ead ope a ion
on objec x, by using hem as pa ame e s o he READREQUEST message sen o a se e si.
When he se e ecei es his message (line 18), i i s checks, using he HasRead mapping,
i he ansac ion has ead om i be o e (line 19). In his case, he snapsho is de e mined
by Vsnap[i], and he se e e u ns he la es e sion e o he objec xw i en by a
ansac ion in he snapsho , i.e., wi h a sequence numbe no highe han Vsnap[i](line 28).
This e sion is de e mined by examining he i- h en y o he commi ec o s in Ve sionLog.
The se e hen eplies o he clien wi h a READRETURN message con aining he alue o he
chosen e sion and i s associa ed e sion ec o , as well as he unmodi ied snapsho ec o
p o ided by he clien : since he se e used a p e iously ixed snapsho , no upda es o he
ec o a e equi ed.
In he case when he clien eads om he se e si o he i s ime (line 21), i is
necessa y o ix he snapsho o he ansac ion Ta his se e . Choosing a sui able
snapsho is complica ed by he ac ha ansac ions a e allowed o be in e ac i e— ha is,
i is no know in ad ance which objec s a ansac ion will ead in he u u e. The snapsho
is hence ixed in such a way ha any la e ead om his snapsho will be causally consis en
wi h any o he ead om he snapsho s ha Thas al eady ixed, as speci ied by HasRead
and Vsnap. To ensu e his, he selec ed snapsho has o sa is y wo equi emen s, depic ed
in Figu e 3.5.
On he one hand, he snapsho canno be oo esh. Fo example, suppose a ansac ion
T1 ha w o e o pa i ion jis excluded om he snapsho chosen by Ta j. Then, he
snapsho chosen by Ta pa i ion icanno con ain T1, no any o he ansac ion ha
causally depends on i , like T2(Figu e 3.5a). I he snapsho chosen by Tincluded T2,
i would be able o ead some o T2’s w i es a i, he eby o cing T o ead he w i es by
T2’s causal dependencies, including T1; bu Tcanno see hese w i es, because i excluded
18
hem om he snapsho a pa i ion j. Thus, when building he snapsho , he se e needs
o ake in o accoun he snapsho s aken by Ta he pa i ions i al eady ead; he se e
selec s he longes p e ix o Commi Log ansac ions, such ha hei w i es—and he ones by
hei causal dependencies—a e included in T’s p e ious snapsho s. This p e ix is deno ed
by (line 23), and is compu ed using he Vagg ec o included in each o he en ies o
Commi Log, summa ising he causal dependencies o all ansac ions up o a gi en eco d
in he log. Thus, he snapsho a siincludes all ansac ions wi h sequence numbe s up o
.Vagg [i].
On he o he hand, he snapsho selec ed canno be oo s ale. Con inuing wi h he
p e ious example, i a ansac ion T3is included in he snapsho aken by Ta some
pa i ion k, hen he snapsho o Ta pa i ion ihas o include he w i es by T3and i s
causal dependencies, e.g., he ansac ion T4in Figu e 3.5a. The snapsho ec o T.Vsnap
summa ises he upda es o he ansac ions (and o i s causal dependencies) included in he
snapsho s ixed by T. Thus, a e de e mining he app op ia e snapsho in line 23, he se e
sichecks ha his snapsho co e s ansac ions wi h sequence numbe s a iup o Vsnap[i]
(line 24). To maximise he chances o passing his check, be o e allowing a ansac ion T o
p oceed wi h a ead, he se e siwai s un il he w i es om he p e ix up o Vsnap[i]ha e
been inco po a ed in o i s s a e (line 22).
I may be he case ha i ’s impossible o sa is y bo h o he abo e equi emen s when
selec ing a snapsho ; e.g., in he si ua ion illus a ed in igu e 3.5b. Assuming ha he
ansac ion Thas ixed a alid snapsho a jand k, i is impossible o build a consis en
snapsho a pa i ion i; gi en ha Tincluded T3a pa i ion k, i is o ced o ead T4’s
w i es a i. A he same ime, because i excluded T1 om he snapsho a j,Tcan’ ead
he w i es by T2a i. In his case, wi hou he second equi emen , he se e siwould build
a snapsho excluding bo h T2and T4, iola ing T’s causal dependency on T3. In his case
he se e sends o he clien a READRETURN message wi h a special alue abo (line 25),
which will cause he clien o abo he ansac ion (line 12).
Once he se e ixes a new snapsho , i selec s he mos ecen e sion o he objec x,
de ined by e.Vagg [i](line 28), o e u n o he clien . The se e eplies wi h a READRETURN
message, ca ying a iple o he alue o he objec , i s associa ed e sion ec o , and he
agg ega e ec o o e.Vagg , summa ising he causal dependencies o all he ansac ions in
he snapsho . When he clien ecei es he message (line 13), i i s se s he j- h en y o
T.HasRead o >, o indica e ha Thas ead an objec a pa i ion j, and joins he e u ned
agg ega e ec o o T.Vsnap. The clien also joins he commi ec o associa ed wi h he
e sion ead o a dependency ec o T.Vdep, which ep esen s all causal dependencies de-
eloped by Tdu ing i s execu ion. This ensu es ha , upon eading a e sion o objec x,
Twill causally depend on he ansac ion T0 ha w o e ha e sion o x, along wi h he
causal dependencies o T0.
Conside he example depic ed in Figu e 3.6a, which shows a comple e execu ion o he
p o ocol. Clien c1issues a pai o ead eques s o se e s s1and s2. In u n, hese se e s
eply wi h he alue o he objec eques ed, along wi h i s e sion ec o and he new
agg ega e ec o o he ansac ion, deno ed by Vdep and Vagg a he bo om. Since his
is he i s ead eques issued on behal o his ansac ion, he se e s1 eplies wi h i s
19
Chap e 4
Implemen a ion and E alua ion
This chap e o e s an e alua ion ha a emp s o explo e he o e head o as PSI’s
s ong consis ency model compa ed o he weak consis ency o Read Commi ed. The
e alua ion also shows how as PSI is able o ou pe o m a p o ocol implemen ing he s onge
se ialisabili y consis ency model. Finally, i e alua es he scalabili y o as PSI as mo e
se e s and pa i ions a e added o he sys em, and discusses some o he limi a ions o he
p o ocol.
4.1. Implemen a ion
The implemen a ion o as PSI consis s o a clien -side lib a y [1] and a se e [3], he
la e being w i en as a plug-in ansac ional p o ocol o An ido e [5], a e e ence pla o m
o e alua ing consis ency p o ocols. Bo h he clien lib a y and he se e a e w i en in
he E lang p og amming language, wi h a o al o 6K lines o code. The An ido e pla -
o m p o ides a key- alue da abase, suppo s bo h in-memo y and disk-based s o age, and
implemen s ull eplica ion. Fo simplici y, he implemen a ion o as PSI only suppo s in-
memo y s o age, and lacks a eplica ion mechanism. The clien -side lib a y communica es
wi h he se e using Google’s P o ocol Bu e s [2]. To enhance ne wo k e iciency, clien
messages a e ansmi ed in pe iodic ba ches o he se e s.
To alida e he esul s o he e alua ion, wo al e na i e p o ocols a e also implemen ed,
sa is ying he Read Commi ed and se ialisabili y consis ency models, called nai eRC and
nai eSER, espec i ely. Bo h a e buil on op o he o iginal as PSI implemen a ion and
a e as e icien as possible. The pseudocode o bo h implemen a ions can be ound in
Appendix A.
As he implemen a ion o as PSI doesn’ a ge eplica ed scena ios, his documen
e ains om compa ing agains p e ious implemen a ions o Pa allel Snapsho Isola ion.
Since he p o ocols and implemen a ions as desc ibed in he li e a u e a e in luenced by
he choice o eplica ion mechanisms, a comp ehensi e e alua ion o as PSI agains o he
implemen a ions o PSI is de e ed o u u e wo k, which could explo e inco po a ing ei he
pa ial o ull eplica ion o as PSI.
26

Gi en ha as PSI equi es he use o mul iple e sions pe objec , i becomes necessa y
o p e en an unbounded g ow h o he numbe o e sions in he Ve sionLog da abase, and
in he numbe o en ies in he pe -pa i ion Commi Log. To ha end, a simple ga bage
collec ion mechanism in he implemen a ion ensu es a ixed numbe o e sions, and egula ly
p unes he oldes e sions om he s a e o a pa i ion.
4.2. E alua ion
This sec ion e alua es he pe o mance o as PSI using se e al wo kloads inspi ed by he
Yahoo! Cloud Se ing Benchma k (YCSB) [18], modi ied o gene a e ansac ional wo k-
loads [6,9]. The implemen a ion o Read Commi ed is used as a baseline o compa ison,
in o de o show he maximum possible pe o mance. Figu e 4.1 desc ibes he wo kloads
used. All expe imen s a e un on a clus e consis ing o machines unning Debian 4.19.67-2
(S e ch) wi h 3.80 GHz o 4.70 GHz In el Xeon p ocesso s wi h six co es, 32 GB o RAM,
and one gigabi ne wo k po . The clus e is pa i ioned in up o h ee di e en si es, wi h
ou se e machines and ou clien machines a each si e. Thus, he e is no sha ed memo y
be ween clien s and se e s, as i clien s we e ac ing as p oxies in he same da a cen e as
se e s. Since all he machines a e loca ed in he same local ne wo k, he c Linux command
is used o a i icially add la ency be ween si es.
In all benchma ks, he sys em is loaded wi h one million andom keys and 256-by e alues
p io o ecei ing any ope a ions om he clien s. Pa i ions a e dis ibu ed uni o mly ac oss
se e s, such ha a se e migh be esponsible o mul iple pa i ions. Keys a e mapped
o pa i ions using consis en hashing [30], wi h clien s being awa e o he dis ibu ion o
keys o pa i ions and se e machines. Thus, clien s can di ec ly add ess he co ec se e
and pa i ion o a speci ic key. Each clien machine spawns mul iple concu en h eads
ha execu e ansac ions and communica e wi h se e s in a closed-loop ashion. When
ansac ions ead mo e han one objec , clien s pe o m hose ope a ions se ially. Fo he
expe imen s ha in ol e mo e han one si e, he la ency be ween si es is o 10 ms.
Key Selec ion Dis ibu ion Ope a ions
Read-Only T an. Upda e T an.
B Uni o m 4 Reads 3 Reads, 1 Upda e
C Uni o m 2 Reads 1 Read, 1 Upda e
D Uni o m 3 Reads 3 Reads, 1 Upda e
E Uni o m 3 Reads 3 Reads, 3 Upda es
Figu e 4.1:T ansac ional YCSB Wo kload Types.
27
●●●
●
●●
●
●
●●
●
90% Read−only T ansac ions
80% Read−only T ansac ions
70% Read−only T ansac ions
0 250 500 750 1,000 1,250 1,500 1,750 2,000 0 250 500 750 1,000 1,250 1,500 1,750 2,000 0 250 500 750 1,000 1,250 1,500 1,750 2,000
0
5
10
15
20
25
0
5
10
15
20
25
0
5
10
15
20
25
Th oughpu (K ps)
Te mina ion La ency o Upd . xn (ms)
Wo kload C on 3 si es
●
nai eSER as PSI nai eRC
Figu e 4.2:Compa ison o h oughpu and e mina ion la ency o upda e ansac ions.
4.2.1. Pe o mance & Scalabili y Limi s
Pe o mance. The i s expe imen se es o in es iga e he o e all pe o mance p o ile o
he implemen a ions. The h oughpu and la ency o he di e en p o ocols is measu ed and
compa ed as he numbe o upda e ansac ions inc eases, while keeping he numbe o si es
cons an . Fo his expe imen , he numbe o concu en clien h eads a ies such ha he
esou ces o he CPU ne e sa u a e. The aim is o explo e he o e all o e head o as PSI
in compa ison wi h nai eRC, as well as he pe o mance bene i s i o e s in compa ison
wi h nai eSER. Figu e 4.2 shows he esul s o using Wo kload C and h ee si es, wi h 64
pa i ions uni o mly dis ibu ed ac oss si es. I measu es he e mina ion la ency o upda e
ansac ions (i.e., he amoun o ime spen on he alida ion o a ansac ion) as he a io
o ead-only o upda e ansac ion anges om 90%/10% o 70%/30% (le o igh ). Since
he la ency is measu ed in he clien , i only e lec s he amoun o ime spen on he p epa e
phase o he commi alida ion, as he clien does no need o wai un il he changes o a
ansac ion a e commi ed o he pa i ion s a e.
T ansac ions as execu ed by nai eRC need minimal synch onisa ion du ing i s commi
phase, and no synch onisa ion a all du ing ead ope a ions. This is e lec ed in i s high
pe o mance, wi h he alida ion o upda e ansac ions as he only bo leneck in he sys em.
Thus, as he p opo ion o upda e ansac ions inc eases, he impac on o e all h oughpu
is p onounced, d opping by as much as 20%.
Fo bo h nai eSER and as PSI, ead ope a ions om a ansac ion Tmus wai un il
he causal dependencies o Tcommi a a pa icula pa i ion, bounded in he wo s case
by he maximum la ency ac oss si es. In addi ion, ead ope a ions accessing he same
pa i ion su e om ha ing o synch onise while ixing a snapsho , as he implemen a ion
o Commi Log is no h ead-sa e. These wo sho comings explain he o e all low h oughpu
in compa ison wi h nai eRC. Ne e heless, bo h implemen a ions exhibi s able pe o mance
as he p opo ion o upda e ansac ions inc eases.
By compa ing as PSI wi h nai eSER, one can obse e ha he la e implemen a ion
is limi ed by i s need o alida e e e y ansac ion, in compa ison wi h as PSI, which only
alida es upda e ansac ions. In addi ion, he weake consis ency model o e ed by as PSI
28
allows i o ou pe o m nai eSER in all cases by app oxima ely 150%, while showing simila
la encies.
Scalabili y. The nex expe imen explo es he o e all scalabili y o as PSI, by examining
how he maximum pe o mance o each p o ocol changes as he numbe o machines in he
sys em is inc eased. Wo kload B is used, wi h a ixed a io o 10% upda e ansac ions, and
he numbe o si es is a ied om one o h ee, while keeping he numbe o pa i ions ixed
o 64. Figu e 4.3 shows he o e all pe o mance o he p o ocols.
●●●
10
25
50
100
250
500
750
1,000
1,250
1 Si es 2 Si es 3 Si es
Th oughpu (K ps) (log)
●
nai eSER as PSI nai eRC
Wo kload B, 90% ead−only ansac ions
Figu e 4.3:Maximum Th oughpu o Consis ency Models.
As be o e, he pe o mance o nai eRC inc eases almos in a linea ashion as mo e
se e s a e added, as explained by i s minimum need o synch onisa ion. Al hough he
scalabili y o as PSI is limi ed by he ixed numbe o pa i ions, i bene i s mode a ely
om inc easing he numbe o machines: as he o e all numbe o pa i ions pe machine
dec eases, se e s ee esou ces, and can hus ul il mo e clien eques s. This is e lec ed
in i s pe o mance a h ee si es being 1.52 imes i s base h oughpu a a single si e. In
con as , he o e all pe o mance o nai eSER s ays almos cons an as he numbe o si es
is inc eased, e lec ing i s need o alida e e e y ansac ion, which equi es g ea e le els
o synch onisa ion.
As he numbe o si es inc eases, so does he di e ence be ween nai eSER and as PSI.
O e all, as PSI manages o ou pe o m nai eSER by a ac o o 2.88 wi h a single si e, and
by a ac o o 3.52 a h ee si es.
Pa ame e Range De aul
Si es 1–3 3
Upda e T an. P opo ion 10%–30% 10%
Figu e 4.4:Pa ame e space used in he compa ison wo kload.
29
●
nai eSER as PSI nai eRC
●
●●
0.03
0.10
0.30
1.00
1 Si es 2 Si es 3 Si es
Numbe o Si es
(a)
●●●
0.03
0.10
0.30
1.00
10 20 30
Upda e T ansac ions (%)
(b)
Th oughpu (no malized)
Figu e 4.5:Pa ame e space explo a ion o e lec he pe o mance compa ison o he p o-
ocols. Each expe imen a ies one pa ame e while keeping he o he ixed a i s de aul
alue ( ep esen ed by he g ey e ical line). Th oughpu is shown no malised compa ed o
nai eRC.
O e all compa ison. The las wo expe imen s ha e shown how he pe o mance and
scalabili y o he implemen a ions is de e mined by he p opo ion o upda e ansac ions
and he numbe o si es. To be e isualise he ela ionship be ween wo kload choice and
pe o mance, he nex expe imen explo es he pa ame e space desc ibed in Figu e 4.4
when using Wo kload B. As in he p e ious expe imen , he numbe o pa i ions is kep
cons an as he numbe o si es inc eases. The esul s a e shown in Figu e 4.5, wi h he
h oughpu depic ed no malised compa ed o he pe o mance o nai eRC.
As shown in Figu e 4.5a, as PSI and nai eSER ha e di e en scalabili y p ope ies.
Al hough bo h implemen a ions su e in compa ison wi h nai eRC, as PSI exhibi s much
be e scalabili y in compa ison wi h nai eSER. Fo nai eSER, he need o alida e e e y
ansac ion imposes a pe o mance penal y ha inc eases as mo e si es a e added, and
consequen ly inc eases he o e all la ency o he commi phase o e e y ansac ion. In
con as , he impac on as PSI is less se e e, as he inc eased la ency only a ec s he ead
ope a ions, since he p opo ion o upda e ansac ions is low.
Figu e 4.5b shows he pe o mance compa ison as he p opo ion o upda e ansac ions
inc eases. While he di e ence in h oughpu be ween nai eRC and as PSI s ays cons an ,
he o e all pe o mance o as PSI is hinde ed by he need o compu e a causally compa ible
snapsho . Ne e heless, he ac ha he ela i e pe o mance s ays cons an in compa ison
wi h nai eRC shows ha he impac o he alida ion p ocess does no g ow wi h he
numbe o upda e ansac ions. The impac o upda e ansac ions on nai eSER is less
p onounced, and i s pe o mance di e ence wi h as PSI ge s smalle as he p opo ion
o upda es inc eases. This is explained by he choice o wo kload: ead-only ansac ions
pe o m ou eads, while upda e ansac ions pe o m h ee. Since nai eSER also alida es
ead-only ansac ions, as he p opo ion o upda es g ows, he a e age numbe o pa i ions
ha pa icipa e in he o ing phase sh inks om ou o h ee, which dec eases he un ime
cos o alida ion.
30
10%
20%
30%
40%
50%
0.00
0.05
0.10
0.15
0.20
0.25
0.30
0.35
0.40
nai eSER as PSI
Abo a io
Wo kload D, o e all abo a e
10%
20%
30%
40%
50%
0.00
0.05
0.10
0.15
0.20
0.25
0.30
0.35
0.40
nai eSER as PSI
Abo a io
Wo kload E, o e all abo a e
Figu e 4.6:O e all ansac ion abo a io o di e en consis ency models and wo kloads.
4.2.2. Abo Ra io
This sec ion ocuses on ano he ad an age o he elaxed consis ency model o as PSI
in compa ison wi h se ialisabili y, namely, he a io o abo ed ansac ions. One o he
cha ac e is ics o as PSI is ha he snapsho s o ansac ions exhibi o wa d eshness: a
ansac ion Tis able o ead objec e sions w i en by ansac ions ha commi ed a e
Ts a ed. In con as , a ansac ion Tunde se ialisabili y o classical Snapsho Isola ion
can only ead e sions w i en by ansac ions ha commi be o e T’s s a ime. This
limi a ion leads o a high numbe o abo ed ansac ions due o s ale eads in high la ency
se ings.
As such, his sec ion aims o explo e he ad an ages o o wa d eshness in as PSI in
compa ison wi h nai eSER, and how di e en wo kloads a ec i . Figu e 4.6 shows how he
abo a io o ansac ions a ies—unde di e en wo kloads—wi h he numbe o upda e
ansac ions. The esul s we e ob ained wi h wo si es. The g aph on he le shows he
ad an ages o he o wa d eshness o ansac ions, wi h he abo a io o as PSI being 30
pe cen age poin s be e han nai eSER, on a e age. Howe e , as he numbe o upda es
inc eases, so does he numbe o con lic ing ansac ions. This is e lec ed in an inc ease o
abo ed ansac ions, om less han one pe cen o a ound i e pe cen . The g aph on he
igh , howe e , shows di e en esul s: as he numbe o upda e ansac ions g ows, so does
he o e all abo a io o as PSI, om 7% o 25%. O e all, in he wo s case he abo
a io o as PSI is only 10 pe cen age poin s be e han nai eSER.
The di e ence be ween wo kloads is explained in he wo g aphs depic ed in Figu e 4.7,
which explo es he easons why ansac ions abo . In as PSI, a ansac ion migh abo
o wo easons: by upda ing an objec ha is o e w i en by a concu en ansac ion, o
by ailing o o m a causally consis en snapsho , as de ailed in 3.5. By i ue o ha ing he
same implemen a ion o causally consis en snapsho s, nai eSER inhe i s he same easons,
and adds a hi d: a ansac ion is o ced o abo i i eads a e sion o an objec ha is
la e o e w i en. Fo bo h p o ocols, a ansac ion migh abo a wo poin s du ing i s
execu ion: ead abo s occu when a ansac ion ails o ix a causally consis en snapsho ,
and o he wise he ansac ion abo s du ing alida ion, i.e., du ing he e mina ion o he
31

●
●●●●
0.005
0.010
0.025
0.050
0.100
1.000
10 20 30 40 50
Upda e T ansac ions (%)
Abo a io (log)
●nai eSER as PSI
Wo kload D, abo s du ing alida ion
●
●●●●
0.005
0.010
0.025
0.050
0.100
1.000
10 20 30 40 50
Upda e T ansac ions (%)
Abo a io (log)
●nai eSER as PSI
Wo kload E, abo s du ing alida ion
Figu e 4.7:Ra io o abo s ha happen du ing he alida ion phase, o di e en consis ency
models and wo kloads.
ansac ion. As seen on he le g aph in Figu e 4.7, in Wo kload D all abo ed ansac ions
in as PSI do so du ing he alida ion phase, while o nai eSER, only a small pe cen age
o abo ed ansac ions (be ween 0.5% and 2.5%) do so du ing e mina ion. In con as ,
as PSI exhibi s a e y di e en beha iou wi h Wo kload E, as shown in he g aph on he
igh . Wi h his wo kload, ansac ions abo o he same eason in bo h p o ocols: hey
a e unable o build causally consis en snapsho s. In bo h cases, he amoun o ansac ions
ha abo while a emp ing o ix a snapsho g ows as he numbe o upda e ansac ions
inc eases.
Recall ha in Wo kload D, upda e ansac ions upda e one single key, while in Wo kload
E, hey upda e h ee. This small di e ence in he numbe o upda ed keys explains he
di e ence in abo ed ansac ions o as PSI. As desc ibed in 3.5, a ansac ion Twill
be unable o ix a causally consis en snapsho when a) di e en pa i ions commi non-
con lic ing ansac ions in di e en o de , and b) T ixes a snapsho in one o hose pa i ions
be o e he upda es o all he non-con lic ing ansac ions become isible. Since upda e
ansac ions in Wo kload D only upda e a single key, upda e ansac ions will only commi
a a single pa i ion, and he e o e, no ansac ion can obse e a di e en commi o de .
This explains why he e a e no abo ed ansac ions due o inconsis en snapsho s when
execu ing his wo kload o as PSI. In con as , upda e ansac ions in Wo kload E upda e
h ee keys, and he e o e commi a h ee di e en pa i ions,1such ha he p obabili y o
pa i ions commi ing ansac ions in di e en o de g ows. In addi ion, since ansac ions
ead h ee keys, he p obabili y o obse ing di e en commi o de s also g ows. Thus, as he
numbe o upda e ansac ions inc eases, so does he p obabili y o ansac ions a emp ing
o ix inconsis en snapsho s. In nai eSER ansac ions also commi a he pa i ions hey
ead om, meaning ha upda e ansac ions in Wo kload D commi a h ee pa i ions.
1Since ansac ions choose keys ollowing an uni o m dis ibu ion, mos keys will be managed by dis inc
pa i ions.
32
0.000
0.025
0.050
0.075
0.100
0.125
0.150
0.175
0.200
0.225
0.250
0.275
0.300
234
Read Keys
(a)
Abo a io
2 w i es / 64 pa i ions
Read keys e ec on abo a io (Two keys w i en)
0.0
0.1
0.2
0.3
1234
W i en Keys
(b)
Abo a io
4 eads / 64 pa i ions
W i en keys e ec on abo a io
0.0
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
1.0
8 16 32 64 128 256
Pa i ions
(c)
Abo a io
4 eads / 4 w i es
Pa i ions numbe e ec on abo a io
Figu e 4.8:Resul s om explo ing he abo a io o as PSI ac oss di e en wo kload and
deploymen scena ios.
This explains why i s abo a io is simila in bo h wo kloads.
Since small changes in wo kload choice a e able o a ec he o e all abo a io o as PSI
in a signi ican manne , he e alua ion is concluded wi h an explo a ion o he pa ame-
e s ha ha e he highes impac on he numbe o abo ed ansac ions. As explained
p e iously, one o he easons why ansac ions obse e inconsis en snapsho s is because
pa i ions commi ansac ions in di e en o de s. Thus, by changing he numbe o keys
upda ed by a ansac ion, one can modi y he numbe o pa i ions in ol ed, which a ec s
he chances o di e en commi o de s. Ano he eason o inconsis en snapsho s is ha
ansac ions a e able o obse e he ansac ions ha commi in di e en o de , which leads
o change he numbe o keys ead by he ansac ions. I ansac ions ead om a small
amoun o pa i ions, he p obabili y ha hey obse e di e en commi o de s will also be
small. Finally, he mos impo an ac o is he numbe o pa i ions, o a he , he amoun
o keys pe pa i ion. When a ew pa i ions manage all he keys, mos ansac ions will
commi a he same pa i ions. The e o e, he p obabili y o ha ing di e en commi o de s
g ows, as well as he p obabili y ha a gi en ansac ion obse es hose o de s. Con e sely,
when he numbe o pa i ions is la ge, o pa i ions manage only a small amoun o keys,
he p obabili y o di e en commi o de s sh inks, as does he p obabili y o hem being
obse ed by ansac ions.
Figu e 4.8 shows he esul s o modi ying each o he pa ame e s men ioned, no ing
ha , o simplici y, a single si e is used while modi ying he numbe o pa i ions, ins ead o
changing he o al amoun o keys in he da abase. The pe cen age o upda e ansac ions
is se o 50%, o show he wo s possible abo a io. The e ec o changing he numbe
o keys ead by a ansac ion, shown in Figu e 4.8a, is small. Al hough he o e all abo
a io ne e g ows la ge han 10%, modi ying he numbe o ead keys esul s, a bes , in
an imp o emen o 7.5 pe cen age poin s. Blind upda es a e no allowed, and as such he
minimum numbe o ead keys is wo, since ansac ions need o upda e a leas wo keys
in wo di e en pa i ions o in oduce inconsis en snapsho s in he sys em. In con as ,
changing he numbe o keys upda ed by a ansac ion p oduces a bigge impac , as shown
33
●
●
●●
●
●
0
5,000
10,000
15,000
20,000
25,000
30,000
8 16 32 64 128 256
Pa i ions
Th oughpu ( ps)
4 eads / 4 w i es
Pa i ions numbe e ec on h oughpu
Figu e 4.9:Pe o mance deg ada ion o as PSI as he numbe o pa i ions inc eases, wi h
a ixed numbe o se e s.
in Figu e 4.8b, wi h an o e all change o 23 pe cen age poin s in he numbe o abo ed
ansac ions. When ansac ions upda e a single key, all ansac ions abo du ing alida-
ion. A his poin , he sys em shows he bes possible abo a io o 64 pa i ions, a
5%. Finally, modi ying he numbe o pa i ions yields he bigges change in he numbe o
abo ed ansac ions, as shown in Figu e 4.8c. Wi h 8 pa i ions, he o e all abo a io is
o almos 70%, which se es as an ex eme example o he impo ance o his pa ame e . As
he numbe o pa i ions g ows, he sys em eaches an abo a io o 27%. By inc easing he
numbe o pa i ions o 256, he esul is an abo a io o 10%. Wi h an o e all di e ence
o 60 pe cen age poin s in he p opo ion o abo ed ansac ions, his shows ha he num-
be o pa i ions is he bigges in luence in he abo a io o ansac ions in as PSI. I is
impo an o no e, howe e , ha inc easing he numbe o pa i ions also has a big impac
on he pe o mance o he sys em, as shown in Figu e 4.9. Du ing he expe imen , he
maximum h oughpu is eached a 32 pa i ions ac oss 4 machines. Wi h a small numbe
o pa i ions, he inc eased con en ion causes he h oughpu o d op. Wi h a big numbe o
pa i ions, each se e machine is also esponsible o a big numbe o pa i ions. As a esul ,
he sys em o e loads. Thus, he numbe o a ailable machines cons ain s he numbe o
pa i ions.
34
Chap e 5
Rela ed Wo k
This chap e gi es an o e iew o he p e ious wo k in he se ings o ansac ional
p o ocols, consis ency, and applica ion obus ness. I also highligh s he main di e ences
be ween he con ibu ions o his wo k and p e ious app oaches.
Applica ion Robus ness. The no ion o obus ness as applied o da abases was i s
in es iga ed by Feke e e al. [22], p oposing a way o analyse i applica ions we e obus
agains Snapsho Isola ion (SI) [13]. The wo k o Feke e e al. has esul ed in he p oli e -
a ion o s a ic analysis ools o de ec ing he p esence o anomalies in applica ions [29], as
well as se e al un- ime echniques o ensu ing se ialisable ansac ions [37]. Mo e ecen ly,
Be na di and Go sman [14] p oposed se e al obus ness c i e ia o a a ie y o consis ency
models, including Pa allel Snapsho Isola ion (PSI) [39]. The wo k on as PSI builds on
he obus ness c i e ia o Pa allel Snapsho Isola ion and o Snapsho Isola ion o build a
hyb id p o ocol ha allows p og amme s o selec i ely s eng hen consis ency gua an ees
o indi idual ansac ions.
En i y G oups. The concep o en i y was in oduced by Helland [28] o e e o a sel -
con ained da a objec , wi h applica ion-de ined bounda ies, and uniquely iden i ied by an
en i y key. In addi ion, Helland a gued o he en i y o be he la ges scope o ansac ional
se ialisabili y: ansac ions can only gua an ee a omici y o objec s held wi hin he same
en i y, and a e p e en ed om modi ying objec s ac oss en i ies.
La e sys ems, such as Megas o e [11], in oduced he concep o en i y g oups as disjoin
agg ega ions o indi idual en i ies. Such sys ems allowed ansac ions o access dis inc en i-
ies, and o e ed s ong consis ency o ansac ions accessing en i ies wi hin a g oup, while
o e ing almos no consis ency gua an ees o ansac ions ha accessed di e en g oups.
Such sys ems hus b oadened he scope o ansac ional se ialisabili y o encompass en i e
en i y g oups. In con as , as PSI p o ides PSI o all ansac ions, e en hose ha ac-
cess objec s in mul iple en i y g oups. A he same ime, i s eng hens he consis ency
gua an ees u he o ansac ions accessing only indi idual en i y g oups, by p o iding SI.
35
5 unc ion ead(T, x)
6i hx, i ∈ T.WS hen
7 e u n ;
8j←pa i ion(x);
9send READREQUEST(x, T.Vsnap, T.HasRead) o sj;
10 wai ecei e READRETURN(m) om sj;
11 i m=abo hen
12 h ow abo ;
13 else i m=h , Vdep,Vagg i hen
14 T.HasRead[j]← >;
15 T.RS ←(T.RS {hx, _i})∪ {hx, Vdep[j]i};
16 T.Vdep ←max(T.Vdep,Vdep);
17 T.Vsnap ←max(T.Vsnap,Vagg );
18 e u n ;
19 when ecei ed READREQUEST(x, Vsnap,HasRead) om cj
20 i HasRead[i] hen
21 V←Vsnap;
22 else
23 wai un il V o al[i]≥Vsnap[i];
24 ←max{ ∈Commi Log | ∀j. HasRead[j] =⇒( .Vagg [j]≤Vsnap[j])};
25 i .Vagg [i]<Vsnap[i] hen
26 send READRETURN(abo ) o cj;
27 e u n;
28 V← .Vagg ;
29 e = max{ e ∈Ve sionLog | e .Vcomm[i]≤V[i]};
30 send READRETURN( e . al, e .Vcomm, V ) o cj;
Figu e A.3:Se ialisable local and emo e ead o objec x
42

31 unc ion commi (T)
32 o all sj∈pa i ions(T.RS ∪T.WS)do
33 send PREPARE(T, T.RS, T.WS,Vdep) o sj;
34 Vcomm ←T.Vdep;
35 decision ←commi ;
36 o all sj∈pa i ions(T.RS ∪T.WS)do
37 wai ecei e VOTE(m) om sj;
38 i m=hT, abo i hen
39 decision ←abo ;
40 b eak;
41 else i m=hT, commi , ki hen
42 Vcomm[j]←k;
43 o all sj∈pa i ions(T.RS ∪T.WS)do
44 send DECIDE(T,Vcomm,decision) o sj;
45 e u n decision;
46 when ecei ed PREPARE(T, RS,WS,Vdep) om cj
47 i (∃T0.(hT0,pending,RS0,WS0i ∈ Commi Queue
∨ hT0,decided,_,_,_i ∈ Commi Queue)
∧(WS0∩RS 6=∅ ∧ RS0∩WS 6=∅)
∨(∃x. hx, sni ∈ RS ∧(Ve sionLog[x].las .Vcomm[i]> sn))
hen
48 send VOTE( , abo ) o cj;
49 e u n;
50 Las P ep ←Las P ep + 1;
51 Commi Queue.pu (T,pending,RS,WS);
52 send VOTE(T,commi ,Las P ep) o cj;
53 when ecei ed DECIDE(T, Vcomm,decision) om cj
54 i decision =commi hen
55 Commi Queue.upda e(hT,decided,_,_,Vcommi);
56 else
57 Commi Queue. emo e(T);
58 upon hT, decided,_,WS,Vcommi=Commi Queue.head()
59 o all {hx, i|hx, i ∈ WS ∧pa i ion(x) = i}do
60 Ve sionLog.add(hx, , Vcommi);
61 V o al ←max(V o al,Vcomm);
62 Commi Log.add(T, V o al);
63 Commi Queue. emo e(T);
Figu e A.4:Se ialisable e mina ion p o ocol.
43
A.2. Read Commi ed
Read Commi ed (RC) is he weakes consis ency model ha sa is ies he isola ion p op-
e y equi ed by ACID ansac ions. I o bids concu en ansac ions om obse ing any
da a ha has no been commi ed, bu i does no place any es ic ion on he o de ing o
ansac ions, and does no p eclude w i e-w i e con lic s. Thus, ansac ions may be o de ed
in any way. Figu e A.5 shows a summa y o he da a s uc u es in ol ed in he p o ocol.
Va iables a a se e si
Name Domain Desc ip ion
Commi Queue Sequence[hTx,S a e,W i eSe i]
whe e S a e ={pending,decided}
Queue con aining in o ma ion abou upda e
ansac ions ying o commi a he se e .
Da abase Se [hObjec ,Valuei]Se ep esen ing he key- alue s o e as a mapping
om objec s o alues.
Con ex o a ansac ion Ta a clien ci
T.WS W i eSe W i e-se o T.
Figu e A.5:Lis o a iables used in he Read Commi ed p o ocol, whe e W i eSe =
Se [hObjec ,Valuei].
Since ansac ions only need o obse e he las commi ed e sion o an objec , i is
su icien o s o e only one e sion. Thus, he Ve sionLog mapping can be subs i u ed wi h
aDa abase ha simply maps an objec o i s la es e sion. In addi ion, ansac ions
don’ need o obse e a consis en snapsho o he s a e o a pa i ion, and he e o e all
da a s uc u es ela ed o compu ing a snapsho can be emo ed. This is e lec ed in he
execu ion o a ansac ion, as can be seen in Figu e A.7. A se e siexecu ing a emo e ead
on behal o a ansac ion Tsimply e ches he cu en ly a ailable alue o he eques ed
objec , and e u ns i o he clien (line 13).
A p o ocol sa is ying Read Commi ed s ill needs o o e a omic isibili y. To do so, he
implemen a ion uses wo-phase commi o gua an ee ha a ansac ion commi s a e e y
pa i ion (line 14). Se e s ha pa icipa e du ing he commi phase always o e commi
(line 30), since RC does no p eclude w i e-w i e con lic s. A e a success ul commi phase,
all se e s inco po a e he upda es o he ansac ion o i s pa i ion s a e (line 38).
1 unc ion s a ()
2 e u n new Tx(WS =∅);
3 unc ion w i e(T, x, )
4T.WS ←(T.WS {hx, _i})∪ {hx, i};
Figu e A.6:Ini ialisa ion o a ansac ion and upda e o an objec xa clien ciunde
Read Commi ed.
44
5 unc ion ead(T, x)
6i hx, i ∈ T.WS hen
7 e u n ;
8j←pa i ion(x);
9send READREQUEST(x) o sj;
10 wai ecei e READRETURN( ) om sj;
11 e u n ;
12 when ecei ed READREQUEST(x) om cj
13 send READRETURN(Da abasei.ge (x)) o cj;
14 unc ion commi (T)
15 i .ws =∅ hen
16 e u n commi ;
17 o all sj∈pa i ions(T.WS)do
18 send PREPARE(T) o sj;
19 decision ←commi ;
20 o all sj∈pa i ions(T.WS)do
21 wai ecei e VOTE(m) om sj;
22 i m=hT, abo i hen
23 decision ←abo ;
24 b eak;
25 o all sj∈pa i ions(T.WS)do
26 send DECIDE(T,decision) o sj;
27 e u n decision;
28 when ecei ed PREPARE(T) om cj
29 Commi Queue.pu (T, pending,WS);
30 send VOTE(T, commi ) o cj;
31 when ecei ed DECIDE(T, decision) om cj
32 i decision =commi hen
33 Commi Queue.upda e(hT, decided,_i);
34 else
35 Commi Queue. emo e(T);
36 upon hT, decided,WSi=Commi Queue.head()
37 o all {hx, i|hx, i ∈ WS ∧pa i ion(x) = i}do
38 Da abasei.apply(x, );
39 Commi Queue. emo e(T);
Figu e A.7:Read Commi ed execu ion p o ocol.
45
Bibliog aphy
[1] as PSI clien -side lib a y. URL h ps://gi hub.com/e gl/p c/ ee/ 0.8.0.
[2] P o ocol Bu e s. URL h ps://gi hub.com/p o ocolbu e s/p o obu .
[3] as PSI Se e . URL h ps://gi hub.com/e gl/an ido e/ ee/p c.
[4] A ul Adya. Weak Consis ency: A Gene alized Theo y and Op imis ic Implemen a ions
o Dis ibu ed T ansac ions. Ph.D., MIT, Camb idge, MA, USA, Ma ch 1999.
[5] Deep hi De aki Akkoo a h, Alejand o Z. Tomsic, Manuel B a o, Zhongmiao Li, Tyle
C ain, Anne e Bieniusa, Nuno P eguica, and Ma c Shapi o. Cu e: S ong Seman ics
Mee s High A ailabili y and Low La ency. In P oceedings o he 36 h In e na ional
Con e ence on Dis ibu ed Compu ing Sys ems (ICDCS 2016), 2016.
[6] M. S. A dekani, P. Su a, and M. Shapi o. Non-mono onic snapsho isola ion: Scalable
and s ong consis ency o geo- eplica ed ansac ional sys ems. In 2013 IEEE 32nd
In e na ional Symposium on Reliable Dis ibu ed Sys ems, pages 163–172, Sep. 2013.
doi: 10.1109/SRDS.2013.25.
[7] Masoud Saeida A dekani. Ensu ing Consis ency in Pa ially Replica ed Da a S o es.
Ph.d., UPMC, Pa is, F ance, Sep embe 2014.
[8] Masoud Saeida A dekani, Ma ek Zawi ski, Pie e Su a, and Ma c Shapi o. The space
complexi y o ansac ional in e ac i e eads. In P oceedings o he 1s In e na ional
Wo kshop on Ho Topics in Cloud Da a P ocessing, Ho CDP ’12, New Yo k, NY, USA,
2012. Associa ion o Compu ing Machine y. ISBN 9781450311625. doi: 10.1145/
2169090.2169094. URL h ps://doi.o g/10.1145/2169090.2169094.
[9] Masoud Saeida A dekani, Pie e Su a, and Ma c Shapi o. G-DUR: A middlewa e o
assembling, analyzing, and imp o ing ansac ional p o ocols. In P oceedings o he
15 h In e na ional Middlewa e Con e ence, Middlewa e ’14, page 13–24, New Yo k,
NY, USA, 2014. Associa ion o Compu ing Machine y. ISBN 9781450327855. doi:
10.1145/2663165.2663336. URL h ps://doi.o g/10.1145/2663165.2663336.
[10] Pe e Bailis, Alan Feke e, Joseph M. Helle s ein, Ali Ghodsi, and Ion S oica. Scalable
a omic isibili y wi h RAMP ansac ions. In P oceedings o he 2014 ACM SIGMOD
In e na ional Con e ence on Managemen o Da a, SIGMOD ’14, page 27–38, New
Yo k, NY, USA, 2014. Associa ion o Compu ing Machine y. ISBN 9781450323765.
doi: 10.1145/2588555.2588562. URL h ps://doi.o g/10.1145/2588555.2588562.
46
[11] Jason Bake , James C. Co be , JJ Fu man, And ey Kho lin, James La son, Jean-
Michel Leon, Yawei Li, Alexande Lloyd, and Vadim Yushp akh. Megas o e: P o id-
ing Scalable, Highly A ailable S o age o In e ac i e Se ices. In P oceedings o he
Con e ence on Inno a i e Da a sys em Resea ch (CIDR), pages 223–234, 2011. URL
h p://www.cid db.o g/cid 2011/Pape s/CIDR11_Pape 32.pd .
[12] Ca los Baque o and Nuno M. P eguiça. Why logical clocks a e easy. Commun. ACM,
59(4):43–47, 2016.
[13] Hal Be enson, Phil Be ns ein, Jim G ay, Jim Mel on, Elizabe h O’Neil, and Pa ick
O’Neil. A C i ique o ANSI SQL Isola ion Le els. In P oceedings o he 1995 ACM
SIGMOD in e na ional con e ence on Managemen o da a - SIGMOD ’95, 1995.
[14] Gio anni Be na di and Alexey Go sman. Robus ness agains Consis ency Models wi h
A omic Visibili y. In Josée Desha nais and Radha Jagadeesan, edi o s, 27 h In e -
na ional Con e ence on Concu ency Theo y (CONCUR 2016), olume 59 o Leib-
niz In e na ional P oceedings in In o ma ics (LIPIcs), pages 7:1–7:15, Dags uhl, Ge -
many, 2016. Schloss Dags uhl–Leibniz-Zen um ue In o ma ik. ISBN 978-3-95977-017-
0. doi: 10.4230/LIPIcs.CONCUR.2016.7. URL h p://d ops.dags uhl.de/opus/
oll ex e/2016/6165.
[15] Philip A. Be ns ein, Vassos Hadzilacos, and Na han Goodman. Concu ency Con ol
and Reco e y in Da abase Sys ems. Addison-Wesley, 1987.
[16] E ic A B ewe . Towa ds Robus Dis ibu ed Sys ems (keyno e). In 19 h ACM Sympo-
sium on P inciples o Dis ibu ed Compu ing (PODC), July 2000.
[17] And ea Ce one, Gio anni Be na di, and Alexey Go sman. A amewo k o ansac-
ional consis ency models wi h a omic isibili y. In 26 h In e na ional Con e ence on
Concu ency Theo y, CONCUR 2015, Mad id, Spain, Sep embe 1-4, 2015.
[18] B ian F. Coope , Adam Silbe s ein, E win Tam, Raghu Ramak ishnan, and Russell
Sea s. Benchma king cloud se ing sys ems wi h ycsb. In P oceedings o he 1s ACM
Symposium on Cloud Compu ing, SoCC ’10, New Yo k, NY, USA, 2010.
[19] James C. Co be , Je ey Dean, Michael Eps ein, And ew Fikes, Ch is ophe
F os , J. J. Fu man, Sanjay Ghemawa , And ey Guba e , Ch is ophe Heise , Pe e
Hochschild, and e al. Spanne : Google’s globally dis ibu ed da abase. ACM T ans.
Compu . Sys ., 31(3), Augus 2013. ISSN 0734-2071. doi: 10.1145/2491245. URL
h ps://doi.o g/10.1145/2491245.
[20] Giuseppe DeCandia, Deniz Has o un, Madan Jampani, Guna a dhan Kakulapa i,
A inash Lakshman, Alex Pilchin, Swamina han Si asub amanian, Pe e Vosshall, and
We ne Vogels. Dynamo: amazon’s highly a ailable key- alue s o e. SIGOPS Ope .
Sys . Re ., 41(6):205, Oc obe 2007. ISSN 01635980. doi: 10.1145/1323293.1294281.
47

[21] Alan Feke e. Alloca ing Isola ion Le els o T ansac ions. In P oceedings o he Twen y-
Fou h ACM SIGMOD-SIGACT-SIGART Symposium on P inciples o Da abase Sys-
ems, PODS ’05, page 206–215, New Yo k, NY, USA, 2005. Associa ion o Com-
pu ing Machine y. ISBN 1595930620. doi: 10.1145/1065167.1065193. URL h ps:
//doi.o g/10.1145/1065167.1065193.
[22] Alan Feke e, Dimi ios Lia okapis, Elizabe h O’Neil, Pa ick O’Neil, and Dennis
Shasha. Making Snapsho Isola ion Se ializable. ACM T ans. Da abase Sys ., 30
(2):492–528, June 2005. ISSN 0362-5915. doi: 10.1145/1071610.1071615. URL
h ps://doi.o g/10.1145/1071610.1071615.
[23] Se h Gilbe and Nancy Lynch. B ewe ’s conjec u e and he easibili y o consis en ,
a ailable, pa i ion- ole an web se ices. SIGACT News, 33(2):51–59, June 2002. ISSN
0163-5700. doi: 10.1145/564585.564601. URL h ps://doi.o g/10.1145/564585.
564601.
[24] Alexey Go sman, Hongseok Yang, Ca la Fe ei a, Mahsa Naja zadeh, and Ma c
Shapi o. ’Cause I’m S ong Enough: Reasoning abou Consis ency Choices in Dis-
ibu ed Sys ems. In P oceedings o he 43 d Annual ACM SIGPLAN-SIGACT Sym-
posium on P inciples o P og amming Languages, POPL ’16, page 371–384, New Yo k,
NY, USA, 2016. Associa ion o Compu ing Machine y. ISBN 9781450335492. doi:
10.1145/2837614.2837625. URL h ps://doi.o g/10.1145/2837614.2837625.
[25] Jim G ay and Leslie Lampo . Consensus on T ansac ion Commi . ACM T ansac ions
on Da abase Sys ems, 31(1):133–160, Ma ch 2006. ISSN 0362-5915. doi: 10.1145/
1132863.1132867. URL h ps://doi.o g/10.1145/1132863.1132867.
[26] Rachid Gue aoui and And é Schipe . Genuine a omic mul icas in asynch onous dis-
ibu ed sys ems. Theo e ical Compu e Science (Else ie ), 254:297–316, 2001. URL
h p://in oscience.ep l.ch/ eco d/49965.
[27] R. C. Hansdah and Lali M. Pa naik. Upda e Se ializabili y in Locking. In P oceedings
o he In e na ional Con e ence on Da abase Theo y, ICDT ’86, page 171–185, Be lin,
Heidelbe g, 1986. Sp inge -Ve lag. ISBN 3540171878.
[28] Pa Helland. Li e beyond Dis ibu ed T ansac ions: an Apos a e’s Opinion. In CIDR
2007, Thi d Biennial Con e ence on Inno a i e Da a Sys ems Resea ch, Asiloma , CA,
USA, Janua y 7-10, 2007, Online P oceedings, pages 132–141. www.cid db.o g, 2007.
URL h p://cid db.o g/cid 2007/pape s/cid 07p15.pd .
[29] Sudhi Jo weka , Alan Feke e, K i hi Ramam i ham, and S. Suda shan. Au oma ing
he de ec ion o snapsho isola ion anomalies. In P oceedings o he 33 d In e na ional
Con e ence on Ve y La ge Da a Bases, VLDB ’07, page 1263–1274. VLDB Endowmen ,
2007. ISBN 9781595936493.
48
[30] Da id Ka ge , E ic Lehman, Tom Leigh on, Rina Panig ahy, Ma hew Le ine, and
Daniel Lewin. Consis en hashing and andom ees: Dis ibu ed caching p o ocols
o elie ing ho spo s on he Wo ld Wide Web. In P oceedings o he Twen y-Nin h
Annual ACM Symposium on Theo y o Compu ing, STOC ’97, page 654–663, New
Yo k, NY, USA, 1997. Associa ion o Compu ing Machine y. ISBN 0897918886. doi:
10.1145/258533.258660. URL h ps://doi.o g/10.1145/258533.258660.
[31] Leslie Lampo . The pa - ime pa liamen . ACM T ans. Compu . Sys ., 16(2):133–169,
May 1998. ISSN 0734-2071. doi: 10.1145/279227.279229. URL h ps://doi.o g/10.
1145/279227.279229.
[32] Wya Lloyd, Michael J. F eedman, Michael Kaminsky, and Da id G. Ande sen.
Don’ Se le o E en ual: Scalable Causal Consis ency o Wide-A ea S o age wi h
COPS. In P oceedings o he Twen y-Thi d ACM Symposium on Ope a ing Sys ems
P inciples, SOSP ’11, page 401–416, New Yo k, NY, USA, 2011. Associa ion o
Compu ing Machine y. ISBN 9781450309776. doi: 10.1145/2043556.2043593. URL
h ps://doi.o g/10.1145/2043556.2043593.
[33] Hen ique Moniz, João Lei ão, Rica do J. Dias, Johannes Geh ke, Nuno P eguiça, and
Rod igo Rod igues. Blo e : Low La ency T ansac ions o Geo-Replica ed S o age. In
P oceedings o he 26 h In e na ional Con e ence on Wo ld Wide Web, WWW ’17, page
263–272, Republic and Can on o Gene a, CHE, 2017. In e na ional Wo ld Wide Web
Con e ences S ee ing Commi ee. ISBN 9781450349130. doi: 10.1145/3038912.3052603.
URL h ps://doi.o g/10.1145/3038912.3052603.
[34] Mahsa Naja zadeh, Alexey Go sman, Hongseok Yang, Ca la Fe ei a, and Ma c
Shapi o. The CISE Tool: P o ing Weakly-Consis en Applica ions Co ec . In
P oceedings o he 2nd Wo kshop on he P inciples and P ac ice o Consis ency o
Dis ibu ed Da a, PaPoC ’16, New Yo k, NY, USA, 2016. Associa ion o Compu -
ing Machine y. ISBN 9781450342964. doi: 10.1145/2911151.2911160. URL h ps:
//doi.o g/10.1145/2911151.2911160.
[35] D. S. Pa ke , G. J. Popek, G. Rudisin, A. S ough on, B. J. Walke , E. Wal on, J. M.
Chow, D. Edwa ds, S. Kise , and C. Kline. De ec ion o mu ual inconsis ency in
dis ibu ed sys ems. IEEE T ans. So w. Eng., 9(3):240–247, May 1983.
[36] Sebas iano Peluso, Ped o Rui o, Paolo Romano, F ancesco Quaglia, and Luis Ro-
d igues. GMU: Genuine Mul i e sion Upda e-Se ializable Pa ial Da a Replica ion.
IEEE T ansac ions on Pa allel and Dis ibu ed Sys ems, 27(10):2911–2925, Oc obe
2016. ISSN 1045-9219. doi: 10.1109/TPDS.2015.2510998. URL h ps://doi.o g/10.
1109/TPDS.2015.2510998.
[37] Dan R. K. Po s and Ke in G i ne . Se ializable Snapsho Isola ion in Pos g eSQL.
P oc. VLDB Endow., 5(12):1850–1861, Augus 2012. ISSN 2150-8097. doi: 10.14778/
2367502.2367523. URL h ps://doi.o g/10.14778/2367502.2367523.
49
[38] Masoud Saeida A dekani, Pie e Su a, Ma c Shapi o, and Nuno P eguiça. On he
scalabili y o snapsho isola ion. In Felix Wol , Be nd Moh , and Die e an Mey, edi o s,
Eu o-Pa 2013 Pa allel P ocessing, pages 369–381, Be lin, Heidelbe g, 2013. Sp inge
Be lin Heidelbe g. ISBN 978-3-642-40047-6.
[39] Yai So an, Russell Powe , Ma cos K. Aguile a, and Jinyang Li. T ansac ional s o age
o geo- eplica ed sys ems. In P oceedings o he Twen y-Thi d ACM Symposium on
Ope a ing Sys ems P inciples - SOSP ’11, 2011.
[40] We ne Vogels. E en ually consis en . ACM Queue, 6(6):14–19, Oc obe 2008.
50