Archive for May, 2010

17 May, 2010

To Trie or not to Trie – a comparison of efficient data structures

Posted by Bhavin Turakhia | (5) Comments

Since my discussion thread on the efficiency of the in-memory data structure of ZeroMQ with Martin Sustrik, I have been reading up a bit by bit on efficient data structures, primarily from the perspective of memory utilization. Data structures that provide constant lookup time with minimal memory utilization can give a significant performance boost since access to CPU cache is considerably faster than access to RAM. This post is a compendium of a few data structures I came across and salient aspects about them

Judy arrays http://judy.sourceforge.net/doc/10minutes.htm
Excerpt: A Judy tree is generally faster than and uses less memory than contemporary forms of trees such as binary (AVL) trees, b-trees, and skip-lists. When used in the “Judy Scalable Hashing” configuration, Judy is generally faster then a hashing method at all populations. A (CPU) cache-line fill is additional time required to do a read reference from RAM when a word is not found in cache. In today’s computers the time for a cache-line fill is in the range of 50..2000 machine instructions. Therefore a cache-line fill should be avoided when fewer than 50 instructions can do the same job. Judy rarely compromises speed/space performance for simplicity (Judy will never be called simple except at the API). Judy is designed to avoid cache-line fills wherever possible. The Achilles heel of a simple digital tree is very poor memory utilization, especially when the N in N-ary (the degree or fanout of each branch) increases. The Judy tree design was able to solve this problem. In fact a Judy tree is more memory-efficient than almost any other competitive structure (including a simple linked list).

HAT-trie – a cache concious trie http://portal.acm.org/citation.cfm?id=1273761
Excerpt: Tries are the fastest tree-based data structures for managing strings in-memory, but are space-intensive. The burst-trie is almost as fast but reduces space by collapsing trie-chains into buckets. This is not however, a cache-conscious approach and can lead to poor performance on current processors. In this paper, we introduce the HAT-trie, a cache-conscious trie-based data structure that is formed by carefully combining existing components. We evaluate performance using several real-world datasets and against other high-performance data structures. We show strong improvements in both time and space; in most cases approaching that of the cache-conscious hash table. Our HAT-trie is shown to be the most efficient trie-based data structure for managing variable-length strings in-memory while maintaining sort order.

Burst Trie http://goanna.cs.rmit.edu.au/~jz/fulltext/acmtois02.pdf
Excerpt: Many applications depend on efficient management of large sets of distinct strings in memory. We propose a new data structure, the burst trie, that has significant advantages over existing options for such applications: it requires no more memory than a binary tree; it is as fast as a trie; and, while not as fast as a hash table, a burst trie maintains the strings in sorted or near-sorted order. These experiments show that the burst trie is particularly effective for the skewed frequency distributions common in text collections, and dramatically outperforms all other data structures for the task of managing strings while maintaining sort order.

Radix trie (aka Patricia trie) http://en.wikipedia.org/wiki/Radix_tree
Excerpt: The radix tree is easiest to understand as a space-optimized trie where each node with only one child is merged with its child. Unlike balanced trees, radix trees permit lookup, insertion, and deletion in O(k) time rather than O(log n)

Ternary Search Trees http://en.wikipedia.org/wiki/Ternary_search_tree
Excerpt: A trie is optimized for speed at the expense of size. The ternary search tree replaces each node of the trie with a modified binary search tree. For sparse tries, this binary tree will be smaller than a trie node. Each binary tree implements a single-character lookup. It has the typical left and right children which are checked if the lookup character is greater or less than the node’s character, respectively. A third child is used if the lookup character is found on that particular node. Unlike the other children, it links to the root of the binary search tree for the next character in the string

Next steps: to trie ;) and setup benchmarks for some of these on a practical application

Category : 0-cosmos | TechTalk

9 May, 2010

Using Javascript to read a users browser history

Posted by Bhavin Turakhia | (9) Comments

While doing some research I came across this article by Mike Nolet on figuring out the gender of a user based on the websites the user has visited. The article has a javascript that does this – so yea I am adding “Allows you to check your testosterone levels” as a feature of Javascript.

But on a more serious note – I was impressed (and puzzled) mostly by the fact that his javascript managed to figure out which websites exist in my browser history. Now that makes me curious. So a few clicks and a google search later I figure that your browser history is NOT private. There is a nifty javascript hack that can allow any website to figure out which other websites you have visited in the past, from a potential list of websites.

