Shulou(Shulou.com)05/31 Report--

This article is about how Redis implements the "people in the neighborhood" function. The editor thinks it is very practical, so share it with you as a reference and follow the editor to have a look.

For the application scenarios of "nearby people" in the field of location services, common DB spatial indexes such as PG, MySQL and MongoDB can be used to implement. On the other hand, Redis, combined with its ordered queue zset and geohash coding, realizes the spatial search function and has a very high running efficiency. This paper will analyze the principle of the algorithm from the point of view of source code, and calculate the query time complexity.

Operation command

Since Redis 3.2, Redis has provided geolocation-related functions based on geohash and ordered collections.

The Redis Geo module contains the following six commands:

GEOADD: adds the given location object (latitude, longitude, name) to the specified key

GEOPOS: returns the position (longitude and latitude) of all given location objects from within key

GEODIST: returns the distance between two given locations

GEOHASH: returns the Geohash representation of one or more location objects

GEORADIUS: returns all location objects in the target set whose distance from the center does not exceed the given maximum distance, centering on a given latitude and longitude.

GEORADIUSBYMEMBER: returns all location objects whose distance does not exceed the given maximum distance, centered on a given location object.

Among them, the combination of GEOADD and GEORADIUS can realize the basic functions of "increase" and "check" in "people nearby". To achieve the "people nearby" function in Wechat, you can use the GEORADIUSBYMEMBER command directly. Where the "given location object" is the user himself, and the search object is other users. But in essence, GEORADIUSBYMEMBER = GEOPOS + GEORADIUS, that is, first find the user's location, and then search for other user objects nearby that meet the distance condition.

The following will analyze the GEOADD and GEORADIUS commands from the point of view of the source code, and analyze their algorithm principles.

The Redis geo operation contains only "add" and "check" operations, and there is no special "delete" command. This is mainly because ordered sets (zset) are used internally in Redis to save location objects, which can be deleted by zrem.

In the file comments of the Redis source code geo.c, it is only stated that the file is the implementation file of GEOADD, GEORADIUS, and GEORADIUSBYMEMBER (in fact, the other three commands are also implemented). From the side, we can see that the other three commands are auxiliary commands.

GEOADD

Mode of use

GEOADD key longitude latitude member [longitude latitude member...]

Adds the given location object (latitude, longitude, name) to the specified key.

Where key is the name of the collection and member is the object corresponding to the latitude and longitude. In practical application, when there are too many objects to be stored, we can set multiple key (such as a province and a key) to do sharding to the object set in disguise, so as to avoid too many single sets.

The return value after successful insertion:

(integer) N

Where N is the number of successful inserts.

Source code analysis

/ * GEOADD key long lat name [long2 lat2 name2... LongN latN nameN] * / void geoaddCommand (client * c) {/ / Parameter check / * Check arguments number for sanity. * / if ((c-> argc-2)% 3! = 0) {/ * Need an odd number of arguments if we got this far... * / addReplyError (c, "syntax error. Try GEOADD key [x1] [y1] [name1] "" [x2] [y2] [name2]... "); return;} / / Parameter extraction Redis int elements = (c-> argc-2) / 3; int argc = 2 elementsextractable 2; / * ZADD key score ele... * / robj* * argv = zcalloc (argc*sizeof (robj*)); argv [0] = createRawStringObject (" zadd ", 4) Argv [1] = c-> argv [1]; / * key * / incrRefCount (argv [1]); / / Parameter traversal + transformation / * Create the argument vector to call ZADD in order to add all * the score,value pairs to the requested zset, where score is actually * an encoded version of lat,long. * / int i; for (I = 0; I

< elements; i++) { double xy[2]; //提取经纬度 if (extractLongLatOrReply(c, (c->

Argv+2) + (iTun3), xy) = = C_ERR) {for (I = 0; I)

< argc; i++) if (argv[i]) decrRefCount(argv[i]); zfree(argv); return; } //将经纬度转换为52位的geohash作为分值 & 提取对象名称 /* Turn the coordinates into the score of the element. */ GeoHashBits hash; geohashEncodeWGS84(xy[0], xy[1], GEO_STEP_MAX, &hash); GeoHashFix52Bits bits = geohashAlign52Bits(hash); robj *score = createObject(OBJ_STRING, sdsfromlonglong(bits)); robj *val = c->

