If you’re reading this blog you probably need help copywriting.

A common trend I’ve seen with hackers is that while we’re strong on technical prowess, we’re short on communicating why our work is important. We can whip up a beautiful rails app in a few hours and craft elegant functional combinators but we struggle to explain why our product is worth someone’s attention (and money).

You may be thinking: wait a minute, copywriting is sleazy and I don’t want to stoop to that. I would argue that while some direct response marketing is scummy, copywriting, in the broader sense, is a lot more than cheap tricks. Being able to craft empathetic and direct copy can mean the difference between failure and success with your product.

Enter Michael Ellsberg.

I first took note of Michael when I read his excellent Forbes article building a social economy through helping others. (He also expounds on this idea in his talk to the Thiel Fellows. Highly recommended.)

Michael was recently interviewed by Andrew Warner on Mixergy and they spent a bit of time talking about how to become a better copywriter.

Michael’s advice was this: create a new email address and sign up for the email lists by master copywriters. This allows you to read and learn their techniques for free. In the interview, Michael also mentioned a number of classic books in the field of copywriting.

I’ve collected links to each of these resources and I’ve listed them for you below.*

Direct Response Copywriters

Please note! These folks range from the soft-sell to the extreme-hard-sell (e.g. Dan Kennedy). Please be aware that I’m not necessarily endorsing these hard-edge techniques, but rather, I want to make you aware of the full range of tools you have in your toolbox.

• Eben Pagan
• Dan Kennedy
• Matt Furey
• Marie Forleo
• Jonathan Fields

Copywriting Books

• Tested Advertising Methods by John Caples
• Scientific Advertising by Claude Hopkins also available as a free pdf
• On Advertising by David Ogilvy
• Breakthrough Advertising by Eugene Schwartz

Hope this helps!

P.S.
Since we’re on the topic of copywriting, I’d suggest you checkout Marc-André Cournoyer’s Copy Writing for Geeks. It’s a great intro for hackers who want to quickly improve their writing skills.

* Note: None of these are affiliate links, I have no financial incentive with any of these folks.

Share:

The key insight is that the n in run n refers not to the number of goals that should be tried, but rather the number of answers that should be returned, if available. Full text below:

Posted: Mon Jan 14, 2008 2:19 pm

Hi all,

I’m currently re-reading the Reasoned Schemer, but am having a bit of
difficulty understanding how values are computed for recursive
functions. For example, in chapter 2, the recursive function lolo and
section 24 asks what is the value of the following:

(run 5 (x)
(lolo ((a b) (c d) . x)))

The first value (), is obvious to me. The variable x is fresh, so it
is associated with () via the nullo check on line 4 of the method.

Here’s my explanation for how the second value is derived. Since we
are asking for another value, and the expressions are evaluated within
the conde, we refresh x and try the next line. At this point, the caro
associates the fresh variable x with the cons of the fresh variable a
and the fresh variable d-prime (introduced by the caro). Then, listo
is called on a. Since a is fresh, this call associates a with ().
Since this question succeeds, we try the answer. The cdro associates x
with the cons of fresh variable a-prime (introduced by the cdro) and
the fresh variable d. Then, lolo is called on d, and so d (being
fresh), is associated with ().

Since a-prime and a co-share, and a is (), and d and d-prime co-share,
and d is (), x can be successfully associated with the cons of () and
(), so the result is (()).

Here’s where I get confused. This invocation of run 2 has actually
produced #s 3 times, once to produce () and twice to produce (())
(once in each of the calls to listo and the recursive call to lolo).
However, we have *asked* for only two goals to be met, in order to
produce two values. If I invoke “run 3 …,” however, which conde
lines in which recursive frames are being evaluated, and having their
associations preserved? Or rather, how is the result expanding beyond
(())?

At the high level, I understand why the answer is (() (()) (() ()) (()
() ()) (() () () ())). But I’m still missing something at the lower
level that makes it harder for me to understand how some of the more
advanced examples, like the adder, work.

Thanks,
Joe
=====================

Posted: Tue Jan 15, 2008 3:30 pm

(run 2 (q) g1 g2 g3) does *not* specify that at most two goal
invocations should succeed, or that at most two #s goals should be
tried. Rather, run 2 specifies that we want two answers (if there are
two answers to be had), regardless of how many goals must be tried,
must succeed, or must fail in order to get those answers.

Hope this helps.

–Will

Share:

Last Friday, I gave a talk on how to overcome some of the challenges of large-scale web crawling at Berkeley. Below are the slides from that talk.

Share:

Here’s an example. We want to find the largest index i such that haystack[i] <= needle. Needle = 15, and haystack is a sorted list of the first 8 prime numbers, indexed by binary numbers:

000     2
001     3
010     5
011     7
100     11
101     13
110     17
111     19

Note first that the haystack index requires no more than 3 bits. Therefore we start with the highest order bit set: b=100. (This font denotes binary numbers here.) Is haystack[100] <= 15? Yes, 11<=15. Observe this means that the first bit of the index we are looking for is 1. We look at the next bit. Is haystack[110] <= 15? No, 17 <= 15 is false. This means the 2nd bit is 0. Finally, is haystack[101] <= 15? Yes, 13 <= 15. Therefore the index we are looking for is 101.

In essence, the main loop to find the index i is simply:

    for( ; b ; b >>= 1 )
        if( haystack[i|b] <= needle ) i |= b;

where b is the value with 1 bit set, that began with b=100 and i=0.

It is the natural structure of the bits within the index variable that automatically tracks both the upper and lower bounds of the search window for each iteration. Compare this with the less efficient and more verbose arithmetic performed in the main loops of standard binary search algorithms.

The full C++ code for the improved binary search algorithm fbsearch() is:

// Binary search revisited.
 
// Define only one of these:
// #define SETBIT_FAST
// #define SETBIT_FASTER
#define SETBIT_FASTEST
 
#ifdef SETBIT_FAST
#include <math.h>
#endif
 
// Return 1 << log_2(list_size-1), or 0 if list_size == 1.
// This sets the initial value of b in fbsearch().
inline unsigned init_bit( unsigned list_size )
{
#ifdef SETBIT_FAST
    return list_size == 1 ? 0 :
        1 << int( log(list_size-1) / M_LN2 );
#endif
#ifdef SETBIT_FASTER
    return list_size == 1 ? 0 :
        1 << ( sizeof(unsigned) << 3 ) - 1
             - __builtin_clz(list_size-1);
#endif
#ifdef SETBIT_FASTEST
    unsigned b;
    __asm__ ( "decl %%eax;"
              "je DONE;"
              "bsrl %%eax, %%ecx;" // BSR - Bit Scan Reverse (386+)
              "movl $1, %%eax;"
              "shll %%cl, %%eax;"
              "DONE:" : "=a" (b) : "a" (list_size)
    );
    return b;
#endif
}
 
// Return the greatest unsigned i where haystack[i] <= needle.
// If i does not exist (haystack is empty, or needle < haystack[0])
// then return unsigned(-1). T can be any type for which the binary
// operator <= is defined.
template <typename T>
unsigned fbsearch( const T haystack[], unsigned haystack_size,
                   const T& needle )
{
    if( haystack_size == 0 ) return unsigned(-1);
    unsigned i = 0;
    for( unsigned b = init_bit(haystack_size) ; b ; b >>= 1 )
    {
        unsigned j = i | b;
        if( haystack_size <= j ) continue;
        if( haystack[j] <= needle ) i = j;
        else
        {
            for( b >>= 1 ; b ; b >>= 1 )
                if( haystack[i|b] <= needle ) i |= b;
            break;
        }
    }
    return i || *haystack <= needle ? i : unsigned(-1);
}
 
// Example Usage
#include <iostream>
using namespace std;
 
int main()
{
    const int sorted_list[] = { 2, 3, 5, 7, 11, 13, 17, 19, 23 };
    const unsigned list_size = sizeof(sorted_list)/sizeof(int);
    int needle = 15;
    cout << "fbsearch(sorted_list,"<<list_size<<','<<needle<<") = "
         << fbsearch(sorted_list,list_size,needle) << endl;
    // fbsearch(sorted_list,9,15) = 5
    return 0;
}

Ancillary notes:

• The function init_bit() sets the initial value of b to having a single bit set in the highest position for indexing the array list. The three SETBIT_FAST, SETBIT_FASTER, and SETBIT_FASTEST code blocks within it are simply 3 different ways of calculating the initial value of b, whose speed ranks are the reverse of their cross-platform compatibility. The first method should compile everywhere, and simply calculates it from a base-2 logarithm. The second method uses the faster GNU __builtin_clz method (thanks Chao Xu for the suggestion) that counts the highest order bit from the left. The third and fastest method uses the Intel assembly instruction BSR that counts it from the right.
• The null return value of unsigned(-1) (=4294967295 for 32-bit unsigned) is the unique value that will never otherwise be returned. Therefore it can safely be checked for by the calling function without risk of misinterpretation.
• The one else block can safely be removed without changing the overall functionality. It exists to simply save having to check that the array index is in bounds on every iteration, since it is at a point in logic where that condition is guaranteed.

Share:

I plan to use NoSQL in the not-too-distance future, but not today. When I port the data over I don’t want to have to map “old ids” to “new ids”. By using a uuid from day one I can easily maintain referential integrity when I migrate to a new datastore.

I looked up how this is typically done in Rails using MySQL and all I could find was examples that store the UUID as strings (e.g. here). The UUID is natively just 16 bytes so storing this in a VARCHAR(36) seemed like a poor solution. Ideally we would store the UUID as binary and let the ORM deal with translating it to and from a UUID object.

activeuuid solves this problem. activeuuid is a Rails plugin that will let you use UUIDTools::UUID objects as primary keys for your ActiveRecords and it stores them in MySQL as binary(16).

Here’s how to use it:

Create a Migration

activeuuid adds the uuid type to your migrations. Example:

class CreateEmails < ActiveRecord::Migration
  def self.up
    create_table :emails, :id => false  do |t|
      t.uuid :id, :unique => true
      t.uuid :sender_id  # belongs_to :sender
 
      t.string :subject
      t.text :body
 
      t.timestamp :sent_at
      t.timestamps
    end
    add_index :emails, :id
  end
 
  def self.down
    drop_table :emails
  end
end

include ActiveUUID::UUID in your model

class Email < ActiveRecord::Base
  include ActiveUUID::UUID
  belongs_to :sender
end

use it

Here are some example specs:

require 'spec_helper'
 
describe Email do
 
  context "when using uuid's as keys" do
    before(:each) do
      Email.delete_all
      @guid = "1dd74dd0-d116-11e0-99c7-5ac5d975667e"
      @e = Email.new(:subject => "hello", :body => "world") {|e| e.id = UUIDTools::UUID.parse(@guid) }
      @e.save
    end
 
    it "the id guid should be equal to the uuid" do
      @e.id.to_s.should eql(@guid)
    end
 
    it "should be able to find an email by the uuid" do
      f = Email.find(UUIDTools::UUID.parse(@guid))
      f.id.to_s.should eql(@guid)
    end
 
  end
end

Benefits

There are a number of benefits to using UUIDs as primary keys.:

• no id conflict during multi-master write
• no locking due to auto-increment
• with time-based UUIDs you can store a timestamp within your UUID
• you can create natural keys (based on the SHA of model attributes)

Future work

• more transparent support for natural and composite keys
• support for MySQLs `INSERT … ON DUPLICATE KEY UPDATE` syntax
• support a primary column name other than `id`
• work on other databases (Postgres, etc)
• tests

Installation

Add this to your Gemfile

    gem "activeuuid"

Or get the code here: https://github.com/jashmenn/activeuuid

References

• http://bret.appspot.com/entry/how-friendfeed-uses-mysql
• http://kekoav.com/blog/36-computers/58-uuids-as-primary-keys-in-mysql.html
• https://gist.github.com/937739
• http://www.codinghorror.com/blog/2007/03/primary-keys-ids-versus-guids.html
• http://krow.livejournal.com/497839.html
• https://github.com/jamesgolick/friendly

Dependencies

Note that this depends on Rails 3.1 because it uses the custom column serialization added by Aaron Patterson. (See: https://github.com/rails/rails/commit/ebe485fd8ec80a1a9b86516bc6f74bc5bbba3476)

Share:

• an object-oriented way to interface with Cassandra
• serialization helpers
• failover support
• connection pooling
• jmx support

There is already a Ruby cassandra gem, but it uses the Ruby Thrift bindings which do not work well for JRuby. In any case, I want to be able to seamlessly serialize Java objects and store them in Cassandra.

Thus hector.rb was born. hector.rb is a JRuby Cassandra client that wraps Hector. The interface is based on clj-hector. Eventually, I’d like the interface to be API compatible with the cassandra gem.

Example Usage

require 'java'
require 'hector'
cluster = Hector.cluster("Hector", "127.0.0.1:9160")
ks_name = java.util.UUID.randomUUID.to_s.gsub("-","")
client = Hector.new(nil, cluster, :retries => 2, :exception_classes => [])
column_families = [{:name =>"a"}, {:name => "b", :type => :super}]
client.add_keyspace({:name => ks_name, :strategy => :local, :replication => 1, :column_families => column_families}) 
client.keyspace = ks_name
 
sopts = {:n_serializer => :string, :v_serializer => :string, :s_serializer => :string}
client.put_row("a", "row-key", {"k" => "v"})
client.get_rows("a", ["row-key"], sopts) # => {"row-key" => {'k' => 'v'}}
client.get_columns("a", "row-key", ["k"], sopts) # => {'k' => 'v'}
 
 
client.put_row("b", "row-key", 
               { "SuperCol"  => {"k" => "v", "k2" => "v2"},
                 "SuperCol2" => {"k" => "v", "k2" => "v2"} })
client.get_super_columns("b", "row-key", "SuperCol", ["k2"], sopts) # => {"k2" => "v2"}

For more examples, see the tests.

Installation

gem install --source http://gems.xcombinator.com hector
or
Get the source here.

Future Work

Now that we can easily deal with [super]rows and columns in Cassandra, the next step is to put an ActiveModel abstraction over it. I’m currently working on modifying cassandra_object to work on JRuby with hector.rb. If you’d like to follow development the branch is here.

Share:

Say you have a large corpus of web documents and you want to group them together by some notion of “similarity”. For instance, we may want to detect plagiarism or find content that appears on multiple pages of a site.

In this scenario, it’s impractical to do a pairwise comparison of all documents. Fortunately, we can use simhashing.

Broadly speaking, simhashing is a algorithm that calculates a “cluster id” (the minimum hash, or minhash) from the content. Because the minhash for an item is calculated independently of the other items in the set, minhashing is an ideal candidate for MapReduce.

Ryan Moulton has written a wonderful article on Simhashing. I’m not going to repeat his content here, so if you’re unfamiliar with simhashing I encourage you to go and read his article first.

In his article, Ryan sketches the proof that the probability that any two sets (in this case, documents) share the same minhash is equal to their Jaccard similarity coefficient. This is a really neat result because we are able to get the Jaccard index without having to actually compare the intersection of the two sets directly.

cascading-simhash

I’ve created a library for calculating simhashes in Hadoop. It’s written in Clojure and Java and uses Casacalog and Cascading.

To use it, you 1) input tuples consisting of a (document_id, body) and 2) define how to tokenize your body. The job emits tuples of the form (minhash, document_id, body). You can then use minhash as the key for your next phase. (All records that share a minhash are potential duplicates.)

The library can be called from either Clojure or Java. Additionally, Simhash returns a Flow so you can use it in your Cascade if you want to make it part of a bigger pipeline.

A Java example

Here’s a quick example on how to use the library from Java:

/**
 * Simple Simhash - an example of how to use Simhash
 *
 * To run this example:
 *   lein uberjar
 *   lein classpath > classpath
 *   java -cp `cat classpath`:build/cascading-simhash-1.0.0-SNAPSHOT-standalone.jar simhash.examples.SimpleSimhash "test-resources/test-documents.txt"
 **/
public class SimpleSimhash {
  private static final Logger LOG = Logger.getLogger( SimpleSimhash.class );
 
  /**
   * Create a tokenizer that is a subclass of clojure.lang.AFn and
   * implements invoke(Object body)
   **/
  public static class Tokenizer extends AFn {
 
    /**
     * Your tokenization logic goes here
     *
     * @param String body
     * @return something seq-able
     */
    public Object invoke(Object body) throws Exception {
      String b = (String)body;
      return b.split(" ");
    }
  }
 
