Vector clocks

 

Once of the concepts I found difficult initially when looking at non-relational systems is the concept of the vector clock.  Some databases – like Cassandra - use timestamps to work out which is the “latest” transaction. If there are two conflicting modifications to a column value, the one with the highest timestamp will be considered the most recent and the most correct.

Other Dynamo systems use a more complex mechanism known as a vector clock. The vector clock has the advantage of not requiring clock synchronization across all nodes, and helps us identify transactions that might be in conflict.

Despite its name, the vector clock does not include any timestamps. Rather it is composed of a set of counters. These counters are incremented when operations complete, in a similar way to the traditional System Change Number pattern that we are familiar with from relational systems like Oracle. The set contains one counter for each node in the cluster. Whenever an operation occurs on a node, that node will increment its own counter within its vector clock. Whenever a node transmits an operation to another node it will include its vector clock within the request. The transmitted vector clock will include the highest counter for the transmitting node as well is the highest counters from other nodes that the transmitting node has ever seen.

When a node receives possibly conflicting updates from other nodes, it can compare the vector clocks to determine the relative sequencing of the requests. There is a defined set of vector clock operations that can tell if:

• The two vector clocks come from nodes that are completely in sync
• One node is “out of date” with respect of the other node
• The clocks are “concurrent” in that each node has some information that is more up to date than the other node. In this case we can’t choose which update is truly the more correct.

Vector clocks are notoriously difficult to understand, though the underlying algorithm is really quite simple. The diagram below shows an example of three vector clocks incrementing across three nodes. The algorithm is somewhat simplified to improve clarity

 

In the example the vector clocks start out set to 0 for all nodes (1). Updates to nodes from external clients caused the nodes to increment their own element of the vector clock (2). When these changes are propagated to other nodes, the receiving node updates its vector clock and merges the vector clocks from the other nodes (3). Event (H) occurs when node 2 receives the vector clock (F) from node 1 and (G) from node 3 (4). Each of these vector clocks contain elements higher than the other - vector clock F has the higher value for node 1, while vector clock G has the higher value for node 3. There is no way for node 2 to be sure which of the two vector clocks represent the most up-to-date data - each of the sending nodes “knows” something that the other node does not, and consequently it’s not clear which of the two nodes “knows” best.

For those of us from the world of strictly consistent databases like Oracle, think of the vector clock as a set of System Change Numbers from each system.  We examine the SCNs from each node to see if there are nodes that might not have seen all the changes that have been recorded on another node.

The Vector clock in above us that Version G and Version F are conflicting – each contains information from unique updates that could both contain important information. What then, is the system to do? Here are some of the options:

• Revert to last write wins: two updates are unlikely to have occurred at the exact same nanosecond, so one will have a higher timestamp value. We could decide that the highest timestamp “wins”.
• Keep both copies, and require that the application or the user resolve the conflict.
• Somehow merge the data. This is the approach taken by the original Dynamo which managed Amazon’s shopping cart. If there are two conflicting shopping carts they are merged and the worst that can happen (from Amazon’s point of view) is that you buy some things twice. Another merge can occur with things like counters: rather than having one counter increment overwrite another, we can deduce that both operations wanted to increment the counter and increment it twice. A special class of data types: Conflict-Free Replicated Data Type (CRDT) exist that allow these sort of merges to be predefined.

There are advocates for the vector clock – such as the architects of Riak - , and advocates for the timestamp system used in Cassandra. Neither party disagree about the concrete implications of the two approaches: they differ on the desirability of the consequences. Last Write Wins represents a simpler model for the application developer and administrator, Vector clocks allow for conflicts to be identified but which must then be resolved.   In a later post I’ll give an example of how you programmatically resolve conflicts in Riak.

Working with Cassandra 0.7

