php - Amazon ElastiCache Memcached/Redis:将IP范围映射到国家/地区

Question

我有一个mysql数据库，它有一个ip范围（开始和结束，所以有两列）和一个国家代码（一列）。数据库用于根据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。
期待你的想法。
马克

Answer 1

刚刚看到你的问题，即使是很久以前你问的，我有一个使用redis的解决方案。
让我们首先尝试用一些基本数字（而不是ips）来模拟这个问题，并看看如何解决它：
范围到国家查找

   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]=>IP地址属于A国。我们从 end:Country A开始的原因将在 6中显而易见。
查找：
查找范围[11，15]中的数字（此处为包含范围）。结果将是 L2=>
L2查找 begin:Country B
=>查找到范围开始的数字点，即 IF
=>确定： L2.1IP属于开始：直接B国值
begin:Country B错误：IP不属于任何已知范围
查找：
结果将是 iff=>错误：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
          |            |

插入：
使IP ELSE和 L3的地址（介于 Empty List or Set和 I1之间）无效。=>有效地 6范围缩小到单个IP地址 7。
插入：
好的，没有距离交叉点
插入：
呈现国家B开头无效+呈现国家D开头（ 5。 8）无效
插入：
好啊
注意：在某些情况下，可能需要引入范围分割逻辑。
基于redis的解决方案
我建议使用redis zset来实现这个目的。以下是观察结果：
除了点式十进制字符串表示法之外，每个IPv4地址都可以表示为32位整数。
redis zset通过使用分数对存储成员进行额外排序来保证存储成员的唯一性。
我们可以使用score range，即 Country A命令来搜索zset成员。
如果我们使用数字IP作为zset分数，我们就完成了。一个国家的独特性是通过在特定范围的前缀前面加上 10和 I2来实现的。在现实生活中，一个国家可能有多个IP地址范围，因此您可能最终将范围编号编码为国家名称，如 I3和 17。您可以将其规范化并引入间接寻址。但是为了保持低查找数，您需要对其进行非规范化，并在单个数据库访问中获得尽可能多的信息。这是因为引入新范围的频率比查找要低得多，因此增加查找次数将降低性能。

   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"

注意： 20是表示为无符号int的ipv4 I4，同样适用于 ZRANGEBYSCORE。
检查特定IP所属的范围

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

注意： begin:是表示为无符号int的ipv4 end:，我们从 begin:r1:Country A开始（即 end:r1:Country A）查找一个元素（即 3232235777）。
检查已查找的IP启动新范围

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

注：结果将 192.168.1.1
复杂性分析
空间复杂性：如果在最坏的情况下，每个IP代表一个范围的开始和结束，我们将需要 192.168.1.100空间，其中n是 3232235778。但在现实生活中，这个数字会小得多。在一些算法书籍中，您将看到 192.168.1.2被认为是一个常数因子，因此将被减少到 LIMIT 0 1。
运行时复杂性：redis声明 192.168.1.8是一个 +inf操作，其中 Lookup 2.1是 3232235777中的元素数，即这里只有1个元素。如果我们在最坏情况下最多有 O(2*N)的分数，那么在redis set实现中 2^32的比较就在 2^32左右。但实际上，我认为不会有超过2千或3千个范围，这是在 O(1)比较。a ZRANGEBYSCORE command的redis状态：
在入门级笔记本电脑上运行的redis可以在40毫秒内扫描100万个密钥数据库。
总的来说，你的查找速度会很快！