Array Sorting Algorithms in the Java Library

The class java.util.Arrays provides overloaded static methods for sorting arrays of primitive types (byte, char, int, long, float, double) as well as objects. The entire array or a range within the array can be specified.

For each type the library provides two overloaded methods: a single-threaded sort() method and a multithreaded parallelSort() implementation.

It is interesting to analyse the time complexity of the algorithms used in the library and compare its performance against that of a text book merge-sort implementation.

Single-threaded Sorting of Primitive Type Arrays

The Java SE 8 API documentation provides the following notes regarding the implementation of the sorting algorithms for primitive types:

“The sorting algorithm is a Dual-Pivot Quicksort by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm offers O(n log(n)) performance on many data sets that cause other quicksorts to degrade to quadratic performance, and is typically faster than traditional (one-pivot) Quicksort implementations.”

If you look at the library source code you will find that the methods actually switch to different algorithms based on the size of the input array. For instance for tiny arrays of less than 50 elements it switches to the insertion-sort algorithm which is very efficient when the number of inversions is small (that is the number of pairs of elements that are out of order).

Single-threaded Sorting of Object Arrays

The library provides an overloaded sort() method for arrays of objects that implement the java.lang.Comparable interface and another that takes a java.util.Comparator implementation as argument if you need to specify custom ordering.

As for the algorithm used the Java SE 8 API documentation provides the following implementation notes:

“This implementation is a stable, adaptive, iterative merge-sort that requires far fewer than n log(n) comparisons when the input array is partially sorted, while offering the performance of a traditional merge-sort when the input array is randomly ordered. If the input array is nearly sorted, the implementation requires approximately n comparisons. Temporary storage requirements vary from a small constant for nearly sorted input arrays to n/2 object references for randomly ordered input arrays”

As noted before the implementation actually switches algorithms based on the size of the input array.

Multithreaded Array Sorting

The algorithm used by the overloaded parallelSort() methods for both primitive and object types still relies on the single-threaded implementations but leverages the Fork-Join framework to obtain parallelism as described in the API documentation:

“The sorting algorithm is a parallel sort-merge that breaks the array into sub-arrays that are themselves sorted and then merged. When the sub-array length reaches a minimum granularity, the sub-array is sorted using the appropriate Arrays.sort method. If the length of the specified array is less than the minimum granularity, then it is sorted using the appropriate Arrays.sort method. The algorithm requires a working space no greater than the size of the original array. The ForkJoin common pool is used to execute any parallel tasks”

Performance Comparison

We will now compare the execution time of the library sorting algorithms for object arrays against a textbook implementation of merge-sort . The source code is on GitHub.

The data used for the tests are arrays of random Integer objects generated by a utility class. The size of the arrays is 10^6 or 1,000,000 elements with a bound value of 10^7 or 10,000,000.

The running time is measured by taking the difference between System.currentTimeMillis() calls before and after the execution of each algorithm.

The JUnit tests are executed by the Maven Surefire Plugin from the command line on a Windows 7 Professional machine based on Intel Core i5-3320M CPU running @ 2.60 GHz clock speed.

These are the results in milliseconds:

Run Merge-Sort JDK sort() JDK parallelSort()
1 966 510 239
2 958 533 241
3 971 505 241
4 989 507 237
5 965 493 237

Whilst the absolute running time is not necessarily indicative as it is heavily influenced by environmental factors, the relative running times should give a good indication of performance differences between the different algorithms when executed under the same conditions.

The full source code can be found on this GitHub repository setup as a Maven project. The development environment used is described here.

Big O Notation Demystified

Our job as programmers is to solve real-world problems by writing algorithms. Often however there is more than one possible solution to a given problem.

For example, suppose you need to implement a Java interface defining a method to sort an array of integers:

public interface Sorter {
  public void sort(int array[]);
}

 
You could use any of the well-known sorting algorithms or even create a new one to solve the problem. But which implementation would you actually use in a production system? Provided there are no computer memory constraints you will want to use the most efficient solution i.e. the algorithm with the best average case performance in terms of running time.

