Redis——Redis扩展应用GeoHash原理

阿里云国内75折回扣微信号：monov8

阿里云国际，腾讯云国际，低至75折。AWS 93折免费开户实名账号代冲值优惠多多微信号：monov8 飞机：@monov6

摘要

经纬度是经度与纬度的合称组成一个坐标系统。又称为地理坐标系统，它是一种利用三度空间的球面来定义地球上的空间的球面坐标系统，能够标示地球上的任何一个位置（小数点后7位，精度可以到1厘米）。经度的范围在 (-180, 180]，纬度的范围在(-90, 90]，纬度正负以赤道为界，北正南负，经度正负以本初子午线 (英国格林尼治天文台) 为界，东正西负。附近的人 也就是常说的 LBS (Location Based Services，基于位置服务)，它围绕用户当前地理位置数据而展开的服务，为用户提供精准的邂逅服务。

附近人的核心思想：

以 “我” 为中心，搜索附近的Ta；
以 “我” 当前的地理位置为准，计算出别人和 “我” 之间的距离；
按 “我” 与别人距离的远近排序，筛选出离我最近的用户。

一、基于数据库实现LBS服务

计算附近的人，通过一个坐标计算这个坐标附近的其他数据，按照距离排序，如何下手呢？

以用户为中心，给定一个 1000 米作为半径画圆，那么圆形区域内的用户就是我们想要邂逅的附近的人。将经纬度存储到 MySQL ：

