~ubuntu-branches/ubuntu/quantal/ceph/quantal

« back to all changes in this revision

Viewing changes to src/mon/Paxos.h

  • Committer: Package Import Robot
  • Author(s): James Page
  • Date: 2012-07-16 09:56:24 UTC
  • mfrom: (0.3.11)
  • mto: This revision was merged to the branch mainline in revision 17.
  • Revision ID: package-import@ubuntu.com-20120716095624-azr2w4hbhei1rxmx
Tags: upstream-0.48
ImportĀ upstreamĀ versionĀ 0.48

Show diffs side-by-side

added added

removed removed

Lines of Context:
35
35
 
36
36
*/
37
37
 
38
 
 
39
 
/*
40
 
 * NOTE: This libary is based on the Paxos algorithm, but varies in a few key ways:
41
 
 *  1- Only a single new value is generated at a time, simplifying the recovery logic.
42
 
 *  2- Nodes track "committed" values, and share them generously (and trustingly)
43
 
 *  3- A 'leasing' mechism is built-in, allowing nodes to determine when it is safe to 
44
 
 *     "read" their copy of the last committed value.
45
 
 *
46
 
 * This provides a simple replication substrate that services can be built on top of.
47
 
 * See PaxosService.h
48
 
 */
49
 
 
50
38
#ifndef CEPH_MON_PAXOS_H
51
39
#define CEPH_MON_PAXOS_H
52
40
 
66
54
 
67
55
 
68
56
// i am one state machine.
 
57
/**
 
58
 * This libary is based on the Paxos algorithm, but varies in a few key ways:
 
59
 *  1- Only a single new value is generated at a time, simplifying the recovery logic.
 
60
 *  2- Nodes track "committed" values, and share them generously (and trustingly)
 
61
 *  3- A 'leasing' mechism is built-in, allowing nodes to determine when it is 
 
62
 *     safe to "read" their copy of the last committed value.
 
63
 *
 
64
 * This provides a simple replication substrate that services can be built on top of.
 
65
 * See PaxosService.h
 
66
 */
69
67
class Paxos {
 
68
  /**
 
69
   * @defgroup Paxos_h_class Paxos
 
70
   * @{
 
71
   */
 
72
  /**
 
73
   * The Monitor to which this Paxos class is associated with.
 
74
   */
70
75
  Monitor *mon;
71
76
 
72
77
  // my state machine info
75
80
 
76
81
  friend class Monitor;
77
82
  friend class PaxosService;
78
 
  friend class PaxosObserver;
79
83
 
80
84
  list<std::string> extra_state_dirs;
81
85
 
83
87
 
84
88
  // -- generic state --
85
89
public:
86
 
  const static int STATE_RECOVERING = 1;  // leader|peon: recovering paxos state
87
 
  const static int STATE_ACTIVE     = 2;  // leader|peon: idle.  peon may or may not have valid lease
88
 
