funny stuff

Cassandra distributed deletes

2012-01-13T04:47:00.000-08:00

Cassandra~

1. Cassandra replaces the value to be deleted with a special value called a tombstone in case of other nodes are down so that they can't receive the deletion request.

2. delete the tombstone after GCGraceSeconds. So, a node is down for a longer than GCGraceSeconds can't get tombstone updates propagation. You need to remove the node.

http://wiki.apache.org/cassandra/DistributedDeletes

c++ exceptions and memory leaks

2010-12-16T02:45:00.001-08:00

I had to come up with a way to deal with erratic and exceptional condition by C++ exception mechanism.
First I refereed to Google C++ coding convention. They say it is not good to use C++ exception with legacy codes which don't use it.
One of reasons is that it causes resource leaks. see the following code.
Here, h() calls g(), and g() calls f(). The problems is when f() throws an exception, if g() doesn't prepare this situation by RAII or others, a memory is leaked in g().
g() has to be very careful that it cleans up every resources it created in a stack unwinding.

void f() throw(myexception)
{
cout << "f() called" <<>
throw myex;
};

void g()
{
int* leak = new int[10];
cout << "g() called" <<>
f();
delete[] leak;
}

void h()
{
cout << "h() called" <<>
try {
g();
}
catch (exception& e)
{
cout <<>
}
}

valgrind --tool=memcheck --leak-check=yes ./a.out
==11647==
==11647== HEAP SUMMARY:
==11647== in use at exit: 40 bytes in 1 blocks
==11647== total heap usage: 2 allocs, 1 frees, 176 bytes allocated
==11647==
==11647== 40 bytes in 1 blocks are definitely lost in loss record 1 of 1
==11647== at 0x4C27939: operator new[](unsigned long) (vg_replace_malloc.c:305)
==11647== by 0x400DAF: g() (in /home/nhn/workspace/study/c++/exception/a.out)
==11647== by 0x400E15: h() (in /home/nhn/workspace/study/c++/exception/a.out)
==11647== by 0x400E93: main (in /home/nhn/workspace/study/c++/exception/a.out)
==11647==
==11647== LEAK SUMMARY:
==11647== definitely lost: 40 bytes in 1 blocks
==11647== indirectly lost: 0 bytes in 0 blocks
==11647== possibly lost: 0 bytes in 0 blocks
==11647== still reachable: 0 bytes in 0 blocks
==11647== suppressed: 0 bytes in 0 blocks

When you use RAII patterns, there will be no memory leak.

class MyRAII
{
public:
MyRAII()
{
cout << "MyRAII() called" <<> m_data = new int[10];
}

~MyRAII()
{
cout << "~MyRAII() called" <<>
delete[] m_data;
}

private:
int* m_data;
};

void g()
{
int* leak = new int[10];
MyRAII myRaii; // no leak

cout << "g() called" << endl
f();
delete[] leak;
}

http://google-styleguide.googlecode.com/svn/trunk/cppguide.xml?showone=Exceptions#Exceptions
http://publib.boulder.ibm.com/infocenter/comphelp/v8v101/index.jsp?topic=%2Fcom.ibm.xlcpp8a.doc%2Flanguage%2Fref%2Fcplr155.htm

Hadoop record boundary

2010-09-01T21:55:00.000-07:00

I am working on build a infrastructure for analysis of a vast amount of emails.
I made a chunk of email archives, size of which is 2G each.

The problem was that when I concatenated each email into a chunk, there had to be a sync mark to distinct the boundaries between each email.
So I put sync marks between emails.

However, when I put this files on the DFS, and run a mapred job, I am just worried about the record boundaries of overlapped record between input splits and have some curiosity about how HADOOP deals with it.

I was able to find the correct answer from this link.
http://wiki.apache.org/hadoop/FAQ#A23

nginx php-fpm TIME_WAIT

2010-04-09T03:26:00.000-07:00

