20

I'm in the process of designing a new system for a large geospatial data set that will require rapid read query performance. Therefore I want to see if anyone thinks it is possible or has experience/advice about suitable DBMSs, data structure, or alternative methods to achieve the required performance in the following situation:

Data will be continuously produced from processed satellite radar data, which will have global coverage. Based on the satellite resolution and land coverage of the globe, I estimate the full data set to produce values at 75 billion discrete locations on the globe. Over the life span of a single satellite, the output will produce up to 300 values at each of these locations (so a total data set of >22 trillion values). This is for one satellite, and there is already a second in orbit, with another two planned in the new few years. So there will be a lot of data! A single data item is very simple and will only consist of (longitude, latitude, value), but due to the number of items I estimate a single satellite to produce up to 100TB.

The written data should never need updating, as it will only grow as new satellite acquisitions are processed. Write performance is not important, but read performance is crucial. The goal of this project is to be able to visualize the data through a simple interface such as a layer over google maps, where each point has a colored value based on its average, gradient, or some function over time. (demo at end of post).

From these requirements, the database needs to be scalable and we are likely to look towards cloud solutions. The system needs to be able to deal with geospatial queries such as "points near (lat,lon)" and "points within (box)", and have read performance of < 1s for locating a single point, and polygons which contain up to 50,000 points (although up to 200,000 points would be preferable).

So far I have a test data set of ~750 million data items at 111 million locations. I've trialed a postgres/postGIS instance, which worked OK, but without the possibility of sharding I don't this this will be able to cope as the data grows.I have also trialed a mongoDB instance, which again appears to OK so far, and with sharding it might be sufficient to scale with the data volume. I've recently learnt a little about elasticsearch, so any comments on this would be helpful as it is new to me.

Here is a quick animation of what we want to achieve with the full data set: Tileserver serving visualization of 750 million data items.

This gif (from my postgres trial) is serving (6x3) pre-computed raster tiles, each containing ~200,000 points and taking ~17s to generate each. By clicking a point the graph is made by pulling all historic values at the nearest location in < 1s.

Apologies for the long post, all comments/advice are welcome.

4

You could shard by location. Partition the globe into a grid and have each square in that grid on one server. Since you mentioned cloud, that would be well suited to cloud. Of course your will need to manually merge the results from multiple servers.

That way you can use any database solution your like. It does not need to be scalable on its own.

The individual squares will have different amounts of data. You can use differently sized machines for them (since this is cloud), or you put multiple small shards on the same machine.

This sharding scheme is great for the kind of queries you perform because each query will only need to touch very few shards. Sharding by time is worse because all time shards must be touched for each query. Random sharding has the same problem.

All in all this is an easy sharding case because the query pattern fits the sharding scheme so well.

Actually, I wonder if you need a database at all for this. Maybe you can partition the globe into 1000x1000 tiles or smaller and have one flat file in blob storage for each tile. Blob storage does not mind 1M blobs at all.

Executing a query is conceptually very easy with this storage scheme. You can store the data redundantly in multiple grid resolutions as well.

  • The sharding by region is the approach I have been looking at with MongoDB, and with the timely release of MongoDB Atlas, I am currently leaning in that direction (using pre-computed aggregated values). At the moment I am unsure how many replica/shard servers I would need, so costing may become an issue. Your proposal of using BLOB storage is also interesting, and you are the second person to propose it. However, using BLOBs is completely new to me, so I need to read into it further, any useful sources you know of? Thanks for the response. – Azwok Jul 11 '16 at 9:35
  • Blobs are trivial to use. The complexity will arise from you needing to implement database features such as serialization, queries, transactions, backups, HA, DA. This is all doable but maybe not wise. Maybe you can store the blobs in a Postgres table. That automates all of that except serialization and query. Perf could be better than blob storage and maybe it's even cheaper. Blobs and VMs are not charged by cost, they have a nice margin (proof: my local webhoster charges 3-5x less for the same compute power than cloud does. This implies high cloud margins). – usr Jul 11 '16 at 9:45
  • Note, that you can run multiple shards on the same mongo instance. You can "overshard". That way you can balance the servers out. – usr Jul 11 '16 at 9:48
  • 1
    I'm not sure you need any spatial features at all. You can compute all of that in the app. You just need the ability to query all data for a rectangle. This can be done by manually splitting the globe into a grid (or multiple resolution grids). Your DB does not need to support spatial I think. – usr Jul 11 '16 at 9:49
