Monday, August 24, 2009

ext4 filesystem

ext4 is the next "version" of filesystem after ext3. It was released with linux kernel version 2.6.28 which comes with ubuntu 9.04 (Jaunty).

Benefits of ext4 over ext3

  • Bigger filesystem and file sizes : ext3 supports 16TB of filesystem size and max file size of 2TB. And ext4 supports 1EB (10^18 bytes = 1024*1024 TB) of filesystem size and max file size of 16TB. Though you would never come across such huge storage system in desktop computers.

  • subdirectory limitations : ext3 allows "only" 32000 subdirectories/files in a directory. ext4 allows unlimited number of subdirectories.

  • Multiblock allocation : ext3 allocates 1 block (4KB) at a time. So if you write a 100 MB file you will be calling the ext3 block allocator 25600 times. Also this does not allow the block allocator to optimize the allocation policy because it does not know the total amount of data being allocated. Ext4 on the other hand used a multiblock allocator to allocate multiple blocks in a single go. This improves performance to a great extent.

  • Extents : Ext3 uses indirect block mapping scheme to keep track of each block for the blocks corresponding to the data of a file. Ext4 uses extents (contiguous physical blocks) that is to say that the data lies in the next n blocks. It improves performance and reduces file fragmentation

  • Delayed allocation : Ext3 allocates the blocks as soon as possible. Ext4 delays the allocation of physical blocks by as much as possible. Until then the blocks are kept in cache. This gives the block allocator the opportunity to optimize the allocation of blocks.

  • fast fsck : The total fsck time improves from 2 to 20 times,

  • journal checksumming : Ext4 checksums the journal data to know if the journal blocks are corrupted. Journal checksumming allows one to convert the two-phase commit system of Ext3's journaling to a single phase, speeding the filesystem operation up to 20% in some cases - so reliability and performance are improved at the same time.

  • "No Journaling" mode : in Ext4 depending on your requirements, the journaling feature can be disabled.

  • Online defragmentation : Ext4 supports online defragmentation. There is a e4defrag tool which can defrag individual files or even complete filesystems.

  • Inode related features : Larger inodes, nanosecond timestamps, fast extended attributes, inodes reservation

  • Persistent preallocation : Applications tell the filesystem to preallocate the space, and the filesystem preallocates the necessary blocks and data structures, but there is no data on it until the application really needs to write the data in the future.

  • Barriers on by default : This option improves the integrity of the filesystem at the cost of some performance. A barrier forbids the writing of any blocks after the barrier until all blocks written before the barrier are committed to the media. By using barriers, filesystems can make sure that their on-disk structures remain consistent at all times.



Now lets see the steps needed to convert your desktop filesystem from ext3 to ext4.


  • check the version of linux kernel. It should be > 2.6.28-11.
    jayant@gamegeek:~$ uname -a
    Linux gamegeek 2.6.28-15-generic #49-Ubuntu SMP Tue Aug 18 19:25:34 UTC 2009 x86_64 GNU/Linux

  • Just in case - take a backup of your important data

  • boot from live cd and run the following commands for converting the partition /dev/sda6 to ext4 from ext3.
    $ sudo bash
    $ tune2fs -O extents,uninit_bg,dir_index /dev/sda6
    $ e2fsck -pf /dev/sda6

  • Mount the partition and change its type entry in /etc/fstab
    $ mount -t ext4 /dev/sda6 /mnt
    $ vim /mnt/etc/fstab

    Change
    # /dev/sda6
    UUID=XXXXXX / ext3 relatime,errors=remount-ro 0 1
    To
    # /dev/sda6
    UUID=XXXXXX / ext4 relatime,errors=remount-ro 0 1

    Save the changes

  • Reinstall grub - this is optional. If you do not do this and you get a fatal error 13 while booting the machine, just boot using the live cd and run these commands.
    $ sudo bash
    $ mkdir /mnt/boot
    $ mount /dev/sda6 /mnt/boot
    $ grub-install /dev/sda --root-directory=/mnt --recheck



After the reboot you would be using the ext4 filesystem.

Important note : Your old files have not been converted to the ext4 technology. Only new files written to disk will use the ext4 technology. But since ext3 & ext4 are compatible, you wont face any problems accessing older ext3 files on disk. With usage the ext3 files will automatically disappear and get converted to ext4.

Saturday, August 15, 2009

Eyes!!!

