cs::apply::Commit_order_queue Class Reference

Queue to maintain the ordered sequence of workers waiting for commit. More...

#include <commit_order_queue.h>

Classes
class	Iterator
	Iterator helper class to iterate over the Commit_order_queue following the underlying commit order. More...
class	Node
	Queue element, holding the needed information to manage the commit ordering. More...

Public Types
enum class	enum_worker_stage {   REGISTERED , FINISHED_APPLYING , REQUESTED_GRANT , WAITED ,   WAITED_OVERTAKE , FINISHED }
	Enumeration to represent each worker state. More...
using	value_type = unsigned long
using	queue_type = container::Integrals_lockfree_queue< value_type >
using	sequence_type = unsigned long long

Public Member Functions
	Commit_order_queue (size_t n_workers)
	Constructor for the class, takes the number of workers and initializes the underlying static list with such size. More...
virtual	~Commit_order_queue ()=default
	Default destructor for the class. More...
Node &	operator[] (value_type id)
	Retrieve the commit order information Node for worker identified by id. More...
Commit_order_queue::queue_type::enum_queue_state	get_state ()
	Retrieves the error state for the current thread last executed queue operation. More...
bool	is_empty ()
	Whether or not there are more workers to commit. More...
std::tuple< value_type, sequence_type >	pop ()
	Removes from the queue and returns the identifier of the worker that is first in-line to commit. More...
void	push (value_type id)
	Adds to the end of the commit queue the worker identifier passed as parameter. More...
value_type	front ()
	Retrieves the identifier of the worker that is first in-line to commit. More...
void	clear ()
	Removes all remaining workers from the queue. More...
void	freeze ()
	Acquires exclusivity over changes (push, pop) on the queue. More...
void	unfreeze ()
	Releases exclusivity over changes (push, pop) on the queue. More...
Iterator	begin ()
	Retrieves an iterator instance that points to the head of the commit queue and that will iterate over the worker Nodes that are in-line to commit, following the requested commit order. More...
Iterator	end ()
	Retrieves an iterator instance that points to the tail of the commit queue. More...
std::string	to_string ()
	Retrieves the textual representation of this object's underlying commit queue. More...
std::tuple< value_type, sequence_type >	remove (value_type index)
	Removes from the queue and returns the first identifier of the worker that is equal to index. More...

Static Public Member Functions
static sequence_type	get_next_sequence_nr (sequence_type current_seq_nr)
	Returns the expected next number in the ticket sequence. More...

Static Public Attributes
static constexpr value_type	NO_WORKER

Private Member Functions
std::tuple< value_type, value_type >	remove_from_commit_queue (value_type to_remove)
	Removes from the commit queue the first identifier that is equal to index. More...

Private Attributes
memory::Aligned_atomic< sequence_type >	m_commit_sequence_generator
	The commit sequence number counter. More...
std::vector< Commit_order_queue::Node >	m_workers
	The list of worker Nodes, indexed by worker ID. More...
queue_type	m_commit_queue
	The queue to hold the sequence of worker IDs waiting to commit. More...
lock::Shared_spin_lock	m_push_pop_lock
	The lock to acquire exlusivity over changes on the queue. More...

Friends
std::ostream &	operator<< (std::ostream &out, Commit_order_queue &to_output)
	Friend operator for writing to an std::ostream object. More...

Detailed Description

Queue to maintain the ordered sequence of workers waiting for commit.

The queue has a static list of elements, each one representing each worker commit information.

The management of the order by which each worker will commit is implemented using:

• A member variable pointing to the first worker to commit, the head.
• A member variable pointing to the last worker to commit, the tail.
• Each queue element holds a member variable that points to the next worker to commit, the next.
• Pushing a new element will move the tail.
• Popping an element will move the head.

Atomics are used to make the queue thread-safe without the need for an explicit lock.

Member Typedef Documentation

queue_type

using cs::apply::Commit_order_queue::queue_type = container::Integrals_lockfree_queue<value_type>

sequence_type

using cs::apply::Commit_order_queue::sequence_type = unsigned long long

value_type

using cs::apply::Commit_order_queue::value_type = unsigned long

Member Enumeration Documentation

enum_worker_stage

enum class cs::apply::Commit_order_queue::enum_worker_stage

strong

Enumeration to represent each worker state.

Enumerator
REGISTERED
FINISHED_APPLYING
REQUESTED_GRANT
WAITED
WAITED_OVERTAKE
FINISHED

Constructor & Destructor Documentation

Commit_order_queue()

cs::apply::Commit_order_queue::Commit_order_queue

(

size_t

n_workers

)

Constructor for the class, takes the number of workers and initializes the underlying static list with such size.

Parameters

n_workers

The number of workers to include in the commit order managerment.

~Commit_order_queue()

virtual cs::apply::Commit_order_queue::~Commit_order_queue ( )

virtualdefault

Default destructor for the class.

Member Function Documentation

begin()

cs::apply::Commit_order_queue::Iterator cs::apply::Commit_order_queue::begin

(

void

)

Retrieves an iterator instance that points to the head of the commit queue and that will iterate over the worker Nodes that are in-line to commit, following the requested commit order.

Returns

An instance of Iterator pointing to the queue's head, that iterates over the workers that are in-line to commit and following the requested commit order.

clear()

