The business scenario

At present, many apps, such as Ele. me, Meituan and wechat, have functions such as nearby stores and nearby people. These functions need to locate people or stores within a specified range according to the latitude and longitude of the current user based on geographical location algorithm.

GeoHash is a commonly used geographic location sorting algorithm in the industry, which is also adopted by Redis. Geo algorithm maps two-dimensional longitude and latitude data to one-dimensional integers, so that all elements will be hanging on a line, and the distance between points with similar two-dimensional coordinates will be very close after mapping to one-dimensional points.

When you need to find people or stores nearby, first map the target location to this line, and then get the nearby points on this one-dimensional line.

The art of using saber

Geo algorithm treats the whole earth as a two-dimensional plane and divides it into a series of square squares, just like a go board. Coordinates of all map elements are placed in unique squares. The smaller the squares are, the more accurate the coordinates are.

The following image, a square, two knife cut into four small square, and then with 00, 01, 10 and 11 respectively marked four small square, and then continue to proceed cutting, each small square cut out a small square with a 4 bit binary integer, as continue to cut, binary integer is more and more long, precision will be more and more is also high.

After encoding, the coordinates of each map element will become an integer, through which the coordinates of the element can be restored. The longer the integer, the smaller the loss of the restored coordinate value. For the function of nearby things, the loss of precision is negligible.

The above is the two-knife method, but there are other knife methods in real algorithms, and different algorithms end up encoding different integer numbers.

The GeoHash then base32 encodes the resulting integer (0-9, a-z, minus the a, I, L, and O) into a string. In Redis, latitude and longitude are encoded as 52-bit integers, stored in zset, and value is the element’s key. Score is a 52-bit integer value of GeoHash, whereas zset score is a floating-point number that can be stored losslessly for 52-bit integer values.

When using Redis for Geo query, remember that its internal structure is actually just a Zset (skiplist). Other elements near the coordinates can be obtained by sorting the SCORE of zset, and the original coordinates of elements can be obtained by restoring score to coordinate values.

Geo instruction

Redis has seven Geo instructions.

Add/geoadd

The geoAdd directive carries the set name and multiple triples of latitude and longitude names. In the following directive, we add a total of five companies’ latitude and longitude.

127.0.0.1:6379> geoadd company 116.48105 39.996794 juejin

(integer) 1


127.0.0.1:6379> geoadd company 116.514203 39.905409 ireader

(integer) 1

127.0.0.1:6379> geoadd company 116.489033 40.007669 meituan

(integer) 1

127.0.0.1:6379> geoadd company 116.562108 39.787602 jd 116.334255 40.027400 xiaomi

(integer) 2

Copy the code

Distance/geodist

The Geodist directive can be used to calculate the distance between two elements, carrying the set name, two unit names, and units of distance (which can be m, km, ML, and ft) representing meters, kilometers, miles, and feet, respectively.

127.0.0.1:6379> Geodist Company Juejin ireader km "10.5501" 127.0.0.1:6379> Geodist Company Juejin meituan km "1.3878" Geodist Company Juejin Meituan M "1387.8166"Copy the code

Get element locations/geopos

The GeopOS directive can obtain the latitude and longitude coordinates of any element in a collection, more than one at a time.

The latitude and longitude geoadded to geopOS and the coordinates derived from GeopOS are slightly incorrect because GeoHash’s one-dimensional mapping of two-dimensional coordinates is lossy.

The value that is restored from the mapping has a small margin of error, which is acceptable for the function of nearby things.

Geopos company juejin 1) 1) "116.48104995489120483" 2 Geopos company meituan 1) 1) 1) "geopos company meituan 1) 1)" 1) "116.48903220891952515" 2) "40.00766997707732031" 2) "116.48104995489120483" 2) "39.99679348858259686"Copy the code

Gets the element hash value/geoHash

The GeoHash retrieves the element’s latitude and longitude encoded string, which can be used to locate the element directly at geohash.org/${hash}.

127.0.0.1:6379> geohash company juejin

1) "wx4gd94yjn0"

127.0.0.1:6379> geohash company meituan

1) "wx4gdg0tx40"

Copy the code

Nearby companies/Georadiusbymember

Georadiusbymember is used to query other elements near the specified element.

# Up to 3 elements within 20km are aligned according to distance. 127.0.0.1:6379> Georadiusbymember Company juejin 20 km count 3 ASC 1) "juejin" 2) "meituan" 3) "ireaderCopy the code

# Up to 3 elements are inverted by distance within 20km. 127.0.0.1:6379> Georadiusbymember Company juejin 20 km count 3 desc 1) "xiaomi" 2) "ireader" 3) "meituan"Copy the code

Withcoord, withdist, and hash 127.0.0.1:6379> GeoradiusBymember Company juejin 20 km Withcoord withdist Withhash count 3 desc 1) 1) "xiaomi" 2) "12.9606" 3) (integer) 4069880904286516 4) 1) "116.33425265550613403" 2) "40.02740024658161389" 2) 1) "iReader" 2) "10.5501" 3) (INTEGER) 4069886008361398 4) 1) "116.5142020583152771" 2) "39.90540918662494363" 3) 1) "meituan" 2) "1.3878" 3) (INTEGER) 4069887179083478 4) 1) "116.48903220891952515" 2) "40.00766997707732031"Copy the code

georadius

Georadius can pick up other elements, such as nearby cars, restaurants and people, based on latitude and longitude.

Georadius Company 116.514202 39.905409 20 km withdist Count 3 desc 1) 1) "JD" 2) "13.7269" 2) 1) "meituan" 2) "11.5748" 3) 1) "juejin" 2) "10.5501Copy the code

delete

The storage of Geo in Redis is ZSet, so it can be deleted directly through ZREM.

Matters needing attention

Since the nature of Geo is ZSet, when the amount of data is relatively large, millions of millions of data, in the redis cluster environment, the set may migrate from one node to another.

If the data of a single ZSet is too large, the migration of the cluster will be greatly affected. In a cluster environment, the data amount corresponding to a single key should not exceed 1MB. Otherwise, the migration of the cluster will lag and the running of online services will be affected.

It is recommended that Geo data be deployed in an independent Redis instance instead of a cluster environment to avoid the preceding problems.

If the data volume is over 100 million or even larger, the Geo data needs to be split by country, province, city and district to reduce the size of a single ZSet.