insideout

package module
v0.0.0-...-12b612f Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: Feb 3, 2022 License: Apache-2.0 Imports: 10 Imported by: 0

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

View Source 
const (

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

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

Variables

This section is empty.

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
}

Source Files

View all Source files

Directories

Path Synopsis
cmd
indexer
insidecli
insided
loadtester
quickpostgisload
gen
go/insidesvc/v1
index
dbindex
postgis
shapeindex
treeindex
debug
package debug expose tools to debug insideout indexed geo data
 package debug expose tools to debug insideout indexed geo data
storage
bbolt

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.