<html><head><meta http-equiv="Content-Type" content="text/html; charset=utf-8"></head><body style="word-wrap: break-word; -webkit-nbsp-mode: space; line-break: after-white-space;" class=""><br class=""><div class=""><br class="Apple-interchange-newline"><br class="Apple-interchange-newline">
</div>
<div><br class=""><blockquote type="cite" class=""><div class="">19 марта 2020 г., в 12:17, Sergey Ostanevich <<a href="mailto:sergos@tarantool.org" class="">sergos@tarantool.org</a>> написал(а):</div><br class="Apple-interchange-newline"><div class=""><span style="caret-color: rgb(0, 0, 0); font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration: none; float: none; display: inline !important;" class="">On 19 мар 11:41, 'Konstantin Osipov' wrote:</span><br style="caret-color: rgb(0, 0, 0); font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration: none;" class=""><blockquote type="cite" style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-size-adjust: auto; -webkit-text-stroke-width: 0px; text-decoration: none;" class="">* Timur Safin <<a href="mailto:tsafin@tarantool.org" class="">tsafin@tarantool.org</a>> [20/03/19 11:11]:<br class=""><blockquote type="cite" class="">: > A matrix clock which allows to maintain a set of vclocks and<br class="">: > their components order. The main target is to be able to<br class="">: > build a vclock which contains lsns each one is less or equal<br class="">: > that n corresponding lsn from a matrix clock.<br class="">: ><br class="">: > The purpose of the matrix clock is to evaluate a vclock<br class="">: > which is already processed by wal consumers like relays<br class="">: > or to obtain a majority vclock to commit journal entries<br class="">: > in case of synchronous replication.<br class="">: ><br class="">: > @sergepetrenko: refactoring & rewrite comments to doxygen style.<br class="">:<span class="Apple-converted-space"> </span><br class="">: I think we have discussed that matrix clock should not be pushed.<br class="">:<span class="Apple-converted-space"> </span><br class="">: It's a huge over complication.<br class="">:<span class="Apple-converted-space"> </span><br class="">: Why are you committing this?<br class="">:<span class="Apple-converted-space"> </span><br class="">: --<br class="">: Konstantin Osipov, Moscow, Russia<br class=""><br class="">That's the very good question. There is smell of some miscommunication<br class="">between parties involved, hopefully we will resolve it soon.<span class="Apple-converted-space"> </span><br class="">Last time we gathered to discuss sync replications, the consensus was<span class="Apple-converted-space"> </span><br class="">That we do not want matrix clock as they overcomplicate conflict resolution process (so, at least, it was not looking like prerequisite to sync<br class="">replications mechanism).<br class=""></blockquote></blockquote></div></blockquote><div><br class=""></div>Hi, Timur. It’s not about conflict resolution or anything user-visible. I guess the structure naming</div><div>is misguiding here. Please see a more detailed answer below.</div><div><br class=""><blockquote type="cite" class=""><div class=""><blockquote type="cite" style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-size-adjust: auto; -webkit-text-stroke-width: 0px; text-decoration: none;" class=""><br class="">George should clarify, but AFAIU his original design introduced<br class="">matrix clock to GC and to sync replication. These series only<br class="">touch the GC. George reported there was an issue with the current<br class="">GC tracker, basically it becomes non-function when sync<br class="">replication is in place -I don't know what the issue is.<span class="Apple-converted-space"> </span><br class=""><br class="">I'd love to discuss the problem first, and then see alternatives.<br class=""><br class="">The thing is, I'd like our vclock to become sparse one day and be<br class="">able to contain thousands of entries. We could use a dynamic data structure<br class="">which changes the underlying structure depending on the actual<br class="">member count.<br class="">To get there and stay efficient, we need to make sure we never<br class="">copy entire vclock by value, and instead begin passing objects<br class="">representing a "vclock diff" around. Maintaining a sparse matrix would be<br class="">hell in this case.<br class=""><br class=""><blockquote type="cite" class="">Serge, if I miss some important detains here, I'd love to get corrected<span class="Apple-converted-space"> </span><br class="">here. I do feel there are some other reasons needed, which I probably<br class="">simply not aware of.<br class=""></blockquote></blockquote><br style="caret-color: rgb(0, 0, 0); font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration: none;" class=""><span style="caret-color: rgb(0, 0, 0); font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration: none; float: none; display: inline !important;" class="">The discussion was with MRG users of Tarantool and their point was: they</span><br style="caret-color: rgb(0, 0, 0); font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration: none;" class=""><span style="caret-color: rgb(0, 0, 0); font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration: none; float: none; display: inline !important;" class="">are facing problems with consistent state restore and root cause</span><br style="caret-color: rgb(0, 0, 0); font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration: none;" class=""><span style="caret-color: rgb(0, 0, 0); font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration: none; float: none; display: inline !important;" class="">analysis in case of Tarantool failure.<span class="Apple-converted-space"> </span></span><br style="caret-color: rgb(0, 0, 0); font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration: none;" class=""><span style="caret-color: rgb(0, 0, 0); font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration: none; float: none; display: inline !important;" class="">It's a huge burden for them to debug and fix their applications even with<span class="Apple-converted-space"> </span></span><br style="caret-color: rgb(0, 0, 0); font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration: none;" class=""><span style="caret-color: rgb(0, 0, 0); font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration: none; float: none; display: inline !important;" class="">vector clock, while introduction of matrix one will make this task<span class="Apple-converted-space"> </span></span><br style="caret-color: rgb(0, 0, 0); font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration: none;" class=""><span style="caret-color: rgb(0, 0, 0); font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration: none; float: none; display: inline !important;" class="">impossible.<span class="Apple-converted-space"> </span></span><br style="caret-color: rgb(0, 0, 0); font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration: none;" class=""></div></blockquote><div><br class=""></div><div>The patches are not making it harder for the customers. The ‘matrix clock’ is just an</div><div>in-memory structure, which cannot be accessed by the database user.</div><div>It is used to build the minimal possible clock, which is still needed by the replicas.</div><div>We may rename it to whatever you wish, just like Georgy said. Let it be vclock sorted set</div><div>(although we already have a vclock set), or something else, like vclock sorter, whatever.</div><div>This structure is not persisted anywhere and no one sees it.</div><div><br class=""></div><div>We do need to rework our GC, and Georgy’s patches regarding matrix clock perform exactly</div><div>this task.</div><div><br class=""></div><div>First of all, let me describe the issue with the current WAL GC:</div><div>it tracks consumers (i.e. remote replicas) by their vclock signature,</div><div>which is the sum of all vclock components.</div><div>It has always been wrong (since the introduction of vclocks, at least):</div><div>Say, you have 2 masters, A and B with ids 1 and 2 respectively, and a replica C with id 3.</div><div>The example will be a little synthetic, but it illustrates the problem:</div><div>Say С replicates from both A and B, and there is no replication between A and B (say, the</div><div>instances were reconfigured to not replicate from each other).</div><div>Now, say replica C has followed A and B to vclock {1:5, 2:13}. At the same time, A has lsn 10</div><div>and B has lsn 15. A and B do not know about each other’s changes, so A’s vclock is {1:10} and</div><div>B’s vclock is {2:15}. Now imagine A does a snapshot and creates a new xlog with signature 10.</div><div>A’s directory will look like: 00…000.xlog 00…010.snap 00….010.xlog</div><div>Replica C reports its vclock {1:5, 2:13} to A, A uses the vclock to update the corresponding GC</div><div>consumer. Since signatures are used, GC consumer is assigned a signature = 13 + 5 = 18.</div><div>This is greater than the signature of the last xlog on A (10), so the previous xlog (00…00.xlog) can be</div><div>deleted (at least A assumes it can be). Actually, replica still needs 00…00.xlog, because it contains</div><div>rows corresponding to vclocks {1:6} - {1:10}, which haven’t been replicated yet.</div><div><br class=""></div><div>If instead of using vclock signatures, gc consumers used vclocks, such a problem wouldn’t arise.</div><div>Replia would report its vclock {1:5, 2:13}. The vclock is NOT strictly greater than A’s most recent</div><div>xlog vclock ({1:10}), so the previous log is kept until replica reports a vclock {1:10, 2:something}.</div><div>(or {1:11, …} and so on).</div><div><br class=""></div><div>Local space rework performed in this patchset in scope of the issue #4114 makes the problem even</div><div>more obvious: I want to use 0-th vclock component to track local space changes.</div><div>Now master has it’s own 0-th vclock component, and replica has its own one.</div><div>If I used the replica clock «as is» with current GC consumer, it wouldn’t work at all: see example 1 below.</div><div>If I substituted the replica clock[0] with masters clock[0] it also wouldn’t work, see example 2 below.</div><div><br class=""></div><div>Example 1:</div><div>master vclock {1:10}, replica vclock {0:5, 1:5}. Replica still needs rows in range {1:5} - {1:10}, but its vclock</div><div>signature is the same as master’s one, so master deletes logs needed by replica.</div><div><br class=""></div><div>Example 2:</div><div>master vclock {0:100500, 1:10}, replica vclock {0:1, 1:5}.</div><div>master substitutes replica’s 0 vclock component, so it becomes {0:100500, 1:5}. Now replica vclock</div><div>signature is 100505, which is much greater than signature 10 of the xlog containing rows in range</div><div>{1:1} - {1:10} and especially the range still needed by replica: {1:6} - {1:10}.</div><div><br class=""></div><div>It might seem than ignoring 0 vclock component is an option, but it’s not: we may ignore 0-th vclock components</div><div>for GC consumers corresponding to remote replicas, but local instance checkpoints(snapshots) are also tracked</div><div>together with GC consumers, and 0 vclock component cannot be ignored for them.</div><div><br class=""></div><div>OK, so now it’s clear that we need to use vclocks to track GC consumers. How do we find the minimal vclock</div><div>that is still needed? We need the biggest vclock, that is less than vclock of every GC consumer. This vclock</div><div>can be built using the matrix clock Georgy introduced. That’s it. Matrix clock works as follows:</div><div>say you have consumer clocks: {1:5, 2:10, 3:15}, {1:10, 2:6, 3:10} and {1:10, 2:15, 3:9}. The matrix clock will</div><div>build a vclock {1:5, 2:6, 3:9}. This vclock holds the minimum component per lsn that is still needed.</div><div>Now all the logs with vclocks strictly less, than the built one, may be deleted.</div><div><br class=""></div><div>I hope my explanation answers most of the questions. Feel free to ask.</div><div><br class=""></div><div><div>--</div><div>Serge Petrenko</div><div><a href="mailto:sergepetrenko@tarantool.org" class="">sergepetrenko@tarantool.org</a></div><div class=""><br class=""></div></div><br class=""><blockquote type="cite" class=""><div class=""><br style="caret-color: rgb(0, 0, 0); font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration: none;" class=""><blockquote type="cite" style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-size-adjust: auto; -webkit-text-stroke-width: 0px; text-decoration: none;" class=""><br class="">--<span class="Apple-converted-space"> </span><br class="">Konstantin Osipov, Moscow, Russia</blockquote></div></blockquote></div><br class=""></body></html>