Understand Multilevel index and Blocking factor

I got the following lecture notes from http://computersciencecafe.blogspot.co.uk/2010/10/blocking-factor-in-multilevel-index.html

Why use Multilevel index? 
In ordered sequential file number of block access required is log(2,b) where b is number of blocks to store the index file. Multilevel index were introduced to reduce the number of block access to access the recordNumber of block access required for multilevel index is log(bfr,b)
so number of access are less if bfr is greater than 2 for multilevel index than for ordered index fileBlocking factor

bfr  =  B/R =  (block size / record size)
blocking factor or fan out of multilevel index specifies number of records that can be accumulated in single block or records per block

Problem 1.1

Consider ordered data file with following parameters

r (number of records) = 16348
R (record size) = 32 bytes
B (block size) = 1024 bytes

index stored as key + pointer pair

key value = 10 bytes
block pointer = 6 bytes

Find the number of first level and second level blocks required for multilevel index on this

Solution:Number of First level Blocks

Lets find Number of blocks in data file

Number of records that can be accumulated in block i.e
Blocking factor  bfr  = 1024/32 = 2^5
so, can have 32 records in a block

now how many such blocks are required for 16348 records

number of blocks required for data file =  (r/bfr)
= 16348/ 32  ~=  511

now we know we need 511 entries in the first level index

Find 511 entries can be stored in how many blocks
i.e  how many blocks in first level of multilevel index will be required to store this much entries where each entry is of 16 bytes(key + pointer size)
R’ = 16
B = 1024
bfr’ = 1024/16 = 2^6

 Blocking factor or fan-out for first level and its subsequent levels will be same because index entry is of same size

so number of blocks required for 512 entries would be  = r’/bfr’
= 511/64 = 2^3  ~= 8

Number of Second level Blocks

Its clear that only a single second level block would be required to store 8 entries
but lets calculate
Number of entries in second level = Number of blocks in the first level  = 8
Number of blocks in second level = (number of fist level blocks)/(bfr)
= r”/bfr’

blocking factor bfr’ is same here as second level because here also we will be storing key + pointer pair
Number of records are now 8.

So, Number of blocks for second level = 8/64  ~= 1

Problem 1.2

For secondary index on unordered key data file
with same parameters


In case of secondary index there is one index entry required for each data record in data file

Number  of First level blocks 

First level index will store index entries for all the records(16348)  in data file

Number of blocks needed for first level index = r/bfr = 16348 / 64 ~= 256
(bfr = 1024/(10+6) )

Number of second level blocks

Number of entries in second level = Number of blocks in first level = 256
bfr = 64 is same and r = 256
so Number of second level blocks = 256/64 = 4

Read More

Configure/Add Tomcat to Startup/Boot list in Linux

1. “/etc/init.d/” contains all the startup services in Linux, so the first step is to create a “tomcat” file in “/etc/init.d/”
And add the following code to the file. Remember to adjust RUN_AS_USER and CATALINA_HOME to your environment.

# Init file for SixSigns Tomcat server
# chkconfig: 2345 55 25
# description: SixSigns Tomcat server

# Source function library.
. /etc/init.d/functions

RUN_AS_USER=root # Adjust run user here
CATALINA_HOME=/usr/local/apache-tomcat-6.0.35/ #Adjust here for different location

start() {
echo "Starting Razuna Tomcat: "
if [ "x$USER" != "x$RUN_AS_USER" ]; then
su - $RUN_AS_USER -c "$CATALINA_HOME/bin/startup.sh"
echo "done."
stop() {
echo "Shutting down Razuna Tomcat: "
if [ "x$USER" != "x$RUN_AS_USER" ]; then
su - $RUN_AS_USER -c "$CATALINA_HOME/bin/shutdown.sh"
echo "done."

case "$1" in
sleep 10
#echo "Hard killing any remaining threads.."
#kill -9 `cat $CATALINA_HOME/work/catalina.pid`
echo "Usage: $0 {start|stop|restart}"

exit 0

2. Save the file
3. Add tomcat to the startup list

chkconfig --add tomcat
chkconfig --level 345 tomcat on

4.To check and confirm if tomcat has been added using:

chkconfig --list

Simple! That’s it. You can also use command to delete service from startup list using:

chkconfig --del

Read More

Solution for Cross Domain/Origin Problems with Tomcat web application and Javascripts

I believe there are a lot of people may have encountered problems when using Tomcat servlet as backend  and HTML+Javascripts(Jquery) as frontend. Most of these problems are related to the Cross-Domain security issues, especially for Chrome users. I am writing this blog to summarise my solution for this.

For example, if we host Tomcat web application at server A ( and frontend html at Apache server B (

  1. Configure your existing web application with Cors Filter http://software.dzhuvinov.com/cors-filter.html(CORS Filter is the first universal solution for fitting Cross-Origin Resource Sharing (CORS) support to Java web applications. CORS is a recent W3C effort to introduce a standard mechanism for enabling cross-domain requests in web browsers and participating servers.)
  2. Configure httpd.conf file in Server B add Proxypass, Proxypassreserve and ProxyPassReverseCookiePath
    ProxyRequests On
    ProxyVia On
    ProxyPass /proxy  ajp://
    ProxyPassReverse /proxy ajp://
    ProxyPassReverseCookiePath / /proxy

    The reason I use ajp(Apache JServ Protocol) and ProxyPassReverseCookiePath is that I do not want to lose any session using the ProxyPass method (each time the controller was invoked, a new session was created). If your application does not use any session control, you can just use Proxypass to normal http and without using ProxyPassReverseCookiePath

That’s all you need to do! More on the session control part you can read this blog: http://budilov.com/blog/?p=57

If you see any error in apache log such as:(13) Permission Denied, here is the solution http://wiki.apache.org/httpd/13PermissionDenied


Read More

CACSS: Towards a Generic Cloud Storage Service (reveal the secret knowledge behind cloud storage services)

Keywords: cacss cloud storage s3 architecture cloud computing amazon s3

Published in the 2nd International Conference on Cloud Computing and Services Science, CLOSER 2012, Porto, Portugal.

Title:      CACSS: Towards a Generic Cloud Storage Service
Author(s):      Yang Li, Li Guo, Yike Guo


The advent of the cloud era has yielded new ways of storing, accessing and managing data. Cloud storage services enable the storage of data in an inexpensive, secure, fast, reliable and highly scalable manner over the internet. Although giant providers such as Amazon and Google have made a great success of their services, many enterprises and scientists are still unable to make the transition into the cloud environment due to often insurmountable issues of privacy, data protection and vendor lock-in. These issues demand that it be possible for anyone to setup or to build their own storage solutions that are independent of commercially available services. However, the question persists as to how to provide an effective cloud storage service with regards to system architecture, resource management mechanisms, data reliability and durability, as well as to provide proper pricing models. The aim of this research is to present an in-depth understanding and analysis of the key features of generic cloud storage services, and of how such services should be constructed and provided. This is achieved through the demonstration of design rationales and the implementation details of a real cloud storage system (CACSS). The method by which different technologies can be combined to provide a single excellent performance, highly scalable and reliable cloud storage system is also detailed. This research serves as a knowledge source for inexperienced cloud providers, giving them the capability of swiftly setting up their own cloud storage services.


Read More