yasemin's notes

How to get a bricked kindle fire back to live

2012-01-23T23:01:00.000-08:00

I've rooted my kindle fire and then started playing with /system/build.prop file to get any app I wanted from android market. However I ended up with a bricked KF - it was stuck at the kindle fire logo.

I thought "luckily I've backed up the build.prop file, so I can just copy it back". But the process I went through wasn't that easy.. It took me a while to figure out how to revert build.prop file.

Here are the steps I followed t get KF back to live again:

1. First of all download latest android-sdk tools. This comes with ./adb and ./fastboot which will be your main tools to access KF.

# see all options
./adb --help  

# Common commands
./adb kill-server #kills
./adb devices #searches for devices
./adb shell  #goes to FK linux shell
./adb push from_file_dir_in_pc to_file_dir_in_kf

2. Next, make sure KF is recognized. Go to KF shell and type su. If moves to # shell, great, you have root permissions. Move to step 4. If there is an error eg. segmentation fault, then move to step3.

3. Download fastboot, copy it to KF and execute. Then reboot and go to KF shell again. This time you should have root permissions. Try su. Refer to this post for further details.

$ ./adb push fbmode /data/local/tmp
$ ./adb shell chmod 755 /data/local/tmp/fbmode
$ ./adb shell /data/local/tmp/fbmode
$ ./adb reboot
$ ./adb shell
  $ su

4. At this point, you should have root permissions and can just go ahead and revert changes in build.prop. Copy stock build.prop in your work directory if does not exist. Download here.

$ ./adb push build.prop /system/

5. Next, follow instructions here. In my case, ./fastboot command never recognized the device and I ended up in cwm-based recovery screen. Since KF has only one button, I was only able to pick the first choice in each screen. At the beginning, this option is "install update" and in the next screen it is a "NO". So "install update" option looks for an update.zip file under /sdcard/ and then just installs if the file is there - even though you have to pick "NO" in the confirmation screen.
So to do this, first download the update.zip file here. Then just click on the power button on KF twice to install. Once installation is completed, reboot the KF.


# Copy update.zip to KF 
$ ./adb push update.zip /sdcard/
# Push on the reboot button twice to install.
# Once installed, reboot the KF.
$ ./adb reboot

And, it's done, the KF is back!

How to get android app store apps on kindle fire

2011-11-28T22:06:00.001-08:00

It was not happy to realize that kindle fire does not allow access to android market place. Probably this is a well thought out marketing strategy of Amazon, but if you're tired of keep being redirected to "can not find app" message and don't want to root your kindle, keep reading :)

