insideout

README

Insideout

Insideout is a suit of software dedicated to give you the best performances to accomplish one operation, query for the position within one or more polygons:

• is this location in a building ?
• in which city are we in ?
• what timezone ?
• anything where a closed polygon describes a geographical region

This is the opensourced part of a project including ready to serve docker images with embedded pre indexed datasets.

Strategy

Several strategies are available:

• On disk index (more reads) data can be larger than memory
• Inside Tree in memory (fast when a location is inside cover), data can be larger than memory only indexes are in memory
• full s2 index, fastest but huge memory consumption, wait for start since indexation is made on start

These 3 strategies give you enough choices to perform better according to your data.

APIS

Two sets of API are provided:

• one using gRPC

     service Inside {
         //  Stab returns features containing lat lng
         rpc Within(WithinRequest) returns (WithinResponse) {}
         // Get returns a feature by its internal ID and polygon index
         rpc Get(GetRequest) returns (Feature) {}
     }
  

• one basic HTTP /api/within/{lat}/{lng}

Metrics are provided via Prometheus at http://host:httpMetricsPort/metrics.

A debug visual map is available at http://host:httpAPIPort/debug/.

Health status is provided via gRPC host:healthPort or via basic HTTP http://host:httpAPIPort/healthz.

Docker & Kubernetes

Main goal of insideout is to be used with container image with pre embedded indexes, ready to run.

There is a simple demo with preindexed Natural Earth data 110m countries:

docker run --rm -it -p 8080:8080 akhenakh/insideout-demo:latest 

Point your browser onto http://yourip:8080/debug/

Indexer

Tune your index parameters according to your data:
Small sparse buildings should be indexed differently than cities also use stopOnFirstFound if you know only one polygon is encircling a position.

Usage of ./cmd/indexer/indexer:
  -dbPath="inside.db": Database path
  -filePath="": FeatureCollection GeoJSON file to index
  -insideMaxCellsCover=24: Max s2 Cells count for inside cover
  -insideMaxLevelCover=16: Max s2 level for inside cover
  -insideMinLevelCover=10: Min s2 level for inside cover
  -logLevel="INFO": DEBUG|INFO|WARN|ERROR
  -outsideMaxCellsCover=16: Max s2 Cells count for outside cover
  -outsideMaxLevelCover=15: Max s2 level for outside cover
  -outsideMinLevelCover=10: Min s2 level for outside cover
  -warningCellsCover=1000: warning limit cover count

Insided

Usage of ./cmd/insided/insided:
  -cacheCount=200: Features count to cache, 0 to disable the cache
  -dbPath="inside.db": Database path
  -grpcPort=9200: gRPC API port
  -healthPort=6666: grpc health port
  -httpAPIPort=9201: http API port
  -httpMetricsPort=8088: http port
  -logLevel="INFO": DEBUG|INFO|WARN|ERROR
  -stopOnFirstFound=false: Stop in first feature found
  -strategy="db": Strategy to use: insidetree|shapeindex|db

K/V Engines

Different engines have been tested: bbolt, pogreb, badger 1.6, goleveldb.

For Insideout particular load (read only random reads), bbolt is the best performer.

Test with loadtester 10s fr-communes using db engines & insidetree when available:

 ./insided -stopOnFirstFound=true -strategy=db -cacheCount=0 -dbPath=../leveldbindexer/inside.db -dbEngine=leveldb
count 31083 rate mean 3108/s rate1 3110/s 99p 980665
Alloc = 13 MiB  TotalAlloc = 3686 MiB   Sys = 71 MiB    NumGC = 321

./insided -stopOnFirstFound=true -strategy=db -cacheCount=0 -dbPath=../bboltindexer/inside.db -dbEngine=bbolt
count 42190 rate mean 4219/s rate1 4211/s 99p 4760278
Alloc = 1 MiB   TotalAlloc = 3479 MiB   Sys = 71 MiB    NumGC = 1635

./insided -stopOnFirstFound=true -strategy=insidetree -cacheCount=0 -dbPath=../bboltindexer/inside.db -dbEngine=bbolt 
count 42135 rate mean 4214/s rate1 4206/s 99p 2259642
Alloc = 208 MiB TotalAlloc = 3638 MiB   Sys = 411 MiB   NumGC = 29

