Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Support delete #7

Open
maximecaron opened this issue Jun 8, 2017 · 2 comments
Open

Support delete #7

maximecaron opened this issue Jun 8, 2017 · 2 comments

Comments

@maximecaron
Copy link

maximecaron commented Jun 8, 2017

With current algorithm it's impossible to Delete a key without leaving a Tombstone forever in each Redis replica.
From the client point of view, it's only safe to assume a key is deleted if all replica respond that the key is missing.

The only solution I can think of at the moment is to implement some kind of copying garbage collector that periodically move all non-deleted key to a new epoch.

@rystsov
Copy link
Collaborator

rystsov commented Jan 17, 2018

It'd be very expensive to move all non-deleted keys. It looks like there is a cheaper way:

  1. Imagine that along with accept.lua there is acceptTombstone.lua which works the same way but also puts a key into a local deleting queue.
  2. Once a client wants to remove a value it puts a tombstone but instead of accept.lua it uses acceptTombstone.lua since it works the same way consistency isn't affected
  3. A GC process regularly:
    • peeks a key from the deleting queue
    • executes identity transformation with the write quorum covering whole cluster
    • pops the key from deleting queue and pushes into deleted queue on every acceptor
  4. Another GC process regularly:
    • peeks a key from the deleted queue
    • connects to each acceptor and wipes a corresponding tombstone
    • pops the key from the deleted queue

Once we know that a tombstone was written to all acceptors it's safe to remove it outside the paxos read/write loop since the state (all value are tombstones) becomes isomorphic to the initial state (all values are null).

During a membership change an operator stops both GC processes, does a migration, updates GC's config (addresses of acceptors and proposers) and restarts the processes.

@rystsov rystsov closed this as completed Jan 17, 2018
@rystsov rystsov reopened this Jan 17, 2018
@maximecaron
Copy link
Author

maximecaron commented Feb 13, 2018

in step #3 when you say write quorum do you mean all nodes or just majority ?
If it's all nodes then it mean Tombstone can only be cleaned when all node are online.

This still seem like a good practical solution, thanks a lot for the feedback.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

2 participants