基于GeoHash+Redis实现LBS附近地点搜索

geohash
文浩

GeoHash

需求

随着移动业务的不断创新，基于位置服务的需求逐渐增多。比如美团搜索附近的美食，嘀嘀打车搜搜附近的司机等。支撑这一业务最主要的就是LBS(基于位置的服务)，特别是嘀嘀打车的业务尤为突出，司机与乘客不断更新的坐标地址，从一大堆无关的坐标地址内找出一定范围内所有的司机，这无疑对服务器承载力带来巨大的挑战。

先比较一下不同的解决方案。最后讲解一下如何使用52位的GeoHash集成Redis实现此需求。

解决方案

  1. 物理计算，正对某个中心点，计算所有周边点，再根据搜索范围刷选。
  2. 基于MySQL，可选择物理计算/GeoHash/MySQL空间索引。
  3. 基于MongoDB，依赖MongoDB的空间搜索算法搜索。
  4. 自行开发搜索算法并存入Redis。

方案解析

物理计算

在我们第一次遇到这类问题，头脑里面最先浮现的解决方案，但是我们的潜意思告诉我们这肯定是不行的。如果搜索的受众量很大，光是计算距离就要消耗大量的时间。

基于MySQL

存入MySQL实现上有三种方式：

  1. 根据纬度和精度每增加0.01度增加1000m为算法，检索出候选坐标，再根据搜索范围刷选。距离搜索3公里以内所有目标，伪代码：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    double kilometer = 3.0;

    double precision = 0.01 * kilometer;

    //SQL 限定条件 
    SELECT * FROM driver_coordinate
    WHERE latitude > latitude - precision && 
          latitude < latitude + precision &&
          longitude > longitude - precisionRadius && 
          longitude < longitude + precisionRadius;

  2. 给每一个坐标计算一个GeoHash值，业界大部分的使用的是基于Base32编码的12位GeoHash字符串。但是这样精度不太容易控制。我们将要讨论的是52位的整形值来表示GeoHash。52位的GeoHash最小能精确到0.6米，足够满足绝大部分需求(52位GeoHash算法见下文)。

  3. MySQL空间存储，MySQL本省就支持空间搜索。

    1
    GLength(LineStringFromWKB(LineString(point1, point2)))

但是由于MySQL的限制，查询效率低，可伸缩性较差。

基于MongoDB

MonggoDB原生也支持地理位置索引，支持位置查询及排序。

命令如:

1
db.runCommand({ geoNear: "places", near: [30.545162, 104.062018], num:1000 })

MongoDB支持地理位置查询，可伸缩性较好，配置集群简单，集成方便快，成本最低。3.0版本之后增加了Collection锁，性能大大提升。业界也有不少公司在使用，比如美团、街旁、全球最大的LBS应用Foursquare用的MongoDB。

自行开发搜索算法并存入Redis

自行开发算法精度与扩展方式容易控制，对第三方没有依赖方便升级与替换。

