private static int computeSum(BufferedImage image, int regionX1, int regionY1, int regionX2, int regionY2) {
   //Compute a sub-region of the image 
   int sum = 0;
   Raster data = image.getData();
   for (int x = regionX1; x <= regionX2; x++) {
      for (int y = regionY1; y <= regionY2; y++) {
         int value = data.getSample(y, x, 0);
         sum = sum + value;
      }
   }
   return sum;
}

public class IntegralImage {
   private int[][] integralImage = null;
	
   public IntegralImage(BufferedImage image) {
      int originalImageHeight = image.getHeight();
      int originalImageWidth = image.getWidth();
      integralImage = new int[originalImageHeight][originalImageWidth];
      Raster originalPixels = image.getData();

      int originalPixelValue = 0;
      for (int row = 0; row < originalImageHeight; row++) {
         for (int column = 0; column < originalImageWidth; column++) {
      originalPixelValue = originalPixels.getSample(column, row, 0); 

         //For the leftmost pixel, just copy value from original
         if (row == 0 && column == 0) {
            integralImage[row][column] = originalPixelValue;
         }

        //For the first row, just add the value to the left of this pixel
         else if (row == 0) {
             integralImage[row][column] = originalPixelValue + integralImage[row][column - 1];
         }

        //For the first column, just add the value to the top of this pixel
         else if (column == 0) {
            integralImage[row][column] = originalPixelValue + integralImage[row - 1][column];       
         }

       //For a pixel that has pixels to its left, above it, and to the left and above diagonally, 
       //add the left and above values and subtract the value to the left and above diagonally
       else {
          integralImage[row][column] = originalPixelValue + integralImage[row][column - 1] + integralImage[row - 1][column] - integralImage[row - 1][column - 1];
       }
    }
}

public int total(int x1, int y1, int x2, int y2) {
   int a = x1 > 0 && y1 > 0 ? integralImage[x1-1][y1-1] : 0;
   int b = x1 > 0 ? integralImage[x1-1][y2] : 0;
   int c = y1 > 0 ? integralImage[x2][y1-1] : 0;
   int d = integralImage[x2][y2];
   return a + d - b - c;
}

Blur is a new Apache 2.0 licensed software project that provides a search capability built on top of Hadoop and Lucene. Elastic Search and Solr already exist so why build something new? While these projects work well, they didn't have a solid integration with the Hadoop ecosystem. Blur was built specifically for Big Data, taking scalability, redundancy, and performance into consideration from the very start, while leveraging all the goodness that already exists in the Hadoop stack.

A year and a half ago, my project began using Hadoop for data processing. Very early on, we were having networking issues that would make our HDFS cluster network connectivity spotty at best. Over one weekend in particular, we steadily lost network connection to 47 of the 90 data nodes in the cluster. When we came in on Monday morning, I noticed that the MapReduce system was a little sluggish but still working. When I checked HDFS I saw that our capacity had dropped by about 50%. After running an fsck on the cluster I was amazed to find that what seemed like a catastrophic failure over the weekend resulted in a still healthy file system. This experience left a lasting impression on me. It was then that I got the idea to somehow leverage the redundancy and fault tolerance of HDFS for the next version of a search system that I was just beginning to (re)write.

I had already written a custom sharded Lucene server that had been in a production system for a couple of years. Lucene worked really well and did everything that we needed for search. The issue that we faced was that it was running on big iron that was not redundant and could not be easily expanded. After seeing the resilient characteristics of Hadoop first hand, I decided to look into marrying the already mature and impressive feature set of Lucene with the built in redundancy and scalability of the Hadoop platform. From this experiment Blur was created.

The biggest technical issues/features that Blur solves:

• Rapid mass indexing of entire datasets
• Automatic Shard Server Failover
• Near Real-time update compatibility via Lucene NRT
• Compression of Lucene FDT files while maintaining random access performance
• Lucene WAL (Write Ahead Log) to provide data reliability
• Lucene R/W directly into HDFS (the seek on write problem)
• Random access performance with block caching of the Lucene Directory

Data Model

Data in Blur is stored in Tables that contain Rows. Rows must have a unique row id and contain one or more Records. Records have a unique record id (unique within the Row) and a column family for grouping columns that logically make up a single record. Columns contain a name and a value, and a Record can contain multiple columns with the same name.

Architecture

Blur uses Hadoop's MapReduce framework for indexing data, and Hadoop's HDFS filesystem for storing indexes. Thrift is used for all inter-process communications and Zookeeper is used to know the state of the system and to store meta data. The Blur architecture is made up of two types of server processes:

• Blur Controller Server
• Blur Shard Server

The shard server, serves 0 or more shards from all the currently online tables. The calculation of the what shards are online in each shard server is done through the state information in Zookeeper. If a shard server goes down, through interaction with Zookeeper the remaining shard servers detect the failure and determine which if any of the missing shards they need to serve from HDFS.

The controller server provides a single point of entry (logically) to the cluster for spraying out queries, collecting the responses, and providing a single response. Both the controller and shard servers expose the same Thrift API which helps to ease debugging. It also allows developers to start a single shard server and interact with it the same way they would with a large cluster. Many controller servers can be (and should be) run for redundancy. The controllers act as gateways to all of the data that is being served by the shard servers.

Updating / Loading Data

Currently there are two ways to load and update data. The first is through a bulk load in MapReduce and the second is through mutation calls in Thrift.

Bulk Load MapReduce Example

Data Mutation Thrift Example

Searching Data

Any element in the Blur data model is searchable through the normal Lucene semantics: analyzers. Analyzers are defined per Blur table.

The standard Lucene query syntax is the default way to search Blur. If anything outside of the standard syntax is needed, you can create a Lucene query directly with Java objects, and submit them through the expert query API.

The column family grouping within Rows allows for results to be discovered across column families similar to what you would get with an inner join across two tables that share the same key (or in this case rowid). For complicated data models that have multiple column families, this makes for a very powerful search capability.

The following example searches for "value" as a full text search. If I had wanted to search for "value" in a single field like column "colA" in column family "famB" the query would look like "famB.colA:value".

Fetching Data

Fetches can be done by row or by record. This is done by creating a selector object in which you specify the rowid or recordid, and the specific column families or columns that you would like returned. When not specified, the entire Row or Record is returned.

Current State

Blur is nearing it's first release 0.1 and is relatively stable. The first release candidate should be available for download within the next few weeks. In the meantime you can check it out on github:

https://github.com/nearinfinity/blur

http://blur.io

Near Infinity is proud to host a new Gradle Expert Training class, taught by Tim Berglund, the Author of the Gradle O'Reilly Book Series. This is an intensive and highly practical 3-day Gradle course. You will become familiar with all major concepts of Gradle and how to best use Gradle for simple as well as complex build scenarios. This course is packed with hands-on exercises.

To learn more please visit Gradeware's Gradle Expert Training course description. To register visit Gradeware's Gradle course registration web page.

Be sure to check out our Upcoming NIC-U Training Courses page for information on more upcoming courses.

Thrift In a Nutshell

Generating the Lucene Index

public class IndexBuilder {

    public static void main(String[] args) throws Exception {
        String namesFile = "names.csv";
        Document doc = new Document();
        Field[] fields = new Field[]{new Field("firstName", "", Field.Store.YES, Field.Index.ANALYZED_NO_NORMS),
                new Field("lastName", "", Field.Store.YES, Field.Index.ANALYZED_NO_NORMS),
                new Field("address", "", Field.Store.YES, Field.Index.ANALYZED_NO_NORMS),
                new Field("email", "", Field.Store.YES, Field.Index.ANALYZED_NO_NORMS)};
        addFieldsToDocument(doc, fields);

        BufferedReader reader = new BufferedReader(new FileReader(namesFile));

        IndexWriter indexWriter = new IndexWriter(FSDirectory.open(new File("blog-index")),new IndexWriterConfig(Version.LUCENE_31, new StandardAnalyzer(Version.LUCENE_31)));

        String line;
        while ((line = reader.readLine()) != null) {
            String[] personData = getPersonData(line);
            setFieldData(personData, fields);
            indexWriter.addDocument(doc);
        }
        indexWriter.optimize();
        indexWriter.close();
    }

    private static String[] getPersonData(String line) {
        return line.split(",");
    }

    private static void setFieldData(String[] data, Field[] fields) {
        int index = 0;
        for (Field field : fields) {
            field.setValue(data[index++]);
        }
    }

    private static void addFieldsToDocument(Document doc, Field[] fields) {
        for (Field field : fields) {
            doc.add(field);
        }
    }
}

Creating the .thrift File

//all generated java code will have the following for package name
namespace java bbejeck.thrift.gen

//this is the person object 
struct Person {
  1: string firstName,
  2: string lastName,
  3: string address,
  4: string email
}

//exception used to send meaningful error messages back to user
exception LuceneSearchException {
  1: string message
}

//service definition used by client and server
service LuceneSearch { 
    list<Person> search(1: string query) throws (1:LuceneSearchException error) 
}

• $ thrift --gen java lucene_search.thrift
• $ thrift --gen rb lucene_search.thrift

Thrift Server - Java

public class LuceneThriftServer {
    private static final int PORT = 9090;
    private static int numberThreads = 5;

    public static void main(String[] args) throws Exception {
        TServerSocket serverSocket = new TServerSocket(PORT, 100000);
        LuceneSearch.Processor searchProcessor = new LuceneSearch.Processor(new SearchHandler(args[0]));
        if (args.length > 1) {
            numberThreads = Integer.parseInt(args[1]);
        }
        TThreadPoolServer.Args serverArgs = new TThreadPoolServer.Args(serverSocket);
        serverArgs.maxWorkerThreads(numberThreads);
        TServer thriftServer = new TThreadPoolServer(serverArgs.processor(searchProcessor).protocolFactory(new TBinaryProtocol.Factory()));
        thriftServer.serve();
    }

Iface Implementation

public class SearchHandler implements LuceneSearch.Iface {
    private IndexSearcher searcher;
    private QueryParser queryParser;
    private static final int MAX_RESULTS = 1000;

    public SearchHandler(String indexPath) {
        try {
            searcher = new IndexSearcher(FSDirectory.open(new File(indexPath)), true);
            queryParser = new QueryParser(Version.LUCENE_31, null, new StandardAnalyzer(Version.LUCENE_31));
            queryParser.setAllowLeadingWildcard(true);
        } catch (IOException e) {
            throw new RuntimeException(e);
        }
    }

    public List<Person> search(String query) throws LuceneSearchException {
        List<Person> results = new ArrayList<Person>();
        try {
            Query q = queryParser.parse(query);
            TopDocs topDocs = searcher.search(q, MAX_RESULTS);
            for (ScoreDoc sd : topDocs.scoreDocs) {
                Document document = searcher.doc(sd.doc);
                results.add(getPersonFromDocument(document));
            }
        } catch (Exception e) {
            throw new LuceneSearchException(e.getMessage());
        }
        return results;
    }

    private Person getPersonFromDocument(Document document) {
        Person p = new Person();
        p.firstName = document.get("firstName");
        p.lastName = document.get("lastName");
        p.address = document.get("address");
        p.email = document.get("email");

        return p;
    }
}

Thrift Client - Ruby

module ThriftConnection

  class LuceneClient

    def initialize(host='localhost', port=9090)
      socket = Thrift::Socket.new(host, port)
      @transport = Thrift::BufferedTransport.new(socket)
      protocol_factory = ::Thrift::BinaryProtocolFactory.new
      protocol = protocol_factory.get_protocol(@transport)
      @transport.open
      @client = LuceneSearch::Client.new(protocol)
    end

    def search(query)
      @client.search(query)
    end

    def close
      @transport.close
    end

  end
end

Running With Scissors

#added to translate from symbol to expected search format
  SEARCH_KEYS_MAPPING = {:first_name => 'firstName',
                                            :last_name => 'lastName',
                                            :email => 'email',
                                            :address => 'address'}


  def self.method_missing(method_name, *args)
    lucene_client = ThriftConnection::LuceneClient.new
    query = ""
        #handles find_by_first_name etc
    if method_name.to_s =~ /^find_by_([a-z]+_?[a-z]*)$/
      query = "#{SEARCH_KEYS_MAPPING[$1.to_sym]}:#{args[0]}"
        #handles find_by_first_name_or_last_name, find_by_first_name_and_email 
    elsif method_name.to_s =~/^find_by_([a-z]+_[a-z]+)_([a-z]+)_([a-z]+_?[a-z]*)$/
      query ="#{SEARCH_KEYS_MAPPING[$1.to_sym]}:#{args[0]} #{$2.upcase} #{SEARCH_KEYS_MAPPING[$3.to_sym]}:#{args[1]}"
    else
       raise ArgumentError.new("search method pattern #{method_name} not recognized")
    end

    results = lucene_client.search(query)
    lucene_client.close
    results
  end

Testing

head names.csv

cat names.csv | grep -iE 'elizabeth|krause' | wc -l 

class SearchTest < Test::Unit::TestCase

  def setup
    @lucene_client = ThriftConnection::LuceneClient.new
  end


  def teardown
    @lucene_client.close
  end

  def test_search_client_first_name
    persons = @lucene_client.search("firstName:Tia")
    assert_equal(5, persons.length)

    persons.each do |person|
      assert_equal("Tia", person.firstName)
    end
  end

  def test_search_person_class_first_name
    persons = Person.find_by_first_name("Tia")
    assert_equal(5, persons.length)

    persons.each do |person|
      assert_equal("Tia", person.firstName)
    end
  end

  def test_search_client_first_name_email_domain
    persons = @lucene_client.search("+firstName:Elizabeth +email:*pookmail.com")
    assert_equal(59, persons.length)
  end

  def test_search_person_class_first_name_email_domain
    persons = Person.find_by_first_name_and_email("elizabeth", "*pookmail.com")
    assert_equal(59, persons.length)
  end

  def test_search_client_first_name_and_last_name
    persons = @lucene_client.search("+firstName:Elizabeth +lastName:Krause")
    assert_equal(1, persons.length)
    person = persons[0]

    assert_equal("Elizabeth", person.firstName)
    assert_equal("Krause", person.lastName)
  end

  def test_search_person_class_first_name_and_last_name
    persons = Person.find_by_first_name_and_last_name("elizabeth", "krause")
    assert_equal(1, persons.length)
    person = persons[0]

    assert_equal("Elizabeth", person.firstName)
    assert_equal("Krause", person.lastName)
  end

  def test_search_person_class_first_name_or_last_name
    persons = Person.find_by_first_name_or_last_name("elizabeth", "krause")
    assert_equal(289, persons.length)
  end

  def test_invalid_search
    assert_raises ArgumentError do
      Person.find_person_by_name("tia")
    end
  end

end

Conclusion

Resources

• For more information on thrift the thrift wiki is a great start
• More information on Lucene can be found here

/**
  * Obtain the status of JMS queues and topics
  * @return List of all JMSDestinationRuntimeMBean objects (one per destination)
  */
private static List<JMSDestinationRuntimeMBean> getJMSStatus()
{
    List<JMSDestinationRuntimeMBean> destinations = new ArrayList<JMSDestinationRuntimeMBean>();
    try
    {
        // Look up the management bean home for the admin server
        Context ctx = new InitialContext();
        MBeanHome home = (MBeanHome) ctx.lookup(MBeanHome.ADMIN_JNDI_NAME);

        // Get all JMS server MBeans
        Set mbeanSet = home.getMBeansByType("JMSServerRuntime");

        // Iterate over the set to find the the JMS Server used by our application
	Iterator mBeanIterator = mbeanSet.iterator();
        while ( mBeanIterator.hasNext() )
        {
            JMSServerRuntimeMBean server = (JMSServerRuntimeMBean) mBeanIterator.next();

            // If it's our application-created JMS server, then get all of its destinations
            String name = server.getName().toUpperCase();
            if ( name.startsWith("JMSServerName") ) //insert the name of the JMS server used by the application
            {
                JMSDestinationRuntimeMBean[] dest = server.getDestinations();
                for ( int i=0; i < dest.length; i++ )
                {
                    //NOTE: This is where we would add another iteration to determine if the destination meets any provided filters
		    destinations.add(dest[i]);
                }
            }
        }
    }
    catch (Exception ex)
    {
        LOG.warn("Could not retrieve JMS statistics for all destinations", ex);
    }

    return(destinations);
}

    /**
    * Obtain the status of JMS queues and topics
    * @param jmsNameList required leading list of names of queue/topic (if null then all queues/topics returned)
    * @return List of all JMSStatus objects (one per destination)
    */
    public static List<JMSStatus> getJMSStatusByNamedList(List<String> jmsNameList)
    {
        QueryExp fullQuery = null;
        if (jmsNameList != null)
        {
            QueryExp query = null;
            for (String jmsName : jmsNameList)
            {
                AttributeValueExp attribute = Query.attr(mBeanName);
                StringValueExp name = Query.value(jmsName);
                query = Query.initialSubString(attribute, name);
                fullQuery = (fullQuery != null) ? Query.or(fullQuery, query) : query;
            }
        }

        return getJMSStatusByQuery(fullQuery);

    }

    /**
    * Obtain the status of JMS queues and topics
    * @param query optional QueryExp to filter the returned jms destinations (if null then all queues/topics returned)
    * @return List of all JMSStatus objects (one per destination) sorted by name
    */
    private static List<JMSStatus> getJMSStatusByQuery(QueryExp query)
    {
        List<JMSStatus> destinations = new ArrayList<JMSStatus>();
	private String[] mBeanAttributes = {"Name", "DestinationType", "MessagesCurrentCount",
            "MessagesPendingCount", "MessagesReceivedCount", "MessagesHighCount"};

        MBeanServerConnection connection = null;
        JMXConnector connector = null;

        try
        {
            connector = initConnection();
            connection = connector.getMBeanServerConnection();

            Set<ObjectName> mbeanSet = connection.queryNames(new ObjectName("*:*,Type=JMSDestinationRuntime"), query);
            for (ObjectName mbean : mbeanSet)
            {
                if (mbean.getKeyProperty("JMSServerRuntime").toLowerCase().startsWith("JMSServerName")) // Name of the application-created JMS Server name
                {
                        AttributeList attributes = connection.getAttributes(mbean, mBeanAttributes);
                    if (attributes.size() == mBeanAttributes.length)
                    {
			JMSStatus stat = new JMSStatus(
                                (Attribute) attributes.get(0),
                                (Attribute) attributes.get(1),
                                (Attribute) attributes.get(2),
                                (Attribute) attributes.get(3),
                                (Attribute) attributes.get(4),
                                (Attribute) attributes.get(5),
                                mbean.getKeyProperty("JMSServerRuntime"),
                                mbean.getKeyProperty("ServerRuntime"));

                        destinations.add(stat);
                 }
                }
            }
        }
        catch (Exception ex)
        {
            LOG.warn("Could not retrieve JMS statistics for all destinations", ex);
        }
        finally
        {
            if (connector != null)
            {
                try {
                    connector.close();
                } catch (IOException ex) {
                    LOG.warn("Could not close the MBean Server connection", ex);
                }
            }
        }

        return(destinations);

    }

    /**
    * Initialize the JMX connection to the WebLogic Admin MBeanServer.
    * @return JMXConnector for the MBeanServer connection
    */
    private static JMXConnector initConnection() throws IOException {

        JMXServiceURL serviceURL = new JMXServiceURL(protocol, host, port, jndiPath); // Update using the appropriate protocol, host, port, jndiPath

        Map<String,Object> env = new HashMap<String,Object>();
        env.put(Context.SECURITY_PRINCIPAL, "login");  // update with admin user login
        env.put(Context.SECURITY_CREDENTIALS, "password");  // update with admin user password
        env.put(JMXConnectorFactory.PROTOCOL_PROVIDER_PACKAGES, "weblogic.management.remote");
        env.put("jmx.remote.x.request.waiting.timeout", 10000);

        return JMXConnectorFactory.connect(serviceURL, env);
   }