本帖最后由 tomcar 于 2021-8-6 07:45 编辑
9、GeoHash(附近的人实现)
将单位和单位的经纬度存入redis中，可以实现附近的单位的功能。
9.1、redis实现
# 先增加公司，包括经纬度
[Bash shell] 纯文本查看 复制代码 > geoadd company 116.48105 39.996794 juejin
> geoadd company 116.514203 39.905409 ireader
> geoadd company 116.489033 40.007669 meituan
> geoadd company 116.562108 39.787602 jd 116.334255 40.027400 xiaomi
# 获取两个公司之间的距离
[Bash shell] 纯文本查看 复制代码 > geodist company juejin ireader km # "10.5501"
> geodist company juejin meituan km # "1.3878"
> geodist company juejin jd km # "24.2739"
> geodist company juejin xiaomi km # "12.9606"
> geodist company juejin juejin km # "0.0000"
# 获取公司位置
[Bash shell] 纯文本查看 复制代码 > geopos company juejin
1) 1) "116.48104995489120483"
2) "39.99679348858259686"
> geopos company ireader
1) 1) "116.5142020583152771"
2) "39.90540918662494363"
> geopos company juejin ireader
1) 1) "116.48104995489120483"
2) "39.99679348858259686"
2) 1) "116.5142020583152771"
2) "39.90540918662494363"
# 获取元素的hash值
[Bash shell] 纯文本查看 复制代码 > geohash company ireader # 1) "wx4g52e1ce0"
> geohash company juejin # 1) "wx4gd94yjn0"
# 附近的公司
[Bash shell] 纯文本查看 复制代码 # 范围 20 公里以内最多 3 个元素按距离正排，它不会排除自身
> georadiusbymember company ireader 20 km count 3 asc
1) "ireader"
2) "juejin"
3) "meituan"
# 范围 20 公里以内最多 3 个元素按距离倒排
> georadiusbymember company ireader 20 km count 3 desc
1) "jd"
2) "meituan"
3) "juejin"
# 三个可选参数 withcoord withdist withhash 用来携带附加参数
# withdist 很有用，它可以用来显示距离
> georadiusbymember company ireader 20 km withcoord withdist withhash count 3 asc
1) 1) "ireader"
2) "0.0000"
3) (integer) 4069886008361398
4) 1) "116.5142020583152771"
2) "39.90540918662494363"
2) 1) "juejin"
2) "10.5501"
3) (integer) 4069887154388167
4) 1) "116.48104995489120483"
2) "39.99679348858259686"
3) 1) "meituan"
2) "11.5748"
3) (integer) 4069887179083478
4) 1) "116.48903220891952515"
2) "40.00766997707732031"
# 根据坐标查附近的公司
[Bash shell] 纯文本查看 复制代码 > georadius company 116.514202 39.905409 20 km withdist count 3 asc
1) 1) "ireader"
2) "0.0000"
2) 1) "juejin"
2) "10.5501"
3) 1) "meituan"
2) "11.5748"
9.2、实现原理及算法
GeoHash算法将二维的经纬度数据映射到一维的整数，这样所有的元素都将挂在到一条线上，距离靠近的二维坐标映射到一维后的点之间的距离也会接近。在计算[附近的人]时，将目标先映射到坐标上，然后取附近的点就好了。
映射及查找原理：
1、将二维平面划分为正方形小格，编码00、01、10、11，然后对每一个小格再进行划分，比如00分为0000、0001、0010、0011... 越长，则越精确。
2、GeoHash算法对整数做一次base32编码(0-9,a-z 去掉 a,i,l,o 四个字母)，变成一个字符串。如："wx4g52e1ce0"。一共11个字符，前10个字符，以base32编码，一个字符占用5位，共占用5*10+2=52位。变成了一个52位的整数。
3、然后放入zset中。key是company，value是公司key，score是52位整数值(score是浮点数，但是对于52位整数，可以无损存储)。通过zset的score排序就可以得到坐标附近的公司。
10、Scan
和keys类似。由于redis是单线程的，如果存储的key较多，执行keys时会有明显的卡顿现象，于是出现了Scan。
10.1、scan使用
scan 参数提供了三个参数，第一个是 cursor 整数值，第二个是 key 的正则模式，第三个是遍历的 limit hint。
[Bash shell] 纯文本查看 复制代码 > scan 0 match key99* count 1000
1) "13976"
2) 1) "key9911"
2) "key9974"
。。。 #(大概有10个)
> scan 13976 match key99* count 1000
1) "1996"
2) 1) "key9982"
2) "key9997"
。。。
从上面的过程可以看到虽然提供的limit值是1000，但是返回的结果只有10个左右。因为这个limit不是限定返回结果的数量，而是限定服务器单次遍历的字典槽位数量(约等于)。如果将limit设置为10，返回结果可能是空的，但是游标不为0，意味着遍历还没有结束。字典存储就和java中的HashMap是一样的，也是一维数组+二维链表构成。
[Bash shell] 纯文本查看 复制代码 > scan 0 match key99* count 10
1) "3072"
2) (empty list or set)
10.2、原理及解析
1、sacn的遍历顺序比较特别。它不是从第一维数组的第0位一直遍历到末尾的，而是采用高位进位加法来遍历。之所以采用这种特殊的方式进行遍历，是考虑到字典的扩容和缩容时避免槽位的遍历重复和遗漏。顺序(例)：000、100、010、110、001、101、011、111。
2、普通加法和高位进位加法的区别。高位进位法从左边加，进位往右边移动，同普通加法正好相反。但是最终它们都会遍历所有的槽位并且没有重复。
如：槽位110扩容为0110和1110，则此时已经遍历到了110了，直接继续遍历1110就好了。
3、因为数组长度都是2^n次，所以此时取模运算等价于位与运算。即：a mod 8 = a&(8-1)=a&7；a mod 16 = a&(16-1)=a&15。
10.3、更多
1、渐进式rehash。
Java 的 HashMap 在扩容时会一次性将旧数组下挂接的元素全部转移到新数组下面。如果 HashMap 中元素特别多，线程就会出现卡顿现象。Redis 为了解决这个问题，它采用渐进式 rehash。它会同时保留旧数组和新数组，然后在定时任务中以及后续对 hash 的指令操作中渐渐地将旧数组中挂接的元素迁移到新数组上。这意味着要操作处于 rehash 中的字典，需要同时访问新旧两个数组结构。如果在旧数组下面找不到元素，还需要去新数组下面去寻找。scan 也需要考虑这个问题，对与 rehash 中的字典，它需要同时扫描新旧槽位，然后将结果融合后返回给客户端。
2、更多的scan指令。
zscan 遍历 zset 集合元素，hscan 遍历 hash 字典的元素、sscan 遍历 set 集合的元素
3、大key扫描。
在集群环境下，如果某个 key 太大，会数据导致迁移卡顿。
在内存分配上，如果一个 key 太大，那么当它需要扩容时，会一次性申请更大的一块内存，这也会导致卡顿。
如果这个大 key 被删除，内存会一次性回收，卡顿现象会再一次产生。
在平时的业务开发中，要尽量避免大 key 的产生。
4、定位大key。
Redis 官方已经在 redis-cli 指令中提供了这样的扫描功能。
redis-cli -h 127.0.0.1 -p 6379 --bigkeys -i 0.1 #-i 0.1 是可选参数，表示每扫描100条scan指令就会休眠0.1秒，避免卡顿。 | 
发表于 2021-7-27 22:24
|
发表于 2021-7-27 22:47