When you use nginx as a fastcgi web server and php-fpm for workers, you might come arocss TCP TIME_WAIT problem.
TIME_WAIT is a state of socket waiting for a certain amount of time to close.

Because of the very frequent communications between nginx and php-fpm, you will find sockets of TIME_WAIT accumulating a lot over 30,000. It looks uncomfortable.

The solution is to use a unix domain socket.

1. php-fpm.con
/tmp/fastcgi.sock

2. nginx.conf
fastcgi_pass unix:/tmp/fastcgi.sock;

you will find a great reduction in the number of sockets of TIME_WAIT.
However, from my test the performance is worse than TCP socket.
I don't know why...

Anyway, the result from my benchmark test, nginx was able to process 4~5 times more requests(10,000 units per sec) as Apache did. it's awesome.

apache mod_rewrite with percent signs

2010-04-01T02:06:00.000-07:00

This article shows a little bit how to use mod_rewrite.

The scenario is
1. A client connects to the web server with a '%'-signed URL.
For example, when you use MBSC(e.g. Korean), the URL turns into other form.
http://test.com/테스트 => http://test.com/%C5%D7%BD%BA%C6%AE

The Solution is the followings. But I don't know the internals.

httpd.conf
RewriteEngine on
RewriteRule /테스트 http://test.com [R]
RewriteLog "rewrite.log"
RewriteLogLevel 10