Jai parked his old yellow bajaj priya scooter in the college's parking lot and took out his polythene containing his books. Since college, he had abandoned taking his books in bags. Bags are for school boys, not for college going big boys. He used to carry a single notebook and a pen in his polybag - simply to scribble during the lectures. He looked at his watch - it was already 11 AM and the first class was almost getting over. He was again late. He thought, why did he have to sit late in the night and read novels on his home PC. It was the same story everyday. Always missing the first lecture.

He walked into the college building and towards his class, and met some of the other late comers in the lobby. They were all waiting for the lecture to finish so that they could go and take their seats in the lecture room. Adi, one of his good friends said `The lecture is not that important`. Jai said `Ya, you would say that. You were also late`. Few other people were also strolling around. Others were sitting on the window slab and discussing girls. Girls tend to be the ususal topic during college times.

The topic of the new batch came in. Someone said `Heard that the cutoff for admission to medical has gone up to 97%`. In those days the admissions in Gujarat based universities used to happen on merit basis. So whatever your score was in the 10+2 exams could decide your future. People used to go to tutions after school for extra coaching. Jai asked `What was the cutoff for computer science?`. That was the branch we were all in. Adi answered `I think it was 95%`. The percentage marks was calculated only for four subjects - Physics, Maths, Biology and Chemistry. Medical seats were the first to get filled up, followed by Chemical - due to the fact that there were a lot of chemical jobs in Gujarat. And then there were Electronics and Computers which got filled up next.

And the topic shifted to the new batch which came in last year. Jai and his friends were now in the third year of their graduation. After feasting their eyes on the girls in their own batch they were now tired and were craving for something new. There was this saying that the girls in the batch one year junior to them were good.

'Have you heard about the girl nikita' Adi asked.
'No, what about her?' Jai answered.
'She is supposed to be a bombshell' Adi answered.
'What yaar? Every good looking girl is a bombshell. What is so special about her?' Jai asked again.
'Man you got to see her to believe her beauty' Adi said.
'Now you have got me interested. What is so good about her - figure, hair ?' Jai presses again to get a vulgar description of the girl.

But it seems that even Adi had not looked at that girl. He had just heard about her. Else he would have gone ahead and gave a complete inch by inch description of the girl.

The bell rang and we went up the stairs to stay out of site of the teacher whose class we had bunked (or missed). We saw the professor go out followed by a bunch of 'intelligent' students asking him questions.

'Trying to impress the prof' - Adi commented
'Well, they make marks by impressing the prof. We should follow in their footsteps' - Jai said.
'To hell with marks. What they want are better recomendations, so they could pursue their MS in US? Do you want to go to US?' - Adi said
'Firstly man, i dont want to study further. I am tired of studying. And secondly, I think it is a waste of money to go to US? You might be at the same level if you have 2 years experience. And lastly, my family does not have enough money to send me to US and i do not want to take a loan for studying' Jai explained.
'I know, i know, lets get into class' - Adi said.

And we got into the class. The last benches were the best. Teachers rarely saw what was happening on the last benches. Some were finishing off their practical journals. Others were simply making doodles. It was the attendance that mattered. Attendance was required to be eligible to give exams.

So how did those guys make the exams when they did not actually "Attend" the class. Mostly simply got the syllabus and studied on their own. They used to get a one month leave for preparing for their exams. And that was enough to sail through the exams.

After 2 boring lectures, there was a half hour lunch break. And we all moved down to the canteen. Jai and Adi went from the back entrance - which was actually a thin wall. After 2 years of trying to cross it without losing their balance, they had now perfected their skill. Adi ran over the wall and Jai followed. Both landed in the Canteen.

The canteen was a huge shed covered with tin. There were cemented tables where one could simply stand and have their food. The food was ok. One can get anything ranging from pakodas to rice and dal here. Jai and Adi were deciding what to have, when someone said 'Look there's nikita'. And we all turned around. She was ordering something from the counter. 'Let me get pakodas and coke' Jai said. And rushed over to the counter.

What Jai saw, amazed him. Nikita was just like a common girl. Nothing great about her. Ofcourse she had a okie figure - nothing great or out of proportion. Hair to her shoulders. She was wearing normal stuff - nothing too revealing or fashionable. Her hair was tied in a ponie.

'One plate pakodas and a coke' - Jai ordered.

And she turned around and looked directly at Jai. Jai stopped breathing for a couple of seconds - while she looked at him. And then she took her order and left. Jai was mesmerized.