CREATE TABLE `nearby_user` (
  `id` int(11) NOT NULL AUTO_INCREMENT,
  `name` varchar(255) DEFAULT NULL COMMENT '名称',
  `longitude` double DEFAULT NULL COMMENT '经度',
  `latitude` double DEFAULT NULL COMMENT '纬度',
  `create_time` datetime DEFAULT NULL ON UPDATE CURRENT_TIMESTAMP COMMENT '创建时间',
  PRIMARY KEY (`id`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8mb4;

我们可以通过区域来过滤出有限「女神」坐标数据，再对矩形区域内的数据进行全量距离计算再排序，这样计算量明显降低。在圆形外套上一个正方形，根据用户经、纬度的最大最小值（经、纬度 + 距离），作为筛选条件过滤数据，就很容易将正方形内的人信息搜索出来。

多出来的这部分区域内的用户，到圆点的距离一定比圆的半径要大，那么我们就计算用户中心点与正方形内所有用户的距离，筛选出所有距离小于等于半径的用户，圆形区域内的所用户即符合要求的附近的人。为了满足高性能的矩形区域算法，数据表需要在经纬度坐标加上复合索引 (longitude, latitude)，这样可以最大优化查询性能。

Redis——Redis扩展应用GeoHash原理_数据

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

package com.zhuangxiaoyan.springbootredis.geohash;

import com.weicoder.common.U;
import org.locationtech.spatial4j.context.SpatialContext;
import org.locationtech.spatial4j.distance.DistanceUtils;
import org.locationtech.spatial4j.shape.Point;
import org.locationtech.spatial4j.shape.impl.PointImpl;

import javax.xml.crypto.Data;
import java.util.*;

/**
 * @Classname nearBySearch
 * @Description TODO
 * @Date 2022/4/10 11:23
 * @Created by xjl
 */
public class nearBySearch {
    private static SpatialContext spatialContext = SpatialContext.GEO;

    public static void main(String[] args) {
        // 利用数据的来实现的查找附近的人
        // 本人的坐标
        User myaddress=new User(1,"庄小焱",163.25,95.36, new Date());
        Point mypoint = new PointImpl(myaddress.getLatitude(),myaddress.getLongitude(),spatialContext);
        // 查询的所有数据中的所有的数据
        List<User> userlist=new ArrayList<>();
        // 设置新的结果集
        HashMap<User,Double> map=new HashMap<>();
        //然后在分别计算两个点的距离，然后在排序
        for (User user:userlist){
            Point otherpoint = new PointImpl(user.getLatitude(),user.getLongitude(),spatialContext);
            double distance =spatialContext.calcDistance(mypoint,otherpoint)* DistanceUtils.DEG_TO_KM;
            map.put(user,distance);
        }
        // 将map转为的list进行排序
        List<Map.Entry<User, Double>> list = new ArrayList<>(map.entrySet());
        Collections.sort(list, new Comparator<Map.Entry<User, Double>>() {
            @Override
            public int compare(Map.Entry<User, Double> o1, Map.Entry<User, Double> o2) {
                return o1.getValue().compareTo(o2.getValue());
            }
        });
        // 然后在去取这个的最近的多人的结果
        for (Map.Entry s : list)
        {
            System.out.println(((User) s.getKey()).getName()+"--"+s.getValue());
        }
    }
}

二、基于Redis的GEOHash实现LBS服务

但是数据库查询性能毕竟有限，如果「附近的人」查询请求非常多，在高并发场合，这可能并不是一个很好的方案。我们一起分析下 LBS 数据的特点：

每一个位置都有一个 ID 编号，每个ID 对应着经纬度信息。
根据的经纬度查找附近的。
获取到位置符合的位置ID 列表后，再从数据库获取 ID 对应的女神信息返回用户。
数据特点就是一个坐标位置对应着一组经纬度，让我想到了 Redis 的 Hash 结构。也就是一个 key（女神 ID）对应着一个 value（经纬度）。

Redis——Redis扩展应用GeoHash原理_redis_02

Hash看起来好像可以实现，但是 LBS 应用除了记录经纬度以外，还需要对 Hash 集合中的数据进行范围查询，根据经纬度换算成距离排序。而 Hash 集合的数据是无序的，显然不可取。Sorted Set 类型是是否合适呢？因为它可以排序。Sorted Set 类型也是一个 key 对应一个 value，key元素内容，而 value `就是该元素的权重分数。Sorted Set 可以根据元素的权重分数对元素排序，这样看起来就满足我们的需求了。比如，Sorted Set 的元素是位置，元素对应的权重 score 是经纬度信息。

Redis——Redis扩展应用GeoHash原理_spring_03

思路对了，为了实现对经纬度比较，Redis 采用业界广泛使用的 GeoHash 编码，分别对经度和纬度编码，最后再把经纬度各自的编码组合成一个最终编码。这样就实现了将经纬度转换成一个值，而 Redis 的 GEO 类型的底层数据结构用的就是 Sorted Set来实现。

2.1 GEOHash 编码

详细的有关于GeoHash精度相关原理：Geohash精度和原理 - feiquan - 博客园

GeoHash 算法将二维的经纬度数据映射到一维的整数，这样所有的元素都将在挂载到一条线上，距离靠近的二维坐标映射到一维后的点之间距离也会很接近。当我们想要计算附近的人时，首先将目标位置映射到这条线上，然后在这个一维的线上获取附近的点就行了。

GeoHash 编码会把一个经度值编码成一个 N 位的二进制值，我们来对经度范围[-180,180]做 N 次的二分区操作，其中 N 可以自定义。在进行第一次二分区时，经度范围[-180,180]会被分成两个子区间：[-180,0) 和[0,180]（我称之为左、右分区）。此时，我们可以查看一下要编码的经度值落在了左分区还是右分区。如果是落在左分区，我们就用 0 表示；如果落在右分区，就用 1 表示。这样一来，每做完一次二分区，我们就可以得到 1 位编码值（不是0 就是 1）。再对经度值所属的分区再做一次二分区，同时再次查看经度值落在了二分区后的左分区还是右分区，按照刚才的规则再做 1 位编码。当做完 N 次的二分区后，经度值就可以用一个 N bit 的数来表示了。所有的地图元素坐标都将放置于唯一的方格中。方格越小，坐标越精确。然后对这些方格进行整数编码，越是靠近的方格编码越是接近。

编码之后，每个地图元素的坐标都将变成一个整数，通过这个整数可以还原出元素的坐标，整数越长，还原出来的坐标值的损失程度就越小。对于附近的人这个功能而言，损失的一点精确度可以忽略不计。比如对经度值等于 169.99 进行 4 位编码（N = 4，做 4 次分区）,把经度区间[-180,180]分成了左分区[-180,0) 和右分区[0,180]。

169.99 属于右分区，使用 1 表示第一次分区编码；
再将 169.99 经过第一次划分所属的 [0, 180] 区间继续分成 [0, 90) 和 [90, 180]，169.99 依然在右区间，编码 ‘1’。
将[90, 180] 分为[90, 135) 和 [135, 180]，这次落在左分区，编码 ‘0’。

2.2 合并经纬度编码

假如计算的经纬度编码分别是11011和00101，目标编码第 0 位则从经度第 0 位的值 1 作为目标值，目标编码的第 1 位则从纬度第 0 位值 0 作为目标值，以此类推：

Redis——Redis扩展应用GeoHash原理_数据_04

就这样，经纬度（35.679，114.020）就可以使用 1010011011 表示，而这个值就可以作为 SortedSet 的权重值实现排序。

GEO 本身并没有设计新的底层数据结构，而是直接使用了 Sorted Set 集合类型。GEO 类型使用 GeoHash 编码方法实现了经纬度到 Sorted Set 中元素权重分数的转换，这其中的两个关键机制就是对二维地图做区间划分，以及对区间进行编码。GEO 类型是将经纬度的经过 GeoHash 编码的合并值作为 Sorted Set 元素的 score 权重。

一组经纬度落在某个区间后，就用区间的编码值来表示，并把编码值作为 Sorted Set 元素的权重分数。在一个地图应用中，车的数据、餐馆的数据、人的数据可能会有百万千万条，如果使用 Redis 的 Geo 数据结构，它们将全部放在一个 zset 集合中。

在 Redis 的集群环境中，集合可能会从一个节点迁移到另一个节点，如果单个 key 的数据过大，会对集群的迁移工作造成较大的影响，在集群环境中单个 key 对应的数据量不宜超过 1M，否则会导致集群迁移出现卡顿现象，影响线上服务的正常运行。所以，这里建议 Geo 的数据使用单独的 Redis 集群实例部署。如果数据量过亿甚至更大，就需要对 Geo 数据进行拆分，按国家拆分、按省拆分，按市拆分，在人口特大城市甚至可以按区拆分。这样就可以显著降低单个 zset 集合的大小。

2.3 GeoHash实战

Redis 提供了 GEOADD key longitude latitude member 命令，将一组经纬度信息和对应的用户记录到 GEO 类型的集合中，如下：一次记录多个用户的经纬度信息。

GEOADD girl:localtion 13.361389 38.115556 "用户1" 15.087269 37.502669 "用户1"

获取自己的经纬度信息，如何查找以这个经纬度为中心的一定范围内的其他用用户呢？

Redis GEO 类型提供了 GEORADIUS 指令：会根据输入的经纬度位置，查找以这个经纬度为中心的一定范围内的其他元素。

假设自己的经纬度是（15.087269 37.502669），需要获取附近 10 km 的用户并返回给 LBS 应用：

GEORADIUS girl:locations 15.087269 37.502669 km ASC COUNT 10

ASC 可以实现让用户信息按照这个距离自己的经纬度由近到远排序。

COUNT 选项表示指定返回的用户数量，防止附近太多用户，节省带宽资源。

用户下线后，如删除下线的用户经纬度呢？

这个问题问得好，GEO 类型是基于 Sorted Set 实现的，所以可以借用 ZREM 命令实现对地理位置信息的删除。

ZREM girl:localtion "用户1"

package com.zhuangxiaoyan.springbootredis.geohash.controller;

import org.springframework.beans.factory.annotation.Autowired;
import org.springframework.beans.factory.annotation.Value;
import org.springframework.data.geo.Distance;
import org.springframework.data.geo.GeoResults;
import org.springframework.data.geo.Point;
import org.springframework.data.redis.connection.RedisGeoCommands;
import org.springframework.data.redis.core.RedisTemplate;
import org.springframework.web.bind.annotation.RequestMapping;
import org.springframework.web.bind.annotation.RestController;

import java.util.List;

/**
 * @Classname RedisGeoHash
 * @Description
 * @Date 2022/4/10 17:36
 * @Created by xjl
 */
@RestController
public class RedisGeoHash {

    @Autowired
    private RedisTemplate redisTemplate;

    @Value("${spring.redis.geo.key}")
    private String GEO_REDIS_KEY;

    /**
     * @description 增加用户位置
     * @param: null
     * @date: 2022/4/10 17:56
     * @return:
     * @author: xjl
     */
    @RequestMapping("/add/GeoLocation")
    public Long addGeoLocation(String username, double x, double y) {
        try {
            RedisGeoCommands.GeoLocation geoLocation = new RedisGeoCommands.GeoLocation(username, new Point(x, y));
            return redisTemplate.opsForGeo().add(GEO_REDIS_KEY, geoLocation);
        } catch (Exception exception) {
            throw new RuntimeException("addGeoLocation error.", exception);
        }
    }

    /**
     * @description 删除用户位置, GEO实际上放在ZSET结构的数据, 因此可用ZREM删除
     * @param: null
     * @date: 2022/4/10 17:56
     * @return:
     * @author: xjl
     */
    @RequestMapping("/delete/GeoLocation")
    public Long deleteGeoLocation(String username) {
        try {
            return redisTemplate.opsForZSet().remove(GEO_REDIS_KEY, username);
        } catch (Exception exception) {
            throw new RuntimeException("deleteGeoLocation error.", exception);
        }
    }

    /**
     * @description 获取用户位置
     * @param: null
     * @date: 2022/4/10 17:56
     * @return:
     * @author: xjl
     */
    @RequestMapping("/delete/GeoLocation")
    public List<Point> getGeoLocation(String username) {
        try {
            return redisTemplate.opsForGeo().position(GEO_REDIS_KEY, username);
        } catch (Exception e) {
            throw new RuntimeException("getGetLocation error.", e);
        }
    }

    /**
     * @description 计算用户相隔距离
     * @param: null
     * @date: 2022/4/10 17:56
     * @return:
     * @author: xjl
     */
    @RequestMapping("/get/Distance")
    public Distance getDistance(String usernameOne, String usernameTwo, RedisGeoCommands.DistanceUnit unit) {
        try {
            return redisTemplate.opsForGeo().distance(GEO_REDIS_KEY, usernameOne, usernameTwo, unit);
        } catch (Exception e) {
            throw new RuntimeException("getDistance error.", e);
        }
    }

    /**
     * @description 获取某个用户 附近 n个距离单位m 内的附近z个用户
     * @param: null
     * @date: 2022/4/10 17:56
     * @return:
     * @author: xjl
     */
    @RequestMapping("/get/GeoResults")
    public GeoResults<RedisGeoCommands.GeoLocation<Object>> getRadius(String username, int radius
            , RedisGeoCommands.DistanceUnit unit, int limit) {
        try {
            Distance distance = new Distance(radius, unit);
            RedisGeoCommands.GeoRadiusCommandArgs args =
                    RedisGeoCommands.GeoRadiusCommandArgs.newGeoRadiusArgs().includeDistance().includeCoordinates().sortAscending().limit(limit);
            return redisTemplate.opsForGeo().radius(GEO_REDIS_KEY, username, distance, args);
        } catch (Exception e) {
            throw new RuntimeException("getDistance error.", e);
        }
    }
}

三、基于Redis的GEOHash局限问题

Redis——Redis扩展应用GeoHash原理_spring_05

利用GeoHash的与Z阶的曲线的空间曲线填充方式

Redis——Redis扩展应用GeoHash原理_数据_06

数据的存储与检索设计？

二进制编码: 11100 11101 00100 01111 00110 11110 采用的base32编码方式可以得到：wx4g6y

GaoHash编码长度	宽度	高度
6	1.2km	609.4m

1、如果基于base32扩大一个级别的搜索范围，缩短一个字符，实际扩大多少倍?

2、6个字符的geohash编码，全国有多少个网格?数据如何检索?

Redis——Redis扩展应用GeoHash原理_spring_07

Redis——Redis扩展应用GeoHash原理_redis_08

Redis中GeoHash的编码实现

package com.zhuangxiaoyan.springbootredis.geohash.utils;

import java.math.BigDecimal;
import java.util.BitSet;
import java.util.HashMap;

import static java.math.BigDecimal.ROUND_HALF_EVEN;

/**
 * @Classname GEOHashUtils
 * @Description TODO
 * @Date 2022/4/10 19:46
 * @Created by xjl
 */
public class GEOHashUtils {
    static final String ONE = "1";
    static final String ZERO = "0";
    static final String TWO = "2";
    static final String LONGITUDE_MAX = "180";
    static final String LONGITUDE_MIN = "-180";
    static final String LATITUDE_MAX = "90";
    static final String LATITUDE_MIN = "-90";
    static final int BIN_NUM = 26;
    static final int MERGE_BIN_NUM = 26 << 1;

    /**
     * Base32编码的字符串池
     */
    private final static char[] BASE_32_CHARS = {'0', '1', '2', '3', '4', '5', '6', '7', '8',
            '9', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'j', 'k', 'm', 'n', 'p',
            'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z'};

    /**
     * 与十进制值的对应关系
     */
    final static HashMap<Character, Integer> BASE_32_LOOKUP = new HashMap<Character, Integer>();


    static {
        int i = 0;
        for (char c : BASE_32_CHARS) {
            BASE_32_LOOKUP.put(c, i++);
        }
    }

    public static void main(String[] args) {
        String longitude = getBin("116.44381989453123", true);
        System.out.println("longitudebin: " + longitude);
        String latitude = getBin("39.915605367786505", false);
        System.out.println("latitudebin: " + latitude);
        String merge = merge(longitude, latitude);
        System.out.println("mergebin: " + merge);
        String geoHash = base32Encode(merge);
        System.out.println("geohash: " + geoHash);
        double[] doubles = base32Decode(geoHash);
        System.out.println("longitude: " + doubles[0] + ",  latitude: " + doubles[1]);
    }

    /**
     * 经纬度的二进制编码
     */
    private static String getBin(String longitudeOrLatitude, boolean isLongitudeOrLatitude) {
        String min, max;
        if (isLongitudeOrLatitude) {
            max = LONGITUDE_MAX;
            min = LONGITUDE_MIN;
        } else {
            max = LATITUDE_MAX;
            min = LATITUDE_MIN;
        }
        BigDecimal num = new BigDecimal(longitudeOrLatitude);
        BigDecimal two = new BigDecimal(TWO), x, y, z;
        StringBuilder stringBuilder = new StringBuilder();
        if (num.compareTo(new BigDecimal(ZERO)) >= 0) {
            stringBuilder.append(ONE);
            x = new BigDecimal(ZERO);
            y = new BigDecimal(max);
        } else {
            stringBuilder.append(ZERO);
            x = new BigDecimal(min);
            y = new BigDecimal(ZERO);
        }
        z = x.add(y).divide(two);
        for (int i = 1; i < 26; i++) {
            if (num.compareTo(z) >= 0) {
                stringBuilder.append(ONE);
                x = z;
                z = x.add(y).divide(two);
            } else {
                stringBuilder.append(ZERO);
                y = z;
                z = x.add(y).divide(two);
            }
        }
        return stringBuilder.toString();
    }

    /**
     * 合并经纬度的二进制编码
     */
    private static String merge(String longitude, String latitude) {
        StringBuilder stringBuilder = new StringBuilder();
        for (int i = 0; i < BIN_NUM; i++) {
            stringBuilder.append(longitude.charAt(i));
            stringBuilder.append(latitude.charAt(i));
        }
        return stringBuilder.toString();
    }


    /**
     * geohash编码
     */
    public static String base32Encode(String longitudeAndLatitudeBinCode) {
        StringBuilder geohash = new StringBuilder();
        for (int i = 0; i < MERGE_BIN_NUM; ) {
            int j = i;
            String substring;
            if ((i += 5) > MERGE_BIN_NUM) {
                substring = longitudeAndLatitudeBinCode.substring(j, MERGE_BIN_NUM);
            } else {
                substring = longitudeAndLatitudeBinCode.substring(j, i);
            }
            int i1 = Integer.parseInt(substring, 2);
            geohash.append(BASE_32_CHARS[i1]);
        }
        return geohash.toString();
    }

    /**
     * geohash解码
     */
    public static double[] base32Decode(String geohash) {
        StringBuilder buffer = getBin(geohash);
        BitSet lonset = new BitSet();
        BitSet latset = new BitSet();

        //偶数位，经度
        int j = 0;
        for (int i = 0; i < MERGE_BIN_NUM; i += 2) {
            boolean isSet = false;
            if (i < buffer.length()) {
                isSet = buffer.charAt(i) == '1';
            }
            lonset.set(j++, isSet);
        }

        //奇数位，纬度
        j = 0;
        for (int i = 1; i < MERGE_BIN_NUM; i += 2) {
            boolean isSet = false;
            if (i < buffer.length()) {
                isSet = buffer.charAt(i) == '1';
            }
            latset.set(j++, isSet);
        }

        double lon = base32Decode(lonset, new BigDecimal(LONGITUDE_MIN), new BigDecimal(LONGITUDE_MAX));
        double lat = base32Decode(latset, new BigDecimal(LATITUDE_MIN), new BigDecimal(LATITUDE_MAX));

        return new double[]{lon, lat};
    }

    private static StringBuilder getBin(String geohash) {
        StringBuilder buffer = new StringBuilder();
        for (char c : geohash.toCharArray()) {
            int i = BASE_32_LOOKUP.get(c) + 32;
            buffer.append(Integer.toString(i, 2).substring(1));
        }
        return buffer;
    }


    private static double base32Decode(BitSet bs, BigDecimal floor, BigDecimal ceiling) {
        BigDecimal two = new BigDecimal(TWO);
        BigDecimal mid = new BigDecimal(ZERO);
        for (int i = 0; i < bs.length(); i++) {
            mid = (floor.add(ceiling).divide(two, 17, ROUND_HALF_EVEN));
            if (bs.get(i)) {
                floor = mid;
            } else {
                ceiling = mid;
            }
        }
        return mid.doubleValue();
    }
}