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

Paul Spencer pspencer at dmsolutions.ca
Wed Jan 17 12:21:05 EST 2007


:O ok ... I'll stop making noise now and let you get on with it :)  I  
remove any previous objections in the interest of getting things done!

Cheers

Paul

On 17-Jan-07, at 11:08 AM, Robert Bray wrote:

> Hey Paul, I think that is because you explicitly added him, for  
> some weird reason this list is already set to reply to list. The  
> change in question would not have made a difference in this case...
>
> Bob
>
> Paul Spencer wrote:
>> 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/ |
>> +-----------------------------------------------------------------+
>>
>>
>>
>>
>> _______________________________________________
>> 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/ |
+-----------------------------------------------------------------+






More information about the mapguide-internals mailing list