  public static void main( String[] args ) {
    Tap inputTap = new Hfs( new TextDelimited( 
                                new Fields("docid", "body"), "\t" ),
                            args[0] );
    Tap outputTap = new StdoutTap();
 
    // create the flow
    Flow simhashFlow = Simhash.simhash(inputTap, outputTap, 
                                       2, // combine n-th lowest minhashes (e.g. 2) 
                                       SimpleSimhash.Tokenizer.class);
    simhashFlow.complete(); // or add to your Cascade, etc
  }
}

Notice a few things here:

• We’re inputting a tap of two fields: (docid, body)
• The 2 parameter is the number of minhashes to combine. In this case, we will combine the 2 lowest hashes to create one minhash. This parameter controls the overlap required for a match. In this case, the two sets much share the same 2 minhashes in order to match.
• The Tokenizer is a subclass of clojure.lang.AFn. Override the invoke(Object) method and you will be passed the body the current record. In this case, we’re tokenizing by doing a simple String split.

If you’ve checked out the source you can run it like this:

lein uberjar
lein classpath > classpath
java -cp `cat classpath`:build/cascading-simhash-1.0.0-SNAPSHOT-standalone.jar simhash.examples.SimpleSimhash "test-resources/test-documents.txt"

Given:

# test-resources/test-documents.txt
# docid \t body
DocA	my dog has fleas
DocB	my dog has fleas
DocC	my dog has hair
DocD	see spot run
DocE	We hold these truths

We get:

RESULTS
-----------------------
23fd68296bc65391799c8c441faf4403c729256f	DocE	We hold these truths
402183e1cbc52e7c87eb230c281f35e4b27c2a39	DocD	see spot run
49c31c1459a7603bd5680d11285a5716c4ba3903	DocA	my dog has fleas
49c31c1459a7603bd5680d11285a5716c4ba3903	DocB	my dog has fleas
58e5a2035461323a37102e22273c9b25cbb9df61	DocC	my dog has hair
-----------------------

A Clojure example

Similarly, here’s how to run the library from Clojure. This time we use bi-grams as the tokens.

(ns simhash.examples.bigrams
  (:use 
   [simhash core util]
   [cascalog api testing])
  (:require 
   [simhash [taps :as t] [ops :as ops]]
   [clojure.contrib.str-utils :as stu])
  (:gen-class))
 
