03. Redis actual battle: meeting goddess nearby by geo type

It is declared that this document is reproduced in the code byte , Reprint the document only for learning 、 Review for no other purpose  

Old and wet , Read your Skillfully using data types to achieve billion level data statistics after , I learned how to use different data types with ease （String、Hash、List、Set、Sorted Set、HyperLogLog、Bitmap） To solve the statistical problems of different scenarios .

The product manager said he had a idea, For the majority of young boys and girls to provide an opportunity to connect with each other .

So that young men and women in this most beautiful age can be in every Twelve o'clock I can meet that in the park  Ta.

So I want to develop a  App, The user can find the one nearby after logging in  Ta, Connect with each other .

How can I find people nearby ？ I also hope that through this  App Meet the goddess ……

In memory , A night off work , She moved lightly through the crowd , The tall and slim figure is like an elegant note floating in the space . Her eyes are full of clear sunlight and vitality , In her eyes are the stars of the galaxy .

The opening remarks

“

Exercise your ability of expression , Especially at work . A lot of people say 「 Those who work are not as good as those who do PPT Of 」, In fact, the boss is not stupid , Why do they approve more of what they do PPT Of ？

Because they think from the boss's point of view , For him , What is needed is a 「 Solution 」. Think more from the perspective of a Creator , It's not just a programmer's perspective ;

Think more about the value of this thing , instead of 「 How do I achieve it 」. Of course , How to achieve it is a must , But it's usually not the most important .

”

What is facing LBS application

Longitude and latitude is the combined name of longitude and latitude to form a coordinate system . It's also called geographic coordinate system , It is a spherical coordinate system that uses the sphere of three dimensions to define the space on the earth , Can mark any position on the earth （ After the decimal point 7 position , The precision can reach 1 centimeter ）.

The range of longitude is (-180, 180], The range of latitudes stay (-90, 90], Latitude is bounded by the equator , North due south negative , The longitude is plus or minus the prime meridian ( Greenwich Observatory, UK ) As a boundary , The East is positive and the west is negative .

The man near the   That's what they say  LBS (Location Based Services, Location based services ), It's a service around the user's current geographic location data , Provide users with accurate encounter service .

The man near the The core idea is as follows ：

1. With “ I ” Centered , Search for nearby Ta;

2. With “ I ” According to the current geographical location , Figure out others and “ I ” Distance between ;

3. Press “ I ” Sort the distance from others , Filter out the users closest to me .

MySQL Realization

“

Calculation 「 The man near the 」, Calculate other data near this coordinate through a coordinate , Sort by distance , How to start ？

”

user-centric , Given a 1000 Draw a circle with meters as the radius , So the users in the circular area are what we want to meet 「 The man near the 」.

Store latitude and longitude in  MySQL：

