[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