  const static int STATE_UPDATING   = 3;  // leader|peon: updating to new value
 
90
  /**
 
91
   * @defgroup Paxos_h_states States on which the leader/peon may be.
 
92
   * @{
 
93
   */
 
94
  /**
 
95
   * Leader/Peon is in Paxos' Recovery state
 
96
   */
 
97
  const static int STATE_RECOVERING = 1;
 
98
  /**
 
99
   * Leader/Peon is idle, and the Peon may or may not have a valid lease.
 
100
   */
 
101
  const static int STATE_ACTIVE     = 2;
 
102
  /**
 
103
   * Leader/Peon is updating to a new value.
 
104
   */
 
105
  const static int STATE_UPDATING   = 3;
 
106
 
 
107
  /**
 
108
   * Obtain state name from constant value.
 
109
   *
 
110
   * @note This function will raise a fatal error if @p s is not
 
111
   *       a valid state value.
 
112
   *
 
113
   * @param s State value.
 
114
   * @return The state's name.
 
115
   */
89
116
  static const char *get_statename(int s) {
90
117
    switch (s) {
91
118
    case STATE_RECOVERING: return "recovering";
96
123
  }
97
124
 
98
125
private:
 
126
  /**
 
127
   * The state we are in.
 
128
   */
99
129
  int state;
 
130
  /**
 
131
   * @}
 
132
   */
100
133
 
101
134
public:
 
135
  /**
 
136
   * Check if we are recovering.
 
137
   *
 
138
   * @return 'true' if we are on the Recovering state; 'false' otherwise.
 
139
   */
102
140
  bool is_recovering() const { return state == STATE_RECOVERING; }
 
141
  /**
 
142
   * Check if we are active.
 
143
   *
 
144
   * @return 'true' if we are on the Active state; 'false' otherwise.
 
145
   */
103
146
  bool is_active() const { return state == STATE_ACTIVE; }
 
147
  /**
 
148
   * Check if we are updating.
 
149
   *
 
150
   * @return 'true' if we are on the Updating state; 'false' otherwise.
 
151
   */
104
152
  bool is_updating() const { return state == STATE_UPDATING; }
105
153
 
106
154
private:
107
 
  // recovery (phase 1)
 
155
  /**
 
156
   * @defgroup Paxos_h_recovery_vars Common recovery-related member variables
 
157
   * @note These variables are common to both the Leader and the Peons.
 
158
   * @{
 
159
   */
 
160
  /**
 
161
   *
 
162
   */
108
163
  version_t first_committed;
 
164
  /**
 
165
   * Last Proposal Number
 
166
   *
 
167
   * @todo Expand description
 
168
   */
109
169
  version_t last_pn;
 
170
  /**
 
171
   * Last committed value's version.
 
172
   *
 
173
   * On both the Leader and the Peons, this is the last value's version that 
 
174
   * was accepted by a given quorum and thus committed, that this instance 
 
175
   * knows about.
 
176
   *
 
177
   * @note It may not be the last committed value's version throughout the
 
178
   *       system. If we are a Peon, we may have not been part of the quorum
 
179
   *       that accepted the value, and for this very same reason we may still
 
180
   *       be a (couple of) version(s) behind, until we learn about the most
 
181
   *       recent version. This should only happen if we are not active (i.e.,
 
182
   *       part of the quorum), which should not happen if we are up, running
 
183
   *       and able to communicate with others -- thus able to be part of the
 
184
   *       monmap and trigger new elections.
 
185
   */
110
186
  version_t last_committed;
 
187
  /**
 
188
   * Last committed value's time.
 
189
   *
 
190
   * When the commit happened.
 
191
   */
111
192
  utime_t last_commit_time;
 
193
  /**
 
194
   * The last Proposal Number we have accepted.
 
195
   *
 
196
   * On the Leader, it will be the Proposal Number picked by the Leader 
 
197
   * itself. On the Peon, however, it will be the proposal sent by the Leader
 
198
   * and it will only be updated iif its value is higher than the one
 
199
   * already known by the Peon.
 
200
   */
112
201
  version_t accepted_pn;
 
202
  /**
 
203
   * @todo This has something to do with the last_committed version. Not sure
 
204
   *       about what it entails, tbh.
 
205
   */
113
206
  version_t accepted_pn_from;
114
 
  map<int,version_t> peer_first_committed, peer_last_committed;
 
207
  /**
 
208
   * @todo Check out if this map has any purpose at all. So far, we have only
 
209
   *       seen it being read, although it is never affected.
 
210
   */
 
211
  map<int,version_t> peer_first_committed;
 
212
  /**
 
213
   * Map holding the last committed version by each quorum member.
 
214
   *
 
215
   * The versions kept in this map are updated during the collect phase.
 
216
   * When the Leader starts the collect phase, each Peon will reply with its
 
217
   * last committed version, which will then be kept in this map.
 
218
   */
 
219
  map<int,version_t> peer_last_committed;
 
220
  /**
 
221
   * @todo Check out what 'slurping' is.
 
222
   */
115
223
  int slurping;
 
224
  /**
 
225
   * @}
 
226
   */
116
227
 
117
228
  // active (phase 2)
 
229
  /**
 
230
   * @defgroup Paxos_h_active_vars Common active-related member variables
 
231
   * @{
 
232
   */
 
233
  /**
 
234
   * When does our read lease expires.
 
235
   *
 
236
   * Instead of performing a full commit each time a read is requested, we
 
237
   * keep leases. Each lease will have an expiration date, which may or may
 
238
   * not be extended. This member variable will keep when is the lease 
 
239
   * expiring.
 
240
   */
118
241
  utime_t lease_expire;
 
242
  /**
 
243
   * List of callbacks waiting for our state to change into STATE_ACTIVE.
 
244
   */
119
245
  list<Context*> waiting_for_active;
 
246
  /**
 
247
   * List of callbacks waiting for the chance to read a version from us.
 
248
   *
 
249
   * Each entry on the list may result from an attempt to read a version that
 
250
   * wasn't available at the time, or an attempt made during a period during
 
251
   * which we could not satisfy the read request. The first case happens if
 
252
   * the requested version is greater than our last committed version. The
 
253
   * second scenario may happen if we are recovering, or if we don't have a
 
254
   * valid lease.
 
255
   *
 
256
   * The list will be woken up once we change to STATE_ACTIVE with an extended
 
257
   * lease -- which can be achieved if we have everyone on the quorum on board
 
258
   * with the latest proposal, or if we don't really care about the remaining
 
259
   * uncommitted values --, or if we're on a quorum of one.
 
260
   */
120
261
  list<Context*> waiting_for_readable;
121
262
 
 
263
  /**
 
264
   * Latest version written to the store after the latest commit.
 
265
   */
122
266
  version_t latest_stashed;
 
267
  /**
 
268
   * @}
 
269
   */
123
270
 
124
271
  // -- leader --
125
272
  // recovery (paxos phase 1)
 
273
  /**
 
274
   * @defgroup Paxos_h_leader_recovery Leader-specific Recovery-related vars
 
275
   * @{
 
276
   */
 
277
  /**
 
278
   * Number of replies to the collect phase we've received so far.
 
279
   *
 
280
   * This variable is reset to 1 each time we start a collect phase; it is
 
281
   * incremented each time we receive a reply to the collect message, and
 
282
   * is used to determine whether or not we have received replies from the
 
283
   * whole quorum.
 
284
   */
126
285
  unsigned   num_last;
 
286
  /**
 
287
   * Uncommitted value's version.
 
288
   *
 
289
   * If we have, or end up knowing about, an uncommitted value, then its
 
290
   * version will be kept in this variable.
 
291
   *
 
292
   * @note If this version equals @p last_committed+1 when we reach the final
 
293
   *       steps of recovery, then the algorithm will assume this is a value
 
294
   *       the Leader does not know about, and trustingly the Leader will 
 
295
   *       propose this version's value.
 
296
   */
127
297
  version_t  uncommitted_v;
 
298
  /**
 
299
   * Uncommitted value's Proposal Number.
 
300
   *
 
301
   * We use this variable to assess if the Leader should take into consideration
 
302
   * an uncommitted value sent by a Peon. Given that the Peon will send back to
 
303
   * the Leader the last Proposal Number he accepted, the Leader will be able
 
304
   * to infer if this value is more recent than the one the Leader has, thus
 
305
   * more relevant.
 
306
   */
128
307
  version_t  uncommitted_pn;
 
308
  /**
 
309
   * Uncommitted Value.
 
310
   *
 
311
   * If the system fails in-between the accept replies from the Peons and the
 
312
   * instruction to commit from the Leader, then we may end up with accepted
 
313
   * but yet-uncommitted values. During the Leader's recovery, he will attempt
 
314
   * to bring the whole system to the latest state, and that means committing
 
315
   * past accepted but uncommitted values.
 
316
   *
 
317
   * This variable will hold an uncommitted value, which may originate either
 
318
   * on the Leader, or learnt by the Leader from a Peon during the collect
 
319
   * phase.
 
320
   */
129
321
  bufferlist uncommitted_value;
130
 
 
 
322
  /**
 
323
   * Used to specify when an on-going collect phase times out.
 
324
   */
131
325
  Context    *collect_timeout_event;
 
326
  /**
 
327
   * @}
 
328
   */
132
329
 
133
330
  // active
 
331
  /**
 
332
   * @defgroup Paxos_h_leader_active Leader-specific Active-related vars
 
333
   * @{
 
334
   */
 
335
  /**
 
336
   * Set of participants (Leader & Peons) that have acked a lease extension.
 
337
   *
 
338
   * Each Peon that acknowledges a lease extension will have its place in this
 
339
   * set, which will be used to account for all the acks from all the quorum
 
340
   * members, guaranteeing that we trigger new elections if some don't ack in
 
341
   * the expected timeframe.
 
342
   */
134
343
  set<int>   acked_lease;
 
344
  /**
 
345
   * Callback responsible for extending the lease periodically.
 
346
   */
135
347
  Context    *lease_renew_event;
 
348
  /**
 
349
   * Callback to trigger new elections once the time for acks is out.
 
350
   */
136
351
  Context    *lease_ack_timeout_event;
 
352
  /**
 
353
   * @}
 
354
   */
 
355
  /**
 
356
   * @defgroup Paxos_h_peon_active Peon-specific Active-related vars
 
357
   * @{
 
358
   */
 
359
  /**
 
360
   * Callback to trigger new elections when the Peon's lease times out.
 
361
   *
 
362
   * If the Peon's lease is extended, this callback will be reset (i.e.,
 
363
   * we cancel the event and reschedule a new one with starting from the
 
364
   * beginning).
 
365
   */
137
366
  Context    *lease_timeout_event;
 
367
  /**
 
368
   * @}
 
369
   */
138
370
 
139
371
  // updating (paxos phase 2)
 
372
  /**
 
373
   * @defgroup Paxos_h_leader_updating Leader-specific Updating-related vars
 
374
   * @{
 
375
   */
 
376
  /**
 
377
   * New Value being proposed to the Peons.
 
378
   *
 
379
   * This bufferlist holds the value the Leader is proposing to the Peons, and
 
380
   * that will be committed if the Peons do accept the proposal.
 
381
   */
140
382
  bufferlist new_value;
 
383
  /**
 
384
   * Set of participants (Leader & Peons) that accepted the new proposed value.
 
385
   *
 
386
   * This set is used to keep track of those who have accepted the proposed
 
387
   * value, so the leader may know when to issue a commit (when a majority of
 
388
   * participants has accepted the proposal), and when to extend the lease
 
389
   * (when all the quorum members have accepted the proposal).
 
390
   */
141
391
  set<int>   accepted;
142
 
 
 
392
  /**
 
393
   * Callback to trigger a new election if the proposal is not accepted by the
 
394
   * full quorum within a given timeframe.
 
395
   *
 
396
   * If the full quorum does not accept the proposal, then it means that the
 
397
   * Leader may no longer be recognized as the leader, or that the quorum has
 
398
   * changed, and the value may have not reached all the participants. Thus,
 
399
   * the leader must call new elections, and go through a recovery phase in
 
400
   * order to propagate the new value throughout the system.
 
401
   *
 
402
   * This does not mean that we won't commit. We will commit as soon as we
 
403
   * have a majority of acceptances. But if we do not have full acceptance
 
404
   * from the quorum, then we cannot extend the lease, as some participants
 
405
   * may not have the latest committed value.
 
406
   */
143
407
  Context    *accept_timeout_event;
144
408
 
 
409
  /**
 
410
   * List of callbacks waiting for it to be possible to write again.
 
411
   *
 
412
   * @remarks It is not possible to write if we are not the Leader, or we are
 
413
   *          not on the active state, or if the lease has expired.
 
414
   */
145
415
  list<Context*> waiting_for_writeable;
 
416
  /**
 
417
   * List of callbacks waiting for a commit to finish.
 
418
   *
 
419
   * @remarks This may be used to a) wait for an on-going commit to finish
 
420
   *          before we proceed with, say, a new proposal; or b) wait for the
 
421
   *          next commit to be finished so we are sure that our value was
 
422
   *          fully committed.
 
423
   */
146
424
  list<Context*> waiting_for_commit;
147
 
 
148
 
  // observers
149
 
  struct Observer {
150
 
    entity_inst_t inst;
151
 
    version_t last_version;
152
 
    utime_t timeout;
153
 
    Observer(entity_inst_t& ei, version_t v) : inst(ei), last_version(v) { }
154
 
  };
155
 
  map<entity_inst_t, Observer *> observers;
156
 
 
157
 
  //synchronization warnings
 
425
  /**
 
426
   * @}
 
427
   */
 
428
 
 
429
  /**
 
430
   * @defgroup Paxos_h_sync_warns Synchronization warnings
 
431
   * @todo Describe these variables
 
432
   * @{
 
433
   */
158
434
  utime_t last_clock_drift_warn;
159
435
  int clock_drift_warned;
160
 
 
161
 
 
 
436
  /**
 
437
   * @}
 
438
   */
 
439
 
 
440
 
 
441
  /**
 
442
   * @defgroup Paxos_h_callbacks Callback classes.
 
443
   * @{
 
444
   */
 
445
  /**
 
446
   * Callback class responsible for handling a Collect Timeout.
 
447
   */
162
448
  class C_CollectTimeout : public Context {
163
449
    Paxos *paxos;
164
450
  public:
168
454
    }
169
455
  };
170
456
 
 
457
  /**
 
458
   * Callback class responsible for handling an Accept Timeout.
 
459
   */
171
460
  class C_AcceptTimeout : public Context {
172
461
    Paxos *paxos;
173
462
  public:
177
466
    }
178
467
  };