In this post,  I experimented with inserting data from Oracle into Cassandra column families using Hector.  Unfortunately, that code isn’t compatible with the latest Cassandra 0.7 release, so I had to rework it.  The new version uses the addInsertion method of the Mutator object and while not totally intuitive didn’t take long to get working.  Here are the key changes:

   1: private static void insertSales(Connection oracleConn, Keyspace keyspace,

   2:         String cfName) throws SQLException {

   3:     int rows = 0;

   4:     ColumnPath cf = new ColumnPath(cfName);

   5:     Statement query = oracleConn.createStatement();

   6:  

   7:     String sqlText = "SELECT cust_id, cust_first_name,  cust_last_name, prod_name, "

   8:             + "           SUM (amount_sold) sum_amount_sold,sum(quantity_sold) sum_quantity_sold "

   9:             + "          FROM sh.sales    "

  10:             + "          JOIN sh.customers USING (cust_id) "

  11:             + "          JOIN sh.products  USING (prod_id)  "

  12:             + "         GROUP BY cust_id, cust_first_name,  cust_last_name,  prod_name "

  13:             + "         ORDER BY cust_id, prod_name ";

  14:     ResultSet results = query.executeQuery(sqlText);

  15:     int rowCount = 0;

  16:     int lastCustId = -1;

  17:     while (results.next()) { // For each customer

  18:         Integer custId = results.getInt("CUST_ID");

  19:         String keyValue = custId.toString();

  20:  

  21:         if (rowCount++ == 0 || custId != lastCustId) { // New Customer

  22:             String custFirstName = results.getString("CUST_FIRST_NAME");

  23:             String custLastName = results.getString("CUST_LAST_NAME");

  24:             System.out.printf("%s %s\n", custFirstName, custLastName);

  25:             // Create a supercolumn for customer details (first, lastname)

  26:             Mutator<String> mutator = HFactory.createMutator(keyspace,

  27:                     stringSerializer);

  28:             mutator.addInsertion(keyValue, cfName, HFactory

  29:                     .createSuperColumn("CustomerDetails", Arrays

  30:                             .asList(HFactory.createStringColumn(

  31:                                     "customerFirstName", custFirstName)),

  32:                             StringSerializer.get(), StringSerializer.get(),

  33:                             StringSerializer.get()));

  34:             mutator.addInsertion(keyValue, cfName, HFactory

  35:                     .createSuperColumn("CustomerDetails", Arrays

  36:                             .asList(HFactory.createStringColumn(

  37:                                     "customerLastName", custLastName)),

  38:                             StringSerializer.get(), StringSerializer.get(),

  39:                             StringSerializer.get()));

  40:  

  41:             mutator.execute();

  42:         }

  43:         // Insert product sales total for that customer

  44:         String prodName = results.getString("PROD_NAME");

  45:         Float SumAmountSold = results.getFloat("SUM_AMOUNT_SOLD");

  46:         Float SumQuantitySold = results.getFloat("SUM_QUANTITY_SOLD");

  47:         // Supercolumn name is the product name

  48:         Mutator<String> mutator = HFactory.createMutator(keyspace,

  49:                 stringSerializer);

  50:         mutator.addInsertion(keyValue, cfName, HFactory.createSuperColumn(

  51:                 prodName, Arrays.asList(HFactory.createStringColumn(

  52:                         "AmountSold", SumAmountSold.toString())),

  53:                 StringSerializer.get(), StringSerializer.get(),

  54:                 StringSerializer.get()));

  55:         mutator.addInsertion(keyValue, cfName, HFactory.createSuperColumn(

  56:                 prodName, Arrays.asList(HFactory.createStringColumn(

  57:                         "QuantitySold", SumQuantitySold.toString())),

  58:                 StringSerializer.get(), StringSerializer.get(),

  59:                 StringSerializer.get()));

  60:         mutator.execute(); 

  61:         lastCustId = custId;

  62:         rows++;

  63:     }

  64:     System.out.println(rows + " rows loaded into " + cf.getColumn_family());

  65: }

The reason why I wanted to do this was to play with Cassandra using our (relatively) new Toad for Cloud Databases Eclipse client.  Toad for Cloud Databases lets you work with non-relational datasources such as Cassandra, HBase, SimpleDB, etc, using SQL.   

Here’s how it works.  We select the column family we want to map from the Cassandra server:

That column family contains data loaded from both the Oracle CUSTOMER and SALES tables.   Toad recognizes that the data in that single column family is best represented by two normalized tables,  and gives us the opportunity to specify the names for the primary and foreign keys.  We can also rename the “tables” (more like views really) that Toad will create:

The resulting tables look similar to the tables that we originally loaded from Oracle, and we can issue SQL queries against them just as we could have with Oracle.  The queries get translated from SQL to thrift calls against the underlying Cassandra Server:

I definitely find it easier to issue SQL than write a 200 line Java program to do the same thing!  Of course, I'm not much of a Java programmer, but at a minimum having Toad to query the Cassandra data is invaluable when checking to see that your program did was it was intended to do 

Oracle tables vs Cassandra SuperColumns

 

In my last post,  I wrote some Java code to insert Oracle tables into Cassandra column families.  As much fun as this was for me, it was  fairly trivial and not a particularly useful exercise in terms of learning Cassandra. 

In Cassandra,  data modelling is very different from the relational models we are used to and one would rarely convert a complete Oracle schema from tables directly to ColumnFamilies .  Instead, Cassandra data modelling involves the creation of ColumnFamilies with SuperColumns to represent master-detail structures that are commonly referenced together

SuperColumns vs Relational schema

At the Cassandra Summit in August,  Eben Hewitt gave a presentation on Cassandra Data Modelling.   There’s a lot of nuance in that talk and in the topic, but a key point in Cassandra – as in many other NoSQL databases – is that you model data to match the queries you need to satisfy,  rather than to a more theoretically "pure" normalized form.   For relational guys, the process is most similar to radical denormalization in which you introduce redundancy to allow for efficient query processing.

For example, let’s consider the Oracle SH sample schema.  Amongst other things, it includes SALES, PRODUCTS and CUSTOMERS:

We could map each Oracle table to a Cassandra ColumnFamily, but because there are no foreign key indexes or joins,  such a Cassandra data model would not necessarily support the types of queries we want.  For instance, if we want to query sales totals by customer ID, we should create a column family keyed by customer id, which contains SuperColumns named for each product which in turn includes columns for sales totals.  It might look something like this:

ID	CustomerDetails	Product Name #1	Product Name #2	…………..	Product Name #N
1	First Name Last Name Guy Harrison	Quantity Value 3 $100,020		…………..	Quantity Value 3 $130,000
2	First Name Last Name Greg Cottman		Quantity Value 34 $10,080	…………..	Quantity Value 4 $99,000

Each customer “row” has super column for each product that contains the sales for that product.  Not all customers have all the supercolumns - each customer has supercolumns only for each product they have purchased.  The name of the SuperColumn is the name of the product.  

Giving the column the name of the product is a major departure from how we would do things in Oracle.  The name of a column or SuperColumn can be determined by the data, not by the schema - a concept completely alien to relational modelling.

Inserting into SuperColumns with Hector

To try and understand this,  I created a Cassandra columnfamily of the type “Super”.  Here’s my definition in the storage-conf.xml file:

<ColumnFamily Name="SalesByCustomer" 
                  ColumnType="Super"
                  CompareWith="UTF8Type"
                  CompareSubcolumnsWith="UTF8Type"
                  Comment="Sales summary for each customer "/>

