object_store: full HTTP range support #5222

clbarnes · 2023-12-18T15:18:36Z

Support suffix and offset ranges in GetOptions and get_opts
Ensure that, if a range is requested, the response contains exactly that range

Which issue does this PR close?

Closes #4611 . Supercedes #5206 .

Rationale for this change

Motivated by fetching file suffixes without needing 2 requests to find the length first.

What changes are included in this PR?

Add utility struct GetRange which represents bounded ranges, offsets, and suffixes
BREAKING: GetOptions now stores a GetRange rather than a Range
Implementations of ObjectStore are updated with these changes

Are there any user-facing changes?

GetOptions::range is now a crate::utils::GetRange rather than a std::ops::Range<usize>. It implements From<RangeBounds<usize>> so this simply means adding .into() to current code.

There are some additional error cases which previously went undetected if a server didn't return exactly the requested range.

Open questions

LocalFileSystem is a special-case store whose get_opts returns a whole file which then must be sliced using the GetResult::range. Other stores return a response containing only the requested bytes, with the range returned only for informational purposes. There is currently little need for users to deal with this complexity as get_range(s) handles it internally, but this PR may guide more users towards having to do so.

There are a bunch of utilities in the GetRange impl and associated free functions which seemed like they could be useful but are not currently used, and could be deleted for simplicity.

- Support suffix and offset ranges in GetOptions and get_opts - Ensure that, if a range is requested, the response contains exactly that range

tustvold

Broadly speaking I like where this is headed, nice work 👍

seemed like they could be useful but are not currently used, and could be deleted for simplicity.

I think my preference would be to keep the scope of this change down, we can always add methods down the line, removing them is much harder 😄

object_store/Cargo.toml

object_store/src/local.rs

object_store/src/util.rs

Xuanwo · 2023-12-27T13:13:58Z

A quick note: some storage services like azblob don't support suffix range like bytes: -1024, we need to return a correct error in this case.

clbarnes · 2024-01-02T14:57:14Z

A quick note: some storage services like azblob don't support suffix range like bytes: -1024, we need to return a correct error in this case.

Yes, we mentioned azure's lack of support for this in the linked issue. This method has a default implementation of making 2 requests: one to find the length and one to get the suffix, which is then overridden in all of the stores which directly support suffix requests.

Xuanwo · 2024-01-02T15:10:48Z

Yes, we mentioned azure's lack of support for this in the linked issue. This method has a default implementation of making 2 requests: one to find the length and one to get the suffix, which is then overridden in all of the stores which directly support suffix requests.

Great, seems fine 👍

tustvold · 2024-01-02T15:12:05Z

This method has a default implementation of making 2 requests: one to find the length and one to get the suffix, which is then overridden in all of the stores which directly support suffix requests

As we're now making a breaking change to support this use-case, I think I would prefer us to return a NotImplemented error in such cases. This is consistent with what we do for preconditions, etc...

clbarnes · 2024-01-02T15:51:19Z

I would prefer us to return a NotImplemented error

Is it also the case with preconditions that it's possible to get that information in an inefficient way, and we choose not to? I'm just thinking about the zarr use case where we want to use object_store so that we can write a library which is generic over the users' stores. If we don't build in the (inefficient) fallback behaviour, then all library authors wanting to make use of generic stores will have to do a lot of re-implementing that exact behaviour with matches on the response and make 3 requests (one to fail, one to get the length, one to actually get the range). An error is the current behaviour (but returned by the server rather than on our side).

tustvold · 2024-01-02T15:58:27Z

If we don't build in the (inefficient) fallback behaviour, then all library authors wanting to make use of generic stores will have to do a lot of re-implementing

The aim of this crate is to be faithful to the APIs exposed by the object stores themselves, and I therefore think returning an error for something that isn't supported by the store is the correct thing to do. Yes workloads that wish to use suffix ranges against any store will have to do more work to support this, and will need to ascertain how it is they wish to achieve this, even if the solution is just to not use suffix ranges and to ensure they always have the object sizes on hand.

FWIW this is the approach that DataFusion takes, and aligns with the fact catalogs store object sizes as these are important for correctly optimizing queries.

Edit: perhaps we could make the fallback configurable and disabled by default 🤔

- Use idiomatic snafu error handling - fast-fail on azure suffix requests - remove unused GetRange utilities

clbarnes · 2024-01-02T17:34:37Z

Implemented all requested changes. For azure, I've checked whether a suffix was requested and then failed before sending the request. It would be valid to just send the suffix request, as the response will trigger an error anyway, and then it would immediately start working if/when microsoft pulls their socks up and implements it, but the error wouldn't be as informative and it would be slower.

tustvold · 2024-01-02T17:44:00Z

It would be valid to just send the suffix request, as the response will trigger an error anyway, and then it would immediately start working if/when microsoft pulls their socks up and implements it, but the error wouldn't be as informative and it would be slower.

Makes sense, I suspect we would need to update the API version anyway for this to work if they added support for this.

Implemented all requested changes

It is EOD for me here, but I'll take a look first thing tomorrow

tustvold

I think this is almost ready to go, I pushed some commits to cleanup some stuff, I think the only question concerns if Display for GetRange should also include the bytes = ?

object_store/src/util.rs

tustvold · 2024-01-03T13:21:17Z

It would appear this is falling foul of #5272

object_store/src/util.rs

Co-authored-by: Raphael Taylor-Davies <1781103+tustvold@users.noreply.github.com>

tustvold · 2024-01-03T21:16:38Z

@clbarnes Ok I have now gotten this updated to the point where CI passes, could you perhaps take a look and check the changes I've made make sense

tustvold · 2024-01-04T09:17:07Z

The only query I had was no longer explicitly checking for StartTooLarge in the GetRange::Bounded::as_range

I removed this because given an object of size x a range of x..x would erroneously fail it.

clbarnes · 2024-01-04T09:23:02Z

I think that should fail a StartTooLarge? Byte indices are zero-based, so trying to get the byte with index 100 from a resource which is 100 bytes long is indeed starting after the end of the resource. The other off-by-one was a hangover from when I stored the right-inclusive bounds.

I'll suggest another couple of changes along those lines.

tustvold · 2024-01-04T09:28:07Z

Interestingly the spec has the following to say

A client can limit the number of bytes requested without knowing the size of the selected representation. If the last-pos value is absent, or if the value is greater than or equal to the current length of the representation data, the byte range is interpreted as the remainder of the representation (i.e., the server replaces the value of last-pos with a value that is one less than the current length of the selected representation).

Which would imply that the logic in this PR is still overly strict

clbarnes · 2024-01-04T09:29:38Z

Ah, because I'm the author it doesn't let me suggest changes, it just puts them right in.

Self::Bounded(r) => {
                if r.end < r.start {

should be a <= because otherwise you're requesting a 0-length range, which is almost certainly not what the user intends.

            Self::Offset(o) => {
                if *o > len {

should also be a >= because the index of the last byte is len-1, so the byte at index len is also after the end of the resource.

tustvold · 2024-01-04T09:30:48Z

should be a <= because otherwise you're requesting a 0-length range, which is almost certainly not what the user intends.

These were changed because they were resulting in failures of existing tests, running against actual object stores.

clbarnes · 2024-01-04T09:34:56Z

Which would imply that the logic in this PR is still overly strict

True! If we want to allow the EndTooLarge case then we also need to update the GetRange::as_range logic to just clamp the last value.

These were changed because they were resulting in failures of existing tests, running against actual object stores.

What it's running against shouldn't matter, should it? As it just catches a few extra cases where where we have requested the wrong thing. It's just a case of whether we want to allow 0-length requests, and whether we want to allow a range where the first byte is after the end of the resource. Are those tests fuzzed or are we explicitly making such requests in the tests?

tustvold · 2024-01-04T09:37:02Z

What it's running against shouldn't matter, should it?

My point was we shouldn't break things that currently work, regardless of opinions on their relative correctness 😄

We should therefore establish what exactly the current behaviour is and look to preserve that, perhaps you might be able to look into this, as I am not likely to have time today, and I intend to cut the release tomorrow.

clbarnes · 2024-01-04T09:42:39Z

I think both should result in a 416 RangeNotSatisfiable, because in one the offset exceeds the resource length, and in the other a std::ops::Range of 10..10 turns into a header of Range: bytes=10..9, which should also not be satisfiable. I can look into this - thanks for all your help pushing this over the line!

- Raise an error before the request is made if the range has <= 0 bytes in it - `GetRange::as_range` now handles more out-of-bounds cases, although in most cases these should result in a 416 from the server anyway.

clbarnes · 2024-01-04T11:09:31Z

Would it be possible to allow the workflows on this PR to run without approval? As the failing tests are dependent on complex and possibly secret CI setup.

Which would imply that the logic in this PR is still overly strict

I think it's OK to be more strict than the HTTP spec on this check, because as_range is only used to compare that we got the range that we requested, as a user is likely to want to then act on the data as if it were the range that they requested. If they request a 100-byte range, and then the server returns a 50-byte range, the user will want to know about it up front even if it's technically permissible. If the user didn't care how long the response was, they could use an offset. We already treat get_range in a rust-y way rather than an HTTP-y way (using a right-exclusive range object); the rust behaviour is to error if the right bound is beyond the end of the indexed object.

tustvold · 2024-01-04T11:16:34Z

Would it be possible to allow the workflows on this PR to run without approval

It doesn't require approvals once you have had code merged, I'm not sure there is a way to turn it off, it's Github enforced IIRC to stop bitcoin miners

If they request a 100-byte range, and then the server returns a 50-byte range, the user will want to know about it up front even if it's technically permissible

So long as this is what it currently does that sounds fine to me

clbarnes · 2024-01-04T11:35:10Z

The tests which were failing were all tests written as part of this PR, as far as I can tell. I think there were a couple of places where the errors' fields were ambiguously named and so some of them were the wrong way round, so I've improved the names and updated the tests for the new, stricter failure cases.

users cannot request a 0-byte range
as_range should raise an error if the first byte requested is after the end of the resource, but in practice this should never be hit because the server will return a 416 Range Not Satisfiable and that error should bubble up first.
as_range raises an error if the user requests a range ending after the end of the resource, even though the server will 206 Partial Content and return the valid part of the requested range. This is to behave more like rust slicing and let the user know early if they are requesting beyond the length of the resource. The downside is that this disallows users implementing their own paginated requests, like "I want to request 100 bytes at a time and if I get < 100 back I'll stop", but I think this is a pretty rare case which should probably fetch the resource length with a HEAD first.

tustvold · 2024-01-04T11:37:05Z

but I think this is a pretty rare case

Does this case currently work, as if it doesn't that would be a pretty compelling argument for "it doesn't matter".

clbarnes · 2024-01-04T13:51:17Z

It currently works in that the server returns some bytes, but it doesn't return the range of bytes which the user requested, and then the reported GetResult::range is incorrect. So if we want the returned bytes to match the returned Range, we need to change something either way. Either

Raise an error
- Implemented here
- Pro: consistent with cases where a requested range cannot be satisfied, e.g. 416
- Pro: consistent with cases where a user uses a Range to slice into a resource that isn't as long as they thought it was
- Pro: matches the the GetResult::Range from the current implementation
- Con: maybe the user wanted whatever bytes are there up to a certain maximum, rather than exactly what they requested; throws away those bytes
Return the bytes from the response and change GetResult::range to reflect the actual bytes returned
- Would be a ~1 statement change (plus test updates)
- Pro: doesn't throw away whatever bytes are actually returned
- Pro: the bytes returned matches the current implementation
- Con: users have to find the intersection between what they wanted and what they got every time they request a range

The middle ground would be to return an error, but have it contain the GetResult with the actual range. However, this might need to be represented at the top of the crate::Error so it could easily be matched on.

tustvold · 2024-01-04T14:15:59Z

I think the use-case of "give me up to the first 100 bytes" is a perfectly valid use-case, and is even called out in the HTTP spec. I therefore don't think we can/should break this if it is currently supported. We should also add additional tests for this, if they don't already exist.

consistent with cases where a user uses a Range to slice into a resource

Although one could argue the lack of support for zero-length ranges also breaks this 😅

users have to find the intersection between what they wanted and what they got every time they request a range

Only if they don't know the size of the object they are requesting data from, otherwise the behaviour is no different from master? Sure an API could return less, much like it could also return gibberish, at some point you just have to trust that the servers implement the spec correctly

clbarnes · 2024-01-04T14:36:59Z

I think the use-case of "give me up to the first 100 bytes" is a perfectly valid use-case

Got it, I'll see if I can get that done this afternoon.

Although one could argue the lack of support for zero-length ranges also breaks this 😅

True, although there is no way to express "return a zero-length slice of bytes" in the HTTP spec because it's right-inclusive. We could bodge it with a HEAD request to fill out the ObjectMeta and then an empty Bytes but that's highly unlikely to be what the user wanted.

tustvold · 2024-01-04T14:40:51Z

Thank you, sorry to go back and forth on this, but whenever I've assumed "nobody could possibly rely on this", I'm proven wrong and everyone then has a bad day 😅

clbarnes · 2024-01-04T15:05:57Z

Relevant xkcd, of course!

That's now implemented and tested, and the docs for get_range have been expanded to note the error cases and how to get the actual output range if you need it.

tustvold · 2024-01-04T16:08:33Z

I took the liberty of pushing e20b130 which makes some minor copy tweaks and also loosens the suffix restrictions. Aside from following the spec, this is important for suffix requests to be useful for systems, such as when dealing with parquet, where the exact footer size isn't necessarily known ahead of time and instead a guess is made.

Edit: updating the tests

tustvold · 2024-01-04T16:20:57Z

object_store/src/memory.rs

-                        (start..len, entry.data.slice(start..len))
-                    }
-                }
+                let r = range.as_range(entry.data.len()).context(RangeSnafu)?;


It seemed simpler to just have this logic in one place, as opposed to duplicating it

tustvold

I think this is now good go, unless you have any objections

Spoke too soon...

tustvold

Right I think we are finally good to go 😅

I'll merge this tomorrow morning in case anyone has any further comments

clbarnes · 2024-01-04T19:54:31Z

Yes, this looks good to me! Thank you so much for your patience and willingness to wade into this.

joroKr21 · 2024-04-18T16:36:02Z

object_store/src/util.rs

+    }
+
+    /// Convert to a [`Range`] if valid.
+    pub(crate) fn as_range(&self, len: usize) -> Result<Range<usize>, InvalidGetRange> {


Why not make this public? It looks like this is needed by anyone implementing an ObjectStore

In general we try to keep the public API as small as possible to allow for evolution

object_store: full HTTP range support

2c46bab

- Support suffix and offset ranges in GetOptions and get_opts - Ensure that, if a range is requested, the response contains exactly that range

github-actions bot added the object-store Object Store Interface label Dec 18, 2023

tustvold mentioned this pull request Dec 19, 2023

object_store: suffix requests #5206

Closed

tustvold reviewed Dec 19, 2023

View reviewed changes

tustvold added the api-change Changes to the arrow API label Dec 19, 2023

tustvold mentioned this pull request Dec 19, 2023

Release Object Store 0.9.0 #5224

Closed

object_store: review comments

9845874

- Use idiomatic snafu error handling - fast-fail on azure suffix requests - remove unused GetRange utilities

tustvold added 2 commits January 3, 2024 13:12

Cleanup

e6b3dba

Further cleanup / fixes

c5c6b6e

tustvold reviewed Jan 3, 2024

View reviewed changes

object_store/src/util.rs Show resolved Hide resolved

object_store/src/util.rs Outdated Show resolved Hide resolved

clbarnes mentioned this pull request Jan 3, 2024

ObjectStore::get_opts Incorrectly Returns Response Size not Object Size #5272

Closed

object_store: Display for GetRange includes bytes=

5787724

clbarnes force-pushed the httpsuff branch from aade898 to 5787724 Compare January 3, 2024 14:36

tustvold reviewed Jan 3, 2024

View reviewed changes

object_store/src/util.rs Outdated Show resolved Hide resolved

clbarnes and others added 6 commits January 3, 2024 16:30

Update object_store/src/util.rs

5b2ed72

Co-authored-by: Raphael Taylor-Davies <1781103+tustvold@users.noreply.github.com>

Merge remote-tracking branch 'upstream/master' into httpsuff

ec4731f

Use size from ContentRange

2de9d0f

Update test

a4c58dd

Fix as_range

b61a64d

Update test

dd62314

Tighten range validation logic

f61befc

- Raise an error before the request is made if the range has <= 0 bytes in it - `GetRange::as_range` now handles more out-of-bounds cases, although in most cases these should result in a 416 from the server anyway.

allow return of partial range

f5fcc53

Tweak docs and loosen suffix restrictions

e20b130

tustvold reviewed Jan 4, 2024

View reviewed changes

tustvold previously approved these changes Jan 4, 2024

View reviewed changes

Fix Azure and Memory

7705361

tustvold force-pushed the httpsuff branch from 983dd70 to 7705361 Compare January 4, 2024 16:24

tustvold approved these changes Jan 4, 2024

View reviewed changes

tustvold merged commit 2f5dcdf into apache:master Jan 5, 2024
13 checks passed

joroKr21 reviewed Apr 18, 2024

View reviewed changes

object_store: full HTTP range support #5222

object_store: full HTTP range support #5222

Conversation

clbarnes commented Dec 18, 2023 • edited

Which issue does this PR close?

Rationale for this change

What changes are included in this PR?

Are there any user-facing changes?

Open questions

tustvold left a comment • edited

Choose a reason for hiding this comment

Xuanwo commented Dec 27, 2023

clbarnes commented Jan 2, 2024 • edited

Xuanwo commented Jan 2, 2024

tustvold commented Jan 2, 2024

clbarnes commented Jan 2, 2024

tustvold commented Jan 2, 2024 • edited

clbarnes commented Jan 2, 2024

tustvold commented Jan 2, 2024

tustvold left a comment

Choose a reason for hiding this comment

tustvold commented Jan 3, 2024

tustvold commented Jan 3, 2024

tustvold commented Jan 4, 2024

clbarnes commented Jan 4, 2024

tustvold commented Jan 4, 2024

clbarnes commented Jan 4, 2024

tustvold commented Jan 4, 2024

clbarnes commented Jan 4, 2024

tustvold commented Jan 4, 2024 • edited

clbarnes commented Jan 4, 2024

clbarnes commented Jan 4, 2024

tustvold commented Jan 4, 2024 • edited

clbarnes commented Jan 4, 2024 • edited

tustvold commented Jan 4, 2024

clbarnes commented Jan 4, 2024

tustvold commented Jan 4, 2024 • edited

clbarnes commented Jan 4, 2024

tustvold commented Jan 4, 2024 • edited

clbarnes commented Jan 4, 2024

tustvold commented Jan 4, 2024 • edited

tustvold Jan 4, 2024

Choose a reason for hiding this comment

tustvold left a comment

Choose a reason for hiding this comment

tustvold left a comment

Choose a reason for hiding this comment

clbarnes commented Jan 4, 2024

joroKr21 Apr 18, 2024

Choose a reason for hiding this comment

tustvold Apr 18, 2024

Choose a reason for hiding this comment

clbarnes commented Dec 18, 2023 •

edited

tustvold left a comment •

edited

clbarnes commented Jan 2, 2024 •

edited

tustvold commented Jan 2, 2024 •

edited

tustvold commented Jan 4, 2024 •

edited

tustvold commented Jan 4, 2024 •

edited

clbarnes commented Jan 4, 2024 •

edited

tustvold commented Jan 4, 2024 •

edited

tustvold commented Jan 4, 2024 •

edited

tustvold commented Jan 4, 2024 •

edited