179
468
 
 
469
  /**
 
470
   * Callback class responsible for handling a Lease Ack Timeout.
 
471
   */
180
472
  class C_LeaseAckTimeout : public Context {
181
473
    Paxos *paxos;
182
474
  public:
186
478
    }
187
479
  };
188
480
 
 
481
  /**
 
482
   * Callback class responsible for handling a Lease Timeout.
 
483
   */
189
484
  class C_LeaseTimeout : public Context {
190
485
    Paxos *paxos;
191
486
  public:
195
490
    }
196
491
  };
197
492
 
 
493
  /**
 
494
   * Callback class responsible for handling a Lease Renew Timeout.
 
495
   */
198
496
  class C_LeaseRenew : public Context {
199
497
    Paxos *paxos;
200
498
  public:
203
501
      paxos->lease_renew_timeout();
204
502
    }
205
503
  };
206
 
 
207
 
 
 
504
  /**
 
505
   * @}
 
506
   */
 
507
 
 
508
  /**
 
509
   * @defgroup Paxos_h_election_triggered Steps triggered by an election.
 
510
   *
 
511
   * @note All these functions play a significant role in the Recovery Phase,
 
512
   *       which is triggered right after an election once someone becomes
 
513
   *       the Leader.
 
514
   * @{
 
515
   */
 
