[bookkeeper] branch asf-site updated: Updated site at revision fe50b8c

[gi...@apache.org]

This is an automated email from the ASF dual-hosted git repository.

git-site-role pushed a commit to branch asf-site
in repository https://gitbox.apache.org/repos/asf/bookkeeper.git


The following commit(s) were added to refs/heads/asf-site by this push:
     new 8edff21  Updated site at revision fe50b8c
8edff21 is described below

commit 8edff214f5309138e9c2c793dd73c5d7ae8fbdea
Author: jenkins <bu...@apache.org>
AuthorDate: Sat Nov 17 17:41:06 2018 +0000

    Updated site at revision fe50b8c
---
 .../bps/BP-34-cluster-metadata-checker/index.html  | 62 ++++++++++++++++++++--
 1 file changed, 59 insertions(+), 3 deletions(-)

diff --git a/content/bps/BP-34-cluster-metadata-checker/index.html b/content/bps/BP-34-cluster-metadata-checker/index.html
index 0b9dfab..28ffcfe 100644
--- a/content/bps/BP-34-cluster-metadata-checker/index.html
+++ b/content/bps/BP-34-cluster-metadata-checker/index.html
@@ -298,13 +298,69 @@
 message GetListOfEntriesOfALedgerResponse {
 	required StatusCode status = 1;
 	required int64 ledgerId = 2;
-	optional bytes availabilityOfEntriesOfLedger = 3; // treated as array of bits indicating availability of entry at that particular index location		
+	optional bytes availabilityOfEntriesOfLedger = 3; // explained below
 }
 </code></pre></div></div>
 
-<p>For the sake of future extensibility it would be helpful to add version info (and possibly some metadata in the future) at the beginning of the ‘availabilityOfEntriesOfLedger’. So the first 64 bytes will be considered reserved space, with the first byte specifying the version for now and the rest of the bytes in the reserved space will be 0’s.</p>
+<p>For ‘availabilityOfEntriesOfLedger’ we can use following condensed encoding format, which helps in reducing the number of bytes needed to represent the list of entries.</p>
 
-<p>Here Bookie is expected to attain this information just from just LedgerCache (Index Files) - IndexPersistenceMgr and IndexInMemPageMgr but it doesn’t actually check the availability of this entry in Entrylogger. Since the intention of this checker is limited to do just metadata validation at cluster level.</p>
+<p>(note: following representation is used just for understanding purpose, but this is not protobuf (or any other) representation)</p>
+
+<div class="highlighter-rouge"><div class="highlight"><pre class="highlight"><code>AvailabilityOfEntriesOfLedger {
+	OrderedCollection sequenceGroup;
+}
+
+SequenceGroup {
+	long firstSequenceStart;
+	long lastSequenceStart;
+	int sequenceSize;
+	int sequencePeriod;
+}
+</code></pre></div></div>
+
+<p>Nomenclature:</p>
+
+<ul>
+  <li>Continuous entries are grouped as a ’Sequence’.</li>
+  <li>Number of continuous entries in a ‘Sequence’ is called ‘sequenceSize’.</li>
+  <li>Gap between Consecutive sequences is called ‘sequencePeriod’.</li>
+  <li>Consecutive sequences with same sequenceSize and same sequencePeriod in between consecutive sequences are grouped as a SequenceGroup.</li>
+  <li>‘firstSequenceStart’ is the first entry in the first sequence of the SequenceGroup.</li>
+  <li>‘lastSequenceStart’ is the first entry in the last sequence of the SequenceGroup.</li>
+  <li>Ordered collection of such SequenceGroups will represent entries of a ledger residing in a bookie.</li>
+</ul>
+
+<p>(in the best case scenario there will be only one SequenceGroup, ‘sequencePeriod’ will be ensembleSize and ‘sequenceSize’ will be writeQuorumSize of the ledger).</p>
+
+<p>for example,</p>
+
+<p>example 1 (best case scenario):</p>
+
+<p>1, 2, 4, 5, 7, 8, 10, 11</p>
+
+<p>in this case (1, 2), (4, 5), (7, 8), (10, 11) are sequences and in this scenario there happens to be just one SequenceGroup, which can be represented like</p>
+
+<p>{ firstSequenceStart - 1, lastSequenceStart - 10, sequenceSize - 2, sequencePeriod - 3 }</p>
+
+<p>example 2 (an entry is missing):</p>
+
+<p>1, 2, 3, 6, 7, 8, 11, 13, 16, 17, 18, 21, 22</p>
+
+<p>(entry 12 is missing and in the last sequence there are only 2 entries 21, 22)
+in this case (1, 2, 3), (6, 7, 8), (11), (13), (16, 17, 18), (21, 22) are the sequences
+so the sequence groups are</p>
+
+<p>{ firstSequenceStart - 1, lastSequenceStart - 6, sequenceSize - 3, sequencePeriod - 5 }, { firstSequenceStart - 11, lastSequenceStart - 13, sequenceSize - 1, sequencePeriod - 2 }, { firstSequenceStart - 16, lastSequenceStart - 16, sequenceSize - 3, sequencePeriod - 0 }, { firstSequenceStart - 21, lastSequenceStart - 21, sequenceSize - 2, sequencePeriod - 0 }</p>
+
+<p>As you can notice to represent a SequenceGroup, two long values and two int values are needed, so each SequenceGroup can be represented with (2 * 8 + 2 * 4 = 24 bytes).</p>
+
+<p>In the ‘availabilityOfEntriesOfLedger’ byte array, for the sake of future extensibility it would be helpful to have reserved space for metadata at the beginning. So the first 64 bytes will be used for metadata, with the first four bytes specifying the int version number, next four bytes specifying the number of entries for now and the rest of the bytes in the reserved space will be 0’s. The encoded format will be represented after the first 64 bytes. The ordered collection of Sequence [...]
+
+<p>So for a ledger having thousands of entries, this condensed encoded format would need one or two SequenceGroups (in the best case, with no holes and no overreplication) 24/48 bytes, which would be much less than what is needed to represent using bit vector (array of bits indicating availability of entry at that particular index location)</p>
+
+<p>Any encoded format needs encoder and decoder at the sending/receiving ends of the channel, so the encoding/decoding logic should be handled optimally from computation and memory perspective.</p>
+
+<p>Here Bookie is expected to just attain index information (say from LedgerCache (Index Files) - IndexPersistenceMgr and IndexInMemPageMgr, unflushed entries in EntryMemTable in SortedLedgerStorage case and from rocksdb database in DBLedgerStorage case) but it doesn’t actually check the availability of this entry in Entrylogger. Since the intention of this checker is limited to do just metadata validation at cluster level.</p>
 
 <h3 id="compatibility-deprecation-and-migration-plan">Compatibility, Deprecation, and Migration Plan</h3>