./insided -stopOnFirstFound=true -strategy=insidetree -cacheCount=0 -dbPath=../leveldbindexer/inside.db -dbEngine=leveldb
count 41021 rate mean 4102/s rate1 4091/s 99p 13443368
Alloc = 390 MiB TotalAlloc = 3441 MiB   Sys = 480 MiB   NumGC = 22

./insided -stopOnFirstFound=true -strategy=insidetree -cacheCount=0 -dbPath=../badgerindexer/inside.db -dbEngine=badger
count 38936 rate mean 3894/s rate1 3874/s 99p 2599252
Alloc = 554 MiB TotalAlloc = 3988 MiB   Sys = 680 MiB   NumGC = 15

./insided -stopOnFirstFound=true -strategy=insidetree -cacheCount=0 -dbPath=../progrebindexer/inside.db -dbEngine=progreb
count 44853 rate mean 4485/s rate1 4476/s 99p 2374910
Alloc = 286 MiB TotalAlloc = 3954 MiB   Sys = 479 MiB   NumGC = 32

Pogreb is faster but does not supports prefix range and consumes a bit more than bbolt.

bbolt is more capable for this load.

Prefiltering

zcat France.geojson.gz| jq '.features[] | select(.properties.admin_level==10)' 

Documentation

Index

• Constants
• func CellKey(id uint32) []byte
• func CellPrefix() byte
• func CellUnionToToken(cu s2.CellUnion) string
• func CellUnionToTokens(cu s2.CellUnion) []string
• func CoordinatesFromLoops(l *s2.Loop) []float64
• func FeatureKey(id uint32) []byte
• func FeaturePrefix() byte
• func GeoJSONCoverCellUnion(f *geojson.Feature, coverer *s2.RegionCoverer, interior bool) ([]s2.CellUnion, error)
• func GeoJSONEncodeLoops(f *geojson.Feature) ([][]byte, error)
• func InfoKey() []byte
• func InsideKey(c s2.CellID) []byte
• func InsideRangeKeys(c s2.CellID) ([]byte, []byte)
• func LoopFromCoordinates(c []float64) *s2.Loop
• func MapKey() []byte
• func OutsideKey(c s2.CellID) []byte
• func OutsideRangeKeys(c s2.CellID) ([]byte, []byte)
• func PropertiesToValues(f *Feature) (map[string]*spb.Value, error)
• func ValueToProperties(src map[string]*spb.Value) map[string]interface{}
• type CellsStorage
• type Feature
• type FeatureIndexResponse
• type FeatureStorage
• type Index
• type IndexInfos
  • func (infos *IndexInfos) String() string
• type IndexResponse
• type MapInfos
• type Store

Constants

const (

	// reserved T & t for tiles
	TilesURLPrefix byte = 't'
	TilesPrefix    byte = 'T'

	InsideTreeStrategy   = "insidetree"
	DBStrategy           = "db"
	ShapeIndexStrategy   = "shapeindex"
	PostgisIndexStrategy = "postgis"
)

Functions

func CellKey

func CellKey(id uint32) []byte

CellKey returns the key for the cell id

func CellPrefix

func CellPrefix() byte

CellPrefix returns the key prefix for cells entry

func CellUnionToToken

func CellUnionToToken(cu s2.CellUnion) string

CellUnionToToken return a comma separated list of tokens

func CellUnionToTokens

func CellUnionToTokens(cu s2.CellUnion) []string

CellUnionToTokens a cell union to a token string list

func CoordinatesFromLoops

func CoordinatesFromLoops(l *s2.Loop) []float64

CoordinatesFromLoops returns []float64 as lng lat adding 1st as last suitable for GeoJSON

func FeatureKey

func FeatureKey(id uint32) []byte

FeatureKey returns the key for the id

func FeaturePrefix

func FeaturePrefix() byte

FeaturePrefix returns the key prefix for features entry

func GeoJSONCoverCellUnion

