Log truncation and sync up when bookie fails and rejoins

[Unmesh Joshi <un...@gmail.com>]

Hi,

In case of partial failures while implementing Replicated Log, there are
few requirements which need to be fulfilled to sync logs on multiple nodes
in case of node failure. e.g. In RAFT, if a node fails, there is a sync up
that happens with communication from leader to push all the entries and
truncation in case of some conflicting entries. Same happens with with
Kafka when followers start re pulling data after startup. Consistency need
to be maintained, by maintaining something like commitIndex or highwater
mark to have the index till which the majority of the servers have
acknowledged write.

In Apache BookKeeper I see that the consistency part is described well with
last add confirmed description in below documentation,
https://bookkeeper.apache.org/archives/docs/r4.4.0/bookkeeperProtocol.html

But who takes care of updating a particular Bookie in case it crashses (or
temporarily partitioned) and rejoins the cluster? Is there any
initialization protocol that is run at startup?
In Kafka, we have something like Controller which managers this
initialization, (or in RAFT its the current leader which will manage it)
I am going through the code to understand, but any pointers or hints will
be very helpful

Thanks,
Unmesh

Re: Log truncation and sync up when bookie fails and rejoins

[Ivan Kelly <iv...@apache.org>]

> From the bookie perspective, if a bookie of a ledger ensemble crashes while a ledger is being written to, then it is replaced and the history of the ledger is updated in the ledger metadata according to the last add confirmed by the crashed bookie. If the bookie crashes after the ledger is closed, then auto-recovery re-replicates the data.

There is one exception to this for the case where the ledger is being
actively written to. When the ack quorum is smaller than the write
quorum. In this case, when a bookie fails, entries between the point
of failure and the point of failure detection will only be replicated
|ackQuorum| times, not |writeQuorum| times. Autorecovery should
eventually pick this up.

-Ivan

Re: Log truncation and sync up when bookie fails and rejoins

[Ivan Kelly <iv...@apache.org>]

> Thanks for the detailed response. Just one question, if writer doesn't
> fail, but bookie write fails (Say a soft failure because of network problem
> or GC pause), the writer will create a new fragment within a ledger. So the
> same sequence of operations that happen while closing the ledger needs to
> happen at fragment level as well. Because the log entry can be copied to
> new fragment, the log from failed bookie (or more of soft-failed bookie
> because of network issue or GC pause) in previous fragment needs to be
> truncated.

In the case of a bookie failing during write, there's no need for the
recovery part of the process. The writer already knows which entry was
the last entry acknowledged before the failure. The write to update
the ensemble, i.e. create the new fragment, is similar as the write to
close the ledger. it fixes the last entry of the previous segment.

In terms of truncating, closing a fragment is not the same as closing
a ledger. Take the following scenario.

Writer w1
Bookie b1, b2

b1: e1, <crash>
b2: e1, e2

w1 is writing to a ledger, and b1 crashes before e2 is acknowledged.
w1 detects the crash and changes the ensemble to b3,b2, and then
promptly crashes. Recovery at this point may then recover the end of
the ledger as e2, even though the end of the fragment was e1. This is
fine, but it demonstrates how in a ensemble change truncation does not
occur.

-Ivan

Re: Log truncation and sync up when bookie fails and rejoins

[Unmesh Joshi <un...@gmail.com>]

Thanks for the detailed response. Just one question, if writer doesn't
fail, but bookie write fails (Say a soft failure because of network problem
or GC pause), the writer will create a new fragment within a ledger. So the
same sequence of operations that happen while closing the ledger needs to
happen at fragment level as well. Because the log entry can be copied to
new fragment, the log from failed bookie (or more of soft-failed bookie
because of network issue or GC pause) in previous fragment needs to be
truncated.

Thanks,
Unmesh

On Tue, Jan 28, 2020 at 6:32 PM Ivan Kelly <iv...@apache.org> wrote:

> > So.. log truncation, the way it's needed in leader based systems like
> RAFT
> > and Kafka, where leader may have entries appended to its log which are
> not
> > replicated. If leader crashes before replicating entries, which will
> elect
> > other node as leader. Once the previous leader rejoins the cluster, it
> > needs to truncate its own log removing all the conflicting entries. This
> > case wont happen in bookkeeper?
>
> Something similar does happen in bookkeeper. Firstly, it's important
> to keep in mind that a single ledger in bookkeeper only has a single
> writer ever. If the writer crashes, no new entries can be added to
> that ledger. In this way, you can kinda think of a ledger as a term in
> RAFT or an epoch in ZK. To build a replicated log in bookkeeper, you
> must chain a bunch of ledgers together. BK leaves that to the user.
>
> In the case of a writer crash, the next writer(i.e. the client adding
> the next ledger to the chain) needs to run the recovery algorithm,
> which finds the last entry which may possibly have been acknowledged
> to the reader. It uses this last entry to mark the ledger as closed.
> This "close" operation is similar to a truncate. Individual bookies in
> the ensemble may have entries past this last entry. However, these
> entries do not exist on enough bookies for the entry to have been
> acknowledged as written, so they can be ignored.
>
> For example, say you have a ledger A across 3 bookies, b1 and b2, and
> being written to by writer w1, with ensemble 2, write quorum 2 and ack
> quorum 2.
>
> w1 crashes when the bookies have the following entries.
>
> b1: e1
> b2: e1, e2
>
> The next writer, w2, could close this ledger at either e1 or e2. Both
> are correct.
> For e1, it would try to read the last entry from both b1 & b2, but
> only b1 would reply. w2 would see that e1 is the last entry on b1 and
> as ack quorum is 2, it no entry beyond e1 has been acknowledged to w1
> (to acknowledge to the writer, acknowledgement must be received from
> |ack quorum| bookies).
> For e2, it would try to read the last entry from both b1 & b2, either
> b2 or both would reply. If both replied w2 would see that e2 was
> written by the client, but not acknowledged to w1. However, it is also
> possible that only b2 replied, so w2 cannot divine whether e2 was
> acknowledged to w1. In both cases, it's safe to take e2 as the last
> entry. w2 ensures that e2 is replicated to |ack quorum| bookies, and
> marks it as the end of the ledger.
>
> The case where e1 was found to be the last ledger can be considered
> similar to truncate.
>
> -Ivan
>

Re: Log truncation and sync up when bookie fails and rejoins

[Ivan Kelly <iv...@apache.org>]

> So.. log truncation, the way it's needed in leader based systems like RAFT
> and Kafka, where leader may have entries appended to its log which are not
> replicated. If leader crashes before replicating entries, which will elect
> other node as leader. Once the previous leader rejoins the cluster, it
> needs to truncate its own log removing all the conflicting entries. This
> case wont happen in bookkeeper?

Something similar does happen in bookkeeper. Firstly, it's important
to keep in mind that a single ledger in bookkeeper only has a single
writer ever. If the writer crashes, no new entries can be added to
that ledger. In this way, you can kinda think of a ledger as a term in
RAFT or an epoch in ZK. To build a replicated log in bookkeeper, you
must chain a bunch of ledgers together. BK leaves that to the user.

In the case of a writer crash, the next writer(i.e. the client adding
the next ledger to the chain) needs to run the recovery algorithm,
which finds the last entry which may possibly have been acknowledged
to the reader. It uses this last entry to mark the ledger as closed.
This "close" operation is similar to a truncate. Individual bookies in
the ensemble may have entries past this last entry. However, these
entries do not exist on enough bookies for the entry to have been
acknowledged as written, so they can be ignored.

For example, say you have a ledger A across 3 bookies, b1 and b2, and
being written to by writer w1, with ensemble 2, write quorum 2 and ack
quorum 2.

w1 crashes when the bookies have the following entries.

b1: e1
b2: e1, e2

The next writer, w2, could close this ledger at either e1 or e2. Both
are correct.
For e1, it would try to read the last entry from both b1 & b2, but
only b1 would reply. w2 would see that e1 is the last entry on b1 and
as ack quorum is 2, it no entry beyond e1 has been acknowledged to w1
(to acknowledge to the writer, acknowledgement must be received from
|ack quorum| bookies).
For e2, it would try to read the last entry from both b1 & b2, either
b2 or both would reply. If both replied w2 would see that e2 was
written by the client, but not acknowledged to w1. However, it is also
possible that only b2 replied, so w2 cannot divine whether e2 was
acknowledged to w1. In both cases, it's safe to take e2 as the last
entry. w2 ensures that e2 is replicated to |ack quorum| bookies, and
marks it as the end of the ledger.

The case where e1 was found to be the last ledger can be considered
similar to truncate.

-Ivan

Re: Log truncation and sync up when bookie fails and rejoins

[Unmesh Joshi <un...@gmail.com>]

==You also ask for pointers. Are you ==looking for code pointers

Yes.. looking for code pointers..
So.. log truncation, the way it's needed in leader based systems like RAFT
and Kafka, where leader may have entries appended to its log which are not
replicated. If leader crashes before replicating entries, which will elect
other node as leader. Once the previous leader rejoins the cluster, it
needs to truncate its own log removing all the conflicting entries. This
case wont happen in bookkeeper?

On Tue 28 Jan, 2020, 4:43 PM Flavio Junqueira, <fp...@apache.org> wrote:

> Hi Umesh,
>
> The BookKeeper protocol is closer to register protocols than it is to
> consensus protocols, although we do need consensus for agreement on the
> closed state of a ledger. A ledger has a single writer, and either the
> writer closes it naturally or a reader needs to close it by running a
> recovery protocol that includes fencing the bookies. That's from the client
> perspective. From the bookie perspective, if a bookie of a ledger ensemble
> crashes while a ledger is being written to, then it is replaced and the
> history of the ledger is updated in the ledger metadata according to the
> last add confirmed by the crashed bookie. If the bookie crashes after the
> ledger is closed, then auto-recovery re-replicates the data.
>
> You also ask for pointers. Are you looking for code pointers?
>
> -Flavio
>
> > On 28 Jan 2020, at 10:15, Unmesh Joshi <un...@gmail.com> wrote:
> >
> > Hi,
> >
> > In case of partial failures while implementing Replicated Log, there are
> > few requirements which need to be fulfilled to sync logs on multiple
> nodes
> > in case of node failure. e.g. In RAFT, if a node fails, there is a sync
> up
> > that happens with communication from leader to push all the entries and
> > truncation in case of some conflicting entries. Same happens with with
> > Kafka when followers start re pulling data after startup. Consistency
> need
> > to be maintained, by maintaining something like commitIndex or highwater
> > mark to have the index till which the majority of the servers have
> > acknowledged write.
> >
> > In Apache BookKeeper I see that the consistency part is described well
> with
> > last add confirmed description in below documentation,
> >
> https://bookkeeper.apache.org/archives/docs/r4.4.0/bookkeeperProtocol.html
> >
> > But who takes care of updating a particular Bookie in case it crashses
> (or
> > temporarily partitioned) and rejoins the cluster? Is there any
> > initialization protocol that is run at startup?
> > In Kafka, we have something like Controller which managers this
> > initialization, (or in RAFT its the current leader which will manage it)
> > I am going through the code to understand, but any pointers or hints will
> > be very helpful
> >
> > Thanks,
> > Unmesh
>
>

Re: Log truncation and sync up when bookie fails and rejoins

[Flavio Junqueira <fp...@apache.org>]

Hi Umesh,

The BookKeeper protocol is closer to register protocols than it is to consensus protocols, although we do need consensus for agreement on the closed state of a ledger. A ledger has a single writer, and either the writer closes it naturally or a reader needs to close it by running a recovery protocol that includes fencing the bookies. That's from the client perspective. From the bookie perspective, if a bookie of a ledger ensemble crashes while a ledger is being written to, then it is replaced and the history of the ledger is updated in the ledger metadata according to the last add confirmed by the crashed bookie. If the bookie crashes after the ledger is closed, then auto-recovery re-replicates the data.

You also ask for pointers. Are you looking for code pointers?

-Flavio 

> On 28 Jan 2020, at 10:15, Unmesh Joshi <un...@gmail.com> wrote:
> 
> Hi,
> 
> In case of partial failures while implementing Replicated Log, there are
> few requirements which need to be fulfilled to sync logs on multiple nodes
> in case of node failure. e.g. In RAFT, if a node fails, there is a sync up
> that happens with communication from leader to push all the entries and
> truncation in case of some conflicting entries. Same happens with with
> Kafka when followers start re pulling data after startup. Consistency need
> to be maintained, by maintaining something like commitIndex or highwater
> mark to have the index till which the majority of the servers have
> acknowledged write.
> 
> In Apache BookKeeper I see that the consistency part is described well with
> last add confirmed description in below documentation,
> https://bookkeeper.apache.org/archives/docs/r4.4.0/bookkeeperProtocol.html
> 
> But who takes care of updating a particular Bookie in case it crashses (or
> temporarily partitioned) and rejoins the cluster? Is there any
> initialization protocol that is run at startup?
> In Kafka, we have something like Controller which managers this
> initialization, (or in RAFT its the current leader which will manage it)
> I am going through the code to understand, but any pointers or hints will
> be very helpful
> 
> Thanks,
> Unmesh

Re: Log truncation and sync up when bookie fails and rejoins

[Unmesh Joshi <un...@gmail.com>]

And in case writing to a bookie fail in a quorum fails, and entry is
rewritten on the other set of set of bookies, the truncation of entries on
that specific bookie beyond  last add confirmed, will also be handled by
auto recovery? So recovery does addition of missing entries, and truncation
of extra entries?

On Tue, Jan 28, 2020 at 2:59 PM Ivan Kelly <iv...@apache.org> wrote:

> > But who takes care of updating a particular Bookie in case it crashses
> (or
> > temporarily partitioned) and rejoins the cluster?
>
> Autorecovery takes care of this. The metadata describes the entries
> that should exist on a bookie. If this doesn't match what actually
> exists on the bookie, autorecovery rereplicates it.
>
> -Ivan
>

Re: Log truncation and sync up when bookie fails and rejoins

[Ivan Kelly <iv...@apache.org>]

> But who takes care of updating a particular Bookie in case it crashses (or
> temporarily partitioned) and rejoins the cluster?

Autorecovery takes care of this. The metadata describes the entries
that should exist on a bookie. If this doesn't match what actually
exists on the bookie, autorecovery rereplicates it.

-Ivan