'20 Rs.' - Said the canteen boy and shook Jai.
'Wow!!' - said Jai and rushed back with pakodas and coke to Adi.

'Oh God!!, she is beautiful' said Jai, 'Lets move closer to her table'.
And they moved closer to her table to overhear what she was saying.

'So,' Adi said, 'What is so good about her?'
'Her eyes man' - Jai answered, 'I have never seen eyes like that. She has brown eyes and they are huge and deep. You could stare at them for a couple of seconds and you could get lost. It is not that i have not seen good eyes. I have seen blue eyes, black eyes and even foggy eyes, really big eyes. But, she has the eyes that could beat all of them - even the best one of them. I dont know where she got them. Otherwise she is a normal girl'.

'Oh!' - Adi shows his realization.
'But man you have to see them to believe them. I am sure i could never forget those eyes. I have never seen eyes like that, and I am sure i would never ever see eyes like those' - Jai repeats.
'Maybe she is wearing contacts' Adi says.
'No yaar, those eyes were real. Even colored contacts could not be that beautiful' - Jayant says.
'But man, do you want ahead and try to be friends with her? I think she has a boyfriend though.' - Adi asks.
'I think she sounds quite dumb.' Said Jai after overhearing to Nitika's conversation for some time. 'I would prefer intelligence over beauty'
'Well, then you have a long way to look - cause beauty and brains and compatibility is a very rare match' - Adi explains.

They finish their lunch and head back to the classes for more lectures. The eyes that Jai had seen stays embedded within his mind - and he may dream about them.

Tuesday, August 11, 2009

Document oriented data stores

A document oriented database or data store does not use tables for storing data. It stores each record as a document with certain characteristics. So a multiple documents in this type of store can have different characteristics - which means different number of fields per record and different fields per row. The benefit would be that if you are using a document oriented database for storing a large number of records in a huge database, any change in the number or type of row does not need an alter on the table. All you need to do is insert new documents with new structure and it is automatically inserted to the current datastore.

I went ahead and tried comparing some document-oriented data stores - TokyoTyrant, MongoDb and CouchDb and i compared them to Mysql-5.4 as well to get an idea about the performance advantage.

I created 3 scripts in all - 2 for insert and 1 for select. And created a 50,00,000 record table with a very normal record structure

field1 -> string, indexed
field2 -> string, indexed
date -> date, not indexed
n -> integer, indexed

The size of the original mysql table was 214 MB data & 205 MB index - total 419 MB for 50,00,000 records. The 3 scripts could be described as follows


  • insert script 1 : went from 1 to 25,00,000 pulling 1000 records in a single query from the source database and inserting the records one by one to the target data store.

  • insert script 2 : went from 50,00,000 to 24,99,999 pulling 1000 records in a single query from source database and inserting the records one by one to the target data store.

  • select script : picks records from the source database and makes 2 queries for both field1 & field2 and fires both the queries on the target data store.



Test Machine configuration:

CPU : Intel Xeon 1.6 GHz - Quad Core [4 MB L2 cache] 64 Bit
Memory : 8 GB RAM
OS : Centos 5.2 - Kernel 2.6.18 64 bit


Mysql

Used mysql version 5.4
Load during execution : 3.5
Time taken by Insert script 1 : 19682.673708916 sec for 2501000 records
Time taken by Insert script 2 : 19608.902073145 sec for 2499000 records
Time taken by Select script : 20465.380266905 sec for 8099782 records
Table engine : MyISAM
Total database size in mysql 5.4 : 215+233 = 248 MB

Ofcourse i used MyISAM which resulted in table locks, and i had indexes on three fields which resulted in increased locking times on these tables during inserts & selects.

MongoDB - www.mongodb.org

Used version for testing : 0.9.1
The current version available is 0.9.7 which has a lot of bug fixes and performance improvement features.MongoDB is written in C++ and stores data in BSON format which is Binary Serialization of JSON documents. It has a console (similar to mysql) which can be used to fire queries - so unlike bdb, you dont have to go and write programs to fire queries. MongoDB has full indexing support for different columns. You can also do query profiling (like explain in mysql) to check the execution path of the query and then make optimizations if possible. It provides replication support. It can be used to store large binary data like videos very efficiently.

The one good thing about the future of mongodb is that it would be providing auto sharding of data for cloud level scalability. This feature is in alpha stage now, but it should be mature in some time and could be used then.