rewrite.log
localhost - - [01/Apr/2010:14:38:07 +0900] [test.com/sid#94f2490][rid#95481a0/initial] (2) init rewrite engine with requested uri /테스트
localhost - - [01/Apr/2010:14:38:07 +0900] [test.com/sid#94f2490][rid#95481a0/initial] (3) applying pattern '/%C5%D7%BD%BA%C6%AE' to uri '/테스트'
localhost - - [01/Apr/2010:14:38:07 +0900] [test.com/sid#94f2490][rid#95481a0/initial] (1) pass through /테스트
localhost - - [01/Apr/2010:14:39:46 +0900] [test.com/sid#8785490][rid#87db118/initial] (2) init rewrite engine with requested uri /테스트
localhost - - [01/Apr/2010:14:39:46 +0900] [test.com/sid#8785490][rid#87db118/initial] (3) applying pattern '/테스트' to uri '/테스트'

C++ new operator and object cloning.

2010-01-12T18:22:00.000-08:00

STL provides a few operator overloadings for the global new operator, which is used by new keyword to allocate a memory block to make a instance. New operators only provide a service for allocation of memory.

These come with header file new.
When you declare it, it will apply the global namespace.

http://www.cplusplus.com/reference/std/new/

You can allocate a memory block for a uninitialized object(, which means its constructor has yet been called) and initialize with its constructor later.

For instance, using this feature, you can do a cloning for a object.

--------------------------------------------------------------------------------

#include iostream
#include stdlib
#include new
using namespace std;

struct myclass {
myclass(int i):m_i(i) {cout << "myclass constructed\n";}
myclass(myclass &src) {
this->m_i = src.m_i;
}

void print() { cout << "my member is " <<>m_i << endl; }

int m_i;
};

int main() {
myclass tmp(1);

myclass *p3 = (myclass *)malloc(sizeof(myclass));

new(p3) myclass(tmp); // call constructor
//operator new (sizeof(myclass), p3);

p3->print();

return 0;
}

RETE algorithm.

2010-01-07T02:45:00.000-08:00

I'm woking on developing a rule-based inference engine nowdays.
I came across an algorithm which can do really fast pattern matching of facts against rules, called RETE.

When you have facts which are augmented into the existing ones, or facts are continuosly chaning, RETE is the solution.

The key idea of RETE is cache memories of nodes. When a node has caclulated a input once, it saves the result of it into its memeory. And when additional facts are known, only compute on newly added facts and join with the existing results in the memories.
Also separation between alpha network and beta network is an amazing idea.

There are a few implemention of this algorithm. Jess in java, Clips in C. Both are open source.

Check the following link out.

http://en.wikipedia.org/wiki/Rete_algorithm

Pig versus Hive

2009-12-16T18:41:00.000-08:00

I'm recently working on detecting traffic trends to achieve my goal, which is classified.

After a few days of contemplation, I've decided to adopt Hive like Twitter did.

The reasons are..
1. use Python to calculate complex statistics operation by Hadoop streaming.
2. There are such many simple operations to run. use Hive QL
3. Build dataware house.

hex to char

2009-11-26T00:22:00.001-08:00

The blow code snipet converts hex value into charater in ISO 8859-1.

For instance, we have letter 'B', the ascii value of which is 0x42.

what[0] = '4'
what[1] = '2'

Since what[0] is less than 'A', substract '0' from it, and we get 4. Next, multiply 4 by 16 resulting 64. Finally we add 2 to 64. we get 66. 66 is the ascii value of 'B'.

If what[0] is bigger than 'A', we can find the result charater in ISO 8859-1 charset.

char _x2c(char *what)
{
char digit;
digit = ((what[0] >= 'A')
? ((what[0] & 0xdf) - 'A') + 10
: (what [0] - '0'));
digit *= 16;
digit += ((what[1] >= 'A')
? ((what[1] & 0xdf) - 'A') + 10
: (what [1] - '0'));
return(digit);
}

python generator.

2009-09-17T02:43:00.000-07:00

Since I am quite a newbie to Python, I don't know much about sophisticate techniques of it. However, as I dig out Python, I find out something interesting topics.

Python generator came out in the early of 2000. It's somewhat old concept, but for me this one is quite amazing.

OOP pursues the idea that puts states and behaviors into An isolated and separated object. Closure in functional programming follow the same idea. It is a function which has free variables bound to lexical scope of the function containing them. In other words, closure is another case of encapsulation like OOP.

Generator in Python goes even further than closure. This doesn't only encapsulates states and behaviors, also control flows. Because of this, there are so many application using this one to solve problems which people find difficult to come up with a neat solution in other languages.

http://docs.python.org/tutorial/classes.html#generators
http://www.ibm.com/developerworks/linux/library/l-pycon.html

Optimization proposal for Hadoop I/O pipelines

2009-09-01T09:57:00.001-07:00

There are a movement to improve Hadoop's I/O performance. The main approach is reducing the number of byte buffer copy operations among the kernel, native and jvm. According to this article, it is possible to reduce 7-time buffer copys to 3-time in a input operation and 6-time to 4-time buffer copys in a output operation. There is sure to be an additional save by reducing switching cost between kernel mode and user modes.
http://developer.yahoo.net/blogs/hadoop/2009/08/the_anatomy_of_hadoop_io_pipel.html

When I saw a presentation "HBase goes realtime", the main point of which was the great achievement in performance , I was curious of what "Unjavafy everything" meant. I guess this sentence meant what the above proposal says. I am going to figure this out soon.

Sector/Sphere

2009-09-01T06:27:00.000-07:00

Sector/Sphere is another materialization of google's DFS and MapReduce framework. Sector and Sphere correspond DFS and MapReduce framework, respectively.

One thing interesting is that Sector/Sphere use UDT which is alternative transportation protocol based on UDP. UDT uses UDP to transfer bulk data with its own reliability control and congestion control mechanisms. It's called faster than TCP. I heard that Sector/Sphere is twice faster than Hadoop. I expect Hadoop will take UDT some day.

There are other different things compared to Hadoop. Even though Sphere looks after MapReduce, you can use your own function, not only map or reduce. In practice, when we analyse log data or do some calculation, the map and reduce chain is convenient, but sometimes become limitation to some extent. Sphere can alleviate this limitation.

check the following links out.
http://sector.sourceforge.net/index.htm

linux utility. `dislocate`

2009-08-31T22:11:00.000-07:00

It's like screen utility when you start a long-term batch job and leave your office, but you still want to continue the job even after the terminal is closed. Next morning you can check the result of the job.

`dislocate` has the ability you want to do. The program never die unless the system halts.

The only thing you need to do is just
$ dislocate `your command`
That's it.

check this out. You'll find funny to read this article.
http://wiki.tcl.tk/9263
http://expect.nist.gov/example/dislocate.man.html

But, I can't use ^D and ^Z command. I'm trying to figure out why.

Hadoop and Stress testing

2009-07-30T18:33:00.000-07:00

albeit hadoop is originally intended for data processing, I think there is another example of using it.

MapReduce is a sort of algorithm strategy to solve a problem with a vast amount of input. It adopts divide and conquer which slice a large problem example into many small examples so that we can alleviate high time complexity.

When we do a stress test, for example web server, we need to prepare a lot of computing power to make a huge stress. This means we want to have many concurrent tasks that make requests at the same time to the server. To do this, we need to split large input into slices for each task and run them parallel. This is exactly what MapReduce framework does.

The recipe is..
1. prepare input data in key, value format. If the source data is raw, we can run a mapreduce task to get normalized input data.
2. write codes for mapper and reducer. Reducers are going to make request to servers because we can specify the number of reducers in order that we control the degree of stress. we can't do this for mappers. Reducers should emit test results as key, value format. If test failes due to exception occurs, increase the customized error count. We can use various counts to keep track of the testing process. In addition, we can see what's going on with them by web pages of the job tracker.
3. submit the job. You can specify the number of reducers depending on how much stress you want to generate. However, due to physical limit of slaves' hardware there is certain point where no more reducers proceed concurrently. This is the maximum number of reducers making stress together. To make more, you need additional computing power.
4. run a mapreduce job to get statistical summary of the testing from result files.

I apply this method to test my server with 270 reducers on 9 nodes. I was able to use hundreds tasks since testing attempts are not CPU bound job, but IO(network) bound job. This works well even though there are some problems to figure out.

Now, I start to think I can make a stress testing framework on Hadoop. Hadoop has almost everything to do a stress test.

Levenshtein distance

2009-05-14T04:00:00.000-07:00

Lavenshtein distance shows a degree of how different two texts are. For example there are two texts, text1, text2.

text1 = kitten
text2 = sitting

Lavenshtein distance is 3 becuase it take 3 actions to turn text1 into text2.
1. substitute k with s resulting sitten
2. substitute e with i resulting sittin
3. add g at the end resulting sitting.

To compute Lavenshtein distance, we use dynamic programming skill.

This psuedo code is from wikipedia. Caculating the matrix to decide an action is the most important part.

If the "upper cell + 1" is the smallest one, it means it needs a insertion to mimimize the cost.
If the "left cell + 1"is the smallest one, it means it needs a deletion to minimize the cost.
If the "upper-left + cost" is the smallest one, the action depends on cost. If cost is zero, there is no action to take becuase the letters of i, j are match. If cost is one, a substitution takes place.

refer to the followings.

If we can transform s[1..i] to t[1..j-1] in k operations, then we can simply add t[j] afterwards to get t[1..j] in k+1 operations.
If we can transform s[1..i-1] to t[1..j] in k operations, then we can do the same operations on s[1..i] and then remove the original s[i] at the end in k+1 operations.
If we can transform s[1..i-1] to t[1..j-1] in k operations, we can do the same to s[1..i] and then do a substitution of t[j] for the original s[i] at the end if necessary, requiring k+cost operations.

int LevenshteinDistance(char s[1..m], char t[1..n])
// d is a table with m+1 rows and n+1 columns
declare int d[0..m, 0..n]

for i from 0 to m
d[i, 0] := i
for j from 0 to n
d[0, j] := j

for i from 1 to n
for j from 1 to m {
if s[i] = t[j] then
cost := 0
else
cost := 1
d[i, j] := minimum(
       d[i-1, j] + 1,     // insertion
       d[i, j-1] + 1,     // deletion
       d[i-1, j-1] + cost   // substitution
    )
}

return d[m, n]

http://en.wikipedia.org/wiki/Levenshtein_distance