The default kindle fire browser (Silk) redirects all android market links to amazon app store. After googling a little bit, idea of getting another browser and using that to access android market seemed like to be a smart way. I tried accessing via dolphin - but failure, still redirect to amazon app store (btw - give a try to dolphin if you haven't done yet, it is a pretty cool browser.). So I'm left with the last option, sideloading apps through third parties such as freewarelovers.com and getjar.com. Just search for the apps online, download the apk file, and click on it to install. Before installing, make sure "allow applications from unknown sources" option is enabled through Settings->Device.

Scalable Manipulation of Archival Web Graphs

2011-11-08T20:18:00.000-08:00

I was working on archival web graphs till last June. Actually, most of the Hadoop related posts on this blog are things I learned while working on this project.

We looked at the problem of processing large-scale archival web graphs and generating a simple representation for the raw input graph data. This representation should allow the end user to be able to analyze & query the graph efficiently. Also, the representation should be flexible enough - so it can be loaded into a database or can be processed using distributed computing frameworks, ie. Hadoop.
To achieve these goals, we developed a workflow for archival graph processing within Hadoop. This project is still going on and its current status has appeared at LSDS-IR '11 workshop at CIKM conference last month. I like to share the paper for those who are interested in further details. The abstract is following:

In this paper, we study efficient ways to construct, represent and analyze large-scale archival web graphs. We first discuss details of the distributed graph construction algorithm implemented in MapReduce and the design of a space-efficient layered graph representation. While designing this representation, we consider both offline and online algorithms for the graph analysis. The offline algorithms, such as PageRank, can use MapReduce and similar large-scale, distributed frameworks for computation. On the other side, online algorithms can be implemented by tapping into a scalable repository (similar to DEC’s Connectivity Server or Scalable Hyperlink Store by Najork), in order to perform the computations. Moreover, we also consider updating the graph representation with the most recent information available and propose an efficient way to perform updates using MapReduce. We survey various storage options and outline essential API calls for the archival web graph specific real-time access repository. Finally, we conclude with a discussion of ideas for interesting archival web graph analysis that can lead us to discover novel patterns for designing state-of-art compression techniques.

Also, the source code for "graph construction algorithm" is open sourced at GitHub.

Setting up EC2 Command Line Tools (API Tools)

2011-10-09T22:21:00.000-07:00

Download the latest version of EC2 API from AWS website and unzip. All APIs are under the bin. Setting up the $EC_HOME It's better to add this directory to your $PATH. Here is how:

export EC2_HOME=/Users/yasemin/My-Apps/ec2-api-tools
export PATH=$PATH:$EC2_HOME/bin

Next is setting up the credentials for the aws account. Create & download a private key and the corresponding certificate from the account's "security credentials" page and link these files to EC2 CLI. Here is how:

export EC2_PRIVATE_KEY=/Users/yasemin/My-Apps/ec2-api-tools/credentilas/pk-HKZYKTAIG2ECMXYIBH3HXV4ZBZQ55CLO.pem 
export EC2_CERT=/Users/yasemin/My-Apps/ec2-api-tools/credentilas/cert-HKZYKTAIG2ECMXYIBH3HXV4ZBZQ55CLO.pem

This is all - you should be good to go!
Notes:
- If the export commands are appended to ~/.bashrc file, then they will be executed automatically with every new bash session - which is nice to have.
- For detailed setup instruction, please see the official docs.- Make sure $JAVA_HOME is also set. Use '$ which java' to figure out the current path.

S3 Access

2011-09-08T19:06:00.000-07:00

Two ways to access your S3 buckets: jets3t and s3cmd. Jet3set provides UI and s3cmd is only UI.
Here is how to get a file using s3cmd:First configure the account:

s3cmd --configure

Then, you can use s3cmd to access your buckets. eg: downloading a folder from s3:

s3cmd get --recursive s3://bucket_name/object_name to_local_file

Mysql command line basics

2011-09-08T14:25:00.000-07:00

show databases;
use db_name; 
show tables; 
describle table_name;

These will get you enogh info to run your real SQL command..
The other way is just to use the UI app eg. MySQL Query Browser

bash alias and colorful ls

2011-09-02T14:01:00.000-07:00

Everything below should go under ~/.bashrc


alias la='ls -la'
alias gopen='gnome-open'
alias gterminal='gnome-terminal'
alias ls='ls --color'

PS1="\`if [ \$? = 0 ]; then echo \e[33\;40m\\\^\\\_\\\^\e[0m; else echo
\e[36\;40m\\\-\e[0m\\\_\e[36\;40m\\\-\e[0m; fi\` \w> "

NOTE: Make sure alias comes after PS1. PS1 is for cutom prompt.

How to pass job specific parameters in Hadoop

2011-06-20T19:03:00.000-07:00

Say there is a parameter your mapper or reducer needs, and it is desirable to get this parameter from the user at the beginning of the job submission. Here is how to use "Configuration" to let the user set the parameter:

public class GenericReplace {



   public static final String IS_KEY_FIRST = "IsKeyFirstInMapFile";



   public static class GenerateLinks extends Mapper {



      public void map(Text key, Text value, Context context)  {

         if (context.getConfiguration().getInt(IS_KEY_FIRST, 1)) {

              //do this .. 

         }

         else{

              //do that .. 

         }

      }

   }



   public static void main(String[] args) throws Exception {



   Configuration conf = new Configuration();

   GenericReplace.graphPath = args[0];

   GenericReplace.outputPath = args[1];

   conf.setBoolean(IS_KEY_FIRST , Boolean.getBoolean(args[3]));

   Job job = Job.getInstance(new Cluster(conf), conf);

   ...

   }

}

Ways to write & read HDFS files

2011-06-20T10:10:00.000-07:00

- Output Stream

FSDataOutputStream dos = fs.create(new Path("/user/tmp"), true); 
dos.writeInt(counter); 
dos.close();

- Buffered Writer/Reader

//Writer
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(fs.create(new Path("/user/tmp"), true)));
bw.write(counter.toString());
bw.close();

//Reader
DataInputStream d = new DataInputStream(fs.open(new Path(inFile)));
BufferedReader reader = new BufferedReader(new InputStreamReader(d));
while ((line = reader.readLine()) != null){
...
}
reader.close();

- SequenceFile Reader and Writer (I think most preferable way for Hadoop jobs):

//writer
SequenceFile.Writer writer = SequenceFile.createWriter(fs, conf, new Path(pathForCounters, context.getTaskAttemptID().toString()), Text.class, Text.class);
   writer.append(new Text(firtUrl.toString()+"__"+ context.getTaskAttemptID().getTaskID().toString()), new Text(counter+""));
   writer.close(); 

//reader
SequenceFile.Reader reader = new SequenceFile.Reader(fs, new Path(makeUUrlFileOffsetsPathName(FileInputFormat.getInputPaths(context)[0].toString())),  conf);
   while (reader.next(key, val)){
    offsets.put(key.toString(), Integer.parseInt(val.toString()));
   }

Hadoop - how to get job output path using context

2011-06-19T13:29:00.001-07:00

FileOutputFormat.getOutputPath(context)

How to ensure each key in Reducer has sorted iterator ?

2011-06-14T14:11:00.000-07:00

There are three properties control how values are partitioned and sorted for reducer's consumption. As mentioned at riccomini's blog Owen O'Malley explains with a very simple & nice example. By default intermediate pairs are partitioned using the key. To manipulate this behavior, custom Partitioner can be defined.

Once we ensure pairs belonging to same partition are sent to the same reducer, now there are two functions take care of their ordering and grouping of keys in each partition/reducer.
setOutputKeyComparatorClass defines the sort order of the keys and setOutputValueGroupingComparator defines the groups, which pairs will be grouped together to process once. Order of values at the reducer's iterator can be set using combination of these two.

public static class RemoveIdentifierAndPartition extends Partitioner< Text, Writable > {

  @Override
  public int getPartition(Text key, Writable value, int numReduceTasks) {
   return (removeKeyIdentifier(key.toString()).hashCode() & Integer.MAX_VALUE) % numReduceTasks;
  }
 }

 public static final class SortReducerByValuesValueGroupingComparator implements RawComparator< Text >  {
     private static Text.Comparator NODE_COMPARATOR = new Text.Comparator();

     @Override
     public int compare(Text e1, Text e2) {
         return e1.compareTo(e2);
     }

     @Override
     public int compare(byte[] b1, int s1, int l1, byte[] b2, int s2, int l2) {

         // skip last 2 bytes ( space 1 / space 2)
         
         int skip = 2;
         int stringsize1 = 0;
         int stringsize2 = 0;

         // compare the byte array of Node first
         return NODE_COMPARATOR.compare(b1, s1 , l1-skip, b2, s2 , l2-skip);
     }
 }

How to set number of Maps with Hadoop

2011-06-14T13:31:00.000-07:00

Setting number of map tasks is not simple like the reduce tasks. User can not explicitly give a fixed number, FileInputFormat decides how to split input files using various parameters.

First one is isSplitable, determines whether file is splittable or not.
Next three variables, mapred.min.split.size, mapred.max.split.size, dfs.block.size determine the actual split size used if input is splittable. By default, min split size is 0 and max split size is Long.MAX and block size 64MB. For actual split size; minSplitSize&blockSize set the lower bound and blockSize&maxSplitSize together sets the upper bound. Here is the function to calculate:

max(minsplitsize, min(maxsplitsize, blocksize))

Note: compressed input files (eg. gzip) are not splittable, there are patches * * available.

Java BitSet Size

2011-04-24T12:16:00.000-07:00

Java BitSet could be described as bit array. It holds certain of bits.
What we used to see is a constructor with a size value as argument returns an object with that size. However BitSet(int nbits) constructor does not work this way. Here is the description from JavaDocs:

Creates a bit set whose initial size is large enough to explicitly represent bits with indices in the range 0 through nbits-1.

Indeed length of the object is equals to or bigger than specified value.

BitSet set = new BitSet(1);
System.out.println(set.size()); //64
BitSet set = new BitSet(10);
System.out.println(set.size()); //64
BitSet set = new BitSet(65);
System.out.println(set.size()); //128

It seems like BitSet constructor sets the size to closest 2^n value starting with n=6.

Hadoop - Incompatible namespaceIDs Error

2011-04-21T18:13:00.000-07:00

After formatting the namenode, restarting Hadoop fails - more specifically namenode does not start with Incompatible namespaceIDs Error.

bin/hadoop namenode -format
..
bin/start-dfs.sh
..
ERROR org.apache.hadoop.hdfs.server.datanode.DataNode:
  java.io.IOException: Incompatible namespaceIDs in /hadoop21/hdfs/datadir: 
  namenode namespaceID = 515704843; datanode namespaceID = 572408927
  ..

Why? -datanodes have the old version number after formatting the namenode.
Solution? - hacking in to <hdfs-data-path>/datadir/current/VERSION file and changing the version number with the new one (which is 572408927 in this example) solves the problem. Make sure to change it for every data-node in the cluster.

WARNING: most probably you will be loosing the data in HDFS. even though it is not deleted, not accessible with the new version.

To avoid such a boring case, be careful before formatting. Take a look at this

Hadoop MultipleOutputs

2011-04-19T13:08:00.000-07:00

Want to generate various types of output files. For example, I have a huge linkgraph with includes timestamp and the outlink information. I want put these two constrains into seperate files. Here is how to use MultipleOutputFormat for this purpose:

public static class FinalLayersReducer extends Reducer<IntWritable, Text, WritableComparable,Writable> 
{
     public void setup(Context context) 
     {
          mos = new MultipleOutputs(context);
     }
  
     public void reduce(IntWritable key, Iterable<text> values, Context context) throws IOException, InterruptedException {
          for ( Text val : values) {
          // some sort of a computation ..
          }
          mos.write("outlink", key, outlink_text);
          mos.write("timestamp", key, timestamp_text);
     }

     protected void cleanup(Context context) throws IOException, InterruptedException {
          mos.close();
     }
}

public static void main(String[] args) throws Exception {

     Job job = new Job(conf, "prepare final layer files");
     
     // other job settings ..

     MultipleOutputs.addNamedOutput(job, "outlink", TextOutputFormat.class , IntWritable.class, Text.class);
     MultipleOutputs.addNamedOutput(job, "timestamp", TextOutputFormat.class , IntWritable.class, Text.class);
}

Facing zero sized output files OR lines in the 2 separate outputs do not match when they supposed to OR can not unzip the output files -> these are signs are telling that you forget to close() the MultipleOutputs object at the end - in the cleanup() function.

Hadoop Intermediate Data Compression

2011-04-18T20:49:00.000-07:00

To enable intermediate data compression, setup corresponding variables in mapred-site.xml.

<!-- mapred-site.xml -->   
<property>
    <name> mapreduce.map.output.compress </name> 
    <value> true</value> 
</property>
<property>
    <name>mapreduce.map.output.compress.codec</name>
    <value>org.apache.hadoop.io.compress.GzipCodec</value>
</property>

Setting up LZO compression is a bit tricky. First of all, should install LZO package on all nodes. I built this package and followed instructions here.

Having difficulty while building eg: "BUILD FAILED make sure $JAVA_HOME set correctly." - then take a look at here.

At the end, this is how my config files look like:

<!-- mapred-site.xml -->
<property>
    <name> mapreduce.map.output.compress </name> 
    <value> true</value> 
</property>
<property>
    <name>mapreduce.map.output.compress.codec</name>
    <value>com.hadoop.compression.lzo.LzoCodec</value>
</property>

<!-- core-site.xml -->
<property>
    <name>io.compression.codecs</name>
    <value>org.apache.hadoop.io.compress.GzipCodec,org.apache.hadoop.io.compress.DefaultCodec,com.hadoop.compression.lzo.LzoCodec,com.hadoop.compression.lzo.LzopCodec,org.apache.hadoop.io.compress.BZip2Codec</value>
</property>
<property>
    <name>io.compression.codec.lzo.class</name>
    <value>com.hadoop.compression.lzo.LzoCodec</value>
</property>

To compress final output data, Job object should be set to output compressed data before its execution.

Compressing Hadoop Output usinig Gzip and Lzo

2011-04-18T20:29:00.000-07:00

In most of the cases, writing out output files in compressed format is faster - less amount of data will be written. To have a faster computation, compression algorithm should perform well - so time is saved even though there is an extra compression time overhead.

Compressing regular output formats with Gzip, use:

job.setOutputFormatClass(TextOutputFormat.class);
TextOutputFormat.setCompressOutput(job, true);
TextOutputFormat.setOutputCompressorClass(job, GzipCodec.class);
...

For Lzo Output compression, download this package by @kevinweil. Then following should work:

job.setOutputFormatClass(TextOutputFormat.class);
TextOutputFormat.setCompressOutput(job, true);
TextOutputFormat.setOutputCompressorClass(job, LzoCodec.class);
...

In terms of space efficiency, Gzip compresses better. However, in terms of time Lzo i smuch faster. Also, it is possible to split Lzo files, splittable Gzip is not available.
Keep in mind that these two techniques will only compress the final outputs of a Hadoop job. To be able to compress intermediate data, parameters in mapred-site.xml should be configured.

LZO build problem

2011-04-11T11:02:00.000-07:00

Trying to built the lzo library for Hadoop, it failed with "make sure $JAVA_HOME" set correctly message. Here is the full error log:

....     
   [exec] checking jni.h usability... no
   [exec] checking jni.h presence... no
   [exec] checking for jni.h... no
   [exec] configure: error: Native java headers not found. 
   Is $JAVA_HOME set correctly?
BUILD FAILED make sure $JAVA_HOME set correctly.

This means build is using incorrect java installation. To make sure JAVA_HOME is pointing to the correct one use apt-file search - searches in all packages installed in your system.

apt-file search jni.h

And then set JAVA_HOME accordingly.

Common Hadoop HDFS exceptions with large files

2011-04-11T10:41:00.000-07:00

Big data in HDFS, so many disk problems. First of all, make sure there are at least ~20-30% free space in each node. There are two other problems I faced recently:

all datanodes are bad
This error could be cause because of there are too many open files. limit is 1024 by default. To increase this use

ulimit -n newsize

For more information click!

error in shuffle in fetcher#k
This is another problem - here is full error log:

2011-04-11 05:59:45,744 WARN org.apache.hadoop.mapred.Child: 
Exception running child : org.apache.hadoop.mapreduce.task.reduce.Shuffle$ShuffleError: 
error in shuffle in fetcher#2
 at org.apache.hadoop.mapreduce.task.reduce.Shuffle.run(Shuffle.java:124)
 at org.apache.hadoop.mapred.ReduceTask.run(ReduceTask.java:362)
 at org.apache.hadoop.mapred.Child$4.run(Child.java:217)
 at java.security.AccessController.doPrivileged(Native Method)
 at javax.security.auth.Subject.doAs(Subject.java:416)
 at org.apache.hadoop.security.UserGroupInformation.doAs(UserGroupInformation.java:742)
 at org.apache.hadoop.mapred.Child.main(Child.java:211)
Caused by: java.lang.OutOfMemoryError: Java heap space
 at org.apache.hadoop.io.BoundedByteArrayOutputStream.(BoundedByteArrayOutputStream.java:58)
 at org.apache.hadoop.io.BoundedByteArrayOutputStream.(BoundedByteArrayOutputStream.java:45)
 at org.apache.hadoop.mapreduce.task.reduce.MapOutput.(MapOutput.java:104)
 at org.apache.hadoop.mapreduce.task.reduce.MergeManager.unconditionalReserve(MergeManager.java:267)
 at org.apache.hadoop.mapreduce.task.reduce.MergeManager.reserve(MergeManager.java:257)
 at org.apache.hadoop.mapreduce.task.reduce.Fetcher.copyMapOutput(Fetcher.java:305)
 at org.apache.hadoop.mapreduce.task.reduce.Fetcher.copyFromHost(Fetcher.java:251)
 at org.apache.hadoop.mapreduce.task.reduce.Fetcher.run(Fetcher.java:149)

One way to go around this problem is making sure there are not too many map tasks for small input files. If possible you can cat input files manually to create bigger chunks or push hadoop to combine multiple tiny input files for a single mapper. For more details, take a look at here.

Also, at Hadoop discussions groups, it is mentioned that default value of dfs.datanode.max.xcievers parameter, the upper bound for the number of files an HDFS DataNode can serve, is too low and causes ShuffleError. In hdfs-site.xml, I set this value to 2048 and worked in my case.

<property>
        <name>dfs.datanode.max.xcievers</name>
        <value>2048</value>
  </property>

Update: Default value for dfs.datanode.max.xcievers is updated with this JIRA.

how to remove unnecessary scrollbar from syntaxhighlighter code

2011-04-04T14:44:00.000-07:00

I've been looking for how to remove annoying scroll bar in syntaxhighlighted code. They were visible in Chrome but not in FF. I came across the solution here. Just add following code snipped at the end of < head > section.

<style type="text/css">
.syntaxhighlighter { overflow-y: hidden !important; }
</style>

java.io.EOFException with Hadoop

2011-04-03T21:05:00.000-07:00

My code runs smoothly with a smaller dataset, however whenever I run it with a larger one, it fails with java.io.EOFException I've been trying to figure out the problem.

11/03/31 01:13:55 INFO mapreduce.Job: 
  Task Id: attempt_201103301621_0025_m_000634_0, Status : FAILED
java.io.EOFException
 at java.io.DataInputStream.readFully(DataInputStream.java:197)
 at org.apache.hadoop.io.DataOutputBuffer$Buffer.write(DataOutputBuffer.java:68)
 at org.apache.hadoop.io.DataOutputBuffer.write(DataOutputBuffer.java:106)
 at org.apache.hadoop.io.SequenceFile$Reader.next(SequenceFile.java:1999)
 at org.apache.hadoop.io.SequenceFile$Reader.next(SequenceFile.java:2131)
 ...
 ...
 ...
 at org.apache.hadoop.mapred.MapTask$
  NewTrackingRecordReader.nextKeyValue(MapTask.java:465)
 at org.apache.hadoop.mapreduce.task.MapContextImpl.nextKeyValue(MapContextImpl.java:80)
 at org.apache.hadoop.mapreduce.lib.map.WrappedMapper$Context.nextKeyValue(WrappedMapper.java:90)
 at org.apache.hadoop.mapreduce.Mapper.run(Mapper.java:143)
 at org.apache.hadoop.mapreduce.lib.input.DelegatingMapper.run
  (Delegatin

So, EOFException means something wrong with your input files. If files are not written & closed correctly, this exception is thrown - the file systems thinks there are more to read but actually number of bytes left are less than expected.
To solve the problem, dig into the input files and make sure they are created carefully without any corruption. Also if MultipleOutputs is used to prepare input files, make sure it is also closed at the end!

WARNING : There are about 1 missing blocks. Please check the log or run fsck.

2011-03-29T11:35:00.000-07:00

hadoop fsck /
hadoop fsck -delete / 
hadoop fsck -move /

-move option moves under /lost+found
-delete option deleted all corrupted files
For more options: http://developer.yahoo.com/hadoop/tutorial/module2.html

Usage of CAP Theorem in Today's Distributed Storage Systems

2011-03-26T09:44:00.000-07:00

CAP Theorem (Eric Brewer) states that a Distributed System can provide at most two of three properties -Consistency, Partition Tolerance, and Availability.

Partition Tolerance is a must in real world systems since machines fail all the time. Therefore, a distributed system has to pick either Availability or Consistency as the second property. Consistency means "always return the correct value" - eg:the latest written one. And availability is "always accept requests" - eg: read & write.
Picking one of these does not always mean loosing the other totally. If application favors from availability, eg: shoppping cart, it is better to prioritize availability and resolving consistency issues later (eventually consistent). On the other hand, if application requires consistency, eg: checkout or backend systems which doesn't require instant response to end user, better to prioritize consistency and give up availability.

Here are some examples:
- Amazon's Dynamo, LinkedIn's Project Voldemort and Facebook's Cassandra provide high availability, but eventual consistency.
- On the other side, Google's Bigtable provides strong consistency and gives up high availability. HyperTable and HBAse are using BigTable approach.

Non-Relational Databases

2011-03-26T09:30:00.000-07:00

Non-Relational DBs

from Data Design point of view; broadly there are two design approaches,
- Google's Bigtable like designs which are column based eg: Hypertable and HBAse
- A simpler Key/Value storage using distributed hash tables (DHTs) eg: Project Voldemort, MongoDB, CouchDB

common specs of both designs

- not a prefixed schema, only domains are set (broadly, these are like RDMS tables)
- entries in domains have a key, and keys have set of attributes
- no prefixed rules defined for these attributes & no explicit definition of domains
- scalable - new nodes can be added and removed easily, able to handle heavy workloads

Bigtable paper by Google summarized here.

hg - detecting renamed files

2011-03-25T06:56:00.000-07:00

hg addremove directory/file --similarity 90

If only want to detect files with no change, then 100 should be used. So the number represents the percentage.

Hadoop - out of disk space

2011-03-24T22:00:00.000-07:00

Facing weird errors like

Exception running child : org.apache.hadoop.util.DiskChecker$DiskErrorException: Could not find any valid local directory for output/spill0.out

means simply some of the nodes run out of memory. To check hdfs status and available storage in each node: http://master-urls:50070/dfsnodelist.jsp?whatNodes=LIVE

Grep for zipped file

2011-03-09T09:17:00.000-08:00

zgrep filename

Hadoop - MapReduce without reducer to avoid sorting

2011-03-09T08:01:00.000-08:00

MR job can be defined with no reducer. In this case, all the mappers write their outputs under specified job output directory. So; there will be no sorting and no partitioning.
Just set the number of reduces to 0.

job.setNumReduceTasks(0);

many small input files

2011-03-07T22:14:00.000-08:00

If MR input directory consists of many small files (couple MBs), then there will be a seperate map task for each and probably these map tasks will last only for 1-2 secs. it kills the performance ! so much scheduling and/or initialization overhead ..

As advised here, it is better to combine input files - so there will be less number of map tasks with larger piece of data to process in each one.

Here is how to combine input files.
(1) Pick a regular record reader class, like LineRecorReader.
(2) Define your own record record reader class for multi file inputs using an instance of (1) .
(3) Define your own input format class which extends CombineFileInputFormat and returns (2)

The trick is regular recordReader uses fileSplit instance, however record reader to be used with combineFileInputFormat should you be using CombineFileSplit. Here is the code:

Name of the regular record reader class I use in this example is RawWebGraphRecordReader. Its basic idea is similar to LineRecordReader.
Below is the code for multi file record reader -MultiFileRawWebGraphRecordReader and input format -RawGraphInputFormat

public class MultiFileRawWebGraphRecordReader extends 
                                       RecordReader < Text, Text > {
 private static final Log LOG = LogFactory.getLog(MultiFileRawWebGraphRecordReader.class);

 private CombineFileSplit split;
 private TaskAttemptContext context;
 private int index;
 private RecordReader< Text, Text > rr;

 public MultiFileRawWebGraphRecordReader(CombineFileSplit split,
                                         TaskAttemptContext context, 
                                         Integer index) throws IOException {
  this.split = split;
  this.context = context;
  this.index = index;
  rr = new RawWebGraphRecordReader();
 }
 
 
 public void initialize(InputSplit genericSplit, TaskAttemptContext context)
 throws IOException, InterruptedException {

  this.split = (CombineFileSplit) genericSplit;
  this.context = context;

  if (null == rr) {
   rr = new RawWebGraphRecordReader();
  }

  FileSplit fileSplit = new FileSplit(this.split.getPath(index), 
                                      this.split.getOffset(index), 
                                      this.split.getLength(index), 
                                      this.split.getLocations());
  this.rr.initialize(fileSplit, this.context);
 }
 
 public boolean nextKeyValue() throws IOException, InterruptedException {
  return rr.nextKeyValue();
 }

 @Override
 public Text getCurrentKey() throws IOException, InterruptedException {
  return rr.getCurrentKey();
 }

 @Override
 public Text getCurrentValue() throws IOException, InterruptedException {
  return rr.getCurrentValue();
 }

 /**
  * Get the progress within the split
  * @throws InterruptedException 
  * @throws IOException 
  */
 @Override
 public float getProgress() throws IOException, InterruptedException {
  return rr.getProgress();
 }

 public synchronized void close() throws IOException {
  if (rr != null) {
   rr.close();
   rr = null;
  }
 }

public static class RawGraphInputFormat extends 
                                 CombineFileInputFormat< Text, Text > {

  @Override
  public RecordReader< Text, Text > 
                     createRecordReader(InputSplit split, 
                                        TaskAttemptContext context)throws IOException {
   return new CombineFileRecordReader< Text, Text >( 
                                 (CombineFileSplit) split, 
                                  context, 
                                  MultiFileRawWebGraphRecordReader.class);
  }
  
  @Override
  protected boolean isSplitable(JobContext context, Path file) {
   CompressionCodec codec = new CompressionCodecFactory(    
                                context.getConfiguration()).getCodec(file);
   return codec == null;
  }

 }

Hadoop - Java Heap Space Error

2011-03-07T15:02:00.000-08:00

"Error: Java Heap space" means I'm trying to allocate more memory then available in the system.
how to go around? (1) better configuration (2) look for unnecessarily allocated objects

Configuration

mapred.map.child.java.opts : heap size for map tasks
mapred.reduce.child.java.opts: heap size for reduce tasks

mapred.tasktracker.map.tasks.maximum: max map tasks can run simultaneously per node
mapred.tasktracker.reduce.tasks.maximum: max reduce tasks can run simultaneously per node

Make sure ((num_of_maps * map_heap_size) + (num_of_reducers * reduce_heap_size)) is not larger than memory available in the system. Max number of mappers & reducers can also be tuned looking at available system resources.

io.sort.factor: max # of streams to merge at once for sorting. Used both in map and reduce.

io.sort.mb: map side memory buffer size used while sorting
mapred.job.shuffle.input.buffer.percent: Reduce side buffer related - The percentage of memory to be allocated from the maximum heap size for storing map outputs during the shuffle

NOTE: Using fs.inmemory.size.mb is very bad idea!

Unnecessary memory allocation

Simply look for new keyword and make sure there is no unnecessary allocation. A very common tip is using set() method of Writable objects rather than re-allocating a new object at every map or reduce.
Here is a simple count example to show the trick:

public static class UrlReducer extends Reducer{
  IntWritable sumw = new IntWritable();
  int sum;

  public void reduce(Text key,Iterable<IntW> vals,Context context){
    sum=0;
    for (IntWritable val : vals) {
      sum += val.get();
    }
    sumw.set(sum);
    context.write(key, sumw);
  }
}

note: There are couple more tips here for resolving common errors in Hadoop.

hg - untracking without deleting

2011-03-01T07:32:00.000-08:00

-A is shortcut for addremove --> adds all files under directory / deletes already deleted ones
f is shortcut for force, rm -f --> forces to delete
-Af surprisingly becomes untracking files without deleting from local repository.
forget is an alias for -Af

hg rm -Af
hg forget

Java Profiler

2011-02-24T07:58:00.000-08:00

HProf is a simple CPU Heap profiling tool. Hadoop's profiling also uses it. Here is the link.

JVM Garbage Collector (Tuning)

2011-02-15T12:46:00.000-08:00

java.lang.OutOfMemoryError: GC overhead limit exceeded means garbage collector is taking so much ( > 98% ) time and can't open up as much space in memory ( < 2% ). I got this exception while working on a large dataset and holding ~1G of data in memory. One way to get over this exception is using a specific jvm garbage collector called Concurrent Collector. Concurrent collector does not let executing program to pause for a long time because of gc. Also concurrent collector takes advantage of multiple CPUs available in the environment. Can be enabled via

-XX:+UseConcMarkSweepGC

Tip: For RMI apps - unnecessary rmi garbage collection can be avoided via tuning its execution frequency. by default it runs every 60,000 msec.

-Dsun.rmi.dgc.client.gcInteraval=3600000
-Dsun.rmi.dgc.server.gcInteraval=3600000

References
- offial reference: [1]
- nice summary: [2]

make sure start-dfs.sh script is being executed on the master !

2010-12-03T14:44:00.000-08:00

everything looks fine when start-all.sh is executed but there is no Namenode process apprear on the jps results. why ? also when I check the logs I see following networking exceptions:

ERROR org.apache.hadoop.hdfs.server.namenode.NameNode: java.net.BindException: Problem binding to hostname/ipaddress:host : Cannot assign requested address
   at org.apache.hadoop.ipc.Server.bind(Server.java:190)
   at org.apache.hadoop.ipc.Server$Listener.(Server.java:253)
   at org.apache.hadoop.ipc.Server.(Server.java:1026)
   at org.apache.hadoop.ipc.RPC$Server.(RPC.java:488)

when I try to do an ls on dfs, I get following:
ipc.Client: Retrying connect to server:  hostname/ipaddress:host
...
...
Bad connection to FS. command aborted

I spent lots of time trying to figure out the "networking" problem, checked if the port is already in use, ip4/ip6 conflict etc ..

at the end, I realized that I'm running start-all.sh script on a random node. When it is executed on the master node, works just fine ! simple fix ..

hadoop - wrong key class exception

2010-11-24T09:20:00.000-08:00

Usually happens because of mismatch between Map or Reduce class signature and configuration settings.

But also be careful about the combiner ! Check if you are using the same class as reducer and combiner. If reducer's input key-value pair is not same as its output key-value pair, then it can not be used as a combiner -because combiner's output will became input on the reducer side !

here is an example:
reducer input key val : < IntWritable, IntWritable >
reducer output key val: < Text, Text >

if this reducer is used as combiner, then the combiner will output <text, text> and reducer will receive <text, text> as input - and boom - wrong key class exception !

java.lang.InstantiationException hadoop

2010-11-23T17:20:00.000-08:00

java.lang.InstantiationException definition:

Thrown when an application tries to create an instance of a class using the newInstance method in class Class, but the specified class object cannot be instantiated because it is an interface or is an abstract class.

I get this exception for setting input reader to FileInputFormat
FileInputFormat is an abstract class !
job.setInputFormatClass(~~FileInputFormat.class~~)

Default is TextInputFormat and it can be used instead..
job.setInputFormatClass(TextInputFormat.class)

exception:

Exception in thread "main" java.lang.RuntimeException: java.lang.InstantiationException
        at org.apache.hadoop.util.ReflectionUtils.newInstance(ReflectionUtils.java:123)
        at org.apache.hadoop.mapreduce.lib.input.MultipleInputs.getInputFormatMap(MultipleInputs.java:109)
        at org.apache.hadoop.mapreduce.lib.input.DelegatingInputFormat.getSplits(DelegatingInputFormat.java:58)
        at org.apache.hadoop.mapreduce.JobSubmitter.writeNewSplits(JobSubmitter.java:401)
        at org.apache.hadoop.mapreduce.JobSubmitter.writeSplits(JobSubmitter.java:418)
        at org.apache.hadoop.mapreduce.JobSubmitter.submitJobInternal(JobSubmitter.java:338)
        at org.apache.hadoop.mapreduce.Job.submit(Job.java:960)
        at org.apache.hadoop.mapreduce.Job.waitForCompletion(Job.java:976)
        at nyu.cs.webgraph.LinkGraphUrlIdReplacement.phase1(LinkGraphUrlIdReplacement.java:326)
        at nyu.cs.webgraph.LinkGraphUrlIdReplacement.main(LinkGraphUrlIdReplacement.java:351)
        at sun.reflect.NativeMethodAccessorImpl.invoke0(Native Method)
        at sun.reflect.NativeMethodAccessorImpl.invoke(NativeMethodAccessorImpl.java:57)
        at sun.reflect.DelegatingMethodAccessorImpl.invoke(DelegatingMethodAccessorImpl.java:43)
        at java.lang.reflect.Method.invoke(Method.java:616)
        at org.apache.hadoop.util.RunJar.main(RunJar.java:192)
Caused by: java.lang.InstantiationException
        at sun.reflect.InstantiationExceptionConstructorAccessorImpl.newInstance(InstantiationExceptionConstructorAccessorImpl.java:48)
        at java.lang.reflect.Constructor.newInstance(Constructor.java:532)
        at org.apache.hadoop.util.ReflectionUtils.newInstance(ReflectionUtils.java:121)
        ... 14 more

Finding a needle in Haystack: Facebook's photo storage

2010-11-20T19:00:00.000-08:00

Summary of the idea Haystack project that Facebook started to use for storing pictures

Total image workload Facebook has:

260 billion images (~20 petabytes) of data
every week 1 billion (~60terabyte) new photos are uploaded

Main charachteristics of Facebook images:

read often
written once
no modification
rarely deleted

Traditional file systems are not fast for these specifications (too many disk accesses per read) and external CDN won't be enough in near future due to increasing workload -especially for long tail. As a solution, Haystack is designed to provide;

High throughput low latency:
- keeps metadata in main memory -at most one disk access per read
Fault tolerance

replicas are in different geographical regions

Cost effective and simple

comparison to NFS based NAS appliance
each usable terabyte costs ~28% less
~4% more reads per sec

Design Previous to Haystack

What is learned from NFS-based Design

more than 10 disk operation to read an image
if directory size is reduced, 3 disk operation to fetch an image
caching file name for highly possible next requests - new kernel func open_by_file_handle

Take away from previous design

Focusing only on caching has limited impact on reducing disk operations for long tail
CDN are not effective for long tail
Would GoogleFS like system be useful ?
Lack of correct RAM/disk ratio in current system

Haystack Solution:

use XFS (extend base file system)

reduce metadata size per picture so all metadata can fit into RAM
store multiple photos per file
so very good price/performance point -better off than buying more NAS appliances
holding all regular size metadata in RAM would be way expensive

design your own CDN (Haystack Cache)

uses distributed hash table
in requested photo can not be find in cache, fetches from Haystack store
store multiple photos per file

DESIGN DETAILS
needs to be updated ..

D. Beaver, S. Kumar, H. C. Li, J. Sobel, and P. Vajgel. Finding a needle in Haystack: Facebook’s photo storage. In OSDI ’10

Using Distributed Cache in Hadoop

2010-11-03T16:38:00.000-07:00

Distributed cache allows to share static data among all nodes. In order use this functionality, the data location should be set before MR job starts.

Here is an example usage for distributed cache. While working on web-graph problem I replace URLs with unique id's. If I have the url-Id mapping in memory, I can easily replace URLs with their corresponding ids. So here is the sample usage:

public static class ReplacementMapper extends Mapper<Text, Text, Text, Text> {

    private HashMap<String, String> idmap;

    @Override
    public void setup(Context context) {
     LoadIdUrlMapping(context);
    }

    @Override
    public void map(Text key, Text value, Context context) throws InterruptedException {
        ....
    }

id-url mapping is loaded at the beginning of each Map task. Below example simply reads the file out of HDFS and stores the data in a hashmap for quick access. Here is the function:

private void loadIdUrlMapping(Context context) {
   
 FSDataInputStream in = null;
 BufferedReader br = null;
 try {
  FileSystem fs = FileSystem.get(context.getConfiguration());
  Path path = new Path(cacheFileLocation);
  in = fs.open(path);
  br  = new BufferedReader(new InputStreamReader(in));
 } catch (FileNotFoundException e1) {
  e1.printStackTrace();
  System.out.println("read from distributed cache: file not found!");
 } catch (IOException e1) {
  e1.printStackTrace();
  System.out.println("read from distributed cache: IO exception!");
 }
 try {
  this.idmap = new HashMap< string, string >();
  String line = "";
  while ( (line = br.readLine() )!= null) {
   String[] arr = line.split("\t");
   if (arr.length == 2)
    idmap.put(arr[1], arr[0]);
  }
  in.close();
 } catch (IOException e1) {
  e1.printStackTrace();
  System.out.println("read from distributed cache: read length and instances");
 }
   }
}

This is one way of accessing shared data among hadoop nodes. Other way of accessing it is through local file system. Here is a great article about how to throw cache data automatically among nodes and access it later.

How to manipulate (copy/move/rename etc..) most recent n files under a directory

2010-11-02T10:35:00.000-07:00

In order to list most recent n files under current directory:


ls --sort-time -r | tail -n

n represent number of files, so should be replaced with a number; eg: 5

in order to move, copy, delete or do something with the result, this line can be fed into "cp" "mv" "rm" commands. However the format is important. This line should be in between single quotes. However not the ones near by enter on your keyboard ( ' ), use the ones under esc key ( ` ).
So here is the command line for moving top n files from one directory to another:


mv `ls --sort-time -r | tail -n` /home/yasemin/hebelek/

Why Hadoop can’t always read properly .gz compressed input files ?

2010-10-31T09:10:00.001-07:00

Hadoop supposed to work happily with .gz input file format by default. [1] So I run my MR job with gz compressed input files and boom! didn’t work.. whenever there is an empty line in the input, Hadoop stucks there and doesn't read -recognize rest of the file. (basically readline returns 0 length string even though there is data) I spent hours to figure out the problem. everything was looking great, .gz files were corrupted or anything, and my code runs fine with the decompressed input... At the end I realized that if I decompress .gz input files and re-compress them again, the size reduces by half ! seems like Hadoop has problems with different versions of .gz compression. I suspect my input files were uncompressed on a Windows machine and looks like some compression applications ends up producing type of .gz file which is incompatible with Hadoop.

Long story short; if Hadoop doesn’t process your .gz compressed input files, try to decompress and re-compress them with gzip under a Linux machine.

gunzip filename.gz
gzip filename

here is the script that unzips and zips all the files under given directory one by one (in case you have a huge archive !)

#!/bin/bash

dir="aaa"
for f in $( ls $dir  ); do
        eval gunzip "$dir/$f"
        eval gzip "$dir/${f%.gz}"
done

[1] Tom White, Hadoop: The Definitive Guide

eclipse Galileo CDT plugin "No Repository found" error

2010-10-13T15:06:00.000-07:00

Seems like people faced similar problems with the < 3.5 eclipse version. However I had the same problem with 3.5 Galileo version. There is an easy work-around solution:

- just download the cdt archive and install it manually.
* Here is the page you can find eclipse-cdt.
* Then go to Help -> Install software and install it.

directory name include space in Linux

2010-09-21T10:08:00.000-07:00

I have both Ubuntu and Windows installed on my computer. When I'm on Ubuntu and want to reach some data from Windows, directory names with spaces causes problem..
Pretty pretty easy way to go around this is using single quotes around the directory in terminal :-)

Inequalities with aws_sdb

2010-08-23T18:41:00.000-07:00

I'm using aws_sdb_proxy for accessing SBD. Since it is using ActiveResource (REST approach), querying with equalities is fairly simple. All the equalities can be passed as a hash with the :params parameter.

Balloon.find(:all, :params => {:color=> "green", :size => "5inch"})

which will be resolves to below GET request:

http://localhost:8080/Baloons.xml?color=green&size=small

In order to support all the other sql-like queries, sdb_proxy allows users to pass a hard-coded string value. Because ActiveResource is used as the underlying communication mechanism, :params value has to be a hash event though all we need to pass is a string. aws_proxy goes around this problem with only looking at the first key of the hash in the case of hard-coded query string.

Balloon.find(:all, :params => {" ['size' > '5inch'] sort 'size' " => nil})

and this will resolve to below GET request:

http://localhost:8080/Baloons/query.xml?:static_query

Note1: I added the query as static_query because I don't have my setup on this machine, but it will add corresponding UTF values for space, quotes and for brackets.. At the end will be something like http://localhost:8080/Baloons/query.xml?size**5inch**sort****size**
Note2: sdb_proxy is using site_prefix for the resource, so the object name (Baloon in this case) is not the domain name. This is a whole different point to discuss, I wrote this entry according to my altered version of sdb. If you are using sdb_proxy as it is, then your http requests will be similar to following:
http://localhost:8080/:domain_name/baloons/query.xml?:static_query
http://localhost:8080/:domain_name/baloons.xml?color=green&size=small

Links for SDB & Rails

2010-08-23T14:04:00.000-07:00

Rails helper

Rails MVC

SDB

SDB-proxy

Synergy -sharing keyboard & mouse

2010-08-12T06:13:00.000-07:00

Here are the instructions I followed.
Two things I had problems with:
- Reverse DNS (make sure your hostname and IP address resolves to each other correctly)
Here is how to check if your DNS resolves backward and forward correctly
>> dig +short hostname
>> dig +short -x your_ip_address
- Make sure the hostname you put in the server configuration matches the "Screen name" in your client.

Then you are good to go! :-)

uuidtools

2010-07-30T08:47:00.000-07:00

Two ways to access random_create method with uuidtools:

UUIDTools::UUID.random_create
UUID.random_create

Use one or another if you get one of the following errors:

NoMethodError: undefined method `random_create' for UUID:Class
NameError: uninitialized constant UUIDTools

* Don't forget to require 'uuidtools' for the both cases..

Prevent connection drops on a ssh connection

2010-07-26T12:24:00.000-07:00

Here is two ways to stop connection drops.

modify /etc/ssh/sshd_config file.
add following:

ClientAliveInterval 30
ClientAliveCountMax 5

and restart sshd:

/etc/init.d/ssh restart

OR

modify /etc/ssh/ssh_config

ServerAliveInterval 15
ServerAliveCountMax 3

colorful ls

2010-07-13T11:02:00.000-07:00

I was looking for a way to distinguish files and folders. It is set to non-colorful in gnome konsole I'm using.
And I find out a more generic way to overwrite a command's behavior.
Here is how to make your ls colorful:
alias 'ls=ls --color=auto'

Can't enable wireless on Linux

2010-07-06T19:08:00.002-07:00

I keep getting error, saying "wireless disabled" on my Dell XPS 1330 laptop.
Then I realized it is hardware disabled...

#rfkill list
>> 3: phy0: Wireless LAN
>> Soft blocked: no
>> Hard blocked: yes

Way to solve this problem is
#sudo rmmod dell_laptop
--enabling it back:
#sudo modprobe dell_laptop

how to change command line editor

2010-07-06T10:57:00.000-07:00

here is how to change command line editor in Linux.
set -o vi
set -o emacs

click for more detailed guidance on shell options.

How to Increase Heap Space of a Project in Eclipse

2010-03-26T13:11:00.001-07:00

Right click source code of the class where your main function is. Then select Run As and Run Configurations. Choose the "Arguments" tab and indicate how much memory you wanna allocate in the VM arguments part. eg: -xmx128m
here is a screenshot:

Also, you can find descriptions of other parameters on this webpage.

How to re-activate hiberbate for Windows Vista

2009-10-28T20:16:00.000-07:00

I was missing the hibernate option on my laptop for a while. And found this webpage very useful.
Basically it tells to run the the command prompt as administrator
then type following commands:
powercfg /hibernate on
powercfg -h on

How to delete .log file in SQL Server 2008

2009-10-21T17:52:00.000-07:00

I've been struggling with deleting 30GB log file for my 8GB of data..
And I figure out that easiest way to do this is just detaching the database and later attaching it without the log file. however this simple approach doesn't work when I try to do it with right click detach and right click attach..
So rather than using interface, try following:
detach the database with following commands;

USE master;
go
SP_DETACH_DB 'dbname';
go

Later just go to the directory where the database reside. Usually the log file name outline is dbname_log and resides under C:\Program Files\Microsoft SQL Server\MSSQL10.MSSQLSERVER\MSSQL\DATA. Delete the log file under this directory.
Later attach the database with following commands:

USE master;
go
SP_ATTACH_DB 'dbname', 'C:\Program Files\....\dbname.mdf'
go

This basically attaches the database with new log file.
Finally you get rid of the this huge log file..
Don't forget to limit auto-growth if you don't want to face same problem later..

Reference sqlhacks