1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
1001
1002
1003
1004
1005
1006
1007
1008
1009
1010
1011
1012
1013
1014
1015
1016
1017
1018
1019
1020
1021
1022
1023
1024
1025
1026
1027
1028
1029
1030
1031
1032
1033
1034
1035
1036
1037
1038
1039
1040
1041
1042
1043
1044
1045
1046
1047
1048
1049
1050
1051
1052
1053
1054
1055
1056
1057
1058
1059
1060
1061
1062
1063
1064
1065
1066
1067
1068
1069
1070
1071
1072
1073
1074
1075
1076
1077
1078
1079
1080
1081
1082
1083
1084
1085
1086
1087
1088
1089
1090
1091
1092
1093
1094
1095
1096
1097
1098
1099
1100
1101
1102
1103
1104
1105
1106
1107
1108
1109
1110
1111
1112
1113
1114
1115
1116
1117
1118
1119
1120
1121
1122
1123
1124
1125
1126
1127
1128
1129
1130
1131
1132
1133
1134
1135
1136
1137
1138
1139
1140
1141
1142
1143
1144
1145
1146
1147
1148
1149
1150
1151
1152
1153
1154
1155
1156
1157
1158
1159
1160
1161
1162
1163
1164
1165
1166
1167
1168
1169
1170
1171
1172
1173
1174
1175
1176
1177
1178
1179
1180
1181
1182
1183
1184
1185
1186
1187
1188
1189
1190
1191
1192
1193
1194
1195
1196
1197
|
<!DOCTYPE doctype PUBLIC "-//w3c//dtd html 4.0 transitional//en">
<html>
<head>
<meta http-equiv="Content-Type"
content="text/html; charset=iso-8859-1">
<meta name="GENERATOR"
content="Mozilla/4.76 [en] (X11; U; FreeBSD 4.3-RELEASE i386) [Netscape]">
<title>Master Lease</title>
</head>
<body>
<center>
<h1>Master Leases for Berkeley DB</h1>
</center>
<center><i>Susan LoVerso</i> <br>
<i>sue@sleepycat.com</i> <br>
<i>Rev 1.1</i><br>
<i>2007 Feb 2</i><br>
</center>
<p><br>
</p>
<h2>What are Master Leases?</h2>
A master lease is a mechanism whereby clients grant master-ship rights
to a site and that master, by holding lease rights can provide a
guarantee of durability to a replication group for a given period of
time. By granting a lease to a master,
a client will not participate in an election to elect a new
master until that granted master lease has expired. By holding a
collection of granted leases, a master will be able to supply
authoritative read requests to applications. By holding leases a
read operation on a master can guarantee several things to the
application:<br>
<ol>
<li>Authoritative reads: a guarantee that the data being read by the
application is durable and can never be rolled back.</li>
<li>Freshness: a guarantee that the data being read by the
application <b>at the master</b> is
not stale.</li>
<li>Master viability: a guarantee that a current master with valid
leases will not encounter a duplicate master situation.<br>
</li>
</ol>
<h2>Requirements</h2>
The requirements of DB to support this include:<br>
<ul>
<li>After turning them on, users can choose to ignore them in reads
or not.</li>
<li>We are providing read authority on the master only. A
read on a client is equivalent to a read while ignoring leases.</li>
<li>We guarantee that data committed on a master <b>that has been
read by an application on the
master</b> will not be rolled back. Data read on a client or
while ignoring leases <i>or data
successfully updated/committed but not read,</i>
may be rolled back.<br>
</li>
<li>A master will not return successfully from a read operation
unless it holds a
majority of leases unless leases are ignored.</li>
<li>Master leases will remove the possibility of a current/correct
master being "shot down" by DUPMASTER. <b>NOTE: Old/Expired
masters may discover a
later master and return DUPMASTER to the application however.</b><br>
</li>
<li>Any send callback failure must result in premature lease
expiration on the master.<br>
</li>
<li>Users who change the system clock during master leases void the
guarantee and may get undefined behavior. We assume time always
runs forward. <br>
</li>
<li>Clients are forbidden from participating in elections while they
have an outstanding lease granted to another site.</li>
<li>Clients are forbidden from accepting a new master while they have
an outstanding lease granted to another site.</li>
<li>Clients are forbidden from upgrading themselves to master while
they have an outstanding lease granted to another site.</li>
<li>When asked for a lease grant explicitly by the master, the client
cannot grant the lease to the master unless the LSN in the master's
request has been processed by this client.<br>
</li>
</ul>
The requirements of the
application using leases include:<br>
<ul>
<li>Users must implement (Base API users on their own, RepMgr users
via configuration) a majority (or larger) ACK policy. <br>
</li>
<li>The application must use the election mechanism to decide a master.
It may not simply declare a site master.</li>
<li>The send callback must return an error if the majority ACK policy
is not met for PERM records.</li>
<li>Users must set the number of sites in the group.</li>
<li>Using leases in a replication group is all-or-none.
Therefore, if a site knows it is using leases, it can assume other
sites are also.<br>
</li>
<li>All applications that care about read guarantees must forward or
perform all reads on the master. Reading on the client means a
read ignoring leases. </li>
</ul>
<p>There are some open questions
remaining.</p>
<ul>
<li>There is one major showstopper issue, see Crashing - Potential
problem near the end of the document. We need a better solution
than the one shown there (writing to disk every time a lease is
granted). Perhaps just documenting that durability means it must be
flushed to disk before success to avoid that situation?<br>
</li>
<li>What about db->join? Users can call join, but the calls
on the join cursor to get the data would be subject to leases and
therefore protected. Ok, this is not an open question.</li>
<li>What about other read-like operations? Clearly <i>
DB->get, DB->pget, DBC->get,
DBC->pget</i> need lease checks. However, other APIs use
keys. <i>DB->key_range</i>
provides an estimate only so it shouldn't need lease checks. <i>
DB->stat</i> provides exact counts
to <i>bt_nkeys</i> and <i>bt_ndata</i> fields. Are those
fields considered authoritative that providing those values implies a
durability guarantee and therefore <i>DB->stat</i>
should be subject to lease verification? <i>DBC->count</i>
provides a count for
the number of data items associated with a key. Is this
authoritative information? This is similar to stat - should it be
subject to lease verification?<br>
</li>
<li>Do we require master lease checks on write operations? I
think lease checks are not needed on write operations. It doesn't
add correctness and adds a lot of complexity (checking leases in put,
del, and cursors, then what about rename, remove, etc).<br>
</li>
<li>Do master leases give an iron-clad guarantee of never rolling
back a transaction? No, but it should mean that a committed transaction
can never be <b>read</b> on a master
unless the lease is valid. A committed transaction on a master
that has never been presented to the application may get rolled back.<br>
</li>
<li>Do we need to quarantine or prevent reads on an ex-master until
sync-up is done? No. A master that is simply downgraded to
client or crashes and reboots is now a client. Reading from that
client is the same as saying Ignore Leases.</li>
<li>What about adding and removing sites while leases are
active? This is SR 14778. A consistent <i>nsites</i> value
is required by master
leases. It isn't
clear to me what a master is
supposed to do if the value of nsites gets smaller while leases are
active. Perhaps it leaves its larger table intact and simply
checks for a smaller number of granted leases?<br>
</li>
<li>Can users turn leases off? No. There is no planned <i>turn
leases off</i> API.</li>
<li>Clock skew will be a percentage. However, the smallest, 1%,
is probably rather large for clock skew. Percentage was chosen
for simplicity and similarity to other APIs. What granularity is
appropriate here?</li>
</ul>
<h2>API Changes</h2>
The API changes that are visible
to the user are fairly minimal.
There are a few API calls they need to make to configure master leases
and then there is the API call to turn them on. There is also a
new flag to existing APIs to allow read operations to ignore leases and
return data that
may be non-durable potentially.<br>
<h3>Lease Timeout<br>
</h3>
There is a new timout the user
must configure for leases called <b>DB_REP_LEASE_TIMEOUT</b>.
This timeout will be new to
the <i>dbenv->rep_set_timeout</i> method. The <b>DB_REP_LEASE_TIMEOUT</b>
has no default and it is required that the user configure a timeout
before they turn on leases (obviously, this timeout need not be set of
leases will not be used). That timeout is the amount of time
the lease is valid on the master and how long it is granted
on the client. This timeout must be the same
value on all sites (like log file size). The timeout used when
refreshing leases is the <b>DB_REP_ACK_TIMEOUT</b>
for RepMgr application. For Base API applications, lease
refreshes will use the same mechanism as <b>PERM</b> messages and they
should
have no additional burden. This timeout is used for lease
refreshment and is the amount of time a reader will wait to refresh
leases before returning failure to the application from a read
operation.<br>
<br>
This timeout will be both stored
with its original value, and also
converted to a <i>db_timespec</i>
using the <b>DB_TIMEOUT_TO_TIMESPEC</b>
macro and have the clock skew accounted for and stored in the shared
rep structure:<br>
<pre>db_timeout_t lease_timeout;<br>db_timespec lease_duration;<br></pre>
NOTE: By sending the lease refresh during DB operations, we are
forcing/assuming that the operation's process has a replication
transport function set. That is obviously the case for write
operations, but would it be a burden for read processes (on a
master)? I think mostly not, but if we need leases for <i>
DB->stat</i> then we need to
document it as it is certainly possible for an application to have a
separate or dedicated <i>stat</i>
application or attempt to use <i>db_stat</i>
(which will not work if leases must be checked).<br>
<br>
Leases should be checked after the local operation so that we don't
have a window/boundary if we were to check leases first, get
descheduled, the lose our lease and then perform the operation.
Do the operation, then check leases before returning to the user.<br>
<h3>Using Leases</h3>
There is a new API that the user must call to tell the system to use
the lease mechanism. The method must be called before the
application calls <i>dbenv->rep_start</i>
or <i>dbenv->repmgr_start</i>.
This new
method is:<br>
<br>
<pre> dbenv->rep_set_lease(DB_ENV *dbenv, u_int32_t clock_scale_factor, u_int32_t flags)<br>
</pre>
The <i>clock_scale_factor</i>
parameter is interpreted as a percentage, greater than 100 (to transmit
a floating point number as an integer to the API) that represents the
maximum shkew between any two sites' clocks. That is, a <span
style="font-style: italic;">clock_scale_factor</span> of 150 suggests
that the greatest discrepancy between clocks is that one runs 50%
faster than the others. Both the
master and client sides
compensate for possible clock skew. The master uses the value to
compensate in case the replica has a slow clock and replicas compensate
in case they have a fast clock. This scaling factor will need to
be divided by 100 on all sites to truly represent the percentage for
adjustments made to time values.<br>
<br>
Assume the slowest replica's clock is a factor of <i>clock_scale_factor</i>
slower than the
fastest clock. Using that assumption, if the fastest clock goes
from time t1 to t2 in X
seconds, the slowest clock does it in (<i>clock_scale_factor</i> / 100)
* X seconds.<br>
<br>
The <i>flags</i> parameter is not
currently used.<br>
<br>
When the <i>dbenv->rep_set_lease</i>
method is called, we will set a configuration flag indicating that
leases are turned on:<br>
<b>#define REP_C_LEASE <value></b>.
We will also record the <b>u_int32_t
clock_skew</b> value passed in. The <i>rep_set_lease</i> method
will not allow
calls after <i>rep_start. </i>If
multiple calls are made prior to calling <i>rep_start</i> then later
calls will
overwrite the earlier clock skew value. <br>
<br>
We need a new flag to prevent calling <i>rep_set_lease</i>
after <i>rep_start</i>. The
simplest solution would be to reject the call to
<i>rep_set_lease
</i>if<b>
REP_F_CLIENT</b>
or <b>REP_F_MASTER</b> is set.
However that does not work in the cases where a site cleanly closes its
environment and then opens without running recovery. The
replication state will still be set. The prevention will be
implemented as:<br>
<pre>#define REP_F_START_CALLED <some bit value><br></pre>
In __rep_start, at the end:<br>
<pre>if (ret == 0 ) {<br> REP_SYSTEM_LOCK<br> F_SET(rep, REP_F_START_CALLED)<br> REP_SYSTEM_UNLOCK<br>}</pre>
In <i>__rep_env_refresh</i>, if we
are the last reference closing the env (we already check for that):<br>
<pre>F_CLR(rep, REP_F_START_CALLED);</pre>
In order to avoid run-time floating point operations
on <i>db_timespec</i> structures,
when a site is declared as a client or master in <i>rep_start</i> we
will pre-compute the
lease duration based on the integer-based clock skew and the
integer-based lease timeout. A master should set a replica's
lease expiration to the <b>start time of
the sent message +
(lease_timeout / clock_scale_factor)</b> in case the replica has a
slow clock. Replicas extend their leases to <b>received message
time + (lease_timeout *
clock_scale_factor)</b> in case this replica has a fast clock.
Therefore, the computation will be as follows if the site is becoming a
master:<br>
<pre>db_timeout_t tmp;<br>tmp = (db_timeout_t)((double)rep->lease_timeout / ((double)rep->clock_skew / (double)100));<br>rep->lease_duration = DB_TIMEOUT_TO_TIMESPEC(&tmp);<br></pre>
Similarly, on a client the computation is:<br>
<pre>tmp = (db_timeout_t)((double)rep->lease_timeout * ((double)rep->clock_skew / (double)100));<br></pre>
When a site changes state, its lease duration will change based on
whether it is becoming a master or client and it will be recomputed
from the original values. Note that these computations, coupled
with the fact that the lease on the master is computed based on the
master's time that it sent the message means that leases on the master
are more conservatively computed than on the clients.<br>
<br>
The <i>dbenv->rep_set_lease</i>
method must be called after <i>dbenv->open</i>,
similar to <i>dbenv->rep_set_config</i>.
The reason is so that we can check that this is a replication
environment and we have access to the replication shared memory region.<br>
<h3>Read Operations<br>
</h3>
Authoritative read operations on the master with leases enabled will
abide by leases by default. We will provide a flag that allows an
operation on a master to ignore leases. <b>All read operations
on a client imply
ignoring leases.</b> If an application wants authoritative reads
they must forward the read requests to the master and it is the
application's responsibility to provide the forwarding.
The consensus was that forcing <span style="font-weight: bold;">DB_IGNORE_LEASE</span>
on client read operations (with leases enabled, obviously) was too
heavy handed. Read operations on the client will ignore leases,
but do no special flag checking.<br>
<br>
The flag will be called <b>DB_IGNORE_LEASE</b>
and it will be a flag that can be OR'd into the DB access method and
cursor operation values. It will be similar to the <b>DB_READ_UNCOMMITTED</b>
flag.
<br>
</b>The methods that will
adhere to leases are:<br>
<ul>
<li><i>Db->get</i></li>
<li><i>Db->pget</i></li>
<li><i>Dbc->get</i></li>
<li><i>Dbc->pget</i></li>
</ul>
The code that will check leases for a client reading would look
something
like this, if we decide to become heavy-handed:<br>
<pre>if (IS_REP_CLIENT(dbenv)) {<br> [get to rep structure]<br> if (FLD_ISSET(rep->config, REP_C_LEASE) && !LF_ISSET(DB_IGNORE_LEASE)) {<br> db_err("Read operations must ignore leases or go to master");<br> ret = EINVAL;<br> goto err;<br> }<br>}<br></pre>
On the master, the new code to abide by leases is more complex.
After the call to perform the operation we will check the lease.
In that checking code, the master will see if it has a valid
lease. If so, then all is well. If not, it will try to
refresh the leases. If that refresh attempt results in leases,
all is well. If the refresh attempt does not get leases, then the
master cannot respond to the read as an authority and we return an
error. The new error is called <b>DB_REP_LEASE_EXPIRED</b>.
The location of the master lease check is down after the internal call
to read the data is successful:<br>
<pre>if (IS_REP_MASTER(dbenv) && !LF_ISSET(DB_IGNORE_LEASE)) {<br> [get to rep structure]<br> if (FLD_ISSET(rep->config, REP_C_LEASE) &&<br> (ret = __rep_lease_check(dbenv)) != 0) {<br> /*<br> * We don't hold the lease.<br> */<br> goto err;<br> }<br>}<br></pre>
See below for the details of <i>__rep_lease_check</i>.<br>
<br>
Also note that if leases (or replication) are not configured, then <span
style="font-weight: bold;">DB_IGNORE_LEASE</span> is a no-op. It
is ignored (and won't error) if used when leases are not in
effect. The reason is so that we can generically set that flag in
utility programs like <span style="font-style: italic;">db_dump</span>
that walk the database with a cursor. Note that <span
style="font-style: italic;">db_dump</span> is the only utility that
reads with a cursor.<span style="font-style: italic;"><span
style="font-style: italic;"></span></span><br>
<h3><b>Nsites
and Elections</b></h3>
The call to <i>dbenv->rep_set_nsites</i>
must be performed before the call to <i>dbenv->rep_start</i>
or <i>dbenv->repmgr_start</i>.
This document assumes either that <b>SR
14778</b> gets resolved, or assumes that the value of <i>nsites</i> is
immutable. The
master and all clients need to know how many sites and leases are in
the group. Clients need to know for elections. The master
needs to know for the size of the lease table and to know what value a
majority of the group is. <b>[Until
14778 is resolved, the master lease work must assume <i>nsites</i> is
immutable and will
therefore enforce that this is called before <i>rep_start</i> using
the same mechanism
as <i>rep_set_lease</i>.]</b><br>
<br>
Elections and leases need to agree on the number of sites in the
group. Therefore, when leases are in effect on clients, all calls
to <i>dbenv->rep_elect</i> must
set the <i>nsites</i> parameter to
0. The <i>rep_elect</i> code
path will return <b>EINVAL</b> if <b>REP_C_LEASE</b> is set and <i>nsites</i>
is non-0.
<h2>Lease Management</h2>
<h3>Message Changes</h3>
In order for clients to grant leases to the master a new message type
must be added for that purpose. This will be the <b>REP_LEASE_GRANT</b>
message.
Granting leases will be a result of applying a <b>DB_REP_PERMANENT</b>
record and therefore we
do not need any additional message in order for a master to request a
lease grant. The <b>REP_LEASE_GRANT</b>
message will pass a structure as its message DBT:<br>
<pre>struct __rep_lease_grant {<br> db_timespec msg_time;<br>#ifdef DIAGNOSTIC<br> db_timespec expire_time;<br>#endif<br>} REP_GRANT_INFO;<br></pre>
In the <b>REP_LEASE_GRANT</b>
message, the client is actually giving the master several pieces of
information. We only need the echoed <i>msg_time</i> in this
structure because
everything else is already sent. The client is really sending the
master:<br>
<ul>
<li>Its EID (parameter to <span style="font-style: italic;">rep_send_message</span>
and <span style="font-style: italic;">rep_process_message</span>)<br>
</li>
<li>The PERM LSN this message acknowledged (sent in the control
message)</li>
<li>Unique identifier echoed back to master (<i>msg_time</i> sent in
message as above)</li>
</ul>
On the client, we always maintain the maximum PERM LSN already in <i>lp->max_perm_lsn</i>.
<h3>Local State Management</h3>
Each client must maintain a <i>db_timespec</i>
timestamp containing the expiration of its granted lease. This
field will be in the replication shared memory structure:<br>
<pre>db_timespec grant_expire;<br></pre>
This timestamp already takes into account the clock skew. All
new fields must be initialized when the region is created. Whenever we
grant our master lease and want to send the <b>REP_LEASE_GRANT</b>
message, this value
will be updated. It will be used in the following way:
<pre>db_timespec mytime;<br>DB_LSN perm_lsn;<br>DBT lease_dbt;<br>REP_GRANT_INFO gi;<br><br><br>timespecclear(&mytime);<br>timespecclear(&newgrant);<br>memset(&lease_dbt, 0, sizeof(lease_dbt));<br>memset(&gi, 0, sizeof(gi));<br>__os_gettime(dbenv, &mytime);<br>timespecadd(&mytime, &rep->lease_duration);<br>MUTEX_LOCK(rep->clientdb_mutex);<br>perm_lsn = lp->max_perm_lsn;<br>MUTEX_UNLOCK(rep->clientdb_mutex);<br>REP_SYSTEM_LOCK(dbenv);<br>if (timespeccmp(mytime, rep->grant_expire, >))<br> rep->grant_expire = mytime;<br>gi.msg_time = msg->msg_time;<br>#ifdef DIAGNOSTIC<br>gi.expire_time = rep->grant_expire;<br>#endif<br>lease_dbt.data = &gi;<br>lease_dbt.size = sizeof(gi);<br>REP_SYSTEM_UNLOCK(dbenv);<br>__rep_send_message(dbenv, eid, REP_LEASE_GRANT, &perm_lsn, &lease_dbt, 0, 0);<br></pre>
This updating of the lease grant will occur in the <b>PERM</b> code
path when we have
successfully applied the permanent record.<br>
<h3>Maintaining Leases on the
Master/Rep_start</h3>
The master maintains a lease table that it checks when fulfilling a
read request that is subject to leases. This table is initialized
when a site calls<i>
dbenv->rep_start(DB_MASTER)</i> and the site is undergoing a role
change (i.e. a master making additional calls to <i>dbenv->rep_start(DB_MASTER)</i>
does
not affect an already existing table).<br>
<br>
When a non-master site becomes master, it must do two things related to
leases on a role change. First, a client cannot upgrade to master
while it has an outstanding lease granted to another site. If a
client attempts to do so, an error, <b>EINVAL</b>,
will be returned. The only way this should happen is if the
application simply declares a site master, instead of using
elections. Elections will already wait for leases to expire
before proceeding. (See below.)
<br>
<br>
Second, once we are proceeding with becoming a master, the site must
allocate the table it will use to maintain lease information.
This table will be sized based on <i>nsites</i>
and it will be an array of the following structure:<br>
<pre>struct {<br> int eid; /* EID of client site. */<br> db_timespec start_time; /* Unique time ID client echoes back on grants. */<br> db_timespec end_time; /* Master's lease expiration time. */<br> DB_LSN lease_lsn; /* Durable LSN this lease applies to. */<br> u_int32_t flags; /* Unused for now?? */<br>} REP_LEASE_ENTRY;<br></pre>
<h3>Granting Leases</h3>
It is the burden of the application to make sure that all sites in the
group
are using leases, or none are. Therefore, when a client processes
a <b>PERM</b>
log record that arrived from the master, it will grant its lease
automatically if that record is permanent (i.e. <b>DB_REP_ISPERM</b>
is being returned),
and leases are configured. A client will not send a
lease grant when it is processing log records (even <b>PERM</b>
ones) it receives from other clients that use client-to-client
synchronization. The reason is that the master requires a unique
time-of-msg ID (see below) that the client echoes back in its lease
grant and it will not have such an ID from another client.<br>
<br>
The master stores a time-of-msg ID in each message and the client
simply echoes it back to the master. In its lease table, it does
keep the base
time-of-msg for a valid lease. When <b>REP_LEASE_GRANT</b>
message comes in,
the master does a number of things:<br>
<ol>
<li>Pulls the echoed timespec from the client message, into <i>msg_time</i>.<br>
</li>
<li>Finds the entry in its lease table for the client's EID. It
walks the table searching for the ID. EIDs of <span
style="font-weight: bold;">DB_EID_INVALID</span> are
illegal. Either the master will find the entry, or it will find
an empty slot in the table (i.e. it is still populating the table with
leases).</li>
<li>If this is a previously unknown site lease, the master
initializes the entry by copying to the <i>eid</i>, <i>start_time, </i>and
<i>lease_lsn</i> fields. The master
also computes the <i>end_time</i>
based on the adjusted <i>rep->lease_duration</i>.</li>
<li>If this is a lease from a previously known site, the master must
perform <i>timespeccmp(&msg_time,
&table[i].start_time, >)</i> and only update the <i>end_time</i>
of the lease when this is
a more recent message. If it is a more recent message, then we
should update
the <i>lease_lsn</i> to the LSN in
the message.</li>
<li>Since lease durations are computed taking the clock skew into
account, clients compute them based on the current time and the master
computes it based on original sending time, for diagnostic purposes
only, I also plan to send the client's expiration time. The
client errs on the side of computing a larger lease expiration time and
the master errs on the side of computing a smaller duration.
Since both are taking the clock skew
into account, the client's ending expiration time should never be
smaller than
the master's computed expiration time or their value for clock skew may
not be correct.<br>
</li>
</ol>
Any log records (new or resent) that originate from the master and
result in <b>DB_REP_ISPERM</b> get an
ack.<br>
<br>
<h3>Refreshing Leases</h3>
Leases get refreshed when a master receives a <b>REP_LEASE_GRANT</b>
message from a client. There are three pieces to lease
refreshment. <br>
<h4>Lazy Lease Refreshing on Read<br>
</h4>
If the master discovers that leases are
expired during the read operation, it attempts to refresh its
collection of lease grants. It does this by calling a new
function <i>__rep_lease_refresh</i>.
This function is very similar to the already-existing function <i>__rep_flush</i>.
Basically, to
refresh the lease, the master simply needs to resend the last PERM
record to the clients. The requirements state that when the
application send function returns successfully from sending a PERM
record, the majority of clients have that PERM LSN durable. We
will have a new public DB error return called <b>DB_REP_LEASE_EXPIRED</b>
that will be
returned back to the caller if the master cannot assert its
authority. The code will look something like this:<br>
<pre>/*<br> * Use lp->max_perm_lsn on the master (currently not used on the master)<br> * to keep track of the last PERM record written through the logging system.<br> * need to initialize lp->max_perm_lsn in rep_start on role_chg.<br> */<br>call __rep_send_message on the last PERM record the master wrote, with DB_REP_PERMANENT<br>if failure<br> expire leases<br> return lease expired error to caller<br>else /* success */<br> recheck lease table<br> /*<br> * We need to recheck the lease table because the client<br> * lease grant messages may not be processed yet, or got<br> * lost, or racing with the application's ACK messages or<br> * whatever. <br> */<br> if we have a majority of valid leases<br> return success<br> else<br> return lease expired error to caller <br></pre>
<h4>Ongoing Update Refreshment<br>
</h4>
Second is having the master indicate to
the client it needs to send a lease grant in response to the current
PERM log message. The problem is
that acknowledgements must contain a master-supplied message timestamp
that the client sends back to the master. We need to modify the
structure of the log record messages when leases are configured
so
that when a PERM message is sent, the master sends, and the client
expects, the message timestamp. There are three fairly
straightforward and different implementations to consider.<br>
<ol>
<li>Adding the timestamp to the <b>REP_CONTROL</b>
structure. If this option is chosen, then the code trivially
sends back the timestamp in the client's reply. There is no
special processing done by either side with the message contents.
So, on a PERM log record, the master will send a non-zero
timestamp. On a normal log record the timestamp will be zero or
some known invalid value. If the client sees a non-zero
timestamp, it sends a <b>REP_LEASE_GRANT</b>
with the <i>lp->max_perm_lsn</i>
after applying that log record. If it is zero, then the client
does nothing different. The advantage is ease of code. The
disadvantage is that for mixed version systems, the client is now
dealing with different sized control structures. We would have to
retain the old control structure so that during a mixed version group
the (upgraded) clients can use, expect and send old control structures
to the master. This is unfortunate, so let's consider additional
implementations that don't require modifying the control structure.<br>
</li>
<li>Adding a new <b>REPCTL_LEASE</b>
flag to the list of flags for the control structure, but do not change
the control structure fields. When a master wants to send a
message that needs a lease ack, it sets the flag. Additionally,
instead of simply sending a log record DBT as the <i>rec</i> parameter
for replication, we
would send a new structure that had the timestamp first and then the
record (similar to the bulk transfer buffer). The advantage of
this is that the control structure does not change. Disadvantages
include more special-cased code in the normal code path where we have
to check the flag. If the flag is set we have to extract the
timestamp value and massage the incoming data to pass on the real log
record to <i>rep_apply</i>. On
bulk transfer, we would just add the timestamp into the buffer.
On normal transfers, it would incur an additional data copy on the
master side. That is unfortunate. Additionally, if this
record needs to be stored in the temp db, we need some way to get it
back again later or <span style="font-style: italic;">rep_apply</span>
would have to extract the timestamp out when it processed the record
(either live or from the temp db).<br>
</li>
<li>Adding a different message type, such as <b>REP_LOG_ACK</b>.
Similarly to <b>REP_LOG_MORE</b> this message would be a
special-case version of a log record. We would extract out the
timestamp and then handle as a normal log record. This
implementation is rejected because it actually would require three new
message types: <b>REP_LOG_ACK,
REP_LOG_ACK_MORE, REP_BULK_LOG_ACK</b>. That is just too ugly
to contemplate.</li>
</ol>
<b>[Slight digression:</b> it occurs
to me while writing about #2 and #3 above, that our implementation of
all of the *_MORE messages could really be implemented with a <b>REPCTL_MORE</b>
flag instead of a
separate message type. We should clean that up and simplify the
messages but not part of master leases. Hmm, taking that thought
process further, we really could get rid of the <b>REP_BULK_*</b>
messages as well if we
added a <b>REPCTL_BULK</b>
flag. I think we should definitely do it for the *_MORE
messages. I am not sure we should do it for bulk because the
structure of the incoming data record is vastly different.]<br>
<br>
Of these options, I believe that modifying the control structure is the
best alternative. The handling of the old structure will be very
isolated to code dealing with old versions and is far less complicated
than injecting the timestamp into the log record DBT and doing a data
copy. Actually, I will likely combine #1 and the flag from #2
above. I will have the <b>REPCTL_LEASE</b>
flag that indicates a lease grant reply is expected and have the
timestamp in the control structure.
Also I will probably add in a spare field or two for future use in the <b>REP_CONTROL</b>
structure.<br>
<h4>Gap processing</h4>
No matter which implementation we choose for ongoing lease refreshment,
gap processing must be considered. The code above assumes the
timestamps will be placed on PERM records only. Normal log
records will not have a timestamp, nor a flag or anything else like
that. However, any log message can fill a gap on a client and
result in the processing of that normal log record to return <b>DB_REP_ISPERM</b>
because later records
were also processed.<br>
<br>
The current implementation should work fine in that case because when
we store the message in the client temp db we store both the control
DBT and the record DBT. Therefore, when a normal record fills a
gap, the later PERM record, when retrieved will look just like it did
when it arrived. The client will have access to the LSN, and the
timestamp, etc. However, it does mean that sending the <b>REP_LEASE_GRANT</b>
message must take
place down in <i>__rep_apply</i>
because that is the only place we have access to the contents of those
stored records with the timestamps.<br>
<br>
There are two logical choices to consider for granting the lease when
processing an update. As we process (either a live record or one
read from the temp db after filling a gap) a PERM message, we send the <b>REP_LEASE_GRANT</b>
message for each
PERM record we successfully apply. Or, second, we keep track of
the largest timestamp of all PERM records we've processed and at the
end of the function after we've applied all records, we send back a
single lease grant with the <i>max_perm_lsn</i>
and a new <i>max_lease_timestamp</i>
value to the master. The first is easier to implement, the second
results in possibly slightly fewer messages at the expense of more
bookkeeping on the client.<br>
<br>
A third, more complicated option would be to have the message timestamp
on all records, but grants are only sent on the PERM messages. A
reason to do this is that the later timestamp of a normal log record
would be used as the timestamp sent in the reply and the master would
get a more up to date timestamp value and a longer lease. <br>
<br>
If we change the <span style="font-weight: bold;">REP_CONTROL</span>
structure to include the timestamp, we potentially break or at least
need to revisit the gap processing algorithm. That code assumes
that the control and record elements for the same LSN look the same
each and every time. The code stores the <span
style="font-style: italic;">control</span> DBT as the key and the <span
style="font-style: italic;">rec</span> DBT as the data. We use a
specialized compare function to sort based on the LSN in the control
DBT. With master leases, the same record transmitted by a master
multiple times or client for the same LSN will be different because the
timestamp field will not be the same. Therefore, the client will
end up with duplicate entries in the temp database for the same
LSN. Both solutions (adding the timestamp to <span
style="font-weight: bold;">REP_CONTROL</span> and adding a <span
style="font-weight: bold;">REPCTL_LEASE</span> flag) can yield
duplicate entries. The flag would cause the same record from the
master and client to be different as well.<br>
<h4>Handling Incoming Lease Grants<br>
</h4>
The third piece of lease management is handling the incoming <b>REP_LEASE_GRANT</b>
message on the
master. When this message is received, the master must do the
following:<br>
<pre>REP_SYSTEM_LOCK<br>msg_timestamp = cntrl->timestamp;<br>client_lease = __rep_lease_entry(dbenv, client eid)<br>if (client_lease == NULL)<br> initial lease for this site, DB_ASSERT there is space in the table<br> add this to the table if there is space<br>} else <br> compare msg_timestamp with client_lease->start_time<br> if (msg_timestamp is more recent && msg_lsn >= lease LSN)<br> update entry in table<br>REP_SYSTEM_UNLOCK<br></pre>
<h3>Expiring Leases</h3>
Leases can expire in two ways. First they can expire naturally
due to the passage of time. When checking leases, if the current
time is later than the lease entry's <i>end_time</i>
then the lease is expired. Second, they can be forced with a
premature expiration when the application's transport function returns
an error. In the first case, there is nothing to do, in the
second case we need to manipulate the <i>end_time</i>
so that all future lease checks fail. Since the lease <i>start_time</i>
is guaranteed to not be in the future we will have a function <i>__rep_lease_expire</i>
that will:<br>
<pre>REP_SYSTEM_LOCK<br>for each entry in the lease table<br> entry->end_time = entry->start_time;<br>REP_SYSTEM_UNLOCK<br></pre>
Is there a potential race or problem with prematurely expiring
leases? Consider an application that enforces an ALL
acknowledgement policy for PERM records in its transport
callback. There are four clients and three send the PERM ack to
the application. The callback returns an error to the master DB
code. The DB code will now prematurely expire its leases.
However, at approximately the same time the three clients are also
sending their <span style="font-weight: bold;">REP_LEASE_GRANT</span>
messages to the master. There is a race between the master
processing those messages and the thread handling the callback failure
expiring the table. This is only an issue if the messages arrive
after the table has been expired.<br>
<br>
Let's assume all three clients send their grants after the master
expires the table. If we accept those grants and then a read
occurs the read will succeed since the master has a majority of leases
even though the callback failed earlier. Is that a problem?
The lease code is using a majority and the application policy is using
something other value. It feels like this should be okay since
the data is held by leases on a majority. Should we consider
having the lease checking threshold be the same as the permanent ack
policy? That is difficult because Base API users implement
whatever they want and DB does not know what it is.<br>
<h3>Checking Leases</h3>
When a read operation on the master completes, the last thing we need
to do is verify the master leases. We've already discussed
refreshing them when they are expired above. We need two things
for a lease to be valid. It must be within the timeframe of the
lease grant and the lease must be valid for the last PERM record
LSN. Here is the logic
for checking the validity of leases in <i>__rep_lease_check</i>:<br>
<pre>#define MAX_REFRESH_TRIES 3<br>DB_LSN lease_lsn;<br>REP_LEASE_ENTRY *entry;<br>u_int32_t min_leases, valid_leases;<br>db_timespec cur_time;<br>int ret, tries;<br><br> tries = 0;<br>retry:<br> ret = 0;<br> LOG_SYSTEM_LOCK<br> lease_lsn = lp->lsn<br> LOG_SYSTEM_UNLOCK<br> REP_SYSTEM_LOCK<br> min_leases = rep->nsites / 2;<br> __os_gettime(dbenv, &cur_time);<br> for (entry = head of table, valid_leases = 0; entry != NULL && valid_leases < min_leases; entry++)<br> if (timespec_cmp(&entry->end_time, &cur_time) >= 0 && log_compare(&entry->lsn, lease_lsn) == 0)<br> valid_leases++;<br> REP_SYSTEM_UNLOCK<br> if (valid_leases < min_leases) {<br> ret =__rep_lease_refresh(dbenv, ...);<br> /*<br> * If we are successful, we need to recheck the leases because <br> * the lease grant messages may have raced with the PERM<br> * acknowledgement. Give those messages a chance to arrive.<br> */<br> if (ret == 0) {<br> if (tries <= MAX_REFRESH_TRIES) {<br> /*<br> * If we were successful sending, but not successful in racing the<br> * message thread, yield the processor so that message<br> * threads may have a chance to run.<br> */<br> if (tries > 0)<br> /* __os_sleep instead?? */<br> __os_yield()<br> tries++;<br> goto retry;<br> } else<br> ret = DB_RET_LEASE_EXPIRED;<br> }<br> }<br> return (ret);</pre>
If the master has enough valid leases it returns success. If it
does not have enough, it attempts to refresh them. This attempt
may fail if sending the PERM record does not receive sufficient
acks. If we do receive sufficient acknowledgements we may still
find that scheduling of message threads means the master hasn't yet
processed the incoming <b>REP_LEASE_GRANT</b>
messages yet. We will retry a couple times (possibly
parameterized) if the master discovers that situation. <br>
<h2>Elections</h2>
When a client grants a lease to a master, it gives up the right to
participate in an election until that grant expires. If we are
the master and <i>dbenv->rep_elect</i>
is called, it should return, no matter what, like it does today.
If we are a client and <i>rep_elect</i>
is called special processing takes place when leases are in
effect. First, the easy case is if the lease granted by this
client has already expired, then the client goes directly into the
election as normal. If a valid lease grant is outstanding to a
master, this site cannot participate in an election until that grant
expires. We have at least two options when a site calls the <i>dbenv->rep_elect</i>
API while
leases are in effect.<br>
<ol>
<li>The simplest coding solution for DB would be simply to refuse to
participate in the election if this site has a current lease granted to
a master. We would detect this situation and return EINVAL.
This is correct behavior and trivial to implement. The
disadvantage of this solution is that the application would then be
responsible for repeatedly attempting an election until the lease grant
expired.<br>
</li>
<li>The more satisfying solution is for DB to wait the remaining time
for the grant. If this client hears from the master during that
time the election does not take place and the call to <i>rep_elect</i>
returns with the
information for the current/old master.</li>
</ol>
<h3>Election Code Changes</h3>
The code changes to support leases in the election code are fairly
isolated. First if leases are configured, we must verify the <i>nsites</i>
parameter is set to 0.
Second, in <i>__rep_elect_init</i>
we must not overwrite the value of <i>rep->nsites</i>
for leases because it is controlled by the <i>dbenv->rep_set_nsites</i>
API.
These changes are small and easy to understand.<br>
<br>
The more complicated code will be the client code when it has an
outstanding lease granted. The client will wait for the current
lease grant to expire before proceeding with the election. The
client will only do so if it does not hear from the master for the
remainder of the lease grant time. If the client hears from the
master, it returns and does not begin participating in the
election. A new election phase, <b>REP_EPHASE0</b>
will exist so that the call to <i>__rep_wait</i>
can detect if a master responds. The client, while waiting for
the lease grant to expire, will send a <b>REP_MASTER_REQ</b>
message so that the master will respond with a <b>REP_NEWMASTER</b>
message and thus,
allow the client to know the master exists. However, it is also
desirable that if the master
replies to the client, the master wants the client to update its lease
grant. <br>
<br>
Recall that the <b>REP_NEWMASTER</b>
message does not result in a lease grant from the client. The
client responds when it processes a PERM record that has the <b>REPCTL_LEASE</b>
flag set in the message
with its lease grant up to the given LSN. Therefore, we want the
client's <b>REP_MASTER_REQ</b> to
yield both the discovery of the existing master and have the master
refresh its leases. The client will also use the <b>REPCTL_LEASE</b>
flag in its <b>REP_MASTER_REQ</b> message to the
master. This flag will serve as the indicator to the master that
it needs to deal with leases and both send the <b>REP_NEWMASTER</b>
message and refresh
the lease.<br>
The code will work as follows:<br>
<pre>if (leases_configured && (my_grant_still_valid || lease_never_granted) {<br> if (lease_never_granted)<br> wait_time = lease_timeout<br> else<br> wait_time = grant_expiration - current_time<br> F_SET(REP_F_EPHASE0);<br> __rep_send_message(..., REP_MASTER_REQ, ... REPCTL_LEASE);<br> ret = __rep_wait(..., REP_F_EPHASE0);<br> if (we found a master)<br> return<br>} /* if we don't return, fall out and proceed with election */<br></pre>
On the master side, the code handling the <b>REP_MASTER_REQ</b> will
do:<br>
<pre>if (I am master) {<br> ...<br> __rep_send_message(REP_NEWMASTER...)<br> if (F_ISSET(rp, REPCTL_LEASE))<br> __rep_lease_refresh(...)<br>}<br></pre>
Other minor implementation details are that<i> __rep_elect_done</i>
must also clear
the <b>REP_F_EPHASE0</b> flag.
We also, obviously, need to define <b>REP_F_EPHASE0</b>
in the list of replication flags. Note that the client's call to <i>__rep_wait</i>
will return upon
receiving the <b>REP_NEWMASTER</b>
message. The client will independently refresh its lease when it
receives the log record from the master's call to refresh the lease.<br>
<br>
Again, similar to what I suggested above, the code could simply assume
global leases are configured, and instead of having the <b>REPCTL_LEASE</b>
flag at all, the master
assumes that it needs to refresh leases because it has them configured,
not because it is specified in the <b>REP_MASTER_REQ</b>
message it is processing. Right now I don't think every possible
<b>REP_MASTER_REQ</b> message should result in a lease grant request.<br>
<h4>Elections and Quiescient Systems</h4>
It is possible that a master is slow or the client is close to its
expiration time, or that the master is quiescient and all leases are
currently expired, but nothing much is going on anyway, yet some client
calls <i>__rep_elect</i> at that
time. In the code above, we will not send the <b>REP_MASTER_REQ</b>
because the lease is
not valid. The client will simply proceed directly to sending the
<b>REP_VOTE1</b> message, throwing all
other clients into an election. The master is still master and
should stay that way. Currently in response to a vote message, a
master will broadcast out a <b>REP_NEWMASTER</b>
to assert its mastership. That causes the election to
complete. However, if desired the master may want to proactively
refresh its leases. This situation indicates to me that the
master should choose to refresh leases based on configuration, not a
flag sent from the client. I believe anytime the master asserts
its mastership via sending a <b>REP_NEWMASTER</b>
message that I need to add code to proactively refresh leases at that
time.<br>
<h2>Other Implementation Details</h2>
<h3>Role Changes<br>
</h3>
When a site changes its role via a call to <i>rep_start</i> in either
direction, we
must take action when leases are configured. There are three
types of role changes that all need changes to deal with leases:<br>
<ol>
<li><i>A master downgrading to a
client.</i> When a master downgrades to a client, it can do so
immediately after it has proactively expired all existing leases it
holds. This situation is similar to an error from the send
callback, and it effectively cancels all outstanding leases held on
this site. Note that if this master expires its leases, it does
not have any effect on when the clients' lease grants expire on the
client side. The clients must still wait their full expected
grant time.<br>
</li>
<li><i>A client upgrading to master.</i>
If a client is upgrading to a master but it has an outstanding lease
granted to another site, the code will return an <b>EINVAL</b>
error. This situation
only arises if the application simply declares this site master.
If a site wins an election then the election itself should have waited
long enough for the granted lease to expire and this state should not
arise then.</li>
<li><i>A client finding a new master.</i>
When a client discovers a new and different master, via a <b>REP_NEWMASTER</b>
message then the
client cannot accept that new master until its current lease grant
expires. This situation should only occur when a site declares
itself master without an election and that site's lease grant expires
before this client's grant expires. However, it is <b>possible</b>
for this situation to arise
with elections also. If we have 5 sites holding an election and 4
of those sites have leases expire at about the same time T, and this
site's lease expires at time T+N and the election timeout is < N,
then those 4 sites may hold an election and elect a master without this
site's participation. A client in this situation must call <i>__rep_wait</i>
with the time remaining
on its lease. If the lease is expired after waiting the remaining
time, then the client can accept this new master. If the lease
was refreshed during the waiting period then the client does not accept
this new master and returns.<br>
</li>
</ol>
<h3>DUPMASTER</h3>
A duplicate master situation can occur if an old master becomes
disconnected from the rest of the group, that group elects a new master
and then the partition is resolved. The requirement for master
leases is that this situation will not cause the newly elected,
rightful master to receive the <b>DB_REP_DUPMASTER</b>
return. It is okay for the old master to get that return
value. When a dual master situation exists, the following will
happen:<br>
<ul>
<li><i>On the current master and all
current clients</i> - If the current master receives an update
message or other conflicting message from the old master then that
message will be ignored because the generation number is out of date.</li>
<li><i>On the old master</i> - If
the old master receives an update message from the current master, or
any other message with a later generation from any site, the new
generation number will trigger this site to return <b>DB_REP_DUPMASTER</b>.
However,
instead of broadcasting out the <b>REP_DUPMASTER</b>
message to shoot down others as well, this site, if leases are
configured, will call <i>__rep_lease_check</i>
and if they are expired, return the error. It should be
impossible for us to receive a later generation message and still hold
a majority of master leases. Something is seriously wrong and we
will <b>DB_ASSERT</b> this situation
cannot happen.<br>
</li>
</ul>
<h3>Client to Client Synchronization</h3>
One question to ask is how lease grants interact with client-to-client
synchronization. The only answer is that they do not. A client
that is sending log records to another client cannot request the
receiving client refresh its lease with the master. That client
does not have a timestamp it can use for the master and clock skew
makes it meaningless between machines. Therefore, sites that use
client-to-client synchronization will likely see more lease refreshment
during the read path and leases will be refreshed during live updates
only. Of course, if a client supplies log records that fill a
gap, and the later log records stored came from the master in a live
update then the client will respond as per the discussion on Gap
Processing above.<br>
<h2>Interaction Matrix</h2>
If leases are granted (by a client) or held (by a master) what should
the following APIs and messages do?<br>
<br>
Other:<br>
log_archive: Leases do not affect log_archive. OK.<br>
dbenv->close: OK.<br>
crash during lease grant and restart: <b>Potential
problem here. See discussion below</b>.<br>
<br>
Rep Base API method:<br>
rep_elect: Already discussed above. Must wait for lease to expire.<br>
rep_flush: Master only, OK - this will be the basis for refreshing
leases.<br>
rep_get_*: Not affected by leases.<br>
rep_process_message: Generally OK. We'll discuss each message
below.<br>
rep_set_config: OK.<br>
rep_set_limit: OK<br>
rep_set_nsites: Must be called before <i>rep_start</i>
and <i>nsites</i> is immutable until
14778 is resolved.<br>
rep_set_priority: OK<br>
rep_set_timeout: OK. Used to set lease timeout.<br>
rep_set_transport: OK.<br>
rep_start(MASTER): Role changes are discussed above. Make sure
duplicate rep_start calls are no-ops for leases.<br>
rep_start(CLIENT): Role changes are discussed above. Make sure
duplicate calls are no-ops for leases.<br>
rep_stat: OK.<br>
rep_sync: Should not be able to happen. Client cannot accept new
master with outstanding lease grant. Add DB_ASSERT here.<br>
<br>
REP_ALIVE: OK.<br>
REP_ALIVE_REQ: OK.<br>
REP_ALL_REQ: OK.<br>
REP_BULK_LOG: OK. Clients check to send ACK.<br>
REP_BULK_PAGE: Should never process one with lease granted. Add
DB_ASSERT.<br>
REP_DUPMASTER: Should never happen, this is what leases are supposed to
prevent. See above.<br>
REP_LOG: OK. Clients check to send ACK.<br>
REP_LOG_MORE: OK. Clients check to send ACK.<br>
REP_LOG_REQ: OK.<br>
REP_MASTER_REQ: OK.<br>
REP_NEWCLIENT: OK.<br>
REP_NEWFILE: OK. Clients check to send ACK.<br>
REP_NEWMASTER: See above.<br>
REP_NEWSITE: OK.<br>
REP_PAGE: OK. Should never process one with lease granted.
Add DB_ASSERT.<br>
REP_PAGE_FAIL: OK. Should never process one with lease
granted. Add DB_ASSERT.<br>
REP_PAGE_MORE: OK. Should never process one with lease
granted. Add DB_ASSERT.<br>
REP_PAGE_REQ: OK.<br>
REP_REREQUEST: OK.<br>
REP_UPDATE: OK. Should never process one with lease
granted. Add DB_ASSERT.<br>
REP_UPDATE_REQ: OK. This is a master-only message.<br>
REP_VERIFY: OK. Should never process one with lease
granted. Add DB_ASSERT.<br>
REP_VERIFY_FAIL: OK. Should never process one with lease
granted. Add DB_ASSERT.<br>
REP_VERIFY_REQ: OK.<br>
REP_VOTE1: OK. See Election discussion above. It is
possible to receive one with a lease granted. Client cannot send
one with an outstanding lease however.<br>
REP_VOTE2: OK. See Election discussion above. It is
possible to receive one with a lease granted.<br>
<br>
If the following method or message processing is in progress and a
client wants to grant a lease, what should it do? Let's examine
what this means. The client wanting to grant a lease simply means
it is responding to the receipt of a <b>REP_LOG</b>
(or its variants) message and applying a log record. Therefore,
we need to consider a thread processing a log message racing with these
other actions.<br>
<br>
Other:<br>
log_archive: OK. <br>
dbenv->close: User error. User should not be closing the env
while other threads are using that handle. Should have no effect
if a 2nd dbenv handle to same env is closed.<br>
<br>
Rep Base API method:<br>
rep_elect: See Election discussion above. <i>rep_elect</i>
should wait and may grant
lease while election is in progress.<br>
rep_flush: Should not be called on client.<br>
rep_get_*: OK.<br>
rep_process_message: Generally OK. See handling each message
below.<br>
rep_set_config: OK.<br>
rep_set_limit: OK.<br>
rep_set_nsites: Must be called before <i>rep_start</i>
until 14778 is resolved.<br>
rep_set_priority: OK.<br>
rep_set_timeout: OK.<br>
rep_set_transport: OK.<br>
rep_start(MASTER): OK, can't happen - already protect racing <i>rep_start</i>
and <i>rep_process_message</i>.<br>
rep_start(CLIENT): OK, can't happen - already protect racing <i>rep_start</i>
and <i>rep_process_message</i>.<br>
rep_stat: OK.<br>
rep_sync: Shouldn't happen because client cannot grant leases during
sync-up. Incoming log message ignored.<br>
<br>
REP_ALIVE: OK.<br>
REP_ALIVE_REQ: OK.<br>
REP_ALL_REQ: OK.<br>
REP_BULK_LOG: OK.<br>
REP_BULK_PAGE: OK. Incoming log message ignored during internal
init.<br>
REP_DUPMASTER: Shouldn't happen. See DUPMASTER discussion above.<br>
REP_LOG: OK.<br>
REP_LOG_MORE: OK.<br>
REP_LOG_REQ: OK.<br>
REP_MASTER_REQ: OK.<br>
REP_NEWCLIENT: OK.<br>
REP_NEWFILE: OK.<br>
REP_NEWMASTER: See above. If a client accepts a new master
because its lease grant expired, then that master sends a message
requesting the lease grant, this client will not process the log record
if it is in sync-up recovery, or it may after the master switch is
complete and the client doesn't need sync-up recovery. Basically,
just uses existing log record processing/newmaster infrastructure.<br>
REP_NEWSITE: OK.<br>
REP_PAGE: OK. Receiving a log record during internal init PAGE
phase should ignore log record.<br>
REP_PAGE_FAIL: OK.<br>
REP_PAGE_MORE: OK.<br>
REP_PAGE_REQ: OK.<br>
REP_REREQUEST: OK.<br>
REP_UPDATE: OK. Receiving a log record during internal init
should ignore log record.<br>
REP_UPDATE_REQ: OK - master-only message.<br>
REP_VERIFY: OK. Receiving a log record during verify phase
ignores log record.<br>
REP_VERIFY_FAIL: OK.<br>
REP_VERIFY_REQ: OK.<br>
REP_VOTE1: OK. This client is processing someone else's vote when
the lease request comes in. That is fine. We protect our
own election and lease interaction in <i>__rep_elect</i>.<br>
REP_VOTE2: OK.<br>
<h4>Crashing - Potential Problem<br>
</h4>
It appears there is one area where we could have a problem. I
believe that crashes can cause us to break our guarantee on durability,
authoritative reads and inability to elect duplicate masters.
Consider this scenario:<br>
<ol>
<li>A master and 4 clients are all up and running.</li>
<li>The master commits a txn and all 4 clients refresh their lease
grants at time T.</li>
<li>All 4 clients have the txn and log records in the cache.
None are flushing to disk.</li>
<li>All 4 clients have responded to the PERM messages as well as
refreshed their lease with the master.</li>
<li>All 4 clients hit the same application coding error and crash
(machine/OS stays up).</li>
<li>Master authoritatively reads data in txn from step 2.</li>
<li>All 4 clients restart the application and run recovery, thus the
txn from step 2 is lost on all clients because it isn't any logs.<span
style="font-weight: bold;"></span><br>
</li>
<li>A network partition happens and the master is alone on its side.</li>
<li>All 4 clients are on the other side and elect a new master.</li>
<li>Partition resolves itself and we have duplicate masters, where
the former master still holds all valid lease grants.<span
style="font-weight: bold;"></span><br>
</li>
</ol>
Therefore, we have broken both guarantees. In step 6 the data is
really not durable and we've given it to the user. One can argue
that if this is an issue the application better be syncing somewhere if
they really want durability. However, worse than that is that we
have a legitimate DUPMASTER situation in step 10 where both masters
hold valid leases. The reason is that all lease knowledge is in
the shared memory and that is lost when the app restarts and runs
recovery.<br>
<br>
How can we solve this? The obvious solution is (ugh, yet another)
durable BDB-owned file with some information in it, such as the current
lease expiration time so that rebooting after a crash leaves the
knowledge that the lease was granted. However, writing and
syncing every lease grant on every client out to disk is far too
expensive.<br>
<br>
A second possible solution is to have clients wait a full lease timeout
before entering an election the first time. This solution solves the
DUPMASTER issue, but not the non-authoritative read. This
solution naturally falls out of elections and leases really. If a
client has never granted a lease, it should be considered as having to
wait a full lease timeout before entering an election.
Applications already know that leases impact elections and this does
not seem so bad as it is only on the first election.<br>
<br>
Is it sufficient to document that the authoritative read is only as
authoritative as the durability guarantees they make on the sites that
indicate it is permanent? Yes, I believe this is sufficient. If
the application says it is permanent and it really isn't, then the
application is at fault. Believing the application when it
indicates with the PERM response that it is permanent avoids the
authoritative problem. <br>
<h2>Upgrade/Mixed Versions</h2>
Clearly leases cannot be used with mixed version sites since masters
running older releases will not have any knowledge of lease
support. What considerations are needed in the lease code for
mixed versions?<br>
<br>
First if the <b>REP_CONTROL</b>
structure changes, we need to maintain and use an old version of the
structure for talking to older clients and masters. The
implementation of this would be similar to the way we manage for old <b>REP_VOTE_INFO</b>
structures.
Second any new messages need translation table entries added.
Third, if we are assuming global leases then clearly any mixed versions
cannot have leases configured, and leases cannot be used in mixed
version groups. Maintaining two versions of the control structure
is not necessary if we choose a different style of implementation and
don't change the control structure.<br>
<br>
However, then how could an old application both run continuously,
upgrade to the new release and take advantage of leases without taking
down the entire application? I believe it is possible for clients
to be configured for leases but be subject to the master regarding
leases, yet the master code can assume that if it has leases
configured, all client sites do as well. In several places above
I suggested that a client could make a choice based on either a new <b>REPCTL_LEASE</b>
flag or simply having
leases turned on locally. If we choose to use the flag, then we
can support leases with mixed versions. The upgraded clients can
configure leases and they simply will not be granted until the old
master is upgraded and send PERM message with the flag indicating it
wants a lease grant. The client will not grant a lease until such
time. The clients, while having the leases configured, will not
grant a lease until told to do so and will simply have an expired
lease. Then, when the old master finally upgrades, it too can
configure leases and suddenly all sites are using them. I believe
this should work just fine and I will need to make sure a client's
granting of leases is only in response to the master asking for a
grant. If the master never asks, then the client has them
configured, but doesn't grant them.<br>
<h2>Testing</h2>
Clearly any user-facing API changes will need the equivalent reflection
in the Tcl API for testing, under CONFIG_TEST.<br>
<br>
I am sure the list of tests will grow but off the top of my head:<br>
Basic test: have N sites all configure leases, run some, read on
master, etc.<br>
Refresh test: Perform update on master, sleep until past expiration,
read on master and make sure leases are refreshed/read successful<br>
Error test: Test error conditions (reading on client with leases but no
ignore flag, calling after rep_start, etc)<br>
Read test: Test reading on both client and master both with and without
the IGNORE flag. Test that data read with the ignore flag can be
rolled back.<br>
Dupmaster test: Force a DUPMASTER situation and verify that the newer
master cannot get DUPMASTER error.<br>
Election test: Call election while grant is outstanding and master
exists.<br>
Call election while grant is outstanding and master does not exist.<br>
Call election after expiration on quiescient system with master
existing.<br>
Run with a group where some members have leases configured and other do
not to make sure we get errors instead of dumping core.<br>
<br>
<small><br>
</small>
</body>
</html>
|