516
  /**
 
517
   * Create a new Proposal Number and propose it to the Peons.
 
518
   *
 
519
   * This function starts the Recovery Phase, which can be directly mapped
 
520
   * onto the original Paxos' Prepare phase. Basically, we'll generate a
 
521
   * Proposal Number, taking @p oldpn into consideration, and we will send
 
522
   * it to a quorum, along with our first and last committed versions. By
 
523
   * sending these informations in a message to the quorum, we expect to
 
524
   * obtain acceptances from a majority, allowing us to commit, or be
 
525
   * informed of a higher Proposal Number known by one or more of the Peons
 
526
   * in the quorum.
 
527
   *
 
528
   * @pre We are the Leader.
 
529
   * @post Recovery Phase initiated by sending messages to the quorum.
 
530
   *
 
531
   * @param oldpn A proposal number taken as the highest known so far, that
 
532
   *              should be taken into consideration when generating a new 
 
533
   *              Proposal Number for the Recovery Phase.
 
534
   */
208
535
  void collect(version_t oldpn);
209
 
  void handle_collect(MMonPaxos*);
210
 
  void handle_last(MMonPaxos*);
 
536
  /**
 
537
   * Handle the reception of a collect message from the Leader and reply
 
538
   * accordingly.
 
539
   *
 
540
   * Once a Peon receives a collect message from the Leader it will reply
 
541
   * with its first and last committed versions, as well as informations so
 
542
   * the Leader may know if his Proposal Number was, or was not, accepted by
 
543
   * the Peon. The Peon will accept the Leader's Proposal Number iif it is
 
544
   * higher than the Peon's currently accepted Proposal Number. The Peon may
 
545
   * also inform the Leader of accepted but uncommitted values.
 
546
   *
 
547
   * @invariant The message is an operation of type OP_COLLECT.
 
548
   * @pre We are a Peon.
 
549
   * @post Replied to the Leader, accepting or not accepting his PN.
 
550
   *
 
551
   * @param collect The collect message sent by the Leader to the Peon.
 
552
   */
 
553
  void handle_collect(MMonPaxos *collect);
 
554
  /**
 
555
   * Handle a response from a Peon to the Leader's collect phase.
 
556
   *
 
557
   * The received message will state the Peon's last committed version, as 
 
558
   * well as its last proposal number. This will lead to one of the following
 
559
   * scenarios: if the replied Proposal Number is equal to the one we proposed,
 
560
   * then the Peon has accepted our proposal, and if all the Peons do accept
 
561
   * our Proposal Number, then we are allowed to proceed with the commit;
 
562
   * however, if a Peon replies with a higher Proposal Number, we assume he
 
563
   * knows something we don't and the Leader will have to abort the current
 
564
   * proposal in order to retry with the Proposal Number specified by the Peon.
 
565
   * It may also occur that the Peon replied with a lower Proposal Number, in
 
566
   * which case we assume it is a reply to an an older value and we'll simply
 
567
   * drop it.
 
568
   * This function will also check if the Peon replied with an accepted but
 
569
   * yet uncommitted value. In this case, if its version is higher than our
 
570
   * last committed value by one, we assume that the Peon knows a value from a
 
571
   * previous proposal that has never been committed, and we should try to
 
572
   * commit that value by proposing it next. On the other hand, if that is
 
573
   * not the case, we'll assume it is an old, uncommitted value, we do not
 
574
   * care about and we'll consider the system active by extending the leases.
 
575
   *
 
576
   * @invariant The message is an operation of type OP_LAST.
 
577
   * @pre We are the Leader.
 
578
   * @post We initiate a commit, or we retry with a higher Proposal Number, 
 
579
   *       or we drop the message.
 
580
   * @post We move from STATE_RECOVERING to STATE_ACTIVE.
 
581
   *
 
582
   * @param last The message sent by the Peon to the Leader.
 
583
   */
 
