libQtCassandra: QtCassandra::QCassandraLock Class Reference

QtCassandra::QCassandraLock Class Reference

Lock mechanism using only Cassandra. More...

#include <include/QtCassandra/QCassandraLock.h>

Inheritance diagram for QtCassandra::QCassandraLock:
Collaboration diagram for QtCassandra::QCassandraLock:

List of all members.

Public Member Functions

 QCassandraLock (QSharedPointer< QCassandraContext > context, const QString &object_name="", const cassandra_consistency_level_t consistency_level=CONSISTENCY_LEVEL_QUORUM)
 Create a lock for mutual exclusion.

 QCassandraLock (QSharedPointer< QCassandraContext > context, const QByteArray &object_key, const cassandra_consistency_level_t consistency_level=CONSISTENCY_LEVEL_QUORUM)
 Create a lock for mutual exclusion.

virtual ~QCassandraLock ()
 Unlock the resource associated with this lock.

bool lock (const QString &object_name)
 Lock the named resource.

bool lock (const QByteArray &object_key)
 Lock the resource.

void unlock ()
 Unlock the resource.

Private Member Functions

void internal_init (const QByteArray &object_name)
 Initialize the QCassandraLock object further.

Private Attributes

const consistency_level_t f_consistency
 This variable holds the consistency of the lock.

QSharedPointer< QCassandraContextf_context
 The context used to create this Cassandra lock.

controlled_vars::fbool_t f_locked
 The current state of this lock.

QByteArray f_object_name
 The name of the object being locked.

QSharedPointer< QCassandraTablef_table
 Pointer to the lock table.

QByteArray f_ticket_id
 The ticket of the lock.


Detailed Description

So... You're super happy, you just found Cassandra and started using it to rewrite your app. You slowly notice that there are things that you can do with Cassandra at lightning speed, no way in 1,000 years would you want to change from this concept to any other concept. But...

All the read and write in Cassandra are individual commands. Cassandra itself does not offer any way to synchronize a read or a write from all the running hosts. What can you do?

The need arise, in most cases, when your application has to create a unique row. For example, you have a registration form where a user can enter a username. That name must be unique throughout the entire database. When that happens, the Cassandra system does not help you. You need to lock that table (or at least that row) before you can create that unique row.

This is where the QCassandraLock object comes in. It will lock an object so a single process will have access to it for a while (until the lock goes out of scope or is deleted.)

The usage is expected to be something like this:

   //... ready to create the new user in the database ...
   {
      QCassandraLock lock(context, "user_table");
      if(users->exists(username))
      {
          // problem
          throw std::runtime_error("sorry, a user with that name exists");
          // Note: the lock destructor takes care of unlocking
      }
      users->row(username)->cell("email")->setValue(email);
      // Note: the lock destructor takes care of unlocking
   }

The lock is implemented using the Cassandra database system itself with the help of the Leslie Lamport's bakery algorithm (1974). You can find detailed explanation of the code on Wikipedia:

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

More details are found in the French version, somehow:

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

A Cassandra version is proposed on the following page:

http://wiki.apache.org/cassandra/Locking

The bakery algorithm is based on the basic idea that a large number of customers go to the store 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 with the smallest ticket number is served next. Once served, the ticket is destroyed. The ticket numbers can restart at one whenever the queue of customers goes empty.

On a computer without any synchronization mechanism available (our case) two customers may enter the bakery simultaneously (especially since we're 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 and its process number. These two numbers are used to further order processes.

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.)

     // declaration and initial values of global variables
     namespace {
         int num_threads = 100;
         std::vector<controlled_vars::fbool_t> entering;
         std::vector<controlled_vars::zuint32_t> tickets;
     }

     // initialize the vectors
     void init()
     {
         entering.reserve(num_threads);
         tickets.reserve(num_threads);
     }

     // i is the thread number
     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...
             [...]
         }
     }

The algorithm requires one important set of information: a list of host numbers from 1 to n. Without that list, the algorithm cannot function. Therefore, before you can use the QCassandraLock object you must add each one of your hosts to the Cassandra lock table in a row named "hosts". You need to list at least all the hosts that are to use this lock functionality; other hosts are not required. Hosts that cannot find themselves in that list generate an exception when trying to use a lock.

Adding hosts to the database is a one time call per host to the QCassandraContext::add_lock_host() function. WARNING: the add_lock_host() function cannot be called by more than one host at a time, in general, you'll use the snap_add_host command line tool to add your hosts and it should be run on a single computer at a time.