void cs::apply::Commit_order_queue::clear

(

)

Removes all remaining workers from the queue.

end()

cs::apply::Commit_order_queue::Iterator cs::apply::Commit_order_queue::end

(

void

)

Retrieves an iterator instance that points to the tail of the commit queue.

Returns

An instance of Iterator that points to the tail of the queue.

freeze()

void cs::apply::Commit_order_queue::freeze

(

)

Acquires exclusivity over changes (push, pop) on the queue.

front()

cs::apply::Commit_order_queue::value_type cs::apply::Commit_order_queue::front

(

)

Retrieves the identifier of the worker that is first in-line to commit.

Returns

The identifier of the worker that is first in-line to commit.

get_next_sequence_nr()

cs::apply::Commit_order_queue::sequence_type cs::apply::Commit_order_queue::get_next_sequence_nr ( sequence_type  current_seq_nr )

static

Returns the expected next number in the ticket sequence.

Parameters

current_seq_nr

The current sequence number, for which the next should be computed.

Returns

The expected next number in the ticket sequence.

get_state()

cs::apply::Commit_order_queue::queue_type::enum_queue_state cs::apply::Commit_order_queue::get_state

(

)

Retrieves the error state for the current thread last executed queue operation.

Values may be:

• SUCCESS is the operation succeeded.
• NO_MORE_ELEMENTS if the last pop tried to access an empty queue.
• NO_SPACE_AVAILABLE if the last push tried to push while the queue was full.

Returns

The error state for the thread's last operation on the queue.

is_empty()

bool cs::apply::Commit_order_queue::is_empty

(

)

Whether or not there are more workers to commit.

Returns

True if there are no more workers, false otherwise.

operator[]()

cs::apply::Commit_order_queue::Node & cs::apply::Commit_order_queue::operator[]

(

value_type

id

)

Retrieve the commit order information Node for worker identified by id.

Parameters

id	The identifier of the worker

Returns

A reference to the commit order information Node for the given worker.

pop()

std::tuple< cs::apply::Commit_order_queue::value_type, cs::apply::Commit_order_queue::sequence_type > cs::apply::Commit_order_queue::pop

(

)

Removes from the queue and returns the identifier of the worker that is first in-line to commit.

If another thread is accessing the commit order sequence number and has frozen it's state, this operation will spin until the state is unfrozen.

Returns

A tuple holding the identifier of the worker that is first in-line to commit and the sequence number for the commit request of the worker scheduled after this one (or NO_SEQUENCE_NR if there is no next worker).

push()

void cs::apply::Commit_order_queue::push

(

value_type

id

)

Adds to the end of the commit queue the worker identifier passed as parameter.

Parameters

id	The identifier of the worker to add to the commit queue.

remove()

std::tuple< cs::apply::Commit_order_queue::value_type, cs::apply::Commit_order_queue::sequence_type > cs::apply::Commit_order_queue::remove

(

value_type

index

)

Removes from the queue and returns the first identifier of the worker that is equal to index.

Returns

A tuple holding the identifier of the worker equal to index and the sequence number for the commit request of the worker scheduled after this one (or NO_SEQUENCE_NR if there is no next worker).

remove_from_commit_queue()

std::tuple< cs::apply::Commit_order_queue::value_type, cs::apply::Commit_order_queue::value_type > cs::apply::Commit_order_queue::remove_from_commit_queue ( value_type  to_remove )

private

Removes from the commit queue the first identifier that is equal to index.

Parameters

to_remove

The value to remove from the queue.

Returns

A tuple, where:

• The first component is the removed value, or NO_WORKER if the value was not found.
• The second component is the value preceding the removed one, or NO_WORKER if the value was not found, or was found in the first slot.

to_string()

std::string cs::apply::Commit_order_queue::to_string

(

)

Retrieves the textual representation of this object's underlying commit queue.

Returns

The textual representation of this object's underlying commit queue.

unfreeze()

void cs::apply::Commit_order_queue::unfreeze

(

)

Releases exclusivity over changes (push, pop) on the queue.

Friends And Related Function Documentation

operator<<

std::ostream & operator<< ( std::ostream &  out, Commit_order_queue &  to_output  )

friend

Friend operator for writing to an std::ostream object.

See also

std::ostream::operator<<

Member Data Documentation

m_commit_queue

queue_type cs::apply::Commit_order_queue::m_commit_queue

private

The queue to hold the sequence of worker IDs waiting to commit.

m_commit_sequence_generator

memory::Aligned_atomic<sequence_type> cs::apply::Commit_order_queue::m_commit_sequence_generator

private

Initial value:

{
      Node::SEQUENCE_NR_FROZEN + 1}

The commit sequence number counter.

m_push_pop_lock

lock::Shared_spin_lock cs::apply::Commit_order_queue::m_push_pop_lock

private

The lock to acquire exlusivity over changes on the queue.

m_workers

std::vector<Commit_order_queue::Node> cs::apply::Commit_order_queue::m_workers

private

The list of worker Nodes, indexed by worker ID.

NO_WORKER

constexpr value_type cs::apply::Commit_order_queue::NO_WORKER

staticconstexpr

Initial value:

{
      queue_type::null_value}

---

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

• sql/changestreams/apply/commit_order_queue.h
• sql/changestreams/apply/commit_order_queue.cc