And here is some of my Hector Java program, which reads sales totals for each customer from the Oracle sample schema, and inserts them into the ColumnFamily:

   1: private static void insertSales(Connection oracleConn, Keyspace keyspace,

   2:         String cfName) throws SQLException {

   3:     int rows = 0;

   4:     ColumnPath cf = new ColumnPath(cfName);

   5:     Statement query = oracleConn.createStatement();

   6:  

   7:     String sqlText = "SELECT cust_id, cust_first_name,  cust_last_name, prod_name, "

   8:             + "           SUM (amount_sold) sum_amount_sold,sum(quantity_sold) sum_quantity_sold "

   9:             + "          FROM sh.sales    "

  10:             + "          JOIN sh.customers USING (cust_id) "

  11:             + "          JOIN sh.products  USING (prod_id)  "

  12:             + "         GROUP BY cust_id, cust_first_name,  cust_last_name,  prod_name "

  13:             + "         ORDER BY cust_id, prod_name ";

  14:     ResultSet results = query.executeQuery(sqlText);

  15:     int rowCount = 0;

  16:     int lastCustId = -1;

  17:     while (results.next()) { // For each customer

  18:         Integer custId = results.getInt("CUST_ID");

  19:         String keyValue = custId.toString();

  20:  

  21:         if (rowCount++ == 0 || custId != lastCustId) { // New Customer

  22:             String custFirstName = results.getString("CUST_FIRST_NAME");

  23:             String custLastName = results.getString("CUST_LAST_NAME");

  24:             System.out.printf("%s %s\n", custFirstName, custLastName);

  25:             //Create a supercolumn for customer details (first, lastname)     

  26:             cf.setSuper_column(StringUtils.bytes("CustomerDetails"));

  27:             cf.setColumn(StringUtils.bytes("customerFirstName"));

  28:             keyspace.insert(keyValue, cf, StringUtils.bytes(custFirstName));

  29:             cf.setColumn(StringUtils.bytes("customerLastName"));

  30:             keyspace.insert(keyValue, cf, StringUtils.bytes(custLastName));

  31:         }

  32:         //Insert product sales total for that customer 

  33:         String prodName = results.getString("PROD_NAME");

  34:         Float SumAmountSold = results.getFloat("SUM_AMOUNT_SOLD");

  35:         Float SumQuantitySold = results.getFloat("SUM_QUANTITY_SOLD");

  36:         //Supercolumn name is the product name 

  37:         cf.setSuper_column(StringUtils.bytes(prodName));

  38:         cf.setColumn(StringUtils.bytes("AmountSold"));

  39:         keyspace.insert(keyValue, cf, StringUtils.bytes(SumAmountSold.toString()));

  40:         cf.setColumn(StringUtils.bytes("QuantitySold"));

  41:         keyspace.insert(keyValue, cf, StringUtils.bytes(SumQuantitySold.toString()));

  42:         

  43:         lastCustId = custId;

  44:         rows++;

  45:     }

  46:     System.out.println(rows + " rows loaded into " + cf.getColumn_family());

  47: }

This code is fairly straightforward,  but let’s step through it anyway:

Lines	Description
7-14	Execute the Oracle SQL to get product summaries for each customer
17	Loop through each row returned (one row per product per customer)
21	Check to see if this is a completely new customer
26-30	If it is a new customer,  create the CustomerDetails SuperColumn for that customer.  The SuperColumn name is “CustomerDetails” and it contains columns for Firstname and Lastname.
37-41	Now we create a SuperColumn for a specfic product, still keyed to the customer.  The SuperColumn name is set to the name of the product (line 37).  Inside the supercolumn are placed columns “AmountSold” (lines 38-39) and “QuantitySold” (lines 40-41)

Querying SuperColumns

Inserting master detail relationships into a supercolumn column family was easy enough.  I had a lot more difficulty writing code to query the data.  The tricky part seems to be when you don’t know the name of the SuperColumn you want to read from.  There's no direct equivalent to the JDBC ResultMetaData object to query the SuperColumn names - instead you create a "SuperSlice" predictate that defines a range of SuperColumns that you want to retrieve.  It's a bit awkward to express the simple case in which you want to return all the SuperColumns. 

Below is a bit of code which retrieves sales totals for a specific customer id.  I suspect I've made a few newbie mistakes :-):

   1: public static void querySuperColumn(Keyspace keyspace, String cfName,

   2:         String keyValue) {

   3:  

   4:     ColumnPath colFamily = new ColumnPath(cfName);

   5:     System.out.println("Details for customer id " + keyValue);

   6:  

   7:     /* Get Customer Details */

   8:     colFamily.setSuper_column(StringUtils.bytes("CustomerDetails"));

   9:     SuperColumn custDetailsSc = keyspace

  10:             .getSuperColumn(keyValue, colFamily);

  11:     for (Column col : custDetailsSc.getColumns()) {

  12:         String colName = StringUtils.string(col.getName()); 

  13:         String colValue = StringUtils.string(col.getValue()); 

  14:         System.out.printf("\t%-20s:%-20s\n", colName, colValue);

  15:     }

  16:     /* Get dynamic columns -  */

  17:     ColumnParent colParent = new ColumnParent(cfName);

  18:     SliceRange sliceRange = new SliceRange(StringUtils.bytes(""), StringUtils

  19:             .bytes(""), false, 2 ^ 32); // TODO: what if there are > 2^32 ??                                             

  20:     SlicePredicate slicePredicate = new SlicePredicate();

  21:     slicePredicate.setSlice_range(sliceRange);

  22:     //TODO:  Surely there's an easier way to select all SC than the above??

  23:     List superSlice = keyspace.getSuperSlice(keyValue,

  24:             colParent, slicePredicate);

  25:     for (SuperColumn prodSuperCol : superSlice) {  //For each super column

  26:         String superColName = StringUtils.string(prodSuperCol.getName());

  27:         if (!superColName.equals("CustomerDetails")) { // Already displayed

  28:                                                          

  29:             System.out.printf("\n%50s:", superColName); // product Name 

  30:             List columns1 = prodSuperCol.getColumns();

  31:             for (Column col : columns1) {               // product data 

  32:                 String colName = StringUtils.string(col.getName()); 

  33:                 String colValue = StringUtils.string(col.getValue()); 

  34:                 System.out.printf("\t%20s:%-20s", colName, colValue);

  35:  

  36:             }

  37:         }

  38:     }

  39:  

  40: }

