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

Paul Spencer pspencer at dmsolutions.ca
Wed Jan 17 07:21:38 EST 2007


Steve's response bounced from the list, but fortunately reply-to-all  
was still actually sending to everyone so I actually got the  
message ... hint, hint ...

Paul


On 16-Jan-07, at 11:18 PM, Steve Lime wrote:

> Paul: Er, I spent too much time at the Camp-to-Camp beer tap so my
> memory is a bit fuzzy. We talked about several things from pre- 
> computing
> label positions to what you mention below. You are correct in how
> MapServer works. It doesn't have any special "tiled" mode and hence
> considers each tile just as any other map. In a single map context,
> computing label positions post-clip makes sense.
>
> Computing label positions pre-clip would result in a single,  
> consistent
> label position for each feature. For points and polygons that's
> generally
> OK I believe. For linear features the results might not always be
> optimal
> since the clipping often provides a nice means of segmenting long
> features
> so that get labeled multiple times. One could work around that at the
> data level by segmenting long features ahead of time.
>
> I don't believe it would hard to hack MapServer drawing routine
> to do this and someone could test it out. Let me know if interested.
>
> Steve
>
>>>> Paul Spencer <pspencer at dmsolutions.ca> 01/15/07 7:03 PM >>>
> 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/ |
> +-----------------------------------------------------------------+
>
>
>
>
>

+-----------------------------------------------------------------+
|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