584
  void handle_last(MMonPaxos *last);
 
585
  /**
 
586
   * The Recovery Phase timed out, meaning that a significant part of the
 
587
   * quorum does not believe we are the Leader, and we thus should trigger new
 
588
   * elections.
 
589
   *
 
590
   * @pre We believe to be the Leader.
 
591
   * @post Trigger new elections.
 
592
   */
211
593
  void collect_timeout();
 
594
  /**
 
595
   * @}
 
596
   */
212
597
 
 
598
  /**
 
599
   * @defgroup Paxos_h_updating_funcs Functions used during the Updating State
 
600
   * 
 
601
   * These functions may easily be mapped to the original Paxos Algorithm's 
 
602
   * phases. 
 
603
   *
 
604
   * Taking into account the algorithm can be divided in 4 phases (Prepare,
 
605
   * Promise, Accept Request and Accepted), we can easily map Paxos::begin to
 
606
   * both the Prepare and Accept Request phases; the Paxos::handle_begin to
 
607
   * the Promise phase; and the Paxos::handle_accept to the Accepted phase.
 
608
   * @{
 
609
   */
 
610
  /**
 
611
   * Start a new proposal with the intent of committing @p value.
 
612
   *
 
613
   * If we are alone on the system (i.e., a quorum of one), then we will
 
614
   * simply commit the value, but if we are not alone, then we need to propose
 
615
   * the value to the quorum.
 
616
   *
 
617
   * @pre We are the Leader
 
618
   * @pre We are on STATE_ACTIVE
 
619
   * @post We commit, iif we are alone, or we send a message to each quorum 
 
620
   *       member
 
621
   * @post We are on STATE_ACTIVE, iif we are alone, or on 
 
622
   *       STATE_UPDATING otherwise
 
623
   *
 
624
   * @param value The value being proposed to the quorum
 
625
   */
213
626
  void begin(bufferlist& value);
214
 
  void handle_begin(MMonPaxos*);
215
 
  void handle_accept(MMonPaxos*);
 
627
  /**
 
628
   * Accept or decline (by ignoring) a proposal from the Leader.
 
629
   *
 
630
   * We will decline the proposal (by ignoring it) if we have promised to
 
631
   * accept a higher numbered proposal. If that is not the case, we will
 
632
   * accept it and accordingly reply to the Leader.
 
633
   *
 
634
   * @pre We are a Peon
 
635
   * @pre We are on STATE_ACTIVE
 
636
   * @post We are on STATE_UPDATING iif we accept the Leader's proposal
 
637
   * @post We send a reply message to the Leader iif we accept his proposal
 
638
   *
 
639
   * @invariant The received message is an operation of type OP_BEGIN
 
640
   *
 
641
   * @param begin The message sent by the Leader to the Peon during the
 
642
   *              Paxos::begin function
 
643
   *
 
644
   */
 
645
  void handle_begin(MMonPaxos *begin);
 
646
  /**
 
647
   * Handle an Accept message sent by a Peon.
 
648
   *
 
649
   * In order to commit, the Leader has to receive accepts from a majority of
 
650
   * the quorum. If that does happen, then the Leader may proceed with the
 
651
   * commit. However, the Leader needs the accepts from all the quorum members
 
652
   * in order to extend the lease and move on to STATE_ACTIVE.
 
653
   *
 
654
   * This function handles these two situations, accounting for the amount of
 
655
   * received accepts.
 
656
   *
 
657
   * @pre We are the Leader
 
658
   * @pre We are on STATE_UPDATING
 
659
   * @post We are on STATE_ACTIVE iif we received accepts from the full quorum
 
660
   * @post We extended the lease iif we moved on to STATE_ACTIVE
 
661
   * @post We are on STATE_UPDATING iif we didn't received accepts from the
 
662
   *       full quorum
 
663
   * @post We have committed iif we received accepts from a majority
 
664
   *
 
665
   * @invariant The received message is an operation of type OP_ACCEPT
 
666
   *
 
667
   * @param accept The message sent by the Peons to the Leader during the
 
668
   *               Paxos::handle_begin function
 
669
   */
 
670
  void handle_accept(MMonPaxos *accept);
 
671
  /**
 
672
   * Trigger a fresh election.
 
673
   *
 
674
   * During Paxos::begin we set a Callback of type Paxos::C_AcceptTimeout in
 
675
   * order to limit the amount of time we spend waiting for Accept replies.
 
676
   * This callback will call Paxos::accept_timeout when it is fired.
 
677
   *
 
678
   * This is essential to the algorithm because there may be the chance that
 
679
   * we are no longer the Leader (i.e., others don't believe in us) and we
 
680
   * are getting ignored, or we dropped out of the quorum and haven't realised
 
681
   * it. So, our only option is to trigger fresh elections.
 
682
   *
 
683
   * @pre We are the Leader
 
684
   * @pre We are on STATE_UPDATING
 
685
   * @post Triggered fresh elections
 
686
   */
216
687
  void accept_timeout();
 
