Logging Input/Output of Apache2

If you want to log all input received and output sent by Apache to its error.log then you are on the right post. We will use "mod_dumpio" which allows us to log the input/output of Apache to its error log. Below are the steps you can follow in order to achieve the desired logging:

Enable mod_dumpio
To enable mod_dumpio module for apache using the following command:

sudo a2enmod dump_io

Module configuration

Next step is to configure this module. To do this open apache's configuration file "apache2.conf":

sudo nano /etc/apache2/apache2.conf

Now add the following configuration options in the configuration file:

DumpIOInput On

DumpIOOutput On

DumpIOLogLevel debug

DumpIOInput enables Apache's input logging whereas DumpIOOutput enables it's output logging. DumpIOLogLevel specifies the level of information to be logged. You can find all levels by taking a look at this link --> http://httpd.apache.org/docs/2.2/mod/core.html#loglevel

Restart Apache

Now you need to restart apache using the following command:

sudo service apache2 restart

or 

sudo /etc/init.d/apache2 restart

Now you can open up the apache error log or tail on it to see Apache input and output logs. Use the following command to tail on the log:

sudo tail -f /var/log/apache2/error.log

Note:

If for some reason you do not see apache's input/output logs in the error.log file, you may want to look at any other config file that might set apache's log level. For example in my case I had a sites enabled module in apache turned on and I had a site configured for that. The location was "/etc/apache2/sites-enabled/xyz". Where xyz may be your site name. Open this file and see if the LogLevel set in this file is different from the DumpIOLogLevel that you just specified for the dump_io module. The values should be the same or you wont see any logging.

Installing Percona Server 5.5 on Ubuntu 10.04 Lucid

Installation

Debian and Ubuntu packages from Percona are signed with a key. So before using the repository, you should add the key to apt. To do that, run the following commands:
gpg --keyserver hkp://keys.gnupg.net --recv-keys 1C4CBDCDCD2EFD2A
gpg -a --export CD2EFD2A | sudo apt-key add -
Add the following lines to '/etc/apt/sources.list':

deb http://repo.percona.com/apt lucid main
deb-src http://repo.percona.com/apt lucid main

If you are using some other distribution, then you can substitute your distribution name with 'lucid'. To get the name of your distribution you can run the following command:

cat /etc/*-release

This command will show you the distribution information. Your distribution name will be the value of 'DISTRIB_CODENAME'

Now update the local cache:
apt-get update

To install Percona Server 5.5 use the command:

sudo apt-get install percona-server-server-5.5

Kudos! Percona Server 5.5 will now be installed.

Note: Percona Server 5.5 does not come with a default configuration file (i.e my.cnf). To figure out where you can put my.cnf file your need to run the following commands:
which mysqld --> /usr/sbin/mysqld
/usr/sbin/mysqld/ --verbose --help | grep -A 1 'Default options'
The output will be some lines. Among those lines you will see text like 'Default options are read from the following files in the given order: /etc/my.cnf /etc/mysql/my.cnf ........'. You can put the 'my.cnf' file in any of these directories but make sure that there is no config file in the directories that will be looked up before the directory you choose, else your my.cnf file will not be read. I personally prefer putting the 'my.cnf' file in '/etc/mysql/my.cnf'

In order to force MySQL not to run automatically when the server starts run the following command:

sudo update-rc.d -f mysql remove 
You will now need to start MySQL manually when you start or reboot your server.

Some post-installation notes and points

Using a custom data directory and log directory for MySQL:

I generally put MySQL data files on a RAID-10 array and MySQL log files on a logical volume (No RAID configuration), so I explicitly mention data and log directories in the 'my.cnf' file. Below is how i specify MySQL data directory and MySQL log file directory:

Under  [mysqld] 

# data file directory
datadir = /var/mysql-data 

#log file directories
log_error = /var/mysql-logs/mysql-error.log
slow_query_log = 1
slow_query_log_file = /var/mysql-logs/mysql-slow.log
general_log = 1

general_log_file =  /var/mysql-logs/mysql-query.log  

Now if you do something like this, you need to keep somethings in mind. 

If you change the 'datadir' to a location other than MySQL's default data directory, you need to move folders 'mysql' and 'performance_schema' from '/var/lib/mysql/' to your new data directory. You can use the following command:

sudo mv /var/lib/mysql/mysql /var/mysql-data

sudo mv /var/lib/mysql/performance_schema /var/mysql-data

Note: Make sure the folder '/var/mysql-data' or whatever folder you are using as MySQL data folder has the right owner. That is owner should me 'mysql' and owner group should be 'mysql' too. You can change the owner using the following command:

sudo chown mysql:mysql /var/mysql-data

The same instructions apply to MySQL log folder, in-case you decide to use a different folder to store the log files.

Using a custom location to store 'socket' and 'pid_file'

Suppose you want to specify a custom location to store MySQL's socket and pid like in the configurations below:

Under [mysqld]

socket = /path/to/mysql/mysql.sock
pid_file =  /path/to/mysql/mysql.pid
Under [client]

socket = /var/lib/mysql/mysql.sock 

Make sure you have the right ownership of the folder containing both the files (mysql:mysql). Secondly, you also need to alter the 'debian.cnf' file which you can find in '/etc/mysql/debian.cnf'. Open 'debian.cnf' file and change the 'socket' location to the location you set in 'my.cnf'. If you do not do that, MySQL fails to start and stop.

Start/Stop/Restart MySQL

To start/stop/restart MySQL using the following command:
service mysql [start or stop or restart]
or 
/etc/init.d/mysql [start or stop or restart] 

Running Ubuntu Server in full screen mode - VirtualBox

I wanted to have Ubuntu Server in Full Screen mode or at-least wanted to increase its resolution while I was running server instances on Virtualbox. Below are the steps I took to change the resolution:

• Open "grub.cfg" file. You can find this file in "/boot/grub/grub.cfg"

sudo vim /boot/grub/grub.cfg

• Change the following assignments:

Change "set gfxmode=640x480" to "set gfxmode=1024x768"

Change "set gfxpayload=640x480" to "set gfxpayload= 1024x768"

• Reboot your Ubuntu Server

Note: You can change the resolution from 1024x768 to any desirable resolution. I just used it as an example.

Amazon EC2 & Scalr – Roles, Instances, Regions, Availibility Zones & ELB

In this blog I will briefly describe some terminologies that you will frequently encounter when deploying an application on Amazon EC2 and while using Scalr for application management in Amazon EC2. I will then describe how these objects work together in harmony. To gain a better understanding of their working we need to first understand what they mean.

Role

A role is a machine image and as the name indicates, it serves a specific purpose of an application in the cloud. Typically a role is an abstraction of an instance (defined next). A role helps in defining a template which consists of a set of installations, needed to fulfil a specific function of an application. For example, a typical application will have web servers, cache servers and data servers. All three can serve as a role (Apache2 + PHP + APC Role, Memcached Role and MySQL Role). Roles are generally assigned to a farm (a set of instances working together to accomplish a task) and have their own security groups. For example, an application role can be made public while caching and database roles should be kept private and internal to the network.

Instances

Unlike a Role, that does not have any physical existence, an Instance is a physical existence of a Role. There can be multiple instances running for a particular role. Roles are templates and Instances are actual implementations of those templates.

Regions

Amazon EC2 infrastructure is spread across the globle in different regions. These regions are geographically seperated and provide an opportunity to run an application in different regions thus making an application fault tolerant. Also application can serve requests to the clients from the closest region. Regions are completely isloated from each other. Following are the regions available in Amazon EC2:

US East (Northern Virginia)

US West (Oregon)

US West (Northern California)

EU (Ireland)

Asia Pacific (Singapore)

Asia Pacific (Tokyo)

South America (Sao Paulo)

Availibility Zones

Availibility Zones are locations within a Region where instances can run. They help in making instances in a region failure proof. We can run instances in a region in one or more availibility zones or distribute the instances equally among the availibility zones. Availibility Zones inside are region are connected to each other.

Elastic Load Balancer

Elastic Load Balance or ELB, as the name indicates distributes incoming traffic among many instances in availability zone or many availibility zones. ELB also checks for unheathy instances in an availability zone and routes the incoming traffic to healthy instances. ELB supports sticky sessions and has the ability to terminate SSL at the balancer level so the application servers do not need to perform SSL decryption. When you launch an ELB in a region, make sure that it routes the traffic to the availability zones that carry instances. By default an ELB will distribute traffic among all availability zones inside a region. Be sure to select only the availablity zones that carry instances, otherwise the application will face timeouts.

Installing Sphinx 2.0.4 on Ubuntu 10.04 - Lucid

This blog post will help you install Sphinx 2.0.4 on Ubuntu 10.04. 

About Sphinx

Sphinx is a distributed search engine for full text searches. While MySQL offers its own storage engine (MyISAM) for full text searches but its not easy to scale it. Sphinx has many other advantages like: 

• better indexing and searching speed 
• good relevance search
• and most importantly better scalability

Sphinx has two parts:

indexer - This part indexes the data source by pulling information from it and then builds indexes. 

searchd - This part serves search queries by looking up in the index created by the indexer.

Installing Sphinx

Following steps will help you install Sphinx successfully on your Ubuntu box: 

First check if the dependencies are already installed. If not install them.

sudo apt-get install libmysql++-dev libmysqlclient15-dev checkinstall

Download Sphinx 2.0.4 in '/tmp'

cd /tmp

sudo wget http://sphinxsearch.com/files/sphinx-2.0.4-release.tar.gz 

Unpack the 'tar.gz' file and install Sphinx 

sudo tar -xzf sphinx-2.0.4-release.tar.gz

The above command will unpack the 'tar.gz' file. You can find the contents in 'sphinx-2.0.4-release' directory

cd sphinx-2.0.4-release

Make install 

sudo ./configure

sudo make

sudo checkinstall

Note: You will be prompted to create a directory and set a description for the package. Also it will ask you some questions with default answers. Fill them as per your convenience.I had an error in package installation. On checking the log file I saw that specifying version was mandatory. So changed version to 2.0.4.

After installation, the package will be saved to: 

/tmp/sphinx-2.0.4-release/sphinx-2.0.4_2.0.4-1_i386.deb

Make a new folder to keep the *.deb package:

sudo mkdir /home/[YOUR_USERNAME]/SphinxInstalls

Move the sphinx-2.0.4_2.0.4-1_i386.deb package from '/tmp/sphinx-2.0.4-release/sphinx-2.0.4_2.0.4-1_i386.deb' to '/home/[YOUR_USERNAME]/SphinxInstalls' 

sudo mv /tmp/sphinx-2.0.4-release/sphinx-2.0.4_2.0.4-1_i386.deb /home/[YOUR_USERNAME]/SphinxInstalls

You can now delete the working folder and the tar.gz file : 

sudo rm -r /tmp/sphinx-2.0.4-release

sudo rm /tmp/sphinx-2.0.4-release.tar.gz

Location of Configuration/Daemons/Documentation

You can find Sphinx Documentation in:

/usr/share/doc/sphinx-2.0.4

Sphinx Configurations are found in '/usr/local/etc/'. The configuration files that exists by default are:

example.sql

sphinx.conf.dist

sphinx-min.conf.dist

Note: Default Sphinx configuration is sphinx.conf. It is not created by default. So you can copy 'sphinx.conf.dist' as 'sphinx.conf': 

sudo cp sphinx.conf.dist sphinx.conf 

Sphinx Processes (indexer, searchd etc.) are found in '/usr/local/bin/'.

To remove Sphinx: sudo dpkg -r sphinxsearch-2.0.4
To install again use the package in '/home/[YOUR_USERNAME]/SphinxInstalls': sudo dpkg -i sphinx-2.0.4_2.0.4-1_i386.deb 

You are done with the installation of Sphinx on your Ubuntu box. In my upcoming posts I will cover Sphinx configuration (configuring local indexes and distributed instances).
^^^^ Coming this weekend

Enabling mod_rewrite Module in Apache2

I came across this situation recently and thought of publishing it on my blog so others can find it useful.

Introduction: 

'mod_rewrite' is a module in Apache that provides a rule-based rewriting engine to rewrite requested URLs. You can read more about it at Apache Module mod_rewrite.

Enabling mod_rewrite:

To enable mod_rewrite, use the following command:

sudo a2enmod rewrite

Now restart Apache:

sudo service apache2 restart (or) sudo /etc/init.d/apache2 restart

MySQL InnoDB Indexes

MySQL Indexing – InnoDB Indexes

A few days back I was reading about MySQL indexes, more specifically InnoDB indexes, to better understand query performance and optimization. So I thought of sharing some information on this topic. Indexes are basically structures that help the database engine in finding (retreiving) the records faster. An opposite to index lookup is full scan. Think of a full table scan as going through all the rows in a table and selecting the right row.

A common example that is generally given when explaining indexes is a book's index. To look up for a topic in any book, you either look up for the topic in an index or scan the whole book page by page. Obviously if the book has less pages, it is viable to go page by page and scan for a topic but if the book has decent number of pages than using an index is a smart and efficient approach. Same is the case with database indexes.

InnoDB Indexes

MySQL InnoDB Index Structure uses B+ Tree structure to store its data. B+ Tree structure is a different topic. I will be writing a blog on how data in B+ Trees is organized and how insert, update and delete effects the tree

Clustered Index

Clustered Index is an approach to store data. Think of a Clustered Index as a tree structure (index), with data rows as leaves and primary key as nodes above the leaves. InnoDB clusters the data by primary key. Below are some points to remember regarding the Clustered Index:

• As stated earlier, InnoDB clusters the data by primary key. If the table has a primary key, MySQL will use this primary key for Clustered Index.
• If the table does not have a primary key, MySQL selects the first UNIQUE and NOT NULL index for Clustered Index.
• If none of the above applies, MySQL will generate a hidden (6 byte) field that contain row IDs. MySQL will use this hidden field to cluster data (as Clustered Index).

As Clustered Index holds both the data and primary key on the same page, row access is faster because no additional disk I/O is needed. On the other hand, in case of MyISAM, an additional disk I/O is needed as index and data are not on the same page. Below are some points worth mentioning:

• Insertion speeds depend on how data is inserted into the table. Insertions are fast if data is inserted in primary key order. A bad approach is to insert data randomly (with random keys) but a good approach is to have sequential keys (like AUTO_INCREMENT)
• Updating primary key may not be a good idea as it forces each updated row to be moved to a different location. Moving rows to a new location may lead to page splits which causes a table to use more disk space.
• Though Clustered Indexes are efficient in terms of retreival, defining a clustered key having many columns may be a disadvantage. It would be clear why its a disadvantage once you read about the secondary index.

Secondary Indexes

Secondary Indexes are also called non-clustered index. Unlike clustered index, they do not store row data as leaves but they store primary key (clustered index) as leaves. It is due to this reason that it is advised to keep primary key short. The size of primary key will effect the size of a secondary index. As far as lookups are concerned, secondary index look up requires two steps. One to get primary keys matching the secondary key lookup and after that fetching the actual data by looking up the primary keys that are fetched before, from the clustered index.

Architecture for Scaleable Resource Discovery (Part II)

This is the second part of this post. In Part I, I explained the problem, analysis, architecture and algorithms that were devised to solve the presented problem. In this part I will be presenting a strategy to test the architecture using Amazon EC2. The strategy includes the implementation of architecture using EC2 and then implementation of testing clusters to simulate thousands of requests per second to test the architecture.

Simulation Strategy

Region Design

In order to go about simulating our algorithm, we chose to use Amazon’s Elastic Compute Cloud (EC2) as a base framework for simulating regional data replication and distribution. Amazon’s EC2 service is already broken into seven regions (known as Availability Zones) which would allow us to partially test our geographically distributed Regional Minimum Spanning Tree building algorithm. Distributing data accesses across multiple servers within a cluster or ring can be handled by the Elastic Load Balancing (ELB) feature which also detects and reroutes traffic from unhealthy instances of the data to healthy instances until the unhealthy instances can be restored. The CloudWatch feature would allow us to monitor just how efficient our design is performing. The following diagram shows our planned usage of the Amazon EC2 platform in order to simulate our regional architecture:

Request for a resource when generated by the client is routed to an appropriate Resource Region (present in one Amazon EC2 Region). The request is routed to the region closest to the client's location. This is done automatically by Amazon. The request first lands on the Elastic Load Balancer (ELB) of the Resource Region. The ELB sends the resource request to one of the region servers. This forwarding of requests is based on the ELB's request distribution algorithm. The region servers are auto-scaled which means that the number of servers will increase or decrease as the resource requests increase or decrease. There can be different auto-scaling criteria like bandwidth, requests per second, idle CPU time, etc. Once the request reaches the region server, the server determines the cluster to which the request should be forwarded (based on the resource type). The region server then forwards the request to the ELB of the selected cluster. The cluster ELB then routes the request to one of the cluster servers. The cluster servers are auto-scaled just like the region servers. When the request is received by the cluster server, the cluster server uses consistent hashing to figure out what ring cluster to forward the request to. After identifying the ring cluster, the request is forwarded to the ring cluster ELB. This ELB then forwards the request to any MySQL ring server. MySQL ring server has a web service that takes the resource ID and looks for the resource in the database. It then returns the appropriate response (resourceLocation or notFound). Unlike the other servers (region and cluster), the ring servers are not auto-scaled. For ease of deployment and re-use, we will use server templates for Region Server, Cluster Server, Ring Server. The templates will contain all of the necessary server configuration. All we need to do to add an additional pre-configured server is spawn

another instance of a template. We can also clone the Ring Cluster (Farm Cloning) to create a new Ring Cluster when we need more rings, in the case of new resources being added to the system.

Security

All of the servers will be closed to public access. Only for the reason of region synchronization will the cluster servers be allowed to connect to the cluster server of the neighbor region.

Testing Clusters

Now that the regional architecture is set up, we also need to simulate millions of users accessing the data concurrently across all seven regions of the EC2 platform. The following diagram is an example of how we plan on testing our region architecture described above:

We will create a separate instance of the EC2 platform which will send requests to our regional architecture at a predefined rate. These instances will be known as the Tester instances. The Tester instances will take advantage of predefined tools and use our Tester template to spawn multiple instances of a tester for each region, which will allow us to scale up the number of requests and analyze the network traffic and bandwidth used. This approach allows us to create as many or as few requests per second as we want for testing purposes.

Architecture for Scaleable Resource Discovery (Part I)

About the Post
This blog post was basically my project for "Distributed Computing". I took this course in Fall 2011, which was my final semester of my graduate studies. This project was basically a group project and therefore I find it necessary to quote my group members involved in this project. Alongside me, following were my group mates:

• Justin Roberts
• Darshan Lathia

Problem

The problem we were trying to resolve was an open ended problem. We have to design a distributed architecture that can support a resource discovery system, which handles millions of request for resource discovery. For example: a user wants to access any particular resource on the cloud. Now this resource is available in different locations on the internet. Before utilizing the resource, the user has to locate it. After which the user can use the resource for a specific task. The purpose of this project was to design a system that allows a user to locate a resource. The system should be able to handle huge traffic coming from all over the world. The system should be scale-able and robust to handle the work load and should be fault tolerant to be able to serve requests, in an event something goes bad or crashes.

Introduction
In this paper, we explore the inner workings of our architecture. This architecture is a complex layering of protocols which individually solve various problems, but all work together to serve the common purpose of resource discovery in a massively distributed system. We intend to analyze our algorithms by providing a small example of how they function, and showing that each one is a robust solution for accomplishing its intended task. Finally, we will conclude by explaining our simulation strategy, and how we would accomplish a simulation if we were to fully develop our distributed system concept.

Overview of Architecture

Figure 1 - Overall Architecture

In Figure 1, we present the top level overview of our regions. Whenever a client makes a request for any hardware or software resource, the request first lands at the DNS (the request will be made to a domain name or domain names). The DNS server will have a list of IP addresses corresponding to the domain name specified in the request. The request is then routed to any of the IP addresses (in a random or round robin fashion). The IP addresses represent routers. These routers when receiving a request will forward the request to an appropriate regional server based on the location of the client (location identified by the clients IP address). A client's request will be routed to a region that is closest to his location (based on his location).

Figure 2 - Region Architecture

A region consists of regional servers and clusters. The number of regional servers depends on the load of requests from the client in that particular region (they are auto-scaleable). There is one resource cluster for each of the available resource types (for example, one cluster could be entirely devoted to the Microsoft resources). The regional server looks for the Resource Type in the requests from the client and accordingly forwards it to on of the Cluster Servers (belonging to the Resource Type Cluster), again in a round robin fashion. All the regional servers of a particular region are connected to every cluster in that region, so if one of the regional servers fails the system will continue to function due to the redundant links.

Figure 3 - Cluster Architecture

Each cluster is made up of a number of cluster servers (auto-scaleable) and replication server rings. The cluster servers will receive the client requests from the regional servers and then forward the requests to the any replication server (in the appropriate ring), based on the ResourceID. The replication servers are arranged in multiple rings where each ring can be accessed by any of the cluster servers. Each ring in a cluster represents a shard (sharding done based on the resource ID) and each replication server contains resource locations. The replication servers inside a ring are mirrors,
that is they contain the same information as all the other replication servers in the same ring (eventually consistent). Replication servers will contain all the resource discovery data required by clients. Clients can read or write on any of the replication server. Whenever update operation is performed by the client on any of the replication servers, the update is synchronized in that ring and then sent to the cluster server for replicating the change in the other rings of clusters of other region. As the load on a particular server increases, the number of cluster servers can be increased to handle multiple requests. If one of the cluster server fails, the other cluster servers will handle the requests coming from the client. So this architecture is fault tolerant as well as scalable.

Figure 4 - Ring Synchronization

Figure 4 shows that if there is an Update in any of the replication servers then the other servers should also be updated accordingly. So, whenever there is an update in one of the servers, it acts as the leader of the bidirectional ring, and sends the updates to its neighboring servers. In this way all the servers in the ring will remain synchronized.

Figure 5 - Cluster Synchronization between Regions

As already mentioned above, each region consists of clusters for every Resource Type. The other regions also have an identical set of clusters. The clusters of the same Resource type in different regions are synchronized so all the data updated in one cluster is passed on to every other cluster of the same resource type. Since all clusters are synched, if a cluster of a particular region fails or even if the whole region is down, client requests can be redirected to the next closest region. More details on cluster synchronization will be provided at a later time.

Figure 6 - Region Interaction Topology

The clusters within each region will sync with only a small subset of neighboring regions, creating a spanning tree of regions as show in Figure 6. With this approach, data in all regions will always remain synchronized and each region only has to update a small subset of the other regions.

Assumptions
For this deliverable, we are assuming that the resources being requested are read-only. Since this paper only describes the resource discovery protocol, there is no need for end users to modify data at this moment. The resource modification techniques will be presented in a future deliverable. We also assume that we have a client application, where the user will browse to find the desired resource type, and then select the resource to discover. The client application will then make a request consisting of a number of fields (User IP, ResourceType, ResourceID) which will be used for request routing.

Overview of Internal Algorithms
In order to make our designed solution work as intended, there are a few different algorithms which will run at the different layers of our architecture, or which will control the interaction between layers.
The first example is what is referred to as the Cluster Sync algorithm. This algorithm is responsible for maintaining consistent clusters across regions. If a resource id is added or removed from a particular cluster, the Cluster Sync algorithm takes care of synchronizing these updates across clusters.

Another example is the algorithm that creates the spanning tree of regions. Once the regional spanning tree is created, the clusters within the regions will be aware of which other regions they are responsible for updating to ensure data consistency across all regions.

As we know that each ring represents a shard (horizontal partition) of the resource records and the data servers are repositories of the resource records. The data in a ring is replicated among all the data servers which are part of the ring. The process is as follows:

1. One data server receives an update (add/edit/delete of a resource location). Call this data server an active data server.
2. The active data server propagates this update to its neighbor (two neighbors). Update includes an identification of the active server and the timestamp.
3. A neighbor on receiving an update will apply the update locally, if there was no update with the same timestamp and identification received from another neighbor.
4. The neighbor then propagates the same update to its neighbor (if it has any neighbor). In this way the data servers in the rings are synchronized to carry the current data. Of course there will be a synchronization delay but the data servers in the rings would be "eventually consistent".

Algorithm Analysis
There are four main algorithms which control the sharing and distribution of resources: the Regional Minimum Spanning Tree, Cluster Synchronization, Ring Synchronization, and finally the Resource Discovery algorithm which allows a user to search for and use a particular resource. The following is our analysis of how each of these algorithms functions, and why we consider each to be robust.

REGIONAL MINIMUM SPANNING TREE
The algorithm that connects various regions across the world is a minimum spanning tree concept which allows the clusters within the regions to be aware of which other regions they are responsible for updating to ensure data
consistency across all regions. At the region level, the most efficient way to create a minimum spanning tree is by using the well-known Asynchronous GHS (AsyncGHS) algorithm. The process of creating the regional spanning tree is as
follows:

1. A single region can contain multiple regional servers, so one server from each region is chosen to be a leader for that particular region. Leader election within a region is assumed to be trivial. Since there will only be a small number of region servers within a region, a leader could be chosen manually.
2. The leaders of each region will begin an instance of the AsyncGHS algorithm. All regions are assumed to be connected in a complete graph topology, so core edges will initially be determined by least-cost paths between regions.
3. Once the AsyncGHS algorithm has finished the merging and absorption process, the leaders of each region will be aware of which other regions it is directly connected to based on the minimum spanning tree created.
4. The leaders of the region will propagate the resulting spanning tree to the other regional servers within its designated region.

Creating a minimum spanning tree to connect the regions together will minimize the number of neighboring clusters that each region is responsible for updating when changes are made. In addition, we assume that larger distances mean greater link cost (either in latency or monetary), so regions far from each other will have a greater cost and hence be less likely to become neighbors. Therefore, geographic separation between regions will ensure that no single region will have too many neighbors.

CLUSTER SYNC
This algorithm is responsible for maintaining consistent clusters across regions. If a resource id is added or removed from a particular cluster, the Cluster Sync algorithm takes care of synchronizing these updates across clusters. Once an MST is created to connect the regions, each region knows what other regions to synchronize. Below are the steps for cluster synchronization:

1. When an update is made to any region (suppose Region1), that region should synchronize its neighbors (suppose Region2 and Region3).
2. In order to synchronize the neighbor regions, the cluster servers (one or more of a specific resourceType) connect to cluster servers (one or more of the same resourceType) of Region2 and Region3.
3. The cluster servers of Region1 will now send the updates to its neighboring cluster servers (of Region2 and Region3).
4. The receiving cluster servers then perform the update on an appropriate resourceType shard based on the same consistent hashing strategy as they use to find the resourceType shard for a resourceID.
5. Similar process is done at Region2 and Region3 to synchronize their neighbors.

Using this process, all of the regions are synchronized. One reason to synchronize all of the regions is to allow the whole system to function properly in case an entire region goes down. Given this situation, we can route the traffic (of the failed region) to neighbor regions or any region we want.

RING SYNCHRONIZATION
As we know that each ring represents a shard (horizontal partition) of the resource records and the data servers are repositories of the resource records. The data in a ring is replicated among all the data servers which are part of the ring. The process is as follows:

1. One data server receives an update (add/edit/delete of a resource location). Call this data server an active data server.
2. The active data server propagates this update to its neighbor (two neighbors in the ring). Update includes an identification of the active server and the timestamp.
3. A neighbor on receiving an update will apply the update locally, if there was no update with the same timestamp and identification received from another neighbor.
4. The neighbor then propagates the same update to its neighbor.

In this way the data servers in the rings are synchronized to carry the current data. Of course there will be a synchronization delay but the data servers in the rings would be "eventually consistent".
We will use record based synchronization to synchronize ring servers. In record based sync technique the actual record is transferred from one ring to its neighbors. This technique will increase the network traffic but is good and efficient if we have non-deterministic query functions.

RESOURCE DISCOVERY
Resource Discovery here is used to find appropriate resource for the clients based on their request. The algorithm operates as follows:
Whenever a client wants to use a particular resource it formulates a request for that particular resource type. This request contains Source IP Address, Resource Type & Resource ID. Source IP address is used by the DNS server to determine the closest Region Server for that particular client. Resource type helps in selecting a particular resource type cluster from all the clusters in that region (One Resource cluster Type for every Region). Resource ID helps in selecting a ring of replication servers among all the Rings connected to the cluster server. This selection is done using Consistent Hashing on the Resource ID. The Complete process from initiating a request to allocation of a resource for a client is as follows:

1. The Client which is in need of a Resource sends a request for that resource with its source IP address, Resource type required and the resource ID.
2. The DNS Server first receives this request and selects a region server based on the IP Address of the client which is the closest to the client. Also, it can redirect the client to the next closest Region if the closest regional server is not functional at that time for some reason.
3. A Region contains many regional servers. One of the regional server is selected in a Round-Robin fashion. This helps in Load Balancing.
4. The Regional server based on the Resource Type requested by the client selects a Resource Type Cluster. There is exactly one Resource type cluster for every resource that a client may want to use in that particular region. So, Cluster Selection can be done by simply mapping the resource type requested to the different clusters in the Region.
5. Each Resource type cluster has some cluster servers. One of the server is selected based on Round-Robin Scheme which again helps in Load Balancing of the number of requests coming from the clients.
6. The cluster servers are connected to the rings of Replication servers. Number of rings in the region depends upon how frequently clients requests for that resource. Consistent Hashing on the Resource ID is used for selecting a ring. Consistent hashing has many advantages over other hashing techniques. Some properties of consistent hashing make it a different and more improved method than other standard hashing schemes like the Spread, Load, Smoothness, Monotonic, and Balancing.
7. Clients can read or write on any of these Replication servers as each server is a mirror of another i.e. all the servers contain the same data and are updated according to a change in other replication server.

The fact that the Resource Discovery algorithm is broken down into regions based on a user’s geographic location, and the round-robin approach to server load balancing ensure that this algorithm performs with an acceptable speed. When this is combined with the consistent hashing technique for locating one particular resource, it ensures that our resource discovery protocol is both fast and scalable.

Example Resource Discovery
The resource discovery protocol which finds and returns resources is currently the focus of our attention. In order to retrieve a particular resource, the algorithm will operate as follows:

1. A user will formulate a request for a particular resource type. This request will consist of multiple parts, including the source IP address (IP), resource type (RTYPE), resource id (RID), and the action being performed (DISCOVER, UPDATE, etc.).
2. The user will attempt a connection, which through the local DNS servers will route the user to the nearest region servers. Since there can be multiple servers operating at the region level, the individual region server picked within the chosen region will be based on a round-robin scheme to load balance all incoming requests into the region.
3. The region server will receive the request and analyze the RTYPE and action. The region server will know that this is a DISCOVER message (meaning the requesting node is attempting to locate a specific resource), so based on the value of RTYPE, the region server will forward the request to the appropriate resource cluster which services the requested resource type. In a similar manner to the region server operation above, requests will be routed to an individual cluster server within the chosen resource cluster in a round-robin fashion to account for load balancing within the cluster.
4. The chosen cluster server will receive the request and analyze the RID. Based on this resource id, the cluster server will know which resource ring to forward the incoming request on to.
5. The chosen server in the resource ring will receive the request, and reply to the incoming user directly with the given resource.

That's all for this blog. In the next blog I will give a brief overview of how we thought we could simulate this architecture. We decided to use Amazon EC2 to develop our architecture and the topologies and also presented a way to test the resource discovery request.

References

• Amazon Web Services – Elastic Compute Cloud (EC2) [http://aws.amazon.com/ec2]
• DeCandia, G., Hastorun, D., Jampani, M., Kakulapati, G., Lakshman, A., Pilchin, A., Sivasubramanian, S., Vosshall, P., and Vogels, W. 2007. Dynamo: Amazon’s Highly Available Key-value Store. (Stevenson, Washington, United States, October 14-17, 2007). SOSP’07. ACM Press, New York, NY, 205-220.

Note: There may be several issues with the approach and the architecture we presented. There might be several additions or improvements to this architecture. Comments will be appreciated.

Installing Xdebug and webgrind on Ubuntu to debug and profile PHP

Xdebug is a PHP extension that allows us to debug and profile PHP scripts. Its a very handy tool that allows you to profile PHP scripts to figure out the performance bottlenecks or to trace/debug the script. Below is the procedure to install Xdebug and use the information generated by Xdebug for the purpose of profiling and debugging.

In this post I will be discussing the basic installation of Xdebug on Ubuntu and then using 'webgrind' front end to view the profiling data generated by Xdebug. You can install Xdebug in two ways. The first one works if you are using older versions of Ubuntu (below 8.0) and the other one works with Ubuntu 8+. When using the older method of installation, Xdebug is installed through PEAR/PECL. If you have Ubuntu 8+, you can still install Xdebug through PEAR/PECL.

Installing Xdebug through PEAR/PECL:

First install the 'php5-dev' package. This package provides php5 source files, needed to compile additional modules.

sudo apt-get install php5-dev

Next install the 'pear' package.

sudo apt-get install php-pear

Now install Xdebug.

sudo pecl install xdebug

Now find where Xdebug extension is, so the path could be included in the 'php.ini' file as a zend extension.

sudo find / -name 'xdebug.so'

Output: /usr/lib/php5/20090626+lfs/xdebug.so

Now open the 'php.ini' file from the location given below:

/etc/php5/apache2/php.ini

In 'php.ini', you add the path to 'xdebug.so'. Below are minimal configuration option that you can use to get started. A complete list can be found at: http://xdebug.org/docs/all_settings

;xdebug

// ADD XDEBUG AS A ZEND EXTENSION

zend_extension="/usr/lib/php5/20090626+lfs/xdebug.so"

// ENABLE PROFILING OF SCRIPTS. TO TURN OFF PUT 0 OR COMMENT THE LINE

xdebug.profiler_enable=1

// DIRECTORY WHERE THE PROFILING DATA FILES ARE GENERATED
xdebug.profiler_output_dir="/tmp"

// IN CASE THE PROFILE NAME IS SAME, OVERWRITE THE FILE. 0 WILL APPEND DATA
xdebug.profiler_append=0

// THE PROFILE FILE NAME %t = TIMESTAMP, %p = PROCESS ID
xdebug.profiler_output_name = "cachegrind.out.%t.%p"

Now restart the 'Apache' server.

sudo service apache2 restart

New installation method:

First install Xdebug.

sudo apt-get install php5-xdebug

Now find where Xdebug extension is, so the path could be included in the 'xdebug.ini' file as a zend extension.

sudo find / -name 'xdebug.so'

Output: /usr/lib/php5/20090626+lfs/xdebug.so

Now open the 'xdebug.ini' file from the location given below:

/etc/php5/conf.d/xdebug.ini

In 'xdebug.ini', you add the path to 'xdebug.so'. Below are minimal configuration option that you can use to get started. A complete list can be found at: http://xdebug.org/docs/all_settings

;xdebug

zend_extension="/usr/lib/php5/20090626+lfs/xdebug.so"

xdebug.profiler_enable=1

xdebug.profiler_output_dir="/tmp"

xdebug.profiler_append=0

xdebug.profiler_output_name = "cachegrind.out.%t.%p"

Note: These are the same configuration settings as mentioned in installation method above. For explanation of each configuration refer to the previous method.

Now restart the 'Apache' server.

sudo service apache2 restart

After installation:

Now that you have successfully installed Xdebug, its time to test your installation. Execute any of the PHP scripts you have, or just write a simple php script and execute it. After execution, you will see that there is a Xdebug Profile file in the "/tmp" directory. Hence the installation was successful.

Now that the profiles are being generated, lets switch on to 'webgrind', which is a web-based tool to provide profile information in a meaningful fashion.

First download 'webgrind' from the location below:

http://code.google.com/p/webgrind/downloads/list

Extract the compressed files to "/var/www/webgrind" or any location you want (should be served by Apache)

Now open the 'webgrind' config file from the location below:

"/var/www/webgrind/config.php"

Or any location where you have extracted the 'webgrind' package.

In 'config.php', change the following variables:

static $storageDir = '';  // DIRECTORY WHERE YOU WANT TO STORE webgrind FILES

static $profilerDir = '/tmp'; // DIRECTORY WHERE THE Xdebug PROFILE FILES ARE

Now you can run 'webgrind', by executing the index.php file. It can be found in the following location:

"/var/www/webgrind/index.php"

Or any location where you have extracted the 'webgrind' package.

MySQL Replication: Statement based Replication vs Row based Replication

Before discussing the replication formats in MySQL it is necessary to discuss how replication works in MySQL. Why is replication required? The answer lies in my earlier post in which I described the process of scaling MySQL for reads (Scale-Out MySQL). Lets proceed by discussing the replication process. Replication process consists of the following steps:

1. MySQL Master writes any changes that occur to the 'binlog'. binlog is a log that contains any updates/inserts/deletes made on the master MySQL.
2. Slave's I/O thread reads the binlog from the master and writes the events in its 'relaylog'.
3. The MySQL thread reads the events from the relaylog and applies those events to the slave.
4. Steps 1 till 3 are repeated so the slave is synchronized with the master all the time.

Below is the diagram that will aid you in understanding the process of replication in MySQL.

Now that you are aware to some extent about the process of replication, lets dive deep into the replication formats. By replication format I mean the format in which events are recorded in master's binlog. There are three types of replication formats:

1. SBR or Statement based Replication
   In this format of replication, the MySQL master, records the events as SQL statements into the binlog. The statements are picked up by the MySQL slaves and replayed in the same way as they are played at master
2. RBR or Row based Replication
   In this format of replication, the MySQL master, records the events as actual rows that indicate how the rows are changed at the master.
3. Mixed Mode Replication
   This format of replication is a mix of RBR and SBR. MySQL switches the format in real-time depending on the type of event.

Of course there are pros and cons of each format, I will primarily address the RBR and SBR. I will discuss the pros and cons of each replication format type.

Statement based Replication

Pros:

1. As in case of statement based replication the events are logged as SQL statements and not in form of row changes, hence the log files are much much smaller and utilize less storage space.
2. The log file contains all the SQL statements and hence can be utilized for analysis, audit or restoring from backup.
3. In terms of bandwidth, statement based replication is much more efficient because its the queries that are transferred to slave and not the actual row updates.

Cons:

1. Statements that possess non-deterministic properties are difficult to replicate using this format.
2. Statements that use stored procedures or user defined functions (UDF) are considered to be nondeterministic statements and hence are difficult to replicate using SBR.
3. DELETE and UPDATE statements that use LIMIT without using ORDER BY are considered to be nondeterministic and hence cannot be replicated using SBR.
4. UPDATE statements with a WHERE clause that doesn't utilize the index require more locks in SBR then in RBR.
5. INSERT statements that use auto-increment, block other non-conflicting INSERT statements. This is applicable to InnoDB engine. Its a very important point to consider as this point effects concurrancy.
6. More locks are required on the slave for INSERT/UPDATE/DELETE
7. Complex statements that are evaluated and executed on the master, need to go through the same process on the slave before applying changes to the slave.
8. Table definations should be identical on the master and slave.

Row based Replication

Pros:

1. Its the safest form of replication though not as old as statement based replication.
2. Fewer row locks are required for INSERT statements with auto-increment.
3. Fewer locks are required for INSERT/UPDATE/DELETE on the slave when compared to statement based replication.
4. Fewer locks are required when UPDATE and DELETE statement's WHERE clause does not make use of the index.

Cons:

1. Contrary to statement based replication, row based replication records changes to each row. The most probable disadvantage from this behavior is the size of the binlog. If a SQL statement effects 100 rows then in SBR just one query is logged whereas in RBR changes to 100 rows are recorded. This behaviour makes binlogs in RBR much much larger then SBR.
2. As in case of SBR, the SQL queries are logged and hence they can be reused and read for audit. In RBR, there is no way to figure out what statements were executed on the master and recieved on the slave. However what rows has been changed or inserted, can be decoded.
3. There is no mechanism available in RBR to ensure that the binlog in MySQL master was processed without any problem at the slave.

After comparison of both the formats, I personally believe that Row based Replication in MySQL is the way to go because:

• Its the safest form of replication
• It is safer when it comes to replicating triggers and stored procedures.
• It requires fewer locks and hence its much faster and achieves high concurrancy.
• Regarding the drawback of having large binlog, I would say that not all applications may issue updates that effect thousands of rows. Comparing to the other advantages that row based replication provides and an informed guess I would say that this disadvantage may be ignored.

The choice of which format to choose depends on the application and requirements. I have not touched mixed format. My guess is that mixed format may bring in the best of both world. I will be discussing mixed format replication in detail, in my upcoming post.

Memcached and MySQL (Part II – Memcached + MySQL)

In part one of this blog (you can see it here) I gave a detailed overview of what Memcached really is. In this part I will address the usage of Memcached to alleviate the load from MySQL. In a scalable + high traffic application, database will prove to be a bottleneck due to the limitations of disk read/write rate, which is slow as compared to reading from memory. As Memcached is a memory-based distributed object storage cache, we can utilize the power of Memcached. Will avoiding database a good optimization? Yes it is. This is where Memcached will come into play, avoiding the requests to hit MySQL. Well not in all cases but yes to a considerable extent. Having Memcache installation on the same server as MySQL and using it will help the data source to perform much better. When I say Memcache it means that I am refering to only one instance of Memcache and not a distributed version (in the latter case its Memcached). Having Memcache on the same server as MySQL means that memory will be distributed between Memcache and MySQL which is not what I prefer. I would prefer a separate server dedicated to Memcache so MySQL can utilize the memory and definitely get more of it. Below is the architecture that I am considering:

As you can see that we have a MySQL server and a Memcache Server. We generally have queries that are either fetching data from database or adding/deleting/updating data in the database. For each type we can follow a particular sequence:

Read Queries:

1. Check Memcached if the data set is available

2. If its available then congratulations you just avoided a hit to the database

3. If its not, too bad. Get the result set from the database

4. You want to avoid hitting the database again, so set the data set in Memcache

Write Queries:

1. Write data to the database

2. If the write was a success, then either drop the data set from the Memcache or update the Memcache with current information

Of course this is a very naive concept when it comes to the practical implementation. Practically things are very much different and a bit complicated when it comes to the usage of Memcached. Additionally there can be different levels of caching in an application which are constructed overtime in the life cycle of an application and are based on the needs. Also we can increase the Memcache servers to develop a Memcached cluster to cater the needs of ever increasing data. Now we can clearly see that the performance of the application will increase greatly by reducing the load on the database, using an in-memory key value storage.

Memcached and MySQL (Part I - Memcached)

We all know that disk I/O is expensive then memory and we also know that data in memory is volatile but on disk is non-volatile. Talking about relational database storage, data is stored on disk which means that it is non-volatile but the retrieval and storage is slower then memory. On the contrary, if we store data in memory the retrieval and storage is super fast but the data is volatile and thus prone to loss. The question is whether we can get the best of both worlds. The question will be anwered ahead. Lets first see what Memcached is. Below is a point-wise explanation of Memcached (will try to cover as much as I can)

Memcached in a nutshell

1. Memcached is a distributed in-memory object caching system. It's distributed, which means that Memcached does not represent a single server but can span hundreds of computers. Its in-memory, which means that all the objects are stored in memory (RAM). Memcached is a distributed version of Memcache.

2. It's an in-memory key/value store, where data/object can be stored using the key as an identifier of the data/object.

3. Data is in-memory and is therefore volatile. Its good as a cache but not good for data that needs to be persisted and the loss of which might not be good for the application or the users.

4. All operations in the Memcached take constant time and hence their complexity is O(1). The basic operations of Memcached are add, set, get, multi-get, delete, replace (Note: a set after a set on the same key is considered to be an update).

5. All items in Memcached have expiration time. An expiration time of zero '0' means that the item will never expire (here never means 30 days of expiration time). If the expiry time is greater then 30, it will be treated as a UNIX timestamp.

6. Memcached does not have a garbage collection mechanism. You need to either explicitely delete the item, get an item that is already expired, or wait for Memcached to run out of alloted memory. In short, Memcached memory reclaiming is lazy, which is logical keeping in mind the complexity and processing involved in garbage collection.

7. Memcached reclaims the memory using the following mechanism:

   1. If an item is requested, Memcached checks it's expiry time. If the item is expired, it returns a negative response and reclaims the memory by freeing its memory.

   2. If Memcached is unable to accommodate any new items, it starts to free the memory of LRU (least recently used) items in order to accommodate new items.

8. Memcached servers are isolated, which means that one server is unaware of the presence of another server. Where to route the request is the responsibility of the Memcached client library.

9. Generally you do not need authentication mechanism for Memcached and previously it was not even supported. Now if the client supports, SASL authentication can be used. Generally Memcached infrastructure is in a closed internal network and hence having authentication and other security measures may complicate and introduce unwanted latency to an otherwise simple concept.

10. Memcached has a client part and the server part. The client part is responsible for routing the request to an appropriate Memcached server in the Memcached server cluster, managing connection and handling failures. The server part is responsible for request processing and reclaiming memory.

11. You can cache objects, queries, data-set and anything sensible in the Memcached. Just remember its a cache and not a persistent storage.

12. There is no replication or a fail-over mechanism in Memcached.

13. Compression and Serielization of cache objects should be investigated when selecting an appropriate client for Memcached. Also connection handling mechanism should be carefully read in order to avoid connection leakages which will render the Memcached server useless.

14. Hashing Algorithm depend on the clients. Generally 'Consistent Hashing' algorithm is implemented by the clients. This algorithm devises a strategy to distribute the keys across several Memcached servers evenly but the biggest advantage comes in when new servers are added to the Memcached cluster. This algorithm minimizes the number of re-hashed keys whenever a new server is added in comparison to the normal hashing algorithms where re-hashing is considerable.

Below is a diagram that shows the client part and server part of Memcached (in a Memcached cluster of two Memcached servers):

The next part will discuss how we can use Memcached to allieviate the load from the database server, which was the actual motive of this post.