Now, to apply that algorithm to a Cassandra cluster, you want several small modifications. Our algorithm is 100% based on the bakery algorithm, however, it makes use of fully dynamic vectors for the entering and the tickets variables. These are replaced by columns in a row of the host lock table. We offer a way to lock any kind of object by give the user of the lock a way to indicate what needs to be locked by name. For example, if you're creating a new row and it needs to be unique throughout all your Cassandra host, the object to lock is that new row, so you can use the key of that new row as the name of the lock. In the sample code below we use object_name for that information. This means we can use a different vector for each lock!

      // lock "object_name"
      void lock(QString object_name)
      {
          // note: somehow object_name gets attached to this object
          QString locks = context->lockTableName();
          QString hosts_key = context->lockHostsKey();
          QString host_name = context->lockHostName();
          int host = table[locks][hosts_key][host_name];
          pid_t pid = getpid();

          // get the next available ticket
          table[locks]["entering::" + object_name][host + "/" + pid] = true;
          int my_ticket(0);
          QCassandraCells tickets(table[locks]["tickets::" + object_name]);
          foreach(tickets as t)
          {
              // we assume that t.name is the column name
              // and t.value is its value
              if(t.value > my_ticket)
              {
                  my_ticket = t.value;
              }
          }
          ++my_ticket; // add 1, since we want the next ticket
          to_unlock = my_ticket + "/" + host + "/" + pid;
          table[locks]["tickets::" + object_name][my_ticket + "/" + host + "/" + pid] = 1;
          // not entering anymore, by deleting the cell we also release the row
          // once all the processes are done with that object_name
          table[locks]["entering::" + object_name].dropCell(host + "/" + pid);
   
          // here we wait on all the other processes still entering at this
          // point; if entering more or less at the same time we cannot
          // guarantee that their ticket number will be larger, it may instead
          // be equal; however, anyone entering later will always have a larger
          // ticket number so we won't have to wait for them they will have to wait
          // on us instead; note that we load the list of "entering" once;
          // then we just check whether the column still exists; it is enough
          QCassandraCells entering(table[locks]["entering::" + object_name]);
          foreach(entering as e)
          {
              while(table[locks]["entering::" + object_name].exists(e))
              {
                  sleep();
              }
          }

          // now check whether any other process was there before us, if
          // so sleep a bit and try again; in our case we only need to check
          // for the processes registered for that one lock and not all the
          // processes (which could be 1 million on a large system!);
          // like with the entering vector we really only need to read the
          // list of tickets once and then check when they get deleted
          // (unfortunately we can only do a poll on this one too...);
          // we exit the foreach() loop once our ticket is proved to be the
          // smallest or no more tickets needs to be checked; when ticket
          // numbers are equal, then we use our host numbers, the smaller
          // is picked; when host numbers are equal (two processes on the
          // same host fighting for the lock), then we use the processes
          // pid since these are unique on a system, again the smallest wins.
          tickets = table[locks]["tickets::" + object_name];
          foreach(tickets as t)
          {
              // do we have the smallest ticket?
              // note: the t.ticket,  t.host and t.pid come from the column key
              if(t.ticket > my_ticket
              || (t.ticket == my_ticket && t.host > host)
              || (t.ticket == my_ticket && t.host == host && t.pid >= pid))
              {
                  // do not wait on larger tickets, just ignore them
                  continue;
              }
              // not smaller, wait for the ticket to go away
              while(table[locks]["tickets::" + object_name][t.column_key].exists(t.name))
              {
                  sleep();
              }
              // that ticket was released, we may have priority now
              // check the next ticket
          }
      }
      
      // unlock "object_name" (as saved in this object)
      void unlock()
      {
          // release our ticket
          QString locks = context->lockTableName();
          table[locks]["tickets::" + object_name].dropCell(to_unlock);
      }
      
      // sample process
      void SomeProcess(QString object_name)
      {
          while(true)
          {
              [...]
              // non-critical section...
              lock(object_name);
              // The critical section code goes here...
              unlock(object_name);
              // non-critical section...
              [...]
          }
      }

VERY IMPORTANT: all database accesses must be done with at least QUORUM if you have multiple centers and want to lock between all centers then the Network Quorum must be used. The ALL is also another option. Only if you want to lock local processes can you use ONE, assuming that all those processes attach themselves to the same Cassandra server.

Note that the name of the lock table can be changed in your context if done early enough (i.e. before any lock is ever created by that process.) By default it is set to "libQtCassandraLockTable". See the QCassandraContext::set_lock_table_name() function for details.

Locks are created to lock any resource that you want to lock. It does not even have to be Cassandra data. Just resources that need to be accessed by at most one process at a time.

The name of the object (object_name) represents the resource to be locked. This can be anything you want. For example, to lock a row in a table, we suggest the name of the table followed by the name of the row, eventually using a separator such as "::". This lock works even for rows that do not yet exist since the lock itself doesn't need the row to lock it.

     // Note: Since "table_name" cannot include a ":" this is always
     //       a unique object name!
     object_name = table_name + "::" + row_name;