Argv [2colleci3 + 2]; / / set the object element name and score of the ordered collection argv [2+i*2] = score; argv [3+i*2] = val; incrRefCount (val);} / / call the zadd command to store the converted object / * Finally call ZADD that will do the work for us. * / replaceClientCommandVector (cMagar argcMagargv); zaddCommand (c);}

Through the source code analysis, we can see that the Redis uses ordered sets (zset) to save location objects. Each element in the ordered set is an object with location, and the score value of the element is the 52-bit geohash value corresponding to its latitude and longitude.

Double type precision is 52 bits

Geohash is encoded in base32, and 52bits can store up to 10 geohash values, corresponding to a grid with a geographic area size of 0.6 to 0.6 meters. In other words, the position converted by Redis geo will theoretically have an error of about 0.3-1.414-0.424 meters.

Algorithm summary

Summarize what the GEOADD command has done:

1. Parameter extraction and verification

2. Convert input longitude and latitude to 52-bit geohash value (score)

3. Call the ZADD command to store the member and its corresponding score in the collection key.

GEORADIUS

Mode of use

GEORADIUS key longitude latitude radius m | km | ft | mi [WITHCOORD] [WITHDIST] [WITHHASH] [ASC | DESC] [COUNT count] [STORE key] [STORedisT key]

Returns all location objects in the target set whose distance from the center does not exceed the given maximum distance, centering on a given latitude and longitude.

Range: M | km | ft | mi-- > meters | kilometers | feet | miles

Additional parameters:

-WITHDIST: returns the distance between the location object and the center as well as the location object. The unit of distance is consistent with the range unit given by the user.

-WITHCOORD: returns the longitude and dimension of the location object as well.

-WITHHASH: returns the ordered set score of the location object encoded by the original geohash as a 52-bit signed integer. This option is mainly used for underlying applications or debugging, but it is not very useful in practice.

-ASC | DESC: return location object elements from near to far | return location object elements from far to near.

-COUNT count: select the first N matching location object elements. (if not set, all elements are returned)

-STORE key: saves the geolocation information of the returned result to the specified key.

-STORedisT key: saves the distance of the returned result from the center point to the specified key.

Due to the existence of STORE and STORedisT options, GEORADIUS and GEORADIUSBYMEMBER commands are technically marked as write commands, so only the primary instance is queried (written). When the QPS is too high, it is easy to cause excessive read and write pressure on the primary instance.

To solve this problem, two read-only commands, GEORADIUS_RO and GEORADIUSBYMEMBER_RO, are added to Redis 3.2.10 and Redis 4.0.0, respectively.

The returned value after a successful query:

Return a member list without WITH qualification, such as:

["member1", "member2", "member3"]

With WITH qualification, each member in member list is also a nested list, such as:

[[member1 ", distance1, [longitude1, latitude1]] [" member2 ", distance2, [longitude2, latitude2]

Source code analysis

The source code of this section is long. If you can't read it, you can read the Chinese notes directly, or skip to the summary section.

/ * GEORADIUS key x y radius unit [WITHDIST] [WITHHASH] [WITHCOORD] [ASC | DESC] * [COUNT count] [STORE key] [STORedisT key] * GEORADIUSBYMEMBER key member radius unit. Options. * / void georadiusGeneric (client * c, int flags) {robj * key = c-> argv [1]; robj * storekey = NULL; int stoRedist = 0; / * 0 for STORE, 1 for STORedisT. * / / get the ordered set robj * zobj = NULL; if ((zobj = lookupKeyReadOrReply (c, key, shared.null [c-> resp])) = = NULL | | checkType (c, zobj, OBJ_ZSET) {return;} / / confirm the center point longitude and latitude int base_args; double xy [2] = {0} according to the user input (longitude and latitude / member); if (flags & RADIUS_COORDS) {. } / / get query range distance double radius_meters = 0, conversion = 1; if ((radius_meters = extractDistanceOrReply (c, c-> argv + base_args-2, & conversion))

< 0) { return; }//获取可选参数 （withdist、withhash、withcoords、sort、count） int withdist = 0, withhash = 0, withcoords = 0; int sort = SORT_NONE; long long count = 0; if (c->

Argc > base_args) {...} / / get STORE and STORedisT parameters if (storekey & & (withdist | | withhash | | withcoords)) {addReplyError (c, "STORE option in GEORADIUS is not compatible with"WITHDIST, WITHHASH and WITHCOORDS options"); return;} / / set sorting if (count! = 0 & & sort = = SORT_NONE) sort = SORT_ASC / / use the center point and radius to calculate the target area range GeoHashRadius georadius = geohashGetAreasByRadiusWGS84 (xy [0], xy [1], radius_meters); / / A pair of center points and eight geohash grid areas around it are searched to find the element objects in the range geoArray * ga = geoArrayCreate (); membersOfAllNeighbors (zobj, georadius, xy [0], xy [1], radius_meters, ga); / unmatched return / * If no matching results, the user gets an empty reply. * / if (ga- > used = = 0 & & storekey = = NULL) {addReplyNull (c); geoArrayFree (ga); return;} / / some return values are set and returned. GeoArrayFree (ga);}

There are two core steps in the above code, one is to "calculate the range of the center point", and the other is to "find the center point and its eight geohash grid areas around it." The corresponding functions are geohashGetAreasByRadiusWGS84 and membersOfAllNeighbors. Let's look at it in turn:

Calculate the center point range:

/ / geohash_helper.cGeoHashRadius geohashGetAreasByRadiusWGS84 (double longitude, double latitude, double radius_meters) {return geohashGetAreasByRadius (longitude, latitude, radius_meters);} / return 9 geohashBoxGeoHashRadius geohashGetAreasByRadius (double longitude, double latitude, double radius_meters) {/ / some parameter settings GeoHashRange long_range, lat_range; GeoHashRadius radius; GeoHashBits hash; GeoHashNeighbors neighbors; GeoHashArea area; double min_lon, max_lon, min_lat, max_lat that can cover the target area Double bounds [4]; int steps;// calculates the longitude and latitude range of the outer rectangle of the target area (the target area is a circle centered on the target longitude and latitude and the radius is a specified distance) geohashBoundingBox (longitude, latitude, radius_meters, bounds); min_lon = bounds [0]; min_lat = bounds [1]; max_lon = bounds [2]; max_lat = bounds [3] / / calculate the geohash precision (bits) of nine search boxes with query according to the latitude and radius of the central point of the target area / / latitude is mainly used here to adjust the accuracy (higher latitude, smaller digits) steps = geohashEstimateStepsByRadius (radius_meters,latitude); / / set the maximum and minimum longitude and latitude:-180encoding = = OBJ_ENCODING_SKIPLIST) {zset * zs = zobj- > ptr; zskiplist * zsl = zs- > zsl ZskiplistNode * ln;// gets the first element in the range of hashBox (jump table data structure, efficiency comparable to binary search tree), and returns 0 if ((ln = zslFirstInRange (zsl, & range)) = = NULL) {/ * Nothing exists starting at our min. No results. * / return 0;} / / traverse the collection while (ln) {sds ele = ln- > ele;// from the first element, break / * Abort when the node is no longer in range if the traversal element is out of the range range. * / if (! zslValueLteMax (ln- > score, & range)) break;// element check (calculating the distance between the element and the center point) ele = sdsdup (ele); if (geoAppendIfWithinRadius (ga,lon,lat,radius,ln- > score,ele) = = C_ERR) sdsfree (ele); ln = ln- > level [0] .forward;} return ga- > used-origincount } int geoAppendIfWithinRadius (geoArray * ga, double lon, double lat, double radius, double score, sds member) {double distance, xy [2]; / / Decoding error, return error if (! decodeGeohash (score,xy)) return Clearer; / * Can't decode. * / / final distance check (calculate spherical distance distance to see if it is less than radius) if (! geohashGetDistanceIfInRadiusWGS84 (lon,lat, xy [0], xy [1], radius, & distance) {return ClearErr;} / / build and return elements geoPoint * gp = geoArrayAppend (ga); gp- > longitude = xy [0]; gp- > latitude = xy [1]; gp- > dist = distance; gp- > member = member Gp- > score = score; return paid OK;}

Algorithm summary

Leaving aside the many optional parameters, let's briefly summarize how the GEORADIUS command uses geohash to obtain the target location object:

1. Parameter extraction and verification

2. Calculate the range of the area to be checked by using the center point and the input radius. This range parameter includes the highest geohash grid level (accuracy) that meets the conditions and the corresponding nine grid positions that can cover the target area; (more on this later)

3. Traverse the Nine Palace grid and select the location object according to the scope box of each geohash grid. Further find out the object whose distance from the center point is less than the input radius and return it.

A simple demonstration of the algorithm is given through the following two pictures:

Make the center of the left image as the search center, the green circle area as the target area, all the points as the location objects to be searched, and the red dots as the location objects that meet the conditions.

In the actual search, the geohash grid level (that is, the grid size level in the right picture) will be calculated according to the search radius, and the location of the ninth palace grid (that is, the red nine palace grid location information) will be determined; then the distance between the points in the nine palace grid (blue and red dots) and the center point will be found and calculated in turn, and finally the points within the distance range (red dots) will be screened out.

Algorithm analysis

Why do you use this algorithm strategy for query, or what are the advantages of this strategy?

Why find the highest geohash grid level that meets the criteria? Why use the Nine Palace grid? This is actually a problem, which is essentially a preliminary screening of all element objects. In a multi-tier geohash grid, each low-level geohash grid is made up of four higher-level grids (see figure).

In other words, the higher the geohash grid level, the smaller the geographic coverage. When we calculate the highest level of the Nine Palace Grid (grid) that can cover the target area based on the input radius and the location of the center point, we have screened out the extra elements of the Nine Palace. The main reason why we use the Nine Palace grid instead of a single grid is to avoid the boundary situation and narrow the query area as much as possible. Imagine taking 0 latitude and longitude as the center, even if you check the range of 1 meter, you have to check the whole region of the earth if a single grid is covered. Expanding around in eight directions can effectively avoid this problem.

How do I select element objects through the scope box of the geohash grid? How efficient is it?

First of all, the geohash values in each geohash grid are continuous and have a fixed range. So just find out the location object in that range in the ordered set. The following is the skip table data structure of an ordered collection:

It has the query efficiency similar to the binary search tree, and the average operation time complexity is O (log (N)). And all the elements at the bottom are arranged in order in the form of a linked list. So when querying, as long as you find the first value in the collection that is in the target geohash grid, and then compare it in turn, you don't have to look it up many times. The nine grid can not be checked together, and the reason for traversing one by one is that the corresponding geohash values of each grid are not continuous. Only when it is continuous, the query efficiency will be high, otherwise it will have to do a lot of distance operations.

To sum up, the detailed process of "GEOADD" and "GEORADIUS" in Redis Geo module is analyzed from the point of view of source code. The function of finding people nearby by GEORADIUS in Redis can be calculated, and the time complexity is O (N+log (M)), where N is the number of location elements within a specified radius, and M is the number of elements surrounded by the ninth grid to calculate the distance. Combined with the memory-based storage characteristics of Redis, it has a very high running efficiency in the process of practical use.

Thank you for reading! This is the end of this article on "how to achieve the" function of people around Redis ". I hope the above content can be of some help to you, so that you can learn more knowledge. if you think the article is good, you can share it for more people to see!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.