Hash based persistent trees

After a long hiatus I returned to blogging.
One of the key things that have perplexed is data base internals especially indexing. Never got a hang of it directly as I always got confused about how pointers are implemented in disk blocks from user space. These questions have always confused me.

Hence I decided to implement my own a no-sql store on a single node and choice of language is none other than Erlang on Mochiweb server. Webserver is just an interface for applications.

It just exposes two APIs in form of GET/POST.

1. GET for fetching the value associated with a key.
2. POST for storing the value associated with a key.

Transaction-managment etc I plan to implement later.

Some points about my choice of language Erlang:

a. Concurrency is baked in language and I don't need to use Thread pools like other boiler plate code.
b. Functional language so easier to think and less bugs.
c. Can easily to multi node in case I need it via OTP.

Now how do I store the key-value pairs. I used B-Tree like idea however instead of comparisons I just used hashes. These hashes are computed based on keys and these hashes form the directory names inside root path.

Let me explain using an example:

Consider a B-Tree of level 10 and each level we store till 1001 nodes.
Key is "K1" and its 10 different hashes (mod 1001) are :
10,20,30,40,50,60,70,80,90,100

So the data is stored at following file:

/10/20/30/40/50/60/70/80/90/100/K1

This is based on principle that file lookup inside directory is extremely fast as each directory has direct information about its subdirectories inside the directory inode.
So we have 10 disk based lookups and hence data structure is O(1).

I can store upto 1000000000000000000000000000000 bytes which serves my purpose very well.

Code is available at following location.

https://github.com/srivasrrahul/Simple-local-db.

Art of programming in C++ (part -1)

C++ is a very complicated language. Learning it thoroughly will take years. You must understand this properly.
First book on C++ should be Thinking in C++. This is easy to get as its free. The only problem with this book is it doesn't tell you how to create abstractions in C++.
But learning a programming language is like learning to speak. First you learn to speak and then make it proper by learning the rules of language. So you must program also. Thinking in C++ doesn't give you that idea. So you must program.
In my experience people find operator overloading as tough part.
Why its tough? I think because of its syntax? Its hard to remember the rules
So when you learn C++ you must program some data structures in it. (For example try implenting link list/tree in C++).(Caution: This will be tough if you are programming in C++ for first time).
It will help you to think logically using C++ as a a language.

A gentle test in C++ to see if you are level 0 inside C++ lanaguage.
Can you write the code of the following:

1. Implement link list in the C++.
2. Implement binary search tree in C++.
3. Implement binary search in C++.

//Design problems.
1. Write a singleton class.
2. Write a factory class.

See if you can spot some errors:

1.
class A
{
public:
virtual void f(){}
};

class B : public A
{
public:
virtual void f(){}

};

void g(A * p)
{
memset(p,0,sizeof(A));
p->f();
}

Any error has been observed?

2. Write a code which stops object from being copied.
(Hint: Inside member functions also)

