Login | Packages | Support | Bugs 

Package home | Report new bug | New search Status: Open | Feedback | All

Bug #14563 possible issue in consistent hashing algorithm
Submitted: 2008-08-25 20:16 UTC
From: jyukes at gmail dot com Assigned:
Status: Open Package: memcache
Version: 5.2.3 OS: ubuntu7
[2008-08-25 20:16 UTC] jyukes at gmail dot com
Description:
------------
I have attached a SimpleTest unit test that reprodues the issue.... the
key can end up on multiple hosts...  when there haven't been any
connection oriented issues.

If I use 10 servers -- there may be 4 copies of the key stored.

I have attached the smallest example that consistently reproduces the
issue.

Reproduce code:
---------------
<?
require_once('simpletest/autorun.php');
SimpleTest :: prefer(new HtmlReporter());

// this fails for various keys - of different length
// if i use a shorter key, it doesn't fail
// and it only seems to fail in the CLI

define( 'TEST_KEY', 'TEST.MEMCACHE.CONSISTENT' );

class TestMemcacheConsistent extends UnitTestCase {
        var $mem;
        var $servers;
        var $strategy;

        function setUp() {
                ini_set('display_errors', 'On');
                error_reporting( E_ALL );
                foreach ( range( 80, 81 ) as $octet ) {
                        $server = '192.168.10.' . $octet;
                        $this->servers[] = $server;
                }
        }

        function mySetUp( $strategy ) {
                ini_set( 'memcache.hash_strategy', $strategy );
                $this->strategy = $strategy;

                foreach ( range( 1, 2 ) as $i ) {
                        $m = new MemcachePool( );
                        $this->mem[] = $m;
                }
                foreach ( $this->servers as $server ) {
                        foreach ( $this->mem as $m )  {
                                $m->addServer( $server );
                        }
                }
        }

        function myTest() {
                foreach ( $this->mem as $m ) {
                        $result = $m->set( constant( 'TEST_KEY' ),
$this->servers );
                        $this->assertTrue( $result );
                }

                foreach ( range( 1, 1 ) as $i ) {
                        foreach ( $this->mem as $m ) {
                                $result = $m->get( constant( 'TEST_KEY'
) );
                                $this->assertTrue( $this->servers ==
$result );

                                $result = $m->set( constant( 'TEST_KEY'
), $this->servers );
                                $this->assertTrue( $result );
                        }
                }
                $count = $this->countKeysFound( constant( 'TEST_KEY' )
);
                $this->assertTrue( $count == 1 );
        }

        function testConsistent() {
                $this->deleteKeysFound( constant( 'TEST_KEY' ) );
                $this->mySetUp( 'consistent' );
                $this->myTest();
        }

        function testConsistent2() {
                $this->mySetUp( 'consistent' );
                $this->myTest();
        }

        function testStandard() {
                $this->deleteKeysFound( constant( 'TEST_KEY' ) );
                $this->mySetUp( 'standard' );
                $this->myTest();
        }

        function testStandard2() {
                $this->mySetUp( 'standard' );
                $this->myTest();
        }

        function sendCommandToServer( $server, $cmd ) {
                $s = @fsockopen($server,'11211');
                if (!$s) {
                        return FALSE;
                }
                fwrite($s, $cmd . "\r\n");

                $buf = fgets($s, 256);
                return $buf;
        }

        function countKeysFound( $key ) {
                $count = 0;
                foreach ( $this->servers as $server ) {
                        $buf = $this->sendCommandToServer( $server, 'get
' . $key );
                        if ( !strncmp( $buf, 'VALUE', 5 ) ) {
                                $count++;
                        }
                }
                return $count;
        }

        function deleteKeysFound( $key ) {
                $count = 0;
                foreach ( $this->servers as $server ) {
                        $buf = $this->sendCommandToServer( $server,
'delete ' . $key );
                        if ( !strncmp( $buf, 'DELETED', 7 ) ) $count++;
                }
                return $count;
        }

        function tearDown() {
                unset( $this->mem );
                unset( $this->servers );
        }
}

?>

Expected result:
----------------
# php test_memcache2.php
test_memcache2.php
OK
Test cases run: 1/1, Passes: 28, Failures: 0, Exceptions: 0

Actual result:
--------------
# php test_memcache2.php
test_memcache2.php
1) Expected true, got [Boolean: false] at [test_memcache2.php line 73]
        in testConsistent2
        in TestMemcacheConsistent
FAILURES!!!
Test cases run: 1/1, Passes: 27, Failures: 1, Exceptions: 0
PRIVACY POLICY | CREDITS
Copyright © 2001-2008 The PHP Group
All rights reserved.
Last updated: Fri Aug 07 10:22:05 2009 UTC
Bandwidth and hardware provided by: pair Networks