If the size of the array is relatively small the difference in performance is probably negligible but it becomes more and more significant as the size of the array grows. The time taken by an algorithm to execute in relation to the size of the input is called time complexity of the algorithm and is commonly expressed using the big O notation. Evaluating algorithms in this way is called asymptotic analysis in computer science.

We can safely assume for the purposes of this discussion that an algorithm is equivalent to a method or function and that the input to an algorithm is the method or function argument. Measuring the size of the input of course will depend on the type of the argument. If the input is an array or higher-level collection its size is determined by the number of elements in the array or collection. If the input is a String object its size is determined by the number of characters in the string.

Now that we have defined the notion of time complexity let’s see how the big O notation is used to express some of the most common cases.

O(1) = Constant Time

As an illustration let’s consider the following Java method that returns the number of elements in an integer array:

public int elements (int[] array) {
  return array.length;
}

 
Whatever the size of the array passed as argument the time taken by this method to execute will be always the same as it performs only a single operation. The method is said to run in constant-time and its time complexity is expressed as O(1).

O(n) = Linear Time

If the running time of a method increases in line with the input size the method is said to run in linear time and its time complexity is expressed as O(n).

An example of linear time complexity is the following Java method that calculates the sum of all the elements in an integer array:

public int total (int[] array) {
  int total = 0;
  for (int index = 0; index < array.length; index++) {
    total += array[index];
  }
  return total;
}

 
For instance given an input size of 256 this method will perform 256 x operations.

O(log n) = Logarithmic Time

Computers use a binary numeral system in which numbers are represented by sequences of 0 (zero) and 1 (one) also known as the base-2 numeral system.

The base 2 is used everywhere in computer science. For instance to work out how many positive integer numbers you can represent with an 8-bit word you raise the base 2 to the power of 8 to obtain 256 i.e. 2^8 = 256.

The logarithm operation does the inverse of exponentiation. It returns the exponent to which the base 2 must be raised to produce a number. For instance log(256) = 8.

Methods that run in logarithmic time are much more efficient than linear ones. Whereas a linear time method with an input size of 256 will perform 256 x operations, a logarithmic time method will only need to perform 8 x operations with the same input size.

Searching a binary tree is an example of time complexity of O(log n).

O(n log n) = Linearithmic Time

Given an input size of 256 a method that runs in linearithmic time will perform 2,048 x operations:

n * log(n) = 256 * log(256) = 256 * 8 = 2,048

The merge sort algorithm is an example of time complexity of O(n log n).

O(n^2) = Quadratic Time

Given an input size of 256 a method that runs in quadratic time will perform 65,536 x operations:

n ^ 2 = 256 ^ 2 = 65,536

The bubble sort algorithm is an example of time complexity of O(n^2).

The above are some of the most common time complexity measures. You can see more examples on the Big O Cheat Sheet website.

We have been assuming so far that the choice of algorithm is based solely on its time complexity without taking into account any other resource constraints.

However the amount of memory required by an algorithm is also an important decisional factor. The amount of working storage an algorithm needs in relation to the size of the input is defined as the algorithm’s space complexity and it is also commonly expressed using the Big O notation.

There is often a trade-off between time and space requirements, and in practice both need to be taken into account when selecting an algorithm.

Java’s 20th Birthday

To anyone with an interest in software engineering and open source projects, last January 23 was a date to celebrate as it marked the 20th anniversary of the first release of the Java Development Kit (JDK) in 1996 by Sun Microsystems (acquired by Oracle in 2010).

At the time the tech world was a different place. Mobile phones were not smart yet and were mostly used to make voice calls and to send the odd short txt msg 🙂

1996 Nokia Mobile Phone

Nokia Mobile Phone circa 1996

The World Wide Web consisted mostly of static HTML pages with hyperlinks, simple forms (processed by primitive CGI scripts on the server) and a sprinkle of GIF or JPEG images. By far the most popular Web browser at the time was Netscape with a market share of 86%.

