[infinispan-dev] ISPN-384 - Implementing hash distribution aware headers in Hot Rod

Galder Zamarreno galder at jboss.org
Fri Apr 23 10:10:00 EDT 2010 

----- "Manik Surtani" <manik at jboss.org> wrote:

> On 21 Apr 2010, at 12:10, Galder Zamarreno wrote:
> 
> > Ok, what about the rest of the points made? 
> > 
> > I.e. Adding int getPosition(Address a) to ConsistentHash interface.
> Can we do that in 4.1? Or do we have to wait for 5.0?
> 
> 4.1 is fine.  Also, I presume by getPosition() you really mean
> getHashId(), which will be between 0 and HASH_SPACE (as opposed to a
> relative position meaning, before AddressX and after AddressY)?

Indeed I meant that. The hash position or id, I'll go with getHashId().

> 
> > Ordering of servers in views returned: For topology changes, ordered
> in started order and for hash aware topology changes, servers ordered
> in ascending hash wheel position?
> 
> Well, we *could* maintain this order, but I don't think it should be
> mandated since order can easily be regained by sorting on the hash
> ids.

Sure, it could always be ordered. I assumed that the client would need to do some ordering after applying the hash on a key and trying to decide which server to send invocation too. Hence, my idea of giving the list ordered to the client would be to make their life easier.

Then again, while implementing detection of crashed members in Hot Rod to update the Hot Rod topology information, I found that not providing order guarantees could make the internals more flexible. For example, we could maintain this topology as a map rather than a list, hence making more efficient to discover whether a member has crashed or not. The efficiency improvement comes from the fact that I checked for crashed members by listening to JGroups view changes and when new member list is smaller than the new one, checking whether any of the nodes that is no longer part of the view is still present in the Hot Rod topology list. Hence, this requires traversing the list which is O(n).

So, to summarise, I prefer not to mandate any order for the time being.

> 
> > 
> > Cheers,
> > 
> > ----- "Manik Surtani" <manik at jboss.org> wrote:
> > 
> >> On 19 Apr 2010, at 10:58, galder at redhat.com wrote:
> >> 
> >>> Hi,
> >>> 
> >>> Re: https://jira.jboss.org/jira/browse/ISPN-384
> >>> 
> >>> The topology headers are in, so the next step is to get the hash
> >> distribution headers in. The first step here is for Hot Rod servers
> to
> >> be able to query an Address' position in the wheel so that this is
> >> sent back to clients (This is what I refer to by hashcode in
> >>
> http://community.jboss.org/wiki/HotRodProtocol#HashDistributionAware_Client_Topology_Change_Header
> >> - it really is the hash wheel position). However, there's no such
> API
> >> at the  moment that allows clients to query it. Having had a look,
> the
> >> most reasonable thing would be to add something like this to the
> >> ConsistentHash interface:
> >>> 
> >>> int getPosition(Address a)
> >>> 
> >>> However, this might be somehow limiting if we end up implementing
> >> virtual nodes. ExperimentalDefaultConsistentHash hints at the
> >> possibility of that happening and so something like this might
> more
> >> future proof:
> >>> 
> >>> List[Integer] getPositions(Address a)
> >> 
> >> We shouldn't design for something that may not be realised. 
> vnodes
> >> are very problematic for many reasons and if we can achieve what
> we
> >> need to achieve without vnodes then that would be my preference.
> >> 
> >>> This also highlights the limitation of the Hot Rod spec where
> it's
> >> assumed that a server has a single position. 
> >>> 
> >>> Moreover, these brings up another interesting topic which is the
> >> order in which Hot Rod orders the servers in the headers. For
> topology
> >> headers, although not written down, I'm following the same kind of
> >> pattern used at the JGroups level where serves started first appear
> in
> >> first in the list returned. I should probably add this to the
> protocol
> >> wiki. 
> >>> 
> >>> In the case of hash distribution headers, I think it'd make sense
> >> for the order to be based on the hash wheel position in ascendant
> >> order. That way it would make life easier for clients to find the
> >> target node for the operation, since it'd avoid them having to do
> the
> >> sorting and finding out the next node. If we take this into
> account
> >> with the fact  that a node might map to multiple positions, I
> think
> >> the hash distribution header might be look better this way:
> >>> 
> >>> [Response header][Topology Id][Num Key Owners][Hash Function
> >> Version][Hash space size][Num servers in topology]
> >>> -> New: 
> >>> [*m1: Server Id*][m1: Host/IP length][m1: Host/IP address]
> >>> [*m2: Server Id*][m2: Host/IP length][m2: Host/IP address]...
> >>> [*m3: Server Id*][m3: Host/IP length][m3: Host/IP address]...
> >>> [Num total positions]
> >>> [*m2: Server Id*][m2: hash wheel position 1]
> >>> [*m3: Server Id*][m3: hash wheel position 2]
> >>> [*m2: Server Id*][m2: hash wheel position 2]
> >>> [*m3: Server Id*][m3: hash wheel position 1]
> >>> [*m3: Server Id*][m3: hash wheel position 3]
> >>> [*m1: Server Id*][m1: hash wheel position 1]
> >> 
> >> Again, this assumes > 1 position for a node.  I think we should
> not
> >> design for this at this stage.  
> >>> 
> >>> So, above I've splitted the server host/port definitions in one
> side
> >> and then the hash wheel positions. I did this to avoid repeating
> the
> >> host/port definition which each hash wheel definition. I've also
> added
> >> a number of total positions and the list following it is ordered
> in
> >> ascendant order of position. The server id would be a vInt.
> >>> 
> >>> WDYT?
> >>> 
> >>> --
> >>> Galder Zamarreño
> >>> Sr. Software Engineer
> >>> Infinispan, JBoss Cache
> >>> 
> >>> _______________________________________________
> >>> infinispan-dev mailing list
> >>> infinispan-dev at lists.jboss.org
> >>> https://lists.jboss.org/mailman/listinfo/infinispan-dev
> >> 
> >> --
> >> Manik Surtani
> >> manik at jboss.org
> >> Lead, Infinispan
> >> Lead, JBoss Cache
> >> http://www.infinispan.org
> >> http://www.jbosscache.org
> >> 
> >> 
> >> 
> >> 
> >> 
> >> _______________________________________________
> >> infinispan-dev mailing list
> >> infinispan-dev at lists.jboss.org
> >> https://lists.jboss.org/mailman/listinfo/infinispan-dev
> > 
> > _______________________________________________
> > infinispan-dev mailing list
> > infinispan-dev at lists.jboss.org
> > https://lists.jboss.org/mailman/listinfo/infinispan-dev
> 
> --
> Manik Surtani
> manik at jboss.org
> Lead, Infinispan
> Lead, JBoss Cache
> http://www.infinispan.org
> http://www.jbosscache.org
> 
> 
> 
> 
> 
> _______________________________________________
> infinispan-dev mailing list
> infinispan-dev at lists.jboss.org
> https://lists.jboss.org/mailman/listinfo/infinispan-dev

More information about the infinispan-dev mailing list