Consistent Hashing

Hashing is a common method of mapping a key to a location. This is useful for many things, but in more relevant terms, this can be used to map keys to a server with great effect. Simple hashing use a Key mod N algorithm, where K is the number of keys and N is the number of slots or servers. This ensures that keys are mapped evenly across N slots. The problem with this algorithm is that adding or removing a slot or server would require a complete rehash of all the keys. And in case of huge data set, it is ideally not feasable to rehash and re-distribute the keys.

Consistent Hashing is a specific implementation of hashing that is well suited for many of today’s web-scale load balancing problems. Consistent Hashing is used particularly because it provides a solution for the typical “K mod N” method of distributing keys across a series of servers. It does this by allowing servers to be added or removed without significantly upsetting the distribution of keys, nor does it require that all keys be rehashed to accommodate the change in the number of servers. When using consistent hashing, only K/N keys need to be remapped on average.

Implementing Consistent Hashing is done by mapping keys and servers onto edge of a circle. All servers are mapped on to a series of angles around a circle. Each key is also hashed onto the circle. Each hashed server contains all keys between itself and the next clock-wise server hashed onto the circle. The bucket where each item should be stored is chosen by selecting the next highest angle which an available bucket maps to. So, each bucket contains resources mapping to an angle between it and the next smallest angle. If a bucket becomes unavailable, the keys being mapped to that bucket get mapped to the next highest bucket (or the next bucket in the circle). So, only keys which were in the bucket which became unavailable is lost. Similarly when a bucket is added, the keys between the new bucket and the next smallest bucket is mapped to the new bucket. Keys which should be associated with the new bucket and were stored previously will become unavailable.

As shown in Figure 1, Keys 1, 2, 3 and 4 map to slots A, B and C. To find which slot a key goes in, we move around the circle until we find a slot. So here key 1 goes into slot A, 2 goes into slot B and 3 goes into slot C, key 4 goes into slot A again. If C is removed, key 3 would belong to slot A.

If another slot D is added as shown in Figure 2, it will take keys 3 and 4 and only leave key 1 belonging to A.

Fig 1: Keys distribution with Consistent hashing

Fig 2: Keys re-distribution with Consistent hashing

Database Consistency

A database system is said to be in a consistent state if it satisfies all known integrity constraints. Integrity is defined as `the accuracy or correctness of data in the database`. There are two famous types of integrity constraints:

1. Entity integrity constraints (for example, no primary key value can be null)
2. Referential integrity constraints (a field in one table which refers to another table must refer to a field that exists in that table).

A database is in a correct state if it is both consistent and if it accurately reflects the true state of affairs in the real world. A database that is in a correct state will always be consistent. But consistent does not necessarily mean correct. A consistent database can be incorrect.

Different types of consistency exists:

Strong consistency means, that all processes connected to the database will always see the same version of a value and a committed value is instantly reflected by any read operation on the database until it is changed by another write operation.

Eventual Consistency is weaker and does not guarantee that each process sees the same version of the data item. Even the process which writes the value could get an old version during the inconsistency window. This behavior is usually caused by the replication of the data over different nodes.

Read-your-own-writes consistency, some distributed databases can ensure that a process can always read its own writes. For this, the database has to connect the same process always to nodes that already store the data written by this process.

A subtype of read-your-writes consistency is session consistency. Thereby it is only guaranteed that a process can read its own written data during a session. If the process starts a new session, it might see an older value during the inconsistency window.

Another variant of eventual consistency is monotonic read consistency, which assures that when a newly written value is read the first time, all subsequent reads on this data item will not return any older values. This type of consistency allows the database to replicate newly written data, before it allows the clients to see the new version.

Most of the NoSQL databases can only provide eventual consistency.

Smarty with symfony 1.4

For last more than two years we have been using symfony 1.0. We used symfony 1.2 also for some of the projects. Since it is official now that symfony developers are not going to support 1.0 and 1.2 version, I thought to give symfony 1.4 a try for one of my new project.

After installing symfony 1.4.6 and setting some config parameters. I was able to run my first page successfully. Now it was turn to enable Smarty plugin. I tried to install sfSmartyViewPlugin that I used with version 1.2. But I came to know that symfony 1.4 does not support sfSmartyViewPlugin. I googled and found that there is a sfSmarty3Plugin that should be used instead.

It took me a long time to make this plugin work since I was not able to find enough information on how to configure this plugin on net.

Here I am giving the steps that I followed in case someone needs it:

Prerequisite:

- sfSmarty3Plugin
- Smarty3

1. extract sfSmarty3Plugin in plugin/ folder

2. vi config/ProjectConfiguration.class.php and add
$this->enablePlugins('sfSmarty3Plugin');
in the setup function

3. vi plugins/sfSmarty3Plugin/config/settings.yml and set

allow_php_tag: true #TO ALLOW THE OLD STYLE
lib_dir: lib/vendor/smarty/libs # path to the Smarty.class.php
left_delimiter:'{' # change it if you do not use default one
right_delimiter: '}' # change it if you do not use default one

4. vi config/module.yml

  default: # For all environments
    enabled: true
    is_internal: false
    view_class: sfSmarty
    partial_view_class: sfSmarty

5. In module.yml of each app

  default: # For all environments
    enabled: true
    is_internal: false
    view_class: sfSmarty
    partial_view_class: sfSmarty

6. In app.yml in each of app

  # default values
  all:
    sfSmarty:
      class_path: lib/vendor/smarty/libs # path to the Smarty.class.php
      template_extension: .tpl
      template_security: false

7. rename layout.php to layout.tpl

8. Make changes in settings.yml related to smarty configs

Memcache

Caching helps, Everybody knows it. The performance of a web site can be improved by a great deal with proper caching. Caching can be done at various levels - browser level, proxy level, server level, database level etc. Here, I would be talking about a system known as memcache that helps cache at both server & database level. Memcache is designed for fast storing and retreiving of information. Its a system which is distributed and which stores information in memory only.

Memcache was developed by Danga interactive, according to them memcache is 'A high performance, distributed memory object caching system'. Memcache has a daemon and client apis for various languages. So you have to run the memcache daemons on servers where free memory is available and use client apis to set and get data from memcache daemon. Data sent by the client apis are serialized and stored corresponding to a key provided by the clients in memcache.

But there are some shortcomings with its distributed architecture. If you have 3 memcache daemons running and you are distributing data over those daemons and if one of those daemons goes down, you simply loose data set on those servers. What also happens is that since the number of servers have changed, the distribution logic of data divides data among these 2 daemons. And later when you bring up the third daemon, the distribution logic now does not know where the data is which were set while one of the daemons was down.

You can download it from http://www.danga.com/memcached/. Download the tar.gz source file. Untar it, go to memcached directory and compile it using ./configure , make and make install.

Now run the memcached binary in daemon mode and assign it some amount of memory. To see a list of all available options run memcached -h, and it will list you all the available options. For example to start memcached in daemon mode with 64 MB RAM, which listens on localhost port 11211, run the following command

./memcached -d -m 64 -l 127.0.0.1 -p 11211

This will start the server. Now clients can connect to this server and store data over there. There are apis available for different languages (perl, python, ruby, java, C# and C) that allow you to connect to memcached daemon and store/retrieve variables, arrays and objects from it. One point to note here: Objects stored in memcache are language dependent. If you extract an object using java api which was stored by a php api. You would not be able to parse it.

Design Patterns : The Singleton Pattern

Why Singleton?

Sometimes we want just a single instance of a class to exist in the system. For example, we want just one database manager instance. We need to have that one instance easily accessible and we want to ensure that additional instances of the class can not be created.

What is Singleton Pattern

The singleton is a useful design pattern that is used to restrict instantiation of a class to one object.  It ensures a class has only one instance and provide a global point of access to it.  In the singleton pattern at any given point only a single instance of the Singleton Class is active. All instantiation of the Singleton Class references the same instance of the Class. The pattern also provides a global point of access to the sole instance of the class.

The Sample Code

Class Singleton
{
//Class Members
private static $instance;

//The Constructor
protected function Singleton() {}

//Static method for creating the single instance of the Constructor
public static function getInstance()
{
// create a new instance if not already done
if( $instance == null )
$instance = new Singleton();

// return the instance of the Singleton Class
return $instance;
}
}

Benefits of Singleton Pattern:   

• Instance control: It ensures that all objects access the single instance, by preventing other objects from instantiating their own copies of the Singleton object.
• Flexibility: The class has the flexibility to change the instantiation process. Because it controls the instantiation.
• As Global variables: Singletons are often preferred to global variables because -   
  • They don't pollute the global namespace with unnecessary variables.
  • They allow lazy allocation and initialization, where global variables in many languages will always consume resources.

Drawbacks of Singleton Pattern:   

• It is usually not recommended to use global objects, since it is hard to test them and the developer has to make assumptions regarding the application and how they will be used.
• Using the singleton pattern makes the classes tightly coupled instead of loosely coupled, meaning that you can only test a few classes together rather than each of the classes at a time, as you should.

When should you use the Singleton design pattern:

Here’s a singleton recommended check list:   

• Singleton should be used in cases where only one object is needed to coordinate actions and/or events across the application.
• The application will always use the object in the same way.
• It doesn’t really matter to the client what’s going on in the rest of the application, meaning that the singleton object is independent.

If your requirement confirms all these points, then it’s a good candidate to use the singleton pattern.

OO Design Principles

Here are some important principles of Object Oriented Design

   
• Identify the aspects of your application that vary and seperate them from what stays the same.
   
• Take what varies and encapsulate it so it won't affect the rest of the code.
   
• Program to an interface, not an implementation.
   
• Favour composition over inheritance.
   
• Strive for loosely coupled designs between objects that interact.
   
• Classes should be open for extension but closed for modification.
   
• Depend on abstractions, do not depend on concrete classes.
   
• Talk only to your immediate friends.
   
• A class should have only one reason to change.

An Introduction to Design patterns

What are design pattrens

Design patterns are commonly defined as time-tested solutions to commonly occurring problems in software design. Design Patterns aren't invented they are discovered. They don't give you code, they give you general solutions to design problems. A design pattern is not a finished design that can be transformed directly into code. A design pattern provides a description for how to solve a problem that can be used in different situations.

Design patterns are grouped mainly into three categories:

Creational patterns:

Creational Patterns deals with object creation mechanisms, they try to create objects in a way that is suitable to a given situation. They are also used for dynamically selecting the class of created objects. Some examples of creational pattrens are

• AbstractFactoryPattern
• BuilderPattern
• FactoryMethodPattern
• SingletonPattern

Structural patterns:

Structural Patterns are those patterns that helps realizing relationships between entities by identifying simple ways for it, these patterns use various language mechanisms for assembling objects and code structuring. Some examples of structural pattrens are

• AdapterPattern
• CompositePattern
• DecoratorPattern
• FacadePattern
• IteratorPattern

Behavioral patterns:

Behavioral Patterns are patterns that identify common communication patterns between objects and realize these patterns. They usually describe how a group of objects collaborate to perform some task that no single object can perform alone. Some examples of behavioral pattrens are

• CommandPattern
• IteratorPattern
• ObserverPattern
• StatePattern
• StrategyPattern
• TemplateMethodPattern
• VisitorPattern

Benefits of Design patterns:

• Design Patterns provide a way to solve issues related to software development using a proven solution.
• Design patterns helps to prevent subtle issues that can cause major problems.
• Design Patterns facilitates the development of highly cohesive modules with minimal coupling.
• Design Patterns isolate the variability that may exist in the system requirements, making the overall system easier to understand and maintain.
• Design Pattern describes the problem, the solution, when to apply the solution, and its consequences.
• Design Patterns also gives implementation hints and examples.
• Design Patterns improves code readability for coders and architects who are familiar with the patterns.
• Design Patterns allow programs to share knowledge about their design.

Stop bots from spamming : Old style CAPTCHA - Alternatives or replacements

Old style CAPTCHAs are pretty much broken. So what else we can use to replace it. Given below are some alternatives to old style CAPTCHAs.

1. reCAPTCHA - It is a free CAPTCHA service that helps to digitize books, newspapers and old time radio shows. They deliver CAPTCHAs that are proved to be unreadable by OCR and donate the human processing to a charitable cause, preserving out of copyright books for future generations.

2. CSS hidden field - Add a text input field to your form and give it a name that makes sense. Then with some CSS hide the table row or div that the input field is in. The bots should fill it in, add some code that checks that the hidden field was not filled in, and if you find this field filled in, you can quit execution right there. Make sure to label this so that people with screen readers can understand not to fill it in.

3. Work out the time that it took for the form to be submitted - In your form, add a hidden variable and set its value to the time stamp of when the form was loaded. Then, once the form has been submitted, get a new time stamp value and compare the two values. If the new value is less than say about 5 seconds (or the time you estimate it will take a human to fill in your form, remembering that spam bots will do it almost instantaneously) then you can return to the form with a error message stating that the form was submitted in too short a time period.

4. Give the user simple Challenge questions like - What are the total number of syllables in the American President's full name. OR, put a simple math equation at the bottom of the form like (2 + 4 - 1 =). Remember the fact that you would need to make the questions random.

5. Use music. Play the music and give the user multiple choice answers.

6. After filling the form have the users go to another link and copy and paste an constantly changing image into a box. This would be similar to an RSA token but without the hardware.

In the end, nothing is perfect but the end result is something that is accessible and will keep your site safe.

Php scripts : problem with whitespace

Recently while working on some project I faced a strange problem. In one of our app we were trying to implement and call a service using hessian. But somehow we were getting malformed reply for all the requests. We checked all the scripts and there were no problems in any of them. Finally, after a lot of efforts we got the problem. The problem was very simple, in one of the scripts there were some blank lines before the php start tag (<?php)

Leaving whitespaces (spaces/line breaks etc) before or after php scripts can be problematic and can result in unexpected or undesirable behaviour. Since these whitespaces will be echoed to the browser along with the normal output, It can break any script attempting to send headers (e.g. initializing session, sending content type, etc.) and can distort the web page layout.

Here is a simple php script that will scan php files in a given directory (and its subdirectories) and will remove all the whitespaces.

<?php
$maindir = "/path_to_the_project_dir";

define("PRE", "/^[\n\r|\r\n|\n|\r|\s]+<\?php/");
define("POST", "/\?>[\n\r|\r\n|\n|\r|\s]+$/");

clearstatcache();

if(scan_dir( $maindir, "removeWSpace", true ) === false)
{
echo "'{$maindir}' is not a valid directory\n";
}

function scan_dir( $maindir, $callback, $recursive = true )
{
$dh = @opendir( $maindir );
if( $dh === false)
return false;

while( $file = readdir( $dh ))
{
if( "." == $file || ".." == $file )
{
continue;
}
call_user_func( $callback, "{$maindir}/{$file}" );
if( $recursive !== false && is_dir( "{$maindir}/{$file}" ))
{
scan_dir( "{$maindir}/{$file}", $callback, $recursive );
}
}
closedir( $dh );
return true;
}

function removeWSpace( $path )
{
if( !is_dir( $path ) && substr($path, -4) == ".php")
{
$fh = file_get_contents($path);
$fh = preg_replace(PRE, ' 0 || $c2 > 0)
{
if(file_put_contents($path, $fh))
echo $path . " -- modified \n";
}
}
}

?>

Convert word/doc files to html using openoffice macros

As many of you know OpenOffice.org has a powerful support for plugins or Macros. These macros allow you to add a lot of additional functionality to the application. You can also use this feature to write a command line tool to convert a .doc or .odt file to a .html file. Writing this tool is a two step process:

Step 1: Write a micro to covert a .doc file to .html

Start up OpenOffice.org Word Processor. Then from the Tools menu, select Macros, Organize Macros, OpenOffice.org Basic. A window will popup. Navigate to My Macros, Standard, Module1. Edit the module to include the following code:

REM  *****  BASIC  *****

Sub ConvertWordToHTML(cFile)
cURL = ConvertToURL(cFile)
dim args(0) as new com.sun.star.beans.PropertyValue
oDoc = StarDesktop.loadComponentFromURL(cURL, "_blank", 0,
Array(MakePropertyValue("Hidden", True),))
cFile = Left(cFile, Len(cFile) - 4) + ".html"
cURL = ConvertToURL(cFile)

' Save the document using a filter.
args(0).Name = "FilterName"
args(0).Value = "HTML (StarWriter)"
oDoc.storeToURL(cURL, args())
oDoc.close(True)
End Sub

Function MakePropertyValue( Optional cName As String, Optional uValue )
As com.sun.star.beans.PropertyValue
Dim oPropertyValue As New com.sun.star.beans.PropertyValue
If Not IsMissing( cName ) Then
   oPropertyValue.Name = cName
EndIf
If Not IsMissing( uValue ) Then
   oPropertyValue.Value = uValue
EndIf
MakePropertyValue() = oPropertyValue
End Function

Now save it and exit from OpenOffice.org.

Step 2: Create a shell script to execute this macro from command line

Create a shell script, called doc2htm in /usr/local/bin with the following code:

#!/bin/sh
DOC=$1                                                    
/usr/bin/oowriter -invisible
"macro:///Standard.Module1.ConvertWordToHTML($DOC)"

Thats it. Now you can run the script from command line like:

$ doc2htm /path_to_the_doc_file/file_name.doc

and you will get file_name.html in the same directory where the original doc file resides.