I just had to blog about this. The hack uses the property of the browser which results in changing the color of an already visited link. Basically through javascript one can find out the color of any item in the DOM. So in order to find out whether you have visited a particular website, all I need to do is insert that website in the DOM as a link (albiet in an invisible manner) and check its color property. If its color matches that of a “visited link” then you have visited that website. Seemingly dell already uses this on their website to determine if a user has visited any of its competitors. Think of the potential uses -

  • You can check if a user coming to your website has already visited any of your competitors, and if so target specific offers to them
  • If you rank at the 5th position in Google for a keyword you can check if the user has visited any of the previous 4 links
  • Lets say you have an offer coupon that you only want an anonymous user to see once. You may use cookies, but a user could delete their cookies if they are on to you. You can now check whether the user has been to that URL before through this hack if the user has not deleted their history

Espionage courtesy Javascript!!

More details available here

Category : 0-cosmos | TechTalk

6 May, 2010

RabbitMQ vs Apache ActiveMQ vs Apache qpid

Posted by Bhavin Turakhia | (20) Comments

We need a simple message queue to ensure asynchronous message passing across a bunch of our server side apps. The message volume is not intended to be very high, latency is not an issue, and order is not important, but we do need to guarantee that the message will be received and that there is no potential for failure irrespective of infrastructure downtime.

Dhruv from my team had taken up the task of researching various persistent message queue options and compiling notes on them. This is a compendium of his notes (disclaimer – this is an outline of our experience, there may be inaccuracies) -

RabbitMQ

General:

  • Some reading on clustering http://www.rabbitmq.com/clustering.html
  • DNS errors cause the DB(mnesia) to crash
  • A RabbitMQ instance won’t scale to LOTS of queues with each queue having fair load since all queues are stored in memory (queue metadata) and also in a clustered setup, each queue’s metadata (but not the queue’’s messages) is replicated on each node. Hence, there is the same amount of overhead due to queues on every node in a cluster
  • No ONCE-ONLY semanamntics. Messages may be sent twice by RabbitMQ to the consumer(s)
  • Multiple consumers can be configured for a single queue, and they will all get mutually exclusive messages
  • Unordered; not FIFO delivery
  • Single socket multiple connections. Each socket can have multiple channels and each channel can have multiple consumers
  • No provision for ETA
  • maybe auto-requeue (based on timeout) — needs investigation
  • Only closing connection NACKs a message. Removing the consumer from that channel does NOT. Hence, all queues being listened to on that channel/connetion are closed for the current consumer
  • NO EXPONENTIAL BACKOFF for failed consumers. Failed messages are re-tried almost immediately. Hence an error in the consumer logic that crashes the consumer while consuming a particular message may potentially block the whole queue. Hence, the consumer needs to be programmed well — error free. However, apps are like; well apps…
  • Consumer has to do rate limiting by not consuming messages too fast (if it wants to); no provision for this in RabbitMQ

Persistence:

  • It will use only it’s own DB — you can’t configure mySQL or any such thing

Clustering and Replication:

  • A RabbitMQ cluster is just a set of nodes running the RabbitMQ. No master node is involved.
  • You need to specify hostname of cluster nodes in a cluster manually on the command line or in a config file.
  • Basic load balancing by nodes in a cluster by redirecting requests to other nodes
  • A node can be a RAM node or a disk node. RAM nodes keep their state only in memory (with the exception of the persistent contents of durable queues which are still stored safely on disc). Disk nodes keep state in memory and on disk.
  • Queue metadata shared across all nodes.
  • RabbitMQ brokers tolerate the failure of individual nodes. Nodes can be started and stopped at will
  • It is advisable to have at least 1 disk node in a cluster of nodes
  • You need to specify which nodes are part of a cluster during node startup. Hence, when A is the first one to start, it will think that it is the only one in the cluster. When B is started it will be told that A is also in the cluster and when C starts, it should be told that BOTH A and B are part of the cluster. This is because if A or B go down, C still knows one of the machines in the cluster. This is only required for RAM nodes, since they don’t persist metadata on disk. So, if C is a memory node and it goes down and comes up, it will have to be manually told which nodes to query for cluster membership (since it itself doesn’t store that state locally).
  • Replication needs to be investigated (check addtl resources) however, from initial reading, it seems queue data replication does not exist
  • FAQ: “How do you migrate an instance of RabbitMQ to another machine?”. Seems to be a very manual process.

Transactions:

  • Any number of queues can be involved in a transaction

Addtl Resources

