Handle the ticket messages. More...

#include <ticket.h>

Inheritance diagram for cluck_daemon::ticket:

Collaboration diagram for cluck_daemon::ticket:

[legend]

Public Types
typedef std::map< std::string, pointer_t >	key_map_t

typedef std::map< std::string, key_map_t >	object_map_t

typedef std::shared_ptr< ticket >	pointer_t

typedef std::int32_t	serial_t

typedef std::uint32_t	ticket_id_t

typedef std::vector< pointer_t >	vector_t

Public Member Functions
	ticket (cluckd *c, messenger::pointer_t messenger, std::string const &lock_name, ed::dispatcher_match::tag_t tag, std::string const &entering_key, cluck::timeout_t obtention_timeout, cluck::timeout_t lock_duration, std::string const &server_name, std::string const &service_name)
	Initialize a ticket object.

	ticket (ticket const &)=delete

void	activate_lock ()
	Check whether this ticket can be activated and do so if so.

void	add_ticket ()
	Send the ADD_TICKET message.

void	drop_ticket ()
	We are done with the ticket.

void	entered ()
	Tell this entering that we received a LOCKENTERED message.

void	entering ()
	Enter the mode that lets us retrieve our ticket number.

pid_t	get_client_pid () const
	Retrieve the client process identifier.

cluck::timeout_t	get_current_timeout_date () const
	Get the current lock timeout date.

std::string const &	get_entering_key () const
	Retrieve a reference to the entering key of this ticket.

cluck::timeout_t	get_lock_duration () const
	Retrieve the lock duration.

cluck::timeout_t	get_lock_timeout_date () const
	Get the lock timeout date.

std::string const &	get_object_name () const
	Retrieve the object name of this ticket.

cluck::timeout_t	get_obtention_timeout () const
	Get the obtention timeout date.

std::string const &	get_owner () const
	Return the name of this ticket's owner.

serial_t	get_serial () const
	Return the serial number of this ticket.

std::string const &	get_server_name () const
	Retrieve the server name of this ticket.

std::string const &	get_service_name () const
	Retrieve the service name of this ticket.

ed::dispatcher_match::tag_t	get_tag () const
	Retrieve the tag of this ticket.

std::string const &	get_ticket_key () const
	Retrieve a reference to the ticket key.

ticket_id_t	get_ticket_number () const
	Return the ticket number of this ticket.

cluck::timeout_t	get_unlock_duration () const
	Get unlock duration.

bool	is_locked () const
	Check whether this ticket is locked or not.

void	lock_activated ()
	Check whether this ticket can be activated and do so if so.

void	lock_failed (std::string const &reason)
	Let the service that wanted this lock know that it failed.

void	lock_tickets ()

void	max_ticket (ticket_id_t new_max_ticket)
	Called whenever a MAX_TICKET is received.

bool	one_leader () const
	Check whether the system only has one leader.

ticket &	operator= (ticket const &)=delete

void	remove_entering (std::string const &key)
	Call any time time an entering flag is reset.

bool	send_message_to_leaders (ed::message &msg)
	Send a message to the other two leaders.

std::string	serialize () const
	Serialize a ticket to send it over to another leader.

void	set_alive_timeout (cluck::timeout_t timeout)
	Define a time when the ticket times out while waiting.

void	set_owner (std::string const &owner)
	Define whether this ticket is the owner of that lock.

void	set_ready ()
	Mark the ticket as being ready.

void	set_serial (serial_t owner)
	Give the lock a serial number for some form of unicity.

void	set_ticket_number (ticket_id_t number)
	Set the ticket number.

void	set_unlock_duration (cluck::timeout_t duration)
	Change the unlock duration to the specified value.

void	ticket_added (key_map_t const &entering)
	Called whenever a TICKET_ADDED is received.

bool	timed_out () const
	Check whether this ticket timed out.

void	unserialize (std::string const &data)
	Unserialize a ticket string back to a ticket object.

Static Public Attributes
static serial_t const	NO_SERIAL = -1

static ticket_id_t const	NO_TICKET = 0

Private Types
enum class	lock_failure_t { LOCK_FAILURE_NONE , LOCK_FAILURE_LOCK , LOCK_FAILURE_UNLOCKING }

Private Attributes
bool	f_added_ticket = false

bool	f_added_ticket_quorum = false

cluck::timeout_t	f_alive_timeout = cluck::timeout_t()

cluckd *	f_cluckd = nullptr

std::string	f_entering_key = std::string()

bool	f_get_max_ticket = false

cluck::timeout_t	f_lock_duration = cluck::timeout_t()

lock_failure_t	f_lock_failed = lock_failure_t::LOCK_FAILURE_NONE

cluck::timeout_t	f_lock_timeout_date = cluck::timeout_t()

bool	f_locked = false

messenger::pointer_t	f_messenger = messenger::pointer_t()

std::string	f_object_name = std::string()

cluck::timeout_t	f_obtention_timeout = cluck::timeout_t()

ticket_id_t	f_our_ticket = NO_TICKET

std::string	f_owner = std::string()

serial_t	f_serial = NO_SERIAL

std::string	f_server_name = std::string()

std::string	f_service_name = std::string()

key_map_t	f_still_entering = key_map_t()

ed::dispatcher_match::tag_t	f_tag = ed::dispatcher_match::DISPATCHER_MATCH_NO_TAG

std::string	f_ticket_key = std::string()

bool	f_ticket_ready = false

cluck::timeout_t	f_unlock_duration = cluck::timeout_t()

cluck::timeout_t	f_unlocked_timeout_date = cluck::timeout_t()

Detailed Description

Introduction

This class manages the Leslie Lamport's Bakery Algorithm (1974) lock mechanism (a critical section that we can get between any number of threads, processes, computers.) Details of this algorithm can be found here:

http://en.wikipedia.org/wiki/Lamport's_bakery_algorithm

The algorithm requires:

A unique name for each computer (server_name)
A unique number for the process attempting the lock (see gettid(2) manual)
A user supplied object name (the name of the lock)
A ticket number (use the largest existing ticket number + 1)

We also include a timeout on any one lock so we can forfeit the lock from happening if it cannot be obtained in a minimal amount of time. The timeout is specified as an absolute time in the future (now + X seconds.) The timeout is given in seconds (a standard time_t value).

This class sends various messages to manage the locks.

The Bakery Algorithm Explained

The bakery algorithm is based on the basic idea that a large number of customers go to one bakery to buy bread. In order to make sure they all are served in the order they come in, they are given a ticket with a number. The ticket numbers increase by one for each new customer. The person still in line with the smallest ticket number is served next. Once served, the ticket is destroyed.

Note: The ticket numbers can restart at one whenever the queue of customers goes empty. Otherwise it only increases. From our usage in Snap, it is really rare that the ticket numbers would not quickly be reset, especially because we have such numbers on a per object_name basis and thus many times the number will actually be one.

On a computer without any synchronization mechanism available (our case) two customers may enter the bakery simultaneously (especially since we are working with processes that may run on different computers.) This means two customers may end up with the exact same ticket number and there are no real means to avoid that problem. However, each customer is also assigned two unique numbers on creation: its "host number" (its server name, we use a string to simplify things) and its process number (we actually use gettid() so each thread gets a unique number which is an equivalent to a pid_t number for every single thread.) These two numbers are used to further order processes and make sure we can tell who will get the lock first.

So, the basic bakery algorithm looks like this in C++. This algorithm expects memory to be guarded (shared or "volatile"; always visible by all threads.) In our case, we send the data over the network to all the snaplock processes. This is definitely guarded.

// declaration and initial values of global variables
namespace {
    int                   num_threads = 100;
    std::vector<bool>     entering;
    std::vector<uint32_t> tickets;
}
 
// initialize the vectors
void init()
{
    entering.reserve(num_threads);
    tickets.reserve(num_threads);
}
 