688
  /**
 
689
   * @}
 
690
   */
217
691
 
 
692
  /**
 
693
   * Commit a value throughout the system.
 
694
   *
 
695
   * The Leader will cancel the current lease (as it was for the old value),
 
696
   * and will store the committed value locally. It will then instruct every
 
697
   * quorum member to do so as well.
 
698
   *
 
699
   * @pre We are the Leader
 
700
   * @pre We are on STATE_UPDATING
 
701
   * @pre A majority of quorum members accepted our proposal
 
702
   * @post Value locally stored
 
703
   * @post Quorum members instructed to commit the new value.
 
704
   */
218
705
  void commit();
219
 
  void handle_commit(MMonPaxos*);
 
706
  /**
 
707
   * Commit the new value to stable storage as being the latest available
 
708
   * version.
 
709
   *
 
710
   * @pre We are a Peon
 
711
   * @post The new value is locally stored
 
712
   * @post Fire up the callbacks waiting on waiting_for_commit
 
713
   *
 
714
   * @invariant The received message is an operation of type OP_COMMIT
 
715
   *
 
716
   * @param commit The message sent by the Leader to the Peon during
 
717
   *               Paxos::commit
 
718
   */
 
719
  void handle_commit(MMonPaxos *commit);
 
720
  /**
 
721
   * Extend the system's lease.
 
722
   *
 
723
   * This means that the Leader considers that it should now safe to read from
 
724
   * any node on the system, since every quorum member is now in possession of
 
725
   * the latest version. Therefore, the Leader will send a message stating just
 
726
   * this to each quorum member, and will impose a limited timeframe during
 
727
   * which acks will be accepted. If there aren't as many acks as expected
 
728
   * (i.e, if at least one quorum member does not ack the lease) during this
 
729
   * timeframe, then we will force fresh elections.
 
730
   *
 
731
   * @pre We are the Leader
 
732
   * @pre We are on STATE_ACTIVE
 
733
   * @post A message extending the lease is sent to each quorum member
 
734
   * @post A timeout callback is set to limit the amount of time we will wait
 
735
   *       for lease acks.
 
736
   * @post A timer is set in order to renew the lease after a certain amount
 
737
   *       of time.
 
738
   */
220
739
  void extend_lease();
221
 
  void handle_lease(MMonPaxos*);
222
 
  void handle_lease_ack(MMonPaxos*);
223
 
 
224
 
  void lease_ack_timeout();    // on leader, if lease isn't acked by all peons
225
 
  void lease_renew_timeout();  // on leader, to renew the lease
 
740
  /**
 
741
   * Update the lease on the Peon's side of things.
 
742
   *
 
743
   * Once a Peon receives a Lease message, it will update its lease_expire
 
744
   * variable, reply to the Leader acknowledging the lease update and set a
 
745
   * timeout callback to be fired upon the lease's expiration. Finally, the
 
746
   * Peon will fire up all the callbacks waiting for it to become active,
 
747
   * which it just did, and all those waiting for it to become readable,
 
748
   * which should be true if the Peon's lease didn't expire in the mean time.
 
749
   *
 
750
   * @pre We are a Peon
 
751
   * @post We update the lease accordingly
 
752
   * @post A lease timeout callback is set
 
753
   * @post Move to STATE_ACTIVE
 
754
   * @post Fire up all the callbacks waiting for STATE_ACTIVE
 
755
   * @post Fire up all the callbacks waiting for readable iif we are readable
 
756
   * @post Ack the lease to the Leader
 
757
   *
 
758
   * @invariant The received message is an operation of type OP_LEASE
 
759
   *
 
760
   * @param The message sent by the Leader to the Peon during the
 
761
   *        Paxos::extend_lease function
 
762
   */
 
763
  void handle_lease(MMonPaxos *lease);
 
764
  /**
 
765
   * Account for all the Lease Acks the Leader receives from the Peons.
 
766
   *
 
767
   * Once the Leader receives all the Lease Acks from the Peons, it will be
 
768
   * able to cancel the Lease Ack timeout callback, thus avoiding calling
 
769
   * fresh elections.
 
770
   *
 
771
   * @pre We are the Leader
 
772
   * @post Cancel the Lease Ack timeout callback iif we receive acks from all
 
773
   *       the quorum members
 
774
   *
 
775
   * @invariant The received message is an operation of type OP_LEASE_ACK
 
776
   *
 
777
   * @param ack The message sent by a Peon to the Leader during the
 
778
   *            Paxos::handle_lease function
 
779
   */
 
780
  void handle_lease_ack(MMonPaxos *ack);
 
781
  /**
 
782
   * Call fresh elections because at least one Peon didn't acked our lease.
 
783
   *
 
784
   * @pre We are the Leader
 
785
   * @pre We are on STATE_ACTIVE
 
786
   * @post Trigger fresh elections
 
787
   */
 
788
  void lease_ack_timeout();
 
789
  /**
 
790
   * Extend lease since we haven't had new committed values meanwhile.
 
791
   *
 
792
   * @pre We are the Leader
 
793
   * @pre We are on STATE_ACTIVE
 
794
   * @post Go through with Paxos::extend_lease
 
795
   */
 
796
  void lease_renew_timeout();
 
797
  /**
 
798
   * Call fresh elections because the Peon's lease expired without being
 
799
   * renewed or receiving a fresh lease.
 
800
   *
 
801
   * This means that the Peon is no longer assumed as being in the quorum
 
802
   * (or there is no Leader to speak of), so just trigger fresh elections
 
803
   * to circumvent this issue.
 
804
   *
 
805
   * @pre We are a Peon
 
806
   * @post Trigger fresh elections
 
807
   */
