<div dir="ltr"><div>Hi Even,</div><div>Thanks for the extensive research you have put into this.</div><div>As a very general remark, this proposal seems to focus on minimizing the bandwidth from the cog storage to the consumer, whereas I'd argue that there are a broad range of usages where the consumer is in the same cloud region as the storage and in that case the transferred bandwidth becomes much less of an issue compared to the number of GET requests sent to the underlying file. That said your proposal does not impede on this remark, I just wanted to point out that in that case I believe a more efficient setup would be to use a larger curl blocksize to include all strile offsets/lengths in a single request.</div><div>A few other remarks inline...</div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Wed, May 29, 2019 at 3:49 PM Even Rouault <<a href="mailto:even.rouault@spatialys.com" target="_blank">even.rouault@spatialys.com</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">Hi,<br>
<br>
I've submitted a PR per <a href="https://github.com/OSGeo/gdal/pull/1600" rel="noreferrer" target="_blank">https://github.com/OSGeo/gdal/pull/1600</a> which <br>
implements the low-level work of below points 4) and 5). To get all benefits, <br>
this requires GDAL to be built against internal libtiff or libtiff master <br>
after <a href="https://gitlab.com/libtiff/libtiff/merge_requests/81" rel="noreferrer" target="_blank">https://gitlab.com/libtiff/libtiff/merge_requests/81</a> and https://<br>
<a href="http://gitlab.com/libtiff/libtiff/merge_requests/82" rel="noreferrer" target="_blank">gitlab.com/libtiff/libtiff/merge_requests/82</a> have been merged. Starting with <br>
libtiff 4.0.11 in which this changes will appear, there won't be any specific <br>
behaviour of building against internal libtiff (currently this is required to <br>
avoid loading the whole tile indexes)<br>
<br>
As I anticipated, reading a single tile from a COG, generated and read with <br>
this PR, now requires just 3 GET range requests: one to get the header and <br>
IFDs (without the tile array indices), one to get the offset of the tile and <br>
its successor, and one to get the tile data. That for images with or without <br>
transparency mask.<br>
<br>
To describe the specific layout of those COG files, I've decided to include a <br>
description of the features used at the beginning of the file, so that <br>
optimized readers (like GDAL) can use them and take shortcuts. I've decided to <br>
include them as ASCII strings "hidden" just after the 8 first bytes of a <br>
ClassicTIFF (or after the 16 first ons for a BigTIFF). That is the first IFD <br>
starts just after those strings. This is completely valid to have 'ghost' <br>
areas like this in a TIFF file, and readers will normally skip over them. So <br>
for a COG file with a transparency mask, those strings will be:<br>
GDAL_STRUCTURAL_METADATA_SIZE=000177 bytes\n<br>
LAYOUT=IFDS_BEFORE_DATA\n<br>
STRILE_ORDER=ROW_MAJOR\n<br>
STRILE_LEADER=SIZE_AS_UINT4\n<br>
STRILE_TRAILER=LAST_4_BYTES_REPEATED\n<br>
KNOWN_INCOMPATIBLE_EDITION=NO\n<br>
MASK_INTERLEAVED_WITH_IMAGERY=YES\n<br>
<br>
For a COG without mask, the last item will not be present of course.<br>
<br>
So it starts with GDAL_STRUCTURAL_METADATA_SIZE=XXXXXX bytes\n where XXXXXX <br>
describes the size of this whole section (starting at the beginning of <br>
GDAL_STRUCTURAL_METADATA_SIZE).<br>
<br>
- LAYOUT=IFDS_BEFORE_DATA: the IFDs are located at the beginning of the file. <br>
GDAL with this PR will also makes sure that the tile index arrays are written <br>
just after the IFDs and before the imagery, so that a first range request of <br>
16 KB will always get all the IFDs<br>
<br>
- STRILE_ORDER=ROW_MAJOR: (strile is a contraction of 'strip or tile') the <br>
data for tiles is written in increasing tile id order. Future enhancements <br>
could possibly implement other layouts, like Z_ORDER or HILBERT_CURVE<br></blockquote><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><br>
- STRILE_LEADER=SIZE_AS_UINT4: each tile data is preceded by 4 bytes, in a <br>
'ghost' area as well, indicating the real tile size (in little endian order). <br>
TileOffset[i] points to the real tile data, that is, just after those 4 bytes. <br>
An optimized reader seeing this metadata item will thus look for TileOffset[i] <br>
and TileOffset[i+1] to deduce it must fetch the data starting at <br>
offset=TileOffset[i] - 4 and of size=TileOffset[i+1]-TileOffset[i]+4. It then <br>
checks the 4 first bytes to see if the size in this leader marker is <br>
consistent with TileOffset[i+1]-TileOffset[i]. When there is no mask, they <br>
should normally be equal (modulo the size taken by STRILE_LEADER and <br>
STRILE_TRAILER). In the case where there is a mask and <br>
MASK_INTERLEAVED_WITH_IMAGERY=YES, then the tile size indicated in the leader <br>
will be < TileOffset[i+1]-TileOffset[i] since the data for the mask will <br>
follow the imagery data (see MASK_INTERLEAVED_WITH_IMAGERY=YES)<br>
<br>
- STRILE_TRAILER=LAST_4_BYTES_REPEATED: just after the tile data, the last 4 <br>
bytes of the tile data are repeated. This is a way if optimized readers to <br>
check that TIFF writers not aware of those optimizations have modified the <br>
TIFF file in a way that breaks the optimizations. If an optimized reader <br>
detects an inconsistency, it then fallback to the regular/slow method if using <br>
TileOffset[i] + TileByteCount[i]. I've hesitated about using something like a <br>
CRC32, but checking for the last 4 bytes is probably sufficient with <br>
compression schemes to detect if STRILE_LEADER is valid.<br>
<br>
- KNOWN_INCOMPATIBLE_EDITION=NO: when a COG is generated this is always <br>
written. If GDAL is then used to modify the COG file, as most of the changes <br>
done on an existing COG file, will break the optimized structure, GDAL will <br>
change this metadata item to KNOWN_INCOMPATIBLE_EDITION=YES, and issue a <br>
warning on writing, and when reopening such file, so that users know they have <br>
'broken' their COG file<br></blockquote><div><br></div><div>Could this one be renamed to COG_VERSION or COG_FLAVOR, which would allow you to have the spec for this metadata evolve over time (e.g. STRILE_ORDER could be left out for now as it only has a single valid value) and still be set to COG_VERSION=INCOMPATIBLE if needed. COG_VERSION should probably become the first member of the metadata string.</div><div> </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">
<br>
- MASK_INTERLEAVED_WITH_IMAGERY=YES: signals that mask data immediately <br>
follows imagery data. So when reading data at offset=TileOffset[i] - 4 and <br>
size=TileOffset[i+1]-TileOffset[i]+4, you'll get a buffer with:<br>
        * leader with imagery tile size (4 bytes)<br>
   * imagery data (starting at TileOffset[i] and of size TileByteCount[i])<br>
   * trailer of imagery (4 bytes)<br>
   * leader with mask tilesize (4 bytes)<br>
   * mask data (starting at mask.TileOffset[i] and of size <br>
mask.TileByteCount[i], but none of them actually need to be read)<br>
   * trailer of mask data (4 bytes)<br>
