[infinispan-issues] [JBoss JIRA] Issue Comment Edited: (ISPN-1275) ConsistentHash implementation producing same hash id for two different cluster nodes

[Manik Surtani (JIRA)]

    [ https://issues.jboss.org/browse/ISPN-1275?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12617846#comment-12617846 ] 

Manik Surtani edited comment on ISPN-1275 at 8/1/11 9:45 AM:
-------------------------------------------------------------

Ok, so with the current HASH_SPACE=10240, and the number of vnodes set to 2048 (for easy math), the probability of a collision is N/5 where N is cluster size.  This is huge, and as you say almost certain to happen with even a modest cluster.

If we make HASH_SPACE to run from Integer.MIN_VALUE ~ Integer.MAX_VALUE, however, this probability drops to (0.00004768 * N) %.

So it isn't perfect as a solution but for now, this is what I am going for.  :)  Captured in ISPN-1281

      was (Author: manik):
    Ok, so with the current HASH_SPACE=10240, and the number of vnodes set to 2048 (for easy math), the probability of a collision is N/5 where N is cluster size.  This is huge, and as you say almost certain to happen with even a modest cluster.

If we make HASH_SPACE to run from Integer.MIN_VALUE ~ Integer.MAX_VALUE, however, this probability drops to (0.00004768 * N) %.

So it isn't perfect as a solution but for now, this is what I am going for.  :)
  
> ConsistentHash implementation producing same hash id for two different cluster nodes
> ------------------------------------------------------------------------------------
>
>                 Key: ISPN-1275
>                 URL: https://issues.jboss.org/browse/ISPN-1275
>             Project: Infinispan
>          Issue Type: Bug
>          Components: Distributed Cache
>    Affects Versions: 5.0.0.FINAL
>            Reporter: Galder Zamarreño
>            Assignee: Manik Surtani
>            Priority: Blocker
>              Labels: consistent_hash
>             Fix For: 5.1.0.BETA1, 5.1.0.FINAL
>
>         Attachments: hashids.log
>
>
> While working on ISPN-1273, I've discovered that when virtual nodes are enabled, ConsistentHash.getHashIds(address) can return the same hash for two different cluster nodes. Example: with 500 virtual nodes, both NodeA-23181 and NodeB-39177 produce hash id *5289*. See attached log.
> Virtual nodes make the problem more apparent, however the problem exists regardless of vnodes being used.

--
This message is automatically generated by JIRA.
For more information on JIRA, see: http://www.atlassian.com/software/jira