8

How up-do-date do your read queries need to be?

You could partition the database by time if the map just needs to show the most recent measurement. This would reduce your query load for the map.

For the history of a given point, you could hold a second store by x and y showing the history. This could be done with a nightly refresh/update as the the historical data won't change.

Then you could pre-compute averages at more coarse resolutions for integrating with maps at different zoom levels. This would reduce the number of points to retrieve for large map areas (zoom out). Finer resolutions would be used for more zoomed in maps which were querying smaller areas. If you really need to speed this up you could compute tiles as blobs and interpret them in your application.

Because these would involve some re-computing of aggregate information there would be some latency in query results. Depending on how much latency was acceptable you could use this sort of approach to optimise your reads.

OK, so your points need to be computed averages over time. With this computation I guess your actual queries come down quite a lot from 22 trillion items as the raster values can be pre-calculated for querying.

  • The read queries can have a bit of a delay (a day or two), so batch processing is a valid option. At any given location, a new value will only be added every 6 days at the fastest (the next satellite pass). The output on the map is not just the latest value, it is calculated based on the whole history of values at that location, e.g. it's average, or gradient, or a custom function. For more zoomed out levels, I'm already working on a clustering/pyramid structure so that I will have a table/collection with averaged values so that no tile (query) will have > 200,000 (or 50,000) location items. – Azwok Jul 9 '16 at 11:14
  • I think that pre-calculating aggregates is the key - your temporal calculations can still be batched. This is how OLAP systems get fast query performance and you will probably need to take this sort of approach. Especially relevant if you can live with data that's a day old for your queries. – ConcernedOfTunbridgeWells Jul 9 '16 at 21:36
  • If you are querying calculated average values, how many discrete locations are you taking samples at - i.e. what's the resolution of the actual bitmap at the highest level of zoom? – ConcernedOfTunbridgeWells Jul 9 '16 at 21:40
  • I agree pre-calculated aggregates is looking very likely the way to go. The calculated averages at the highest zoom are not averaged over an area, it is the average of the values over time at 1 location. Only as it zooms out will I have separate tables/collections that will average areas to ensure no query/tile has too many location points within in it (max of 50,000-200,000). The maximum resolution of any tile is 256x256 pixels. – Azwok Jul 11 '16 at 9:15
3

It sounds like there are two classes of query - one to understand which locations lie within the current view window and a second to deliver the desired statistic for those points. My suggestion is to use separate, specialised tools for each.

I'm assuming all measurements relate to the same set of 75Bn points. These lat/longs, once established, are therefore static. They can be grouped, aggregated and indexed at a one-off cost. Therefore I would suggest sharding by region and zoom level. The size of each shard will be driven by the performance that can be achieved from each GIS instance.

The GIS will return a set of points that are passed to a time series database. This holds the measured values and performs aggregates. KDB is one I'm aware of. It targets securities trading, which will have fewer keys but more data points per key than your scenario.

There will be a cost to transferring the key values from the GIS server to the timeseries DB. My hypothesis is that this cost will be paid back by the faster processing in the task-specific timeseries DB. From the wording of the question it seems that a single instance will not be able to hold all data so some cross-server traffic seems inevitable. Given the relative speed of the components it seems likely sending a keyset to a remote server which has the data cached will be faster than reading the data off local disk.

If the point-finding and value-calculation parts can be local to each other then of course I would expect response to be faster. My (limited) understanding is that finding the N closest neighbours to a given point is a non-trivial task. This is why I suggested using specific software to perform it. If the point-finding can be reduced to

where latitude between x1 and x2
and logitude between y1 and y2

then that part could be handled by the value-storing software and the GIS eliminated from the architecture.

I have not implemented such a system. I'm really just thinking out loud here. At the petabyte scale there are no off-the-shelf solutions. There are, however, many satellite data providers so your problem is tractable. Good luck.

  • Agreed, there are two classes. 1) make a picture of the single values from many locations, 2) get all historic values at a location. All measurements are related to the same billions of locations, the only change will be the number of historic values at each point. Sharding by region is the approach I am looking at taking, for the reasons you stated. I hadn't considered passing the returned values into a separate time series DB. I would have thought the selection and transfer into a time series database would add too much time to make that a viable option, unless I misunderstood your proposal. – Azwok Jul 11 '16 at 9:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.