Lines	Description
8-9	Set the superColumn to the “CustomerDetails” supercolumn
11-14	Retrieve the column values (firstname, surname) for the CustomerDetails supercolumn
17-21	Set up a “SlicePredicate” that defines the supercolumns to be queried.  I want to get all of the supercolumns (eg every product), so I set up an unbounded range (line 18) and supply that to the slice predicate (line 21)
23	Create a list of supercolumns.  This will include all the SuperColumns in the column family (including, unfortunately,  CustomerDetails)
27	Eliminate CustomerDetails from the result.  Here we only want product names
30-35	Iterate through the columns in each supercolumn.  THis will extract QuantitySold and AmountSold for each Product name

Here’s some output from the Java program.  It prints out customer Details and product sales totals for customer# 10100:

Details for customer id 101000
    customerFirstName   :Aidan               
    customerLastName    :Wilbur              

                       CD-RW, High Speed Pack of 5:              AmountSold:11.99                           QuantitySold:1.0                 
                               Keyboard Wrist Rest:              AmountSold:11.99                           QuantitySold:1.0                 
                     Multimedia speakers- 3" cones:              AmountSold:44.99                           QuantitySold:1.0       

SuperColumns with Toad for Cloud Databases 

Toad for cloud databases now has Cassandra support, which makes querying SuperColumns s a lot easier.  SuperColumns that have dynamic names but uniform internal column structure (as in my example above) are represented by Toad for Cloud Databases as a detail table.  To put it another way,  Toad for Cloud Databases re-normalizes the data - displaying it in the format that we would typically use in an RDBMS. 

So when we point Toad for Cloud databases at our SalesByCustomer column family, it maps the column family to two tables:  one for CustomerDetails and the other - which by default it will call SalesByCustomersuper_column” – for product sales totals.  We can rename the subtable and subtable key during the mapping phase to make it clearer that it represents product details.

Now if we want to extract product details for a particular customer, we can do a SQL join.  Below we build the join in the query builder, but of course we could simply code the SQL by hand as we would for any NoSQL or SQL database supported by Toad for Cloud Databases:

And just to close the loop, here we can see that the Toad for Cloud databases query returns the same data as the Hector query:

Conclusion

All NoSQL databases require that we change the way we think about data modelling, and Cassandra is no exception.  SuperColumns are an incredibly powerful construct, but I can’t say that I found them intuitive or easy.  Hopefully APIs and tooling will evolve to make life easier for those of us coming from the relational world.

Playing with Cassandra and Oracle

Cassandra  is one of the hottest of the NoSQL databases.  From a production DBAs perspective it’s not hard to see why:  while some of the other NoSQLs offer more programming bells and whistles for the developer, Cassandra is built from the ground up for total and transparency redundancy and scalability, close to the heart of every DBA.

However,  Cassandra involves some complex data modelling concepts – mainly around the notorious SuperColumn concept, and I don’t think I’ll ever understand it fully until I’ve played directly with some data.  To that end, I thought I’d start by trying to model some familiar Oracle sample schemas in Cassandra.

Toad for Cloud Databases is releasing support for Cassandra early next month (eg September 2010), so I’ve been using that – as well as Java of course – to try to get some initial data loaded.