In this context the arrival of Java applet technology was quite revolutionary. Developers could embed a fully interactive graphic application on a Web page to be run on the user’s computer, including games, spreadsheets and charts. Applets made Java an overnight sensation.

The first browser to support Java applets was HotJava, released by Sun Microsystems in 1997 to showcase Java technology.

HotJava Web Browser

HotJava Web browser

Ironically however despite making headlines initially as a technology that would radically change the Web user’s experience, Java’s great success was to be on the server-side and enterprise application space.

In 1998 Java 2 was released along with the Java Enterprise Edition (J2EE, now JEE) which extended the Java platform to provide an API and runtime environment for distributed computing. It was a powerful proposition and led Java to become a popular back-end workhorse on countless enterprise and Web systems. This popularity is still very strong today with Java powering some of the most popular websites including Google, YouTube, Facebook, Twitter and Amazon.

JEE Architecture

JEE Architecture

1998 also saw the initial release of the Java Platform Micro edition (Java ME), designed for embedded systems, today widely used in mobile handsets and set-top boxes. Java ME is in a strong position to become the platform of choice for the Internet of Things expected to be one of the most important technology trends in the next decade.

Subsequent releases of the three Java platforms (Standard, Enterprise and Micro) into the new Millennium brought more features and more efficient runtimes reinforcing its strong position.

What is the reason for Java’s continued success over its 20 year history? I think there are at least three key factors: portability, simplicity and vision.

Portability: with its virtual machine architecture, programs written in Java can run in any platform where a Java Virtual Machine exists without any change in the code.

Simplicity: its automatic memory management and verbose syntax make Java an easy programming language to learn. Its extensive software library allow developers to easily accomplish complex tasks such as network programming and database access with just a few lines of code.

Vision: Java is in fact much more than a programming language. It is also a software library, an enterprise platform, an embedded platform, an architecture, a virtual machine. This powerful ecosystem supporting the language will continue to play a key part in Java’s persistent success.

Java's Mascot

Happy 20th Birthday, Java!

References:

http://spectrum.ieee.org/computing/software/the-2015-top-ten-programming-languages
https://en.wikipedia.org/wiki/Programming_languages_used_in_most_popular_websites

Towards Functional Java: Method References

In the previous post of the Towards Functional Java series, we saw how to create a reference to a method implementation using lambda expressions and functional interfaces, passing it as an argument to methods in the same way we are used to pass object references.

Note: to try out the examples in this post, you need a Java 8 development environment. If you do not have one, you can follow this tutorial to set one up.

In the following JUnit test, we implement the functional interface Comparator so that it compares two strings by length (instead of alphabetical order) using a lambda expression, and assign the implementation to the variable comp. We then use the variable name to pass the implementation to the Collections.sort method to sort a List of strings. The API doc can be found here:

https://docs.oracle.com/javase/8/docs/api/java/util/Collections.html#sort-java.util.List-java.util.Comparator-

@Test
public void lambdaExpressionTest() {

   Comparator<String> comp = (str1, str2) -> 
       Integer.compare(str1.length(), str2.length());

   List<String> list = new ArrayList<String>();
   list.add("abcd");
   list.add("abcdef");
   list.add("ab");

   Collections.sort(list, comp);

   assertTrue(list.get(0).equals("ab"));
}

 
Now, suppose the above functionality was already provided by a method of an existing class, as in the following example:

public class AlternativeStringComparison {	
   public int compareByLength(String str1, String str2) {
      return Integer.compare( str1.length(), str2.length());
   }
}

 
You can refer to the compareByLength method directly using the following notation:

@Test
public void lengthComparisonTest() {	
   AlternativeStringComparison comp = new AlternativeStringComparison();
      
   List<String> list = new ArrayList<String>();
   list.add("abcd");
   list.add("abcdef");
   list.add("ab");

   Collections.sort(list, comp::compareByLength);

  assertTrue(list.get(0).equals("ab"));	
}

 
The expression comp::compareByLength is called a method reference. In this case we are creating a reference to an instance method, using the notation object::instanceMethodName.