(defn my-source [path]
  (<- [?docid ?body]
      ((hfs-textline path) ?line)
      (ops/re-split-op [#"\t" 2] ?line :> ?docid ?body)
      (:distinct false)))
 
(defn tokenize 
  "tokenize into bi-grams (sliding window)"
  [body]
  (map
   (fn [tokens] (stu/str-join " " tokens))
   (partition 2 1 (stu/re-split #"\s+" body))))
 
(defn -main [& args]
  (?- (stdout) 
      (simhash-q (my-source (first args))
                 2 ;; number of minhashes
                 tokenize)))

A few things to point out about the Clojure example:

• simhash-q is just a Cascalog query. Unlike the Java example (which required a Tap as the input) simhash-q can accept any other Cascalog query as the input.
• You must use gen-class on the namespace that holds your tokenize function. This is because Cascading will serialize your Flow and it has a hard time with functions generated at run-time. Generally speaking, if the tokenize function isn’t aot compiled into a class you’re going to run into problems.

The project also includes a tokenizer for extracting text from HTML documents. For examples see tokenizers.html_text.clj for an example on how to write a tokenizer in Clojure. See HtmlSimhash.java for a Java example on how to use it.

Summary

Simhashing in MapReduce is a quick way to find clusters in a huge amount of data. By using Cascading and Cascalog we’re able to work with MapReduce jobs at the level of functions rather than individual map-reduce phases.

Have any data you need clustered? Try cascading-simhash and let me know how it goes!

Learn more about big data by following me on twitter.

You can get the jars via clojars:
leiningen:

  [cascading-simhash "1.0.0-SNAPSHOT"]

maven

<dependency>
  <groupId>cascading-simhash</groupId>
  <artifactId>cascading-simhash</artifactId>
  <version>1.0.0-SNAPSHOT</version>
</dependency>

View the source on github.

References

1. http://knol.google.com/k/simple-simhashing
2. http://en.wikipedia.org/wiki/Jaccard_index
3. http://en.wikipedia.org/wiki/MinHash

Share:

Why is XOR the default way to combine hashes?

I posted this question on Stackoverflow and got this excellent and concise answer from Greg Hewgill:

Assuming random (1-bit) inputs, the AND function output probability distribution is 25% 0 and 75% 1. Conversely, OR is 75% 0 and 25% 1.

The XOR function is 50% 0 and 50% 1, therefore it is good for combining uniform probability distributions.

The distributions become clear when we chart the output of each of the operations:

If you are combining two random bits with AND you have a 75% chance of 1. Similarly, if you combine two random bits with OR you have a 75% chance of 0.

My friend Rob Zinkov [1] explains it by framing it in terms of entropy:

[When combining hashes] essentially you want an operation that maximizes entropy since lower entropy implies the hash is storing less data than it appears.

With AND and OR lots of the variation in bits is being removed, so the hash you end up with tend to be biased to towards 1s (as in the OR case) or 0s (as in the AND case)

That bias means each bit is storing slightly less information (since that bias is present).

Summary: If you need to combine two hashes, XOR them together and you’ll have a better chance at maintaining the entropy of the original hashes.

[1] Rob runs the L.A. Machine Learning meetup group. If you’re in L.A. AND interested in machine learning, stop by sometime.

Share:

Introduction

  (ns smoker.udf.MyLowerCase
    (:import [org.apache.hadoop.hive.ql.exec UDF])
    (:import [org.apache.hadoop.io Text])
    (:require [clojure.contrib.str-utils2 :as su])
    (:gen-class
     :name smoker.udf.MyLowerCase
     :extends org.apache.hadoop.hive.ql.exec.UDF
     :methods [[evaluate [org.apache.hadoop.io.Text] org.apache.hadoop.io.Text]]))
 
  (defn #^Text -evaluate 
    "Lower-case the text"
    [this #^Text s]
    (when s
      (Text. (su/lower-case (.toString s)))))

  # make the jar
  lein compile
  lein uberjar   # include dependencies for Hive/Hadoop
 
  # tell hive about your jars
  hive --auxpath ./build
  add jar /home/nmurray/hive-jars/smoker-standalone.jar;
  list jars; # verfiy it is there
 
  # create your operations
  create temporary function my_lower as 'smoker.udf.MyLowerCase';
 
  # given:  a_table
  # format: id,sentence
  1,My dog has fleas
  2,My cat Mr. Mittens has fleas
 
  SELECT my_lower(sentence) from a_table;
 
  # returns:
  my dog has fleas
  my cat mr. mittens has fleas

 
  # given:  a_table
  # format: id,sentence
  1,My dog has fleas
  2,My cat Mr. Mittens has fleas
 
  SELECT tokenize(sentence) AS (word, count) FROM a_table;
 
  # returns:
  my 1
  dog 1
  has 1
  fleas 1
  my 1
  cat 1
  mr. 1
  mittens 1
  has 1
  fleas 1

  (ns smoker.udf.MyTokenize
    (:require [smoker.udtf.gen :as gen])
    (:import [org.apache.hadoop.hive.serde2.objectinspector.primitive 
              PrimitiveObjectInspectorFactory])
    (:require [clojure.contrib.str-utils2 :as su]))
 
  (gen/gen-udtf)
  (gen/gen-wrapper-methods 
   [PrimitiveObjectInspectorFactory/javaStringObjectInspector
    PrimitiveObjectInspectorFactory/javaIntObjectInspector])
 
  (defn -operate [this line]
    (map 
     (fn [token] [token (Integer/valueOf 1)]) 
     (su/split line #"\s+")))

(gen/gen-wrapper-methods 
 [PrimitiveObjectInspectorFactory/javaStringObjectInspector
  PrimitiveObjectInspectorFactory/javaIntObjectInspector])

  # wrong
  SELECT id, tokenize(sentence) AS (word, count) FROM a_table;
  # Hive ERROR...

  SELECT tokenize(sentence) AS (word, count) FROM a_table;
 
  SELECT id, word, count
  FROM a_table 
  LATERAL VIEW tokenize(sentence) tokenizedTable as word, count 
 
  # returns:
  # id word count
  1 my 1
  1 dog 1
  1 has 1
  1 fleas 1
  2 my 1
  2 cat 1
  2 mr. 1
  2 mittens 1
  2 has 1
  2 fleas 1

Share:

If you’re not familiar with PermGen space, it is a portion of memory reserved for the JVM itself. It is used for storing information about Classes and interned Strings.

When you intern a String the JVM stores a single copy of that String in the PermGen space. This can save RAM because only one copy of the String will exist in the system. It can also speed up == comparisons for two interned Strings because you only have to compare the reference not the characters.

The problem is, the PermGen space is typically very small (64m is a common default). So if you have many classes or a lot of interned Strings, you can easily blow out the PermGen space.

This problem was showing up in our crawler and we traced it to how we were parsing robots.txt.

robots.txt is a convention website owners can use that will instruct
crawlers how to act while they are on their site. All polite crawlers
use them. For example:

Disallow: /no-crawl/
Allow: /
Sitemap: http://www.foo.com/sitemap.xml

In our crawler, we’ve written a custom robots.txt parsing library: clj-robots (github).

In clj-robots, there was one section of the code where we were taking the left hand side of the robots.txt and converting it to a keyword. This made for cleaner code than comparing Strings. Since there are only a fixed number of robots.txt directives, this should be safe, right?

It turns out it isn’t safe. First, you don’t know what people are actually going to put in their robots.txt. Second, what we forgot was that many sites don’t have a robots.txt, but they don’t return an empty 404, they often return their custom 404 HTML page. What happened was we were parsing an HTML page as a robots.txt and then interning everything that looked like a robots.txt directive.

The result was a spectacular “java.lang.OutOfMemoryError: PermGen space” after just a few minutes. The general principle here is that you should never allow user-generated input become an interned String.

Lessons learned:

• PermGen stores Classes and interned Strings
• Clojure’s keyword interns a String
• Don’t call keyword on user-generated input
• A profiling tool (e.g. JProfiler) can be your best friend in these situations

References:

• Java GC FAQ
• Keyword.java from Clojure Core
• interned Strings : Java Glossary

Share:

Every CS student knows how to write a binary search algorithm. The question is, are we really making full use of the fact that we are using a binary computer to do a binary search? While it is true that computers are good at doing arithmetic, they are even better at doing pure bit logic. Often times our grammar school arithmetic way of thinking can get in the way of solving a problem that has a more elegant solution in terms of lower-level bit logic. Binary search in an ordered list is one such problem.

Your homework problem: re-write the typical textbook binary search in an ordered list algorithm, making it faster, without doing any arithmetic within the main loop of the search algorithm (underlying pointer arithmetic by direct access of array elements is ok).

Solution in C++:

// Fastest binary search
#include <iostream>
#include <math.h>

int main()
{
    const int sorted_list[] =
        { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29 };
    const size_t list_size = sizeof(sorted_list)/sizeof(int);
    int i = 7;
    cout << "fbsearch(sorted_list,"<<list_size<<‘,’<<i<<") = "
         << fbsearch(sorted_list,list_size,i) << endl;
    return 0;
}

Technical Notes:

• Feel free to add a statement within the loop that returns the index if found. Note that for large n, you will spend more time on average checking for equality than the time you will save by returning early.
• Instead of dividing by ln(2), feel free to save the constant 1/ln(2) and multiply by it instead.

So what’s going on here? Take a list of the first 10 prime numbers, for example, and enumerate them using base-2:

0000   2
0001   3
0010   5
0011   7
0100  11
0101  13
0110  17
0111  19
1000  23
1001  29

If we are given one of the items on the list, say 13, then we are looking for its 4-bit index. Each bit is a yes/no question. The first bit asks, “Are you at index 1000 or higher?” If no, then the second bit asks, “Are you at index 0100 or higher?” If yes, then the third bit asks, “Are you at 0110 or higher?” If no then the last bit asks, “Are you at 0101 or higher?” By now we have asked all 4 questions, and thus have all 4 bits of the index.

Moral of the story: Sometimes it’s better to think like a silicon being than a carbon one.

p.s. Happy birthday, Nate!

Share:

The naive solution to this is to just use the URL as the key. But it’s easy to see that this will cause duplicate pages to be downloaded because:

• URLs for a given page aren’t consistent even within a given site. (e.g. http://www.foo.com/ and http://www.foo.com/index.html)
• Many pages have links to anchor tags which are all on the same page (e.g. http://www.foo.com/index.html and http://www.foo.com/index.html#locations)

Pop Quiz: What’s the “normal” form of each of these URL?

http://www.foo.com:80/foo
http://www.foo.com/foo/../foo#bam
http://:@www.FOO.com/foo/../foo

The answer: http://www.foo.com/foo.

We need a URL normalizer that will return a consistent URL for all URLs that point to a given page. Again, note that a single page has many URLs.

If the URL http://:@www.FOO.com/foo/../foo seems a bit contrived,
let me tell you: it isn’t. As soon as you start crawling you learn the web is full of hideous markup including non-intuitive (and nonsensical) URLs.

URL normalization is one of those problems that seems simple but, in fact, the details get pretty hairy. So Jay Donnell and I have been working on a small URL normalizer that makes it easy. It’s still young but already passes a large number of tests, including most of the Pace URL Normalization Tests.

Usage

 (ns my.namespace
     (:use [url-normalizer.core))

 (canonicalize-url "http://www.example.com:80/foo#bar")
 -> "http://www.example.com/foo"

The code is on github and the jar is on clojars.

The inspiration for this library comes from Sam Ruby’s urlnorm.py.

Interested in URL Normalization? Want to write a large-scale web-crawler in Clojure? We’re hiring. Send me an email.

Share:

Here’s a quick example on how to use it:

;; lein dependency: [net.htmlparser.jericho/jericho-html "3.1"]
(ns foo.preprocess
  (:import 
   [java.io File BufferedInputStream FileInputStream]
   [net.htmlparser.jericho Source TextExtractor]))
 
(defn extract-text 
  "given File returns a String of the extracted text"
  [f]
  (let [source (Source. (BufferedInputStream. (FileInputStream. f)))]
    (.toString (TextExtractor. source))))
 
(def filename "data/some-index.html")
(extract-text (java.io.File. filename))

TextExtractor has sensible defaults and ignores the css and javascript by default. See the TextExtractor class for more details.

Share:

You can find the code on github.

Usage:

    BoyerMoore.search(haystack, needle)   # returns index of needle or nil

Examples:

Basic search in string:

    BoyerMoore.search("ANPANMAN", "ANP")   # => 0
    BoyerMoore.search("ANPANMAN", "ANPXX") # => nil 
    BoyerMoore.search("foobar", "bar")     # => 3

You can also search an array of tokens:

    BoyerMoore.search(["<b>", "hi", "</b>"], ["hi"])         # => 1 
    BoyerMoore.search(["bam", "foo", "bar"], ["foo", "bar"]) # => 1 
    BoyerMoore.search(["bam", "bar", "baz"], ["foo"])        # => nil

A token can be a regular expression:

    BoyerMoore.search(["Sing", "99", "Luftballon"], [/\d+/]) == 1
    BoyerMoore.search(["Nate Murray", "5 Pine Street", "Los Angeles", "CA", "90210"], [/^\w{2}$/, /^\d{5}$/]) == 3

Notes:

The regular-expression token matching is a bit of a hack and will be fairly slow because every hash miss is compared against every regular expression key. You probably shouldn’t use the regular expression token search for anything more than a toy.

Download the Boyer-Moore string search algorithm in Ruby.

Share:

You can find the code on github

My solution’s main ideas are adapted from these two pages:

• http://getsetgames.com/2009/08/21/cocos2d-and-uiscrollview/
• http://blog.proculo.de/archives/180-Paging-enabled-UIScrollView-With-Previews.html

My contribution is combining the UIScrollView with previews with Cocos2d and cleaning it up.

If you haven’t tried to implement this before it might not be obvious why this is tricky to implement. Apple’s UIScrollView allows you to have a view which scrolls and optionally snaps to pages. The effect you see in the video above (and in Angry Birds level selection and many other apps) shows a preview of each panel on either side. This let’s you easily see if a next or previous page exists and you see a preview of that page.

The problem is that Apple’s UIScrollView doesn’t let you set the width of the frame, so you can’t page less than a whole screen (well, a whole width of theUIScrollView, more on that later).

To get around this I originally tried writing my own paging controller. If you’ve tried this you’ll know that it is extremely tricky to get the same interaction dynamics as Apple’s. (For instance, pull out your phone and play with the Photo application. Notice if you just drag slowly you lack enough inertia to go to the next page so it will snap back to the frame your are on. If you flick fast over a small area the page will skip to the next frame. Etc.) While at first glance the rules seem easy to reimplement, you have to cover a lot of edge cases to recreating the familiar paging interaction.

So ideally we need to figure out a way to use Apple’s UIScrollView and we should save ourselves a lot of work.

Like we said above, a UIScrollView will only page the width of the entire UIScrollView. So to get this preview effect you can create a UIScrollView that is less than the width of the entire screen. The problem here is that any touches that lie outside of that UIScrollView (say on the edge of the screen won’t be sent to the UIScrollView.

Our solution, (again, borrowed largely from the above links) looks like this:

The idea is this:

• We create a CCMenu and add it to a CCLayer
• The UIScrollView is resized to the width of our panel images (smaller than the whole screen)
• The UIScrollView transforms its scrolling action into moving the position of the CCLayer containing our CCMenu
• We create a full-screen TouchDelegatingView that simply forwards its touches on to the UIScrollView

More Details

In Jacob’s Shapes (JS), we have a GameController which knows all of the levels. For the sake of this example, we’re just going to store all the level names in an NSArray.

# HCUPPanelScene.m (in onEnter)
NSArray* panelNames = [NSArray arrayWithObjects: 
    @"amazon", @"arctic",
    @"brkfst", @"camp", 
    @"city", nil];
int numberOfPages = [panelNames count];
 
// create an empty layer for us to work with
CCLayer* panels = [CCLayer node];

Custom CCMenu and CCMenuItem

We use a custom subclass of CCMenu and CCMenuItem, NMPanelMenu and NMPanelMenuItem, respectively. NMPanelMenu tweaks how the current item is determined. Overriding NMPanelMenuItem allows us to add metadata about the panel, play sounds, and optimize how we use the images for selected panels.

# HCUPPanelScene.m
NMPanelMenu* menu = [NMPanelMenu menuWithItems: nil];
float onePanelWide = -1;
 
// Now add the panels
for(int i=0; i < numberOfPages; i++) {
    NSString* currentName = [panelNames objectAtIndex:i];
    CCSprite* pane2 = [CCSprite spriteWithFile:[NSString stringWithFormat: @"%@-panel.png", currentName]];
    NMPanelMenuItem* menuItem2 = [[NMPanelMenuItem alloc] initFromNormalSprite:pane2 
                                                                selectedSprite:pane2
                                                                  activeSprite:pane2
                                                                disabledSprite:pane2
                                                                          name:currentName
                                                                        target:self selector:@selector(levelPicked:)];
    menuItem2.world = i;
    menuItem2.name = currentName;
    [menu addChild: menuItem2];
    [menuItem2 release];
    // set onePanelWide to be the width of the first panel
    if(i==0) onePanelWide = [pane2 textureRect].size.width;
}

Here we used CCSprite#spriteWithFile, but in JS we use Zwoptex-created sprite sheets for the panels and then create sprites from those frames. This makes a huge difference in the load time of this scene when you have 20 panels. In JS, instead of loading 20 textures (one for each panel) we only load 2 textures, each containing 10 panels each.

JS is graphics heavy and we definitely had to pay attention to file sizes to keep it under 22MB. Originally I had created two versions of each panel, one for “off” and one with a glow for “on” (active/selected). Each of the panels as a transparent png was somewhere around 100k. So 100k x 2 for each state x 20 panels was somewhere around 4MB just for this single scene.

We decided to sacrifice a bit of the quality of the glow for the “on” state and just create one transparent image for the glow and reuse that for every panel.

To use the glow a portion of our NMPanelMenuItem looks like this:

# NMPanelMenuItem.m
-(void) activate
{
    isActive_ = YES;
    // play sound here
    [super activate];
}
 
-(void) draw
{
    if(isActive_) {
        [self.activeImage draw];
        if(self.showGlow) [self.glow draw];
    } else {
        [super draw];
    }
}

Where self.glow is a CCSprite attached to the NMPanelMenuItem.

Adding the Cocos2d Panels

Next we need to setup some basic options for how much padding we want and what the total width of the panels layer is going to be. Then we add the panels to our scene and set the position.

# HCUPPanelScene.m
float padding = 15;
float totalPanelWidth = onePanelWide + padding*2;
float totalWidth = numberOfPages * totalPanelWidth; // (wait, do we need padding in here?)
 
int currentWorldOffset = 0;    // current world number. 
// int currentWorldOffset = 1; // Try changing to 1 and see what happens
 
[menu alignItemsHorizontallyWithPadding: padding*2];
 
// add our panels layer
[panels addChild:menu];
[self addChild:panels];
 
// set the position of the menu to the center of the very first panel
menu.position = ccpAdd(menu.position, ccp(totalWidth/2 - totalPanelWidth/2, 0));

Note that the panels are the visual representation but we haven’t added in any scrolling dynamics. To do that we need to add a UIScrollView.

Adding the UIScrollView

Here we do two things:

1. Add our CocosOverlayScrollView which is only one panel wide (less than the whole screen). If we had this layer only then we wouldn’t be notified of touches on the edge of the screen.

2. We add the TouchDelegatingView which is full screen. The TouchDelegatingView will delegate any touches it receives to our paging scroll view

# HCUPPanelScene.m
// Note that we're only concerned with a horizontal iPhone. If your game is
// vertical, change accordingly
touchDelegatingView = [[TouchDelegatingView alloc] initWithFrame:CGRectMake(0, 0, 320, 480)];
scrollView = [[CocosOverlayScrollView alloc] initWithFrame:CGRectMake(0, 0, 320, totalPanelWidth)
                                                  numPages: numberOfPages
                                                     width: totalPanelWidth
                                                     layer: panels];
touchDelegatingView.scrollView = scrollView;
 
// this is just to pre-set the scroll view to a particular panel
[scrollView setContentOffset: CGPointMake(0, currentWorldOffset * totalPanelWidth) animated: NO];
 
// Add views to cocos2d
// We called it a TouchDelegatingView, but it actually isn't containing anything at all.
// In reality it is just taking up any space under our ScrollView and delegating the touches. 
[[[CCDirector sharedDirector] openGLView] addSubview:touchDelegatingView];
[[[CCDirector sharedDirector] openGLView] addSubview:scrollView];
 
[scrollView release];
[touchDelegatingView release];

You can configure your UIScrollView options by simply changing the code in CocosOverlayScrollView#initWithFrame:numPages:width:layer. (Note that this class was originally written by Alexander Repty)

The TouchDelegatingView simply delegates any touches it receives to the CocosOverlayScrollView.

And there you have it! Feel free to fork and make any changes to the code and send me a pull request.

What do you think? Have any ideas for cleaning it up? Leave your comments below!

Share:

We’re on a quest to write a scalable web crawler. Our goal is to build a web crawler that will download a billion pages a week. We’ve calculated that to download a billion pages in a week we need to sustain a rate of 1653 pages per second .

The problem with these kinds of numbers is that, unless you are familiar with web-crawling, it is not obvious how fast that really is. How fast can a simple crawler go? 10 pages per second? A thousand?

We set out to benchmark the simplest thing that could possibly work: wget and xargs.

Our Tools

wget is a popular tool used for downloading files from the web. It has a flexible set of options and built in support for crawling.

xargs is used to run a command repeatedly over a given set of inputs. In our case, we’re using a fixed URL list as our input. We use xargs as our “thread-pool” (it’s actually a “process-pool”). Using the -P <numprocs> option. xargs will run through the input file of URLs and each wget process will take a URL off the stack and run until it finishes the crawl for that domain. The number of concurrent processes is limited by <numprocs>.

Napkin Calculations

Before we actually run our jobs, let’s try to predict the kind of results we’ll get. I’m running the jobs on my MacBookPro Intel Core 2 Duo with 4GB RAM. I’m on my home network where I have AT&T U-Verse with advertised download speed of 18Mbps (mega bits per second).

wget measures rate limiting in kilobytes rather than kilobits, so we’ll use bytes rather than bits:

18Mbps = 2.25 megabytes per second =~ 2300 kilobytes/s

We’re just doing rough calculations at this point, so lets just guess that the mean size of each page is 10KB. At this page size, the absolute best number we can expect to get is around 230 pages/second before we saturate my connection.

Politeness

While we want our crawler as a system to go as fast as possible, we don’t want to hit any one server too many times. Not only might we get banned, but we it isn’t kind to the site owners. Many smaller servers can’t handle the load of a crawler thrown against it at full speed.

So if we want to get to 200+ pages/sec we’re going to have to have many concurrent connections. wget has a number of options that we can set to be nicer to each individual server. So our strategy will be to crawl many servers concurrently, but only hit a particular server lightly.

Here are a few of the relevant wget options we will set:

• --wait=2 and --random-wait – wait a random amount of time between requests averaging 2 seconds. The waiting time is for the servers benefit but the random time is for ours. Given that we are going to be running a large number of processes in parallel, we’d rather have them be out of step with each other.
• --tries=5 – only retry 5 times
• --timestamping – If the file exists on disk, send the server a HEAD request and check the Last-Modified header. If the file on disk has a timestamp greater than or equal to the Last-Modified date, we don’t request the whole page. This extra HEAD request doesn’t really slow us down because wget will only request it if the file already exists on disk. This is just a little extra protection in case our separate processes start to visit the same sites.

DMOZ Sample Set

For multiple runs of our test we don’t want to hit one particular server repeatedly. We’re going to use DMOZ to get a random sample of URLs to test and use a few commands to extract some random URLs:

mkdir -p data/dmoz
curl -0 http://rdf.dmoz.org/rdf/content.rdf.u8.gz > data/dmoz/dmoz-content.rdf.u8.gz
cd data/dmoz
unzip data/dmoz/dmoz-content.rdf.u8.gz
cat dmoz-content.rdf.u8 | grep http | grep r:resource | \
    grep -o '<link r:resource=['"'"'"][^"'"'"']*['"'"'"]' | \
    sed -e 's/^<link r:resource=["'"'"']//' -e 's/["'"'"']$//' \
    > urls.txt
ruby random-lines.rb urls.txt 300 > random-urls.txt

(You can get the random-lines.rb script here).

The DMOZ file is around 300MB so this will take a few minutes. The DMOZ RDF file is well formed, so we’re just using grep and sed to extract the URLs.

Shaping wget

Our wget command is below. You can see we aren’t trying very hard to access a page that doesn’t respond quickly (the various timeout options). Also, we’re only looking 5 pages deep per URL. We are not visiting any “parent” pages, that is, we’re not crawling up any directories. We don’t want any images or binary files (the reject) options and we don’t care about invalid SSL certificates (no-check-certificate).

wget \
  --tries=5 \
  --dns-timeout=30 \
  --connect-timeout=5 \
  --read-timeout=5 \
  --timestamping \
  --directory-prefix=data/pages \
  --wait=2 \
  --random-wait \
  --recursive \
  --level=5 \
  --no-parent \
  --no-verbose \
  --reject *.jpg --reject *.gif \
  --reject *.png --reject *.css \
  --reject *.pdf --reject *.bz2 \
  --reject *.gz  --reject *.zip \
  --reject *.mov --reject *.fla \
  --reject *.xml \
  --no-check-certificate

DNS

A nice thing about our setup is that each wget process is assigned to one domain. wget caches the DNS lookup so we only need to make one DNS request per process. A problem with this setup is that wget uses gethostbyname (or getaddrinfo depending on your platform). A quick check on man gethostbyname shows that on my BSD-based Mac gethostbyname is thread-safe e.g. it is synchronized. The result is that there is going to be some resource starvation when we have hundreds of wget processes all trying to call BIND all at the same time. 1

We set a DNS timeout of 30 seconds here, but in practice I found that it didn’t matter much. All of the processes race to grab the DNS lookup lock at the beginning, a large number time-out (waiting for the lock), but the requests even out over a couple of minutes.

xargs

xargs acts as our thread-pool or, more specifically, our process-pool.

-P specifies the number of processes to use. -I <sub> is a substitution parameter. It means “for each line in STDIN run CMD substituting the current line for <sub>“. So below we substitute _URL_ with the actual URL contained in the URLS_FILE.

cat $URLS_FILE | xargs -P $CRAWLERS -I _URL_ $WGET_CMD _URL_

Code

Our crawler script looks like this:

#!/bin/bash
# a basic crawler in bash
# usage: crawl.sh urlfile.txt <num-procs>
URLS_FILE=$1
CRAWLERS=$2

mkdir -p data/pages

WGET_CMD="wget \
  --tries=5 \
  --dns-timeout=30 \
  --connect-timeout=5 \
  --read-timeout=5 \
  --timestamping \
  --directory-prefix=data/pages \
  --wait=2 \
  --random-wait \
  --recursive \
  --level=5 \
  --no-parent \
  --no-verbose \
  --reject *.jpg --reject *.gif \
  --reject *.png --reject *.css \
  --reject *.pdf --reject *.bz2 \
  --reject *.gz  --reject *.zip \
  --reject *.mov --reject *.fla \
  --reject *.xml \
  --no-check-certificate"

cat $URLS_FILE | xargs  -P $CRAWLERS -I _URL_ $WGET_CMD _URL_

I’ve put this code on github with a Rakefile so you can follow along.

git clone git://github.com/jashmenn/bashpider.git
cd bashpider
rake data:get_urls # downloads and parses DMOZ, will take a while
rake crawl:restart # this will run a crawl

If you want to monitor the downloads per second, in another window type the following:

rake crawl:watch

When you feel you’ve gathered enough data, CTRL-C to kill both windows and then type:

rake results:process

Results at Home

As you can see from the chart, on my home computer through u-verse we max out at about 150 agents at 27 pages/sec, far below our original estimate of 200 pages/sec.

procs pages/sec
10     3.9
25     8.9
50    15.8
75    19.7
100   25.8
125   26.1
150   27.3
175   22.3
200    6.0

First of all, our initial estimate of 10KB per page was too low. In reality we observed a mean page size of around 37KB. This means on our 2300KB connection we can only expect a best-case download rate of 62 pages/sec. Still, 27 pages/sec is not even half that speed.

The other problem could be DNS requests. My home router also serves as my DNS server. It’s good enough for home use, but I’m pretty sure it’s not up to this task. Come to think of it, I’m not even sure how fast this CAT5 cable is.

I think it’s time to try out this setup in a better environment.

In the Data Center

For this experiment we loaded our script onto a beefy 8-core machine with a fat bandwidth connection.

The results were much better:

procs  pages/sec
  150   54
  200   71
  300  107
  400  141
  500  178
  600  214
  700  244
  800  386
  900  327
 1000  203
 1100  222
 1200  392
 1300  202
 1500  249
 1600  485
 2000  577
 3000  679
 3500  459
 4000  336

Take these numbers as rough estimates. For each of these entries I only let them run for a few minutes.

Processes

When I started getting into the thousands of processes, I wondered if I would hit the user process limit. Jay Donnell pointed out to me that uname will also give the process limit:

 ulimit -a
 max user processes              (-u) 268287

So with 260k+ processes available, we have no problem there.

Files

Using wget process gets its own file, which is uncompressed. So we’ve got a lot of disk IO going on. We’d probably save a good amount of time if each process just opened one file and appended content to it. We’d also save the file system from creating hundreds of thousands of inodes.

Also, the decline we see around 3000 agents may be due, in part, to the max number of open files on our system:

$ ulimit -a
open files                      (-n) 1024

Each crawler waits an average of 2 seconds before making the next request, at which time it makes the request and then downloads the file. So each process is making 1 file every >2 seconds. This means the number of wget processes we can run should be at least twice the max number of open files (2048).

My theory is this: at around 3000 concurrent agents the time it takes to actually download the content means that the probability that we will have enough file descriptors available. However, once we have 4000 concurrent agents the probability that any two agents will need to write a file at the same time is much higher, we see a significant performance drop.

I think we’re going to need to look at the file system format. Currently we’re using ext3, but I’m not sure if we should switch to xfs. While monitoring the file count using find I kept getting the following error:

find: WARNING: Hard link count is wrong for <some file>: this may be a bug
    in your filesystem driver.  Automatically turning on find's -noleaf option.
    Earlier results may have failed to include directories that should have been searched.

Also kjournald seemed to be working very hard to keep up with all the file writes. I’m not sure if this is unavoidable or not. I’m going to leave this problem for future work.

Summary

This crawler is just a baseline to see what performance is possible of basic unix utilities. Obviously, this approach used a list of static URLs and in a “real” crawler you probably want to have a mechanism for communicating and prioritizing URLs throughout the system.

That said, if you already know the list of URLs you want to download, you could download tens-of-million pages over a 24-hour window. For instance, if we assume a sustained rate of 600 pages per second you could download 51.8 million pages in 24 hours.

So how long would it take to download a billion pages with xargs and wget?

If you had the list of URLs beforehand, according to these numbers it would
take 19 days .

To download a billion pages is a week we’re going to need to figure out a way to download at least 1000 more pages per second.

What we’ve learned:

• watch out for file limits
• append to a single file rather than creating thousands of tiny files
• run your own non-locking DNS server
• unix tools are handy and powerful

What do you think?

Any suggestions for cranking out more performance out of wget? Should I try increasing my open file limit and see what happens? Think these numbers are ridiculous? Leave a comment below!

Share:

I was trying some remote git repo tests last night, and when I went to push my changes, I received this warning message:

warning: updating the currently checked out branch; this may cause confusion, as the index and working tree do not reflect changes that are now in HEAD.

On remote server I created a directory and did “git init“. Then cloned it from my local machine, did changes, committed, and then push. All seemed straightforward there. Any thoughts?

The issue git is warning you about is that your remote has both the repository and a working copy. That is, on the remote server you have a directory project/ with files in it (the working copy) and the folder project/.git (the repository).

If you push from your local machine to the remote, you will only be updating files in the repository and not the working copy. That is, the non-git files will not be changed. This can be confusing because you might log into the remote after you push an expect the working copy to be different.

To deal with this possible confusion git init provides a --bare option. What this does is create the repository only (no working copy). You can then push and pull from the remote like you might a central svn server.

Let me show an example. Say I have an existing git repository on my local machine and I want to create a new remote to back it up. My workflow would look like this:

ssh me@myserver.com
mkdir ~/git/newproject.git
cd ~/git/newproject.git
git init --bare
exit
git remote add myserver me@myserver.com:/home/nmurray/git/newproject.git
git push myserver master

If you want, you could even chain these together as a single command:

ssh me@myserver.com "mkdir ~/git/newproject.git && cd ~/git/newproject.git && git init --bare" && echo git remote add myserver me@myservercom:/home/nmurray/git/newproject.git

Hope this helps!

Share:

I like to use Cascading (or cascalog) for my Hadoop jobs, but out of the box Cascading doesn’t support using SequenceFiles that were created outside of Cascading. That is to say, Cascading requires that your SequenceFiles values be an instance of Tuple.

The solution is to create your own Scheme that parses a SequenceFile according to your own format. In my case I just want to parse each line as the string list.

The code is simple but may not be obvious for a first-time Cascading user. I hope this will save someone a few minutes.

    package com.xcombinator;
 
    import java.io.IOException;
 
    import cascading.tap.Tap;
    import cascading.tuple.Fields;
    import cascading.tuple.Tuple;
    import cascading.tuple.TupleEntry;
    import cascading.tuple.Tuples;
    import cascading.scheme.SequenceFile;
    import org.apache.hadoop.mapred.JobConf;
    import org.apache.hadoop.mapred.OutputCollector;
    import org.apache.hadoop.mapred.SequenceFileInputFormat;
    import org.apache.hadoop.mapred.SequenceFileOutputFormat;
 
    /**
     * A SequenceFileAsText is a type of {@link SequenceFile}, however the
     * SequenceFile has been created outside of Cascading and is assumed to have a
     * value of a string.
     */
    public class SequenceFileAsText extends SequenceFile
      {
      /** Field serialVersionUID */
      private static final long serialVersionUID = 1L;
 
      /** Protected for use by TempDfs and other subclasses. Not for general consumption. */
      protected SequenceFileAsText()
        {
        super( null );
        }
 
      /**
       * Creates a new SequenceFileAsText instance that stores the given field names.
       *
       * @param fields
       */
      public SequenceFileAsText( Fields fields )
        {
        super( fields );
        }
 
      @Override
      public Tuple source( Object key, Object value )
      {
        if (value instanceof Tuple)
        {
          return (Tuple) value;
        }
        else if (value instanceof Comparable)
        {
          return new Tuple((Comparable) value);
        }
        else if (value != null)
        {
          return new Tuple(String.valueOf(value));
        }
        else
        {
          return new Tuple((Comparable)null);
        }
      }
 
    }

Share:

Git Cheat Sheet Preview

I realize there are a number of cheatsheets for git already. However, I wanted a simple, one-page sheet specifically for my attendees.

You can download it here:

• git cheatsheet pdf
• git cheatsheet LaTeX source

Like it? Hate it? Find a typo? Leave your feedback in the comments!

Here are my raw notes from the talk:

;; -*- mode: Markdown; -*-

# How to read:
commands are indented
actions to perform while presenting are marked with @
left to right

# Welcome
see progit.org
what is version control

why use it:

  * backup/restore
  * synchronization sharing
  * track changes
  * ownership
  * branching and merging

who has used subversion 

git
  * you've heard its distributed
  * b/c branching and merging

pace - slow, no slides

leave with practical understanding

# Install & Config

    sudo port install git-core +svn
    git config --global user.name "Nate Murray"
    git config --global user.email "nate@natemurray.com"

# Basic Commands

    cd ~
    mkdir -p projects/demo       # explain only a little
    cd projects/demo
    git init
    git status                   # nothing here
    ls -a                        # talk .git repository vs. working copy
    echo "version 1" > README.txt
    git status                   # untracked file
    git add README.txt
    git status                   # changes to be committed
    git commit -m "added version one of the file"
    git status                   # clean

stop, draw the picture of the local operation phases - e.g. svn vs. git

> Principle 1: (almost) everything is local

so now that you know about the staging area, lets do it again

    echo "new file" > sheep.rb
    git status                   # draw untracked
    git add sheep.rb
    git status                   # draw staged
    git commit -m "added"

    cat README.txt                 # draw unmodified
    echo "version 2" > README.txt
    git status                   # draw modified
    git commit -a -m "updated version" # shorthand for git add
    git status

Tips:

    git config --global alias.st status
    git st

# Git Internals

* Before we can talk about branching you *have* to understand how git (tried to avoid this)
* files and folders

three objects -  @ Draw first commit

  * blob        - raw data
  * tree        - folder (stores blobs and trees)
  * commit      - snapshot of the repo + meta 

You won't need to use `git cat-file` on a daily basis. however, understanding
the concepts we're going to talk about is really important for branching.

    git log # view the log
    git show ----  # first commit, whatever it is

    git cat-file -p  ---- # first commit
    git cat-file -p  ---- # tree
    git cat-file -p  ---- # blob

draw the rest using git `cat-file`

    git log           # show the log again
    git cat-file -p ---- # second commit

draw the picture. point out the parent connection.
note committer / author

    git cat-file -p ---- # tree

note here there are two blobs!

finish drawing out the second commit
* git stores reference to first file.
* snapshot of the *whole project*
* git stores each file once
* filename is in the `tree` 

draw the last commit

     git log
     git cat-file -p ---- # third commit

> Principle #2 : Git commits are snapshots

* A commit in git is a snapshot of the entire project, not just a list of diffs.
* snapshot is based on the SHA hash function. guarantees file integrity

# refs/branches

questions?

@ stop. redraw commits as *linear* . looking only at commits

ready to define a branch
a branch is a pointer to a commi
text file with a sha. thats it. 

start with one branch called `master`

    git branch

bash prompt

    # skip this
    tree .git/refs/
    cat .git/refs/heads/master
    git log
    # compare the SHAs

update diagram by adding a `ref` to our commit. (`master`). 

@ draw circle pointing to commit

create testing branch

# branching

So lets create another branch:

    git branch testing
    git branch

only created, didn't switch. just created a ref pointing to this
commit

@ update diagram

How does git know what branch we are "on"?

special ref called `HEAD` that points to the local branch
since we are still on master HEAD points to master

@ add HEAD

To switch working copy, use the `git checkout`

    git checkout testing
    git branch

HEAD moves from `master` to `testing`

@ update diagram

master and testing point to the same commit, working directory isn't changed

checkout means something different in git than it does in svn.
checkout in git to switch our working directory to a particular commit. 

now make changes:

    cat README.txt
    echo "we are on the testing branch!" > README.txt
    cat README.txt
    git commit -a -m "updated the readme"
    git log

@ update diagram, adding new commit. move the testing ref and the HEAD ref with it

add a "test"

    echo "this is a test" > test.rb
    git add test.rb                    # stage it for our commit
    git commit -m "added a test"       # now commit
    git log

@ update diagram - should have two commits

hotfix - scenario: you need to switch back to master

    git checkout master
    ls

@ move HEAD

so notice two things.
1) switching to this branch was fast - everything is local
2) our file test.rb is absent

and if we

    cat README.txt

it says 'version 2' just like we would expect

    echo "applying fix" >> sheep.rb
    cat sheep.rb
    git commit -a -m "applied important fix"
    git log
    git cat-file -p ---- # last commit

@ draw the new commit, and draw its reference back to the parent. move HEAD and master

now fixed, can push into production
and get back to work in `testing`

    git checkout testing
    cat README.txt
    cat test.rb

This is a general pattern:

> Principle #3: Branching is cheap, use it often

If you are working on a particular feature, create a branch. 

If you're coming from svn, making frequent branches might seem unnatural.
in svn, a branch is global -> namespace issues.
vs. git: private branches
name your branch 'test' and it won't collide with anyone elses

But branching itself isn't that useful unless its easy to merge.

* how many of you have merged a branch in svn?
* how many of you enjoyed it?

merging is one of git's strength and git makes it relatively easy

# merging

    cat sheep.rb

two branches: `master` and `testing` - need to merge

    git checkout master
    git merge testing
    git show HEAD

instead of a 'parent' we have a line that says 'merge'
a merge commit has more than one parent

@ draw the commit object
@ draw lines to the commits

    gitx

sometimes merging doesn't go as planned - conflicts

    git checkout -b breaker

this is shorthand for create and then checkout a new branch based on the
current HEAD

    vi sheep.rb # changing fix
    git commit -a -m "changed the fix"
    git checkout master
    vi sheep.rb # improving fix
    git commit -a -m "improved the fix"

@(update diagram, adding breaker and master refs)

    git merge breaker
    git status

there are many diff viewing tools.
* perforce
* opendiff - from apple

    git mergetool -t opendiff

I don't really like using the visual tools.
Sometimes you need character level editing

    vi sheep.rb
    git add sheep.rb
    git commit -a

talk about merge with conflicts

@ update diagram draw new merge commit

    gitx

Questions?

# Remotes

Everything so far on one machine. 

I work offline (I take the train)
If I break something I can rollback see where I was an hour ago 

want to share our changes.
might seem scary or messy because changes to totally independent lines of the code.
but in practice its not a problem.

svn version numbers are incremental - so two repos would get out of
step
no easy way of merging two separate repostories. 

git blob identifiers are a SHA of the content.
if the same content is created anywhere in the universe you'll still
have the same SHA

git doesn't care about where your commits come from or how you get them

Protocols:
  * ssh
  * git
  * http
  * local file system

sample project on our github

    cd ..
    open http://XXX/nmurray/simple-echo
    git clone git@XXX:nmurray/simple-echo.git
    cd simple-echo
    git log

svn checkout just HEAD
vs. git - whole repo

To be able to collaborate with others you have to manage 'remote repositories'.
When you clone a project, you have a default remote called 'origin'. 

    git remote -v

Remotes are pointers to other repositories that are _usually_ over the network.
'pull' and 'push' changes.

    vi README.mkd
    # make a change
    git commit -a -m "make a change"
    git push

If someone else makes a change:

    git pull origin master

This means pull from `origin` the branch `master` into local branch `master`. You can often to just

    git pull

which means pull from origin whatever branch Im on (i.e. HEAD) into this branch.

Now let's say someone pushes a change and I make a change
I can't push unless I pull first. This is good.

# remote forks

So that is while we are on the same line. What if were on different lines?

@(open up webbrowser again)

Bh also has forked my project. But when we say forked, all the means is he has
created his own development line from some of my commits

    git remote add bh git@XXX:bhenderson/simple-echo.git
    git remote -v

Now you shouldn't be surprised to learn that adding the remote doesn't change
anything. First we have to `fetch` hist changes

    git fetch bh

`fetch` brings his commits into my repo but again, doesnt change my working copy.

fetch brought branches + commits into repo
work with those branches just like any other branch.

    git branch -a

So you see here we have 

* `master`, which is our local master
* we have at the bottom `origin/master` which is the origin where we pulled from branch master
* and then we have `bh/master`, which is bhendersons master branch

These are all regular branches: they are just pointers to commits. We
can even checkout as branch 

    git checkout bh/master

scary message

    git checkout master

So how would we merge bhendersons changes with our own? I'm sure you could guess by now. Simply:

    git merge bh/master # don't press enter!!!

But lets take it up a notch.
say you didn't want to merge bh changes in your master branch.
real world, you might not know if his changes would merge cleanly
don't want to mess up your master branch.  

What we are going to do is
* create a new branch,
* merge bhs branch in THAT branch
* then we're going to merge to master.

It will make more sense when we do it. Lets try:

Okay we first want to create a new branch based on our master

    git checkout -b bh-merge
    git branch -a 

Now lets merge his changes

    cat simple-echo.rb
    git merge bh/master
    cat simple-echo.rb
    git log                  # see bh as the author of the commit

okay everything was clean! *phew* now lets go back to master

    git checkout master
    git merge bh-merge
    git log

and there we go! merged nicely.
now I don't need bhendersons merge branch anymore, so lets delete it

    git branch -d bh-merge
    git branch -a

git is distributed

Instead of one central server, that everyone has to sync to,
* independent lines of work can go on.
* If someone creates something good in their branch, they just tell people about it.
* permission-less 

you can see why it is so good for open-source development

questions about branching?

# Advanced

* tagging
* rebase
* cherry pick
* git bisect
* hooks
* tracking branches
* submodules
* interactive staging
* squashing commits
* git-svn
* setting up your own server
* patches via email
* gitjour

Share:

Scalability

The web is enormous and continually growing. A crawler should scale
linearly with the number of agent-machines that are added to the
system. This allows us to add more agents as our needs increase.

Speed

Speed is a significant issue at this scale. For example, if we want to crawl 1
billion pages in a week (this is less than 1/1000th of the web), our system
will have to sustain a rate of 1653 downloads per second.

To achieve this speed we need to employ a number of techniques such as
concurrent connections, data compression, dns caching, minimize disk seeks,
etc.

Politeness

While we need a high rate of download, we must be polite and not
overload one particular server. Najork et. al. propose limiting requests to
a single server by waiting 10 times the time it took to download the
last page. 1

Quality

We aim to build a crawler that visits “high-quality” or “relevant” pages
well-known quality metric. However, Najork et. al. found that a simple
breadth-first crawl tends to visit high-quality pages first 2.
We’ll eventually build a more intelligent page-selection mechanism, but for now
breadth-first will work.

Agents as a Distributed System

Given that the crawling problem cannot be solved by a single machine,
we are required to form our solution as a distributed
system. Distributed systems introduce more room for failures
and errors in coordination. Therefore we define the following desirable
features for our distributed system:

Fault Tolerance

Hardware failure is unavoidable. The failure of one node should not
prevent survivors from continuing to operate.

Even Partitioning

The URL frontier should be evenly distributed across all agents to
evenly assign the work. Many crawlers use a hashing function to distribute
the URLs among machines.

Minimize Overlap

Overlap is defined as (n-u)/u, where n is the total number of
crawled pages and u is the number of unique pages (sometimes u < n
because the same page has been erroneously fetched several times).
Optimally, we want an overlap of 0. 3

Agent churn

During the crawl we may want to add additional resources. The system
should support agents coming and leaving the group.

Next Steps

There are five major parts to a web crawler:

• The URL frontier
• IP address lookup
• Page download
• Page processing
• Tracking URLs encountered

Over the next few articles we will be designing a each of the five
components. The list of desirable features give us guidelines
that help shape the decisions about each component.

1. Najork M. High-Performance Web Crawling. Systems Research. 2001.
2. Najork M, Wiener JL. Breadth-First Search Crawling Yields High-Quality Pages. Systems Research. 2001:114-118.
3. Boldi P, Codenotti B, Santini M, Vigna S. UbiCrawler: a scalable fully distributed Web crawler. Software: Practice and Experience. 2004;34(8):711-726.

Share: