Are they extents, regions, dessert toppings, or thingies?
All, Our discussion about data forks being one-byte records or a sequenced collection of bytes (or a "file", to use the generic term) confused me. It's also a topic that is fundamental and, so, I don't want to wait for the next call to get a better handle on the topic. What I understood from the call was that some want to view this "data fork" the same as a "record fork", except the records are not variable length, they are always one byte in length. Or, well, at least you get to define it that way. I wasn't enamored of this because it will be manipulated strictly as a file of bytes. No, not the "file" you are thinking of. I mean one of the alternative definitions one could find in a dictionary. Specifically: A line<http://dictionary.reference.com/browse/line> of persons or things arranged one behind another (distinguished from rank<http://dictionary.reference.com/browse/rank>). l'm thinking the "things" are bytes, of course. During the call, this generalization didn't seem to fit well with that use-case. Well, it does by definition but it forces one to map the "file" in a very nasty way, potentially, so I'm thinking "fit" as in natural to work with and practical to implement. To put it another way, it gives rise to an implementation requirement that is very, very ugly. I came to that conclusion because when I view things this way it removes the single-byte limit. It's a "file", yes, but it could be a "file" of two-byte, or any-number-bytes in the record. Which is what our record-fork is all about. Not quite, though. We have no way of manipulating multiple records. In the record-fork, such a thing didn't make sense. None of our use-cases required that. Hmm, except for punch in the record-fork but I'll come back to that. All this gave me pause. I felt that as a concept it was equivalent but practically it was sub-optimal. I was wrong. Not in my conclusion that it "gives rise to an implementation requirement that is very, very ugly" or is "sub-optimal", I was absolutely spot-on about that. What I was wrong about is that we've already crossed that "ugly" bridge. That ugly implementation has already been accepted into our model, since our atomic unit is the byte we are *already* storing extent information for the "data" fork. It's just that we assume one address maps one byte in that fork. Since we've already accepted that (we had to in order to store arbitrarily sized regions, with version information) it is no real pain to add one more field. In this case the new field would be used to indicate that all of the records in the "extent" have the same size. In the "data" fork, in the way I want to think of it, every extent record-length member is set to one. It could be two, though, or it could be millions, or more. Doesn't matter. It still works just fine. In fact ranges of records could even have different record lengths. Everything still works. I just plain don't have a leg to stand on because it's always the client that is defining the semantics, and the view too, that it wishes of the fork and we have already chosen a one-byte atomic unit and, thus, have already accepted the pain. I so lose. Sorry. My bad. This is the second time this week I've had to say that and it's getting really annoying. I'll try harder to "get it" in the future, I promise. I wish I could guarantee success. I can't, but I will try. I would still like to keep the number of calls down to a dull roar. I propose the following changes then: write address, range, recsiz, buf Where address == record-number (or key if you prefer), range == the number of records to write, recsiz == the number of bytes in each record. Note, I haven't specified version. Not because it is absent, only because it's use and meaning is unchanged. It's there, along with other things I don't think are relevant to the discussion at hand. The buffer should be at least range X recsiz bytes in length. If shorter, an error may result or one might store content one did not intend, or, well who knows what but it's not cool. We can't reliably detect this so it's best to just document the result as undefined. Punch is altered similarly. Probe will need to be modified to include the record size and where it now returns a length, it should return the size of the range. Is that just another kind of "length" really? I'm using range is some (vain?) attempt to distinguish it from a length of byes. Unnecessary? I think read is obvious from the description of write, yes? Well, almost. What happens if the requested range of records spans records of different size or includes those "virtual zeros"? I think "virtual zeros" in this case are defined as one-byte records containing zero, so the question can be simplified to just the range of records of different size if we maintain Rob's suggestion that "virtual zeros" are transferred. The server already knows the length of each record and, so, can source the store accurately, depositing bytes into the caller's buffer. The client can, certainly should, know the mapping since it allowed the store, previously. The client *should* know what it is doing because it previously allowed a write operation that stored different sized records in the fork or was careful to just never allow that in the first place. Which allows me to expand Rob's suggestion that we go ahead and "move" the virtual-zeros to we go ahead and "move" the bytes without regard to record size. Which is a little weird, though. We've asked for the record size information and we would be able to *know* it does not match at least some of the records in the region. We *could* return an error? We would be forcing the caller to use different calls for each region it is interested in, if they do not share the same record sizes. We could just move the bytes and let the client figure it out. Maybe define read to require address and byte-count instead of address, range, recsiz? In this case, what do we do if the byte-count doesn't completely map all of the bytes in the records involved? Error? Just move the first few bytes in the last record? I don't think I much like this last redefine read to take different arguments approach since it only changes how the craziness manifests and not whether it manifests. A bunch of questions that are detail. You can reply and we could talk about it on the mailing list or just wit for the next con call. I think I have preferences but not strong ones so I'd like to hear what others think. I hope by taking the time to admit my mistake, apologize, then think (a lot) and propose at least some of the modifications we might need in order to offer a robust solution I've at least partially atoned for my stupidity? In any case, I'll try to be less dense. It's hard though, it really is, I was born stupid. Thanks. --Lee
Hi Lee, Thanks for all of the comments. I don't have much to add on the specific details that you raise, but I thought I would throw my 2c in: I had pushed back on the conceptual merging of record forks and data forks up until now (having one kind of fork that does everything, or even merely describing one in terms of the other) but I'm ready to let it go at this point :) From my point of view, when the dust settles I would just like to be able to show brief examples of how more traditional key/value and read/write calls map to this model as a sanity check. For example, a put(key, value, value_sz) maps to write(key, 1, value_sz, value) in your example API below. If we can do those kinds of common examples when all is said and done, then I will feel comfortable that everything worked out fine. On our end we'll also need to do some exercises to make sure our replication protocol still works as well (because it relies heavily on versioning semantics etc.) but I don't think that part will be a problem. Our _internal_ replication message semantics (between servers) will likely diverge slightly from the system model, but not in any drastic way, and that will be hidden anyhow. Until pondering it this weekend I had also still thought that we needed (at least) a hint to warn the back-end local storage that a given fork would be used for data fork -style (1 byte record) access, just for efficiency reasons. However, if we have writes like you describe below then it isn't really a big deal to store fragments (dessert toppings) with underlying IDB metadata that says "addr, range, recordlen, version" instead of "offset, size, version". In what we have thought of as a data fork, all adjacent records will have the same recordlen so we can merge metadata (describing a big chunk of bytes with a single underlying IDB entry) just like we always have and there is no danger of an explosion of record size information. In fact, if someone happens to write multiple adjacent key/value pairs with matching recordlen > 1 and version, then we can merge those just as well. Overall, this generalization ends up being a win for maintenance in the long run to have not just a similar, but in fact an identical code path for storing byte streams and key/value data. At any rate, I'm basically talking myself into getting on board with this too :) Make some room for me on the bandwagon. -Phil On 03/30/2012 06:26 PM, Ward, Lee wrote:
All,
Our discussion about data forks being one-byte records or a sequenced collection of bytes (or a "file", to use the generic term) confused me. It's also a topic that is fundamental and, so, I don't want to wait for the next call to get a better handle on the topic.
What I understood from the call was that some want to view this "data fork" the same as a "record fork", except the records are not variable length, they are always one byte in length. Or, well, at least you get to define it that way.
I wasn't enamored of this because it will be manipulated strictly as a file of bytes. No, not the "file" you are thinking of. I mean one of the alternative definitions one could find in a dictionary. Specifically:
A line <http://dictionary.reference.com/browse/line>of persons or things arranged one behind another (distinguished from rank <http://dictionary.reference.com/browse/rank>).
l'm thinking the "things" are bytes, of course.
During the call, this generalization didn't seem to fit well with that use-case. Well, it does by definition but it forces one to map the "file" in a very nasty way, potentially, so I'm thinking "fit" as in natural to work with and practical to implement. To put it another way, it gives rise to an implementation requirement that is very, very ugly. I came to that conclusion because when I view things this way it removes the single-byte limit. It's a "file", yes, but it could be a "file" of two-byte, or any-number-bytes in the record. Which is what our record-fork is all about. Not quite, though. We have no way of manipulating multiple records. In the record-fork, such a thing didn't make sense. None of our use-cases required that. Hmm, except for punch in the record-fork but I'll come back to that. All this gave me pause. I felt that as a concept it was equivalent but practically it was sub-optimal.
I was wrong. Not in my conclusion that it "gives rise to an implementation requirement that is very, very ugly" or is "sub-optimal", I was absolutely spot-on about that. What I was wrong about is that we've already crossed that "ugly" bridge. That ugly implementation has already been accepted into our model, since our atomic unit is the byte we are *already* storing extent information for the "data" fork. It's just that we assume one address maps one byte in that fork. Since we've already accepted that (we had to in order to store arbitrarily sized regions, with version information) it is no real pain to add one more field. In this case the new field would be used to indicate that all of the records in the "extent" have the same size. In the "data" fork, in the way I want to think of it, every extent record-length member is set to one. It could be two, though, or it could be millions, or more. Doesn't matter. It still works just fine. In fact ranges of records could even have different record lengths. Everything still works. I just plain don't have a leg to stand on because it's always the client that is defining the semantics, and the view too, that it wishes of the fork and we have already chosen a one-byte atomic unit and, thus, have already accepted the pain. I so lose.
Sorry. My bad. This is the second time this week I've had to say that and it's getting really annoying. I'll try harder to "get it" in the future, I promise. I wish I could guarantee success. I can't, but I will try.
I would still like to keep the number of calls down to a dull roar. I propose the following changes then:
write address, range, recsiz, buf
Where address == record-number (or key if you prefer), range == the number of records to write, recsiz == the number of bytes in each record. Note, I haven't specified version. Not because it is absent, only because it's use and meaning is unchanged. It's there, along with other things I don't think are relevant to the discussion at hand.
The buffer should be at least range X recsiz bytes in length. If shorter, an error may result or one might store content one did not intend, or, well who knows what but it's not cool. We can't reliably detect this so it's best to just document the result as undefined.
Punch is altered similarly.
Probe will need to be modified to include the record size and where it now returns a length, it should return the size of the range. Is that just another kind of "length" really? I'm using range is some (vain?) attempt to distinguish it from a length of byes. Unnecessary?
I think read is obvious from the description of write, yes? Well, almost. What happens if the requested range of records spans records of different size or includes those "virtual zeros"? I think "virtual zeros" in this case are defined as one-byte records containing zero, so the question can be simplified to just the range of records of different size if we maintain Rob's suggestion that "virtual zeros" are transferred. The server already knows the length of each record and, so, can source the store accurately, depositing bytes into the caller's buffer. The client can, certainly should, know the mapping since it allowed the store, previously. The client *should* know what it is doing because it previously allowed a write operation that stored different sized records in the fork or was careful to just never allow that in the first place. Which allows me to expand Rob's suggestion that we go ahead and "move" the virtual-zeros to we go ahead and "move" the bytes without regard to record size.
Which is a little weird, though. We've asked for the record size information and we would be able to *know* it does not match at least some of the records in the region. We *could* return an error? We would be forcing the caller to use different calls for each region it is interested in, if they do not share the same record sizes. We could just move the bytes and let the client figure it out. Maybe define read to require address and byte-count instead of address, range, recsiz? In this case, what do we do if the byte-count doesn't completely map all of the bytes in the records involved? Error? Just move the first few bytes in the last record? I don't think I much like this last redefine read to take different arguments approach since it only changes how the craziness manifests and not whether it manifests.
A bunch of questions that are detail. You can reply and we could talk about it on the mailing list or just wit for the next con call. I think I have preferences but not strong ones so I'd like to hear what others think.
I hope by taking the time to admit my mistake, apologize, then think (a lot) and propose at least some of the modifications we might need in order to offer a robust solution I've at least partially atoned for my stupidity? In any case, I'll try to be less dense. It's hard though, it really is, I was born stupid.
Thanks.
--Lee
_______________________________________________ ASG mailing list [email protected] https://lists.mcs.anl.gov/mailman/listinfo/asg
Lee, thanks for dissecting and working out the details for this. I've looked through the questions we had last week, and doing things this way definitely simplifies the model and removes some confusion about the versioning. Therefore, this might be a good time to revisit the issue we were discussing last Friday: interaction between ranges and operations. I would propose the following: - A read/write/punch operation either succeeds completely or fails completely. - For an operation to succeed, the operation should succeed for every record in the range. - For a conditional to succeed, the condition should apply to every record in the range. - The version number of a non-existent record can be considered to be 0 for the purpose of conditional read/write/punch. Some examples: I'm using 1-byte records in the examples below, but the same should apply to differently sized records. So let's say: [ 2 | 2 | 3 | 2 ] is a range of 4 1 bytes records, where the number indicates the current version. Let's define the key of the first record to be 0 (even though the same would apply if the range started at a different record number). Now, read, write and punch *without specifying a conditional flag* are pretty straight forward. After issuing write (<container,object,fork>, range_start=0, range_len=3, version=1, record_size=1, data) [where data is pointing to a 3 byte buffer], the situation would change to: [ 1 | 1 | 1 | 2 ] Now, if we enable conditional write based on the condition that the version number needs to be higher than the existing version: write (<same>, range_start=0, range_len=3, version=3, if_higher, ... ) (applied to the state as shown above) we would get: [ 3 | 3 | 3 | 2 ] Trying the same operation again would fail (due to 3 not being strictly smaller than 3). write (..., range_start=2, range_len=2, version=3, if_higher, ...) would fail because one of the records in the range does not pass the conditional. The same operation would succeed if record 3 had never been written to or had been reset, since a 'default' or 'missing' record has version 0. Comments? Dries
This makes sense to me. I have a question on the "auto-increment" scenario, though. We talked about a flag that the client can use to have the storage system automatically increment the version number. Do we have any particular rules on what version number the storage system should pick in that case? In Triton it would be convenient to do this: 1) version number = (highest existing version number set anywhere in the object) + 1 Alternatively, one could interpret that flag to mean one of the following: 2) version number = (highest existing version number set in the affected range) + 1 3) version number = for each record: (existing version of record) + 1 // so the resulting versions could actually vary across the range being modified Or even: 4) anything goes as long as a) the write succeeds and b) the version number of each affected record ends up higher than it used to be (leaving it up to the imlementor to pick any of the above according to whatever is most efficient for their implementation) Is there a consensus on this? My vote would be for 4) or 1). -Phil On 04/04/2012 05:59 PM, Dries Kimpe wrote:
Lee, thanks for dissecting and working out the details for this.
I've looked through the questions we had last week, and doing things this way definitely simplifies the model and removes some confusion about the versioning.
Therefore, this might be a good time to revisit the issue we were discussing last Friday: interaction between ranges and operations.
I would propose the following:
- A read/write/punch operation either succeeds completely or fails completely.
- For an operation to succeed, the operation should succeed for every record in the range.
- For a conditional to succeed, the condition should apply to every record in the range.
- The version number of a non-existent record can be considered to be 0 for the purpose of conditional read/write/punch.
Some examples:
I'm using 1-byte records in the examples below, but the same should apply to differently sized records.
So let's say:
[ 2 | 2 | 3 | 2 ]
is a range of 4 1 bytes records, where the number indicates the current version.
Let's define the key of the first record to be 0 (even though the same would apply if the range started at a different record number).
Now, read, write and punch *without specifying a conditional flag* are pretty straight forward.
After issuing
write (<container,object,fork>, range_start=0, range_len=3, version=1, record_size=1, data) [where data is pointing to a 3 byte buffer], the situation would change to:
[ 1 | 1 | 1 | 2 ]
Now, if we enable conditional write based on the condition that the version number needs to be higher than the existing version:
write (<same>, range_start=0, range_len=3, version=3, if_higher, ... ) (applied to the state as shown above) we would get:
[ 3 | 3 | 3 | 2 ]
Trying the same operation again would fail (due to 3 not being strictly smaller than 3).
write (..., range_start=2, range_len=2, version=3, if_higher, ...)
would fail because one of the records in the range does not pass the conditional.
The same operation would succeed if record 3 had never been written to or had been reset, since a 'default' or 'missing' record has version 0.
Comments? Dries
_______________________________________________ ASG mailing list [email protected] https://lists.mcs.anl.gov/mailman/listinfo/asg
participants (3)
-
Dries Kimpe -
Phil Carns -
Ward, Lee