Mongodb provides drivers/apis for a lot of languages including python, php, java, ruby, c++ and perl. I downloaded the php driver and compiled it and installed the extension mongo.so in the php extentions directory. And then i ran the same tests to check out the speed of mongodb.

Load during execution : 2.5
Time taken by Insert script 1 : 1006.6038348675 sec for 2501000 records
Time taken by Insert script 2 : 1435.0536739826 sec for 2499000 records
Time taken by Select script : 2942.2539789677 sec - 9999914 records
Total database size in mongodb : 4 GB (both data & index)

Wow, so Mongodb turns to be approximately 16 times faster than simple mysql - MyISAM tables

But it takes up a huge amount of space. Why is that? Well, Mongodb creates data files with predefined sizes so that it does not have to increase or decrease the file size as per requirements. The first file it creates is of 64MB, the next file is 128MB etc. upto 2GB. After 2GB the remaining files are of 2GB only. So, even if we exceed a byte above the current file of 2GB, another file of 2GB will be created - even if it is 98% empty.

Another important fact about mongodb is that mongodb's storage engine uses memory-mapped files for performance. This limits the data size on a 32 bit machine to around 2GB. I had hit this limitation earlier so i used a 64 bit machine for testing. But this architecture of data files in
mongodb storage engine allows the code to be much plain and simple and open to embrace the 64 bit world. Mongodb does not support traditional locking which is another reason it is fast.

More info / References :
32 bit limitation => blog.mongodb.org/post/137788967/32-bit-limitations
performance testing => www.mongodb.org/display/DOCS/Performance+Testing
regarding mongodb => www.mongodb.org/display/DOCS/Home
Quickstart => www.mongodb.org/display/DOCS/Quickstart
Production deployments => www.mongodb.org/display/DOCS/Production+Deployments
Locking in mongodb => www.mongodb.org/display/DOCS/Atomic+Operations

Tokyo Cabinet/Tyrant

Tokyo Tyrant is a set of 3 applications
- tokyo cabinet : the embedded data store
Tokyo Cabinet => tokyocabinet.sourceforge.net/spex-en.html
- tokyo tyrant : network api
Tokyo Tyrant => tokyocabinet.sourceforge.net/tyrantdoc/
- tokyo dystopia : fulltext search system
Tokyo Dystopia => tokyocabinet.sourceforge.net/dystopiadoc/

I explored tokyo cabinet-1.4.29 & tokyo tyrant-1.1.30. So after installing tokyo cabinet, I had to go ahead and install tokyo tyrant on top of tokyo cabinet for the networking support. Tokyo tyrant provides a set of binaries for talking to the tokyo cabinet embedded database. So you can use tokyo tyrant to insert and select data from a tokyo cabinet server.

I got an api for php to interact with the tokyo tyrant server. It is known as Php Tyrant and it can be obtained from mamasam.indefero.net/p/tyrant/. It is written completely in php and is not a C extension.

If you go through the documentation, you would see that Tokyo cabinet supports majorly 4 types of databases.

Hash database - a key value store which uses hash algorithm to retrieve records. The time complexity in this case is constant [ O(1) ].
B+ tree database - a B+Tree is slower than the hash database. Records of a B+Tree are sorted and arranged in logical pages. So the time complex
ity of record retrival is O(log n). But the size of a B+Tree database is half of a hash database.
Fixed length database - It is faster than a hash database. But it has a restriction that each key has to be a natural number and the length of
each value is limited. The whole region of the database is mapped to memory by the mmap call - which reduces overhead related to file I/O.
Table database - It is close to a document oriented database than a key value pair. You can also form indexes on columns in the table to improve search and sorting performance. Indices are implemented as different files of B+Tree database.

So, i created a simple table database with the structure i wanted and created indexes on the required columns. And started running my scripts. But i found that tokyo cabinet is fast in the beginning, but it suffers from file locks. So any operation happening on the table locks the comp
lete file. This caused a lot of problem with simultaneous inserts & selects. In fact i had cases where the server stopped responding totally. And it took 1 hr 17 minutes to push in just 661 inserts & fire 270 selects. So i stopped running the select script and focused on running multiple insert scripts. And then ran the select script separately.

This says that if you go ahead implementing tokyo tyrant on a huge table, you should be aware of the file locks and hence should implement the selects on a slave of the main database. A master can handle multiple inserts while a slave can handle multiple selects. Or you form a queue for firing queries sequentially instead of simultaneously.

