MEMQ : Fast queue implementation using Memcached and PHP only

Standard

Memcached is a scalable caching solution developed by Danga interactive. One can do a lot of cool things using memcached including spam control, online-offline detection of users, building scalable web services. In this post, I will demonstrate and explain how to implement fast scalable queues in PHP.

MEMQ: Overview
Every queue is uniquely identified by it’s name. Let’s consider a queue named “foo” and see how MEMQ will implement it inside memcached:

  • Two keys namely, foo_head and foo_tail contains meta information about the queue
  • While queuing, item is saved in key foo_1234, where 1234 is the current value of key foo_tail
  • While de-queuing, item saved in key foo_123 is returned, where 123 is the current value of key foo_head
  • Value of keys foo_head and foo_tail start with 1 and gets incremented on every pop and push operation respectively
  • Value of key foo_head NEVER exceeds value of foo_tail. When value of two meta keys is same, queue is considered empty.

MEMQ: Code
Get the source code from GitHub:
http://github.com/abhinavsingh/memq

<?php

	define('MEMQ_POOL', 'localhost:11211');
	define('MEMQ_TTL', 0);

	class MEMQ {

		private static $mem = NULL;

		private function __construct() {}

		private function __clone() {}

		private static function getInstance() {
			if(!self::$mem) self::init();
			return self::$mem;
		}

		private static function init() {
			$mem = new Memcached;
			$servers = explode(",", MEMQ_POOL);
			foreach($servers as $server) {
				list($host, $port) = explode(":", $server);
				$mem->addServer($host, $port);
			}
			self::$mem = $mem;
		}

		public static function is_empty($queue) {
			$mem = self::getInstance();
			$head = $mem->get($queue."_head");
			$tail = $mem->get($queue."_tail");

			if($head >= $tail || $head === FALSE || $tail === FALSE)
				return TRUE;
			else
				return FALSE;
		}

		public static function dequeue($queue, $after_id=FALSE, $till_id=FALSE) {
			$mem = self::getInstance();

			if($after_id === FALSE && $till_id === FALSE) {
				$tail = $mem->get($queue."_tail");
				if(($id = $mem->increment($queue."_head")) === FALSE)
					return FALSE;

				if($id <= $tail) {
					return $mem->get($queue."_".($id-1));
				}
				else {
					$mem->decrement($queue."_head");
					return FALSE;
				}
			}
			else if($after_id !== FALSE && $till_id === FALSE) {
				$till_id = $mem->get($queue."_tail");
			}

			$item_keys = array();
			for($i=$after_id+1; $i<=$till_id; $i++)
				$item_keys[] = $queue."_".$i;
			$null = NULL;

			return $mem->getMulti($item_keys, $null, Memcached::GET_PRESERVE_ORDER);
		}

		public static function enqueue($queue, $item) {
			$mem = self::getInstance();

			$id = $mem->increment($queue."_tail");
			if($id === FALSE) {
				if($mem->add($queue."_tail", 1, MEMQ_TTL) === FALSE) {
					$id = $mem->increment($queue."_tail");
					if($id === FALSE)
						return FALSE;
				}
				else {
					$id = 1;
					$mem->add($queue."_head", $id, MEMQ_TTL);
				}
			}

			if($mem->add($queue."_".$id, $item, MEMQ_TTL) === FALSE)
				return FALSE;

			return $id;
		}

	}

?>

MEMQ: Usage
The class file provide 3 methods which can be utilized for implementing queues:

  1. MEMQ::is_empty – Returns TRUE if a queue is empty, otherwise FALSE
  2. MEMQ::enqueue – Queue up the passed item
  3. MEMQ::dequeue – De-queue an item from the queue

Specifically MEMQ::dequeue can run in two modes depending upon the parameters passed, as defined below:

  1. $queue: This is MUST for dequeue to work. If other optional parameters are not passed, top item from the queue is returned back
  2. $after_id: If this parameter is also passed along, all items from $after_id till the end of the queue are returned
  3. $till_id: If this paramater is also passed along with $after_id, dequeue acts like a popRange function

Whenever optional parameters are passed, MEMQ do not remove the returned items from the queue.

MEMQ: Is it working?
Add following line of code at the end of the above class file and hit the class file from your browser. You will get back inserted item id as response on the browser:

var_dump(MEMQ::enqueue($_GET['q'], time()));

Lets see how cache keys looks like in memcached:

abhinavsingh@abhinavsingh-desktop:~$ telnet localhost 11211
Trying ::1...
Trying 127.0.0.1...
Connected to localhost.
Escape character is '^]'.

get foo_head
VALUE foo_head 1 1
1
END

get foo_tail
VALUE foo_tail 1 1
2
END

get foo_1
VALUE foo_1 1 10
1265540583
END

