0

我有一个 MySQL 数据库，它有一个 ip 范围（开始和结束，所以两列）和一个国家代码（1 列）。该数据库用于根据 IP 地址查找国家/地区。它有效，但我想加快速度。一个想法是使用 Redis 或 Memcache 将数据存储在 Amazon ElastiCache 上。我遇到的问题是如何使用这种方法？Redis 和 Memcache 使用键值，在我看来，很难存储 IP 范围和国家代码。对于使用 ElastiCache Memcache 或 Redis，您建议采用哪种方法？

国家范围将类似于：

  • 192.168.1.1 - 192.168.1.100（A 国）
  • 192.168.2.1 - 192.168.2.50（B 国）
  • 192.168.1.150 - 192.168.1.200（A 国）

现在我得到了 IP 地址，例如 192.168.1.160，我需要尽快查找并在这种情况下返回国家 A。

期待你的想法。

马克

4

2 回答 2

3

刚看到你的问题，你问的很久以前，我有一个使用Redis的解决方案。

让我们首先尝试用一些基本数字（而不是 IP）对问题进行建模，看看如何解决它：

范围到国家/地区查找

   Lookup |   Range    |     Country
  --------|------------+------------------
          |     5      |  begin:Country A
      L1 >>>           |
          |     10     |  end:Country A
          |            |
      L2 >>>           |
          |            |
      L2.1>>>   15     |  begin:Country B
          |            |
          |     20     |  end:Country B
      L3 >>>           |
          |            |

查找L1：

[6,10]在（此处包括范围）之间进行数字查找。在这种情况下，结果将是end:Country A=> IP Address 属于Country A。我们开始的原因6在L2.

查找L2：

查找范围 [11, 15] （包括范围）中的数字。结果将是begin:Country B=>

  • IFLookup L2.1
    => Looked Up Number指向范围start，即begin:Country B
    => OK: iffIP属于begin:Country B值直接

  • ELSE错误：IP 不属于任何已知范围

查找L3：

结果将是Empty List or Set=> 错误：IP 不属于任何已知范围

插入更棘手！

插入范围必须小心，因为新插入的范围可能会破坏现有范围。以下是插入的情况：

   Insert |   Range    |     Country
  --------|------------+------------------
          |     5      |  begin:Country A
          |            |
      I1 >>>    8,9    |  !!! Country C !!!
          |            |
          |     10     |  end:Country A
          |            |
          |            |
      I2 >>>    12,14  |  Country E
          |            |
          |            |
          |     15     |  begin:Country B
          |            |
      I3 >>>    17,21  |  !!! Country D !!!
          |            |
          |     20     |  end:Country B
          |            |
      I4 >>>    22,27  |  Country F
          |            |

插入I1：

使带有 IP6和7（介于5和之间8）的地址无效。=> 有效Country A范围缩小到单个 IP 地址10。

插入I2：

好的，没有范围交叉点

插入I3：

渲染B 国的开头无效 + 渲染D 国的开头（17.. 20）无效

插入I4：

好的

注意：在某些情况下，您可能需要引入范围分割逻辑。

基于 Redis 的解决方案

我建议为此目的使用 Redis ZSET。以下是观察结果：

  1. 除了点分十进制字符串表示之外，每个 IPv4 地址都可以表示为 32 位整数。

  2. Redis ZSET 通过额外使用分数对存储的成员进行排序来保证存储成员的唯一性

  3. ZRANGEBYSCORE我们可以通过使用分数范围，即命令来搜索ZSET成员。

如果我们使用数字 IP 作为 ZSET 分数，我们就完成了。一个国家的唯一性是通过为特定范围添加前缀来begin:强制执行的。end:在现实生活中，一个国家/地区可能有多个 IP 地址范围，因此您最终可能会将范围编号编码为国家名称，例如begin:r1:Country Aand end:r1:Country A。您可以对此进行规范化并引入间接性。但是为了保持低查找次数，您需要对其进行非规范化并在单个数据库访问中拥有尽可能多的信息。这是因为引入新范围的频率远低于进行查找，因此增加查找次数会降低性能。

   Lookup |   Score    |     Country
  --------|------------+------------------
          |     5      |  begin:Country A
      L1 >>>           |
          |     10     |  end:Country A
          |            |
      L2 >>>           |
          |            |
      L2.1>>>   15     |  begin:Country B
          |            |
          |     20     |  end:Country B
      L3 >>>           |
          |            |

使用什么 Redis 命令

这里只是简单的命令，没有你的逻辑来检查插入等期间的错误情况。

  • 添加新范围

    > ZADD ip-to-country 3232235777 "begin:Country A" 3232235876 "end:Country A"

    注意： 3232235777 IPv4 是否192.168.1.1表示为 unsigned int，同样适用于192.168.1.100.

  • 检查特定 IP 属于哪个范围

    > ZRANGEBYSCORE ip-to-country 3232235778 +inf WITHSCORES LIMIT 0 1

    注意： 3232235778 IPv4是用 unsigned int 表示的吗？我们从后面（ie ）开始192.168.1.2查找一个元素（ ie ）。LIMIT 0 1192.168.1.8+inf

  • 检查Lookup 2.1查找的 IP 开始新的范围

     > ZSCORE ip-to-country "begin:Country A"

    注意：结果将是3232235777

复杂性分析

空间复杂性：如果在最坏的情况下我们最终得到每个 IP 代表范围的开始和结束，我们将需要O(2*N)空间，其中 N 是2^32。但在现实生活中，这个数字会小得多。在一些算法书籍中，您会看到它2^32被认为是一个常数因子，因此将减少为O(1).

运行时复杂性： Redis 声明这ZRANGEBYSCORE是一个O(log(N)+M)操作，其中M是 中的元素数量LIMIT，即这里只有 1。如果我们2*2^32在最坏的情况下最多得分，而不是log2(8billion)在33Redis 集合实现中进行比较。但实际上我认为不会超过 2 或 3000 个范围，这是围绕11比较。Redis 状态为KEYS命令：

在入门级笔记本电脑上运行的 Redis 可以在 40 毫秒内扫描 100 万个关键数据库。

总而言之，您的查找速度将非常快！

于 2017-05-25T16:58:14.773 回答
0

如果您有每个开始/结束范围的键（例如“80-255”）和国家代码的值，您可以使用 Memcached 或 Redis。

如果你想要更少的键，你可以在 Redis 中使用一个排序集，其中键是开始范围，分数是结束范围，值是国家代码（也可以节省你的内存，因为 Redis 更有效地存储这些东西）。

于 2014-10-09T13:39:42.410 回答