CREATE TABLE `nearby_user` (
  `id` int(11) NOT NULL AUTO_INCREMENT,
  `name` varchar(255) DEFAULT NULL COMMENT ' name ',
  `longitude` double DEFAULT NULL COMMENT ' longitude ',
  `latitude` double DEFAULT NULL COMMENT ' latitude ',
  `create_time` datetime DEFAULT NULL ON UPDATE CURRENT_TIMESTAMP COMMENT ' Creation time ',
  PRIMARY KEY (`id`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8mb4;

“

But I can't traverse all of them 「 The goddess 」 Longitude and latitude and their own longitude and latitude data are sorted according to the distance , It's too much calculation .

”

We can filter out the Limited... By region 「 The goddess 」 Coordinate data , Then the data in the rectangular area is calculated by the full distance and sorted again , In this way, the amount of calculation is significantly reduced .

“

How to divide a rectangular area ？

”

A square on the round jacket , According to the user's experience 、 The maximum and minimum of latitude （ the 、 latitude + distance ）, Filter data as a filter , It's very easy to put 「 The goddess 」 Search for information .

“

What about the extra areas ？

”

The extra users in this part of the area , The distance to the dot must be larger than the radius of the circle , Then we calculate the distance between the user center and all users in the square , Filter out all users whose distance is less than or equal to radius , All users in the circular area meet the requirements The man near the .

In order to meet the high-performance rectangular region algorithm , The data table needs to add a composite index to the longitude and latitude coordinates  (longitude, latitude), This maximizes query performance .

actual combat

According to latitude and longitude and distance, the maximum value of the circumscribed rectangle is obtained 、 The minimum latitude and longitude and the distance calculated according to latitude and longitude use a third-party class library ：

<dependency>
     <groupId>com.spatial4j</groupId>
     <artifactId>spatial4j</artifactId>
     <version>0.5</version>
</dependency>

After getting the circumscribed rectangle , Maximum and minimum longitude of rectangle 、 The latitude value searches for users in a square area , Then remove users who exceed the specified distance , It's the ultimate The man near the .

/**
 *  Get around  x  The man of rice 
 *
 * @param distance  Search range   Company km
 * @param userLng   Longitude of current user 
 * @param userLat   The latitude of the current user 
 */
public String nearBySearch(double distance, double userLng, double userLat) {
  //1. Get the outer square 
  Rectangle rectangle = getRectangle(distance, userLng, userLat);
  //2. Get all users in the square 
  List<User> users = userMapper.selectUser(rectangle.getMinX(), rectangle.getMaxX(), rectangle.getMinY(), rectangle.getMaxY());
  //3. Eliminate redundant users whose radius exceeds the specified distance 
  users = users.stream()
    .filter(a -> getDistance(a.getLongitude(), a.getLatitude(), userLng, userLat) <= distance)
    .collect(Collectors.toList());
  return JSON.toJSONString(users);
}

//  Get the bounding rectangle 
private Rectangle getRectangle(double distance, double userLng, double userLat) {
  return spatialContext.getDistCalc()
    .calcBoxByDistFromPt(spatialContext.makePoint(userLng, userLat), 
                         distance * DistanceUtils.KM_TO_DEG, spatialContext, null);
}

     /***
     *  In the sphere , The distance between two points 
     * @param longitude  longitude 1
     * @param latitude   latitude 1
     * @param userLng    longitude 2
     * @param userLat    latitude 2
     * @return  Return distance , Company km
     */
    private double getDistance(Double longitude, Double latitude, double userLng, double userLat) {
        return spatialContext.calcDistance(spatialContext.makePoint(userLng, userLat),
                spatialContext.makePoint(longitude, latitude)) * DistanceUtils.DEG_TO_KM;
    }

Because the ranking of distances between users is implemented in business code , You can see SQL The sentence is also very simple .

SELECT * FROM nearby_user
WHERE 1=1
AND (longitude BETWEEN #{minlng} AND #{maxlng})
AND (latitude BETWEEN #{minlat} AND #{maxlat})

But the performance of database query is limited after all , If 「 The man near the 」 There are a lot of query requests , In the case of high concurrency , This may not be a good solution .

Try Redis Hash failed

Let's analyze it together LBS Characteristics of data ：

1. Every 「 The goddess 」 There is one. ID Number , Every ID Corresponding to latitude and longitude information .

2. 「 Indoorsman 」 land  app obtain 「 Girl heart 」 When ,app according to 「 Indoorsman 」 Look for the nearby 「 The goddess 」.

3. Get the location matching 「 The goddess 」ID After the list , And get it from the database ID Corresponding 「 The goddess 」 The information is returned to the user .

“

The data feature is a goddess （ user ） Corresponding to a set of longitudes and latitudes , It reminds me of Redis Of Hash structure . That's one key（ The goddess ID） Corresponding One value（ Longitude and latitude ）.

”

Hash It looks like it can be done , however LBS In addition to recording longitude and latitude , Also need to Hash Data in the collection for range query , According to the longitude and latitude converted into distance sort .

and Hash The data of the set is out of order , Obviously not desirable .

Sorted Set It's the first time I saw the clue

“

Sorted Set Is the type appropriate ？ Because it can sort .

”

Sorted Set  The type is also a  key Corresponding to one  value,key Element content , and value ` It's the weight fraction of the element .

Sorted Set You can sort elements according to their weight scores , This seems to meet our needs .

such as ,Sorted Set The element is 「 The goddess ID」, The weight of the element score It's latitude and longitude information .

“

The problem is coming. ,Sorted Set The weight value of an element is a floating-point number , Longitude and latitude are longitude 、 Two latitude values , Do how? ？ Can we convert longitude and latitude into a floating point number ？

”

The idea is right , In order to compare longitude and latitude ,Redis Adopt the widely used GeoHash code , Encode longitude and latitude, respectively , Finally, the codes of latitude and longitude are combined into a final code .

In this way, we can convert longitude and latitude into a value , and  Redis Of GEO The underlying data structure of type uses  Sorted Set To achieve .

Let's see  GeoHash  How to encode latitude and longitude .

GEOHash code

“

About GeoHash May refer to ：https://en.wikipedia.org/wiki/Geohash

”

GeoHash The algorithm maps two-dimensional latitude and longitude data to one-dimensional integers , In this way, all elements will be attached to one line , The distance between the two-dimensional coordinates which are close to each other and the points after one-dimensional mapping will also be very close .

When we want to calculate 「 When people are nearby 」, First, map the target location to this line , And then take the nearby points on this one-dimensional line .

GeoHash Encoding encodes a longitude value into a N Binary value of bit , Let's look at the longitude range [-180,180] do N Second partition operation , among N You can customize .

In the first second partition , Longitude range [-180,180] It will be divided into two subintervals ：[-180,0) and [0,180]（ I call it left 、 Right partition ）.

here , We can check whether the longitude value to be encoded falls in the left partition or the right partition . If it falls on the left partition , We will use 0 Express ; If it falls on the right side , Just use 1 Express .

thus , Every time I finish the second partition , We can get it 1 Bit code value （ No 0 Namely 1）.

Then make a second partition for the partition to which the longitude value belongs , At the same time, check again whether the longitude value falls in the left or right partition after the second partition , Do it according to the rules 1 Bit code . When it's done N After the second partition , You can use one for longitude N bit It's the number of .

All map element coordinates will be placed in a unique grid . The smaller the grid is , The more accurate the coordinates are . And then we code these squares as integers , The closer the grid code is, the closer it is .

After coding , The coordinates of each map element will become an integer , This integer can be used to restore the coordinates of the elements , The longer the integer is , The smaller the loss of the restored coordinate value is . about 「 The man near the 」 In terms of this function , A little bit of precision lost is negligible .

For example, the longitude value is equal to  169.99  Conduct 4 Bit code （N = 4, do 4 Subarea ）, Put the longitude between [-180,180] It's divided into left partitions [-180,0) And the right partition [0,180].

1. 169.99 It belongs to the right partition , Use  1  Represents the first partition encoding ;

2. then 169.99 After the first division of belonging to [0, 180] The interval continues to be divided into [0, 90) and [90, 180],169.99 Still in the right range , code ‘1’.

3. take [90, 180] It is divided into [90, 135) and [135, 180], This time it's on the left , code ‘0’.

such , In the end, we get a 4 Bit code .

And latitude is encoded in the same way as longitude , I won't repeat .

Merge latitude and longitude codes

If the calculated longitude and latitude codes are respectively  11011 and 00101`, Target code No 0 The position is from longitude 0 The value of a 1 As the target value , The second part of the target code 1 From latitude to latitude 0 A value 0 As the target value , And so on ：

That's it , Longitude and latitude （35.679,114.020） You can use  1010011011  Express , And this value can be used as  SortedSet  The weight value of the realization of sorting .

Redis GEO Realization

“

GEO The type is the course of latitude and longitude GeoHash The combined value of the encoding is taken as Sorted Set Elemental score The weight ,Redis Of GEO What are the instructions ？

”

We need to land app The girl of ID And the corresponding latitude and longitude Sorted Set Inside .

more GEO The type instruction can refer to ：https://redis.io/commands#geo

GEOADD

Redis Provides  GEOADD key longitude latitude member  command , Combine a set of latitude and longitude information with the corresponding 「 The goddess ID」 It was recorded that GEO In a collection of types , as follows ： Record multiple users at a time （ Sora Aoi 、 Yui Hatano ） The latitude and longitude information of .

GEOADD girl:localtion 13.361389 38.115556 " Sora Aoi " 15.087269 37.502669 " Yui Hatano "

GEORADIUS

“

I landed app, Get your own latitude and longitude information , How to find other users within a certain range centered on this latitude and longitude ？

”

Redis GEO Types provide  GEORADIUS Instructions ： According to the longitude and latitude position input , Find other elements within a certain range centered on this latitude and longitude .

Suppose your latitude and longitude are （15.087269 37.502669）, Need to get near 10 km Of 「 The goddess 」 And return it to LBS application ：

GEORADIUS girl:locations 15.087269 37.502669 km ASC COUNT 10

ASC It can make 「 The goddess 」 The information is sorted according to the latitude and longitude of the distance .

COUNT The option specifies the returned 「 The goddess 」 Number , Prevent too much around 「 The goddess 」, Save bandwidth resources .

If you feel like you need more goddesses , Then there's no limit , But you need to pay attention to your body , Eat more eggs .

“

After the user goes offline , Such as deleting offline 「 The goddess 」 Longitude and latitude ？

”

That's a good question ,GEO  The type is based on  Sorted Set  Realized , So you can borrow  ZREM  Command to delete geographic location information .

For example, delete 「 Sora Aoi 」 Location information for ：

ZREM girl:localtion " Sora Aoi "

Summary

GEO It doesn't design a new underlying data structure , It's direct use Sorted Set Collection types .

GEO Type used GeoHash The coding method realizes the transformation from longitude and latitude to Sorted Set The conversion of element weight fraction in , Two of the key mechanisms are interval division of two-dimensional maps , And coding intervals .

A set of longitudes and latitudes fall behind an interval , It's represented by the coding value of the interval , And take the encoded value as Sorted Set The weight fraction of the element .

In a map application , Car data 、 Restaurant data 、 There could be millions of human data , If you use Redis Of Geo data structure , They will all be in one zset Collection .

stay Redis In the cluster environment , Collections may migrate from one node to another , If single key The data is too large , It will have a great impact on the migration of the cluster , Single... In a clustered environment key The corresponding amount of data should not exceed 1M, Otherwise, the cluster migration will be stuck , Affect the normal operation of online services .

therefore , Here's the advice Geo Using separate Redis Cluster instance deployment .

If the amount of data is over 100 million or more , You need to be right about Geo Split the data , Split by country 、 Split by province , Split by market , In a city with a large population, it can even be divided into districts .

This can significantly reduce the number of individual zset The size of the collection .