If the instance method is defined by the same class of the receiver object, you can use the notation Class::instanceMethodName. For example, the String class defines an instance method to perform a case-insensitive string comparison. See the API doc:

https://docs.oracle.com/javase/8/docs/api/java/lang/String.html#compareToIgnoreCase-java.lang.String-

You can create a reference to it as follows:

@Test
public void caseInsensitiveComparisonTest() {

   List<String> list = new ArrayList<String>();
   list.add("bobby");
   list.add("Andrew");
   list.add("john");

   Collections.sort(list, String::compareToIgnoreCase);

   assertTrue(list.get(0).equals("Andrew"));
}

 
Likewise, it is possible to create a reference to a static method with the notation Class::staticMethodName. Consider the following class:

public class AlternativeStringComparison {	
   public static int compareByLen(String str1, String str2) {
      return Integer.compare( str1.length(), str2.length());
   }
}

 
You can create a reference to its static method as follows:

@Test
public void staticLengthComparisonTest() {
		
   List<String> list = new ArrayList<String>();
   list.add("abcd");
   list.add("abcdef");
   list.add("ab");

   Collections.sort(list, AlternativeStringComparison::compareByLen);

   assertTrue(list.get(0).equals("ab"));	
}

 
Constructor methods can be also referenced using the notation Class::new. We will look at practical applications of constructor references in a later post when discussing Java 8 streams.

In summary, four types of method references have been introduced in Java 8:

Type Notation Notes
Reference to a bound instance method object::instanceMethodName  
Reference to an unbound instance method Class::instanceMethodName  
Reference to a static method Class::staticMethodName  
Reference to a constructor Class::new  

In the next post we will look at more Java 8 functional features. Feel free to leave any comments or suggestions. Thank you for reading.

Defining DevOps

Research and industry surveys clearly show that DevOps is one of the most ill-defined terms in the IT industry today, with definitions ranging from “improved collaboration between development, QA and operations” to “the shifting of operation tasks to the development team”.

Surprisingly however, there is a lot more consensus on what the objectives of DevOps are, so perhaps this could be used as a reliable starting point in the search for a coherent definition. In fact, most people would agree that DevOps has three key objectives:

  • Frequent releases of software to production
  • Increased software quality
  • Reduced production costs

It is a tall order, and one that can only be achieved through automation at three levels: infrastructure, deployment and testing. These are all intertwined and interdependent. Testing automation enables continuous delivery, and infrastructure automation enables the timely provisioning of runtime environments into which the software product is deployed and tested.

This automation effort is therefore what DevOps is all about, so it could be redefined as:

“The process of automating infrastructure provisioning, deployment and testing with the aim to deliver software to production frequently, with fewer defects and utilising fewer resources”

From this perspective, DevOps should not be considered a methodology by itself, but rather an enabling set of tools and practices to achieve Agile software delivery, as defined by the principles in the Agile Manifesto. Unlike other Agile processes like Scrum and XP, which emphasizes the human factor in software development without providing the tools for the job – with mixed results – DevOps clearly focuses on the latter – the tools – to empower Agile teams.

Towards Functional Java: an Introduction to Lambda Expressions

A major feature of the Java 8 release is the language-level support for lambda expressions, which brings Java into the realm of functional-style programming. Other object-oriented programming languages such as Scala, JavaScript and Python had lambda expressions built in from the start, and now Java has joined the rank.

Why is this interesting? Functional programming (FP) is based on the recursive evaluation of pure functions, whose output depends solely on the input arguments to the function, avoiding side-effects (i.e. changing the state of objects). This immutability results in code that behaves more predictably and performs better in concurrent and parallel systems. This is the first of a series of posts that will explore functional programming in Java, and the starting point is to understand lambda expressions (also known as closures or first-class functions).

