[mapguide-internals] RFC required for tile caching changes?

Walt Welton-Lair walt.welton-lair at autodesk.com
Mon Jan 15 14:54:21 EST 2007


"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
	

-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/ms-tnef
Size: 18498 bytes
Desc: not available
Url : http://lists.osgeo.org/pipermail/mapguide-internals/attachments/20070115/b9fae469/attachment-0001.bin


More information about the mapguide-internals mailing list