// i is a thread "number" (0 to 99)
void lock(int i)
{
    // get the next ticket
    entering[i] = true;
    int my_ticket(0);
    for(int j(0); j < num_threads; ++j)
    {
        if(ticket[k] > my_ticket)
        {
            my_ticket = ticket[k];
        }
    }
    ++my_ticket; // add 1, we want the next ticket
    entering[i] = false;
 
    for(int j(0); j < num_threads; ++j)
    {
        // wait until thread j receives its ticket number
        while(entering[j])
        {
            sleep();
        }
 
        // there are several cases:
        //
        // (1) tickets that are 0 are not assigned so we can just go
        //     through
        //
        // (2) smaller tickets win over us (have a higher priority,)
        //     so if there is another thread with a smaller ticket
        //     sleep a little and try again; that ticket must go to
        //     zero to let us through that guard
        //
        // (3) if tickets are equal, compare the thread numbers and
        //     like the tickets, the smallest thread wins
        //
        while(ticket[j] != 0 && (ticket[j] < ticket[i] || (ticket[j] == ticket[i] && j < i))
        {
            sleep();
        }
    }
}
 
// i is the thread number
void unlock(int i)
{
    // release our ticket
    ticket[i] = 0;
}
 
void SomeThread(int i)
{
    while(true)
    {
        [...]
        // non-critical section...
        lock(i);
        // The critical section code goes here...
        unlock(i);
        // non-critical section...
        [...]
    }
}

Note that there are two possible optimizations when actually implementing the algorithm:

You can enter (entering[i] = true), get your ticket, exit (entering[i] = false) and then get the list of still existing 'entering' processes. Once that list goes empty, we do not need to test the entering[j] anymore because any further entering[j] will be about processes with a larger ticket number and thus processes that will appear later in the list of tickets.

By sorting (and they are) our ticket requests by ticket, server name, and process pid, we do not have to search for the smallest ticket. The smallest ticket is automatically first in that list! So all we have to do is: if not first, sleep() some more.

Our implementation in cluck

Locks are given a name by our users. This is used to lock just one small thing for any amount of time as required by your implementation.

That name is used as an index to the f_tickets object in the snaplock class. Within such a ticket, you have one entry per process trying to obtain that lock.

For example, the users plugin generates a unique user identifier which is a number starting at 1. When a process needs to do this, we need a lock to prevent any other processes to do it at the same time. We also use a QUORUM consistency in Cassandra to load/increment/save the user number.

In this example, all we need to lock is an object named something like "user number". Actually, if the number is specific to a website, we can use the website URI. In this case, we can use a name like this: "http://www.example.com/user#number". This says we are managing an atomic "#number" at address "http://www.example.com/user". This also means we do not need to block anyone if the other people need to lock a completely different field (so process A can lock the user unique number while process B could lock an invoice unique number.)

As a result, the locking mechanism manages the locks on a per lock name basis. In other words, if only two processes request a lock simultaneously and the object_name parameter are not equal, they both get their lock instantaneously (at least very quickly.)

Message Sequence Chart

Any drawback?

Timeouts

All our locks come with a timeout. The default is defined in CLUCK_LOCK_DURATION_DEFAULT_TIMEOUT, which is 5 seconds. (5 seconds, which for a front end hit to a website is very long already!) If that timeout is too short (i.e. a backend does heavy lifting work on the data), then you can make it larger. Our backends are given 4h by default.

Deadlock

Like with any lock, if you have two processes that both try two distinct locks each in the other order, you get a deadlock:

P1 tries to get L1, and gets it;

P2 tries to get L2, and gets it;

P1 tries to get L2, and has to wait on P2;

P2 tries to get L1, and creates a deadlock.

The deadlock itself will be resolved once a lock times out, but P2 will "never" have a chance to work on L1 if that sequence always happens.

Definition at line 41 of file ticket.h.

Member Typedef Documentation

◆ key_map_t

typedef std::map<std::string, pointer_t> cluck_daemon::ticket::key_map_t

Definition at line 47 of file ticket.h.

◆ object_map_t

typedef std::map<std::string, key_map_t> cluck_daemon::ticket::object_map_t

Definition at line 48 of file ticket.h.

◆ pointer_t

typedef std::shared_ptr<ticket> cluck_daemon::ticket::pointer_t

Definition at line 45 of file ticket.h.

◆ serial_t

typedef std::int32_t cluck_daemon::ticket::serial_t

Definition at line 49 of file ticket.h.

◆ ticket_id_t

typedef std::uint32_t cluck_daemon::ticket::ticket_id_t

Definition at line 50 of file ticket.h.

◆ vector_t

typedef std::vector<pointer_t> cluck_daemon::ticket::vector_t

Definition at line 46 of file ticket.h.

Member Enumeration Documentation

◆ lock_failure_t

enum class cluck_daemon::ticket::lock_failure_t

strongprivate

Enumerator
LOCK_FAILURE_NONE
LOCK_FAILURE_LOCK
LOCK_FAILURE_UNLOCKING

Definition at line 113 of file ticket.h.

Constructor & Destructor Documentation

◆ ticket() [1/2]

cluck_daemon::ticket::ticket	(	cluckd *	c,
		messenger::pointer_t	messenger,
		std::string const &	object_name,
		ed::dispatcher_match::tag_t	tag,
		std::string const &	entering_key,
		cluck::timeout_t	obtention_timeout,
		cluck::timeout_t	lock_duration,
		std::string const &	server_name,
		std::string const &	service_name
	)

The constructor initializes a ticket object by creating a ticket key and allocating an entering object.

Once the entering object was acknowledged by QUORUM cluck daemon instances (i.e. one other computer since we allow exactly 3 leaders,) we can then create the ticket.

Note: We create a key from the server name, client PID, and object name for the entering process to run. This key is unique among all computers assuming (1) your client PID is unique and (2) your servers all have unique names and both of these conditions are always true (i.e. we do not allow a cluckd to join a cluster if its name was already registered).; If you use threads, or are likely to use threads, make sure to use the gettid() function instead of getpid() to define a unique client PID. (Note: this is done in the cluck library.)

Parameters

[in]	c	A pointer to the cluckd object.
[in]	messenger	A pointer to the messenger.
[in]	object_name	The name of the object getting locked.
[in]	tag	The tag from the message to distinct different attempts.
[in]	entering_key	The key (ticket) used to enter the bakery.
[in]	obtention_timeout	The time when the attempt to get the lock times out in seconds.
[in]	lock_duration	The amount of time the lock lasts once obtained.
[in]	server_name	The name of the server generating the locked.
[in]	service_name	The service waiting for the LOCKED message.

Definition at line 356 of file ticket.cpp.

References f_entering_key, f_lock_duration, f_object_name, f_obtention_timeout, f_server_name, f_service_name, f_tag, and set_unlock_duration().

◆ ticket() [2/2]

cluck_daemon::ticket::ticket ( ticket const & )

delete

Member Function Documentation

◆ activate_lock()

void cluck_daemon::ticket::activate_lock ( )

This function checks whether the ticket is ready to be activated. This means it got a ticket and the ticket is ready. If so, then it sends the LOCKED message back to the system that required it.

This function can be called multiple times. It will send the ACTIVATE_LOCK message only once.

On a system with only one computer, it will also send the LOCKED message immediately.

Definition at line 750 of file ticket.cpp.

References f_lock_failed, f_locked, f_ticket_key, f_ticket_ready, lock_activated(), LOCK_FAILURE_NONE, one_leader(), and send_message_to_leaders().

Referenced by cluck_daemon::cluckd::activate_first_lock().

◆ add_ticket()

void cluck_daemon::ticket::add_ticket ( )

This function sends the ADD_TICKET message to all the cluckd instances currently known.

Exceptions

logic_error This exception is raised if the function gets called twice or more. Since it is considered an internal function, it should not be an issue.

Definition at line 601 of file ticket.cpp.

References f_added_ticket, f_cluckd, f_entering_key, f_object_name, f_obtention_timeout, f_our_ticket, f_ticket_key, cluck_daemon::cluckd::get_entering_tickets(), one_leader(), send_message_to_leaders(), cluck_daemon::cluckd::set_ticket(), and ticket_added().

Referenced by max_ticket().

◆ drop_ticket()

void cluck_daemon::ticket::drop_ticket ( )

This function sends the DROP_TICKET message to get rid of a ticket from another leader's list of tickets.

Another leader has a list of tickets as it receives LOCK and ADDTICKET messages.

Definition at line 813 of file ticket.cpp.

References f_entering_key, f_lock_failed, f_messenger, f_object_name, f_server_name, f_service_name, f_tag, f_ticket_key, LOCK_FAILURE_NONE, LOCK_FAILURE_UNLOCKING, and send_message_to_leaders().

◆ entered()

void cluck_daemon::ticket::entered ( )

This function gets called each time we receive a LOCKENTERED message with this ticket entering key.

Since we have 1 to 3 leaders, the quorum and thus consensus is reached as soon as we receive one LOCKENTERED message. So as a result this function sends GETMAXTICKET the first time it gets called. The GETMAXTICKET message allows us to determine the ticket number for the concerned object.

Note: The msg_lockentered() function first checked whether the LOCKENTERED message had anything to do with this ticket. If not, the message was just ignored.

Definition at line 521 of file ticket.cpp.

References f_cluckd, f_entering_key, f_get_max_ticket, f_object_name, f_our_ticket, cluck_daemon::cluckd::get_last_ticket(), max_ticket(), one_leader(), and send_message_to_leaders().

Referenced by entering().

◆ entering()

void cluck_daemon::ticket::entering ( )

In order to make sure we can get the current largest ticket number in a unique enough way, cluck has to enter the lock loop. This process starts by sending a LOCK_ENTERING message to all the other cluckd leaders.

Definition at line 471 of file ticket.cpp.

References entered(), f_entering_key, f_lock_duration, f_obtention_timeout, f_serial, f_server_name, f_service_name, f_unlock_duration, one_leader(), and send_message_to_leaders().

Referenced by cluck_daemon::cluckd::msg_lock().

◆ get_client_pid()

pid_t cluck_daemon::ticket::get_client_pid ( ) const

This function splits the entering key and return the process identifier. This is primarily used to resend a LOCK message since in most cases this information should not be required.

Note: This is not really information that the ticket is supposed to know about but well... there is now a case where we need to know this.

Returns: The process identifier of this ticket owner.

Definition at line 1114 of file ticket.cpp.

References f_entering_key.

◆ get_current_timeout_date()

cluck::timeout_t cluck_daemon::ticket::get_current_timeout_date ( ) const

This function returns the "current" lock timeout.

The "current" timeout is one of:

If the lock is being re-requested (after the loss of a leader) then the ALIVE timeout may be returned for a short period of time.

If the lock was not yet obtained, this function returns the obtention timeout timestamp.

Once the lock was obtained, the lock timeout gets defined and that one is returned instead.

When the UNLOCK is received or the timeout happens and cluckd sends the UNLOCKING message, the function returns the unlock timeout. In this case, the f_lock_time_date field is still used.

Note: This is the date used in the timed_out() function.

Returns: The date when the ticket will timeout or zero.

Definition at line 1428 of file ticket.cpp.

References f_alive_timeout, f_lock_timeout_date, f_locked, and f_obtention_timeout.

Referenced by timed_out().

◆ get_entering_key()

std::string const & cluck_daemon::ticket::get_entering_key ( ) const

This function returns the entering key of this ticket. The entering key is defined on instantiation so it is always available.

Note: By contrast, the ticket key is not available up until the time the ticket number is marked as valid.

Returns: The entering key of this ticket.

Definition at line 1540 of file ticket.cpp.

References f_entering_key.

◆ get_lock_duration()

cluck::timeout_t cluck_daemon::ticket::get_lock_duration ( ) const

This function returns the lock duration in seconds as defined with the constructor.

Returns: The lock duration in seconds.

Definition at line 1381 of file ticket.cpp.

References f_lock_duration.

◆ get_lock_timeout_date()

cluck::timeout_t cluck_daemon::ticket::get_lock_timeout_date ( ) const

This function returns the lock timeout. If not yet defined, the function will return zero.

Note: The ticket will immediately be assigned a timeout date when it gets activated.

Returns: The date when the ticket will timeout or zero.

Definition at line 1398 of file ticket.cpp.

References f_lock_timeout_date.

◆ get_object_name()

std::string const & cluck_daemon::ticket::get_object_name ( ) const

This function returns the name of the object associated with this lock (i.e. what is being locked).

Returns: The object name of the ticket.

Definition at line 1476 of file ticket.cpp.

References f_object_name.

◆ get_obtention_timeout()

cluck::timeout_t cluck_daemon::ticket::get_obtention_timeout ( ) const

This function returns the obtention timeout. Note that if the lock was already obtained, then this date may be in the past. You can test that by checking the get_lock_timeout() function first.

Returns: The date when the obtention of the ticket timeouts.

Definition at line 1319 of file ticket.cpp.

References f_obtention_timeout.

◆ get_owner()

std::string const & cluck_daemon::ticket::get_owner ( ) const

This function returns the name of the owner of this ticket. When a leader dies out, its name stick around until a new leader gets assigned to it.

The owner is actually the name of the sending server. So if leader 1 is named "alfred" and it sends a ticket message (i.e. LOCK_ENTERING), then the ticket owner parameter will be set "alfred".

The owner name is set when you create a ticket or by unserializing a ticket dump. Serialization is used to share tickets between cluck daemon when we lose a leader and a new computer becomes a new leader.

Returns: The name of this ticket owner.

Definition at line 1096 of file ticket.cpp.

References f_owner.

◆ get_serial()

ticket::serial_t cluck_daemon::ticket::get_serial ( ) const

This function returns the serial number of this ticket. See the set_serial() function for additional information about this number.

Returns: The serial number of the ticket.

Definition at line 1160 of file ticket.cpp.

References f_serial.

◆ get_server_name()

std::string const & cluck_daemon::ticket::get_server_name ( ) const

This function returns the name of the server associated with this lock, i.e. the server to which the LOCKED and UNLOCKED commands are to be sent back to.

This name is also used in case of an error to send the LOCKFAILED back to the service that requested the lock.

Returns: The server name of the ticket.

Definition at line 1506 of file ticket.cpp.

References f_server_name.

◆ get_service_name()

std::string const & cluck_daemon::ticket::get_service_name ( ) const

This function returns the name of the service associated with this lock. This is the service to which the LOCKED and UNLOCKED messages are sent.

This name is also used in case of an error to send the LOCKFAILED back to the service that requested the lock.

Returns: The service name of the ticket.

Definition at line 1523 of file ticket.cpp.

References f_service_name.

◆ get_tag()

ed::dispatcher_match::tag_t cluck_daemon::ticket::get_tag ( ) const

This function returns the tag of the object associated with this lock (i.e. the specific instance of the lock being locked).

Returns: The tag associated with this ticket.

Definition at line 1489 of file ticket.cpp.

References f_tag.

◆ get_ticket_key()

std::string const & cluck_daemon::ticket::get_ticket_key ( ) const

This function returns the ticket key of this ticket. The ticket key is only defined at a later time when the ticket has properly entered the bakery. It includes three parameters:

Ticket number as a hexadecimal number of 8 digits,
Server name of the server asking for the lock,
Process Identifier (PID) of the service daemon asking for the lock.

Note: This function returns an empty string until the ticket key is available.

Returns: The ticket key.

Definition at line 1561 of file ticket.cpp.

References f_ticket_key.

Referenced by cluck_daemon::cluckd::msg_activate_lock().

◆ get_ticket_number()

ticket::ticket_id_t cluck_daemon::ticket::get_ticket_number ( ) const

This function returns the ticket number of this ticket. This is generally used to determine the largest ticket number currently in use in order to attach a new ticket number to a lock object.

By default the value is NO_TICKET meaning that no ticket number was yet assigned to that ticket object.

Returns: The current ticket number.

Definition at line 1278 of file ticket.cpp.

References f_our_ticket.

◆ get_unlock_duration()

cluck::timeout_t cluck_daemon::ticket::get_unlock_duration ( ) const

The unlock duration is used in case the lock times out. It extends the lock duration for that much longer until the client acknowledge the locks or the lock really times out.

Note: If not yet set, this function returns zero (a null timestamp).

Returns: The unlock acknowledgement timeout duration.

Definition at line 1213 of file ticket.cpp.

References f_unlock_duration.

◆ is_locked()

bool cluck_daemon::ticket::is_locked ( ) const

This function returns true if the ticket is currently locked.

Returns: true when the ticket was successfully locked at some point.

Definition at line 1290 of file ticket.cpp.

References f_locked.

◆ lock_activated()

void cluck_daemon::ticket::lock_activated ( )

This function checks whether the ticket is ready to be activated. This means it got a ticket and the ticket is ready. If so, then it sends the LOCKED message back to the system that required it.

This function can be called multiple times. It will send the LOCKED message only once.

Definition at line 779 of file ticket.cpp.

References f_cluckd, f_lock_duration, f_lock_failed, f_lock_timeout_date, f_locked, f_messenger, f_object_name, f_owner, f_server_name, f_service_name, f_tag, f_ticket_ready, f_unlock_duration, f_unlocked_timeout_date, cluck_daemon::cluckd::get_server_name(), and LOCK_FAILURE_NONE.

Referenced by activate_lock(), and cluck_daemon::cluckd::msg_activate_lock().

◆ lock_failed()

void cluck_daemon::ticket::lock_failed ( std::string const & reason )

This function sends a reply to the server that requested the lock to let it know that it somehow failed.

The function replies with a LOCK_FAILED when the lock was never obtained. In this case the origin server cannot access the resources.

The function replies with UNLOCKING when the lock timed out. The server is expected to send an UNLOCK reply to acknowledge the failure and fully release the lock. The lock will remain in place until that acknowledgement is received or an amount of time equal to the lock duration by default with a minimum of 1 minute.

The UNLOCKING acknowledgement timeout is set to the same amount as the LOCK duration if the unlock_duration parameter is not specified in the LOCK message. When the unlock_duration parameter is specified, then that amount is used instead.

Note: The function may get called multiple times. The failure message is sent only on the first call.; If the ticket was created on another cluck daemon (not the one that received the LOCK event in the first place) then this ticket is not marked as being owned by this cluck daemon and as a result this function only marks the ticket as failed.

Parameters

[in] reason A reason for the failure (i.e. "timed out")

Definition at line 897 of file ticket.cpp.

References f_cluckd, f_entering_key, f_lock_failed, f_lock_timeout_date, f_locked, f_messenger, f_object_name, f_owner, f_server_name, f_service_name, f_tag, f_unlock_duration, cluck_daemon::cluckd::get_server_name(), LOCK_FAILURE_LOCK, LOCK_FAILURE_NONE, LOCK_FAILURE_UNLOCKING, and timed_out().

◆ lock_tickets()

void cluck_daemon::ticket::lock_tickets ( )

◆ max_ticket()

void cluck_daemon::ticket::max_ticket ( ticket_id_t new_max_ticket )

This function registers the largest ticket number. Once we reach QUORUM, then we have the largest number and we can move on to the next stage, which is to add the ticket.

Note: We reach quorum immediately in our current implementation since we have 1, 2, or 3 leaders. So this function takes the input in account once, calls add_ticket() immediately and if the 3rd leader does send a reply too, it gets ignored.

Parameters

[in] new_max_ticket Another possibly larger ticket.

Definition at line 566 of file ticket.cpp.

References add_ticket(), f_added_ticket, f_our_ticket, and NO_TICKET.

Referenced by entered().

◆ one_leader()

bool cluck_daemon::ticket::one_leader ( ) const

The function check the number of known leaders. If just one, then it returns true. This is important for our algorithm to work properly in that one specific case.

Returns: true if there is only one leader (i.e. one single computer in your whole cluster).

Definition at line 1305 of file ticket.cpp.

References f_cluckd, and cluck_daemon::cluckd::get_computer_count().

Referenced by activate_lock(), add_ticket(), entered(), entering(), and send_message_to_leaders().

◆ operator=()

ticket & cluck_daemon::ticket::operator= ( ticket const & )

delete

◆ remove_entering()

void cluck_daemon::ticket::remove_entering ( std::string const & key )

This function gets called whenever an entering flag gets set back to false (i.e. removed in our implementation).

This function knows whether this ticket received its number and is not yet ready. In both of these circumstances, we are waiting for all entering flags that got created while we determined the largest ticket number to be removed.

Parameters

[in] key The key of the ticket that was entered.

Definition at line 694 of file ticket.cpp.

References f_added_ticket_quorum, f_still_entering, f_ticket_key, f_ticket_ready, and send_message_to_leaders().

◆ send_message_to_leaders()

bool cluck_daemon::ticket::send_message_to_leaders ( ed::message & msg )

The msg is "broadcast" to the other two leaders.

This is a safe guard so if one of our three leaders fails, we have a backup of the lock status.

The locking system also works if there are only two or even just one computer. In those cases, special care has to be taken to get things to work as expected.

Parameters

[in] msg The message to send to the other two leaders.

Returns: true if the message was forwarded at least once, false otherwise.

Definition at line 417 of file ticket.cpp.

References f_cluckd, f_messenger, f_object_name, f_tag, cluck_daemon::cluckd::get_leader_a(), cluck_daemon::cluckd::get_leader_b(), and one_leader().

Referenced by activate_lock(), add_ticket(), drop_ticket(), entered(), entering(), remove_entering(), and ticket_added().

◆ serialize()

std::string cluck_daemon::ticket::serialize ( ) const

This function serialize a ticket to share it with the other leaders. This is important when a new leader gets elected as it would not otherwise have any idea of what the existing tickets are, although it is not 100% important, if another of the two snaplock was to go down, it becomes primordial for the tickets to be known in the other leaders.

This is used at the start before a leader starts accepting new lock requests.

Returns: This ticket as a serialized string.

See also: unserialize()

Definition at line 1583 of file ticket.cpp.

References f_added_ticket, f_added_ticket_quorum, f_entering_key, f_get_max_ticket, f_lock_duration, f_lock_failed, f_lock_timeout_date, f_locked, f_object_name, f_obtention_timeout, f_our_ticket, f_owner, f_serial, f_server_name, f_service_name, f_tag, f_ticket_key, f_ticket_ready, f_unlock_duration, LOCK_FAILURE_LOCK, LOCK_FAILURE_NONE, LOCK_FAILURE_UNLOCKING, and NO_SERIAL.

◆ set_alive_timeout()

void cluck_daemon::ticket::set_alive_timeout ( cluck::timeout_t timeout )

This function defines the time threshold when to timeout this ticket in case a service does not reply to an ALIVE message.

Whenever a leader dies, a ticket which is not locked yet may be transferred to another leader. To not attempt to lock a ticket for nothing, the new leader first checks that the service which requested that lock is indeed still alive by send an ALIVE message to it. In return, it expects an ABSOLUTELY reply.

If the ABSOLUTELY reply does not make it in time (at this time we limit this to 5 seconds) then we consider that this service is not responsive and we cancel the lock altogether.

To cancel this timeout, call the function with cluck::timeout_t() in timeout (i.e. zero duration).

Note: Since that message should happen while the cluck daemon is waiting for the LOCK event, the reply should be close to instantaneous. So 5 seconds is plenty until somehow your network is really busy or really large and the time for the message to travel is too long.

Parameters

[in] timeout The time when the ALIVE message times out.

Definition at line 1353 of file ticket.cpp.

References f_alive_timeout, and f_obtention_timeout.

Referenced by cluck_daemon::cluckd::msg_lock().

◆ set_owner()

void cluck_daemon::ticket::set_owner ( std::string const & owner )

Whenever comes time to send the LOCK, UNLOCK, or LOCK_FAILED messages, only the owner is expected to send it. This flag tells us who the owner is and thus who is responsible for sending that message.

Todo:: The ownership has to travel to others whenever a leader disappears.

Parameters

[in] owner The name of this ticket owner.

Definition at line 1073 of file ticket.cpp.

References f_owner.

Referenced by cluck_daemon::cluckd::msg_lock_entering().

◆ set_ready()

void cluck_daemon::ticket::set_ready ( )

This ticket is marked as being ready.

A ticket is ready when all the entering tickets were removed from it on the owning leader. On the other two leaders, the ticket gets marked as being ready once they receive the LOCKEXITING message.

Definition at line 1227 of file ticket.cpp.

References f_ticket_ready.

◆ set_serial()

void cluck_daemon::ticket::set_serial ( serial_t serial )

When we lose a leader, the unicity of the ticket may be required as we start sharing the tickets between the surviving leaders. This is done for the RELOCK message which attempts to restart the an old LOCK. In that case, two leaders end up attempt a RELOCK on the same ticket. To make sure that we can easily ignore the second attempt, we use the serial number to see that the exact same message is getting there twice.

The cluck daemon uses the leader number as part of the serial number (bits 24 and 25) so it is unique among all the instances, at least until a cluck deamon dies and its unique numbers get mingled (and the old leaders may change their own number too...)

Parameters

[in] serial The serial number of the ticket.

Definition at line 1147 of file ticket.cpp.

References f_serial.

Referenced by cluck_daemon::cluckd::msg_lock(), and cluck_daemon::cluckd::msg_lock_entering().

◆ set_ticket_number()

void cluck_daemon::ticket::set_ticket_number ( ticket_id_t number )

The other two leaders receive the ticket number in the ADDTICKET message. That number must be saved in the ticket, somehow. This is the function we use to do that.

It is very important to have the correct number (by default it is zero) since the algorithm asks for the maximum ticket number currently available and without that information that request cannot be answered properly.

Parameters

[in] number The ticket number to save in f_our_ticket.

Definition at line 1246 of file ticket.cpp.

References f_added_ticket, f_entering_key, f_our_ticket, f_ticket_key, and NO_TICKET.

◆ set_unlock_duration()

void cluck_daemon::ticket::set_unlock_duration ( cluck::timeout_t duration )

If the service requesting a lock fails to acknowledge an unlock, then the lock still gets unlocked after this duration.

By default, this parameter gets set to the same value as duration with a minimum of 3 seconds. When the message includes an unlock_duration parameter then that value is used instead.

Note: If duration is less than cluck::CLUCK_UNLOCK_MINIMUM_TIMEOUT, then cluck::CLUCK_UNLOCK_MINIMUM_TIMEOUT is used. At time of writing cluck::CLUCK_UNLOCK_MINIMUM_TIMEOUT is 3 seconds.

Warning: It is important to understand that as soon as an UNLOCKED event arrives, you should acknowledge it. Not doing so increases the risk that two or more processes access the same resource simultaneously.

Parameters

[in] duration The amount of time to acknowledge an UNLOCKED event; after that the lock is released no matter what.

Definition at line 1188 of file ticket.cpp.

References cluck::CLUCK_DEFAULT_TIMEOUT, cluck::CLUCK_MAXIMUM_TIMEOUT, cluck::CLUCK_UNLOCK_MINIMUM_TIMEOUT, f_lock_duration, and f_unlock_duration.

Referenced by ticket(), cluck_daemon::cluckd::msg_lock(), and cluck_daemon::cluckd::msg_lock_entering().

◆ ticket_added()

void cluck_daemon::ticket::ticket_added ( key_map_t const & still_entering )

This function sends a LOCK_EXITING if the ticket reached the total number of TICKET_ADDED required to get a quorum (which is just one with 1 to 3 leaders.)

The still_entering paramater defines the list of tickets that are still trying to enter the same object. This is very important. It needs to be completely drained before we can proceed and mark the ticket as assigned.

Parameters

[in] still_entering The list of still entering processes

Definition at line 657 of file ticket.cpp.

References f_added_ticket_quorum, f_cluckd, f_entering_key, f_still_entering, cluck_daemon::cluckd::lock_exiting(), and send_message_to_leaders().

Referenced by add_ticket().

◆ timed_out()

bool cluck_daemon::ticket::timed_out ( ) const

This function returns true if the ticket timed out in its current state and should be moved to its next state.

The function calls the get_current_timeout_date() to select the correct date. This depends on the current state of the ticket (i.e. maybe we sent the ALIVE message and are using the alive time out value).

There are five timeout dates that can happen:

Time to obtain a lock
Time to keep the lock alive
Time to wait for a reply after an UNLOCKING message
Time to wait for the UNLOCK message
Time to wait for the ALIVE reply (i.e. the ABSOLUTELY message)

Returns: true if the ticket timed out in its current state.

Definition at line 1463 of file ticket.cpp.

References get_current_timeout_date().

Referenced by lock_failed().

◆ unserialize()

void cluck_daemon::ticket::unserialize ( std::string const & data )

This function unserialize a string that was generated using the serialize() function.

Note that unknown fields are ignored and none of the fields are considered mandatory. Actually the function generates no errors. This means it should be forward compatible.

The data gets unserialized in this object.

Parameters

[in] data The serialized data.

Definition at line 1659 of file ticket.cpp.

Member Data Documentation

◆ f_added_ticket

bool cluck_daemon::ticket::f_added_ticket = false

private

Definition at line 147 of file ticket.h.

Referenced by add_ticket(), max_ticket(), serialize(), and set_ticket_number().

◆ f_added_ticket_quorum

bool cluck_daemon::ticket::f_added_ticket_quorum = false

private

Definition at line 152 of file ticket.h.

Referenced by remove_entering(), serialize(), and ticket_added().

◆ f_alive_timeout

cluck::timeout_t cluck_daemon::ticket::f_alive_timeout = cluck::timeout_t()

private

Definition at line 131 of file ticket.h.

Referenced by get_current_timeout_date(), and set_alive_timeout().

◆ f_cluckd

cluckd* cluck_daemon::ticket::f_cluckd = nullptr

private

Definition at line 123 of file ticket.h.

Referenced by add_ticket(), entered(), lock_activated(), lock_failed(), one_leader(), send_message_to_leaders(), and ticket_added().

◆ f_entering_key

std::string cluck_daemon::ticket::f_entering_key = std::string()

private

Definition at line 141 of file ticket.h.

Referenced by ticket(), add_ticket(), drop_ticket(), entered(), entering(), get_client_pid(), get_entering_key(), lock_failed(), serialize(), set_ticket_number(), and ticket_added().

◆ f_get_max_ticket

bool cluck_daemon::ticket::f_get_max_ticket = false

private

Definition at line 142 of file ticket.h.

Referenced by entered(), and serialize().

◆ f_lock_duration

cluck::timeout_t cluck_daemon::ticket::f_lock_duration = cluck::timeout_t()

private

Definition at line 132 of file ticket.h.

Referenced by ticket(), entering(), get_lock_duration(), lock_activated(), serialize(), and set_unlock_duration().

◆ f_lock_failed

lock_failure_t cluck_daemon::ticket::f_lock_failed = lock_failure_t::LOCK_FAILURE_NONE

private

Definition at line 167 of file ticket.h.

Referenced by activate_lock(), drop_ticket(), lock_activated(), lock_failed(), and serialize().

◆ f_lock_timeout_date

cluck::timeout_t cluck_daemon::ticket::f_lock_timeout_date = cluck::timeout_t()

private

Definition at line 162 of file ticket.h.

Referenced by get_current_timeout_date(), get_lock_timeout_date(), lock_activated(), lock_failed(), and serialize().

◆ f_locked

bool cluck_daemon::ticket::f_locked = false

private

Definition at line 161 of file ticket.h.

Referenced by activate_lock(), get_current_timeout_date(), is_locked(), lock_activated(), lock_failed(), and serialize().

◆ f_messenger

messenger::pointer_t cluck_daemon::ticket::f_messenger = messenger::pointer_t()

private

Definition at line 127 of file ticket.h.

Referenced by drop_ticket(), lock_activated(), lock_failed(), and send_message_to_leaders().

◆ f_object_name

std::string cluck_daemon::ticket::f_object_name = std::string()

private

Definition at line 128 of file ticket.h.

Referenced by ticket(), add_ticket(), drop_ticket(), entered(), get_object_name(), lock_activated(), lock_failed(), send_message_to_leaders(), and serialize().

◆ f_obtention_timeout

cluck::timeout_t cluck_daemon::ticket::f_obtention_timeout = cluck::timeout_t()

private

Definition at line 130 of file ticket.h.

Referenced by ticket(), add_ticket(), entering(), get_current_timeout_date(), get_obtention_timeout(), serialize(), and set_alive_timeout().

◆ f_our_ticket

ticket_id_t cluck_daemon::ticket::f_our_ticket = NO_TICKET

private

Definition at line 146 of file ticket.h.

Referenced by add_ticket(), entered(), get_ticket_number(), max_ticket(), serialize(), and set_ticket_number().

◆ f_owner

std::string cluck_daemon::ticket::f_owner = std::string()

private

Definition at line 136 of file ticket.h.

Referenced by get_owner(), lock_activated(), lock_failed(), serialize(), and set_owner().

◆ f_serial

serial_t cluck_daemon::ticket::f_serial = NO_SERIAL

private

Definition at line 137 of file ticket.h.

Referenced by entering(), get_serial(), serialize(), and set_serial().

◆ f_server_name

std::string cluck_daemon::ticket::f_server_name = std::string()

private

Definition at line 134 of file ticket.h.

Referenced by ticket(), drop_ticket(), entering(), get_server_name(), lock_activated(), lock_failed(), and serialize().

◆ f_service_name

std::string cluck_daemon::ticket::f_service_name = std::string()

private

Definition at line 135 of file ticket.h.

Referenced by ticket(), drop_ticket(), entering(), get_service_name(), lock_activated(), lock_failed(), and serialize().

◆ f_still_entering

key_map_t cluck_daemon::ticket::f_still_entering = key_map_t()

private

Definition at line 153 of file ticket.h.

Referenced by remove_entering(), and ticket_added().

◆ f_tag

ed::dispatcher_match::tag_t cluck_daemon::ticket::f_tag = ed::dispatcher_match::DISPATCHER_MATCH_NO_TAG

private

Definition at line 129 of file ticket.h.

Referenced by ticket(), drop_ticket(), get_tag(), lock_activated(), lock_failed(), send_message_to_leaders(), and serialize().

◆ f_ticket_key

std::string cluck_daemon::ticket::f_ticket_key = std::string()

private

Definition at line 148 of file ticket.h.

Referenced by activate_lock(), add_ticket(), drop_ticket(), get_ticket_key(), remove_entering(), serialize(), and set_ticket_number().

◆ f_ticket_ready

bool cluck_daemon::ticket::f_ticket_ready = false

private

Definition at line 157 of file ticket.h.

Referenced by activate_lock(), lock_activated(), remove_entering(), serialize(), and set_ready().

◆ f_unlock_duration

cluck::timeout_t cluck_daemon::ticket::f_unlock_duration = cluck::timeout_t()

private

Definition at line 133 of file ticket.h.

Referenced by entering(), get_unlock_duration(), lock_activated(), lock_failed(), serialize(), and set_unlock_duration().

◆ f_unlocked_timeout_date

cluck::timeout_t cluck_daemon::ticket::f_unlocked_timeout_date = cluck::timeout_t()

private

Definition at line 163 of file ticket.h.

Referenced by lock_activated().

◆ NO_SERIAL

serial_t const cluck_daemon::ticket::NO_SERIAL = -1

static

Definition at line 52 of file ticket.h.

Referenced by serialize().

◆ NO_TICKET

ticket_id_t const cluck_daemon::ticket::NO_TICKET = 0

static

Definition at line 53 of file ticket.h.

Referenced by cluck_daemon::cluckd::get_last_ticket(), max_ticket(), and set_ticket_number().

The documentation for this class was generated from the following files:

daemon/ticket.h
daemon/ticket.cpp

Public Types

Public Member Functions

Static Public Attributes

Private Types

Private Attributes

Detailed Description

Introduction

The Bakery Algorithm Explained

Our implementation in cluck

Message Sequence Chart

Any drawback?

Timeouts

Deadlock

Member Typedef Documentation

◆ key_map_t

◆ object_map_t

◆ pointer_t

◆ serial_t

◆ ticket_id_t

◆ vector_t

Member Enumeration Documentation

◆ lock_failure_t

Constructor & Destructor Documentation

◆ ticket() [1/2]

◆ ticket() [2/2]

Member Function Documentation

◆ activate_lock()

◆ add_ticket()

◆ drop_ticket()

◆ entered()

◆ entering()

◆ get_client_pid()

◆ get_current_timeout_date()

◆ get_entering_key()

◆ get_lock_duration()

◆ get_lock_timeout_date()

◆ get_object_name()

◆ get_obtention_timeout()

◆ get_owner()

◆ get_serial()

◆ get_server_name()

◆ get_service_name()

◆ get_tag()

◆ get_ticket_key()

◆ get_ticket_number()

◆ get_unlock_duration()

◆ is_locked()

◆ lock_activated()

◆ lock_failed()

◆ lock_tickets()

◆ max_ticket()

◆ one_leader()

◆ operator=()

◆ remove_entering()

◆ send_message_to_leaders()

◆ serialize()

◆ set_alive_timeout()

◆ set_owner()

◆ set_ready()

◆ set_serial()

◆ set_ticket_number()

◆ set_unlock_duration()

◆ ticket_added()

◆ timed_out()

◆ unserialize()

Member Data Documentation

◆ f_added_ticket

◆ f_added_ticket_quorum

◆ f_alive_timeout

◆ f_cluckd

◆ f_entering_key

◆ f_get_max_ticket

◆ f_lock_duration

◆ f_lock_failed

◆ f_lock_timeout_date

◆ f_locked

◆ f_messenger

◆ f_object_name

◆ f_obtention_timeout

◆ f_our_ticket