[infinispan-dev] ISPN-384 - Implementing hash distribution aware headers in Hot Rod
Galder Zamarreno
galder at redhat.com
Fri Apr 23 10:13:36 EDT 2010
--
Galder Zamarreño
Sr. Software Engineer
Infinispan, JBoss Cache
----- "Galder Zamarreno" <galder at jboss.org> wrote:
> ----- "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).
Forgot to add the ending :). So, if we ever wanted to keep the topology as a map, finding whether an old member is still present in the topology view would be an O(1) with Address as key.
>
> 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