Most people would know of Dennis Ritchie as the person who invented C and Unix. What most folks do not realize is how profound C and Unix were when they were created and what amazing impact they have had on the industry.

Consider this – before C, you had to program directly to the instruction set of the machine you were programming on. Today when most hardware happens to be x86 or ARM, this seems simple, but back then, the variety of hardware was far more. And this hardware was different not just in terms of instruction sets, but also in terms of information representation, memory addressing, etc. Sure enough there were languages like Fortran and COBOL which could do math and data, but there was no general purpose language which could produce programs that could compete in terms of performance with custom code written for the hardware. Writing a portable program, much less a portable operating system was un-imaginable.

And yet, Dennis Ritchie imagined just such a world and invented a highly performant, high level programming language and then used that to write an operating system which could be ported to any hardware. This one change meant that programmers did not have to create a new OS for every new piece of hardware that got thrown at them – they could take for granted a set of tools, calls and programs, as being available and could spend time going up the value chain and doing more interesting things than just re-inventing the wheel. The result was a spurt of innovation and growth which allowed the industry to grow exponentially into a myriad different directions leading to the world we are in.

If you are a programmer, you owe a lot to Ritchie, whether you have ever programmed in C or worked on Unix or not.

[Edit: Bjarne Stroustrup expresses the same sentiment way more eloquently: http://herbsutter.com/2011/10/12/dennis-ritchie/

Most of us are happy to settle for incremental change. People like Ritchie don’t, and that’s what sets them apart.]

I never thought I would be so affected by the passing away of someone I never knew personally. But if you are in the world of tech and developing consumer products, it is not possible to have not thought about life as Steve Jobs – how his brain functions, how he figures out what should be built, how he sets the bar, how he hires and build teams, how he delves upon every aspect of the product, … you wish you had 0.1% of his ability, you wish you could be more like him, since being him means creating profound impact, and that is what you are really here for.

And this I believe is his true legacy. The products he helped create would have a shelf life of maybe a decade, Apple as a company would be perhaps super successful for another 2-3 decades, but what would inspire generations of current and future entrepreneurs, programmers and designers is the way he set about building products:

• leapfrogging the current state of the art, not incremental change
• relentless focus on the user
• not settling for less than perfection

This approach to building products is his true legacy, and for that, the world would be a better place.

PS: Could not cross link to references since there is no authoritative version of the C-99 standard in an HTML form – the standard docs are all in PDF.

C Declaration Grammar

Understanding a C declaration requires that we understand what elements can a C declaration have. While I will describe the overall syntax over here, I will not go into semantics:

declaration:
	declaration-specifiers init-declarator-listopt ;
declaration-specifiers:
	storage-class-specifier declaration-specifiersopt
	type-specifier declaration-specifiersopt
	type-qualifier declaration-specifiersopt
	function-specifier declaration-specifiersopt
init-declarator-list:
	init-declarator
	init-declarator-list , init-declarator
init-declarator:
	declarator
	declarator = initializer

This is what the above grammar is saying:

• A declaration is:
  • declaration-specifiers followed by an optional list of init-declarators
• The declaration-specifiers are:
  • A storage-class specifier, followed by other optional declaration specifiers
  • A type-specifier, followed by other optional declaration specifiers
  • A type-qualifier, followed by other optional declaration specifiers
  • A function-specifier, followed by other optional declaration specifiers
• List of init-declarators is:
  • An init-declarator
  • An init-declarator list, followed by a comma, followed by an init-declarator
• An init-declarator is:
  • A declarator
  • A declarator followed by an assignment operator (=),  followed by an initializer

Declaration Specifiers

As per the grammar defined above, a declaration starts with a declaration specifier. A declaration-specifier can be:

• Storage-class specifier: These are: auto, static, extern, register and typedef. Default is auto, so if nothing is specified, auto is assumed.
• Type-specifier: A type-specifier is one of the following. Default is int
  • void
  • char
  • signed char
  • unsigned char
  • short, signed short, short int, or signed short int
  • unsigned short or unsigned short int
  • int, signed or signed int
  • unsigned or unsigned int
  • long, signed long, long int or signed long int
  • unsigned long or unsigned long int
  • long long, signed long long, long long int, or signed long long int
  • unsigned long long or unsigned long long int
  • float
  • double
  • long double
  • _Bool
  • float _Complex
  • double _Complex
  • long double _Complex
  • struct-or-union-specifier
  • enum-specifier
  • typedef-name
• Type-Qualifer: Applicable only to l-values: const, volatile, restrict
• Function-specifier: There is only one function specifier: inline

Declarators

What follows a declaration-specifier is a init-declarator-list – a comma separated sequence of declarators that may optionally be initialized. A declarator [2] is defined as:

declarator:
	pointeropt direct-declarator
direct-declarator:
	identifier
	( declarator )
	direct-declarator [ type-qualifier-listopt assignment-expressionopt ]
	direct-declarator [ static type-qualifier-listopt assignment-expression ]
	direct-declarator [ type-qualifier-list static assignment-expression ]
	direct-declarator [ type-qualifier-listopt * ]
	direct-declarator ( parameter-type-list )
	direct-declarator ( identifier-listopt )
pointer:
	* type-qualifier-listopt
	* type-qualifier-listopt pointer
type-qualifier-list:
	type-qualifier
	type-qualifier-list type-qualifier
parameter-type-list:
	parameter-list
	parameter-list , ...
parameter-list:
	parameter-declaration
	parameter-list , parameter-declaration
parameter-declaration:
	declaration-specifiers declarator
	declaration-specifiers abstract-declaratoropt
identifier-list:
	identifier
	identifier-list , identifier

We can break down the above grammar the same way we did for the grammar of a declaration, but I’m gonna skip that and give some examples of declarators, just to give an idea of what declarators are supposed to be:

• i – An identifier (and hence a direct-declarator)
• i, j – A list of identifiers
• i = 10 – An Identifer followed by an assignment expression
• *p – A pointer declarator
• * const p – A pointer declarator with a type-qualifer (const)
• a[10] – An array declarator with a constant size
• a[*] – An array declarator with a variable size
• a[] – An array declarator with an unspecified size – the size will need to be defined somewhere else
• f() – A function declarator
• f(void) – A function declarator with no parameters
• f(int i) – A function declarator with a parameter
• f(int i, int j) – A function declarator with a parameter-list

Structure of a Declaration

Now that we have developed an idea of declaration-specifiers and declarators, we can see that the overall structure of a declaration is of the following form:

1. One or more declaration-specifiers followed by
2. One or more declarators (separated by commas)

However, not all combinations are valid. The following are not allowed:

f()[] // function can't return an array
f()() // function can't return a function
a[]() // array can't hold a function

The following, however, are allowed:

(* f())[] // function returning pointer to an array
(* f())() // function returning pointer to a function
(* a[])() // array holding pointers to functions

If you are flummoxed by the last three examples of combining pointers, functions and arrays, you are not alone. Such declarations can look scary till you develop a technique to start deciphering them. In order to do that however, we need to know the basic order of precedence

Operator Precedence

1. Parentheses grouping together parts of a declaration
2. Postfix operators: parentheses (for a function), square brackets (for an array)
3. Prefix operator: Asterisk (for a pointer)

Here are some examples of how this order applies:

Now the way to use these rules is as follows:

1. Read from left to right
2. For the first identifier you encounter (or if there is no identifier, then look for the inner-most construct), look to the immediate right
   • If there is nothing, or if you have a closing parenthesis, go to 3
   • Otherwise you have a function declarator indicated by () or an array declarator indicated by [] to the right of the identifier
   • Read left to right – you will have a “function returning” or “array of”
   • This would typically end with a right parenthesis, or the end of the declarator (semi-colon or assignment)
3. Look to the left
   • If you find nothing on the left, or if you find an opening parenthesis, go to 4
   • Otherwise you have a pointer declarator indicated by an asterisk to the left of the identifier. Read right to left – you will get a “pointer to”
   • This would end with a left parenthesis, or start of declarator
4. At this point you have either
   • A complete declarator – then you are done
   • Or an expression in parenthesis – go back to step 2.

If you did not realize this on reading the above description, what we are really doing in steps 2 and 3 is to convert the C declaration into a postfix expression by taking into account the lower predence of the asterisk. This same approach is used in the cdecl program given in K&R.

This will become clear with a few examples:

int * f();

• Start with identifer – f
• Parenthesis to the right – “function returning”
• Asterisk to the left – “pointer to”
• int

The postfix expression is:

f () * int // "f is" "a function returning" "pointer to int"

Here are a few more examples:

int * a[10];
// postfix expression: a [10] * int
// "a is" "array of 10" "pointers to int"

int (* a)[10]
// postfix: a * [10] int
// "a is" "pointer to" "array of 10" "int"

int **p;
// postfix: p * * int
// "p is" "pointer to" "pointer to" int

int **p[10];
// postfix: p [10] * * int
// "p is" "array of 10" "pointer to" "pointer to" int

int *f();
// postfix: f () * int
// "f is" "function returning" "pointer to" int

int (*f)();
// postfix: f * () int
// "f is" "a pointer to" "function returning" int

int (* vtable[])();
// postfix: vtable [] * () int
// vtable is an array of pointer to function returning int

int (* a[])(int, int);
// postfix: a [] * (int, int) int
// a is an array of pointer to function returning int
// and taking (int, int) as parameters

Applying Type-Qualifiers

The way you apply a type-qualifier (const, volatile) is that:

1. If next to a type-specifer, it applies to the type-specifier
2. Otherwise applies to the asterisk (pointer) on its immediate left

Examples:

const int * p;
// postfix: p * const int
// p is a pointer to a const int

int const * p;
// postfix: p * const int
// p is a pointer to a const int

int * const p;
// postfix: p const * int
// p is a const pointer to int

int * const * p;
// postfix: p * const * int
// p is a pointer to a const pointer to int

int * const * (* p)();
// postfix: p * () * const * int
// p is a pointer to a function returning a
// pointer to const-pointer-to-int

Abstract Declarators

An abstract declarator is a declarator without an identifer. However, lack of an identifier does not mean that we can’t interpret such declarators, since the missing identifier’s position can be determined by the placement of (), [] and * Some examples will help clarify this:

int *
// pointer to int

int * [10]
// array of 10 pointers to int

int * (*)
// function returing a pointer to int and taking no arguments

int (*) [10]
// pointer to array of 10 int

int (*) (*)
// pointer to a function returning an int and taking no arguments

With this background, lets tackle this gem from Andrew Koenig’s C Traps and Pitfalls (PDF):

(*(void(*)())0)();

Clearly, we are casting 0 to some type here. The type being:

void(*)()

We know this type:

// postifx: * () void
// pointer to function returning void

In the next step, this pointer is de-referenced and then called. So what is happening here is that zero is being cast to a pointer to a function returning void, then dereferenced and called!

After having gone thru the Android documentation and videos from Google IO, I found the documentation on Blackberry to be somewhat disorganized – it is not easy to get the big picture and grasp key concepts. You need to go thru a lot of documentation to figure out how things works together as a system. I also tried to access the materials from http://www.blackberrydevcon.com/2010-on-demand but it turned out that it would require a registration for $ 20. That was a bit of a WTF moment … I mean, you want to make money by selling conference materials? Who does that?? Anyway I proceeded to register on https://www.eventreg.com/pls/pg_rim/reg_rim.reg_login?icpid=&ipr_code=ONDNON and after filling two lengthy forms, was unable to make a payment despite getting a registration id. I wrote to BlackBerryDEVCON@eventreg.com with my registration id (this was on 3rd Mar), but am yet to hear from them. Rather discourgaing for somene starting off on a new platform.

The Blackberry Platform

The Blackberry platform consists of the following key components:

• Phone: Blackberry phones support two kind of applications:
  • Java Apps: These are native Blackberry apps which can take full advantages of all the features available in a Blackberry phone, for example the BBM API.
  • WebWorks Apps: Browser based apps built using HTML, CSS, JS and capable of accessing native APIs thru the WebWorks SDK.
• Tablet: One can build playbook tablet applications in two ways:
  • Adobe AIR apps: Based on Action Script 3 with a bunch of Blackberry specific APIs. Use this to build apps with a native look and feel.
  • WebWorks apps: Similar to WebWorks apps for the Blackberry phone.
• Platform Services: Bunch of services provided by RIM including Push, Location, Advertising and Payment services
• Connectivity Services: RIM also provides a couple of connectivity services:
  • Blackberry Enterprise Server (BES): Enterprises can make their mail infrastructure available over the Blackberry network using BES which acts as a relay between the mail server and Blackberry’s NOC co-located with a carrier providing Blackberry services. One of the components of BES called the Mobile Data System (MDS) provides  HTTP and TCP proxies for a Blackberry application. This allows a Blackberry device to communicate with app / web-servers behind a corporate firewall without using VPN.
  • Blackberry Internet Services (BIS): For individuals, the alternative to BES is the BIS. This provides the ability to access mail over POP and IMAP email without going thru BES. The service is provided in partnership with a carrier.
• AppWorld: The blackberry application store front, similar to the iPhone App Store

This post is specific to Java development for the Blackberry phones. Moreover, it is specific to Blackberry 5 since 75-85% of app downloads from the App World are from Blackberry 5 devices.

Java ME

Native apps on the Blackberry phone are Java apps that run on RIM’s JVM implementation. This Java API is based on Java ME with Blackberry adding its own extensions. If you are new to Java ME like I am, here is a quick review:

Java ME (Micro Edition) is Java targeted for small devices. It is a collection of specs and technologies to address the needs of providing a programming interface to small devices. Since there is a large variety in the types of devices and their capabilities, it is quite likely that a device manufacturer would implement some specs and not others, leading to API fragmentation and hence non-portable code. To address this, Java ME defines capabilities for devices which are organized into Configurations, Profiles and Optional APIs:

(Organization of the Java ME technologies – source: http://developers.sun.com/mobility/getstart/articles/survey/)

• Configurations: A configuration is a specification for a virtual machine + some base APIs designed for a specific kind of device, based on memory constraints and processor power.
  • Connected Limited  Device Configuration (CLDC): The CLDC is meant for small wireless devices with intermittent network connections, like pagers, mobile phones and PDAs
  • Connected Device Configuration (CDC):  The CDC is a superset of the CLDC meant for larger devices with robust connections, like Set-top boxes and internet appliances.
• Profiles: A profile is more specific than a configuration. A profile is based on a configuration and adds APIs for UI, Storage, or whatever else is required to develop apps. For CLDC, a profile called Mobile Information Device Profile (MIDP) is specified. For CDC, there is a hierarchy of profiles:
  • Foundation Profile
  • Personal Basis Profile
  • Personal Profile
  • Information Module Profile
• Optional APIs: A device implementing Java ME may define additional optional APIs besides the ones that are defined as a part of a Java ME profile.

Based on the configurations, profiles and optional APIs, Java ME is able to address a wide variety of small devices including Handsets, Smart-cards and embedded devices:

(Map of the Java ME Universe – source: http://developers.sun.com/mobility/getstart/articles/survey/)

A device implements a stack consisting of a Configuration, Profile and Optional APIs. For wireless devices like mobile phones, the stack is based on CLDC, MIDP and some optional APIs. An application targeting the MIDP profile is called a MIDlet.

(Stack for wireless devices. Source: http://www.oracle.com/technetwork/java/javame/tech/technology-139316.html)

As one can imagine, despite the CLDC and MIDP being defined, a lot of commonly required functionality and the way it is provided remains un-defined, thus introducing scope for API fragmentation and un-portable code. This was addressed thru JSR 185 – Java Technology for the Wireless Industry – a specification that addresses fragmentation by defining key APIs and code portability issues by clarifying spces and providing a suite of compliance tests. JSR 185 consists of CLDC 1.0 or 1.1, MIDP 2.0 and WMA (Windows Messaging API – JSR 120 and JSR 205), with support for MMAPI (Mobile Media API – JSR 135) being optional:

(JSR 185 – JTWI Stack. Source: http://developers.sun.com/mobility/getstart/)

This was superseded by the MSA (Mobile Services Architecture) specification which defined two stacks: a full stack of 16 JSRs and a subset of 8 JSRs:

(MSA Stacks. Source: http://developers.sun.com/mobility/midp/articles/msaintro/)

Blackberry 5 is based on CLDC 1.1, MIDP 2.0 and is JSR-185 compliant. It also supports the full MSA stack except for JSR 184 (3-D graphics), JSR 180 (SIP) and JSR 229 (Payment). For other JSRs supported by Blackberry 5, see http://docs.blackberry.com/en/developers/deliverables/9095/Support_for_standard_Java_APIs_446981_11.jsp

Blackberry Applications

Blackberry applications are of two types:

• MIDlet Application: A MIDlet is an application targeting MIDP (javax.microedition namespace). Such an app can run on other MIDP 2.0 compliant phones from other vendors
• Blackberry Java Application: A Blackberry Java Application (also called a RIMlet) targets the CLDC, but uses Blackberry specific APIs (from the net.rim namespace). Such an app can run only on a Blackberry device.

Unless your code is targeting mulitple Java ME platforms, it makes sense to build Blackberry Java applications since they tend to be a lot richer than MIDlets. Specifically, if you want the look and feel of applications that RIM ships with a Blackberry (also called “native apps”), then you should build a Blackberry Java application by using net.rim.device.api.ui and not use javax.microedition.lcdui. More differences on the UI capabilities of both frameworks are given on http://www.blackberry.com/developers/docs/5.0.0api/UI-summary.html.

Note that all APIs are always available to all apps. So if your app is using the Blackberry UI, you can always invoke MIDP APIs. If your app is using the MIDP UI, you can always invoke Blackberry APIs, but of course doing so would render the application non-portable. The only exception to this is on mixing UI. The MIDP UI model allows concurrent access while the Blackberry UI model does not and hence mixing UI library calls is unsupported.

In the rest of this post, I would be focussing mostly on the Blackberry Java Application.

Startup

A Blackberry application can start in one of the following ways:

1. Use clicking an icon on the Home screen
2. By another app
3. OS starting an app automatically when the device starts
4. OS starting an app at a scheduled time

This startup is managed by an entity called the Application Manager. An running application can obtain a reference to the Application Manager by calling getApplicationManager(), and then, can use this to:

• Run or Launch another application
• Schedule an application to run at a specific time
• Post a global event to the OS
• Lock and Unlock the system

To start an application, the App Manager creates a new process and a thread within that process and then starts the main() function on that thread with a set of input parameters. The parameters are specified in the application descriptor. It is possible to create multiple descriptors for the same app and associate them with different icons on the screen, This allows the creation of multiple entry points for the same app.

Event Processing

Once started, an application can choose to do a series of operations and then quit, never showing a UI. However, most applications want to stay around and respond to system events, including UI events. For this, one of the threads of the application needs to acquire what is called the Event Lock by calling Application.getEventLock(). Only one thread in the application can acquire this lock – this thread is then called the Event Thread. Typically, the first thread acquires this lock by calling enterEventDispatcher(). Once this method is called, the application starts receiving system events. Note that this does not mean that the application is showing a UI – just that is it receiving all system events, including UI events. So as of now, the application is still running in the background. An application can control whether it wants to continue processing systems events by toggling setAcceptEvents().

Showing a UI

All the visible elements in a Blackberry Java Application are of three types:

• Fields: A building block element that is used to work with a particular kind of data for which it draws the UI and if required handles user-input. It typically corresponds to a control like a button / text-field, etc. You can create custom Fields by sub-classing the Field class, implementing the layout() and paint() abstract methods and optionally overriding getPreferredHeight() and getPreferredWidth() methods.
• Managers: Responsible for arranging fields. Each field must belong to only one manager. Since a manager is also a field, managers are composable, making it possible to build complex, rich, UI layouts. There are several types of managers provided: Horizontal, Vertical, Grid, Flow, Absolute, etc., and you can also build your own by sub-classing the Manager class and implementing sublayout(), getPreferredHeight() and getPreferredWidth() methods and optionally overriding subpaint() method.
• Screens: A screen is a window that is active at any given time. There are two types of screens: PopupScreen and a FullScreen.

(Blackberry UI Framework. Source: http://www.blackberry.com/developers/docs/5.0.0api/UI-summary.html)

The way the system works is that the UI Engine maintains a stack of Screen objects. As new screens are created, they are pushed on the display stack. Only the screen at the top receives input events. When a screen is popped from the stack, the underlying screens are drawn as necessary. Note that the Blackberry display stack is not the same as the Android back-stack. The Android back-stack is a system-managed structure, scoped to a task with acitivities from different processes getting interleaved. The Blackberry display stack is a per-process application-managed stack of Screens.

To show a UI, the application extends the net.rim.device.api.ui.UiApplication class (which implements UiEngine and extends the Application class), creates an instance of MainScreen (which is of type FullScreen) and then pushes this instance on the display stack.

class MyApp extends UiApplication {
	MyApp() {
		MyAppScreen myAppScreen = new MyAppScreen();
		pushScreen(myAppScreen);
	}

	public static void main(String[] args) {
		MyApp app = new MyApp();
		app.enterEventDispatcher();
	}
}

class MyAppScreen extends MainScreen {
	MyAppScreen() {
		// add fields etc.
	}
}

Termination

An application terminates when System.exit() is called. This method causes the Blackberry JVM to terminate the process of the caller. For applications that show a UI, the typical way of quitting is that when the close() method is called on a screen, it pops the screen from the display stack, and if the display stack is empty, calls System.exit(). So if the user keeps pressing back and hits the first screen of your application, pressing back once again would by default exit the app. To avoid this, one needs to override the close() method.

Doing Long Running Work

As described in the Event-Processing section above, the Blackberry UI model is a single threaded one. That means that you cannot do long-running work on it, and instead need to launch a worker thread. This worker thread can update the UI in two ways:

1. Acquire and synchronize on the event lock: To do this, the worker thread invokes Application.getEventLock() and then synchronizes this object to access the UI. While this is being done the Event Thread is paused, so the lock should be held for a really short period of time.

   // on the background thread
   synchronized(Application.getEventLock()) {
       // update the UI
   }

2. Inject an event in the UI message queue: To inject an event, you model it as a class that implements Runnable and inject it into the Event Thread message queue by calling invokeAndWait() or invokeLater(). The event thread would then call the runnable’s run() method at the next available opportunity. While for invokeAndWait(), the worker thread would block till run() returns, invokeLater does not block and returns immediately.

   // on the background thread:
   UiApplication.getUiApplication().invokeLater (new  Runnable() {
       public void run()
       {
           // update the UI - runs on the Event thread
       }
   });

Interprocess Communication

There are two ways in which Blackberry applications can communicate with each other:

1. Using the RuntimeStore: The RuntimeStore is a system-wide volatile storage where applications can place data to share with other applications.
2. Using Global Events: Use Application.addGlobalEventListener() to add a GlobalEventListener to listen to global events. Post a Global Event by calling ApplicationManager.postGlobalEvent().

Security Model

Blackberry has a complex security model, owing to its roots in enterprise software. When businesses issue their employees Blackberry devices, they also expect to able to exercise control over what the user is able to do on the device. This is made possible thru a policy which is pushed to the device using BES or the Blackberry Desktop Manager. Such policies can limit the resources available to an application, and to handle that gracefully, applications should:

1. Find out what permissions they have: By calling ApplicationPermissionsManager.getApplicationPermissions(). This returns an instance of ApplicationPermissions class which gives all the permissions that are set.
2. Ask for permissions they need: By calling ApplicationPermissionsManager.invokePermissionsRequest() and passing it an instance of ApplicationPermissions with the requested permissions set.

Besides this, RIM has marked a number of APIs as controlled APIs. To access these APIs on the device, you must sign your application using a key or signature obtained from RIM. For details, see http://us.blackberry.com/developers/javaappdev/codekeys.jsp. On the simulators, these APIs are accessible without code-signing.

Packaging

When you build your app, you create a JAR, alongwith a manifest. Java ME defines certain mandatory and optional attributes that applications should include in the JAR manifest, besides any other app-specific info that maybe present.

However, a Blackberry device cannot directly execute a JAR. It first needs to be converted into a proprietary format file called a .COD file which is essentially RIM’s own version of the JAR. So if you want to run a MIDlet on a Blackberry device, you first need to convert the JAR into a COD file which can be done using the Eclipse plugin or by using the RAPC compiler on the command line. Some more details on using the RAPC compiler are given here.

However, the max size of a COD file is 128 kb with a 64 kb limit on compiled code and 64-kb limit on resource data. In case the compiled code produced is larger than these limits, the compiler breaks the code into mulitple COD files, naming them in increasing numerical order like this:

• HelloWorld.cod
• HelloWorld-1.cod
• HelloWorld-2.cod
• HelloWorld-3.cod
• …

The compiler then takes the numbered files (called sibling COD files), zips them and names the zip as a COD file (HelloWorld.cod above) – this is called the main COD file. There is a max limit to the main COD file too – it can contain up to 127 sibling COD files, thus imposing a theoretical size limit. For more details, see http://supportforums.blackberry.com/t5/Java-Development/The-maximum-size-of-a-BlackBerry-smartphone-application/ta-p/502534.

Packaging the application for Wireless or Over-the-Air (OTA) distribution requires more work. For this, Java ME defines an additional manifest called a JAD (Java Application Descriptor) that Java ME applications should provide for OTA distribution. The main purpose of a JAD is for locating a JAR and figuring out its size. Besides the JAR URL and JAR size, the JAD must also contain certain other attributes that are also required in a JAR manifest and may contain any attribute that is in a JAR manifest. For details, see here. Blackberry specific attributes for a JAD are given here. Also, for OTA distribution, you need to extract the sibling COD files from the main COD file. For details see here.

Distribution

Blackberry applications can be distributed in two ways:

1. Direct Connection: Connect the device to your computer and install the app. There are two possibilities here:
   • Using the Blackberry Desktop Manager: The application needs to have a COD file alongwith an additional manifest file called the ALX file.
   • Using a Web Page: For this, you need to put up an ActiveX control called a  Web Loader on the web-page from where you want the installation to happen. The user browses to a web-page on his desktop using IE and the control starts an installer. In case the user visits the page using a Blackberry device, the user is prompted to connect the device to a desktop.
2. OTA: There are two ways in which OTA distribution may happen:
   • BES Push: An organization with a Blackberry Enterprise server deployment can push notifications to Blackberry devices for applications based on policies defined by an administrator.
   • Blackberry App-World: The process is described here.

Android Architecture

The following diagram (from http://developer.android.com/guide/basics/what-is-android.html) gives the overall architecture of the Android OS:

The Android OS is basically a Linux 2.6.4 kernel fork. The Linux kernel is used for memory management, process management, security, driver model, shared lib model. Google has added Android specific enhancements: Power management, Kernel debugger, Logger, Low Memory killer, Shared Memory Driver, IPC Driver, etc.

Above the kernel, in the user space, sits the Hardware abstraction layer – this deals with stuff like Radio, Wifi, GPS, Graphics, Audio, Camera, Bluetooth, etc. Basically this defines a set of interfaces that drivers need to implement. These libaries are loaded by the system at runtime on a need basis.

Above the HAL, sit a bunch of libraries – the most important of course is libc – Google has written a port called Bionic libc which is optimized for embedded use – in terms of being small in size (since it is loaded in every process) and fast (since CPU is limited), but also because libc is GPL and Google wanted to protect apps from being GPLed. Besides there is webkit of course and SQLite. Google also provides a Media Framework, OpenGL library, and libraries for UI rendering and audio.

The Android programming environment is based on Java. For this, the OS ships with Dalvik – a custom implementation of the JVM optimized for the embedded environment. Dalivk does not run the Java bytecode, but its own custom bytecode called Dex – Dalvix Executable. It uses runtime memory very efficiently, the bytecode interpreter is highly CPU optimized, and because of this low footprint, the VM can be run in multiple processes – basically each app gets its own Linux process with its own instance of a Dalvik VM. The VM is exposed by a set of core Java APIs which provide the familiar Java library.

All of the above is wrapped in a set of platform services called the Android Application Framework – these services work behind the scenes to provide abstractions like Activities, Packages, Windows, Resources, Content Providers, View System, hardware access, etc.

Startup

Like a typical Linux system, in Android, the bootstrapper loads the Linux kernel and starts the init process, which in turn starts various daemons like Android Debug Bridge (adbd), Radio Interface Layer Daemon (rild), etc. After this, init starts what is called the Zygote process. The purpose of this process is to kick off the rest of the Android system and later help in the instantiation of apps. The Zygote process initializes a Dalvik VM instance and loads a bunch of libraries and starts listening on a socket for requests to spawn more processes (with VM instances). As requests come in, it forks to create new processes with VM instances. Copy-on-write is used to maximize reuse and minimize footprint.

(Android Startup Sequence – source: http://sites.google.com/site/io/anatomy–physiology-of-an-android)

Once Zygote is in place, the init process starts what is called the Runtime process. This basically does two things:

1. Start the Service Manager – this is responsible for managing IPC and all services are required to register with it. It acts like a local DNS providing a way to bind to a service given its name.
2. Ask Zygote to fork what is called the System Server. This is the first process (besides Zygote) that has a running VM instance. The System server starts services for display (Surface Flinger) and audio (Audio Flinger). These services register with the service manager like all services are expected to. Now other apps can start using display and audio. After this, the System server starts up all the core platform services – Window manager, Telephony manager, Power manager, Activity manager, etc. Each one of these services also registers with the Service Manager, so that apps can use these services.

At this stage, we have the following processes in place:

1. Init – the original init process started by the bootstrapper
2. Daemons – started by init
3. Runtime – also started by init
4. Zygote – the original zygote which will continually get forked as new apps get launched
5. System Server – the first managed process which contains all the core services and platform components.

After this, the Home Screen or the Idle screen is launched – basically the Activity Manager (which is inside the System Server) sends a message to Zygote to start the “Home” Activity, which causes Zygote to fork into a new process with a Dalvik VM and the Home activity. Now depending on the action carried out by the user, the appropriate app would be launched with the Zygote forlking each time to create a new VM instance inside a new process. So for example, if the user starts the Contacts app, the apt process would be setup:

(Startup processes in Android -  source: http://sites.google.com/site/io/anatomy–physiology-of-an-android)

Each new app gets a unique user Id which is opaque to the app, and the system sets permissions for all files in the app so that only the user id assigned to the app can access those files.This makes the system secure since the app only has access to the components that it needs to do its work and nothing else. However,  apps may need to communicate with each other and the system services, which are all running in separate processes. This is accomplished thru Inter Process Communication

IPC

With its emphasis on isolating apps and services in process boundaries, it is clear that Android requries a lightweight IPC. The IPC mechanism in Android is called Binder and is based on shared memory. Recall that when a process starts it registers itself with the Service Manager. This happens behind the scenes, and on registeration, each process gets what is called a Context object – a reference to the Service manager. Now lets say app A needs to communicate with service B, and the two are running in two separate processes. To do this, app A asks the Context for the Service B by passing the well known name of the service. The Context returns a reference to the service to A, on which A can call a method – say foo. This method call is intercepted by the Binder driver. The driver marshals the object and passes a reference of it to the receiver – B. Note that this is passing by reference, not passing by value, in which the object is serialized. On the side of the service B, the Binder maintains a thread-pool (transparent to the service). One of the threads in this pool receives the incoming call, locates the actual object in the service B and make the call. The return value is then similarly passed back to the caller. The following diagram (from http://sites.google.com/site/io/anatomy–physiology-of-an-android) illustrates this:

The entire operation is synchronous, and the objects are reference counted so that when they are no longer in use, they can be deleted. Since there is no serialization / de-serialization, there is no overhead and therefore this model can also be used to communicate with services that run in your own process without any penalty.

Applications

An application in Android is a collection of components. There are four types of components:

• Activity: An Activity is a UI component corresponding to one screen with which a user interacts in order to do something.
• Service: A Service is an application component without a UI used to perform long running operations in the background.
• Broadcast Receiver: A broadcast receiver is a component that responds to system-wide broadcasts (for example screen turned off, battery low, etc.)
• Content Provider: A content provider is a component that stores and retrieves data and makes it available to all applications. There are different types of content providers: audio, video, contacts, etc. and you can create your own custom provider also.

As mentioned earlier, each application runs in its own process. By default, all components used by that app also run in the same process, and on the main thread. However, it is possible to make a component of your app run in a separate process thru the manifest file. Thus, an application in Android may span multiple processes.

Application Startup

Android follows a fairly unique model in that there is no single entry point for an application – there is no main() function. Instead, a component in one application can start another application’s component, thus bringing the application to life. This communication across apps happens thru the IPC mechanism descibed above. So while an Activity is owned by an application, it is possible for another application to start it (if the owning application allows it). An example is clicking on a hyperlink in an app opening up the browser. This applies for not just Activities, but other types of components also. In order for this to happen, there are two steps required:

1. In case the application is not already running, the Android system would bring the application to life in a new process forked from Zygote.
2. The desired component inside the app would need to be activated.

Note that in case the application is already running, the new component would be by default instantiated in the same process.

As mentioned above, IPC happens thru a Context object. So when a component A inside one app needs to activate another component B in a different app, or give it something new to do, it basically uses the Context object to send a message to the other component. In the case of an Activity, Service or a BroadcastReceiver, this takes the form of a what is called an Intent – a passive data structure that defines the operation to be performed for an Activity and a Service, and for a Broadcast Receiver, a defintion of the announcement being broadcast.

Content Providers however are not activated thru Intents. Instead, activation happens on a request from a ContentResolver, which acts as a mediator between the requesting component and the Content Provider.

The Activity Back-Stack

Consider the following scenario:

1. You are on the Home Screen. This is Activity 1
2. You click on the Mail app icon, and that activates the main activity in the Mail app which comes to the foreground. This is Activity 2
3. You now click on Compose and that activates the Compose activity in the Mail app. This is Activity 3
4. You decide to cancel out of composing a new message and press the back button. You come back to Activity 2

Here is what happens in the background:

• When one activity starts another activity, it stops and its state is saved. So when Activity 1 starts activity 2, activity 1 is stopped, its state saved and so on
• The system maintains a stack (called a back-stack) with the latest activity on top and the oldest activity at the bottom.
• When the user presses the back-key, Activity 3 is popped and Activity 2 is started from its saved state

(The Activity Back Stack – source: http://developer.android.com/guide/topics/fundamentals/tasks-and-back-stack.html)

This approach allows Android to seamlessly transition from one app to the other in a consistent way.

Tasks

In the scenario described above, assume that when the user was in Compose mail (Activity 3), he decided to call someone and pressed the Home key. This would not unwind the back-stack, but start a new stack. In order to do this, the collection of Activities in the first stack needs to go into the background. This is achieved thru the notion of a Task – a cohesive unit of Acitivities. When a task moves to the background, all activities in the Task are stopped but the back-stack for the task remains intact, so that when the user returns back to the Task, she can resume where she left off. However, to save memory, the back-stack for a background Task is not retained for a very long period and if the user does not go back to the task, the back-stack is cleared except for the root activity.

(Background and Foreground Tasks – source: http://developer.android.com/guide/topics/fundamentals/tasks-and-back-stack.html)

Activity Life Cycle

The lifecycle of an activity is affected by its association with other activities, its task and its back-stack. There are three states in which an activity can exist:

• Resumed / Running: Activity is in the foreground and has user focus. Such an activity is never killed by the system,
• Paused: Activity is visible, but another activity is in the foreground and has user focus. This could happen if the other activity is at the top, but is translucent, or because it does not cover the entire screen. In the paused state, the Activity object is retained in memory, maintains all state and member info and remains attached to the Window manager. However it can be killed in extremely low memory conditions.
• Stopped: The Activity is not visible to the user.While the Activity object is retained in memory, maintains all state and member info, it does not remain attached to the Window manager. The activity can be killed by the system to reclaim memory if required.

(Activity Lifecycle – source: http://developer.android.com/guide/topics/fundamentals/activities.html#Lifecycle)

Saving Activity State

Note that it is entirely possible that the system, in order to reclaim memory, may destroy an Activity, or even the process in which the Activity was running. However, when the user comes back to the activity (thru the back-stack), you still want to resume at the point the user left. To do this, an activity must save its state. This happens thru the Activity.onSaveInstanceState() method.

(Saving and restoring Activity State – source: http://developer.android.com/guide/topics/fundamentals/activities.html#SavingActivityState)

Process Lifecycle

The Android system may need to kill a process in order to reclaim memory. To ensure that this creates minimal impact on the user expereince, Android ranks processes in a priority order:

• Foreground Process: A process that is required for what the user is currently doing. Such a process is killed only as a last resort
• Visible Process: This process is not in the foreground but can affect what the user is seeing on the screen. For example it may host a paused Activity. Such a process is not killed unless doing so is required to keep all foreground processes running
• Service Procress: A process that is running a service and is not one of the two types above. For example the service may be playing music or downloading something. The system would keep such a process running unless there is not enough memory to keep Foreground and Visible processes running.
• Background Process: A process that is holding an activity not currently visible to the user (the activity is stopped). Such a process has no impact on the user experience (if the activity lifecycle is correctly implemented and the activity state is being properly saved and restored) The system can kill such a process any time. Typically there are mulitple background processes running and the system maintains a LRU list which is used to kill such processes.
• Empty Process: An empty process does not hold any active component. The only reason such a process is kept alive in the first place is for caching and to improve startup time. The system often kills such processes to maintain the balance between process caches and underlying kernel caches.

Of course it can so happen that a higher priority process is dependent on a lower priority process. In such a case the ranking of the serving process is increased to the same level as that of the dependent process.

A situation where this ranking has a direct impact is this:

• Your app needs to download something big which may take time and the user is likely to move out of the app’s activity to something else.
• If you spawn a worker thread for this task and the user moves out, the process would become a background process.
• However, if you instead spawn a service, the process would be a service process and be less likely to be killed

Main / UI Thread

When an application is launched and a new process created to host it, the application gets a single thread called the main thread or the UI thread since this thread is responsible for servicing the UI. The way this works is mostly the same for almost any UI implementation – be it desktop operating systems or mobile OS. Basically, the UI thread runs an infinite loop which checks a queue to see if there are any pending UI events. In the case of Android, this concept is formalized in the form of a Looper.  The looper loops over a MessageQueue which contains the messages to be dispatched. The actual task of managing the queue is done by a Handler which is responsible for handling (adding, removing, dispatching) messages in the message queue.

(Android Threading – source: http://sites.google.com/site/io/inside-the-android-application-framework)

For the main thread, a Looper is setup by the system. However, you can also associate a Looper with your own thread. Note that the Looper can be associated only with one thread and that association cannot be changed. The way Android ensures this is by putting the Looper on the thread local storage of the thread and not exposing a constructor for the Looper. You get a Looper by calling the static prepare method which first checks the TLS to see if there is already a Looper, and if not creates one. You then call the loop method on it to start pumping messages. Unlike a Looper, mulitple handlers can be associated with a message queue.

So quite obviously, one should not run a blocking operation on the UI thread. If you do, messages would stop getting processed from the Message Queue and your app would become unresponsive. This is what leads to the famous Application Not Responding (ANR) dialog. One solution is decsribed here: create a handler, spawn a worker thread, post results back from the worker thread to the handler, update the UI. But this is a bit cumbersome to do. A simpler solution is to use a AysncTask which takes care of the underlying plumbing.

Service

As mentioned earlier, a Service is a type of component that is used to carry out a background operation, and does not provide a UI. An app component can start a service, and even if the user switches out of the application, the service would keep running. Typical use cases include playing music and downloading a file. Android ensures that a process running a Service is not killed as far as possible (see Process lifecycle above).

Note that a service by default runs on the main UI thread in the same process. This means that if it carries out a blocking operation, your UI would become unresponsive since the thread would not be available to run the Activity. To circumvent this, you should launch a worker thread inside the service.

• Architecture
• HTTP
• Security Model
• Content and Rendering
• JavaScript
• Apps

Having said that, I have a few posts lying around where I have never gotten around to writing part 2. Let’s hope it does not happen in this case

1. Rendering Process

The job of a browser is to fetch and display a web-page. At a high level, most modern browsers carry out the following steps to render an HTML page:

(Source: https://developer.mozilla.org/en/Introduction_to_Layout_in_Mozilla)

• Load the HTML
• Parse it
• Apply styles
• Build frames
• Layout the frames (flow)
• Paint the frames

1. Load: The browser tries to fetch the page from the specified location. Typically this would be thru a HTTP client. However, a HTML page may also be loaded from a filesystem. Irrespective, the loader fetches the HTML page from its location. The super important concept of Browser Cache comes into play over here – but more on this later. The way the HTML page gets loaded is different from the way the resources get loaded. In WebKit there are two different pipelines – one for loading the page and another for loading resources:

(source: http://webkit.org/blog/1188/how-webkit-loads-a-web-page/)

2. Parse: As the stream comes thru from the loader, an HTML parser starts building the DOM (also called a “Content Tree”) – each node here is an HTML element. Now a lot of HTML on the net is broken, and each browser has had to implement its own quirks to parse HTML leading to subtle incompatibilities. HTML 5 however specifies the parsing algorithm. As this gets adopted, the x-browser incompatibilities because of parsing should go away. While parsing, the engine may come across resources (JS, CSS, images, fonts, etc.) When that happens the particular resource is queued for loading and parsing continues. Again, there is more to this, which we’ll tackle later.
3. Compute Styles: The browser provides a default stylesheet. Often the HTML page also has a set of styles specified. These styles need to be applied to the Content Tree. For this purpose, a “Rendering Tree” is built – this essentially consists of elements that are to be rendered. For example an element with display set to none would not appear in this tree (nor would its descendants). Nor would elements like HEAD and SCRIPT. Nodes in the Render Tree represent style information: CSS box model, z-order, opacity are all specified here
4. Construct Frames: Most render-able elements follow the CSS box model: They have height, width, border, spacing, padding, margin and position. For these objects, a rectangular box – called a Frame – is created. Not all objects have a frame – for example the SVG image above does not have a frame. It is put inside an iframe, which has a frame. A frame has all the information on how the object itself is going to be rendered. What is not known however, is how is the element going to be placed w.r.t other elements.
5. Compute Flow: Flow Computation or Layout Computation is about how elements are placed w.r.t each other and is mostly controlled by the CSS Visual Rendering Model. This is typically a recursive process from the root of the tree to leafs. Also, this is typically a lazy process – it is done on a need-basis. Basically when the layout engine determines that an element needs to be laid out (for example a newly added Node), it marks it as such by setting a dirty bit. The actual layout is done only when some method is called which requires the new information. A visual representation of the layout process can be seen in these videos:
   • Gecko reflow for Google homepage
   • Gecko reflow for Wikipedia homepage
   • Gecko reflow for Mozilla.org homepage

   Most browsers do flow calculation at a higher resolution than what any display would have. This is to support zooming – when the user zooms in or out, the objects can be drawn correctly on the screen without requiring any extra steps other than mapping the coordinates to real pixels.

6. Paint: Once the engine knows exactly where the objects need to be drawn, comes the process of actually rendering the objects on the screen. This process – called Painting – is described in agonizing detail in Appendix E of the CSS 2.1 Spec. This is basically a Tree walk from the root of the Rendering tree, where each node is asked to paint itself. The actual rendering is abstracted out thru a Graphics Engine which is responsible for actually turning on the pixels and things like hardware acceleration.

2. Rendering Modes

The actual execution of the rendering process described above can change completely based upon the rendering mode the browser decides to use for a particular page. The reason browsers have different rendering modes is because of the history of the web, and understanding rendering modes is very important to understanding how browsers behave. However, I would not touch upon it here since http://hsivonen.iki.fi/doctype/ does an excellent job of capturing all the details. If you are just interested in the background, read http://en.wikipedia.org/wiki/Quirks_mode.

3. Dynamic Pages

Pages can change because of JavaScript or because of user interaction which triggers parts of the rendering process:

(Source: https://developer.mozilla.org/en/Introduction_to_Layout_in_Mozilla)

• If DOM elements are added or removed, the typical response of the browser is to follow the rendering process described earlier in almost serial order
• If the Style attribute on an element is changed, the style for the element needs to be recomputed, the page re-flown and re-painted
  • Browsers may optimize this by batching style re-computes by queuing them
  • However, scripts often read back changes that they have just made which requires the re-styling queue to be flushed
  • For better performance, make style changes as a batch and then read them in a batch so that the queue is flushed less frequently
• Some style changes are cheaper:
  • Changing size / location would not require style re-compute but only re-flowing and re-painting
  • Color change does not require re-flowing, but only re-painting
  • Scrolling also does not require re-computation, but only re-painting – this is typically done incrementally and may not even require full repainting (but things like fixed background images would necessitate full repainting). So moving elements by scrolling programmatically can be faster than moving elements by modifying their style attribute
• Re-Flow – because of position or size changes – is typically recursive (root to leafs)
  • Some attribute changes in a child can trigger changes in the entire ancestry all the way up to the root. Example: Height changes
  • Some attribute changes in a parent can trigger changes in all the descendants right down to leaves. Example: Width changes
  • Browsers can detect that only a section of the tree may change and do re-flow only on that sub-tree

4. Resource Loading

As the Parser goes over the Content Tree, it may see an element referring an external resource (image, CSS, JS, font, etc), which needs to be loaded. This loading happens as follows:

Order of Loading

While typically resources get loaded in the order of appearance in the document, browsers optimize this by prioritizing stylesheets and JavaScript files ahead of images. It is also recommended that stylesheets be put at the top. This is because:

• Stylesheets are required to build the Rendering Tree, but have no impact on Content Tree, so HTML parsing and JS execution can continue while CSS is downloaded and loaded.
• A script could ask for style information even as the stylesheet is being downloaded and the rendering tree is being built. If this happens, you get an error. So you want to load styles before JS starts executing

Parallel Loading

Modern browsers maintain multiple persistent connections to a server. This allows parallel loading. Parallel loading is a good thing because it reduces the overall latency of the page getting delivered to the end-user. However, out of consideration for the load factor on web-servers, The HTTP 1.1 RFC recommends that “Clients that use persistent connections SHOULD limit the number of simultaneous connections that they maintain to a given server. A single-user client SHOULD NOT maintain more than 2 connections with any server or proxy”.

Note that there is a trade-off here between the overhead of number of open sockets vs. the overhead of opening new sockets, and its impact on latency. With the number of external resources being fetched by a page going up, it makes sense to optimize for reducing the number of times a new connection has to be setup, to reduce the latency and improve the user experience. Indeed, most browsers these days allow more than 2 simultaneous connections per host. Steve Souders summarizes the current situation nicely in his Roundup on Parallel Connections.

Blocking Loads

Since a script can call document.write(), parsing can’t proceed before the script is fully loaded, executed (if there is any inline script in the script block) and document.write() has been inserted. This means that a script load blocks parsing, and that means that further loading is blocked, preventing the parallelism mentioned above from being exploited. Modern browsers do help a bit. For example, in WebKit, when the main parser gets blocked because of a script load, it starts a side parser that figures out other resources to load in the rest of the HTML. However, that is WebKit – for other browsers, there are a couple of ways out:

1. Put script blocks at the end – that way they do not pause any further parsing
2. Use a hack to download scripts asynchronously – Souders sums these up in his post on Loading Scripts Without Blocking
3. HTML 5 specifies the async attribute on the script tag which tells the browser that the script does not require synchronous execution and the parser can continue. WebKit recently started supporting this attribute and Firefox has supported this since 3.6.

5. Physical Architecture

Web browsers started off with a single process, single thread model. This was acceptable since web-pages were just documents that had to be rendered. However, the web has evolved from being document-centric to becoming application-centric – a lot of sites these days are applications, with a lot of active code, a far-cry from the static content browsers were designed to render. This gives rise to problems of stability, performance and security. To address these, most browsers have moved (or are in the process of moving) to a multi-process architecture. There are three drivers behind this trend:

• Performance: Multiple processes exploit multiple cores
• Security: The browser can spin up a new process in a lower privilege mode, reducing / removing the impact of malicious code
• Stability: A badly behaved page / script / plugin does not impact others since it is isolated in a process.

Firefox

Firefox uses a single thread, single process model. This means that in Firefox a single UI thread is shared by all windows. The reason for that apparently is to allow X-DOM blocking calls from diff pages of the same origin. More details on http://www.mail-archive.com/mozilla-layout@mozilla.org/msg03580.html. Network calls and web-worker requests are handled on different threads.

To provide better isolation and reliablility Firefox will move to a multi-process model with its Electrolysis project. However, this seems to be for plugins alone and pages would continue to be served from a single process.

IE

The first browser to ship with multiple process support was IE 7, with each browser window running in its own process:

(source: http://blogs.msdn.com/b/ie/archive/2008/03/11/ie8-and-loosely-coupled-ie-lcie.aspx)

IE 8 improved upon this model by putting each tab in its own process, but moving the frame and the broker into a common process for improving startup time. Microsoft calls this architecture Loosely Coupled Internet Explorer (LCIE):

(source: http://blogs.msdn.com/b/ie/archive/2008/03/11/ie8-and-loosely-coupled-ie-lcie.aspx)

The actual model is however more sophisticated than what the diagram above suggests since IE 8 tries to balance the benefits of more processes with the extra overhead, without compromising on security. The actual process model is:

• Protected Mode processes: Irrespective of memory overhead, sites with different levels of configured security open in different processes. This approach called Protected Mode is based on Mandatory Integrity Control
• Context-based tab-processes: The decision on whether to create a new tab-process or not is made depending upon the amount of memory available
• Max tab-processes: A specific value of maximum tab processes that can be created for a single isolated session at specific MIC

More details: http://blogs.msdn.com/b/askie/archive/2009/03/09/opening-a-new-tab-may-launch-a-new-process-with-internet-explorer-8-0.aspx

Chrome

Chrome follows an approach similar to that of IE 8 – the host process for a tab is called a Renderer and the broker process is called Browser:

(source: http://dev.chromium.org/developers/design-documents/multi-process-architecture)

Chrome supports four process models:

• Process per site-instance: Different visits to a site are in separate processes. Provides the highest level of isolation but also creates more overhead.
• Process per site: Different sites are isolated from each other, but visits to the same site run in the same process. Reduces overall memory overhead, but if you have several pages from a site open, the size of a single Renderer would be quite large, perhaps slowing it down.
• Process per tab: While the previous models consider source of origin, the process per tab model is based on the choice a user makes. One process is used for rendering one tab, and if in the same tab you switch to a different site, the process would continue.
• Single process: This is the simplest process with no isolation.

In both Chrome and IE, a frame runs in the same process as its parent page. Also, separate process may prevent legal interactions between two pages from the same origin. Chrome’s solution to this is to not permit a x-process call even if it is legal. What IE does is to proxy these specific calls and convert them behind the scenes into some sort of IPC. This may also be supported by Chrome at some later stage.

Cloud

Ok, I’m gonna stick my neck out on this – IMHO, post PDC 2010, Microsoft has the most comprehensive offering among all the Cloud vendors when it comes to Windows. They are doing what everyone else is doing, and more. Besides, they are making it far simpler to move existing apps to the cloud and integrating your on-premise apps + infra with the cloud. The big problem is that they are only doing this for Windows, and there is nothing on the Linux side. So if you are a pure Microsoft shop, choosing Azure for the Cloud is a no-brainer. However, if you have a mixed environment, you would need to host your Linux workloads somewhere else, which may / may not work for you.

VM Role: Azure now offers a hypervisor in the sky to host your Windows VMs. This is interesting since with the VM Role, Azure now provides both models – a auto-scalable, compute service exposed thru CLR and Win32, that competes with Google App Engine’s Python / JVM fabric, as well as the your-own-box-in-the-sky VPS model that competes with Amazon EC2, Rackspace and others. Jargon hungry analysts call the former PaaS (Platform as a Service) and the latter IaaS (Infrastructure as a Service). Both are useful – the former model works where you need agility of deployment, infinite scalability, and where your app and deployment architecture can be accommodated on top of the primitives provided by the service. The latter is useful if you need more flexibility in your architecture, or if you want to do a quick migration of an existing app without modifying stuff. The VM role would initially be available thru a invite-only beta program starting next year.

Enhancements to Windows Azure: While the VM role certainly creates more flexibility, the PaaS version has become more flexible too:

• Full IIS and Elevated Privilege: So far an Azure deployment could have a web-role, a worker-role or both, with the web-role mapping to a IIS website. What changes is that the web-role would now start mapping to an IIS instance, allowing you to run multiple websites under a single web-role, not to mention the ability to install IIS modules (or configure the APS.net pipeline). Also, the web and worker roles in Azure can now run in an elevated privilege mode. This would again help people migrate their existing apps.
• Azure Connect: A virtual network that enables direct IP-based connectivity of app instances to and from on-premise infra. Basically sets up a IpSec based tunnel. Very helpful for sysads and devs who need to bring cloud instances under the org AD, or where cloud apps need to access on-premise data.
• Remote Desktop: Right now the way to manage your Azure deployment is to use the Powershell Cmdlets for Azure. Most people like them since they are bandwidth friendly and scriptable. But now there is help for the command-line challenged. You can now “see” your application host over remote desktop. Not sure if this exposes any new functionality beyond what was already available thru the Management API.
• Better Java Support: I am not sure if people are aware of this, but it has been possible to run Java apps on Azure since around an year, including the ability to run Tomcat (thru the Tomcat Acclerator), ability to access Windows Azure services thru the open source Azure SDK for Java and a JDBC driver for SQL Azure. What’s new is an Eclipse plugin and App Fabric SDK to access App-Fabric (see below) from Java.
• Better PHP Support: Similar to Java, it is possible to run PHP apps on Azure. And similarly, there is a Windows Azure SDK, an Eclipse plugin and a PHP driver to talk to SQL Azure. Some extras: command-line tools for PHP and a Windows Azure Companion to make it easy to deploy, diagnose and monitor PHP applications.

Improved App Fabric: The App Fabric is one of the strongest differentiators in the Azure stack. This is some very sophisticated middleware that I think is unique among all the Cloud vendors today:

• Access Control: Identity integration with AD, Live Id, Facebook, Google and Yahoo. Authorization thru declarative rules that transform incoming security claims into claims understood by app. REST API.
• Service bus: Allows message exchange across firewalls, NAT gateways, etc. with the same programming model as for WCF or using REST, Pub-Sub system with multiple topics, Full-duplex bi-directional communication, including P2P with NAT traversal. It is now possible to do durable messaging, which increases delivery assurance to mobile devices / 3rd parties. If you have ever tried to do cross network messaging, you know how difficult firewall traversal and NAT traversal can get, and how troublesome DoS attacks can get. The Service Bus addresses all these issues and more.
• Integration: BizTalk in the sky – pipelines, transforms, adaptors, BAM, Rules, self-service trading partner community portal and provisioning of B2B pipelines. What, you do not know about BizTalk? Well, think of it as a higher degree of abstraction for the messaging layer, and a lot of pre-built patterns and functionality. If you are running multiple apps in your IT, sooner or later you need something like this. App Fabric Integration brings it to the sky so that you can integrate your on-premise apps and cloud apps using the same model. Not available yet though – the invite only CTP starts in 2011.
• Caching: Memcached like distributed in-memory cache, available on the local network. No limits on object size, pre-built ASP.net providers for session state and page output caching (so no app code changes required). Additionally, this can be secured thru Access Control (mentioned above). However, there is no HA yet. Available thru a invite-only CTP.
• Composite Apps: So you have got your app all nicely written with access control defined, endpoints exposed using Service Bus, message transformation, etc. being handled by the Integration service and frequently used data cached. Is this enough? What about lifetime management? Scale out/scale-in? Deployment automation? Monitoring? Mission critical systems need all this and more. This is where the Composite Apps service comes in. This essentially provides a multi-tenant runtime and tools for handling all of the above thru a declarative model. Again, CTP would be available in 2011

Improved CDN: So far Azure CDN was only able to pull content from Azure Storage. Now it can also cache data returned from the app (dynamic caching). Also the CDN is available over SSL/TLS. Besides, they have put up POPs in Middle East and improved the pipe.

Improved SQL Azure: SQL Azure would start providing Reporting Services (thru an invite-only CTP to begin with), a Web-based management console (called Database Manager) and ability to Sync entire databases or specific tables between on-premises SQL Server and SQL Azure, or between SQL Azure datacenters. The data to be synced is declarative defined, and the sync can be scheduled, with conflict handling and logging + monitoring support.

Azure Marketplace: The Azure Marketplace “is an online marketplace for developers to share, find, buy and sell building block components, training, service templates, premium data sets plus finished services and applications needed to build Windows Azure platform applications.” The data part (which I think is more interesting) is already available at the Data Market. This includes both public domain data-sets as well as commercial data-sets on a wide variety of topics – “everything from demographics, navigation, crime, media, to web services and algorithms for data cleansing.” Cool stuff!

Web and Mobile

One good thing that happened at the PDC was that Microsoft came clean on its UI platform strategy, and the strategy is a pretty simple, logical one:

• Web Apps thru HTML 5
• Native apps on Desktop thru WPF
• Native apps on Mobile thru Silverlight

There is a lot of noise in the media about how Microsoft has dumped Silverlight and is repositioning it for the mobile, etc. There are three aspects to this discussion:

Why focus on HTML 5 for the Web

This is a no-brainer:

• HTML 5 already provides most capabilities that required plugins like Flash / SL not so long back, so SL is not adding a ton of value over HTML 5 anymore.
• HTML 5 enjoys tremendous momentum with web-devs
• Firefox and Webkit have better support for HTML 5 than IE, and hence more web-dev mind-share
• IE is losing ground to Chrome, Firefox and Safari

The choice for Microsoft is obvious – embrace HTML 5 completely and take a leadership role. And now with this commitment coming right from the top, with SteveB himself vaxing eloquent about HTML 5, you can bet that the IE team will produce the goods. This may not happen in the IE 9 timeframe though, but then this is a long-term play.

What about SL on the Web

There are lot of people who think that SL is about to disappear from the web, but that is incorrect. There are lots of things that are still very hard to do in HTML 5, for which developers will continue to rely on plugins like Flash and Silverlight. However, there is no doubt that SL will move into a niche role, being utilized more to fill HTML 5 gaps, at least when it comes to the consumer web. On the enterprise side, SL may enjoy a more mainstream role since x-platform, x-browser and plugin deployment issues are more controllable there, and development on SL is any day simpler than on HTML 5, especially if you have a background in imperative languages.

Why SL for Mobile

The vision for CoreCLR – the version of CLR that powers Silverlight – has always been to provide the .Net experience on all low footprint environments. If my memory serves me right, a lot of SL core came from .Net Compact Framework which was the version of .Net shipped on Windows Mobile back in 2002-2003. And since SL 2, a team in Hyderabad has been working on making SL available on the mobile. So SL on Mobile is nothing new. It also makes sense as the mainstream platform for the Mobile, since SL is a proper subset of WPF and therefore you can share a lot of code between desktop and mobile. So why not WPF itself? I’m not very sure, but certainly the lighter footprint of SL as compared to WPF is more suitable for mobile. Also, this would allow Microsoft to optimize SL for the mobile, focussing on issues like reducing power consumption and CPU utilization. Last, but not the least, the developer momentum behind Silverlight is certainly bigger than that behind WPF, and therefore this allows Microsoft to accelerate the app development on Windows Mobile.

IE 9 HTML 5 Support

Things are looking better than ever on the HTML 5 support front. The first Official HTML5 Test Suite Conformance Results from W3C show that IE 9 is passing most tests, however the coverage of the test itself seems fairly small – only a few features are being tested. More illuminating are the following comparisons on wikipedia:

• JavaScript
• CSS
• DOM
• HTML 5
• HTML 5 Canvas
• HTML 5 Media

After going thru these comparisons, my take is that all browsers are at varying degrees of HTML 5 support and IE 9 is not too far behind. How quickly the various browsers start supporting the major features would be a function of resources deployed and how quickly the release cycles go.

What should also be obvious from the above comparisons is that it is utterly foolish to do browser detection since the feature set of each browser is going to change very rapidly over the next couple of years. What we should do instead is feature detection and fail gracefully. This is of course done by all the major JS libraries already, the risk is in your own custom code. If you are doing browser detection, you should get rid of it right now to keep it forward compatible.

Windows Phone 7

The development model for Windows Phone is clear enough – Silverlight for apps and XNA for games. Both make sense and provide a ton of power. What Microsoft has done is to provide a bunch of templates, tooling and APIs to make it simpler to do Windows Phone apps. Moreover, this can be done using VS Express, so there is no cost! However, for developing apps, you need to get familiar with the UI, its nothing like iOS or Android. If you do not have a Windows Phone, the simplest way is to run the emulator that ships with VS Express and figure your way around. Finally there is also the Windows Phone Marketplace – same concept as the App-Store, including an approval process and $ 100 fees for submitting an app. But none of this is really new – all of this has been in place for a while.

While we are on this topic, I do want to mention that I am surprised that Microsoft is taking the Apple approach to the marketplace. The real value of a marketplace is in providing consumers and developers a single point for app publication, discovery and access. The approval process and the submission fee are not good for anyone in the long run, including the platform vendor. Especially for Microsoft, who need to steal share from iOS and Android, I think a more open marketplace would have helped:

• Reduced costs for the developer, and therefore for the end consumer
• Less process overhead for the developer
• Freedom of expression – this counts for a lot in spirit, if not in fact
• Mature content can be marked as such by reviewers or community, same as what happens on sites like YouTube / Facebook
• There is the problem of crapware, but then a rating / popularity / recommendation system would easily address that
• There would be some upfront loss of revenue, but I think right now the real problem is increasing adoption for which you need to drive up the platform value by having more content + functionality available on it.

A marketplace that requires content approval and a submission fees discourages the developer from building native apps and instead focus on building mobile apps. No platform vendor likes that, since that reduces the tie-in to the platform. Microsoft understands this well enough and despite that we have an Apple like marketplace. Very baffling.

Languages and Tools

The focus of the next version of C# and VB would be asynchronous programming. There are two motivations for this:

• UI responsiveness: As apps get more and more connected, the data often comes over a network call, which must not block the UI thread
• Scalability: Use the thread for doing some useful work and not keep it blocked

Now at this stage, there is a chance that one would confuse asynchrony with parallelism. That is not the case – asynchrony is about yielding control while results are awaited, whereas concurrency is about doing two things in parallel. The former is necessarily cooperative, while the latter maybe achieved thru multiple hardware threads or pre-emptive / co-operative scheduling of multiple threds.

Just to be sure, .Net Framework has provided async support since version 1 via the begin-end pattern. So to appreciate the value of the async support being provided requires us to go a little deeper in terms of semantics, what happens behind the scenes and why the feature has been designed the way it is. These are all involved topics, and I would try and cover async support in a different post. Meanwhile, you can find more details on http://msdn.com/vstudio/async.

For one, they are taking a platform approach exactly like Microsoft –  Facebook Connect is the most powerful and widely used identity platform on the Internet today – as enticing to developers and businesses as Windows was in its heydays. They have succeeded where Microsoft failed (Hailstorm, Passport) as well as the open source community (OpenId). Apparently, 10,000 websites integrate with Facebook everyday and people are even taking the Facebook experience offline! This means that as other companies innovative and create value, Facebook gets richer. Exactly like Windows. IIRC, one of the metrics at Microsoft used to be the ratio of ISV revenue to Windows revenue, the idea being that this ratio should keep going up. Facebook today is in a similar position and benefits similarly from their platform.

Second, they are changing the rules of the game, much like Microsoft did. The model before Microsoft was a single integrated stack and customers had to pay big money for the iron, the software and the services – all from the same vendor – IBM. Microsoft changed this by commoditizing software and opening up the vertically integrated stack. In a similar vein, Facebook changes the game by offering an alternative to Google Search, hitherto the de-facto gateway to the web. A lot of content discovery today happens thru the Facebook News-feed. This means that publishers once again need to target their audience and not just the search engine, which is biased for more frequently changing content and can be, and has been gamed by publishers. This helps the small, niche publisher who would otherwise be lost in the long-tail, never landing on the first page of a Google Search. This is not just about stuff you read, but also about what you buy. My wife’s latest acquisition – a DSLR camera – was entirely based on recommendations received from friends and family, mostly on Facebook. An year back, she would have been searching and going thru review sites. Not that we did not search or read reviews, but the decision was mostly based on recommendations.

Finally, they are using this tremendous leverage to move into markets they find interesting, and much like Microsoft when they decide to move into that market, the incumbents are under threat to becoming irrelevant. This is what happened when they announced the beta of their Q&A system, with Quora and Aardvark coming under threat. This is again happening with Facebook Places and this time Foursquare is under threat. Now one could argue that this is bound to happen anytime the 800 pound gorilla in any industry forays into a market, but this is different. This is about leverage. Google / Apple, despite being larger, would never create the kind of threat that Facebook creates simply because Facebook owns the user like no one else does. Exactly the same as Microsoft owning the PC like no one else. Of course Microsoft was prudent about it – they focussed only on the software bit (where the margins were highest) and deliberately kept away from the hardware and the services businesses to let the ecosystem thrive and drive the platform forward. Facebook would also need to figure out where they want to pursue opportunities and where they would not go.

• Staying with a cloud provider for the blog service
• Ability to install plugins

Now WordPress.com does not allow you to install plugins unless you are really big, and therefore Blogger made sense. However, I have found Blogger to be very limiting and every time I looked at the WordPress plugin ecosystem, I found myself yearning for all that richness. Finally, yesterday evening, I set up a box in the sky, installed WordPress, added the plugins I wanted and imported my blog from Blogger.

What went well:

• Installation was a breeze – took me less than 10 minutes to get WP up and running on a bare Ubuntu box (and I am a newbie to LAMP)
• Plugins – you are spoilt for choice here, and the time taken was mostly in trying out various plugins and selecting which one to use for a specific functionality.
• Import went off without a hitch, except that it kept throwing an error for one of the posts (the migration from Live to Blogger one)
• Bonus was that I was able to bring back all the comments I had lost on my older Live Space blog – they could not be imported to Blogger, but WordPress worked like a charm.

The only thing that did not work was that I could not find any simple way of retaining the permalinks – Blogger appends a random number after each post and short of entering that manually for each post, I can’t think of any other mechanism to retaining them. This is bad because it will break people’s bookmarks, but with the new scheme, I don’t think this will ever need changing hence.

Summary

The need to look at Non SQL systems arises out of scalability issues with relational databases, which are a function of the fact that relational databases were not designed to be distributed (which is key to write scalability), and could thus afford to provide abstractions like ACID transactions and a rich high-level query model.
All NoSQL databases try and address the scalability issue in many ways – by being distributed, by providing a simpler data / query model, by relaxing consistency requirements, etc. I find it useful to bucket them as follows:

Distributed vs. Not-distributed: Distributed databases take the responsibility of data partitioning (for scalability) and replication (for availability) and do not leave that to the client.

Over here, the model of distribution which seems most compelling is the one used by Dynamo. Indeed, it is copied by Voldemort, Riak and Cassandra – three very different kinds of stores. The reason it is most compelling is because it gives simple knobs to an application to tune its expectations of durability, read performance, consistency, write performance, etc. This makes it very general purpose. The other reason this model is good is because it allows heterogeneous hardware to be used in an efficient way (however Cassandra departs from this).

Data Model richness: The other key distinction is in terms of richness of data model:

On one end of the spectrum are the simple key-value stores: Dynamo, S3, Redis, Scalaris, Voldemort, etc. At the other end of the spectrum are the column-stores which provide a very rich model: BigTable, Cassandra, Hypertable and HBase fall into this bucket. This richness comes at a price – the model is not simple, and you need to think data modeling grounds up. Somewhere in between are the document stores – a sort of schema free cousins of relational databases: CouchDb, Riak, MongoDb, etc. Simple to understand and richer than plain key-value stores.

Disk vs. Memory: A third useful dimension is whether the database is memory-driven or disk-driven. This is important since in the latter case you need an explicit cache, while in the former case you are not durable:

On one end of the spectrum is Scalaris which is entirely memory-driven, and Redis which is primarily memory oriented (you can do background snapshots). Cassandra, BigTable, Hypertable, Hbase allow configuring how large the Memtable can get, so that provides a lot of control. The document stores – CouchDb, MongoDb and Riak – all seem to be using on-disk B+ trees, and Voldemort uses BDB and MySQL. Having a pluggable storage engine which is in-memory, does not make it configurable since the in that scenario you are entirely memory driven with no durability at all!

So which one wins? Well, I am biased towards the database solving the scalability issue by taking over the responsibility of partitioning instead of leaving that problem with me. So theoretically, Cassandra seems to combine the best of both worlds: the sophisticated distribution model of Dynamo with the richness of a column-store. Also, it is in heavy production use despite still being in beta. However, I believe the learning curve here would be higher for modeling data, and it may make sense to opt for the simplicity of a Voldemort for most cases. Ultimately it would depend on your app requirements and development team.

1. Why Non-Relational

Some of the stuff here may not resonate with you if you are an enterprise developer since enterprise apps don’t have to deal with the kind of gigantic scale that (some) consumer web applications deal with. However, given the rate at which data is growing and the number of users who are using IT systems, these issues are only going to become more and more common – for smaller consumer apps, as well as for enterprise apps. In fact, even today, irrespective of the scale at which your app operates, if you want to take advantage of a Cloud platform like Google App Engine or Microsoft Azure or Amazon Web Services, you would perhaps need to think of some of the issues below, because at the infra level these platforms do have to bother about high scale and may impose constraints on the application / data model to help them scale.

1.1 Relational databases are hard to scale

1.1.1 Replication – scaling by duplication

• Master-Slave:
  • Each write results in N x writes where N is the number of slaves. This leads to diminishing returns beyond a point, thus imposing a limit
  • While reads would get faster (since you can now read from N nodes), writes are still bottle-necked to one node
  • Critical reads still need to go the master since the write may not have propagated to all nodes. This logic needs to be built into the app.
  • High volumes of data pose a problem since you need to duplicate the data N times. This also leads to limiting how much you can scale with
    this approach.
• Multi-Master
  • Can improve write scaling by adding more masters, but this may lead to conflicts
  • Conflict resolution happens at O(N³) or O(N²) – http://research.microsoft.com/~gray/replicas.ps

1.1.2 Partitioning (sharding) – scaling by division:

• Scales reads as well as writes
• Not transparent to the application. The application needs to be partition aware.
• The value of an RDBMS is in relations. Once partitioned, these relations get broken – you cannot do a join across shards – this now needs to be done in the app layer.
• In general, manual sharding in relational databases is not simple.

1.2 Don’t need some features

1.2.1 UPDATEs and DELETEs

• Typically not used since that leads to loss of information
  • May need the record for auditing, or for re-activation
  • Typically, the info is never really “deleted” from a domain perspective anyway
    • A user “leaves” a community – his posts would not be removed
    • Employees “leave” companies – their employment record is maintained
    • The canonical ACID transactions example: debits from a bank account – this is not a DELETE, but an INSERT
  • Nor is info just “updated”
    • Salary gets “incremented” – the previous record is maintained
    • Your bank account balance is not updated – there are “debits” and “credits”
• So one can typically model an UPDATE / DELETE as an INSERT and version the record.
  • When data gets too large, archive inactive parts of data
• Two problems that arise when you go for an INSERT-only system:
  • The database cannot help you with cascades thru triggers – this needs to be done explicitly in the app layer
    • The cascades are actually far more complex than propagating a DELETE / UPDATE – this is a domain requirement:
      • When an employee leaves, you need to update the payroll system so that full and final compensation can be carried out
      • Everytime a bank account gets debited, checks need to be made on standing instructions, minimum account balance, etc.
  • Queries need to filter out the inactive records
    • Can lead to dirty looking code – addressed using views
    • There would be some perf penalty that can be addressed by archival

1.2.2 JOINs

• Why avoid
  • Joins are expensive when data volumes are high since the database server has to perform complex set operations over large volumes of data
  • Do not work across partitions
  • Techniques like Materialized / Indexed Views not supported by all databases
• How to avoid? De-normalize!
  • Purpose of normalization
    • Make it easier to have consistent data by keeping just one copy
    • Reduce the amount of storage
  • With De-normalization
    • Burden of consistency shifts from the database to the application layer
    • Easier if you only do INSERTs and no UPDATEs / DELETEs
    • Would lead to data bloat – can be significant for large volumes, but storage is cheap and you can archive inactive data

1.2.3 ACID Transactions

• Atomic – do not need atomicity on modification of more than one record. Single key atomicity is enough
• Consistency – CAP theorem – can get any two of Consistency, Availability, Partition tolerance – not all three. (Also see http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.41.1915)
  • Most systems need partition tolerance and availability ahead of consistency.
    • Customer wants to place an order – you will accept the order, not return the money saying the system is unavailable – availability is important
    • Inventory would be checked asynchronously
    • Order details would be checked asynchronously
    • … would be done asynchronously
    • All this while data would be in an inconsistent state
    • This is ok – businesses are like that. They do not operate on a single version of truth. Reconciliation happens all the time.
  • Therefore our data model need not be strongly / strictly consistent. We can do with Eventual Consistency.
  • In most scenarios we need Read-Your-Writes Consistency and Monotonic Reads Consistency (as defined by Vogels in the paper above)
  • Strong consistency relies upon conflict resolution at write time to keep read complexity simpler. This does not scale.
• Isolation – do not need isolation beyond Read-Committed. Easy with single key atomicity (above)
• Durability – need durability till the time that RAM becomes cheap enough that one can afford many peer replicated nodes holding data in memory so that data is available even with node failures.

1.2.4 Fixed Schema

• In an RDBMS you have to define the schema before you can start using data (somewhat like declaring types in statically typed languages)
  • Define each entity (table), its attributes (columns) and relations between entities
  • Define usage patterns (indexes)
• Modifying schemas is essential
  • Intense competition and rapid growth necessitate adding new features / tweaking existing features rapidly
  • Changes usually require modifying the data model, thus precipitating schema changes
• Modifying the schema is hard
  • Adding / Deleting / Modifying a column may lock the rows (imagine doing this for several million rows)
  • Adding / Removing an index may lock up the table

1.3 Don’t get some features

• Hard to model hierarchical data
• Hard to model graphs
• Don’t rely primarily on main memory
  • Preferable to avoid going to disk as far as possible and serve out of main memory to get faster response time
  • Most relational systems are not memory oriented, but disk-oriented. Even with large main memory, relational databases end up going to disk for most queries – they are not aggressive about serving data from main memory and avoiding going to disk.
  • Vendors are trying to address this by acquiring / building in-memory database technology, but this is far from mainstream

2. Desired Characteristics

The environment expected is that the system would be spread over 100s to 1000s of commodity machines (hence called nodes) with different capacities. In a system like this failure is expected, tolerated and recovered from, with no loss of data, and without affecting the overall a
vailability and scalability of the system at large. The following characteristics are explicitly required to address these requirements:

2.1 High Scalability

• Ability to add nodes incrementally to support more users and data
• Achieved via partitioning
• Increasing number of nodes should not result in a diminishing return beyond a threshold

2.2 High Availability

• No single point of failure
• Data should be available even as some nodes go down
• Achieved via replication since data is duplicated
• Also achieved via partitioning since at least some data continues to be available

2.3 High Performance

• Operations should return fast
• Achieved via being main-memory oriented instead of being disk-oriented, using non-blocking writes, lower complexity algorithms, etc.

2.4 Atomicity

• Individual writes need to be atomic – should not expose in-between state to a read operation
• Batching of multiple writes into a single atomic unit not required

2.5 Consistency

• Do not need strong consistency
• Ok to have eventual consistency (read-your-writes consistency)

2.6 Durability

• Data should be persisted to disk and not just kept in volatile memory

2.7 Deployment Flexibility

• Addition / removal of nodes should distribute data and load automatically without requiring manual intervention
• Should not impose constraints like requiring a distributed file system or a shared storage
• Should not require specialized hardware
• Should be able to work with heterogeneous hardware – identical hardware should not be required to use the system optimally (otherwise you need to upgrade all nodes to get max efficiency which is not practical in a system running on 1000s of nodes)
• Application should be able to control the degree of consistency, durability and read / write performance it requires without being aware of the deployment model.

2.8 Modeling flexibility

Should be able to model various types of data in a simple way:

• Key-Value pairs
• Hierarchical data
• Graphs

2.9 Query Flexibility

• Multi-Gets (retrieve a bunch of values, for the set of keys provided, in one call)
• Range queries (retrieve data based on the specified range of the key)

3. Database Managers

A Database Manager is a software library that is loaded in-process to provide a high performance database. Its focus is typically restricted to the job of maintaining on-disk (or in-memory) data structures. These libraries are often used by distributed databases as a storage backend for managing the CRUD operations.

3.1 Berkley DB

• http://www.oracle.com/database/berkeley-db/index.html
• Written in C. Language bindings: C++, Java
• Data Model: BTree, Hash, Queue (fixed length) and Logical Record Number
• API model: Key-Value. Value is opaque
• Concurrency support
  • Multi-process and multi-threaded access
  • Locking subsystem.
• Optional ACID transactions
  • Three isolation levels
  • Support for non-durable transactions
• Optional Replication
  • Master-slave replication (single master). Master selection based on Paxos type elections.
  • Pluggable communication layer

3.2 Tokyo Cabinet

• http://1978th.net/tokyocabinet/
• Written in C. Language Bindings: Java, Ruby, Perl, Lua
• Data Model: Hash, B+ Tree, Fixed length and Table
• Concurrency:
  • Re-entrant API functions.
  • Writers block
  • Locking granularity is per record for hash and fixed length databases, Per file for others
• Transactions:
  • Atomic operations
  • Two isolation levels: serializable and read uncommitted
  • Durability thru write ahead logging and shadow paging

4. Key Value Stores

Key-Value stores provide the simplest possible data model. However, this comes at a cost. Range queries are not straightforward (unless the database provides explicit support), and in general modeling applications in general on top of a key-value store can get complicated.

4.1 Amazon Dynamo

• http://www.allthingsdistributed.com/2007/10/amazons_dynamo.html – terrific paper, must read!
• Distributed key-value store. Values are opaque to system. Targets objects typically < 1 MB
• Internal to Amazon, not available for direct consumption externally
• Partitioning
  • Uses a variant of consistent hashing that addresses
    • Non-uniform data and load distribution
    • Heterogeneity in capacity / performance of each node
  • The hash ring is divided into V partitions – each being serviced by a virtual node. There are P physical servers, with each physical server being typically responsible for Q/P virtual nodes, however this is decided based on the capacity of each physical node. Number of physical nodes is much less than number of virtual nodes.
  • When a physical node starts for the first time, it chooses its set of tokens (virtual nodes) and maps nodes to their tokens. This mapping is stored on disk and initially contains only the local node and token set.
  • Mappings stored at different nodes are communicated to peers using a Gossip based protocol.
  • Eventually consistent view of mappings – each node connects to a randomly chosen peer every second and efficiently reconciles mappings.
• Replication – data is duplicated on multiple hosts.
  • Each key is associated with a
    “Preference List” -  a list of nodes to which it is propagated. This consists of N nodes where replicas are stored, and some more nodes for failure handling (see below)
  • Also, since number of physical nodes < virtual nodes, the preference list is built to ensure that the list contains only distinct physical nodes (by skipping positions in the hash ring). Since each node is aware of the token ranges handled by its peers (because of mappings getting propagated), this allows each node to forward a key’s Read / Write operation to the correct set of nodes directly
  • There are three configurable values:
    • N = number of nodes that store replicas of data
    • W = Min no. of nodes that must acknowledge the receipt of a Write before a Write completes.
    • R = Min of nodes that are contacted when a data item is to be read
    • If R +W > N, then write and read set overlap, giving Quorum.
  • Both Read and Write requests are handled by nodes called coordinators. A coordinator node is one of the top nodes in the Preference List for the key. The selection of a coordinator node is done by either using a partition aware client, or by using a load balancer.
    • Writes: The Write (Put) request is sent to the coordinator. The coordinator stores the value locally and then sends it to N highest ranking nodes in the Preference List that are reachable (healthy). If at least W-1 nodes respond with success, the Write is considered successful.
    • Reads: A Read (Get) request is received by the coordinator. The coordinator asks for all existing versions of that key from the top N ranking nodes in the Preference List that are reachable. If at least R nodes respond, the Read is considered a success.
    • So performance would be governed by the slowest node in a R/W operation.
  • This model of configurable (N, R, W) values gives applications control on the desired performance, availability, durability and consistency
    • Increasing W would ensure that data is replicated many times increasing durability. However, since W nodes would also be required to have a successful write, availability would reduce as W increases. Performance would also reduce since the chance that one of the nodes is a low thruput node increases. Also increasing W would potentially increase number of divergent versions (see below) creating reconciliation overhead.
    • Increasing R would ensure that consistency is high, but again availability would be reduced and performance may also reduce.
    • Reducing R would improve read performance. So for a read-intensive, low updates application, (N, R, W) can be set to (3, 1, 3)
    • Typical values of (N, R, W) for Amazon Apps are (3, 2, 2)
• Consistency – Since updates propagate to replicas asynchronously, the model is eventually consistent
  • Uses object versioning (each update results in a new immutable object) using Vector Clocks.
  • Consistency protocol: As mentioned above, a successful read requires that at least R nodes respond. Each response includes all versions of the object. If the coordinator node ends up with multiple versions of data, it does the following:
    • Returns all versions it deems to be causally un-related
    • Divergent versions are reconciled
    • Reconciled version superseding the current version is written back.
• Handling Temporary Failures:
  • As mentioned above, the Read and Write propagation considers the first N healthy nodes, not the first N nodes in the Preference List.
  • However, when a node that is not in the top N nodes (but in the top N Healthy nodes) receives a Write request, it is also given extra metadata to indicate which node was it actually meant for. This is called a Hinted Replica.
  • Each node periodically scans its hinted replica set and tries to connect to the original nodes for which the replica was meant.
  • If it is able to connect, the node tries to deliver the replica to the original node and if delivered, may delete the replica
  • This process is called Hinted Handoff
• Handling Permanent Failures:
  • Permanent failures can arise in case a hinted replica becomes unavailable or some other risk
  • To reduce chances of permanent failures, nodes sync replicas thru Merkel Trees
  • Each node maintains a Merkel tree for the key range hosted by it
  • To sync, two nodes exchange the root of the tree common to the key ranges hosted by them, and in case there are any divergences, the apt sync action is taken.
• Ring membership:
  • Addition / removal of node from ring is relatively expensive because of the need to rebalance partition assignment
  • Therefore addition of a node to a ring and its departure are explicit and not based on non-availability since non-availability can be because of transient conditions (say network)
  • Membership propagation and reconciliation happens during the same communication that is used for token mapping propagation and reconciliation (see partitioning above)
• Failure Detection:
  • The need to detect failure is to avoid trying to reach unhealthy (unreachable) nodes.
  • When a node A fails to reach another node B, it propagates that information thru Gossip. Checks periodically to see if B comes back. Info on arrival of node also propagates using Gossip.
• Persistence:
  • Pluggable model – Berkley DB Transactional store, MySQL, In-memory buffer with persistent backing store.
  • Apps choose the kind of storage they need.

4.2 Amazon S3

• http://aws.amazon.com/s3/
• Distributed key-object store. Objects are opaque to system.
• Size of an object can range from 1 byte to 5 GB.
• No limits on number of objects – unlimited storage.
• Geo-aware: You decide the Geo where your object is, and the object would stay within Amazon data-centers in that Geo.
• Consistency: Read your writes on new PUTs, Eventual consistency on overwrite PUTs and DELETEs. Depends on Geo. See http://aws.amazon.com/s3/faqs/#What_data_consistency_model_does_Amazon_S3_employ.
• Query model
  • Iterable lists: http://docs.amazonwebservices.com/AmazonS3/2006-03-01/ListingKeys.html
  • Retrieve objects using HTTP GET – supports chunked downloads. See http://docs.amazonwebservices.com/AmazonS3/2006-03-01/UsingGettingObjects.html
• Should be useful if objects to be stored are large (files, blobs, persisted graphs, etc.)

4.3 Project Voldemort

• http://project-voldemort.com/
• Distributed key-value store written in Java. Inspired from Amazon Dynamo.
• Partitioning and replication – same as Dynamo: Consist
  ent Hashing, virtual nodes, preference lists for routing, Gossip based state propagation, etc.
• Cluster Rebalancing – add node to cluster, node steals a partition from another node, pull-based gossip to let other nodes know. Donor nodes handles GETs while new node is transferring partitions.
• Versioning – Based on Vector Clocks. Same as Dynamo again
• Consistency – Read-repair. Write inconsistent versions across nodes, detect conflict during reads and fix them
• Pluggable storage using Berkley DB, In-memory, MySQL
• Pluggable serialization – supports JSON, Thrift, raw strings, Java, Google Protocol Buffers
• Offline index rebuilding (using map-reduce, etc.) and then push to live server, transparently swap
• Support for read-only nodes (for offline build and swap)
• Pluggable NIO socket implementation
• Support for data compression
• Performance – 10 to 20k reqs / sec
  • Running at: LinkedIn
• License: Apache

4.4 Redis

• http://code.google.com/p/redis/
• Key-Value store written in ANSI C
  • Values can be of multiple types: strings, lists, sets, ordered sets
• Memory-driven – loads the entire data in RAM, but data can be persisted:
  • Asynchronously saved snapshot – policies: time since last save, updates since last save
  • Append-only mode (commands logged to a file). Three options: on every command, every second, upto OS
• Single Process, no threads
• Memcache like protocol. Multiple client libraries across several languages
• Some of the more interesting Supported operations:
  • Strings: Increments and Decrements, atomic multi-set
  • Lists: Push and Pop, atomic R-pop, L-push (safe queues), Ranged Get
  • Sets: Intersection, Union and Diff, and their corresponding operations that store the result against a key
  • Sorting:
    • Sort operation that can be applied on a list or a set.
    • Sets when ordered return Ordered Sets (implemented using hash tables and skip lists). This means O(Log N) writes and O(1) reads. Ordered sets support Range operations.
• Replication: Master-Slave
• Partitioning: Up to the client library. Currently supported by
  • http://github.com/nrk/predis/ (PHP)
  • http://github.com/jdp/redisent (PHP)
  • http://github.com/ezmobius/redis-rb (Ruby)
  • http://github.com/ezmobius/redis-rb (Scala)
• Performance:
  • http://code.google.com/p/redis/wiki/Benchmarks reports 110k sets / sec and 81k gets / sec. Lots of other people have reported results as well
  • Replication – http://groups.google.com/group/redis-db/browse_thread/thread/3ab1c8b2126f1b8/29bdb6c5973f0388 mentions 10 M keys replicated in 12 seconds on EC2
  • Connections on Redis are cheap – no auth, etc. just a TCP handshake. Pipelining makes it even faster
• License: New BSD
• In use at: Github, Engine Yard, VideoWiki, and few others

4.5 Scalaris

• http://code.google.com/p/scalaris/
• Distributed key-value store based on written in Erlang
• No persistence, entirely memory driven. Can use a backend like Tokyo Cabinet for handling database size > RAM + Swap.
• Partitioning – Uses a modified version of Chord called Chord# that
  • Preserves key order (allowing range queries)
  • Does routing in node space
  • Delivers proven O(Log N) performance (proof in the paper linked above)
• Replication – Essential for being fault tolerant since there is no persistence. Uses a peer to peer replication approach called Symmetric Replication that reads and writes to a majority of nodes participating in replication.
• Consistency: Strong consistency – uses a modified version of Paxos that provides atomic transactions
  : non-blocking writes that execute in parallel with strong consistency.
• Language support: Erlang, Java, JSON RPC
• License: Apache 2.0
• Production Use: None mentioned

4.6 Others

• Tokyo Tyrant
  • http://1978th.net/tokyotyrant/
  • Network interface to Tokyo Cabinet. Acts as a database server
  • Written in C. Language bindings: Ruby, Perl.
  • Basically it is a process that embeds Tokyo Cabinet and then provides an implementation for concurrent and remote access to the database.
    • Uses a thread pool using epoll / kqueue
    • Protocols: Binary over TCP/IP, Memcache, HTTP
  • Partitioning: Up to client
• MemcacheDb
  • http://memcachedb.org/
  • Key-Value store (uses BerkleyDB)
  • Memcache protocol
  • Master-slave replication
  • Supports range queries
• Chordless
  • http://sourceforge.net/projects/chordless/
  • Java implementation of http://pdos.csail.mit.edu/chord/
  • Provides ACID transactions
• MNesia
  • http://www.erlang.org/doc/apps/mnesia/
  • Written in Erlang, part of OTP
  • Erlang specific – tables contain instances of Erlang records and records are represented as Erlang tuples

5. Document Stores

Document stores are a step further from key-value stores in the sense that a value associated with a key is a full blown record (document) which is not opaque to the database, but exposes a structure which allows the database to perform some operations on it. For example, the document  can be a JSON serialized object.
Note that this approach is different from a relational database where the schema is defined upfront in the form of a table. In a document store, each document can have a different schema. Despite this, it is possible to describe relationships between records, just the way you do in relational databases:

• One to Many:
  • Embed key of foreign entity in the document. Then the foreign entity can be retrieved.
  • Embed foreign entity itself in the document. Does not scale, but is faster
• Many to Many
  • Embed keys of one type of entities in the other type of entity
  • Maintain another entity that embeds the keys of the related entities.

As should be obvious – document stores are conceptually very similar to relational databases except that schema definition is not upfront.

5.1 Amazon SimpleDB

• http://aws.amazon.com/simpledb/
• Written in Erlang
• Data is modeled in terms of
  • Domain (a container for holding related data together)
  • Item (a entity that goes into a domain)
  • Attribute and its Value (a properties of an item)
• So basically each item is a dictionary to which you can add / remove attributes (keys) at any time. Related items go into a Domain.
• When an item is added, it is indexed based on its attributes (and the attributes of other items in the domain).
• You can issue SELECT statements much the way you would issue to a relational system, with the concept of a table being replaced by a Domain.
• Eventually consistent
• Partitioning: The domain-item-attribute model imposes limits on size of each domain, number of attributes / domain and number of domains, so in order to scale, you need to partition the data manually.

5.2 Apache CouchDB

• http://couchdb.apache.org/
• Written in Erlang
• Data and Storage Model
  • Records serialized in the form of JSON strings (documents)
  • Each document has a unique DocId
  • Uses B+ Trees: Both for main data as well as for Indexes
  • Append only operations (Every update generates a new Sequence Id for the DocId). Committed data is never over-written
    • Every write operation also results in index updates which are also append only, so a new node is added to the B+ Tree which recursively leads to Log(n) updates to the B+ tree.
    • During Compaction older versions are removed
  • Append only model means that Reads are done using Multi-Version Concurrency Control. A client can hold on to the older root of the B+ tree and get a consistent view while the data is being modified continuously.
  • Writes are serialized, except for blobs which can be concurrently written.
  • An update to a document is atomically committed with data and index updates getting synchronously flushed to disk, and the database header is updated.
  • When resuming from a crash, no recovery is required (except for recovering the database header). Partial updates are simply truncated.
• Views
  • Required to “add structure back to unstructured and semi-structured data.”
  • Can have multiple views for the same data
  • Defined using a JavaScript function that maps keys to values in a special type of document called a Design Document.
  • View functions are run when your query a view: The system takes the source code and runs it against every document in the database. There are basically two kinds of functions:
    • Map function: takes a single parameter – the document – a single document in the system, does some operation on it (can’t modify the document) and returns a result (mapping an input to a result).
    • Reduce function: takes a list of key-values and returns a single result after performing some aggregate operation on it (reducing multiple inputs to a single result)
  • View results are stored in a B+ tree and unless the document changes or the view definition changes, the results are not re-computed and fetched straight from the B+ tree.
• Replication
  • Master-slave with multi-master support
  • Only latest revision replicated
• Conflict Handling in Multi-master
  />
  • CouchDb detects conflicts and uses a deterministic algorithm for picking a “winner”. Deterministic means that all replicas end up winning the same version without talking to each other.
  • This winner may or may not be the one your app expected. This will have to fixed by the app itself.
• Partitioning and Load Balancing – Provided thru CouchDb Lounge
  • Uses consistent hashing to partition the data
  • Dumbproxy used for all requests except View requests. Implemented as an Nginx module
  • Smartproxy used for View requests only
    • Twisted python based daemon
    • Sends view requests to all shards
    • Merges responses before sending them back
    • Merges happen in constant memory space
• License: Apache 2.0
• Production Use: BBC, PylonsHQ, GPirate, and several others

5.3 Riak

• http://riak.basho.com/
• Written in Erlang. Uses the same architecture and algorithms as Amazon Dynamo.
• Client libraries
  • Erlang (JSON) – Jiak Client
  • Erlang (raw) – Riak Client
  • Python, PHP, Ruby, Java, JavaScript
• Data Model
  • Key-Value. Value is a document.
• Riak nodes go on a ordered consistent hash ring
  • 160-bit binary hash of key-value pair, maps to a position on the ring.
  • Ring divided into partitions. Each partition is designated an owner called v-node. The v-node is said to claim a partition.
  • Nodes try and run equal number of v-nodes. So each node is responsible for 1/(number of nodes) or (number of partitions) / (number of v-nodes). So if 2 nodes define a 16-partition cluster, each node would run 8 v-nodes.
• Writes (Puts)
  • Any node may be chosen as coordinator for the Write request
  • Coordinator node figures out the v-node responsible for the partition where the key needs to go.
  • Coordinator sends Write request to that v-node as well as next N-1 partitions in the ring, where N is a configurable parameter that defines how many copies of the value need to be created.
  • Write request may also specify that at least W (=< N) of the v-nodes respond with success, and that DW (=< W) of the W nodes respond with success only after durably storing the state.
• Reads (Gets)
  • Any node may be chosen as a coordinator for the Read request
  • Coordinator node figures out the v-node responsible for the partition for the key
  • Sends request to v-node, as well as next N-1 nodes
  • Request can also specify R (=< N) nodes that must reply before a response is returned.
• Ring state propagation
  • Consists of things like arrival and departure of nodes on ring
  • Done using Gossip protocol
• Eventual Consistency
  • When a object is added it is tagged with a vector clock specifying its initial version
  • For each update, the clock is updated in such a way that the system can compare two versions of an object and determine how the two objects are related (direct descendant, common parents, unrelated)
  • To compare object versions, a Merkle tree is used
• Failure handling is done using the same hinted replicas and hinted hand-offs approach as described in the Dynamo paper.
• Storage model – pluggable:
  • File based in a on-disk nested directory structure
  • Erlang gb_trees based (http://www.erlang.org/doc/man/gb_trees.html)
  • Volatile ETS tables (hash based data storage and access – see http://www.erlang.org/doc/man/ets.html)
  • On-disk DETS tables (see http://www.erlang.org/doc/man/dets.html)
  • Osmos tables – uses the Osmos file storage system. Useful for write-intensive systems.
• Queries
  • Map-reduce model
  • Map operations run local to the data on the hash ring – can be run in parallel
  • Reduce operations take inputs from the preceding phase and reduce (typically perform an aggregate operation) the input. This cannot be parallelized
• License: Apache 2.0
• Production use: No names mentioned, except that the FAQ says that “Riak has robustly served the needs of multiple revenue-generating applications for nearly two years now.”

5.4 MongoDB

• http://www.mongodb.org/
• Written in C++
• Language bindings (drivers): C, C++, Java, JavaScript, Perl, PHP, Python, Ruby. Also community provided support for C#, F#, Erlang, Groovy, etc.
• Data Model
  • Collections – similar to Domains in Amazon SimpleDb – a bucket to hold together similar documents
  • Key-Value, with value being binary serialized JSON (BSON)
    • 4 MB limit on a BSON object
    • Large object support via GridFS
  • B-Trees used for indexes. You specify the fields on which to index using a function called db.things.ensureIndex() that takes the field as a parameter.
• Storage: Uses memory mapped files. So caching is controlled by the OS VMM
• Writes
  • In-place updates
  • Provides partial updates – you can update the value without sending a full row update.
  • Single document Atomic updates. Atomic batch updates possible thru db.eval() but may not be supported with partitioned data

  <
  br />

• Queries
  • Provides a JSON style based syntax to pick values from inside documents
  • Support for conditional operators, regular expressions, etc.
  • Supports forward-only cursors
  • Query optimizer is not cost-based, instead multiple query plans are tried and the one that works best is picked.
• Batch Operations
  • Supports Map-Reduce over a Collection
• Replication:
  • Master-slave
  • Replica pairs – automatically figure out master and slave roles
  • Master-Master: Not recommended. Eventually consistent (how?)
• Partitioning:
  • Partitioning In alpha stage.
  • Data sharded by Collection with order preservation
  • A shard consists of one or more servers replicating using an enhanced version of replica pairs
  • Shards deal with data in units called Chunks.
    • A chunk is a contiguous range of data from a collection with a max limit of 50 mb. After that a chunk splits into two chunks
    • Data migrates from one shard to another in chunks (in case of shard having excess data, or having nearby shards)
• License: AGPL 3.0
• In Production use at: Sourceforge, Github, EA, and several others

6. Column-Family Stores

6.1 BigTable

• http://labs.google.com/papers/bigtable.html
• Internally used at Google. Exposed to general public thru Google App Engine
• Building Blocks
  • Google File System – a distributed file system. Provides raw storage
    • Files broken into chunks (typically 64 mb)
    • Each chunk is replicated across 3 machines for safety.
      • A heuristic here is that one of the replicas tries be on the same rack as the original and the other two replicas somewhere else
    • Chunk Servers – responsible for storing chunks
    • Data transfer happens directly between clients and chunk servers
    • Master – responsible for metadata in the file system
  • The storage file format is called SSTable (sorted strings table)
    • Persistent, ordered, immutable map of keys to values with both keys and values being arbitrary byte strings
    • Operations to look up the value specified with a key and to iterate over key/value pairs in a given key range
    • Optionally, an SSTable can be completely mapped into memory
    • Immutability of SSTables:
      • Means no synchronization required during file access.
      • Makes removing permanently deleted data a garbage collection exercise (happens in a major compaction – see below)
  • Scheduler
    • Schedules jobs on machines
    • Watches for failures and re-schedules if required
  • Chubby Service – Distributed lock / file / name manager
    • Coarse grained lock – can store small amount of data in lock
    • 5 replicas, 1 master. Need majority vote to be active. Uses Paxos to keep replicas in sync
    • Provides a namespace that consists of directories and small files. Each file / directory can be used as a lock, and reads and writes to a file are atomic.
    • Each chubby client maintains a session with a chubby service. There is a lease time which needs to renewed.
    • Clients can register callbacks on Chubby files and directories for notification of changes / session expiration
  • Optional Services used by BigTable applications (but not used by BigTable itself)
    • Map-Reduce: Batch processing – clients often use this to read / write BigTable data
    • Sawzall: to support execution of client provided scripts in the server space for transformation, filtering and summarization
• Data Model
  • Multi-dimensional map (map of maps)
  • Data organized into tables. A table is an entity that holds related data
    • Each record is identified by a row key
    • Each row has columns. Columns here should be thought of as attributes of a row. Not all rows would have the same columns
    • Intersection of a row and a column creates a cell
    • A cell has versioned data based on timestamp. So a single cell may holds multiple versions.
    • It is convenient to organize attributes. Thus columns are grouped into column families. A column family can be thought of as a namespace for a set of related attributes.
  • So the dimensions of the multi-dimensional map are:
    • Row key: Uniquely identifies a datum (arbitrary byte string)
    • Column-family: A grouping of attributes – a namespace for a set of related attributes.
    • Column: A single attribute.
    • Timestamp: Denoting the time when the value was changed.
      • Different versions are stored in decreasing order of timestamp, so most recent versions can be read first
      • Client can specify that only last n-revisions of cell should be kept, or only values written in the last n-days should be kept
  • Transactional access possible to any column within a single row
    • Can perform atomic read-modify-write sequences on data stored under a single row key
    • Transactions across row keys not supported
    • Batch operations across row keys are possible but are not atomic
• Tablets
  • Data is sorted lexicographically by Row key
  • Row range for a table is dynamically partitioned.
  • A row range is called a Tablet. So you can describe a tablet in terms of a start row key and an end row key
  • One tablet = 100 to 200 mb
    • Tablets can be split based on tablet size or load
  • A tablet server may end up serving anywhere from 10 to 1000 tablets (typically hundreds).
    • While each tablet consists of contiguous data, a tablet server would pick up tablets spread across the entire data set and not data that is related. This helps allevi
      ate hot spots since load gets spread evenly
    • The high ratio of tablets to tablet servers gives very fast recovery since if a machine that was serving 100 tablets fails, 100 machines can each pick up 1 tablet from the failed machine making recovery highly parallelized
    • Also gives fine-grained load balancing – you can migrate tablets away from an overloaded machine.
  • Servers are further grouped into cells
    • A cell is a collection of servers. Most cells have 10-20 servers
    • Some cells have as many as thousands of servers managing several hundred TB of data
• A typical cluster consists of
  • Commodity Intel based PC hardware with each node running
    • Google’s version of Linux
    • GFS Chunk server – for raw reads and writes
    • Scheduler slave process – runs jobs
    • Tablet server – serves BigTable read / write requests
    • Some nodes may also run a BigTable master which is responsible for meta-data requests (create a new table) and load monitoring / balancing
  • GFS Master
  • Cluster scheduling master – talks to the scheduler slave process on each node to startup jobs
  • Lock service – used for electing BigTable masters and for bootstrapping the tablet lookup (below)
• Locating Tablets
  • To figure out which server is serving which tablet (row key range), this mapping info is kept in special metadata tables (which in turn can split into tablets)
  • Three level hierarchical lookup with bootstrap provided by Chubby
    • Chubby file points to a root metadata tablet – this tablet is never split
    • This tablet points to other metadata tablets
    • Each 2nd level metadata tablet points to app data tablets
    • Each metadata row is an encoding of tablet’s table id and end row key, and takes approx 1 kb
    • With a 128 mb limit on metadata tables, this scheme can address upto 2^34 tablets (or 2^61 bytes in 128 mb tablets)
  • The lookup is aggressively pre-fetched and cached by clients so most queries end up going straight to servers
    • Empty cache: There are 3 network round trips including one read from Chubby
    • Stale cache: could take up to  round trips since stale entries are discovered via misses
• Tablet Assignment
  • Each tablet assigned to one server at a time. Master keeps track
  • When a tablet gets unassigned, the Master asks a Tablet server with available capacity to take over the tablet
  • Tablet assignment uses Chubby
    • On starting, a tablet server creates and acquires an exclusive lock on a uniquely named file in a specific Chubby directory called Servers
    • Master monitors this directory to discover tablet servers
    • If a tablet server loses its exclusive lock it stops serving the tablets
    • Tablet server may try and re-acquire the lock if the file still exists, however if the file is gone, the tablet server kills itself
  • Master asks each tablet server periodically for the status of its lock
    • If tablet server reports a loss, or if master fails to connect to tablet server, the master tries to acquire an exclusive lock on the tablet server’s file
    • If master is able to acquire lock, it means Chubby is alive. So master deletes the file so that the tablet server can never serve again, and the master moves all tablets assigned to the tablet server to the set of unassigned tablets
    • If master is unable to reach Chubby, it kills itself
• Writes
  • When a write request goes to a tablet server, it checks it for well formedness, and authorization (Chubby maintains a list of permitted writers)
  • Valid mutations are written to a commit log (grouped for small mutations)
  • After the write has been committed, its contents are inserted into a sorted in-memory buffer called memtable. From here, updates keep going to a sequence of SSTables as they get older
• Reads
  • Similar checks as for a write request – well formedness and auth
  • Read op executed on a merged view of SSTable sequence and memtable
• Tablet Recovery
  • Maybe required if a Tablet server dies
  • Tablet server reads its metadata from the MetaData table – list of SSTables and set of redo points which point to commit logs
  • Server reads indices of SSTables into memory and reconstructs memtable by applying all updates that have been committed since redo points
• Compactions
  • Minor Compactions:
    • As writes occur, memtable grows till a threshold. Is frozen. New memtable created. Frozen memtable converted to SSTable and written to GFS.
    • Shrinks memory usage of tablet server
    • Reduces amount of data that needs to be read from Commit log during recovery
  • SSTable Compactions
    • As minor compactions occur, new SSTables get created. This can lead to a Read operation slowing down as it may need to merge data from multiple SSTables
    • So periodically a merging compaction runs which reads a few SSTables and the Memtable and writes out a new SSTable
    • This does not remove special deletion entries (used to suppress deleted data)
  • Major Compactions
    • From time to time BigTable runs a compaction that rewrites all SSTables into exactly one table is. This is called a Major compaction
    • During this compaction deleted data / deletion entries are removed.
    • Required for claiming resources
• Refinements
  • Locality Groups: Are used to group together parts of data that have similar usage characteristics.
    • Client can group multiple column families into a locality group
    • Separate SSTable generated for each locality group
    • Locality group can be marked as being in-memory (lazy loaded). BigTable itself uses it for the Location column-family in metadata table.
  • Compression: Clients can specify whether or not SSTables for a locality group are compressed or not, and which compression algorithm to use
  • Caching: Tablet servers use two levels of caching:
    • Scan cache – higher level. Caches key-value pairs returned by SSTable interface to Tablet server code. Useful for apps that tend to read the same data repeatedly
    • Block cache – lower level. Caches SSTable blocks reads from GFS. Useful for apps that read data close to data they recently read

6.2 Cassandra

• http://incubator.apache.org/cassandra/
• Combines the distributed architecture of Dynamo with BigTable’s column-family data model
• Written in Java. Thrift based interface. High-level libraries available on Ruby, Perl, Python, Scala and Java
• Data Model:
  • Multi-dimensional map indexed by a key like BigTable.
    • Each application creates its own key-space (table in BigTable)
    • Key – a name for a record. Can be an arbitrarily long string. Indexed by Cassandra
    • Column – an attribute of a record. Smallest datum you can get hold of. This is timestamped.
    • Column-family: Grouping of columns. Similar to a relational table.
    • Super-Colum
      ns: A list of columns
    • A column-family can either contain columns or super-columns, but not both. Coumn family containing super-columns is called super-column-family
    • The way to get to a piece of data is: KeySpace.ColumnFamily.Key.[SuperColumn].Column
  • Sorting
    • Data is sorted at write time (unlike relational)
    • Columns are sorted within their row by column-name. The sorting provider is pluggable
• Partitioning: Similar to Dynamo
  • Consistent hashing using an order preserving hash function.
  • However uses the Chord approach to load balancing rather than Dynamo’s v-node approach
• Replication
  • Same concept of coordinator nodes and preference lists as Dynamo
  • Various replication policies: Datacenter aware, Rack-aware, Rack-unaware
  • Rack-unaware approach is same as Dynamo (replicate to N-1 nodes)
  • Rack aware and Datacenter aware use a more intricate algorithm which involves a leader (chosen using Zookeeper) that maintains the N-1 replicas invariant. This is apparently not there in Apache Cassandra.
• Membership: Membership based on Scuttlebutt – anti-entropy Gossip based mechanism. Same concept of explicit membership changes as Dynamo
• Failure detection: Uses a modified version of Φ Accrual Failure Detector which gives a probabilistic value for each monitored node. This apparently is fairly accurate and more representative of network conditions.
• Failure Handling: Same concept of hinted replicas and hinted hand offs as in Dynamo
• Persistence:
  • Relies on local file system (unlike BigTable that uses GFS)
  • Storage structure and approach is similar to BigTable: SSTables, Memtables, Commit logs, Compaction, Bloom filters, etc.
• Writes
  • Similar to the BigTable approach of writing to commit log for durability and recoverability, followed by update to Memtable
  • Dedicated disk on each machine for commit log makes the writes sequential and thus maximizes thruput
  • When memtable crosses a threshold (out of space / too many keys / client provided time duration), it gets written to two files:
    • Data file – SSTable
    • Index File – key/offset pair
  • No seeks – always sequential, thus quite fast
  • Atomic within Columnfamily
• Reads
  • Similar approach as Dynamo for figuring out which nodes will serve, read-repair, etc.
  • At a storage level, approach is similar to BigTable: read from memtable + SSTable sequence
• License: Apache 2
• In Production at: Facebook, Digg, Rackspace