<div class="gmail_quote">On Wed, Jun 13, 2012 at 2:12 PM, Manik Surtani <span dir="ltr"><<a href="mailto:manik@jboss.org" target="_blank">manik@jboss.org</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<div style="word-wrap:break-word"><br><div><div><div><div>On 13 Jun 2012, at 09:05, Dan Berindei wrote:</div><br><blockquote type="cite"><div>Sanne and I resumed the meeting later yesterday afternoon, but we<br>
basically just rehashed the stuff that we've been discussing before<br>lunch. Logs here:<br><br>(07:10:10 PM) jbott: Meeting ended Tue Jun 12 16:09:55 2012 UTC.<br>Information about MeetBot at <a href="http://wiki.debian.org/MeetBot" target="_blank">http://wiki.debian.org/MeetBot</a> . (v<br>
0.1.4)<br>(07:10:10 PM) jbott: Minutes:<br><a href="http://transcripts.jboss.org/meeting/irc.freenode.org/infinispan/2012/infinispan.2012-06-12-15.26.html" target="_blank">http://transcripts.jboss.org/meeting/irc.freenode.org/infinispan/2012/infinispan.2012-06-12-15.26.html</a><br>
(07:10:10 PM) jbott: Minutes (text):<br><a href="http://transcripts.jboss.org/meeting/irc.freenode.org/infinispan/2012/infinispan.2012-06-12-15.26.txt" target="_blank">http://transcripts.jboss.org/meeting/irc.freenode.org/infinispan/2012/infinispan.2012-06-12-15.26.txt</a><br>
(07:10:10 PM) jbott: Log:<br><a href="http://transcripts.jboss.org/meeting/irc.freenode.org/infinispan/2012/infinispan.2012-06-12-15.26.log.html" target="_blank">http://transcripts.jboss.org/meeting/irc.freenode.org/infinispan/2012/infinispan.2012-06-12-15.26.log.html</a><br>
<br><br>The main conclusion was that the number of total virtual nodes/hash<br>segments will be fixed per cluster, not per node. Kind of like the old<br>AbstractWheelConsistentHash.HASH_SPACE, only configurable. A physical<br>
node will have a variable number of vnodes/segments over its lifetime.<br><br>We also decided to add a pull component to our state transfer. The<br>current NBST design requires all the nodes to push state to a joiner<br>
more or less at the same time, which results in lots of congestion at<br>
the network layer and sometimes even in the joiner being excluded from<br>the cluster. We have decided that a node will not start pushing data<br>as soon as it receives the PREPARE_VIEW command from the coordinator,<br>but instead it will wait for a START_PUSH command from the receiver.<br>
The receiver will only ask one previous owner at a time, thus<br>eliminating the congestion.<br><br><br>We've had a lot of back-and-forth discussions about whether the CH<br>should be "non-deterministic". We agreed in the end that (I think)<br>
that it's fine if the creation of the CH is not based solely on the<br>current members list, and it depends on the previous CH as well. This<br>is quite important, I think it would be hard to find an algorithm<br>based only on member list that doesn't change ownership for a lot of<br>
nodes in case of a leave (even if we use the previous members list as<br>well): see <a href="https://issues.jboss.org/browse/ISPN-1275" target="_blank">https://issues.jboss.org/browse/ISPN-1275</a>.<br></div></blockquote>
<div><br></div></div></div><div>Would this still be encapsulated by the existing ConsistentHash interface? We should be careful about impl details leaking into the rest of the codebase.</div><div><br></div></div></div></blockquote>
<div><br>Regular code would not have to deal with the key -> segment or segment -> physical node mapping, but the query module would need access to this stuff in order to build a separate index for each vnode/segment. There may be others who could use this functionality as well...<br>
<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div style="word-wrap:break-word"><div><div><blockquote type="cite">
<div><br>I had an idea (that I'm pretty sure I didn't explained properly in the<br>chat) that we could avoid state transfer blocking everything while<br>receiving the transaction table from a previous owner by splitting the<br>
state transfer in two:<br>* In the first phase, we'd pick the new backup owners for each<br>segment, and we'd transfer all the state to them (entries, transaction<br>table, etc.)<br>* In the second phase, we'd pick a new primary owner for each segment,<br>
but the primary owner can only be one of the existing backup owners.<br>Since the data has already been transferred, we can now also remove<br>the extra owners.<br></div></blockquote><div><br></div></div><div>Who is "we"? The joiner? The coordinator? Everyone (deterministic, triggered on an event/message)?</div>
<div><br></div></div></div></blockquote><div><br>This is the basic flow I was thinking of:<br>1. Upon a cache membership change, the coordinator computes a new CH that removes the dead nodes and doesn't add any new owners unless there is a segment with 0 owners.<br>
2. The coordinator broadcasts this CH to all the cache members, there is no state transfer at this point.<br>3. The coordinator checks the CH and notices that the number of segments owned by each node is not balanced. This could be immediately or triggered manually by the administrator.<br>
4. The coordinator computes a new CH that balances the number of owners for each segment (but without removing any of the old owners, so some segments will have > numOwners owners). It starts state transfer for this CH.<br>
5. After the state transfer ends, the coordinator checks the CH again. If the number of "primary owned" segments for each node is not balanced, it creates a new CH where each node primary owner for about the same number of segments, and broadcasts this new CH. Again, no state transfer is necessary.<br>
<br>So the coordinator creates the CHs, but everyone can compute it based on the "base" CH and the new list of members:<br>1. If a node in the base CH is no longer a member, remove it from all owner lists. Stop here. Otherwise go to 2.<br>
2. If the number of owned segments per node is not balanced, add owners (algorithm TBD, but it won't be random). Stop here. Otherwise, go to 3.<br>3. If the number of primary-owned segments per node is not balanced, pick different primary owners from the existing owners. Remove extra owners.<br>
<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div style="word-wrap:break-word"><div><div><blockquote type="cite"><div>During the first phase, a segment could have more than numOwners<br>
owners, and commands would reach both the new owners and the old<br>owners. We will need to handle commit commands for transactions that<br>
the new owner doesn't have yet in its transaction table, but we would<br>not need to block prepare commands (like the current NBST design<br>does). During the second phase, the new primary owner already has the<br>transaction table, so we don't need a blocking phase either.<br>
</div></blockquote><div><br></div></div><div>So the new primary owner would queue up these commit commands? Or just ignore them/respond with a +1?</div><div><br></div></div></div></blockquote><div><br>During the 1st phase there is no new primary owner, just new backup owners. They would need to queue commit commands or otherwise handle commit commands for prepares that they haven't received yes via state transfer - in the current NBST design this is handled by blocking everything until we have received transaction information from the old owners. I would prefer marking the transactions as 1PC, like TOB does.<br>
<br>During the 2nd phase, the new primary owner already has the prepare commands (either received via state transfer or received as a backup owner), so it doesn't need to block/queue.<br><br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">
<div style="word-wrap:break-word"><div><div><blockquote type="cite"><div><br>I didn't explain this properly in the chat because I was certain it<br>
would only make sense if the coordinator initiated state transfer one<br>node at a time, making it non-deterministic. But I think if we allow<br>the CH creation algorithm to use the previous CH, we can<br>deterministically decide if the backup owners are properly balanced<br>
(if not, we need to start phase 1) and if the primary owners are<br>properly balanced (if not, we need to start phase 2).<br></div></blockquote><div><br></div></div><div>+1 to a deterministic CH.</div><div><br></div></div>
</div></blockquote><div><br>Does that mean -1 to using the previous CH to compute the new CH?<br> </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">
<div style="word-wrap:break-word"><div><div>
<blockquote type="cite"><div><br><br>There is something else that I've been thinking about since yesterday<br>that might improve performance and even simplify the state transfer at<br>the cost of determinism. When state transfer fails (usually because a<br>
node has died, but not necessarily), the coordinator could ask each<br>node how far it got with the state transfer in progress (how many<br>segments they got, from which owners, etc). The coordinator would then<br>create a new "base CH" based on the actually transferred data instead<br>
of the actual start CH or the "pending CH", or even the whole<br>chain/tree of CHs, none of which reflect how data is effectively<br>stored in the clustered at that moment. Because this base CH would<br>reflect the actual owners of each segment, there would be less data<br>
moving around in the new state transfer and we wouldn't need to keep a<br>chain/tree of previous owner lists either.<br></div></blockquote><div><br></div></div><div>When you say at the cost of determinism, what are the consequences of this? Some nodes may get "wrong answers" from their CH instances? And if so, then what? When these nodes contact "wrong nodes" for a specific key, would this "wrong node" then proxy to the coordinator (who has the definitive CH)?</div>
<br></div></div></blockquote><div><br>At the cost of determinism = only the coordinator gets the "status updates" from the members after the interruption, so only the coordinator can compute the new CH. It can then broadcast the new CH, and everyone will use that new CH.<br>
<br>The individual members will never compute their own CH, they would use the old CH until they got the new CH from the coordinator. Because we only remove owners for a key after everyone else has it, there are only two ways a command can reach the wrong node:<br>
1. The node was an owner a long time ago but is no longer an owner (or may even be dead). If the node is still alive, it can forward the command to any/all owners in the new CH. Otherwise, the originator will have to deal with a SuspectException and retry once it gets the updated CH from the coordinator.<br>
2. The node is an owner in the latest CH, but hasn't received all the entries/prepares yet. Again, it can forward to a node that's an owner in both the latest CH and the base CH (if it's a read), mark the transaction as 1PC (commit), or perform the command normally (write/prepare).<br>
<br> </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div style="word-wrap:break-word"><div><blockquote type="cite"><div><div>I'm going to take a stab at implementing a new CH with a fixed number<br>
of vnodes, that can take an existing CH as input and change owners as<br>little as possible. Then I'm going to try and implement the balanced<br>
backup owners/balanced primary owners check as well, just to see if<br>it's really possible. I'm not going to modify the design document just<br>yet, I need to see first if it does work and what you guys think about<br>
</div>it…<br></div></blockquote><div><br></div><div>+1. It will also give you an idea of the effort involved in implementing this, and how to break up the work into subtasks, how to test, etc.</div><div><br></div><div>Cheers</div>
<span><font color="#888888"><div>Manik</div></font></span><div><div><div><br></div><br><blockquote type="cite"><div><br><br>Cheers<br>Dan<br><br><br>On Tue, Jun 12, 2012 at 4:02 PM, Manik Surtani <<a href="mailto:manik@jboss.org" target="_blank">manik@jboss.org</a>> wrote:<br>
<blockquote type="cite">Meeting minutes from part 1. Had to break for lunch. :)<br></blockquote><blockquote type="cite"><br></blockquote><blockquote type="cite"><br></blockquote><blockquote type="cite">Meeting ended Tue Jun 12 13:00:43 2012 UTC. Information about MeetBot <a>athttp://wiki.debian.org/MeetBot</a> . (v 0.1.4)<br>
</blockquote><blockquote type="cite">14:01<br></blockquote><blockquote type="cite">Minutes: <a href="http://transcripts.jboss.org/meeting/irc.freenode.org/infinispan/2012/infinispan.2012-06-12-09.58.html" target="_blank">http://transcripts.jboss.org/meeting/irc.freenode.org/infinispan/2012/infinispan.2012-06-12-09.58.html</a><br>
</blockquote><blockquote type="cite">14:01<br></blockquote><blockquote type="cite">Minutes (text): <a href="http://transcripts.jboss.org/meeting/irc.freenode.org/infinispan/2012/infinispan.2012-06-12-09.58.txt" target="_blank">http://transcripts.jboss.org/meeting/irc.freenode.org/infinispan/2012/infinispan.2012-06-12-09.58.txt</a><br>
</blockquote><blockquote type="cite">14:01<br></blockquote><blockquote type="cite">Log: <a href="http://transcripts.jboss.org/meeting/irc.freenode.org/infinispan/2012/infinispan.2012-06-12-09.58.log.html" target="_blank">http://transcripts.jboss.org/meeting/irc.freenode.org/infinispan/2012/infinispan.2012-06-12-09.58.log.html</a><br>
</blockquote><blockquote type="cite"><br></blockquote><blockquote type="cite"><br></blockquote><blockquote type="cite">--<br></blockquote><blockquote type="cite">Manik Surtani<br></blockquote><blockquote type="cite"><a href="mailto:manik@jboss.org" target="_blank">manik@jboss.org</a><br>
</blockquote><blockquote type="cite"><a href="http://twitter.com/maniksurtani" target="_blank">twitter.com/maniksurtani</a><br></blockquote><blockquote type="cite"><br></blockquote><blockquote type="cite">Project Lead, Infinispan<br>
</blockquote><blockquote type="cite"><a href="http://www.infinispan.org" target="_blank">http://www.infinispan.org</a><br></blockquote><blockquote type="cite"><br></blockquote><blockquote type="cite">Platform Architect, JBoss Data Grid<br>
</blockquote><blockquote type="cite"><a href="http://www.redhat.com/promo/dg6beta" target="_blank">http://www.redhat.com/promo/dg6beta</a><br></blockquote><blockquote type="cite"><br></blockquote><blockquote type="cite">
<br>
</blockquote><blockquote type="cite">_______________________________________________<br></blockquote><blockquote type="cite">infinispan-dev mailing list<br></blockquote><blockquote type="cite"><a href="mailto:infinispan-dev@lists.jboss.org" target="_blank">infinispan-dev@lists.jboss.org</a><br>
</blockquote><blockquote type="cite"><a href="https://lists.jboss.org/mailman/listinfo/infinispan-dev" target="_blank">https://lists.jboss.org/mailman/listinfo/infinispan-dev</a><br></blockquote><br>_______________________________________________<br>
infinispan-dev mailing list<br><a href="mailto:infinispan-dev@lists.jboss.org" target="_blank">infinispan-dev@lists.jboss.org</a><br><a href="https://lists.jboss.org/mailman/listinfo/infinispan-dev" target="_blank">https://lists.jboss.org/mailman/listinfo/infinispan-dev</a><br>
</div></blockquote></div></div></div><div><div><br><div>
<span style="text-indent:0px;letter-spacing:normal;font-variant:normal;text-align:-webkit-auto;font-style:normal;font-weight:normal;line-height:normal;border-collapse:separate;text-transform:none;font-size:medium;white-space:normal;font-family:Helvetica;word-spacing:0px"><span style="text-indent:0px;letter-spacing:normal;font-variant:normal;font-style:normal;font-weight:normal;line-height:normal;border-collapse:separate;text-transform:none;font-size:medium;white-space:normal;font-family:Helvetica;word-spacing:0px"><div style="word-wrap:break-word">
<div><div><div>--</div><div>Manik Surtani</div><div><a href="mailto:manik@jboss.org" target="_blank">manik@jboss.org</a></div><div><a href="http://twitter.com/maniksurtani" target="_blank">twitter.com/maniksurtani</a></div>
<div><br></div><div>Project Lead, Infinispan</div><div><a href="http://www.infinispan.org" target="_blank">http://www.infinispan.org</a></div><div><br></div><div>Platform Architect, JBoss Data Grid</div><div><a href="http://www.redhat.com/promo/dg6beta" target="_blank">http://www.redhat.com/promo/dg6beta</a></div>
</div></div></div></span></span>
</div>
<br></div></div></div><br>_______________________________________________<br>
infinispan-dev mailing list<br>
<a href="mailto:infinispan-dev@lists.jboss.org" target="_blank">infinispan-dev@lists.jboss.org</a><br>
<a href="https://lists.jboss.org/mailman/listinfo/infinispan-dev" target="_blank">https://lists.jboss.org/mailman/listinfo/infinispan-dev</a><br></blockquote></div><br>