高朋Groupon使用 Redis 每分钟扩展数百万个地理空间查询


为了让高朋Groupon用户附近找到相关的交易,需要进行大量的地理空间搜索。这些搜索是在地理空间实体上执行的,例如邮政编码、时区、社区或兴趣点。每分钟以低延迟提供数百万次查询需要高效的空间索引器进行优化。
本文介绍了 Groupon 如何使用 Redis 来支持两种主要类型的地理空间搜索 - 查找最近的实体和查找半径内所有附近的实体。我们还将了解 Redis 集群如何提供可扩展和高性能的解决方案。
Redis 提供了GEOADDGEORADIUSGEORADIUSBYMEMBERGEOSEARCHGEOSEARCHSTORE等命令,用于地理空间索引和搜索。空间实体存储在排序集中,坐标使用Geohash技术形成 52 位整数。
 
为什么要使用Redis?
有很多解决方案可用于实现空间搜索。Quadtree、R-tree 和 Kd 树等数据结构可用于索引实体。S2 和 H3 等地理空间索引器可用于类似的查询。
但是,Redis 在可扩展性、性能和可用性方面具有优势。与其他解决方案相比,Redis 有几个优势:
1. 可扩展性
从时间复杂度可以看出,随着地理数据量的增加,命令执行的时间也会增加。使用的内存也必然会增加。在这种情况下,Redis 集群可以随着数据量的变化而扩展。
Redis 集群有两种扩展方式——水平扩展和垂直扩展。

  • 水平扩展允许在集群中添加或删除节点(分片)。即使在重新分片期间,集群也会继续为请求提供服务,同时扩展/缩小。
  • 垂直扩展允许在为请求提供服务时更改节点的大小以进行向上/向下扩展。

2. 高可用
Redis 集群通过复制提供高可用性。主节点可以跨物理机架(或数据中心)配置多个副本。Redis 集群也支持自动故障转移。
3. 性能
Redis 是一种内存数据存储,其数据结构针对性能进行了优化。但是,在对地理空间查询的性能进行基准测试和调整时,需要牢记以下几点:
  • GEOADD 和 GEORADIUS 命令的时间复杂度分别为 O(log(N)) 和 O(N + log(M))。保持密钥大小小并且数据分区是很重要的,以避免任何单个节点过载。半径的增加会导致命令执行时间增加。
  • 客户端使用 TCP 连接与 Redis 服务器通信。客户端套接字处于非阻塞状态,因为 Redis 使用多路复用和非阻塞 I/O。应启用 TCP Keepalive 以进行性能调整。Keepalive 是一种允许使用相同的 TCP 连接而不是为每个新请求打开一个新连接的方法。
  • 水平扩展允许键分布在分片上,并通过减少每个分片的负载来提高性能。
  • 如果启用了Redis集群模式,则不需要RDB持久化和AOF。
  • 默认情况下,Redis 允许 10,000 个客户端连接,并且可以进行配置。
  • Redis 命令的性能可以使用redis-benchmark实用程序进行基准测试