226
808
  void lease_timeout();        // on peon, if lease isn't extended
227
809
 
 
810
  /**
 
811
   * Cancel all of Paxos' timeout/renew events. 
 
812
   */
228
813
  void cancel_events();
229
814
 
 
815
  /**
 
816
   * Generate a new Proposal Number based on @p gt
 
817
   *
 
818
   * @todo Check what @p gt actually means and what its usage entails
 
819
   * @param gt A hint for the geration of the Proposal Number
 
820
   * @return A globally unique, monotonically increasing Proposal Number
 
821
   */
230
822
  version_t get_new_proposal_number(version_t gt=0);
231
 
  
 
823
 
 
824
  /**
 
825
   * @todo document sync function
 
826
   */
232
827
  void warn_on_future_time(utime_t t, entity_name_t from);
233
828
 
234
829
public:
 
830
  /**
 
831
   * @param m A monitor
 
832
   * @param mid A machine id
 
833
   */
235
834
  Paxos(Monitor *m,
236
835
        int mid) : mon(m),
237
836
                   machine_id(mid), 
266
865
  bool is_consistent();
267
866
 
268
867
  void restart();
 
868
  /**
 
869
   * Initiate the Leader after it wins an election.
 
870
   *
 
871
   * Once an election is won, the Leader will be initiated and there are two
 
872
   * possible outcomes of this method: the Leader directly jumps to the active
 
873
   * state (STATE_ACTIVE) if it believes to be the only one in the quorum, or
 
874
   * will start recovering (STATE_RECOVERING) by initiating the collect phase. 
 
875
   *
 
876
   * @pre Our monitor is the Leader.
 
877
   * @post We are either on STATE_ACTIVE if we're the only one in the quorum,
 
878
   *       or on STATE_RECOVERING otherwise.
 
879
   */
269
880
  void leader_init();
 
881
  /**
 
882
   * Initiate a Peon after it loses an election.
 
883
   *
 
884
   * If we are a Peon, then there must be a Leader and we are not alone in the
 
885
   * quorum, thus automatically assume we are on STATE_RECOVERING, which means
 
886
   * we will soon be enrolled into the Leader's collect phase.
 
887
   *
 
888
   * @pre There is a Leader, and he's about to start the collect phase.
 
889
   * @post We are on STATE_RECOVERING and will soon receive collect phase's 
 
890
   *       messages.
 
891
   */
270
892
  void peon_init();
271
893
 
272
 
  void share_state(MMonPaxos *m, version_t first_committed, version_t last_committed);
 
894
  /**
 
895
   * Include an incremental state of values, ranging from peer_first_committed
 
896
   * to the last committed value, on the message m
 
897
   *
 
898
   * @param m A message
 
899
   * @param peer_first_committed Lowest version to take into account
 
900
   * @param peer_last_committed Highest version to take into account
 
901
   */
 
902
  void share_state(MMonPaxos *m, version_t peer_first_committed,
 
903
                   version_t peer_last_committed);
 
904
  /**
 
905
   * Store the state held on the message m into local, stable storage.
 
906
   *
 
907
   * @param m A message
 
908
   */
273
909
  void store_state(MMonPaxos *m);
274
910
 
 
911
  /**
 
912
   * @todo This appears to be used only by the OSDMonitor, and I would say
 
913
   *       its objective is to allow a third-party to have a "private"
 
914
   *       state dir. -JL
 
915
   */
275
916
  void add_extra_state_dir(string s) {
276
917
    extra_state_dirs.push_back(s);
277
918
  }
278
919
 
279
920
  // -- service interface --
 
921
  /**
 
922
   * Add c to the list of callbacks waiting for us to become active.
 
923
   *
 
924
   * @param c A callback
 
925
   */
280
926
  void wait_for_active(Context *c) {
281
927
    waiting_for_active.push_back(c);
282
928
  }
283
929
 
 
930
  /**
 
931
   * Erase old states from stable storage.
 
932
   *
 
933
   * @param first The version we are trimming to
 
934
   * @param force If specified, we may even erase the latest stashed version
 
935
   *              iif @p first is higher than that version.
 
936
   */
284
937
  void trim_to(version_t first, bool force=false);
285
 
  
 
938
 
 
939
  /**
 
940
   * @defgroup Paxos_h_slurping_funcs Slurping-related functions
 
941
   * @todo Discover what slurping is
 
942
   * @{
 
943
   */
286
944
  void start_slurping();
287
945
  void end_slurping();
288
946
  bool is_slurping() { return slurping == 1; }
 
947
  /**
 
948
   * @}
 
949
   */
289
950
 
290
951
  // read
 
952
  /**
 
953
   * @defgroup Paxos_h_read_funcs Read-related functions
 
954
   * @{
 
955
   */
 
956
  /**
 
957
   * Get latest committed version
 
958
   *
 
959
   * @return latest committed version
 
960
   */
291
961
  version_t get_version() { return last_committed; }
 
962
  /**
 
963
   * Get first committed version
 
964
   *
 
965
   * @return the first committed version
 
966
   */
 
967
  version_t get_first_committed() { return first_committed; }
 
968
  /**
 
969
   * Check if a given version is readable.
 
970
   *
 
971
   * A version may not be readable for a myriad of reasons:
 
972
   *  @li the version @v is higher that the last committed version
 
973
   *  @li we are not the Leader nor a Peon (election may be on-going)
 
974
   *  @li we do not have a committed value yet
 
975
   *  @li we do not have a valid lease
 
976
   *
 
977
   * @param seen The version we want to check if it is readable.
 
978
   * @return 'true' if the version is readable; 'false' otherwise.
 
979
   */
292
980
  bool is_readable(version_t seen=0);
 
981
  /**
 
982
   * Read version @v and store its value in @bl
 
983
   *
 
984
   * @param[in] v The version we want to read
 
985
   * @param[out] bl The version's value
 
986
   * @return 'true' if we successfully read the value; 'false' otherwise
 
987
   */
293
988
  bool read(version_t v, bufferlist &bl);
 
989
  /**
 
990
   * Read the latest committed version
 
991
   *
 
992
   * @param[out] bl The version's value
 
993
   * @return the latest committed version if we successfully read the value;
 
994
   *         or 0 (zero) otherwise.
 
995
   */
294
996
  version_t read_current(bufferlist &bl);
 
997
  /**
 
998
   * Add onreadable to the list of callbacks waiting for us to become readable.
 
999
   *
 
1000
   * @param onreadable A callback
 
1001
   */
295
1002
  void wait_for_readable(Context *onreadable) {
296
1003
    //assert(!is_readable());
297
1004
    waiting_for_readable.push_back(onreadable);
298
1005
  }
 
1006
  /**
 
1007
   * @}
 
1008
   */
299
1009
 
 
1010
  /**
 
1011
   * @warning This declaration is not implemented anywhere and appears to be
 
1012
   *          just some lingering code.
 
1013
   */
 
1014
  bool is_leader();
300
1015
  // write
301
 
  bool is_leader();
 
1016
  /**
 
1017
   * @defgroup Paxos_h_write_funcs Write-related functions
 
1018
   * @{
 
1019
   */
 
1020
  /**
 
1021
   * Check if we are writeable.
 
1022
   *
 
1023
   * We are writeable if we are alone (i.e., a quorum of one), or if we match
 
1024
   * all the following conditions:
 
1025
   *  @li We are the Leader
 
1026
   *  @li We are on STATE_ACTIVE
 
1027
   *  @li We have a valid lease
 
1028
   *
 
1029
   * @return 'true' if we are writeable; 'false' otherwise.
 
1030
   */
302
1031
  bool is_writeable();
 
1032
  /**
 
1033
   * Add c to the list of callbacks waiting for us to become writeable.
 
1034
   *
 
1035
   * @param c A callback
 
1036
   */
303
1037
  void wait_for_writeable(Context *c) {
304
1038
    assert(!is_writeable());
305
1039
    waiting_for_writeable.push_back(c);
306
1040
  }
307
1041
 
 
1042
  /**
 
1043
   * Propose a new value to the Leader.
 
1044
   *
 
1045
   * This function enables the submission of a new value to the Leader, which
 
1046
   * will trigger a new proposal.
 
1047
   *
 
1048
   * @param bl A bufferlist holding the value to be proposed
 
1049
   * @param oncommit A callback to be fired up once we finish committing bl
 
1050
   */
308
1051
  bool propose_new_value(bufferlist& bl, Context *oncommit=0);
 
1052
  /**
 
1053
   * Add oncommit to the back of the list of callbacks waiting for us to
 
1054
   * finish committing.
 
1055
   *
 
1056
   * @param oncommit A callback
 
1057
   */
309
1058
  void wait_for_commit(Context *oncommit) {
310
1059
    waiting_for_commit.push_back(oncommit);
311
1060
  }
 
1061
  /**
 
1062
   * Add oncommit to the front of the list of callbacks waiting for us to
 
1063
   * finish committing.
 
1064
   *
 
1065
   * @param oncommit A callback
 
1066
   */
312
1067
  void wait_for_commit_front(Context *oncommit) {
313
1068
    waiting_for_commit.push_front(oncommit);
314
1069
  }
 
1070
  /**
 
1071
   * @}
 
1072
   */
315
1073
 
316
 
  // if state values are incrementals, it is usefult to keep
317
 
  // the latest copy of the complete structure.
 
1074
  /**
 
1075
   * @defgroup Paxos_h_stash_funcs State values stashing-related functions
 
1076
   *
 
1077
   * If the state values are incrementals, it is useful to keep the latest
 
1078
   * copy of the complete structure.
 
1079
   *
 
1080
   * @{
 
1081
   */
 
1082
  /**
 
1083
   * Get the latest version onto stable storage.
 
1084
   *
 
1085
   * Keeping the latest version on a predefined location makes it easier to
 
1086
   * access, since we know we always have the latest version on the same
 
1087
   * place.
 
1088
   *
 
1089
   * @param v the latest version
 
1090
   * @param bl the latest version's value
 
1091
   */
318
1092
  void stash_latest(version_t v, bufferlist& bl);
 
1093
  /**
 
1094
   * Get the latest stashed version's value
 
1095
   *
 
1096
   * @param[out] bl the latest stashed version's value
 
1097
   * @return the latest stashed version
 
1098
   */
319
1099
  version_t get_stashed(bufferlist& bl);
 
1100
  /**
 
1101
   * Get the latest stashed version
 
1102
   *
 
1103
   * @return the latest stashed version
 
1104
   */
320
1105
  version_t get_stashed_version() { return latest_stashed; }
321
 
 
322
 
  version_t get_first_committed() { return first_committed; }
323
 
 
324
 
  void register_observer(entity_inst_t inst, version_t v);
325
 
  void update_observers();
 
1106
  /**
 
1107
   * @}
 
1108
   */
 
1109
 
 
1110
  /**
 
1111
   * @}
 
1112
   */
326
1113
};
327
1114
 
328
1115
 
329
 
 
330
1116
#endif
331
1117