You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@bookkeeper.apache.org by "Sijie Guo (JIRA)" <ji...@apache.org> on 2012/05/10 02:54:48 UTC
[jira] [Created] (BOOKKEEPER-249) Revisit garbage collection
algorithm in Bookie server
Sijie Guo created BOOKKEEPER-249:
------------------------------------
Summary: Revisit garbage collection algorithm in Bookie server
Key: BOOKKEEPER-249
URL: https://issues.apache.org/jira/browse/BOOKKEEPER-249
Project: Bookkeeper
Issue Type: Sub-task
Components: bookkeeper-server
Reporter: Sijie Guo
Per discussion in BOOKKEEPER-181, it would be better to revisit garbage collection algorithm in bookie server. so create a subtask to focus on it.
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators: https://issues.apache.org/jira/secure/ContactAdministrators!default.jspa
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Commented] (BOOKKEEPER-249) Revisit garbage collection
algorithm in Bookie server
Posted by "Sijie Guo (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/BOOKKEEPER-249?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13506710#comment-13506710 ]
Sijie Guo commented on BOOKKEEPER-249:
--------------------------------------
{quote}
1) A bookie b is not added to set B originally (bookie missing);
2) A bookie b writes entries of L after garbage-collecting it (bookie race).
{quote}
for case 2), I think it would already or could (if not) be addressed by some kind of agreements on the ledger state in ledger metadata.
But for case 1), it was difficult to track all the possible candidates of a ledger fragment, since failure could happen at any time between changing ledger metadata and writing entries. There are several concerns why talking about a FULL gc. first one is to not overwhelm the design and implementation of a fast gc algorithm to cover rare cases (like zombie entries). secondly, when the new gc algorithm is introduced, there are still lots of ledgers are deleted by old version of bookie clients, whose ledger metadata are not recorded in "/ledgers/deleted/Bi" znode. so at least we need a FULL gc to clean those ledgers deleted by old bookie clients.
A FULL gc is a easier and more consistent way to address the above concerns. And the cost of a FULL gc is quite fine since it would not be run frequently on every bookies.
> Revisit garbage collection algorithm in Bookie server
> -----------------------------------------------------
>
> Key: BOOKKEEPER-249
> URL: https://issues.apache.org/jira/browse/BOOKKEEPER-249
> Project: Bookkeeper
> Issue Type: Improvement
> Components: bookkeeper-server
> Reporter: Sijie Guo
> Fix For: 4.2.0
>
> Attachments: gc_revisit.pdf
>
>
> Per discussion in BOOKKEEPER-181, it would be better to revisit garbage collection algorithm in bookie server. so create a subtask to focus on it.
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Commented] (BOOKKEEPER-249) Revisit garbage collection
algorithm in Bookie server
Posted by "Flavio Junqueira (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/BOOKKEEPER-249?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13506651#comment-13506651 ]
Flavio Junqueira commented on BOOKKEEPER-249:
---------------------------------------------
GLB is the largest deleted ledger id in a prefix of deleted ledgers with no holes. Given a list of ledgers to delete, the GLB can be calculated from the list itself, after deleting all ledgers in the prefix. Of course, it assumes that the identifiers of ledgers a bookie stores increase monotonically. As you observed and I confirmed, if this assumption doesn't hold, then the scheme doesn't work.
> Revisit garbage collection algorithm in Bookie server
> -----------------------------------------------------
>
> Key: BOOKKEEPER-249
> URL: https://issues.apache.org/jira/browse/BOOKKEEPER-249
> Project: Bookkeeper
> Issue Type: Improvement
> Components: bookkeeper-server
> Reporter: Sijie Guo
> Fix For: 4.2.0
>
> Attachments: gc_revisit.pdf
>
>
> Per discussion in BOOKKEEPER-181, it would be better to revisit garbage collection algorithm in bookie server. so create a subtask to focus on it.
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Commented] (BOOKKEEPER-249) Revisit garbage collection
algorithm in Bookie server
Posted by "Flavio Junqueira (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/BOOKKEEPER-249?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13506332#comment-13506332 ]
Flavio Junqueira commented on BOOKKEEPER-249:
---------------------------------------------
I think your interpretation of what I've written is correct, but I haven't expressed properly what I was trying to achieve, so let me step back.
When we delete a ledger L, we notify to a set B of bookies through zookeeper that they need to garbage collect L. The set B is the union of all ensembles of L as written in its metadata. There are possibly two reasons for getting spurious or zombie entries:
# A bookie b is not added to set B originally (bookie missing);
# A bookie b writes entries of L after garbage-collecting it (bookie race).
According to your examples, I think the former can happen if a bookie writes entries of L but ends up no forming part of the ensemble of L. I don't see a way of detecting it other than:
* Having a confirmation from the client that a bookie is actually part of the ledger ensemble, which in some sense "commits" the ledger fragment the bookie wrote. We don't have such a confirmation today, so it would be necessary to add this mechanism.
* Having bookies periodically check if the ledger metadata still exists.
The mechanism I was proposing was for the bookie race case, to avoid the extra polling mechanism you suggested. I was essentially trying to maintain a greatest lower bound for the ledgers that have already been deleted. I understand that we don't delete them in order, although my example did give that impression.
To maintain such a greatest lower bound, I was thinking that we could delete only entire prefixes, with no holes. Let me go back to the example. If a bookie has entries for ledgers L1, L5, and L6, and L5 is deleted, then we wouldn't remove L5 or move the greatest lower bound until L1 is deleted. Once L1 is deleted, then we have a prefix formed by L1 and L5, and we remove the corresponding ledger fragments, setting also the greatest lower bound to 5.
One main drawback of this approach is having to wait until L1 is actually deleted, which can happen in principle at any arbitrary time. If ledgers don't live long, then it works fine. Otherwise, it could prevent bookies from reclaiming space for arbitrarily long periods.
> Revisit garbage collection algorithm in Bookie server
> -----------------------------------------------------
>
> Key: BOOKKEEPER-249
> URL: https://issues.apache.org/jira/browse/BOOKKEEPER-249
> Project: Bookkeeper
> Issue Type: Improvement
> Components: bookkeeper-server
> Reporter: Sijie Guo
> Fix For: 4.2.0
>
> Attachments: gc_revisit.pdf
>
>
> Per discussion in BOOKKEEPER-181, it would be better to revisit garbage collection algorithm in bookie server. so create a subtask to focus on it.
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Commented] (BOOKKEEPER-249) Revisit garbage collection
algorithm in Bookie server
Posted by "Rakesh R (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/BOOKKEEPER-249?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13496903#comment-13496903 ]
Rakesh R commented on BOOKKEEPER-249:
-------------------------------------
Hi Sijie, The idea of having DELETED state is nice and avoids unnecesary GC passes.
{quote}
Even we restricted deletion semantic above, we would still encountering zombie entries when changing ensemble
(it would happen during bookie failures and auto-rereplication).
{quote}
Re-replication of an OPEN ledger:-
For the above concern, if there is a bk failure in the writing ensemble, auto-rereplication process would wait for the defined grace period and initiate fence the ledger. Only after successful fencing would continue with re-replication of the ledger to new bookie. So the writer would get exception when tries writing later and prevents zombie entries.
Re-replication of CLOSED ledger:-
Here, the auto-rereplication would results zombie entries due to ensemble change. In your proposal I understand there is a place to hold all the ledgers to be deleted in ledgerManager, we could use that and just add one more step in autorereplication logic to update these failed bookie's ledgers in 'ledgers/deleted/Bi/'. So later once the failed bookie comes back, will do GCing. Also, we could think of using zk multi-transaction apis if there is any problem with zkDisconnection while updating failed bookie to new bookie(ledger's ensemble) and updating deleted ledgers of failed bookie.
Whats your opinion, Sijie?
> Revisit garbage collection algorithm in Bookie server
> -----------------------------------------------------
>
> Key: BOOKKEEPER-249
> URL: https://issues.apache.org/jira/browse/BOOKKEEPER-249
> Project: Bookkeeper
> Issue Type: Improvement
> Components: bookkeeper-server
> Reporter: Sijie Guo
> Fix For: 4.2.0
>
> Attachments: gc_revisit.pdf
>
>
> Per discussion in BOOKKEEPER-181, it would be better to revisit garbage collection algorithm in bookie server. so create a subtask to focus on it.
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Commented] (BOOKKEEPER-249) Revisit garbage collection
algorithm in Bookie server
Posted by "Fangmin Lv (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/BOOKKEEPER-249?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13506532#comment-13506532 ]
Fangmin Lv commented on BOOKKEEPER-249:
---------------------------------------
Actually I'm not quite clear about how to easily maintain GLB, it would be good if you could explain more about this, I mean the detailed algorithm to maintain this value.
> Revisit garbage collection algorithm in Bookie server
> -----------------------------------------------------
>
> Key: BOOKKEEPER-249
> URL: https://issues.apache.org/jira/browse/BOOKKEEPER-249
> Project: Bookkeeper
> Issue Type: Improvement
> Components: bookkeeper-server
> Reporter: Sijie Guo
> Fix For: 4.2.0
>
> Attachments: gc_revisit.pdf
>
>
> Per discussion in BOOKKEEPER-181, it would be better to revisit garbage collection algorithm in bookie server. so create a subtask to focus on it.
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Commented] (BOOKKEEPER-249) Revisit garbage collection
algorithm in Bookie server
Posted by "Flavio Junqueira (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/BOOKKEEPER-249?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13506518#comment-13506518 ]
Flavio Junqueira commented on BOOKKEEPER-249:
---------------------------------------------
I don't think the cost of maintaining the greatest lower bound would be high, but your observation about ledger ids not being monotonically increasing is a good one. I guess it could happen for example because of auto-replication.
In any case, I don't like the full gc idea. It would be nicer to rely upon a single mechanism instead of having to fall back to an alternative one.
> Revisit garbage collection algorithm in Bookie server
> -----------------------------------------------------
>
> Key: BOOKKEEPER-249
> URL: https://issues.apache.org/jira/browse/BOOKKEEPER-249
> Project: Bookkeeper
> Issue Type: Improvement
> Components: bookkeeper-server
> Reporter: Sijie Guo
> Fix For: 4.2.0
>
> Attachments: gc_revisit.pdf
>
>
> Per discussion in BOOKKEEPER-181, it would be better to revisit garbage collection algorithm in bookie server. so create a subtask to focus on it.
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Commented] (BOOKKEEPER-249) Revisit garbage collection
algorithm in Bookie server
Posted by "Fangmin Lv (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/BOOKKEEPER-249?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13506496#comment-13506496 ]
Fangmin Lv commented on BOOKKEEPER-249:
---------------------------------------
An interesting idea, but I think it's not appropriate for our scenario. It's hard and high costs to maintain the greatest lower bound(GLB), when delete one ledger we need to scan zookeeper and meta store to decide the GLB, partially or totally.
Maybe there will be large space waste, consider an extreme case, suppose we have L1, L2, ... L(2n-1), L(2n) ledgers, only the odd ledgers were deleted in the following time, then the deleted ledger will never been reclaimed.
Also it's difficult to keep things correct, take the same example:
1. initially we set the GLB to 0, we had L1, L5, and L6 in a bookie. and L5 is deleted.
2. a gc cycle is coming. found the GLB is 0, skip gc
3. L1 is deleted, GLB is updated to L5
4. new gc cycle is coming. found the GLB is L5 and would delete ledgers less then L5, in the mean time, L2 is added to the bookie, then this bookie will delete L2 which should not happen.
Correct me if I'm wrong or misread your idea, thanks.
> Revisit garbage collection algorithm in Bookie server
> -----------------------------------------------------
>
> Key: BOOKKEEPER-249
> URL: https://issues.apache.org/jira/browse/BOOKKEEPER-249
> Project: Bookkeeper
> Issue Type: Improvement
> Components: bookkeeper-server
> Reporter: Sijie Guo
> Fix For: 4.2.0
>
> Attachments: gc_revisit.pdf
>
>
> Per discussion in BOOKKEEPER-181, it would be better to revisit garbage collection algorithm in bookie server. so create a subtask to focus on it.
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Updated] (BOOKKEEPER-249) Revisit garbage collection
algorithm in Bookie server
Posted by "Sijie Guo (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/BOOKKEEPER-249?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Sijie Guo updated BOOKKEEPER-249:
---------------------------------
Issue Type: Improvement (was: Sub-task)
Parent: (was: BOOKKEEPER-181)
> Revisit garbage collection algorithm in Bookie server
> -----------------------------------------------------
>
> Key: BOOKKEEPER-249
> URL: https://issues.apache.org/jira/browse/BOOKKEEPER-249
> Project: Bookkeeper
> Issue Type: Improvement
> Components: bookkeeper-server
> Reporter: Sijie Guo
> Fix For: 4.2.0
>
> Attachments: gc_revisit.pdf
>
>
> Per discussion in BOOKKEEPER-181, it would be better to revisit garbage collection algorithm in bookie server. so create a subtask to focus on it.
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Commented] (BOOKKEEPER-249) Revisit garbage collection
algorithm in Bookie server
Posted by "Sijie Guo (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/BOOKKEEPER-249?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13506136#comment-13506136 ]
Sijie Guo commented on BOOKKEEPER-249:
--------------------------------------
{quote}
Let me give an example to illustrate. Say a bookie stores fragments for ledgers L1,L5,L6 and a client deletes L1 and L5. When it runs a gc cycle, it deletes L1 and L5 and writes to znode '/ledgers/deleted/Bi/Largest' the value L5. Eventually, another client deletes L6, the bookie deletes L6 and sets the data of '/ledgers/deleted/Bi/Largest' to L6. While checking the entries that it has stored, Bi finds that it has entries for a ledger with id smaller than 6, say L5, then it is safe to delete the entries.
{quote}
I don't think it was correct. since you could not guarantee the ledgers are created in bookie in ledger id's order.
take you example:
1) at time T, we had L1, L5, L6 in a bookie. L1 and L5 is deleted.
2) a gc cycle is coming. L1 and L5 are deleted and 'Largest' znode is updated to L5.
3) client of L2 is writing entries to this bookie now. L2 is created in this bookie to stored its fragments.
4) next gc cycle is coming. this bookie would delete L2 even L2 hasn't been deleted.
If I didn't understand your idea correctly, please correct me.
> Revisit garbage collection algorithm in Bookie server
> -----------------------------------------------------
>
> Key: BOOKKEEPER-249
> URL: https://issues.apache.org/jira/browse/BOOKKEEPER-249
> Project: Bookkeeper
> Issue Type: Improvement
> Components: bookkeeper-server
> Reporter: Sijie Guo
> Fix For: 4.2.0
>
> Attachments: gc_revisit.pdf
>
>
> Per discussion in BOOKKEEPER-181, it would be better to revisit garbage collection algorithm in bookie server. so create a subtask to focus on it.
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Commented] (BOOKKEEPER-249) Revisit garbage collection
algorithm in Bookie server
Posted by "Rakesh R (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/BOOKKEEPER-249?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13497061#comment-13497061 ]
Rakesh R commented on BOOKKEEPER-249:
-------------------------------------
bq.after updating failed bookie's ledgers in '/ledgers/deleted/Bi' when changing ensemble
In general, I agree with your suggestion of first update for deletion and then go to rereplication. Please go through the corner case in the ZKLedgerManager impl and causing data loss like, successfully updated the failed bookie's ledgers in '/ledgers/deleted/Bi' and while changing ensemble for auto-rereplication zk got disconnected. Now Bi will go ahead with ledger deletion if it rejoins, also rereplication process will see the bookie is live and stops rereplication. I feel, this is very straight scenario with ZKLedgerManager and nothing comes in my mind otherthan multi-transaction api usage:(
> Revisit garbage collection algorithm in Bookie server
> -----------------------------------------------------
>
> Key: BOOKKEEPER-249
> URL: https://issues.apache.org/jira/browse/BOOKKEEPER-249
> Project: Bookkeeper
> Issue Type: Improvement
> Components: bookkeeper-server
> Reporter: Sijie Guo
> Fix For: 4.2.0
>
> Attachments: gc_revisit.pdf
>
>
> Per discussion in BOOKKEEPER-181, it would be better to revisit garbage collection algorithm in bookie server. so create a subtask to focus on it.
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Updated] (BOOKKEEPER-249) Revisit garbage collection
algorithm in Bookie server
Posted by "Sijie Guo (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/BOOKKEEPER-249?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Sijie Guo updated BOOKKEEPER-249:
---------------------------------
Attachment: gc_revisit.pdf
Attach a improved gc algorithm proposal.
> Revisit garbage collection algorithm in Bookie server
> -----------------------------------------------------
>
> Key: BOOKKEEPER-249
> URL: https://issues.apache.org/jira/browse/BOOKKEEPER-249
> Project: Bookkeeper
> Issue Type: Sub-task
> Components: bookkeeper-server
> Reporter: Sijie Guo
> Fix For: 4.2.0
>
> Attachments: gc_revisit.pdf
>
>
> Per discussion in BOOKKEEPER-181, it would be better to revisit garbage collection algorithm in bookie server. so create a subtask to focus on it.
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Updated] (BOOKKEEPER-249) Revisit garbage collection
algorithm in Bookie server
Posted by "Sijie Guo (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/BOOKKEEPER-249?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Sijie Guo updated BOOKKEEPER-249:
---------------------------------
Fix Version/s: (was: 4.2.0)
4.3.0
> Revisit garbage collection algorithm in Bookie server
> -----------------------------------------------------
>
> Key: BOOKKEEPER-249
> URL: https://issues.apache.org/jira/browse/BOOKKEEPER-249
> Project: Bookkeeper
> Issue Type: Improvement
> Components: bookkeeper-server
> Reporter: Sijie Guo
> Fix For: 4.3.0
>
> Attachments: gc_revisit.pdf
>
>
> Per discussion in BOOKKEEPER-181, it would be better to revisit garbage collection algorithm in bookie server. so create a subtask to focus on it.
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Commented] (BOOKKEEPER-249) Revisit garbage collection
algorithm in Bookie server
Posted by "Sijie Guo (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/BOOKKEEPER-249?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13497139#comment-13497139 ]
Sijie Guo commented on BOOKKEEPER-249:
--------------------------------------
{quote}
Please go through the corner case in the ZKLedgerManager impl and causing data loss like, successfully updated the failed bookie's ledgers in '/ledgers/deleted/Bi' and while changing ensemble for auto-rereplication zk got disconnected. Now Bi will go ahead with ledger deletion if it rejoins
{quote}
first, I clarify a zombie entry is an entry was added to a bookie which could not be GC'ed. In the proposed algorithm, an zombie entry is the entry that are not referred in ledger metadata, since proposed algorithm is metadata-based gc algorithm.
second, '/ledgers/deleted/Bi' is kind of gc index : bookie -> ledgers.
third, changing ensemble would happen at following two cases:
1) changing ensemble when writing entries failed for a writer, which is update ledger metadata first and write entries later. (in the case, failed bookie would introduce zombie entry. e.g BK1, BK2, BK3 changed ensemble to BK1, BK4, BK3. BK2 is the bookie introduced zombie entry.)
2) changing ensemble when auto-replicating, which is write entries first and update ledger metadata later. (in the case, failed bookie and replaced bookie would both introduce zombie entry. e.g BK2 is failed in the ensemble BK1, BK2, BK3, we re-replicate entries belongs to BK2 to BK4. both BK2 and BK4 would introduce zombie entry.)
for the proposed GC algorithm, we need to track those bookies which would introduce zombie entries. The idea is we should add the bookies that would introduce zombie entry to the deleted index '/ledgers/deleted/Bi' when updating ensemble.
GC thread should go thru the deleted index and check the ledgers' metadata. GC thread would gc the ledger only when if the ledger is DELETED or doesn't exist. so I don't think it would case data loss.
But there was still a corner case we need to take care about auto-rereplication:
1) autorerep L, replace A with B. both A and B would be added to gc index.
2) client deleted L, autorerep is still replicating entries from A to B.
3) B runs gc, gc ledger L.
4) B would still have zombie entries since autorerep still writes entries to B even B finished gc ledger L.
one possible solution for this is when autorerep finished replicating entries from A to B and update ensemble. it would see BadVersion or NoSuchLedgerExists, it should add B again to gc index. But it was getting the algorithm messy.
The simple way for zombie entries, I believe would be running different gc algorithms in different granularity. For most case, we could run the proposed algorithm to do fast gc. When a bookie's disk space went out (suppose reached a specific threshold), the bookie runs a FULL GC. The FULL GC is the POLLING based gc algorithm, which takes the ledgers owned by the bookie and check whether the ledger was deleted or not and gc those deleted. Mostly zombie entries would be quite rare and we had compaction to take care of disk space. Only when a bookie's disk went out, we need to do a FULL GC to check whether it was caused by zombie entries.
> Revisit garbage collection algorithm in Bookie server
> -----------------------------------------------------
>
> Key: BOOKKEEPER-249
> URL: https://issues.apache.org/jira/browse/BOOKKEEPER-249
> Project: Bookkeeper
> Issue Type: Improvement
> Components: bookkeeper-server
> Reporter: Sijie Guo
> Fix For: 4.2.0
>
> Attachments: gc_revisit.pdf
>
>
> Per discussion in BOOKKEEPER-181, it would be better to revisit garbage collection algorithm in bookie server. so create a subtask to focus on it.
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Commented] (BOOKKEEPER-249) Revisit garbage collection
algorithm in Bookie server
Posted by "Sijie Guo (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/BOOKKEEPER-249?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13496945#comment-13496945 ]
Sijie Guo commented on BOOKKEEPER-249:
--------------------------------------
Thanks Rakesh for comments.
{quote}
just add one more step in autorereplication logic to update these failed bookie's ledgers in 'ledgers/deleted/Bi/'.
{quote}
It was a good idea to resolve zombie entry issue when changing ensembles. We could first add the failed bookie to '/ledgers/deleted/Bi', then update the ledger metadata to use new ensemble. just one point that bookie needs to take care, it should not garbage collect those ledgers still not marked as DELETED.
{quote}
using zk multi-transaction apis
{quote}
In general, we could not use multi-transaction. As in BOOKKEEPER-181, ledger metadata might be stored in other metadata storage. so the key point is that we should only update ledger metadata after updating failed bookie's ledgers in '/ledgers/deleted/Bi' when changing ensemble.
> Revisit garbage collection algorithm in Bookie server
> -----------------------------------------------------
>
> Key: BOOKKEEPER-249
> URL: https://issues.apache.org/jira/browse/BOOKKEEPER-249
> Project: Bookkeeper
> Issue Type: Improvement
> Components: bookkeeper-server
> Reporter: Sijie Guo
> Fix For: 4.2.0
>
> Attachments: gc_revisit.pdf
>
>
> Per discussion in BOOKKEEPER-181, it would be better to revisit garbage collection algorithm in bookie server. so create a subtask to focus on it.
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Commented] (BOOKKEEPER-249) Revisit garbage collection
algorithm in Bookie server
Posted by "Flavio Junqueira (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/BOOKKEEPER-249?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13505905#comment-13505905 ]
Flavio Junqueira commented on BOOKKEEPER-249:
---------------------------------------------
Here is a thought for dealing with zombie entries. We could keep for each bookie Bi, under '/ledgers/deleted/Bi', a znode containing the largest id (LL) of a ledger that the bookie has deleted. This way the bookie can check in each garbage-collection cycle if it has entries for a ledger L < LL. In this case, the bookie deletes those ledgers.
Let me give an example to illustrate. Say a bookie stores fragments for ledgers L1,L5,L6 and a client deletes L1 and L5. When it runs a gc cycle, it deletes L1 and L5 and writes to znode '/ledgers/deleted/Bi/Largest' the value L5. Eventually, another client deletes L6, the bookie deletes L6 and sets the data of '/ledgers/deleted/Bi/Largest' to L6. While checking the entries that it has stored, Bi finds that it has entries for a ledger with id smaller than 6, say L5, then it is safe to delete the entries.
What do you think, Sijie?
> Revisit garbage collection algorithm in Bookie server
> -----------------------------------------------------
>
> Key: BOOKKEEPER-249
> URL: https://issues.apache.org/jira/browse/BOOKKEEPER-249
> Project: Bookkeeper
> Issue Type: Improvement
> Components: bookkeeper-server
> Reporter: Sijie Guo
> Fix For: 4.2.0
>
> Attachments: gc_revisit.pdf
>
>
> Per discussion in BOOKKEEPER-181, it would be better to revisit garbage collection algorithm in bookie server. so create a subtask to focus on it.
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators
For more information on JIRA, see: http://www.atlassian.com/software/jira