get foo_2
VALUE foo_2 1 10
1265540585
END

MEMQ: Benchmark
Below are the benchmarking results for varying load:

  1. Queuing performance: 697.18 req/sec (n=1000, c=100) and 258.64 req/sec (n=5000, c=500)
  2. Dequeue performance: 641.27 req/sec (n=1000, c=100) and 242.87 req/sec (n=5000, c=500)

MEMQ: Why and other alternatives
There are several open source alternatives which provide a lot more scalability. However, MEMQ was written because my application doesn’t expect a load in order of 10,000 hits/sec. Listed below are a few open source alternatives for applications expecting high load:

  1. ActiveMQ: A reliable and fast solution under apache foundation
  2. RabbitMQ: Another reliable solution based on AMQP solution
  3. Memcacheq: A mash-up of two very stable stacks namely memcached and berkleyDB. However, it’s installation is a bit tricky.

MEMQ: Mantra and Customization
At the base MEMQ implementation can be visualized as follows:

There is a race between two keys in memcached (foo_head and foo_tail). Both are incremented on every dequeue and queue operation respectively. However, foo_tail is strong enough and never allows foo_head to exceed. When value of keys foo_tail and foo_head are equal, queue is considered empty.

The above code file still doesn’t include utility methods like MEMQ::total_items etc. However, writing such methods should be pretty easy depending upon your application needs. Also depending upon your application requirement, you should also take care of overflowing integer values.

  • Pingback: Webby Scripts MEMQ : Fast queue implementation using Memcached and PHP only …()

  • Pingback: MEMQ : Fast queue implementation using Memcached and PHP only … » KHMER855.COM()

  • JasonDavis

    This may sound like a simple question but I think an answer could help many others as well. What are some good uses for this? I am working on a social network site so I have many uses for memcache and would love to know what kind of uses I could use somethings like this for?

    • http://abhinavsingh.com Abhinav Singh

      Alright, I will just give you a simple mantra for web dev. Whole web is just a queue, specially social networking apps. You are the publisher of a queue, which deliver your status update to your friends on a social network.

      Similarly you can view every entity in a similar way. Twitter can be another perfect example here. Hope this helps!

  • Pingback: uberVU - social comments()

  • Pingback: MEMQ | traffic-internet.net()

  • http://google.co.in Joe

    hi to all

  • Pingback: vivanno.com::aggregator » Archive » MEMQ()

  • Pingback: Tweets that mention MEMQ : Fast queue implementation using Memcached and PHP only | Abhi's Weblog -- Topsy.com()

  • http://triop.se Jonas Lejon

    I was a heavily memcache user before I found Redis. Switching from memcache to Redis took me about 5 min and Redis also has lists so creating a queue in Redis is 2 lines of code

    • http://abhinavsingh.com Abhinav Singh

      absolutely right. This code fix was written about an year back when we didn’t had facility to use mongodb, redis etc. Redis no doubt is champion in many sense.

  • http://myworld.se Henrik

    Hi, rly cool class.

    I just tried your memq class and I get some errors. It seems I’m using the memcache extension and not the memcached. The error message I get is about Memcached::GET_PRESERVE_ORDER and I can’t find the syntax I need to use if i have the memchace extension. Anyone know how to fix this?

  • Pingback: Weeknotes: Redis, PHP, mail and SOAP « The Aust Gate()

  • http://php-base.blogspot.com belajar php

    this is awesome post, thank you . its very helpfully for me, many thanks anda i will adding feed this blog

  • paullush

    Great but this will destroy any queue where the int overflows on a 32bit system and php starts returning the queue position as exponential. If you see 4 billion queue slots as a realistic figure, then you may want to think about running it on a 64bit php5 box.

  • paul lush

    You dont remove items from memcache once dequeued. This relies on memcache to dispose of them. If you have other items in the memcache, it might start throwing them out first. Please consider

    if($id get($queue.”_”.($id-1)); $mem->delete($queue.”_”.($id-1)); return $ret
    } else …

  • Eddie

    I agree with Paul, the TTL is set to 0. When you run out of space you will get forceful evictions. This would not be that bad unless you are using it for other data and that gets evicted.
    If you are using membase you would probably run out of disk space and crash the box.

  • Liad Livnat

    Hi i would like to add a pick to your queue, you implimented it very well and it would like to use it, i implimented it ain the following way:

    public static function pick($queue)

    {

    $mem = self::getInstance();

    $head = $mem->get($queue.”_head”);

    $head_val = $mem->get($queue.”_”.$head);

    $tail = $mem->get($queue.”_tail”);

    $tail_val = $mem->get($queue.”_”.$tail);

    if ($head_val == $tail_val)

    {

    // queue is empty

    return false;

    }

    return $head_val;

    }

    what do you think can it work?