3. Write a code which stops the object construction if an event has occured in the network.
(Hint: You can know about the event from a function which is given. But there shouldn't be any leak in code).

More about this in next blog.

Generic Programming in C++

Last week I was working on how does the templates can solve some problems which can avoid to write repeated code. Basically I was trying to apply principles which Generative Programming tells (In a very beautiful way indeed).
One of the few principles it states that about domain engineering. How for a particular domain, code can be inside common repository.
The easy part is code can be written prety easily using templates. But all this depends on projects that you are doing. Most of the time code gets written based on requirements of a concrete product. I feel in those environments writing domain based code is not possible. (Like STL can't be written with a particular project in time).
To write the code which can be used in a domain there should be two approched one is vertical and horizontol.
Vertical approach is required when code is written for a product and in those places generalization can be done. There you'll see the plethora of libraries being written which solve various purpose.
More difficult is to use horizontol approach. Here the true generic programming takes place.
I think this is similar to data mining: In data mining data is analyzed to get the patterns hidden in data. Similarly for "code mining" its required to do code analysis and find patterns in code and help in writing code which can be used across similar product lines.

Take an example: Take a model of trying to route a message based on a configured policy.
Now for a router (IP Layer) this could be based on IP tables for an HTTP server it should be based on DNS. (Network Layer)
If you see the code is almost easy and should be written like below so that each prodfuct can be used it independently.

template typename Message,
class MessageRouter
{
bool operator()(Message & message,RoutingPolicy & routingPolicy)
{
RoutingPolicy::Iterator itr = routingPolicy.getFirstPolicy();
for (;itr != routingPolicy.end();++itr)
{
if (itr->route(message))
{
return true;
}
}

return false;
}
};

This code is a simplification. But we can see the principles here. The same code code is repeated across the IP layer and application layer across TCP/IP leyer.

Why C++ STL is bad for interfaces design?

Let me correct myself and some disclaimers.
This is not a critique of STLs but how bad use can turn this into nightmare.
STL is one of best things to happen for C++.
It allows rapid creation of code (almost like interprted language). But there are some inherent problems here.
(Though I don't know how to overcome it).
For example take STL string. Default allocator moves to new but I can tweak it to customized allocator. But consider I want to code like below:
void fun()
{
char buf[128] = "test";
manipulate(buf,128);
}

Now manipuate is a library function which doesn't takes string. What to do? Well I think the usual answer is library design is wrong? Change the library to accept string like below.

Well this is disater. The code that was mainpualting data structures on stack has suddenty moved on heap.

void mainputae(std::string & str);
Now try to change default allocator. Will it work.
Something like below:

void fun()
{
std::string<....,my_alloctor> str;
manipuate(*((std::string *) (&str)));
}

This also doesn't work. Since the allocator function is like below:

void * p = allocator::allocate(size);
This code is inside library. Inside the libtary the default allocator is still default so no use.

Actually STL are not meant for interfaces. Interfaces are designed so as to hide implementaion details and STL philosphy is not for that.
STL aim to provide generic algorithm and express is as type independent and key decisisions can be tuned as per details (memory allocation etc.) But tuning it to different types can lead to different data types. Hence the type is not completely defined.
Don't use STL for interfaces. (library design and you want to give library with simple .h types).

More about this in next post.

Programming and Indian engineering colleges

This is about proragmming. (how I learnt it)
Long back when I started programming (that was in college) I couldn't understand what was its all about.
A sample example was to write a code for checking prime numbers. (from 1-100). I remember not to able to write code for it (it was in C and it was first time I was seeing the computer in my whole life). To add to my misery all my classmates (most of them) were able to write it and understand it.
I was very depressed.

I thought I can't do programming much. Hence I almost asked (didn't do it though) to change my engineering branch (I had taken information tech).

So I began avoiding programming. (There were hardly few programming subjects). I focussed on what I was good at, Mathematics (at least I though so). So I studied same topics from different books in mathematics. That made me good at mathematics. All my colleagues when focussed on learning latest languages (C++/JAVA/VB (yes VB?)) I didn't understood ABC of that. Though I studied computer science (Data structures + algorithm + os) but I couldn't program.
Now when I sit here today I thought it was a blessing in disguise. More mathematics means I could analayze program complexity (yes I solved Coremen Program complexity chapter) easily and till today after seeing any code I can understand this will have a performance bottleneck.
In those times,folks at my college used to study C by Yashwant Kanitker. I was never able to understand what problem you will solve by telling printf("%d,%d",++a,a++); output
(plus some placement papers were like that)

I never understood it. After coming to Bangalore I knew Kernighan & C is "the" book of C.
This had much clearer explanation of programming. I wrote hell number of code in office/home during my free time. Sometimes writing BST/queues. (In college I couldn't undestand what was malloc and what happens if I don't free it).
Then I studied C++ (Bruce Eckel). It should be read after learning C. It has very good explanation of basic C++.
After doing this I still can see there was a huge difference between Indian programmers and same persons working in US (western countries) after numerous interactions with them.
For example consider the following case how did you design state and corresponding handlers.
For initial months I though better write a blob of switches and each case will handle the event.
Now in some code I saw on net it used array of function pointers. I thought why the hell person will do like that. I discussed with some persons and they told me its design patterns and to master it you need to study design patterns book. I bought it immediately (GOF). Though I could correlate singleton/factory easily but I couldn't go beyond that.
I was horrified at my inability to understand GOF in depth. (further I can't understand widget till today)
I thought these are solutions to problem but who solved it in first place.
Design patterns are like dishes,you know them then you can be good cook sometimes but once every-one get used to those dishes then you will be just an ordinary cook.

Design patterns doesn't give you capability to write great code. It only gives you solution to some missing things (you can think of if they are missing)

Somethings was missing in my understanding. C/C++ can help me to write great code but to design somethings (imagine a movie director directing Avtaar-2 with an old camera) essential tools/concepts were missing.

I studied Modern C++ design. Its an amazing book. Straight away I can see the usefullness of the patterns there. But still how Modern C++ idea cropped in Alexander's head is a mystery.

Then a colleague mentioned about SICP. After completing about 2 chapters of SICP I think now I understand the code.
For example
1. The state/event handler mentioned above is nothing but a data directed programming.
2. Programming in terms of interfaces is clearly set about in second chapter3. Function object pattern is nothing but a higher order functions and why its useful.
This is used heavily inside STL.

I think Indian engineering colleges must relook at curriculum again. That is some reason I don't see any Indians (residing in India) didn't contribute anything to open souce etc.

SICP should be made compulsory across the collegess.