<br>
One point I hesitated about was how to write those structural metadata. Other <br>
possibilities would have been to include them in the GDAL_METADATA TIFF tag <br>
which contains user visible metadata serialized as XML. But I prefered those <br>
structural details to remain mostly hidden. There are really low level details <br>
not describing the image content. A possibility based on GDAL_METADATA would <br>
have been to use a dedicated metadata domain to hold them, but a utility that <br>
would for example copy TIFF to TIFF could propagate the content of this tag <br>
while not including the needed leader & trailer that would be unknown of it.<br>
One could also have introduced a new (or several) TIFF tag(s) to describe <br>
them, but that would have require to register them and caused warnings to be <br>
emitted when reading them with older GDAL versions. The only drawback I can <br>
think of about the solution I implemented is that if using only libtiff API <br>
those structural metadata cannot be discovered. Let me know if you believe <br>
that this could cause issues and what other solution would be preferred.<br>
<br>
One other thought I had is that we could actually potentially save the reading <br>
of TileOffset[i] and TileOffset[i+1]. For uncompressed data, this would be <br>
trivial since only TileOffset[0] is needed to deduce the location of other <br>
tiles when STRILE_ORDER=ROW_MAJOR. But uncompressed data for COG must not be a <br>
very common use case. For compressed data, we could imagine to take the <br>
maximum compressed size of a tile, which would be written as a new metadata <br>
item, and adding padding to smaller tiles to get to that size. So that would <br>
require doing a first pass to compute that maximum tile size, and then the <br>
real one to write the file, so basically a x2 slowdown on generation. For JPEG <br>
compression, one could imagine to avoid most of that initial pass, by exmining <br>
just a few random samples in the source raster to compute the mean compressed <br>
tile size and its standard deviation, and use that to determine a maximum <br>
compressed tile. It could happen that some tiles would still be larger, in <br>
which case the writer would need to remove the higher frequencies of the tile <br>
data until the compressed data fits in the maximum allowed size. Another <br>
drawback is also potential significant lost space in the file if there a lot <br>
of variations in the compression rate among tiles. The criticity of this <br>
depends on how the file size vs the number of requests is seen as important <br>
(depends on cloud storage fees and use patterns).<br></blockquote><div>I see wasted storage space as important :)</div><div>Another optimization going down a similar road would be to store the uint8/uint (depending on bigtiff or not) offset of the first strile in the IFD description, and then just having to read the short/uint TileByteCounts knowing that each strile is stored consecutively to its predecessor.</div><div><br></div><div>--</div><div>Thomas</div><div><br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">
And we could also potentially save the reading of the header (IFD description) <br>
of the file is the calling code could provide it to the GTiff reader (cases <br>
where it would always read the same COG and so could hardcode its header)<br>
Anyway, those ideas are perhaps unneeded overcomplications and are not part of <br>
my current scheduled tasks, but I wanted to share them in case that seems of <br>
interest to anyone.<br>
<br>
Even<br>
<br>
> <br>
> 4) Optimizations specific to JPEG-compressed imagery (YCbCr color space)<br>
> with a 1-bit transparency channel, to minimize the number of HTTP range<br>
> requests needed to read them.<br>
> As JPEG compression cannot include the transparency information, two TIFF<br>
> IFD have to be created: one for YCbCr, and another one for alpha. Currently<br>
> the COPY_SRC_OVERVIEWS=YES creation option of the GeoTIFF driver separates<br>
> data for all the tiles of the color channels from data for all the tiles of<br>
> the transparency channel. In practice, readers will generally want to<br>
> access, for a same location, to data of both color and transparency<br>
> channels. I will modify the writer to interleave blocks so that color and<br>
> transparency information are contiguous. If COLOR_X_Y designates the tile<br>
> with color information at coordinates X,Y (in tile coordinate space), the<br>
> layout of data in the file will be: COLOR_0_0, TRANSPARENCY_0_0, COLOR_1_0,<br>
> TRANSPARENCY_1_0, etc. The GeoTIFF driver will be improved to fetch<br>
> together the color and transparency channel when such a layout is detected.<br>
> <br>
> A further improvement is to be able to avoid completely to read the<br>
> TileByteCount array of the color channel, and the TileByteCount & TileOffset<br>
> arrays of the transparency channel. The trick is to reserve 4 bytes before<br>
> the start of each COLOR_X_Y tile to indicate its size (those bytes will be<br>
> 'ghost', that is not in the range of data pointed by<br>
> TileByCount&TileOffset). An optimized reader wanting to read tile<br>
> i=Y*nb_tiles_in_width+X will start by reading the offsets of tile i and<br>
> i+1: TileOffset_color[i] and<br>
> TileOffset_color[i+1]. It will then seek to TileOffset_color[i] – 4 and read<br>
> 4 + TileOffset_color[i+1] – TileOffset_color[i] bytes in a buffer. The<br>
> first 4 bytes of this buffer will indicate the number of bytes of the color<br>
> tile, and thus it is possible to deduce the offset and size of the mask<br>
> tile that is located at the end of the buffer. A TIFF metadata item will be<br>
> written to indicate that such layout has been used (with an indication of<br>
> the file size so as to be able to detect if the file has been later be<br>
> altered in a non- optimized way), so that optimized readers can adopt the<br>
> above described behavior. This will require to extend the libtiff interface<br>
> so that the user can directly provide the input buffer to decompress.<br>
> As the file will remain fully TIFF/BIGTIFF compliant, non-optimized readers<br>
> (such as newer GDAL builds against an older external libtiff version, or<br>
> previous GDAL versions) will still be able read it, loading values from the<br>
> 4 arrays instead of just one.<br>
> Note: for other compressions types, a simpler version of the above<br>
> optimization can still be done, by using TileOffset[i] and TileOffset[i+1],<br>
> and saving the read of TileByteCount[i]<br>
> To sum up, with the improvements of this task, once the initial loading of<br>
> metadata has been done, a GDAL ReadBlock(x,y) request will cause only two<br>
> networks range requests: one to read TileOffset[i] and TileOffset[i+1]<br>
> (potentially already cached if neighboring tiles have been previously<br>
> accessed in the same process), and another one to read the imagery (+mask)<br>
> data. Whereas currently, 6 might be needed for JPEG YcbCr+mask.<br>
> <br>
> 5) Optimizing the layout of the header of a COG file<br>
> <br>
> The current layout of the header part of COG file is:<br>
> - TIFF / BigTIFF signature, followed by the offset of the first IFD (Image<br>
> File Directory)<br>
> - IFD of full resolution image, that is the list of the tags and their value<br>
> when it consists of a single numeric value, followed by the offset of the<br>
> next - IFD. Its size is 2 + number_of_tags * 12 + 4 (or 2 + number_of_tags<br>
> * 20 + 8) bytes, so typically 200 bytes maximum<br>
> - Values of TIFF tags that don't fit inline in the IFD directory, such as<br>
> TileOffsets and TileByteCounts arrays and GeoTIFF keys<br>
> - IFD of first overview (typically subsampled by a factor of 2)<br>
> - Values of its tags that don't fit inline<br>
> - ...<br>
> -IFD of last overview<br>
> - Values of its tags that don't fit inline<br>
> <br>
> When the COG file is not too large, the fact of having the TileOffsets and<br>
> TileByteCounts between IFD descriptors is not an issue since they are not<br>
> too large, and most TIFF readers will load their values when opening the<br>
> IFD. But for an optimized reader such as GDAL with internal libtiff support<br>
> (or with external libtiff after the optimization of task 4), loading the<br>
> values of the TileOffsets/TileByteCounts arrays is only needed when<br>
> accessing imagery.<br>
> <br>
> A more efficient layout for network access is :<br>
> - TIFF / BigTIFF signature, followed by the offset of the first IFD<br>
> - IFD of full resolution image, followed by the value of its non-inline<br>
> tags, except  TileOffsets/TileByteCounts<br>
> - IFD of first overview followed by the value of its non-inline tags, except<br>
> - TileOffsets/TileByteCounts<br>
> - IFD of last overview followed by the value of its non-inline tags, except<br>
> TileOffsets/TileByteCounts<br>
> - Values of the TileOffsets/TileByteCounts arrays of IFD of full resolution<br>
> image<br>
> - Values of the TileOffsets/TileByteCounts arrays of IFD of first overview<br>
> - ...<br>
> - Values of the TileOffsets/TileByteCounts arrays of IFD of last overview<br>
> <br>
> With such a structure, the initial reading of 16 KB at the start of the file<br>
> will be able to load the IFD descriptors of all overviews (and masks, which<br>
> are actually interleaved in between when present). So, combined together<br>
> with task 4, a cold read of a tile at any zoom level (ie opening the file +<br>
> tile request) could result in just 3 network range requests: one to get the<br>
> IFD descriptors at the start of the file, one to read the location of the<br>
> tile from the TileOffsets array and one to read the tile data.<br>
> The proposed structure itself is still fully TIFF compliant. The script that<br>
> validates the COG structure will be adapted to accept that new variant of<br>
> the header structure.<br>
<br>
-- <br>
Spatialys - Geospatial professional services<br>
<a href="http://www.spatialys.com" rel="noreferrer" target="_blank">http://www.spatialys.com</a><br>
_______________________________________________<br>
gdal-dev mailing list<br>
<a href="mailto:gdal-dev@lists.osgeo.org" target="_blank">gdal-dev@lists.osgeo.org</a><br>
<a href="https://lists.osgeo.org/mailman/listinfo/gdal-dev" rel="noreferrer" target="_blank">https://lists.osgeo.org/mailman/listinfo/gdal-dev</a></blockquote></div></div>