Apache qpid

  • Supports transactions
  • Persistence using a pluggable layer — I believe the default is Apache Derby
  • This like the other Java based product is HIGHLY configurable
  • Management using JMX and an Eclipse Management Console application - http://www.lahiru.org/2008/08/what-qpid-management-console-can-do.html
  • The management console is very feature rich
  • Supports message Priorities
  • Automatic client failover using configurable connection properties -
  • Cluster is nothing but a set of machines have all the queues replicated
  • All queue data and metadata is replicated across all nodes that make up a cluster
  • All clients need to know in advance which nodes make up the cluster
  • Retry logic lies in the client code
  • Durable Queues/Subscriptions
  • Has bindings in many languages
  • For the curious: http://qpid.apache.org/current-architecture.html
  • In our tests -
    • Speed: Non-persistent mode: 5000 messages/sec (receive rate), Persistent mode: 1100 messages/sec (receive rate) (send rate will be typically a bit more, but when you start off with an empty queue, they are almost the same for most queue implementations). However, the interesting bit is that even in transacted mode, I saw a lot of message loss if I crashed the broker (by crash I mean Ctrl+C, not even the more -9 signal type of thing that I usually do). Why I stress this is that apps. can usually hook on to Ctrl+C and save data before quitting, but qpid didn’t think it prudent to do so. Out of 1265 messages sent (and committed), only 1218 were received by the consumer (before the inflicted crash). Even on restarting the broker and consumer, that didn’t change. We observed similar behaviour with RabbitMQ in our tests. However, RabbitMQ docs. mention that you need to run in TRANSACTED mode (not just durable/persistent) for guaranteed delivery. We haven’t run that test yet.

Apache ActiveMQ

  • HIGHLY configurable. You can probably do anything you want it to with it
  • You can choose a message store. 4 are already available
  • Has lots of clustering options:
    • Shared nothing Master-Slave: ACK sent to client when master stores the message
    • Shared Database: Acquires a lock on the DB when any instance tries to access the DB
    • Shared Filesystem: Locks a file when accessing the FS. Issues when using NFS with file-locking; or basically any network based file system since file locking is generally buggy in network file systems
  • Network of brokers: This is an option that allows a lot of flexibility. However, it seems to be a very problematic/buggy way of doing things since people face a lot of issues with this configuration
  • Scaling:
    • A. Default transport is blocking I/O with a thread per connection. Can be changed to use nio
    • Horizontal scaling: Though they mention this, the way to achieve this is by using a network of brokers
    • Patitioning: We all know Mr. Partitioning, don’t we. The client decides where to route packets and hence must maintain multiple open connections to different brokers
  • Allows producer flow-control!!
  • Has issues wrt lost/duplicate messages, but there is an active community that fixes these issues
  • Active MQ crashes fairly frequently, at least once per month, and is rather slow - http://stackoverflow.com/questions/957507/lightweight-persistent-message-queue-for-linux
  • Seems to have bindings in many languages(just like RabbitMQ)
  • Has lots of tools built around it 12. JMS compliant; supports XA transactions: http://activemq.apache.org/how-do-transactions-work.html
  • Less performant as compared to RabbitMQ
  • We were able to perform some tests on Apache Active MQ today, and here are the results:
    • Non persistent mode: 5k messages/sec
    • Persistent mode: 22 messages/sec (yes that is correct)
  • There are multiple persisters that can be configured with ActiveMQ, so we are planning to run another set of tests with MySQL and file as the persisters. However, the current default (KahaDB) is said to be more scalable (and offers faster recoverability) as compared to the older default(file/AMQ Message Store: http://activemq.apache.org/amq-message-store.html).
  • The numbers are fair. Others on the net have observed similar results: http://www.mostly-useless.com/blog/2007/12/27/playing-with-activemq/
  • With MySQL, I get a throughput of 8 messages/sec. What is surprising is that it is possible to achieve much better results using MySQL but ActiveMQ uses the table quite unwisely.
  • ActiveMQ created the tables as InnoDB instead of MyISAM even though it doesn’t seem to be using any of the InnoDB features.
  • I tried changing the tables to MyISAM, but it didn’t help much. The messages table structure has 4 indexes !! Insert takes a lot of time because MySQL needs to update 4 indexes on every insert. That sort of kills performance. However, I don’t know if performance should be affected for small (< 1000) messages in the table. Either ways, this structure won’t scale to millions of messages since everyone will block on this one table.
Category : 0-cosmos | TechTalk