1 // -*- mode:C++; tab-width:8; c-basic-offset:2; indent-tabs-mode:t -*-
2 // vim: ts=8 sw=2 smarttab
4 * Ceph - scalable distributed file system
6 * Copyright (C) 2004-2006 Sage Weil <sage@newdream.net>
8 * This is free software; you can redistribute it and/or
9 * modify it under the terms of the GNU Lesser General Public
10 * License version 2.1, as published by the Free Software
11 * Foundation. See file COPYING.
18 cccccccccccccccccca????????????????????????????????????????
19 cccccccccccccccccca????????????????????????????????????????
20 cccccccccccccccccca???????????????????????????????????????? leader
21 cccccccccccccccccc?????????????????????????????????????????
22 ccccc??????????????????????????????????????????????????????
37 * Paxos storage layout and behavior
39 * Currently, we use a key/value store to hold all the Paxos-related data, but
40 * it can logically be depicted as this:
43 * first_committed -> 1
50 * Since we are relying on a k/v store supporting atomic transactions, we can
51 * guarantee that if 'last_committed' has a value of '4', then we have up to
52 * version 4 on the store, and no more than that; the same applies to
53 * 'first_committed', which holding '1' will strictly meaning that our lowest
56 * Each version's value (value_1, value_2, ..., value_n) is a blob of data,
57 * incomprehensible to the Paxos. These values are proposed to the Paxos on
58 * propose_new_value() and each one is a transaction encoded in a bufferlist.
60 * The Paxos will write the value to disk, associating it with its version,
61 * but will take a step further: the value shall be decoded, and the operations
62 * on that transaction shall be applied during the same transaction that will
63 * write the value's encoded bufferlist to disk. This behavior ensures that
64 * whatever is being proposed will only be available on the store when it is
65 * applied by Paxos, which will then be aware of such new values, guaranteeing
66 * the store state is always consistent without requiring shady workarounds.
68 * So, let's say that FooMonitor proposes the following transaction, neatly
69 * encoded on a bufferlist of course:
72 * put(foo, last_committed, 3)
73 * put(foo, 3, foo_value_3)
76 * put(foo, first_committed, 3)
78 * And knowing that the Paxos is proposed Tx_Foo as a bufferlist, once it is
79 * ready to commit, and assuming we are now committing version 5 of the Paxos,
80 * we will do something along the lines of:
83 * proposed_tx.decode(Tx_foo_bufferlist);
86 * our_tx.put(paxos, last_committed, 5);
87 * our_tx.put(paxos, 5, Tx_foo_bufferlist);
88 * our_tx.append(proposed_tx);
90 * store_apply(our_tx);
92 * And the store should look like this after we apply 'our_tx':
95 * first_committed -> 1
101 * 5 -> Tx_foo_bufferlist
103 * first_committed -> 3
104 * last_committed -> 3
109 #ifndef CEPH_MON_PAXOS_H
110 #define CEPH_MON_PAXOS_H
112 #include "include/types.h"
113 #include "mon_types.h"
114 #include "include/buffer.h"
115 #include "msg/msg_types.h"
116 #include "include/Context.h"
117 #include "common/perf_counters.h"
120 #include "MonitorDBStore.h"
121 #include "mon/MonOpRequest.h"
127 l_paxos_first
= 45800,
128 l_paxos_start_leader
,
132 l_paxos_refresh_latency
,
136 l_paxos_begin_latency
,
139 l_paxos_commit_bytes
,
140 l_paxos_commit_latency
,
142 l_paxos_collect_keys
,
143 l_paxos_collect_bytes
,
144 l_paxos_collect_latency
,
145 l_paxos_collect_uncommitted
,
146 l_paxos_collect_timeout
,
147 l_paxos_accept_timeout
,
148 l_paxos_lease_ack_timeout
,
149 l_paxos_lease_timeout
,
151 l_paxos_store_state_keys
,
152 l_paxos_store_state_bytes
,
153 l_paxos_store_state_latency
,
155 l_paxos_share_state_keys
,
156 l_paxos_share_state_bytes
,
158 l_paxos_new_pn_latency
,
163 // i am one state machine.
165 * This libary is based on the Paxos algorithm, but varies in a few key ways:
166 * 1- Only a single new value is generated at a time, simplifying the recovery logic.
167 * 2- Nodes track "committed" values, and share them generously (and trustingly)
168 * 3- A 'leasing' mechanism is built-in, allowing nodes to determine when it is
169 * safe to "read" their copy of the last committed value.
171 * This provides a simple replication substrate that services can be built on top of.
176 * @defgroup Paxos_h_class Paxos
180 * The Monitor to which this Paxos class is associated with.
184 /// perf counter for internal instrumentations
185 PerfCounters
*logger
;
189 // my state machine info
190 const string paxos_name
;
192 friend class Monitor
;
193 friend class PaxosService
;
195 list
<std::string
> extra_state_dirs
;
199 // -- generic state --
202 * @defgroup Paxos_h_states States on which the leader/peon may be.
207 * Leader/Peon is in Paxos' Recovery state
211 * Leader/Peon is idle, and the Peon may or may not have a valid lease.
215 * Leader/Peon is updating to a new value.
219 * Leader proposing an old value
221 STATE_UPDATING_PREVIOUS
,
223 * Leader/Peon is writing a new commit. readable, but not
228 * Leader/Peon is writing a new commit from a previous round.
230 STATE_WRITING_PREVIOUS
,
231 // leader: refresh following a commit
236 * Obtain state name from constant value.
238 * @note This function will raise a fatal error if @p s is not
239 * a valid state value.
241 * @param s State value.
242 * @return The state's name.
244 static const string
get_statename(int s
) {
246 case STATE_RECOVERING
:
252 case STATE_UPDATING_PREVIOUS
:
253 return "updating-previous";
256 case STATE_WRITING_PREVIOUS
:
257 return "writing-previous";
267 * The state we are in.
276 * Check if we are recovering.
278 * @return 'true' if we are on the Recovering state; 'false' otherwise.
280 bool is_recovering() const { return (state
== STATE_RECOVERING
); }
282 * Check if we are active.
284 * @return 'true' if we are on the Active state; 'false' otherwise.
286 bool is_active() const { return state
== STATE_ACTIVE
; }
288 * Check if we are updating.
290 * @return 'true' if we are on the Updating state; 'false' otherwise.
292 bool is_updating() const { return state
== STATE_UPDATING
; }
295 * Check if we are updating/proposing a previous value from a
298 bool is_updating_previous() const { return state
== STATE_UPDATING_PREVIOUS
; }
300 /// @return 'true' if we are writing an update to disk
301 bool is_writing() const { return state
== STATE_WRITING
; }
303 /// @return 'true' if we are writing an update-previous to disk
304 bool is_writing_previous() const { return state
== STATE_WRITING_PREVIOUS
; }
306 /// @return 'true' if we are refreshing an update just committed
307 bool is_refresh() const { return state
== STATE_REFRESH
; }
311 * @defgroup Paxos_h_recovery_vars Common recovery-related member variables
312 * @note These variables are common to both the Leader and the Peons.
318 version_t first_committed
;
320 * Last Proposal Number
322 * @todo Expand description
326 * Last committed value's version.
328 * On both the Leader and the Peons, this is the last value's version that
329 * was accepted by a given quorum and thus committed, that this instance
332 * @note It may not be the last committed value's version throughout the
333 * system. If we are a Peon, we may have not been part of the quorum
334 * that accepted the value, and for this very same reason we may still
335 * be a (couple of) version(s) behind, until we learn about the most
336 * recent version. This should only happen if we are not active (i.e.,
337 * part of the quorum), which should not happen if we are up, running
338 * and able to communicate with others -- thus able to be part of the
339 * monmap and trigger new elections.
341 version_t last_committed
;
343 * Last committed value's time.
345 * When the commit finished.
347 utime_t last_commit_time
;
349 * The last Proposal Number we have accepted.
351 * On the Leader, it will be the Proposal Number picked by the Leader
352 * itself. On the Peon, however, it will be the proposal sent by the Leader
353 * and it will only be updated if its value is higher than the one
354 * already known by the Peon.
356 version_t accepted_pn
;
358 * The last_committed epoch of the leader at the time we accepted the last pn.
360 * This has NO SEMANTIC MEANING, and is there only for the debug output.
362 version_t accepted_pn_from
;
364 * Map holding the first committed version by each quorum member.
366 * The versions kept in this map are updated during the collect phase.
367 * When the Leader starts the collect phase, each Peon will reply with its
368 * first committed version, which will then be kept in this map.
370 map
<int,version_t
> peer_first_committed
;
372 * Map holding the last committed version by each quorum member.
374 * The versions kept in this map are updated during the collect phase.
375 * When the Leader starts the collect phase, each Peon will reply with its
376 * last committed version, which will then be kept in this map.
378 map
<int,version_t
> peer_last_committed
;
385 * @defgroup Paxos_h_active_vars Common active-related member variables
389 * When does our read lease expires.
391 * Instead of performing a full commit each time a read is requested, we
392 * keep leases. Each lease will have an expiration date, which may or may
395 utime_t lease_expire
;
397 * List of callbacks waiting for our state to change into STATE_ACTIVE.
399 list
<Context
*> waiting_for_active
;
401 * List of callbacks waiting for the chance to read a version from us.
403 * Each entry on the list may result from an attempt to read a version that
404 * wasn't available at the time, or an attempt made during a period during
405 * which we could not satisfy the read request. The first case happens if
406 * the requested version is greater than our last committed version. The
407 * second scenario may happen if we are recovering, or if we don't have a
410 * The list will be woken up once we change to STATE_ACTIVE with an extended
411 * lease -- which can be achieved if we have everyone on the quorum on board
412 * with the latest proposal, or if we don't really care about the remaining
413 * uncommitted values --, or if we're on a quorum of one.
415 list
<Context
*> waiting_for_readable
;
421 // recovery (paxos phase 1)
423 * @defgroup Paxos_h_leader_recovery Leader-specific Recovery-related vars
427 * Number of replies to the collect phase we've received so far.
429 * This variable is reset to 1 each time we start a collect phase; it is
430 * incremented each time we receive a reply to the collect message, and
431 * is used to determine whether or not we have received replies from the
436 * Uncommitted value's version.
438 * If we have, or end up knowing about, an uncommitted value, then its
439 * version will be kept in this variable.
441 * @note If this version equals @p last_committed+1 when we reach the final
442 * steps of recovery, then the algorithm will assume this is a value
443 * the Leader does not know about, and trustingly the Leader will
444 * propose this version's value.
446 version_t uncommitted_v
;
448 * Uncommitted value's Proposal Number.
450 * We use this variable to assess if the Leader should take into consideration
451 * an uncommitted value sent by a Peon. Given that the Peon will send back to
452 * the Leader the last Proposal Number it accepted, the Leader will be able
453 * to infer if this value is more recent than the one the Leader has, thus
456 version_t uncommitted_pn
;
460 * If the system fails in-between the accept replies from the Peons and the
461 * instruction to commit from the Leader, then we may end up with accepted
462 * but yet-uncommitted values. During the Leader's recovery, it will attempt
463 * to bring the whole system to the latest state, and that means committing
464 * past accepted but uncommitted values.
466 * This variable will hold an uncommitted value, which may originate either
467 * on the Leader, or learnt by the Leader from a Peon during the collect
470 bufferlist uncommitted_value
;
472 * Used to specify when an on-going collect phase times out.
474 Context
*collect_timeout_event
;
481 * @defgroup Paxos_h_leader_active Leader-specific Active-related vars
485 * Set of participants (Leader & Peons) that have acked a lease extension.
487 * Each Peon that acknowledges a lease extension will have its place in this
488 * set, which will be used to account for all the acks from all the quorum
489 * members, guaranteeing that we trigger new elections if some don't ack in
490 * the expected timeframe.
492 set
<int> acked_lease
;
494 * Callback responsible for extending the lease periodically.
496 Context
*lease_renew_event
;
498 * Callback to trigger new elections once the time for acks is out.
500 Context
*lease_ack_timeout_event
;
505 * @defgroup Paxos_h_peon_active Peon-specific Active-related vars
509 * Callback to trigger new elections when the Peon's lease times out.
511 * If the Peon's lease is extended, this callback will be reset (i.e.,
512 * we cancel the event and reschedule a new one with starting from the
515 Context
*lease_timeout_event
;
520 // updating (paxos phase 2)
522 * @defgroup Paxos_h_leader_updating Leader-specific Updating-related vars
526 * New Value being proposed to the Peons.
528 * This bufferlist holds the value the Leader is proposing to the Peons, and
529 * that will be committed if the Peons do accept the proposal.
531 bufferlist new_value
;
533 * Set of participants (Leader & Peons) that accepted the new proposed value.
535 * This set is used to keep track of those who have accepted the proposed
536 * value, so the leader may know when to issue a commit (when a majority of
537 * participants has accepted the proposal), and when to extend the lease
538 * (when all the quorum members have accepted the proposal).
542 * Callback to trigger a new election if the proposal is not accepted by the
543 * full quorum within a given timeframe.
545 * If the full quorum does not accept the proposal, then it means that the
546 * Leader may no longer be recognized as the leader, or that the quorum has
547 * changed, and the value may have not reached all the participants. Thus,
548 * the leader must call new elections, and go through a recovery phase in
549 * order to propagate the new value throughout the system.
551 * This does not mean that we won't commit. We will commit as soon as we
552 * have a majority of acceptances. But if we do not have full acceptance
553 * from the quorum, then we cannot extend the lease, as some participants
554 * may not have the latest committed value.
556 Context
*accept_timeout_event
;
559 * List of callbacks waiting for it to be possible to write again.
561 * @remarks It is not possible to write if we are not the Leader, or we are
562 * not on the active state, or if the lease has expired.
564 list
<Context
*> waiting_for_writeable
;
566 * List of callbacks waiting for a commit to finish.
568 * @remarks This may be used to a) wait for an on-going commit to finish
569 * before we proceed with, say, a new proposal; or b) wait for the
570 * next commit to be finished so we are sure that our value was
573 list
<Context
*> waiting_for_commit
;
576 * Pending proposal transaction
578 * This is the transaction that is under construction and pending
579 * proposal. We will add operations to it until we decide it is
580 * time to start a paxos round.
582 MonitorDBStore::TransactionRef pending_proposal
;
585 * Finishers for pending transaction
587 * These are waiting for updates in the pending proposal/transaction
590 list
<Context
*> pending_finishers
;
593 * Finishers for committing transaction
595 * When the pending_proposal is submitted, pending_finishers move to
596 * this list. When it commits, these finishers are notified.
598 list
<Context
*> committing_finishers
;
601 * @defgroup Paxos_h_sync_warns Synchronization warnings
602 * @todo Describe these variables
605 utime_t last_clock_drift_warn
;
606 int clock_drift_warned
;
612 * Should be true if we have proposed to trim, or are in the middle of
613 * trimming; false otherwise.
618 * true if we want trigger_propose to *not* propose (yet)
620 bool plugged
= false;
623 * @defgroup Paxos_h_callbacks Callback classes.
627 * Callback class responsible for handling a Collect Timeout.
629 class C_CollectTimeout
;
631 * Callback class responsible for handling an Accept Timeout.
633 class C_AcceptTimeout
;
635 * Callback class responsible for handling a Lease Ack Timeout.
637 class C_LeaseAckTimeout
;
640 * Callback class responsible for handling a Lease Timeout.
642 class C_LeaseTimeout
;
645 * Callback class responsible for handling a Lease Renew Timeout.
654 class C_Proposal
: public Context
{
655 Context
*proposer_context
;
658 // for debug purposes. Will go away. Soon.
660 utime_t proposal_time
;
662 C_Proposal(Context
*c
, bufferlist
& proposal_bl
) :
666 proposal_time(ceph_clock_now())
669 void finish(int r
) override
{
670 if (proposer_context
) {
671 proposer_context
->complete(r
);
672 proposer_context
= NULL
;
681 * @defgroup Paxos_h_election_triggered Steps triggered by an election.
683 * @note All these functions play a significant role in the Recovery Phase,
684 * which is triggered right after an election once someone becomes
689 * Create a new Proposal Number and propose it to the Peons.
691 * This function starts the Recovery Phase, which can be directly mapped
692 * onto the original Paxos' Prepare phase. Basically, we'll generate a
693 * Proposal Number, taking @p oldpn into consideration, and we will send
694 * it to a quorum, along with our first and last committed versions. By
695 * sending these information in a message to the quorum, we expect to
696 * obtain acceptances from a majority, allowing us to commit, or be
697 * informed of a higher Proposal Number known by one or more of the Peons
700 * @pre We are the Leader.
701 * @post Recovery Phase initiated by sending messages to the quorum.
703 * @param oldpn A proposal number taken as the highest known so far, that
704 * should be taken into consideration when generating a new
705 * Proposal Number for the Recovery Phase.
707 void collect(version_t oldpn
);
709 * Handle the reception of a collect message from the Leader and reply
712 * Once a Peon receives a collect message from the Leader it will reply
713 * with its first and last committed versions, as well as information so
714 * the Leader may know if its Proposal Number was, or was not, accepted by
715 * the Peon. The Peon will accept the Leader's Proposal Number if it is
716 * higher than the Peon's currently accepted Proposal Number. The Peon may
717 * also inform the Leader of accepted but uncommitted values.
719 * @invariant The message is an operation of type OP_COLLECT.
720 * @pre We are a Peon.
721 * @post Replied to the Leader, accepting or not accepting its PN.
723 * @param collect The collect message sent by the Leader to the Peon.
725 void handle_collect(MonOpRequestRef op
);
727 * Handle a response from a Peon to the Leader's collect phase.
729 * The received message will state the Peon's last committed version, as
730 * well as its last proposal number. This will lead to one of the following
731 * scenarios: if the replied Proposal Number is equal to the one we proposed,
732 * then the Peon has accepted our proposal, and if all the Peons do accept
733 * our Proposal Number, then we are allowed to proceed with the commit;
734 * however, if a Peon replies with a higher Proposal Number, we assume he
735 * knows something we don't and the Leader will have to abort the current
736 * proposal in order to retry with the Proposal Number specified by the Peon.
737 * It may also occur that the Peon replied with a lower Proposal Number, in
738 * which case we assume it is a reply to an older value and we'll simply
740 * This function will also check if the Peon replied with an accepted but
741 * yet uncommitted value. In this case, if its version is higher than our
742 * last committed value by one, we assume that the Peon knows a value from a
743 * previous proposal that has never been committed, and we should try to
744 * commit that value by proposing it next. On the other hand, if that is
745 * not the case, we'll assume it is an old, uncommitted value, we do not
746 * care about and we'll consider the system active by extending the leases.
748 * @invariant The message is an operation of type OP_LAST.
749 * @pre We are the Leader.
750 * @post We initiate a commit, or we retry with a higher Proposal Number,
751 * or we drop the message.
752 * @post We move from STATE_RECOVERING to STATE_ACTIVE.
754 * @param last The message sent by the Peon to the Leader.
756 void handle_last(MonOpRequestRef op
);
758 * The Recovery Phase timed out, meaning that a significant part of the
759 * quorum does not believe we are the Leader, and we thus should trigger new
762 * @pre We believe to be the Leader.
763 * @post Trigger new elections.
765 void collect_timeout();
771 * @defgroup Paxos_h_updating_funcs Functions used during the Updating State
773 * These functions may easily be mapped to the original Paxos Algorithm's
776 * Taking into account the algorithm can be divided in 4 phases (Prepare,
777 * Promise, Accept Request and Accepted), we can easily map Paxos::begin to
778 * both the Prepare and Accept Request phases; the Paxos::handle_begin to
779 * the Promise phase; and the Paxos::handle_accept to the Accepted phase.
783 * Start a new proposal with the intent of committing @p value.
785 * If we are alone on the system (i.e., a quorum of one), then we will
786 * simply commit the value, but if we are not alone, then we need to propose
787 * the value to the quorum.
789 * @pre We are the Leader
790 * @pre We are on STATE_ACTIVE
791 * @post We commit, if we are alone, or we send a message to each quorum
793 * @post We are on STATE_ACTIVE, if we are alone, or on
794 * STATE_UPDATING otherwise
796 * @param value The value being proposed to the quorum
798 void begin(bufferlist
& value
);
800 * Accept or decline (by ignoring) a proposal from the Leader.
802 * We will decline the proposal (by ignoring it) if we have promised to
803 * accept a higher numbered proposal. If that is not the case, we will
804 * accept it and accordingly reply to the Leader.
807 * @pre We are on STATE_ACTIVE
808 * @post We are on STATE_UPDATING if we accept the Leader's proposal
809 * @post We send a reply message to the Leader if we accept its proposal
811 * @invariant The received message is an operation of type OP_BEGIN
813 * @param begin The message sent by the Leader to the Peon during the
814 * Paxos::begin function
817 void handle_begin(MonOpRequestRef op
);
819 * Handle an Accept message sent by a Peon.
821 * In order to commit, the Leader has to receive accepts from a majority of
822 * the quorum. If that does happen, then the Leader may proceed with the
823 * commit. However, the Leader needs the accepts from all the quorum members
824 * in order to extend the lease and move on to STATE_ACTIVE.
826 * This function handles these two situations, accounting for the amount of
829 * @pre We are the Leader
830 * @pre We are on STATE_UPDATING
831 * @post We are on STATE_ACTIVE if we received accepts from the full quorum
832 * @post We extended the lease if we moved on to STATE_ACTIVE
833 * @post We are on STATE_UPDATING if we didn't received accepts from the
835 * @post We have committed if we received accepts from a majority
837 * @invariant The received message is an operation of type OP_ACCEPT
839 * @param accept The message sent by the Peons to the Leader during the
840 * Paxos::handle_begin function
842 void handle_accept(MonOpRequestRef op
);
844 * Trigger a fresh election.
846 * During Paxos::begin we set a Callback of type Paxos::C_AcceptTimeout in
847 * order to limit the amount of time we spend waiting for Accept replies.
848 * This callback will call Paxos::accept_timeout when it is fired.
850 * This is essential to the algorithm because there may be the chance that
851 * we are no longer the Leader (i.e., others don't believe in us) and we
852 * are getting ignored, or we dropped out of the quorum and haven't realised
853 * it. So, our only option is to trigger fresh elections.
855 * @pre We are the Leader
856 * @pre We are on STATE_UPDATING
857 * @post Triggered fresh elections
859 void accept_timeout();
865 utime_t commit_start_stamp
;
866 friend struct C_Committed
;
869 * Commit a value throughout the system.
871 * The Leader will cancel the current lease (as it was for the old value),
872 * and will store the committed value locally. It will then instruct every
873 * quorum member to do so as well.
875 * @pre We are the Leader
876 * @pre We are on STATE_UPDATING
877 * @pre A majority of quorum members accepted our proposal
878 * @post Value locally stored
879 * @post Quorum members instructed to commit the new value.
882 void commit_finish(); ///< finish a commit after txn becomes durable
884 * Commit the new value to stable storage as being the latest available
888 * @post The new value is locally stored
889 * @post Fire up the callbacks waiting on waiting_for_commit
891 * @invariant The received message is an operation of type OP_COMMIT
893 * @param commit The message sent by the Leader to the Peon during
896 void handle_commit(MonOpRequestRef op
);
898 * Extend the system's lease.
900 * This means that the Leader considers that it should now safe to read from
901 * any node on the system, since every quorum member is now in possession of
902 * the latest version. Therefore, the Leader will send a message stating just
903 * this to each quorum member, and will impose a limited timeframe during
904 * which acks will be accepted. If there aren't as many acks as expected
905 * (i.e, if at least one quorum member does not ack the lease) during this
906 * timeframe, then we will force fresh elections.
908 * @pre We are the Leader
909 * @pre We are on STATE_ACTIVE
910 * @post A message extending the lease is sent to each quorum member
911 * @post A timeout callback is set to limit the amount of time we will wait
913 * @post A timer is set in order to renew the lease after a certain amount
918 * Update the lease on the Peon's side of things.
920 * Once a Peon receives a Lease message, it will update its lease_expire
921 * variable, reply to the Leader acknowledging the lease update and set a
922 * timeout callback to be fired upon the lease's expiration. Finally, the
923 * Peon will fire up all the callbacks waiting for it to become active,
924 * which it just did, and all those waiting for it to become readable,
925 * which should be true if the Peon's lease didn't expire in the mean time.
928 * @post We update the lease accordingly
929 * @post A lease timeout callback is set
930 * @post Move to STATE_ACTIVE
931 * @post Fire up all the callbacks waiting for STATE_ACTIVE
932 * @post Fire up all the callbacks waiting for readable if we are readable
933 * @post Ack the lease to the Leader
935 * @invariant The received message is an operation of type OP_LEASE
937 * @param lease The message sent by the Leader to the Peon during the
938 * Paxos::extend_lease function
940 void handle_lease(MonOpRequestRef op
);
942 * Account for all the Lease Acks the Leader receives from the Peons.
944 * Once the Leader receives all the Lease Acks from the Peons, it will be
945 * able to cancel the Lease Ack timeout callback, thus avoiding calling
948 * @pre We are the Leader
949 * @post Cancel the Lease Ack timeout callback if we receive acks from all
952 * @invariant The received message is an operation of type OP_LEASE_ACK
954 * @param ack The message sent by a Peon to the Leader during the
955 * Paxos::handle_lease function
957 void handle_lease_ack(MonOpRequestRef op
);
959 * Call fresh elections because at least one Peon didn't acked our lease.
961 * @pre We are the Leader
962 * @pre We are on STATE_ACTIVE
963 * @post Trigger fresh elections
965 void lease_ack_timeout();
967 * Extend lease since we haven't had new committed values meanwhile.
969 * @pre We are the Leader
970 * @pre We are on STATE_ACTIVE
971 * @post Go through with Paxos::extend_lease
973 void lease_renew_timeout();
975 * Call fresh elections because the Peon's lease expired without being
976 * renewed or receiving a fresh lease.
978 * This means that the Peon is no longer assumed as being in the quorum
979 * (or there is no Leader to speak of), so just trigger fresh elections
980 * to circumvent this issue.
983 * @post Trigger fresh elections
985 void lease_timeout(); // on peon, if lease isn't extended
987 /// restart the lease timeout timer
988 void reset_lease_timeout();
991 * Cancel all of Paxos' timeout/renew events.
993 void cancel_events();
995 * Shutdown this Paxos machine
1000 * Generate a new Proposal Number based on @p gt
1002 * @todo Check what @p gt actually means and what its usage entails
1003 * @param gt A hint for the geration of the Proposal Number
1004 * @return A globally unique, monotonically increasing Proposal Number
1006 version_t
get_new_proposal_number(version_t gt
=0);
1009 * @todo document sync function
1011 void warn_on_future_time(utime_t t
, entity_name_t from
);
1014 * Begin proposing the pending_proposal.
1016 void propose_pending();
1019 * refresh state from store
1021 * Called when we have new state for the mon to consume. If we return false,
1022 * abort (we triggered a bootstrap).
1024 * @returns true on success, false if we are now bootstrapping
1028 void commit_proposal();
1029 void finish_round();
1033 * @param m A monitor
1034 * @param name A name for the paxos service. It serves as the naming space
1035 * of the underlying persistent storage for this service.
1037 Paxos(Monitor
*m
, const string
&name
)
1041 state(STATE_RECOVERING
),
1046 accepted_pn_from(0),
1048 uncommitted_v(0), uncommitted_pn(0),
1049 collect_timeout_event(0),
1050 lease_renew_event(0),
1051 lease_ack_timeout_event(0),
1052 lease_timeout_event(0),
1053 accept_timeout_event(0),
1054 clock_drift_warned(0),
1057 const string
get_name() const {
1061 void dispatch(MonOpRequestRef op
);
1063 void read_and_prepare_transactions(MonitorDBStore::TransactionRef tx
,
1064 version_t from
, version_t last
);
1069 * dump state info to a formatter
1071 void dump_info(Formatter
*f
);
1074 * This function runs basic consistency checks. Importantly, if
1075 * it is inconsistent and shouldn't be, it asserts out.
1077 * @return True if consistent, false if not.
1079 bool is_consistent();
1083 * Initiate the Leader after it wins an election.
1085 * Once an election is won, the Leader will be initiated and there are two
1086 * possible outcomes of this method: the Leader directly jumps to the active
1087 * state (STATE_ACTIVE) if it believes to be the only one in the quorum, or
1088 * will start recovering (STATE_RECOVERING) by initiating the collect phase.
1090 * @pre Our monitor is the Leader.
1091 * @post We are either on STATE_ACTIVE if we're the only one in the quorum,
1092 * or on STATE_RECOVERING otherwise.
1096 * Initiate a Peon after it loses an election.
1098 * If we are a Peon, then there must be a Leader and we are not alone in the
1099 * quorum, thus automatically assume we are on STATE_RECOVERING, which means
1100 * we will soon be enrolled into the Leader's collect phase.
1102 * @pre There is a Leader, and it?s about to start the collect phase.
1103 * @post We are on STATE_RECOVERING and will soon receive collect phase's
1109 * Include an incremental state of values, ranging from peer_first_committed
1110 * to the last committed value, on the message m
1112 * @param m A message
1113 * @param peer_first_committed Lowest version to take into account
1114 * @param peer_last_committed Highest version to take into account
1116 void share_state(MMonPaxos
*m
, version_t peer_first_committed
,
1117 version_t peer_last_committed
);
1119 * Store on disk a state that was shared with us
1121 * Basically, we received a set of version. Or just one. It doesn't matter.
1122 * What matters is that we have to stash it in the store. So, we will simply
1123 * write every single bufferlist into their own versions on our side (i.e.,
1124 * onto paxos-related keys), and then we will decode those same bufferlists
1125 * we just wrote and apply the transactions they hold. We will also update
1126 * our first and last committed values to point to the new values, if need
1127 * be. All this is done tightly wrapped in a transaction to ensure we
1128 * enjoy the atomicity guarantees given by our awesome k/v store.
1130 * @param m A message
1131 * @returns true if we stored something new; false otherwise
1133 bool store_state(MMonPaxos
*m
);
1134 void _sanity_check_store();
1137 * Helper function to decode a bufferlist into a transaction and append it
1138 * to another transaction.
1140 * This function is used during the Leader's commit and during the
1141 * Paxos::store_state in order to apply the bufferlist's transaction onto
1144 * @param t The transaction to which we will append the operations
1145 * @param bl A bufferlist containing an encoded transaction
1147 static void decode_append_transaction(MonitorDBStore::TransactionRef t
,
1149 auto vt(std::make_shared
<MonitorDBStore::Transaction
>());
1150 bufferlist::iterator it
= bl
.begin();
1156 * @todo This appears to be used only by the OSDMonitor, and I would say
1157 * its objective is to allow a third-party to have a "private"
1160 void add_extra_state_dir(string s
) {
1161 extra_state_dirs
.push_back(s
);
1164 // -- service interface --
1166 * Add c to the list of callbacks waiting for us to become active.
1168 * @param c A callback
1170 void wait_for_active(MonOpRequestRef op
, Context
*c
) {
1172 op
->mark_event("paxos:wait_for_active");
1173 waiting_for_active
.push_back(c
);
1175 void wait_for_active(Context
*c
) {
1177 wait_for_active(o
, c
);
1181 * Trim the Paxos state as much as we can.
1186 * Check if we should trim.
1188 * If trimming is disabled, we must take that into consideration and only
1189 * return true if we are positively sure that we should trim soon.
1191 * @returns true if we should trim; false otherwise.
1193 bool should_trim() {
1194 int available_versions
= get_version() - get_first_committed();
1195 int maximum_versions
= g_conf
->paxos_min
+ g_conf
->paxos_trim_min
;
1197 if (trimming
|| (available_versions
<= maximum_versions
))
1203 bool is_plugged() const {
1207 assert(plugged
== false);
1211 assert(plugged
== true);
1217 * @defgroup Paxos_h_read_funcs Read-related functions
1221 * Get latest committed version
1223 * @return latest committed version
1225 version_t
get_version() { return last_committed
; }
1227 * Get first committed version
1229 * @return the first committed version
1231 version_t
get_first_committed() { return first_committed
; }
1233 * Get the last commit time
1235 * @returns Our last commit time
1237 utime_t
get_last_commit_time() const{
1238 return last_commit_time
;
1241 * Check if a given version is readable.
1243 * A version may not be readable for a myriad of reasons:
1244 * @li the version @e v is higher that the last committed version
1245 * @li we are not the Leader nor a Peon (election may be on-going)
1246 * @li we do not have a committed value yet
1247 * @li we do not have a valid lease
1249 * @param seen The version we want to check if it is readable.
1250 * @return 'true' if the version is readable; 'false' otherwise.
1252 bool is_readable(version_t seen
=0);
1254 * Read version @e v and store its value in @e bl
1256 * @param[in] v The version we want to read
1257 * @param[out] bl The version's value
1258 * @return 'true' if we successfully read the value; 'false' otherwise
1260 bool read(version_t v
, bufferlist
&bl
);
1262 * Read the latest committed version
1264 * @param[out] bl The version's value
1265 * @return the latest committed version if we successfully read the value;
1266 * or 0 (zero) otherwise.
1268 version_t
read_current(bufferlist
&bl
);
1270 * Add onreadable to the list of callbacks waiting for us to become readable.
1272 * @param onreadable A callback
1274 void wait_for_readable(MonOpRequestRef op
, Context
*onreadable
) {
1275 assert(!is_readable());
1277 op
->mark_event("paxos:wait_for_readable");
1278 waiting_for_readable
.push_back(onreadable
);
1280 void wait_for_readable(Context
*onreadable
) {
1282 wait_for_readable(o
, onreadable
);
1289 * Check if we have a valid lease.
1291 * @returns true if the lease is still valid; false otherwise.
1293 bool is_lease_valid();
1296 * @defgroup Paxos_h_write_funcs Write-related functions
1300 * Check if we are writeable.
1302 * We are writeable if we are alone (i.e., a quorum of one), or if we match
1303 * all the following conditions:
1304 * @li We are the Leader
1305 * @li We are on STATE_ACTIVE
1306 * @li We have a valid lease
1308 * @return 'true' if we are writeable; 'false' otherwise.
1310 bool is_writeable();
1312 * Add c to the list of callbacks waiting for us to become writeable.
1314 * @param c A callback
1316 void wait_for_writeable(MonOpRequestRef op
, Context
*c
) {
1317 assert(!is_writeable());
1319 op
->mark_event("paxos:wait_for_writeable");
1320 waiting_for_writeable
.push_back(c
);
1322 void wait_for_writeable(Context
*c
) {
1324 wait_for_writeable(o
, c
);
1328 * Get a transaction to submit operations to propose against
1330 * Apply operations to this transaction. It will eventually be proposed
1333 MonitorDBStore::TransactionRef
get_pending_transaction();
1336 * Queue a completion for the pending proposal
1338 * This completion will get triggered when the pending proposal
1339 * transaction commits.
1341 void queue_pending_finisher(Context
*onfinished
);
1344 * (try to) trigger a proposal
1346 * Tell paxos that it should submit the pending proposal. Note that if it
1347 * is not active (e.g., because it is already in the midst of committing
1348 * something) that will be deferred (e.g., until the current round finishes).
1350 bool trigger_propose();
1353 * Add oncommit to the back of the list of callbacks waiting for us to
1354 * finish committing.
1356 * @param oncommit A callback
1358 void wait_for_commit(Context
*oncommit
) {
1359 waiting_for_commit
.push_back(oncommit
);
1362 * Add oncommit to the front of the list of callbacks waiting for us to
1363 * finish committing.
1365 * @param oncommit A callback
1367 void wait_for_commit_front(Context
*oncommit
) {
1368 waiting_for_commit
.push_front(oncommit
);
1378 MonitorDBStore
*get_store();
1381 inline ostream
& operator<<(ostream
& out
, Paxos::C_Proposal
& p
)
1383 string proposed
= (p
.proposed
? "proposed" : "unproposed");
1384 out
<< " " << proposed
1385 << " queued " << (ceph_clock_now() - p
.proposal_time
)
1387 auto t(std::make_shared
<MonitorDBStore::Transaction
>());
1388 bufferlist::iterator p_it
= p
.bl
.begin();
1390 JSONFormatter
f(true);