[mapguide-internals] RFC required for tile caching changes?
Paul Spencer
pspencer at dmsolutions.ca
Mon Jan 15 20:03:32 EST 2007
Walt,
I don't believe it got documented. I spoke with Steve Lime (cc'd)
directly about this during OSGeo.
At the time, I believe Steve suggested label placement would be done
before features are clipped for rendering. I believe the way
mapserver works, it grabs all features that intersect a given bbox
then clips the features to the bbox then renders them. Labelling is
currently done post-clip. If it were done pre-clip, then labels
would be in a fixed position and could overlap tile boundaries
without problems.
I do believe that there were some potential problems with this
approach, but I don't know enough of mapserver internals to remember
what they were.
Steve, perhaps you could jump in and fix my explanation? Also, do
you think that label rendering changes would be a potential for
version 5?
Cheers
Paul
On 15-Jan-07, at 2:54 PM, Walt Welton-Lair wrote:
> "In lieu of fixing this in MapServer (there is actually a proposal
> to fix this)..."
>
> Paul - is there per chance a public link to this proposal? I'd be
> interested in looking at it.
>
> Thanks,
> Walt
>
> -----Original Message-----
> From: mapguide-internals-bounces at lists.osgeo.org on behalf of Paul
> Spencer (External)
> Sent: Mon 1/15/2007 7:40 PM
> To: MapGuide Internals Mail List
> Cc:
> Subject: Re: [mapguide-internals] RFC required for tile caching
> changes?
>
>
>
> Trevor,
>
> I don't think I got my idea across clearly :) Let me explain a
> little more clearly.
>
> In ka-Map, the size of a tile is configurable and by default is
> 200x200 px. There is a second concept that I've called a 'meta
> tile'. A meta tile is some number of tiles wide x high, typically 10
> x 10. When a request for a tile comes to the tile server, it checks
> the cache.
>
> If the tile exists, the tile (200x200px) is returned. This happens
> without invoking any map rendering ... the tile exists as an image on
> disk.
>
> If the tile does not exist, then a map render happens. A map the
> size of the meta tile is rendered and sliced into tile-sized chunks
> that are stored on disk in the cache directory structure. While the
> tiles are being created, a lock file is used to 'pause' requests for
> tiles in the same meta-tile directory so that they can all be served
> from the same map draw when it is finished.
>
> We chose this approach for several reasons. First, MapServer suffers
> from edge effects when rendering map images. This is normally not
> noticeable, but when you put several map draws together in a tiled
> client, it becomes horribly obvious. The solution was to render a
> slightly larger map image (about 10 pixels in fact) and clip out the
> center as the tile. Second, MapServer labelling only considers the
> current map draw. Depending on the size of the rendered label, it
> may not fit into a single tile. Depending on the size of a feature,
> the label may appear on several adjacent tiles. In lieu of fixing
> this in MapServer (there is actually a proposal to fix this),
> rendering a much larger map and slicing it into smaller tiles
> produces a reasonable effect. Finally, it is relatively expensive to
> parse the map file and find/read the data compared to rendering so
> rendering a single large image and slicing it is cheaper than
> rendering each smaller tile (with diminishing returns).
>
> I don't know how you actually render the tiles in MapGuide, but I
> don't think you suffer from the same edge and label issues.
>
> The ka-Map directory structure looks something like this:
>
> <map>/<layer-group>/<scale>/<row-of-metatile>/<col-of-metatile>/<row-
> of-tile><col-of-tile>.<ext>
>
> ... which is similar to Chris' suggestion :) I don't get the
> impression that you render the entire contents of the metatile
> directory in one go though. Because I do, I only have to check if
> the meta-tile directory exists to know if any tile in the directory
> exists, which is a small optimizatin.
>
> One difference between Chris' proposal and the way ka-Map works is
> that the scale and layer group are reversed. This makes it
> theoretically possible to share the <layer-group> cache directory
> between different maps simply by creating symlinks or by allowing a
> per-layer-group setting that indicates the root directory to keep the
> tile cache in.
>
> Cheers
>
> Paul
>
> On 15-Jan-07, at 11:49 AM, Trevor Wekel wrote:
>
> > Hi everyone,
> >
> > I did some analysis on file systems a little while ago in support
> > of the
> > directory structure change. Here are some approximate numbers for
> > directory entry and file system entries that I pulled from an
> internet
> > search:
> >
> > Linux ext3 - each file or directory is approx 8 bytes + length of
> > file
> > or directory name
> > Linux Reiserfs - each file or directory is 18 bytes + length of
> > file or
> > directory name
> >
> > If we assume each file name has a format of R99999_C99999.PNG then
> > each
> > file entry will require 26 bytes under ext3 and 34 bytes under
> > ReiserFS.
> >
> > To facilitate fast directory access, tiles which are close to each
> > other
> > should like in the same directory. This reduces the directory
> entry
> > reads for each tile request. If we also assume that the read block
> > size
> > for the file system is 32kbytes (32/64k is often used in RAID
> arrays)
> > then a directory with 900 entries (30x30 block) will get read in a
> > single IOP (900*34 = 30600). And since the tiles are blocked
> > together,
> > it is very likely that adjacent tiles will fall within the same
> > directory. Since the directory was just read, it will be cached
> and
> > there will be no disk access required.
> >
> > If we increase the size of the directories to more than 900 entries
> > then
> > we will incur more than IOP to read the bottom-most directory
> > structure.
> >
> > I also think Traian's suggestion of Base Layer Group/
> 30/60/3_4.png is
> > reasonable. It is more readable than the original mod scheme.
> >
> >> From a rendering perspective, dealing with 2000x2000 pixel blocks
> >> may be
> > more efficient but cutting the tiles up from these larger images
> will
> > require some computational effort. Rendering the tiles in the same
> > size
> > as requested from the client reduces server load because the HTTP
> > request ends up being simply a file serving operation.
> >
> > With some of the latest optimizations I have been working on,
> MapGuide
> > tile serving speeds using "client-sized" tiles are quite
> respectable.
> > On a machine with a single 3GHz CPU, MapGuide can service more than
> > 100
> > tiles per second assuming the tiles are being served from memory,
> > ie. no
> > disk access. The additional computational effort required to
> generate
> > "client" tiles from larger pixel blocks will significantly impact
> > performance.
> >
> >
> > Thanks,
> > Trevor
> >
> > -----Original Message-----
> > From: mapguide-internals-bounces at lists.osgeo.org
> > [mailto:mapguide-internals-bounces at lists.osgeo.org] On Behalf Of
> Paul
> > Spencer (External)
> > Sent: Sunday, January 14, 2007 11:59 AM
> > To: MapGuide Internals Mail List
> > Subject: Re: [mapguide-internals] RFC required for tile caching
> > changes?
> >
> > FWIW, Traian's suggestion for naming folders based on a mod of r/
> c is
> > essentially the same approach I took with ka-Map (for the same
> reason
> > that Chris brought this up) and it seems to work very well. In ka-
> > Map,
> > tiles are rendered in blocks of about 2000x2000 pixels (tile
> size is
> > configurable but you might get 10 x 10 tiles in a typical
> > configuration) and they would go in one of these sub-
> directories. I
> > think I figured out that this would be enough directories to
> decently
> > cache a pretty large area (say, all of the US) without running into
> > file
> > system limits for most scales.
> >
> > It would be interesting to know the limits on:
> >
> > * files per directory
> > * directories per directory
> > * total number of directories
> > * total number of files
> > * minimum block(?) size in the file system compared to typical size
> > of a
> > tile (wasted space per tile).
> >
> > for various operating systems/file system combinations. I know
> we use
> > ReiserFS because it handles lots of small files better than ext3
> for
> > instance. Knowing some of this might help make the caching system
> > more
> > tunable in different environments.
> >
> > Paul
> >
> > On 13-Jan-07, at 11:09 AM, Traian Stanev wrote:
> >
> >> Can you also give an example for tiles with negative indices?
> >> For example if in the current scheme the tile is -33, -64, what
> would
> >> be the resulting directory path?
> >>
> >> R-2/C-3/-3_-4
> >>
> >> What about tile -1,-1
> >>
> >> Another suggestion I have -- name the folder part of the path
> (30 *
> >> tile index div 30) and then the file part would be (tile index mod
> >> 30).
> >>
> >> So for tile 33,64 the folder would be:
> >>
> >> Base Layer Group/30/60/3_4.png
> >>
> >> And for tile -33,-64 the folder would be:
> >>
> >> Base Layer Group/-30/-60/-3_-4.png
> >>
> >> For tile 1,1, the folder would be:
> >>
> >> Base Layer Group/0/0/1_1.png
> >>
> >> For tile -1,-1 the folder would be:
> >>
> >> Base Layer Group/-0/-0/-1_-1.png
> >>
> >>
> >> It's a little weird around 0, but it allows for arbitrary
> >> groupings of
> >
> >> tiles in folders (they don't have to be 30x30) since the tile
> index
> >> can be computed directly from the file path, by adding the folder
> >> term
> >
> >> to the file path term.
> >>
> >> Also, can you tell us what the problem is with having too many
> images
> >> in one directory? Is it a file system issue? And how many tiles is
> >> the
> >
> >> limit, i.e. why is 30x30 the preferred grouping and not
> 1000x1000 for
> >> example?
> >>
> >> Traian
> >> -----Original Message-----
> >> From: mapguide-internals-bounces at lists.osgeo.org on behalf of
> Jason
> >> Birch
> >> Sent: Fri 1/12/2007 8:57 PM
> >> To: MapGuide Internals Mail List
> >> Cc:
> >> Subject: RE: [mapguide-internals] RFC required for tile caching
> >> changes?
> >>
> >> Can I forward this to the "tiling" list for comment?
> >>
> >>
> >> From: mapguide-internals-bounces at lists.osgeo.org on behalf of
> Chris
> >> Claydon
> >> Sent: Fri 2007-01-12 12:24 PM
> >> To: MapGuide Internals Mail List
> >> Subject: RE: [mapguide-internals] RFC required for tile caching
> >> changes?
> >>
> >> A sample tile location would be as follows:
> >>
> >>
> >> ......\ Repositories\TileCache\Samples_Sheboygan_Maps_Sheboygan\7
> >> \Base
> >> Layer Group\R2\C3\3_4.png
> >>
> >>
> >> The R and C indices correspond to rows and columns where each row
> >> contains 30 tiles vertically and each column contains 30 tiles
> >> horizontally.
> >>
> >>
> >> This indicates that:
> >>
> >>
> >> 1) We're at zoom level 7
> >>
> >> 2) We're in grouped row 2
> >>
> >> 3) We're in grouped column 3
> >>
> >> 4) The tile location within this grouped row/column
> >> combination is (3,4).
> >>
> >>
> >> The R and C indices never take a zero value (to avoid issues with
> >> negative values around the origin), so this tile corresponds to a
> >> location of (33, 64) in the old scheme.
> >>
> >>
> >> I took a quick look at the Tile Map Service Specification, but it
> >> doesn't appear to support the concept of grouping blocks of tiles
> >> into subfolders in its current form. Can you provide more
> >> information on whether this is possible?
> >>
> >>
> >> Chris.
> >>
> >>
> >> _______________________________________________
> >> mapguide-internals mailing list
> >> mapguide-internals at lists.osgeo.org
> >> http://lists.osgeo.org/mailman/listinfo/mapguide-internals
> >
> > +-----------------------------------------------------------------+
> > |Paul Spencer pspencer at dmsolutions.ca |
> > +-----------------------------------------------------------------+
> > |Chief Technology Officer |
> > |DM Solutions Group Inc http://www.dmsolutions.ca/ |
> > +-----------------------------------------------------------------+
> >
> >
> >
> >
> > _______________________________________________
> > mapguide-internals mailing list
> > mapguide-internals at lists.osgeo.org
> > http://lists.osgeo.org/mailman/listinfo/mapguide-internals
> >
> > _______________________________________________
> > mapguide-internals mailing list
> > mapguide-internals at lists.osgeo.org
> > http://lists.osgeo.org/mailman/listinfo/mapguide-internals
>
> +-----------------------------------------------------------------+
> |Paul Spencer pspencer at dmsolutions.ca |
> +-----------------------------------------------------------------+
> |Chief Technology Officer |
> |DM Solutions Group Inc http://www.dmsolutions.ca/ |
> +-----------------------------------------------------------------+
>
>
>
>
> _______________________________________________
> mapguide-internals mailing list
> mapguide-internals at lists.osgeo.org
> http://lists.osgeo.org/mailman/listinfo/mapguide-internals
>
>
> <winmail.dat>
> _______________________________________________
> mapguide-internals mailing list
> mapguide-internals at lists.osgeo.org
> http://lists.osgeo.org/mailman/listinfo/mapguide-internals
+-----------------------------------------------------------------+
|Paul Spencer pspencer at dmsolutions.ca |
+-----------------------------------------------------------------+
|Chief Technology Officer |
|DM Solutions Group Inc http://www.dmsolutions.ca/ |
+-----------------------------------------------------------------+
More information about the mapguide-internals
mailing list