func GeoJSONCoverCellUnion(f *geojson.Feature, coverer *s2.RegionCoverer, interior bool) ([]s2.CellUnion, error)

GeoJSONCoverCellUnion generates an s2 cover normalized

func GeoJSONEncodeLoops

func GeoJSONEncodeLoops(f *geojson.Feature) ([][]byte, error)

GeoJSONEncodeLoops encodes all MultiPolygons and Polygons as loops []byte

func InfoKey

func InfoKey() []byte

InfoKey returns the key for the info entry

func InsideKey

func InsideKey(c s2.CellID) []byte

func InsideRangeKeys

func InsideRangeKeys(c s2.CellID) ([]byte, []byte)

InsideRangeKeys returns the min and max range keys for c

func LoopFromCoordinates

func LoopFromCoordinates(c []float64) *s2.Loop

LoopFromCoordinates creates a LoopFence from a list of lng lat

func MapKey

func MapKey() []byte

MapKey returns the key for the map entry

func OutsideKey

func OutsideKey(c s2.CellID) []byte

func OutsideRangeKeys

func OutsideRangeKeys(c s2.CellID) ([]byte, []byte)

OutsideRangeKeys returns the min and max range keys for c

func PropertiesToValues

func PropertiesToValues(f *Feature) (map[string]*spb.Value, error)

PropertiesToValues converts feature's properties to protobuf Value

func ValueToProperties

func ValueToProperties(src map[string]*spb.Value) map[string]interface{}

ValueToProperties converts a protobuf Value map to its JSON serializable map equivalent

Types

type CellsStorage

type CellsStorage struct {
	// Cells inside cover
	CellsIn []s2.CellUnion

	// Cells outside cover
	CellsOut []s2.CellUnion
}

CellsStorage are used to store indexed cells for use with the treeindex

type Feature

type Feature struct {
	Loops      []*s2.Loop
	Properties map[string]interface{}
}

Feature representation in memory

type FeatureIndexResponse

type FeatureIndexResponse struct {
	// id of the feature
	ID uint32
	// index of the polygon (in case of multipolygon)
	Pos uint16
}

FeatureIndexResponse a feature response to find back a feature from an index.

type FeatureStorage

type FeatureStorage struct {
	Properties map[string]interface{}

	// Next entries are arrays since a multipolygon may contains multiple loop
	// LoopsBytes encoded with s2 Loop encoder
	LoopsBytes [][]byte
}

FeatureStorage on disk storage of the feature

type Index

type Index interface {
	// Stab returns ids of polygon we are inside and polygons we may be inside
	Stab(lat, lng float64) (IndexResponse, error)
}

Index offers different strategy indexers to speed up queries.

type IndexInfos

type IndexInfos struct {
	Filename       string
	IndexTime      time.Time
	IndexerVersion string
	FeatureCount   uint32
	MinCoverLevel  int
}

IndexInfos used to store information about the index in DB

func (*IndexInfos) String

func (infos *IndexInfos) String() string

type IndexResponse

type IndexResponse struct {
	IDsInside      []FeatureIndexResponse
	IDsMayBeInside []FeatureIndexResponse
}

IndexResponse a response to find back a feature from an index.

type MapInfos

type MapInfos struct {
	CenterLat, CenterLng float64
	MaxZoom              int
	Region               string
	IndexTime            time.Time
}

MapInfos used to store information about the map if any in DB

type Store

type Store interface {
	LoadFeature(id uint32) (*Feature, error)
	LoadAllFeatures(add func(*FeatureStorage, uint32) error) error
	LoadFeaturesCells(add func([]s2.CellUnion, []s2.CellUnion, uint32)) error
	LoadCellStorage(id uint32) (*CellsStorage, error)
	LoadIndexInfos() (*IndexInfos, error)
	LoadMapInfos() (*MapInfos, bool, error)
	StabDB(lat, lng float64, StopOnInsideFound bool) (IndexResponse, error)
	Index(fc geojson.FeatureCollection, icoverer *s2.RegionCoverer, ocoverer *s2.RegionCoverer,
		warningCellsCover int, fileName, version string) error
}