So, what is a lambda expression? Put simply, it is a concise syntax to create a reference to a method implementation for later execution. In Java, lambda expressions are used in conjunction with functional interfaces. A functional interface is a plain old interface that defines just one single abstract method, and is marked with the @FunctionalInterface annotation.

It works like this: you define a variable of a functional interface type, and assign a lambda expression to it. This variable can then be passed around just like any other reference, but instead of containing a reference to an object, it contains a reference to a method implementation.

Confusing? Do not worry; it will all become clear with a few practical examples. By the way, to follow the examples in this post, you need a development environment that supports Java 8. If you don’t have one, you can follow this tutorial to get it setup.

For our first example, we will use the Runnable functional interface, whose API documentation can be found here:

https://docs.oracle.com/javase/8/docs/api/java/lang/Runnable.html

The Runnable interface has been around for a long time, and if you wrote multi-threaded programs in Java you will be familiar with it; it is used to define tasks for later execution in a separate thread.

If you look at the source code of Runnable, you will see that it is annotated with @FunctionalInterface. It is not mandatory to use the annotation, in fact any interface that declares a single abstract method can be used as a functional interface; but it is good practice to annotate it so the compiler will check that it is a valid definition.

@FunctionalInterface
public interface Runnable {
    /**
     * When an object implementing interface <code>Runnable</code> is used
     * to create a thread, starting the thread causes the object's
     * <code>run</code> method to be called in that separately executing
     * thread.
     * <p>
     * The general contract of the method <code>run</code> is that it may
     * take any action whatsoever.
     *
     * @see     java.lang.Thread#run()
     */
    public abstract void run();
}

 
By the way, if you don’t know where to find the source code of the Java library classes, this post will show you:

http://robertovormittag.net/learn-from-the-experts-a-look-at-the-java-source-code/

Enough talk. Let’s write some code. Create a Java console application on your IDE, and place this code in main()

public static void main(String[] args) {
   Runnable r = () -> {
   System.out.println("Hello lambda!");
   };

   Thread t1 = new Thread(r);
   t1.start();
}    

 

Code analysis

First, we have declared a variable r of type Runnable, and assigned a lambda expression to it. This automagically becomes the implementation of the run() method declared by the interface.

Next, we have built a Thread object passing to the constructor our Runnable implementation, and started the thread. If you run the app, the thread will run and the string “Hello from a lambda expression!” will be printed on the console.

Syntax analysis

Let’s now take a closer look at the syntax of the lambda expression. All lambda expressions consist essentially of three parts:

  • a set of parameters (in parenthesis)
  • an arrow (or rocket) operator
  • a body (with the method implementation)

In this case, because the run() method takes no parameters, we have an empty parenthesis at the start of the expression.

Let’s look at another example, this time with parameters, and implement the java.util.Comparator functional interface, defined here:

https://docs.oracle.com/javase/8/docs/api/java/util/Comparator.html

This interface declares the abstract method

int compare(T o1, T o2)

which compares its two arguments for order, and returns a negative integer, zero, or a positive integer as the first argument is less than, equal to, or greater than the second.

Note from the API documentation that Comparator also declares other non-abstract, static and default methods but that is OK; it still is a valid functional interface, as it declares only a single abstract method.

We will now implement this interface so that it compares two String objects based on length. Here is the code:

public static void main(String[] args) {

   Comparator<String> comp = (String str1, String str2) -> {
         return Integer.compare( str1.length(), str2.length());
   };

   int result = comp.compare("ab", "abc");
   System.out.println(result);
}    

 
Here we declare the variable comp of type Comparator<String> and assign it to the lambda expression, starting with the two String parameters in parenthesis, followed by the rocket operator, followed by the function body which returns a value. We use the Integer class utility method compare() to compare the length of the String arguments.

https://docs.oracle.com/javase/8/docs/api/java/lang/Integer.html#compare-int-int-

The variable comp becomes a reference to our method implementation, and can be used in a way similar to the way object references are used. In the next line, we use comp to call our implementation passing two arguments “ab” and “abc”, capturing the return value in the variable result, which is printed to stdout.

