[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