For example, you have a user registering on your website and you request that user to enter a username. That username becomes the row key in your users table. Say the user enters "snap" for his username, then following our example the object name would be: "users::snap".

The lock is attempted for a limited amount of time as specified in the context with the QCassandraContext::set_lock_timeout().

Note:
It is possible to lock as many resources as you want. However, it is very likely that you will run in lockup problems if you attempt to lock more than one resource at a time from multiple processes. Instead, think about the problem and create one higher level lock that locks everything you need at once. That way you completely avoid lockups in your applications.
Warning:
Althoug this class allows you to lock multiple processes, it is NOT thread safe. If you are using multiple threads in your application, then you should create one thread that locks and unlocks process resources.
Bug:
If something goes wrong, as in a read or a write fails, the system throws and tries to remove the lock. When a lock times out (takes too long to lock the resource,) it may be because a process died without unlocking the given resource. This also means that the lock table now includes information that will actually not be deleted until it times out (because of its TTL.) Obviously that means all the other processes will timeout until that TTL kicks in. Finally, there isn't a really safe way to clean up such a mess. More or less, what this means is that the entire process better never fail (which is why you want "many" nodes and a QUORUM is pretty much always attainable.) This being said, we use a short TTL on all the data because a process should never take that long to handle its resource. That TTL is a guarantee that resources get released even if the resource owner does not properly release it (because of a bad crash, the host gets interrupted, the Internet connections are not cooperative...) Obviously you will always be able to connect to your cluster with cassandra-cli and delete the offensive lock data if required.
Warning:
The main failure mechanism requires your C++ compiler to make use of proper RAII all the way. In Linux this often means that you need to have a try/catch somewhere like in your main() function. Without that, the unlock() function may not be called blocking all the other processes until the TTL kicks in.

Definition at line 49 of file QCassandraLock.h.


Constructor & Destructor Documentation

QtCassandra::QCassandraLock::QCassandraLock ( QSharedPointer< QCassandraContext context,
const QString &  object_name = "",
const cassandra_consistency_level_t  consistency_level = CONSISTENCY_LEVEL_QUORUM 
)

This function is an overload of the QCassandraLock. It does the same as the other constructors except that the name of the object can be specified as UTF-8.

Parameters:
[in]contextThe context where the lock is to be created.
[in]object_nameThe name of the object to be locked as a QString.
[in]consistency_levelThe level to use for the lock, defaults to QUORUM.

Definition at line 502 of file QCassandraLock.cpp.

References internal_init().

QtCassandra::QCassandraLock::QCassandraLock ( QSharedPointer< QCassandraContext context,
const QByteArray &  object_name,
const cassandra_consistency_level_t  consistency_level = CONSISTENCY_LEVEL_QUORUM 
)

This function creates an inter process lock for the safety usage of shared resources by means of mutual exclusion. In other words, a read/write full exclusive access to any Cassandra content.

The lock implementation is documented in the class documentation, see QCassandraLock.

Note that if object_name is set to an empty string, then the lock is not obtained in the constructor. Instead you have to call the lock() function. Not obtaining the lock in the constructor gives you a chance to avoid the throw on failure.

Warning:
The object name is left available in the lock table. Do not use any secure/secret name/word, etc. as the object name.
Exceptions:
std::runtime_errorThis exception is raised if the lock cannot be obtained after the lock times out. This only happens if a named object is specified on the constructor. To avoid this exception, use the lock() function after construction and make sure to test the returned result.
Parameters:
[in]contextThe context where the lock is created.
[in]object_nameThe resource to be locked.
[in]consistency_levelThe level to use for the lock, defaults to QUORUM.
See also:
QCassandraContext::addLockHost()
QCassandraContext::setLockTimeout()
QCassandraContext::setLockTableName()
lock()
unlock()

Definition at line 553 of file QCassandraLock.cpp.

References internal_init().

The QCassandraLock destructor ensures that the associated resource, if any, gets unlocked before it completely goes away.

Although the function is considered safe in regard to the C++ language semantic, the unlock() may fail for many reasons, one reason being that the Cassandra cluster is somehow not available anymore.

Definition at line 602 of file QCassandraLock.cpp.

References unlock().


Member Function Documentation

void QtCassandra::QCassandraLock::internal_init ( const QByteArray &  object_name) [private]

This function initialize the QCassandraLock object.

Parameters:
[in]object_nameThe resource to be locked.

Definition at line 574 of file QCassandraLock.cpp.

References f_context, f_table, and lock().

Referenced by QCassandraLock().

bool QtCassandra::QCassandraLock::lock ( const QString &  object_name)