If you run the application, you will see the value -1 printed, as expected, since the length of “ab” is less than that of “abc”.

An even more concise syntax

If the compiler can work out the type of the method parameters (in this case String), it is not even necessary to specify them (this feature is called type inference). And, if the method body is limited to a single expression, you can omit the angle brackets {} and the return keyword.

So our implementation can be written even more concisely like this:

public static void main(String[] args) {

   Comparator<String> comp = (str1, str2) -> 
      Integer.compare( str1.length(), str2.length());

   int result = comp.compare("ab", "abc");
   System.out.println(result);
}    

 
If you run the new version of the app, you will get the same result. How much concise you want to be is simply a matter of personal preference and programming style. Personally speaking, I value more much more readability and clarity in the code than conciseness, but the choice is there.

We can make a more interesting use of our Comparator implementation by applying it to the List sorting algorithm in the Collections utilities:

https://docs.oracle.com/javase/8/docs/api/java/util/Collections.html#sort-java.util.List-java.util.Comparator-

This utility sorts the specified list according to the order induced by the specified comparator. Try the following code:

public static void main(String[] args) {

   Comparator<String> comp = (String str1, String str2) -> {
      return Integer.compare( str1.length(), str2.length());
   };

   List<String> list = new ArrayList<String>();
   list.add("abcd");
   list.add("abcdef");
   list.add("ab");

   System.out.println(list);
   Collections.sort(list, comp);
   System.out.println(list);
}    

 
Here, we pass comp (the reference to our implementation of Comparator<String>) as the second parameter to the Collections.sort method.

If you run the app, you can check from the console output that, after the call to Collections.sort, the list has been sorted according to our Comparator implementation.

We covered a lot of ground, it is time to summarize. This is what we have learned so far:

  • What is a lambda expression
  • What is a functional interface
  • How lambda expressions and functional interfaces work together
  • The syntax of lambda expressions
  • A couple of practical examples using threads and collection algorithms

In the next post we will look at method references. Feel free to leave any comments / suggestions. Thank you for reading.

Learn from the Experts: A Look at the Java Source Code

The best way to learn and improve coding skills in any programming language is to look at code written by expert programmers. The Java Development Kit (JDK) comes with the source code of the complete Java Runtime Library; it is located in the src.zip archive under the JDK installation directory.

java-src

The location of the source file archive in the JDK 7 installation

Obviously your main reference when using the Java library classes should be always the API documentation, which can be found online or downloaded separately from the JDK downloads website. Here is the URL for the Java 8 API:

https://docs.oracle.com/javase/8/docs/api/

However, it can be very instructive to take a look at the source code of some of the key classes in the library, such as those in the java.lang and java.util packages.

Using Eclipse to view the Java Runtime Library Source Code

First, make sure you have the JDK selected as the default installed JRE. To do this select from the Eclipse menu: Window → Preferences. The following dialog pops up:

Setting up the JDK as the default JRE in Eclipse Mars

Setting up the JDK as the default JRE in Eclipse Mars

Select Java → Installed JREs

If the JDK is not there, click [Add…] and follow the prompts to select your JDK installation directory. Then make this JRE default by selecting the checkbox next to it. Now click [Edit…]. The following dialog pops up:

Setting up the runtime library source attachment

Setting up the runtime library source attachment

Expand the rt.jar library (this is the runtime binary) and click on [Source Attachment…]

The source attachment configuration dialog

The source attachment configuration dialog

Browse to the external location of your src.zip and click [OK]. Apply and close all parent windows.

Now to view the source file of a library class, e.g. LinkedList, either select from the menu:
Navigate → Open Type or use the shortcut [CTRL]+[SHIFT]+[T]

The Eclipse Open Type dialog

The Eclipse Open Type dialog

Type the name of the class, or select it from the list. The source code will open in the Editor.

the Eclipse editor showing the source code for LinkedList.java

The Eclipse editor showing the source code for LinkedList.java

Happy studying!!

