[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