<div dir="ltr"><br><div class="gmail_extra"><br><div class="gmail_quote">On Wed, Jan 21, 2015 at 3:12 AM, Sanne Grinovero <span dir="ltr"><<a href="mailto:sanne@infinispan.org" target="_blank">sanne@infinispan.org</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex"><span>On 20 January 2015 at 13:32, Dan Berindei <<a href="mailto:dan.berindei@gmail.com" target="_blank">dan.berindei@gmail.com</a>> wrote:<br>
> Adrian, I don't think that will work. The Hash doesn't know the number of<br>
> segments so it can't tell where a particular key will land - even assuming<br>
> knowledge about how the ConsistentHash will map hash codes to segments.<br>
><br>
> However, I'm all for replacing the current Hash interface with another<br>
> interface that maps keys directly to segments.<br>
<br>
</span>Right, I'll eventually need a different abstraction, or a change to<br>
the Hash interface. However my need seems highly specialistic, I'm not<br>
sure if there would be a general interest into such a capability for<br>
other Hash implementors?<br></blockquote><div><br></div><div>If it's better than KeyAffinityService and/or grouping, I'm pretty sure there will be other takers.</div><div> <br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex">
Never ever sign if you have more interesting comments below, I only<br>
saw them by chance ;)<br></blockquote><div><br></div><div>Oops, I only intended to reply to Adrian, and I forgot to remove the signature when I went further... I removed it now :)</div><div><br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex">
<div><div><br>
<br>
> On Tue, Jan 20, 2015 at 4:08 AM, Adrian Nistor <<a href="mailto:anistor@redhat.com" target="_blank">anistor@redhat.com</a>> wrote:<br>
>><br>
>> Hi Sanne,<br>
>><br>
>> An alternative approach would be to implement an<br>
>> org.infinispan.commons.hash.Hash which delegates to the stock<br>
>> implementation for all keys except those that need to be assigned to a<br>
>> specific segment. It should return the desired segment for those.<br>
>><br>
>> Adrian<br>
>><br>
>><br>
>> On 01/20/2015 02:48 AM, Sanne Grinovero wrote:<br>
>> > Hi all,<br>
>> ><br>
>> > I'm playing with an idea for some internal components to be able to<br>
>> > "tag" the key for an entry to be stored into Infinispan in a very<br>
>> > specific segment of the CH.<br>
>> ><br>
>> > Conceptually the plan is easy to understand by looking at this patch:<br>
>> ><br>
>> ><br>
>> > <a href="https://github.com/Sanne/infinispan/commit/45a3d9e62318d5f5f950a60b5bb174d23037335f" target="_blank">https://github.com/Sanne/infinispan/commit/45a3d9e62318d5f5f950a60b5bb174d23037335f</a><br>
>> ><br>
>> > Hacking the change into ReplicatedConsistentHash is quite barbaric,<br>
>> > please bear with me as I couldn't figure a better way to be able to<br>
>> > experiment with this. I'll probably want to extend this class, but<br>
>> > then I'm not sure how to plug it in?<br>
><br>
><br>
> You would need to create your own ConsistentHashFactory, possibly extending<br>
> ReplicatedConsistentHashFactory. You can then plug the factory in with<br>
><br>
> configurationBuilder.clustering().hash().consistentHashFactory(yourFactory)<br>
><br>
> However, this isn't a really good idea, because then you need a different<br>
> implementation for distributed mode, and then another implementation for<br>
> topology-aware clusters (with rack/machine/site ids). And your users would<br>
> also need to select the proper factory for each cache.<br>
<br>
</div></div>Right, this is the complexity I was facing. I'll stick to my hack<br>
solution for our little POC... but ultimately I'll need to plug this<br>
in if none of the solutions below work out.<br></blockquote><div><br></div><div>In the meantime Adrian clarified that you're creating the configuration yourself, so there's no problem picking the proper consistent hash factory - as long as the user didn't plug in his own for the indexed cache.</div><div> </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex">
<span><br>
>> > What would you all think of such a "tagging" mechanism?<br>
>> ><br>
>> > # Why I didn't use the KeyAffinityService<br>
>> > - I need to use my own keys, not the meaningless stuff produced by the<br>
>> > service<br>
>> > - the extensive usage of Random in there doesn't seem suited for a<br>
>> > performance critical path<br>
><br>
><br>
> You can plug in your own KeyGenerator to generate keys, and maybe replace<br>
> the Random with a static/thread-local counter.<br>
<br>
</span>Thanks for the tip on KeyGenerator, I'll investigate on that :)<br>
But I'll never add a static/threadlocal.. I'd rather commit my ugly<br>
code from the commit linked above.<br></blockquote><div><br></div><div>Indeed, the fact that you need to generate a different key every time makes KeyAffinityService harder to work with.</div><div><br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex">
<span><br>
><br>
>><br>
>><br>
>><br>
>> ><br>
>> > # Why I didn't use the Grouping API<br>
>> > - I need to pick the specific storage segment, not just co-locate with<br>
>> > a different key<br>
>> ><br>
><br>
><br>
> This is actually a drawback of the KeyAffinityService more than Grouping.<br>
> With grouping, you can actually follow the KeyAffinityService strategy and<br>
> generate random strings until you get one in the proper segment, and then<br>
> tag all your keys with that exact string.<br>
<br>
</span>Interesting! A bit convoluted but could spare me to plug in the HashFactory.<br>
BTW I really dislike this idea of the KeyAffinityService to generate<br>
random keys until it works out.. I guess it might not be too bad if<br>
you want to pick a node out of ten, but I'm working at segment<br>
granularity level and with the right luck it could take a long time.<br>
It would be nice to have a function like this which would return in a<br>
deterministic amount of time, like simply an inverse Hash.<br></blockquote><div><br></div><div>Weird, I was 100% sure that there's no way to reverse MurmurHash3, but it seems there is [1]. Our implementation is a bit different, but it shouldn't be very hard to adopt.</div><div><br></div><div>On the other hand, AbstractTopologyAwareEncoder1x.denormalizeSegmentHashIds brute-forces MurmurHash3 on each topology update to get a "denormalized" start value for each segment, which has to map to 0.2% of the segment. I don't remember how much it took, but it wasn't that bad. The good part about using grouping is that you can have lots of keys with the same group key, so you would only have to find the inverse once.</div><div><br></div><div>[1] <a href="https://131002.net/siphash/#at" target="_blank">https://131002.net/siphash/#at</a></div><div> </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex">
<span><br>
>> > The general goal is to make it possible to "tag" all entries of an<br>
>> > index, and have an independent index for each segment of the CH. So<br>
>> > the resulting effect would be, that when a primary owner for any key K<br>
>> > is making an update, and this triggers an index update, that update is<br>
>> > A) going to happen on the same node -> no need to forwarding to a<br>
>> > "master indexing node"<br>
>> > B) each such writes on the index happen on the same node which is<br>
>> > primary owner for all the written entries of the index.<br>
>> ><br>
>> > There are two additional nice consequences:<br>
>> > - there would be no need to perform a reliable "master election":<br>
>> > ownership singleton is already guaranteed by Infinispan's essential<br>
>> > logic, so it would reuse that<br>
>> > - the propagation of writes on the index from the primary owner<br>
>> > (which is the local node by definition) to backup owners could use<br>
>> > REPL_ASYNC for most practical use cases.<br>>> ><br>
>> > So net result is that the overhead for indexing is reduced to 0 (ZERO)<br>
>> > blocking RPCs if the async repl is acceptable, or to only one blocking<br>
>> > roundtrip if very strict consistency is required.<br>
><br>
><br>
> Sounds very interesting, but I think there may be a problem with your<br>
> strategy: Infinispan doesn't guarantee you that one of the nodes executing<br>
> the CommitCommand is the primary owner at the time the CommitCommand is<br>
> executed. You could have something like this:<br>
<br>
</span>Index storage is generally used without transactions, but even<br>
assuming we had transactions enabled or the "vanilla" put operation<br>
suffered had a similar timing issue (as we'd determine this node to be<br>
owner higher up in the search stack, before the actual put reaches the<br>
Infinispan core API) it's not a problem as we'd simply lose locality<br>
of the write: it would be slightly less efficient, but still write the<br>
"right thing".<br></blockquote><div><br></div><div><div>I was thinking about the indexed cache, not the storage cache. In the storage cache I think the only serious problem is when the originator dies, especially if it's also the primary owner, neither tx nor non-tx deal with that properly ATM.</div></div><div><br></div><div>However, if I understood your idea correctly, only the primary owner in the indexed cache will ever write to the index, and the indexed cache may well use transactions. So I think my scenario is relevant, and the index won't be updated by B or anyone else.</div><div><br></div><div>Non-transactional caches do not have the issue, the index update can only disappear if you use async replication in the index storage cache. Instead you can have a single write triggering multiple index updates, but I'm guessing you have that covered.</div><div> <br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex">
The intention is to maximise locality with the hints, but failing<br>
locality on writes I just expect it to be handled as any other put<br>
operation on Infinispan.. with a couple more RPCs, with any race<br>
condition regarding topology changes being handled at lower level.<br>
Which is exactly why I'm now working on top of container segments:<br>
they are a stable building block and allow us to not worry on how<br>
you'll actually distribute data or re-route update commands.<br>
<br></blockquote><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex">Thanks all for the suggestions!<br>
<span><font color="#888888">Sanne<br>
</font></span><div><div><br>
><br>
> Cluster [A, B, C, D], key k, owners(k) = [A, B] (A is primary)<br>
> C initiates a tx that executes put(k, v)<br>
> Tx prepare succeeds on A and B<br>
> A crashes, but the other nodes don't detect the crash yet<br>
> Tx commit succeeds on B, who still thinks is a backup owner<br>
> B detects the crash, installs a new cluster view consistent hash with<br>
> owners(k) = [B]<br>
></div></div></blockquote><div> </div></div></div><div class="gmail_extra">Cheers</div><div class="gmail_extra">Dan</div><div class="gmail_extra"><br></div></div>