From SQL to NewSQL via NoSQL: A Database Odyssey

We often read about the “data explosion” phenomenon, but in parallel with that, there has also been a “database explosion” in recent years. Cassandra… MongoDB… NoSQL… NewSQL… the database technology landscape in 2015 can be daunting and confusing. From Oracle to VoltDB it has been a 30+ year’s journey, which we will revisit with the intent to better understand how this technology has evolved over time and what are the choices available today when designing the persistence layer of an enterprise software system.

Let’s begin by rewinding back the clock to where it all started.

The Dawn of SQL

odyssey011970: at IBM San Jose Research Lab, Edgar F. Codd conceptualized a model for data access consisting of a set of tables containing rows, with each row representing an entity of interest. Data can be normalized to eliminate duplication, and relationships between tables can be enforced by foreign keys. The relational model was born.

Codd’s research started from a simple premise: to be able to ask the computer for information, and then let the computer figure out how to retrieve it. No low-level knowledge of data structures should be required. His idea spawned the creation of an industry-standard computer language for working with relational databases: the Standard Query Language, or SQL.

At that time, computer memory on commodity hardware was a fairly limited resource, so the only option was to design relational database software as disk-based systems. This forced choice will have a significant impact on performance, as accessing data on disk is several orders of magnitude slower than accessing data in memory.

The first commercially available relational database management system (RDBMS) was Oracle, released in 1979 by Relational Software (now Oracle Corporation). Other notable early RDBMS commercial releases were Informix (1981), IBM DB2 (1983) and Sybase (1987).

Apart from supporting SQL and the relational model, the commercial RDBM systems also provide support for transactions, multi-user concurrent access, and failure recovery.

Simply put, a transaction consists of a collection of data updates that the RDBMS treats as a unit of work: all the updates within the transaction either succeed (commit) or fail (rollback). For example, in a financial application, if you move money from account A to account B, you want both account balances to be updated if all is well, or in case of an exception, no updates should occur. With correct use of transactions, the database is always left in a consistent state, with minimal effort on the part of the programmer. Any application with integrity constraints greatly benefits from transaction support.

Transactions, concurrent access and failure recovery help to build applications that are robust, accurate and durable, but at a cost. A large chunk of CPU cycles is spent by RDBM systems to perform the locking, latching and logging required to support them, slowing down performance.

However, the flexibility of the relational model and SQL, the robustness provided by transaction support and an adequate performance for most business applications have made RDBM systems very successful and the unchallenged persistence technology for more than two decades.

But something was about to change.

The Data Explosion and the arrival of NoSQL

2000: The evolution of the World Wide Web has created global-reaching organizations in the fields of Internet search, social media, blogging, collaboration and online retail which had to cope with massive amounts of data, growing at an unprecedented scale.

This scenario represented a challenge for the traditional SQL relational databases. To start with, RDBM systems were originally designed to run as standalone servers. A single machine cannot scale beyond the physical hardware limits of disk space, memory and processing power. What happens when you reach the limit? The only solution is to combine the resources of several machines together in a cluster.

A cluster is a set of computers that perform the same task, controlled and coordinated by software in such a way that it can be viewed as a single system from a client’s perspective.

Some of the traditional SQL RDBM systems (e.g. Oracle RAC, Microsoft SQL Server) can be clustered using shared-disk architecture. In this configuration the database relies on disk storage that is shared by all the computers in the cluster and accessed via the network. This configuration does offer a degree of scalability, but the disk subsystem still represents a single point of failure which limits availability.

The level of scale and availability required by the Web 2.0 and other Big Data use cases demanded clusters with shared-nothing architecture. In shared-nothing clusters, each machine uses its own local hardware resources (processor, memory and disk) and, as the name implies, it shares nothing with the other machines in the cluster. Requests from clients are routed to the machine that owns the resource.

The relational model used by the traditional SQL RDBMS also was not ideally suited to be distributed in a cluster, without heavy management from the application code outside the database.