I ran 2 insert scripts simultaneously and the results were even worse then mysql.

Load during execution : 2.9
Time taken by Insert script 1 : 65671.21945715 sec for 2501000 records
Time taken by Insert script 2 : 63807.51564312 sec for 2499000 records
Total database size : 1095 MB [715 MB data + 380 MB index]

And i ran 2 select scripts simultaneously and the results were comparable to that of mysql.

Load during execution : 2.1
Time taken by Select script 1 : 20269.342120886 sec for 9999914 records
Time taken by Select script 2 : 20115.848437071 sec for 9999914 records

What could be said about tokyo tyrant is that it should be used as a key-value store - maybe by using a hash database or a fixed length database for persistent session storage.

Couchdb
couchdb.apache.org/

The third database i looked into was couchdb. Which i had heard a lot about. The good thing about couchdb is that it provides a RESTful JSON API that can be accessed from any environment that allows HTTP requests. Couchdb is written in erlang and is quite fast. Again it does not have a c extention. There is a php api known as phpillow which wraps all functionalities of couchdb in its function calls.

You can download phpillow at arbitracker.org/phpillow.html

Also note that it works only with php 5.3. With php 5.2.x it still has a lot of bugs. Firstly there is no proper documentation, so it took me some time to figure out how to write insertion and select scripts and how to go about creating views (couchdb calls indexes as views). When i ra
n the scripts i found that it was crashing a lot. So, i did not go ahead with a proper testing of couchdb. Couchdb also supports master master replication (with developer supplied conflict resolution).

You could go ahead and read the comparison of couchdb & mongodb at mongodb's page

www.mongodb.org/display/DOCS/Comparing+Mongo+DB+and+Couch+DB
www.mongodb.org/display/DOCS/MongoDB%2C+CouchDB%2C+MySQL+Compare+Grid

Saturday, August 08, 2009

Why should we watch movies at home


  • Because movies@home are free - thanks to piracy

  • You do not have to adjust your schedule according to the movie timings. The movie timings adjusts to your schedule

  • You do not have to drive all the way to the movie hall

  • You do not have to search for parking and even pay for it

  • You do not have to stand in queue for tickets

  • In case you had not booked the tickets in advance, you do not have to get disappointed because the tickets are not available

  • You do not have to stand in queue for entry and get frisked by the guard

  • You do not have to wait outside the movie hall - in heat and croud and without a place to sit

  • You do not have to walk slowly with the crowd and take your seats - seats which were previously occupied by someone else - who had left popcorn and god knows what else on it

  • You do not have to pay for popcorn - which might not be good. Home made popcorns are really good

  • At home you do not have to watch the complete movie if it is crap.

  • You can leave the movie incomplete - and still feel no guilt about it - cause it was free

  • You can fast-forward the crappy scenes and time-pass songs. You don't have to bear them if you do not want to.

  • And you can pause the movie if you need to attend a nature's call. You do not have to wait for an interval to attend nature's call or risk missing an important scene.

  • And eventually you can avoid swine flu - by avoiding contact with so many people at the movie hall

  • And also save yourself from any terrorist attack - which cannot happen at your home



I am still unsure why people go to halls to watch movies. Today's halls have screens which resemble a huge LCD TV. In the past the halls had the charm of huge screens and balcony seats. It made more sense to watch movies at movie halls at those times.

Wednesday, August 05, 2009

12 Angry Men

I am referring to the movie 12 Angry Men [imdb rating 8.9].

I keep on searching and downloading movies which suit my fancy - mostly horror, comedy, action, thrillers. Lots of times when i had been to the top 250 list on imdb, i had seen this movie at the top. Also when i had searched for top movies, this was on the list.

But when i read about the plot and the synopsis of the movie - it told me that there are 12 men in a room discussing talking to each other about some murder trial - it seemed quite boring. And on top of it - the complete movie is in black & white (not even eastman color).

But some days ago a friend of mine highly recommended this movie to me. So, i thought what the heck, we should watch old B/W movies as well - they are good - even if it is about 12 men sitting in a room and talking to each other - no action whatever...

So, with a "lets get it over with" attitude, i sat down to watch the movie. And it turned out to be very good. 12 men inside a room can make wonders happen. The concept is very simple, but the way it is portrayed is just wow!!!.

A must watch...