10:38 a.m.
ccing vinzvault ml since question is generally applicable there
On Mon, 2010-05-10 at 11:11 -0400, Jeff Darcy wrote:
One of the things that I was surprised not to see in your list of
requirements is consistency. I know that you don't need instantaneous
fine-grain serializable consistency, but it seems like there still has
to be some assurance that an instantiated image won't be subject to
arbitrary data-retrieval failures or staleness even though the image was
written somewhere else quite recently with an unknown network
environment in between. As soon as there's a need for any level of
consistency at all, there's an issue of how to prevent/avoid conflicts
or reconcile results after they've occurred - e.g. Hinted Handoff, Read
Repair, and Anti-Entropy in the Dynamo/Cassandra model - without
creating a bottleneck at the coordination point(s). An image-storage
system that's "best effort" and either fails or delivers incorrect
(stale) data under conditions that are impossible to predict or to
identify post-mortem might not be very broadly accepted among the people
who have thousands of machines to look after. Given enough machines and
enough time, even exotic failures do occur. Do you have some thoughts
on what easily-checked rules vinzvault will apply to ensure data
consistency (and BTW integrity as well)?
As there is only one writer in every case, a simple lamport time stamp
would do the trick. The reason those full database systems you mention
have all that complicated consistency management is because they
potentially have multiple writers. With multiple writers, after a
failure during an update, a consistent view must be created out of the
mess. With one writer, the worst case that could happen is that *some*
of the blocks were not written. This happens with normal storage in a
block system all the time during failure and is well tolerated by
journal filesystems.
Regards
-steve
1:26 p.m.
New subject: Vinzvault consistency?
On 05/10/2010 11:38 AM, Steven Dake wrote:
As there is only one writer in every case, a simple lamport time
stamp
would do the trick.
How is there only one writer? Either there's only one possible writer
globally, there's only one possible writer per object, or you have to
coordinate/reconcile between possible writers - potentially across
sites, despite partitions, etc. Nothing in the very brief description
I've seen implies either the first or second. The first is so
non-scalable it's beneath notice, so that's just as well. The second is
possible if you adopt a write-once model where the object ID has the
writer ID as a prefix and objects are immutable once written, but I
haven't seen any mention of that and in any case it leaves open the
question of how to know an object is fully written. In either the
initial-write or the migration case (which is specifically mentioned in
the requirements), it's necessary to define what will happen when
someone at one end of a slow/flaky network connection writes a block and
someone at the far end asks for it while it's still in transit, or what
happens when two nodes on opposite sides of a network partition - i.e.
lacking any means of coordination - attempt to write the same block.
Who blocks? Who fails? Who reconciles conflicts? Lamport clocks and
their relatives do not solve the problem by themselves. They merely
provide information that some other part of the system must use (often
using multiple clock vectors for multiple related pieces of data) to
arrive at a correct result.
The reason those full database systems you mention
have all that complicated consistency management is because they
potentially have multiple writers. With multiple writers, after a
failure during an update, a consistent view must be created out of the
mess. With one writer, the worst case that could happen is that *some*
of the blocks were not written.
This is not something that only happens under failure conditions. In a
*distributed system*, data might be absent locally even if it's present
somewhere else in the system, and an EOF before the actual end of the
file - as when the writer was notified of completion at a clearly prior
time - is incorrect data. The situation's even worse when the data are
being written to multiple destinations with no assurance of order
between them, and I've seen nothing so far that assures order.
This happens with normal storage in a
block system all the time during failure and is well tolerated by
journal filesystems.
Yes, by having a journal that's fully/sequentially/consistently written
before the live filesystem, so that it can be replayed accurately even
if the writes to the live filesystem are interrupted. What do you
propose other nodes should do if they ask for data that's sitting in the
journal of a failed/unreachable node? Would those blocks be unavailable
for either reading or writing until that node comes back up, or do you
propose to implement a global distributed journal with all of the
necessary consistency and ordering to enable recovery? At some point
the hard distributed-system problems have to be solved, not just pushed
into another component.
1:48 p.m.
New subject: Vinzvault consistency?
On Mon, 2010-05-10 at 14:26 -0400, Jeff Darcy wrote:
On 05/10/2010 11:38 AM, Steven Dake wrote:
> As there is only one writer in every case, a simple lamport time stamp
> would do the trick.
How is there only one writer? Either there's only one possible writer
globally, there's only one possible writer per object, or you have to
coordinate/reconcile between possible writers - potentially across
sites, despite partitions, etc. Nothing in the very brief description
There is only ever one VM which may write to the vm store. During
migration LTS can be used to determine who has the most recent replica.
I don't see a strong motivation for vector clocks. I don't have a clear
migration solution worked out yet, but don't see it as the most pressing
difficulty of the project...
I've seen implies either the first or second. The first is so
non-scalable it's beneath notice, so that's just as well. The second is
possible if you adopt a write-once model where the object ID has the
writer ID as a prefix and objects are immutable once written, but I
haven't seen any mention of that and in any case it leaves open the
question of how to know an object is fully written. In either the
initial-write or the migration case (which is specifically mentioned in
the requirements), it's necessary to define what will happen when
someone at one end of a slow/flaky network connection writes a block and
someone at the far end asks for it while it's still in transit, or what
happens when two nodes on opposite sides of a network partition - i.e.
lacking any means of coordination - attempt to write the same block.
Who blocks? Who fails? Who reconciles conflicts? Lamport clocks and
their relatives do not solve the problem by themselves. They merely
provide information that some other part of the system must use (often
using multiple clock vectors for multiple related pieces of data) to
arrive at a correct result.
> The reason those full database systems you mention
> have all that complicated consistency management is because they
> potentially have multiple writers. With multiple writers, after a
> failure during an update, a consistent view must be created out of the
> mess. With one writer, the worst case that could happen is that *some*
> of the blocks were not written.
This is not something that only happens under failure conditions. In a
*distributed system*, data might be absent locally even if it's present
somewhere else in the system, and an EOF before the actual end of the
file - as when the writer was notified of completion at a clearly prior
time - is incorrect data. The situation's even worse when the data are
being written to multiple destinations with no assurance of order
between them, and I've seen nothing so far that assures order.
> This happens with normal storage in a
> block system all the time during failure and is well tolerated by
> journal filesystems.
Yes, by having a journal that's fully/sequentially/consistently written
before the live filesystem, so that it can be replayed accurately even
if the writes to the live filesystem are interrupted. What do you
propose other nodes should do if they ask for data that's sitting in the
journal of a failed/unreachable node? Would those blocks be unavailable
for either reading or writing until that node comes back up, or do you
propose to implement a global distributed journal with all of the
necessary consistency and ordering to enable recovery? At some point
the hard distributed-system problems have to be solved, not just pushed
into another component.
My model with developing software is a little like blowing into many
balloons. I make a few small balloons, and blow into them and over time
they grow to encompass the problem space I am interested in solving.
The balloon blowing happens in an iterative fashion. I have found most
experienced and/or even high performing engineers are unaware of 80% of
the requirements until they are about 80% done.... What better way to
get to 80% then blow up the balloons. Rather then try to solve every
problem all at once let us focus on the smaller problems we can tackle
to give ourselves a foothold.
Regards
-steve
2:13 p.m.
New subject: Vinzvault consistency?
On 05/10/2010 02:26 PM, Jeff Darcy wrote:
On 05/10/2010 11:38 AM, Steven Dake wrote:
> As there is only one writer in every case, a simple lamport time stamp
> would do the trick.
How is there only one writer? Either there's only one possible writer
globally, there's only one possible writer per object, or you have to
coordinate/reconcile between possible writers - potentially across
sites, despite partitions, etc. Nothing in the very brief description
If I understand the vinzvault project correctly, it will be used to
provide block-level storage to a node, somewhat similar to Amazon's
Elastic Block Storage (EBS).
For that case, each block device will likely have only a single writer:
the kernel/FUSE to which vinzvault is providing storage.
Certainly, one will have multiple writers to -different- storage areas,
but each individual vinzvault storage area would seem to be a
single-client scenario.
Jeff
2:54 p.m.
New subject: Vinzvault consistency?
On Mon, 2010-05-10 at 15:13 -0400, Jeff Garzik wrote:
On 05/10/2010 02:26 PM, Jeff Darcy wrote:
> On 05/10/2010 11:38 AM, Steven Dake wrote:
>> As there is only one writer in every case, a simple lamport time stamp
>> would do the trick.
>
> How is there only one writer? Either there's only one possible writer
> globally, there's only one possible writer per object, or you have to
> coordinate/reconcile between possible writers - potentially across
> sites, despite partitions, etc. Nothing in the very brief description
If I understand the vinzvault project correctly, it will be used to
provide block-level storage to a node, somewhat similar to Amazon's
Elastic Block Storage (EBS).
For that case, each block device will likely have only a single writer:
the kernel/FUSE to which vinzvault is providing storage.
Certainly, one will have multiple writers to -different- storage areas,
but each individual vinzvault storage area would seem to be a
single-client scenario.
Ya thats correct. The one consistency issue I can see occurs during
migration + failure of a node where membership may change at the same
time a new node takes on writing activities. If this occurs, a read
which would have been targeted at position 3, may now be targeted at
position 2, while the write has been replicated to 4, 5, 6 but not 2
yet. In this case, that new node may end up reading an out of sync
replica. I had thought of using LTS for this since its very simple and
I am familiar with the algorithm. Maybe there are other choices. The
D1HT membership algorithm is not immediate and completes in Ologn time
so there is some opportunity for inconsistency in the membership on the
various nodes resulting in a migrated node reading from a different
replica then the main writing replica.
Thinking about migration and membership changes is worthwhile since it
presents the only real challenge I have been able to think up regarding
synchrony of replicas.
Regards
-steve
Jeff
_______________________________________________
vinzvault mailing list
vinzvault(a)lists.fedorahosted.org
https://fedorahosted.org/mailman/listinfo/vinzvault
3:38 p.m.
New subject: Vinzvault consistency?
On 05/10/2010 03:54 PM, Steven Dake wrote:
Ya thats correct. The one consistency issue I can see occurs during
migration + failure of a node where membership may change at the same
time a new node takes on writing activities. If this occurs, a read
which would have been targeted at position 3, may now be targeted at
position 2, while the write has been replicated to 4, 5, 6 but not 2
yet. In this case, that new node may end up reading an out of sync
replica. I had thought of using LTS for this since its very simple and
I am familiar with the algorithm. Maybe there are other choices. The
D1HT membership algorithm is not immediate and completes in Ologn time
so there is some opportunity for inconsistency in the membership on the
various nodes resulting in a migrated node reading from a different
replica then the main writing replica.
I had to deal with this exact issue for CloudFS. Eventually I decided
to make the list of data servers for an object explicit, determined at
creation time and stored as object metadata instead of trying to
recalculate based on current membership. It's just too easy for the
recalculation scheme to yield an incorrect answer, not only when
membership changes but also when there are partitions, when tokens are
reassigned to distribute load, when different objects have different
replication/striping policies, etc. The explicit approach does mean an
extra lookup at open time, but avoids a whole bunch of nasty cases
thereafter and also makes debugging/auditing easier.
3:28 p.m.
New subject: Vinzvault consistency?
On 05/10/2010 03:13 PM, Jeff Garzik wrote:
If I understand the vinzvault project correctly, it will be used to
provide block-level storage to a node, somewhat similar to Amazon's
Elastic Block Storage (EBS).
For that case, each block device will likely have only a single writer:
the kernel/FUSE to which vinzvault is providing storage.
Not only a single writer, then, but no sharing (even for read) between
that writer and anyone else. That certainly does make things simpler.
Is there any plan to implement an overlay/COW scheme as part of
vinzvault so that nodes can share a base object read-only and store
private changes in a per-instance object, or will we rely on the block
layer for that?
3:58 p.m.
New subject: Vinzvault consistency?
On Mon, 2010-05-10 at 16:28 -0400, Jeff Darcy wrote:
On 05/10/2010 03:13 PM, Jeff Garzik wrote:
> If I understand the vinzvault project correctly, it will be used to
> provide block-level storage to a node, somewhat similar to Amazon's
> Elastic Block Storage (EBS).
>
> For that case, each block device will likely have only a single writer:
> the kernel/FUSE to which vinzvault is providing storage.
Not only a single writer, then, but no sharing (even for read) between
that writer and anyone else. That certainly does make things simpler.
Is there any plan to implement an overlay/COW scheme as part of
vinzvault so that nodes can share a base object read-only and store
private changes in a per-instance object, or will we rely on the block
layer for that?
I was thinking 2.0+ for COW and snapshots. Hardest part at this point
is to get a working D1HT that integrates with a DB. A functional D1HT
is probably about 5k lines of C code of pure protocol - so that is quite
a bit of chunk of work to knock out :)
The best way to sum up 1.0 is D1HT where every node participates +
Tokyocabinet + fuse + autotool + basic replica consistency and
correctness. Eg really rough prototype.
Regards
-steve
_______________________________________________
vinzvault mailing list
vinzvault(a)lists.fedorahosted.org
https://fedorahosted.org/mailman/listinfo/vinzvault
5101
days inactive
5101
days old
vinzvault@lists.fedorahosted.org
7 comments
3 participants
participants (3)
-
Jeff Darcy -
Jeff Garzik -
Steven Dake