Because of these limitations, some Web giants, primarily Google and Amazon, started to work on a new class of databases that would become known under the umbrella term of NoSQL with the following design goals:

  • Shared-nothing clustering
  • Fast access to large amounts of data
  • Data models that are cluster-friendly

The NoSQL family of databases did not adopt a standard data model or a standard query language. The only common denominator is that they are non-relational. In practice, the majority of NoSQL implementations use either an aggregate-oriented or a graph data model.

An aggregate, as defined in domain-driven design, is a collection of objects that we wish to treat as a unit for data manipulation and consistency management. For example, an with its associated , and objects could be treated as a single aggregate. Aggregates are used in key-value, column family and document data models.

The graph data model, on the other hand, allows the user to store entities and the relationship between those entities. It is suitable for models with a large number of small records and complex relationships.

Aggregates allow the fast retrieval of large chunks of data. In key-value databases for example, a single lookup for a given key it is all that is needed to retrieve an aggregate of any size. In a relational model to achieve this would typically require several queries or joins, and a much longer execution time.

To make data access even faster, the NoSQL designers also decided that it was OK to sacrifice consistency in exchange for performance, and adopted an “eventual consistency” solution, which means, in practice, that it is OK for most applications to accept inconsistent data in some nodes in the cluster for a period of time following a database update.

The pioneering work by Google and Amazon spawned a number of NoSQL implementations; some examples (by data model) include:

Key-Value databases:

Riak (Basho Technologies), Oracle NoSQL Database (Oracle Corporation), Redis (Pivotal Software)

Document databases:

MongoDB (MongoDB Inc.), CouchDB (Apache Foundation)

Column-Family databases:

Cassandra (Apache Foundation), HBase (Apache Foundation)

Graph databases:

Neo4j (Neo Technology), InfinitGraph (Objectivity Inc.)

The NoSQL databases support highly scalable and highly available architectures. Some implementations can efficiently store unstructured data, such as video and audio files, which are not handled very well by the traditional RDBM systems. With NoSQL, a wider range of data models became available, catering for specialized use cases unsuitable for relational models and SQL.

Despite these advantages, there are downsides. The trade-off between consistency and latency cannot be accepted by all applications; the lack of support for transactions places a big burden on the developers to circumvent it; and the inexistence of a standard query language requires specialized knowledge to extract data.

The NewSQL Era

odyssey03First used in 2011, the NewSQL designation refers to a new class of contemporary relational database management systems that have been designed to offer the same scalability of NoSQL stores by providing shared-nothing cluster ability, whilst at the same time maintaining support for transactions and the consistency guarantees of the traditional RDBMS SQL systems. This new class of databases aim to yield better performance by adopting new architectures that vastly reduce the overhead required to support transactions, consistency and failure recovery. For example, most implementations use replication instead of transaction logs to achieve high availability and durability, which is much more efficient.

By now, the amount of memory available on commodity hardware means that most NewSQL stores are implemented as main-memory databases, which vastly reduces data access times.

All NewSQL databases support the relational data model, as well as the standard SQL query language. To make the relational model more easily distributable over a cluster, most implementations provide a middleware layer to automatically split relational data across multiple nodes; a technique called sharding.

Some implementations of this class of databases are:

  • MySQL Cluster (Oracle Corporation)
  • Spanner (Google)
  • VoltDB (VoltDB Inc)
  • MemSQL (MemSQL Inc)
  • SQLFire (Pivotal Labs)

What Next?

2015: as the amount of data produced in the digital world will continue to grow at an exponential rate, it is reasonable to assume that database technology will continue to evolve at the same pace.

We left out of this discussion third-party hosted alternatives such as cloud databases and Database as a Service (DaaS). There are also multi-model configurations, which comprises of two or more database types coordinated by a common manager, and hybrid solutions where a caching technology (such as Oracle Coherence) creates an in-memory key-value layer on top of a traditional disk based RDBMS.

My aim is to follow up and report developments in this space. In another post, we will look at what considerations should be applied when selecting a persistence technology for your project.