具体实现

  1. 坐标转换成52bit二进制编码值。

    • 52bit精度在0.6m足够满足搜索范围需求。

    • 算法，根据经纬度计算GeoHash二进制编码：

      • 首先将纬度范围(-90, 90)平分成两个区间(-90, 0)、(0, 90)， 如果目标纬度位于前一个区间，则编码为0，否则编码为1。由于39.92324属于(0, 90)，所以取编码为1。然后再将(0, 90)分成 (0, 45), (45, 90)两个区间，而39.92324位于(0, 45)，所以编码为0。以此类推，直到精度符合要求为止，得到纬度编码为1011 1000 1100 0111 1001。
      • 经度也用同样的算法，对(-180, 180)依次细分，得到116.3906的编码为1101 0010 1100 0100 0100。
      • 接下来将经度和纬度的编码合并，奇数位是纬度，偶数位是经度，得到编码 11100 11101 00100 01111 00000 01101 01011 00001。 
      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      20
      21
      22
      23
      24
      25
      26
      27
      28
      29
      30
      31
      32
      33
      34
      35
      36
      37
      38
      39
      40
      41
      42
      43
      44
      45
      46
      47
      48
      49
      50
      51
      52
      53
      54
      55
      56
      57
      58
      59
      60
      61
      62
      63
      64
      65
      66
      67
      68
      69
      70
      71
      72
      73
      74
      75
      76
      77
      78
      79
      80
      81
      82
      83
      84
      85
      86
      87
      88
      89
      90
      91
      92
      93
      94
      95
      96
      97
      98
      99
      100
      101
      102
      103
      104
      105
      106
      107
      108
      109
      110
      111
      112
      113
      114
      115
      116
      117
      118
      119
      120
      121
      122
      123
      124
      125
      126
      127
      128
      129
      130
      131
      132
      133
      134
      135
      136
      137
      138
      139
      140
      141
      142
      143
      144
      145
      146
      147
      148
      149
      150
      151
      152
      153
      154
      155
      156
      157
      158
      159
      160
      161
      162
      163
      164
      165
      166
      167
      168
      169
      170
      171
      172
      173
      174
      175
      176
      177
      178
      179
      180
      181
      182
      183
      184
      185
      186
      187
      188
      189
      190
      191
      192
      193
      194
      195
      196
      197
      198
      199
      200
      201
      202
      203
      204
      205
      206
      207
      208
      209
      210
      211
      212
      213
      214
      215
      216
      217
      218
      219
      220
      221
      222
      223
      224
      225
      226
      227
      228
      229
      230
      231
      232
      233
      234
      235
      236
      237
      238
      239
      240
      241
      242
      243
      244
      245
      246
      247
      248
      249
      250
      251
      252
      253
      254
      package com.github.wenhao.geohash;
      import static java.lang.Math.abs;
      import static java.lang.Math.atan2;
      import static java.lang.Math.cos;
      import static java.lang.Math.sin;
      import static java.lang.Math.sqrt;
      import static java.lang.Math.toRadians;
      import java.util.Arrays;
      import java.util.List;

      import com.github.wenhao.geohash.domain.Coordinate;

      public class GeoHash {

          public static final int MAX_PRECISION = 52;
          private static final long FIRST_BIT_FLAGGED = 0x8000000000000L;
          private long bits = 0;
          private byte significantBits = 0;
          private Coordinate coordinate;

          private GeoHash() {
          }

          public static GeoHash fromCoordinate(double latitude, double longitude) {
              return fromCoordinate(latitude, longitude, MAX_PRECISION);
          }

          public static GeoHash fromCoordinate(double latitude, double longitude, int precision) {
              GeoHash geoHash = new GeoHash();
              geoHash.coordinate = new Coordinate(latitude, longitude);
              boolean isEvenBit = true;
              double[] latitudeRange = {-90, 90};
              double[] longitudeRange = {-180, 180};

              while (geoHash.significantBits < precision) {
                  if (isEvenBit) {
                      divideRangeEncode(geoHash, longitude, longitudeRange);
                  } else {
                      divideRangeEncode(geoHash, latitude, latitudeRange);
                  }
                  isEvenBit = !isEvenBit;
              }
              geoHash.bits <<= (MAX_PRECISION - precision);
              return geoHash;
          }

          public static GeoHash fromLong(long longValue) {
              return fromLong(longValue, MAX_PRECISION);
          }

          public static GeoHash fromLong(long longValue, int significantBits) {
              double[] latitudeRange = {-90.0, 90.0};
              double[] longitudeRange = {-180.0, 180.0};

              boolean isEvenBit = true;
              GeoHash geoHash = new GeoHash();

              String binaryString = Long.toBinaryString(longValue);
              while (binaryString.length() < MAX_PRECISION) {
                  binaryString = "0" + binaryString;
              }
              for (int j = 0; j < significantBits; j++) {
                  if (isEvenBit) {
                      divideRangeDecode(geoHash, longitudeRange, binaryString.charAt(j) != '0');
                  } else {
                      divideRangeDecode(geoHash, latitudeRange, binaryString.charAt(j) != '0');
                  }
                  isEvenBit = !isEvenBit;
              }

              double latitude = (latitudeRange[0] + latitudeRange[1]) / 2;
              double longitude = (longitudeRange[0] + longitudeRange[1]) / 2;

              geoHash.coordinate = new Coordinate(latitude, longitude);
              geoHash.bits <<= (MAX_PRECISION - geoHash.significantBits);
              return geoHash;
          }
          
          public double distance(double latitude, double longitude) {
              double startLatitude = this.coordinate.getLatitude();
              double startLongitude = this.coordinate.getLongitude();
              double diffLongitudes = toRadians(abs(longitude - startLongitude));
              double diffLatitudes = toRadians(abs(latitude - startLatitude));
              double slat = toRadians(startLatitude);
              double flat = toRadians(latitude);
              double factor = sin(diffLatitudes / 2) * sin(diffLatitudes / 2) + cos(slat) * cos(flat) * sin(diffLongitudes / 2)
                      * sin(diffLongitudes / 2);
              double angularDistance = 2 * atan2(sqrt(factor), sqrt(1 - factor));
              return EARTH_RADIUS * angularDistance;
          }

          public List<GeoHash> getAdjacent() {
              GeoHash northern = getNorthernNeighbour();
              GeoHash eastern = getEasternNeighbour();
              GeoHash southern = getSouthernNeighbour();
              GeoHash western = getWesternNeighbour();
              return Arrays.asList(northern, northern.getEasternNeighbour(), eastern, southern.getEasternNeighbour(),
                      southern, southern.getWesternNeighbour(), western, northern.getWesternNeighbour(), this);
          }

          private GeoHash getNorthernNeighbour() {
              long[] latitudeBits = getRightAlignedLatitudeBits();
              long[] longitudeBits = getRightAlignedLongitudeBits();
              latitudeBits[0] += 1;
              latitudeBits[0] = maskLastNBits(latitudeBits[0], latitudeBits[1]);
              return recombineLatLonBitsToHash(latitudeBits, longitudeBits);
          }

          private GeoHash getSouthernNeighbour() {
              long[] latitudeBits = getRightAlignedLatitudeBits();
              long[] longitudeBits = getRightAlignedLongitudeBits();
              latitudeBits[0] -= 1;
              latitudeBits[0] = maskLastNBits(latitudeBits[0], latitudeBits[1]);
              return recombineLatLonBitsToHash(latitudeBits, longitudeBits);
          }

          private GeoHash getEasternNeighbour() {
              long[] latitudeBits = getRightAlignedLatitudeBits();
              long[] longitudeBits = getRightAlignedLongitudeBits();
              longitudeBits[0] += 1;
              longitudeBits[0] = maskLastNBits(longitudeBits[0], longitudeBits[1]);
              return recombineLatLonBitsToHash(latitudeBits, longitudeBits);
          }

          private GeoHash getWesternNeighbour() {
              long[] latitudeBits = getRightAlignedLatitudeBits();
              long[] longitudeBits = getRightAlignedLongitudeBits();
              longitudeBits[0] -= 1;
              longitudeBits[0] = maskLastNBits(longitudeBits[0], longitudeBits[1]);
              return recombineLatLonBitsToHash(latitudeBits, longitudeBits);
          }

          private GeoHash recombineLatLonBitsToHash(long[] latBits, long[] lonBits) {
              GeoHash geoHash = new GeoHash();
              boolean isEvenBit = false;
              latBits[0] <<= (MAX_PRECISION - latBits[1]);
              lonBits[0] <<= (MAX_PRECISION - lonBits[1]);
              double[] latitudeRange = {-90.0, 90.0};
              double[] longitudeRange = {-180.0, 180.0};

              for (int i = 0; i < latBits[1] + lonBits[1]; i++) {
                  if (isEvenBit) {
                      divideRangeDecode(geoHash, latitudeRange, (latBits[0] & FIRST_BIT_FLAGGED) == FIRST_BIT_FLAGGED);
                      latBits[0] <<= 1;
                  } else {
                      divideRangeDecode(geoHash, longitudeRange, (lonBits[0] & FIRST_BIT_FLAGGED) == FIRST_BIT_FLAGGED);
                      lonBits[0] <<= 1;
                  }
                  isEvenBit = !isEvenBit;
              }
              geoHash.bits <<= (MAX_PRECISION - geoHash.significantBits);
              geoHash.coordinate = getCenterCoordinate(latitudeRange, longitudeRange);
              return geoHash;
          }

          private long[] getRightAlignedLatitudeBits() {
              long copyOfBits = bits << 1;
              long value = extractEverySecondBit(copyOfBits, getNumberOfLatLonBits()[0]);
              return new long[]{value, getNumberOfLatLonBits()[0]};
          }

          private long[] getRightAlignedLongitudeBits() {
              long copyOfBits = bits;
              long value = extractEverySecondBit(copyOfBits, getNumberOfLatLonBits()[1]);
              return new long[]{value, getNumberOfLatLonBits()[1]};
          }

          private long extractEverySecondBit(long copyOfBits, int numberOfBits) {
              long value = 0;
              for (int i = 0; i < numberOfBits; i++) {
                  if ((copyOfBits & FIRST_BIT_FLAGGED) == FIRST_BIT_FLAGGED) {
                      value |= 0x1;
                  }
                  value <<= 1;
                  copyOfBits <<= 2;
              }
              value >>>= 1;
              return value;
          }

          private Coordinate getCenterCoordinate(double[] latitudeRange, double[] longitudeRange) {
              double minLon = Math.min(longitudeRange[0], longitudeRange[1]);
              double maxLon = Math.max(longitudeRange[0], longitudeRange[1]);
              double minLat = Math.min(latitudeRange[0], latitudeRange[1]);
              double maxLat = Math.max(latitudeRange[0], latitudeRange[1]);
              double centerLatitude = (minLat + maxLat) / 2;
              double centerLongitude = (minLon + maxLon) / 2;
              return new Coordinate(centerLatitude, centerLongitude);
          }

          private int[] getNumberOfLatLonBits() {
              if (significantBits % 2 == 0) {
                  return new int[]{significantBits / 2, significantBits / 2};
              } else {
                  return new int[]{significantBits / 2, significantBits / 2 + 1};
              }
          }

          private long maskLastNBits(long value, long number) {
              long mask = 0xffffffffffffffffL;
              mask >>>= (MAX_PRECISION - number);
              return value & mask;
          }

          private static void divideRangeEncode(GeoHash geoHash, double value, double[] range) {
              double mid = (range[0] + range[1]) / 2;
              if (value >= mid) {
                  geoHash.addOnBitToEnd();
                  range[0] = mid;
              } else {
                  geoHash.addOffBitToEnd();
                  range[1] = mid;
              }
          }

          private static void divideRangeDecode(GeoHash geoHash, double[] range, boolean isOnBit) {
              double mid = (range[0] + range[1]) / 2;
              if (isOnBit) {
                  geoHash.addOnBitToEnd();
                  range[0] = mid;
              } else {
                  geoHash.addOffBitToEnd();
                  range[1] = mid;
              }
          }

          private void addOnBitToEnd() {
              significantBits++;
              bits <<= 1;
              bits = bits | 0x1;
          }

          private void addOffBitToEnd() {
              significantBits++;
              bits <<= 1;
          }

          public long toLong() {
              return bits;
          }

          public Coordinate coordinate() {
              return coordinate;
          }

          @Override
          public String toString() {
              if (significantBits % 5 == 0) {
                  return String.format("bits: %s", Long.toBinaryString(bits));
              } else {
                  return String.format("bits: %s", Long.toBinaryString(bits));
              }
          }
      }

      支持坐标转换成GeoHash与Long型值反转回坐标，转换会有误差，误差分米级能够接受。

  2. 估算搜索范围起始值。

    52bit把地球总面积等分成2^26(2的26次方)个区域, 每个区域大小等于0.6mx0.6m的正方形面积. 同理如果采用30bit,就是把地球等分成2^15个区域, 每个区域大小等于1222mx1222m.

    精度估算

    • 算法, 如果用52位来表示一个坐标, 那么总共有: 2^26 * 2^26 = 2^52 个框:

      • 地球半径：radius = 6372797.560856m
      • 每个框的夹角：angle = 1 / 2^26 (2的26次方)
      • 每个框在地球表面的长度: length = 2 x π x radius x angle
      • 52bit:0.59m, 50bit:1.19m……,30bit:1221.97m, 28bit:2443.94m, 26bit:4887.87m, 24bit: 9775.75m……

  3. 给出查询的中心坐标并计算其GeoHash值(52bit)。

  4. 计算中心坐标相邻的8个坐标(中心坐标在两个框边界会有误差，此规避误差)。

  5. 加上中心坐标共9个52bit的坐标值，针对每个坐标值参照搜索范围值算出区域值[MIN, MAX]。

    • 算法：MIN为坐标的搜索指定位起始长度后补零；MAX为坐标的搜索指定位终止长度后+1再补零。

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      20
      21
      22
      23
      24
      25
      26
      27
      28
      29
      30
      31
      32
      33
      34
      35
      36
      37
      38
      39
      40
      41
      42
      43
      44
      45
      46
      47
      48
      49
      50
      51
      52
      53
      54
      55
      56
      57
      58
      59
      60
      61
      package com.github.wenhao.geohash;

      import static java.math.BigDecimal.ROUND_HALF_UP;
      import static java.util.stream.Collectors.toList;

      import java.math.BigDecimal;
      import java.util.HashMap;
      import java.util.List;
      import java.util.Map;
      import java.util.Optional;

      import static com.github.wenhao.geohash.GeoHash.MAX_PRECISION;

      import com.github.wenhao.geohash.domain.GeoRange;

      public class GeoSearch {
          private static final BigDecimal EARTH_RADIUS = new BigDecimal(6372797.560856);
          private static Map<BigDecimal, Integer> PRECISION_MAP;

          static {
              PRECISION_MAP = new HashMap<>();
              for (int angle = 1; angle <= MAX_PRECISION / 2; angle++) {
                  BigDecimal bigDecimal = new BigDecimal(2)
                          .multiply(new BigDecimal(Math.PI))
                          .multiply(EARTH_RADIUS)
                          .divide(new BigDecimal(2).pow(angle), ROUND_HALF_UP);
                  PRECISION_MAP.put(bigDecimal, 2 * angle);
              }
          }

          public static List<GeoRange> range(double latitude, double longitude, double range) {
              int desiredLength = getDesiredLength(range);
              return getNineAroundCoordinate(latitude, longitude, desiredLength).stream()
                      .map(geoHash -> {
                          long longValue = geoHash.toLong();
                          long min = longValue << (MAX_PRECISION - desiredLength);
                          long max = (longValue + 1) << (MAX_PRECISION - desiredLength);
                          return new GeoRange(min, max);
                      })
                      .collect(toList());
          }

          private static List<GeoHash> getNineAroundCoordinate(double latitude, double longitude, int desiredLength) {
              long longValue = GeoHash.fromCoordinate(latitude, longitude).toLong();
              long centralPoint = longValue >>> (MAX_PRECISION - desiredLength);
              return GeoHash.fromLong(centralPoint).getAdjacent();
          }

          private static int getDesiredLength(double range) {
              int desiredLength = 0;
              Optional<BigDecimal> rangeKey = PRECISION_MAP.keySet()
                      .stream()
                      .sorted()
                      .filter(bigDecimal -> bigDecimal.compareTo(BigDecimal.valueOf(range)) == 1)
                      .findFirst();
              if (rangeKey.isPresent()) {
                  desiredLength = PRECISION_MAP.get(rangeKey.get());
              }
              return desiredLength;
          }
      }

      例如搜索3000m~5000m的目标，最小3000m介于精度28bit：2443.94m~26bit：4887.87m之间故最小精度取右28bit右全补零。最大5000m介于26bit：4887.87m~24bit：9775.75m之间取右24bit的值加1后右全补零。

  6. 使用Redis命令ZRANGEBYSCORE key MIN MAX WITHSCORES查找。

  7. 避免误差按照距离公式在将所有结果过滤一次(GeoHash反坐标再计算距离)。

文章目录
←
  1. 1. 需求
  2. 2. 解决方案
  3. 3. 方案解析
    1. 3.0.1. 物理计算
    2. 3.0.2. 基于MySQL
    3. 3.0.3. 基于MongoDB
    4. 3.0.4. 自行开发搜索算法并存入Redis
  • 4. 具体实现
    • 分享到