For other NoSQL databases,  Toad for Cloud lets us create NoSQL tables from relational tables with a couple of clicks.  Unfortunately, we can’t do that with Cassandra, since you can’t create a ColumnFamily on the fly.  So my first Cassandra tasks was to write a simple program to take an Oracle table (or query) and create a matching column family.

Getting started

Getting started with Cassandra was surprisingly easy.  I followed the instructions in http://schabby.de/cassandra-installation-configuration/ to install Cassandra on my laptop, and installed the hector Java interface from http://prettyprint.me/2010/02/23/hector-a-java-cassandra-client/.

Terminology in NoSQL can be confusing, with each NoSQL database using terms differently from each other, and all of them using terms differently from RDBMS.  In Cassandra:

• A Keyspace is like a schema
• ColumnFamily is roughly like a table

Things get very funky when SuperColumns are introduced, but lets skip that for now.

To create a ColumnFamily in Cassandra 0.6, we have to add its name to the storage-conf.xml file which is in the Conf directory and then restart Cassandra.  In 0.7 there’ll be a way to do this without restarting the server.

Here is where I created a keyspace called “Guy” and created some ColumnFamilies to play with:

   1: "Guy">

   2:   "G_Employees" CompareWith="UTF8Type"/>

   3:   "G_Employees2" CompareWith="UTF8Type"/>

   4:   "G_Employees3" CompareWith="UTF8Type"/>

   5:   org.apache.cassandra.locator.RackUnawareStrategy

   6:   1

   7:   org.apache.cassandra.locator.EndPointSnitch

   8: 

 

Loading data

I wrote some Java code that takes a SQL statement, and loads the result set directly into a column family.  Here’s the critical method (the complete java program with command line interface is here):

   1: private static void oracle2Cassandra(Connection oracleConn,

   2:         Keyspace keyspace, String cfName, String sqlText)

   3:         throws SQLException {

   4:     int rows = 0;

   5:     ColumnPath cf = new ColumnPath(cfName);

   6:     Statement oraQuery = oracleConn.createStatement();

   7:     ResultSet result = oraQuery.executeQuery(sqlText);

   8:     ResultSetMetaData rsmd = result.getMetaData();

   9:     while (result.next()) { // For each row in the output

  10:         // The first column in the result set must be the key value

  11:         String keyValue = result.getString(1);

  12:         // Iterate through the other columns in the result set

  13:         for (int colId = 2; colId <= rsmd.getColumnCount(); colId++) {

  14:             String columnName = rsmd.getColumnName(colId);

  15:             String columnValue = result.getString(colId);

  16:             if (!result.wasNull()) {

  17:             cf.setColumn(StringUtils.bytes(columnName));

  18:                 keyspace.insert(keyValue, cf, StringUtils

  19:                         .bytes(columnValue));

  20:             }

  21:         }

  22:         rows++;

  23:     }

  24:     System.out.println(rows + " rows loaded into " + cf.getColumn_family());

  25: }

The method take s a Oracle connection and a SQL statement, and pushes the data from that SQL into the Cassandra column family and keyspace specified.   The first column returned by the query is used on the key to the Cassandra data.

Lines 6-8 execute the statement and retrieve a ResultSet object – which contains the data – and a ResultSetMetaData object which contains the column names.  Lines 9-21 just iterate through the rows and columns and create entries in the Column Family that match.   We use the Hector setColumn methodto set the name of the column and the insert method to apply the column value.  Too easy!

Of course, I’d have no idea as to whether my job had worked if I didn’t have Toad for Cloud databases available.  Using TCD, I can map the Cassandra columnFamily to a TCD “table” and browse the table (eg Cassandra Column Family) to see the resulting data:

I can even use SQL to join the Cassandra data to the Oracle data to make absolutely certain that the data transfer went OK:

It’s surprisingly easy to get started with Cassandra.  Installation of a test cluster is a breeze, and the Hector Java API is straight forward.    Of course,  direct mapping of RDBMS tables to Cassandra ColumnFamilies doesn’t involve the complexities of advanced Cassandra data models using variable columns and SuperColumns.    Next, I’m going to try and map a more complex ColumnFamily which maps to multiple Oracle tables – hopefully won’t make my brain hurt too much!

Toad for Cloud Databases is introducing Cassandra support in the 1.1 release due out within the next two weeks.  Its a free download from toadforcloud.com