This function transforms the object name in a usable key (i.e. the UTF-8 of the object name.) It then calls the other lock() function.

Parameters:
[in]object_nameThe name of the object to lock.
Returns:
true if the object lock was obtained; false otherwise

Definition at line 617 of file QCassandraLock.cpp.

Referenced by internal_init().

bool QtCassandra::QCassandraLock::lock ( const QByteArray &  object_name)

This function locks the specified resource object_name. It returns when the resource is locked or when the lock timeout is reached.

See the QCassandraLock constructor for more details about the locking mechanisms.

Note that if lock() is called with an empty string then the function unlocks the lock and returns immediately with false. This is equivalent to calling unlock().

Note:
The function reloads all the parameters (outside of the table) because we need to support a certain amount of dynamism. For example, an administrator may want to add a new host on the system. In that case, the list of host changes and it has to be detected here.
Warning:
The object name is left available in the lock table. Do not use any secure/secret name/word, etc. as the object name.
Bug:
At this point there is no proper protection to recover from errors that would happen while working on locking this entry. This means failures may result in a lock that never ends.
Parameters:
[in]object_nameThe resource to be locked.
Returns:
true if the lock was successful, false otherwise.
See also:
unlock()

Definition at line 655 of file QCassandraLock.cpp.

References QtCassandra::appendUInt32Value(), f_consistency, f_context, f_locked, f_object_name, f_table, f_ticket_id, QtCassandra::QCassandraValue::setCharValue(), QtCassandra::QCassandraColumnPredicate::setConsistencyLevel(), QtCassandra::QCassandraValue::setConsistencyLevel(), QtCassandra::QCassandraColumnRangePredicate::setCount(), QtCassandra::QCassandraColumnRangePredicate::setEndColumnKey(), QtCassandra::QCassandraValue::setTtl(), QtCassandra::QCassandra::timeofday(), QtCassandra::QCassandraValue::TIMESTAMP_MODE_DEFINED, QtCassandra::uint32Value(), and unlock().

This function unlocks the resource specified in the call to lock().

Definition at line 955 of file QCassandraLock.cpp.

References f_consistency, f_locked, f_object_name, f_table, f_ticket_id, QtCassandra::QCassandra::timeofday(), and QtCassandra::QCassandraValue::TIMESTAMP_MODE_DEFINED.

Referenced by lock(), and ~QCassandraLock().


Member Data Documentation

This variable is used to hold the consistency level used to read and write data for this lock.

By default is is set to QUORUM so it works accross your entire cluster. However, you may have optimizations which could be used to allow a LOCAL QUORUM instead (much faster if you have many data centers.)

At this point all the consistency levels are accepted in this variable.

Definition at line 68 of file QCassandraLock.h.

Referenced by lock(), and unlock().

The QCassandraLock needs to have access to the context in which it is created. Its shared pointer is saved in this variable.

The context pointer cannot be null (the constructors throw if the context pointer is null.)

Definition at line 63 of file QCassandraLock.h.

Referenced by internal_init(), and lock().

Whether the lock is currently in effect (true) or not (false).

The lock() function sets this value to true when the lock succeeds.

The unlock() function sets this value to false once the lock was released.

The lock constructors set this flag to false by default. If you specify the name of the object to lock in the constructor, then the lock() is called so in effect it will look like the constructor sets the variable to true.

Definition at line 67 of file QCassandraLock.h.

Referenced by lock(), and unlock().

Whenever you create a lock, you give it a name. This is where the lock object saves that name. The name is expected to be shared between all the locking processes.

The name is used by the unlock() to remove the lock, it is then cleared.

Definition at line 65 of file QCassandraLock.h.

Referenced by lock(), and unlock().

On creation of a lock object, it calls its parent context to request the lock table. If it does not exist yet, the context creates it and waits until the Cassandra cluster is synchronized. This means the first lock may actually take a very long time to obtain. To make sure it always works, you should have an initialization process in your application such that a lock table is created before your full application ever runs.

The test cassandra_lock can currently be used for that purpose. A tool will be added later to apply those commands by scripts.

Definition at line 64 of file QCassandraLock.h.

Referenced by internal_init(), lock(), and unlock().

When a call to lock() succeeds, the lock created a ticket and this is its identifier. The ticket is kept internally so the unlock() functions does not have to attempt to determine its value later. It can just delete it.

The ticket identifier is cleared by the unlock() function.

Definition at line 66 of file QCassandraLock.h.

Referenced by lock(), and unlock().


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

This document is part of the Snap! Websites Project.

Copyright © 2011-2013 by Made to Order Software Corp.

Syndicate content

Snap! Websites
An Open Source CMS System in C++

Contact Us Directly