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

我有一个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.

期待你的想法。

Marc

刚刚看到你的问题，即使你很久以前问过，我也有一个使用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地址属于国家A。为什么我们从6开始，在L2中会很明显。

查找`L2`：

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

IF查找L2.1
=>查找编号指向范围起始，即begin:Country B
=>确定：iff IP属于开始：国家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`：

将IP为6和7（位于5和8之间）的地址呈现为无效。=>有效地，Country A范围缩小到单个IP地址10。

插入`I2`：

好，无范围交叉

插入`I3`：

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

插入`I4`：

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

基于Redis的解决方案

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

每个IPv4地址都可以表示为一个32位整数，除了点十进制字符串表示。
Redis ZSET通过额外订购带有分数的成员来保证存储成员的唯一性
我们可以使用分数范围来搜索ZSET成员，即ZRANGEBYSCORE命令。

如果我们使用数字IP作为ZSET分数，我们就完了。国家的唯一性是通过在特定范围的前缀前加上begin:和end:来实现的。在现实生活中，一个国家可能有多个IP地址范围，因此您可能会将范围编号编码为国家名称，如begin:r1:Country A和end:r1:Country A。您可以将其规范化并引入间接寻址。但是，为了保持较低的查找数量，您可能需要对其进行反规范化，并在单个DB访问中拥有尽可能多的信息。这是因为引入新的范围比查找频率低得多，所以查找次数的增加会降低性能。

   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 192.168.1.2，表示为无符号int，我们从192.168.1.8（即+inf）开始查找一个元素（即LIMIT 0 1）。
检查Lookup 2.1查找的IP启动新范围
```
 > ZSCORE ip-to-country "begin:Country A"
```
注意：结果将为3232235777

复杂性分析

空间复杂性：如果在最坏的情况下，我们的每个IP都表示Range的开始和结束，那么我们将需要O(2*N)空间，其中N是2^32。但在现实生活中，这个数字会小得多。在一些算法书中，你会看到2^32被认为是一个常数因子，因此会被简化为O(1)。

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

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

总而言之，你的查找速度会很快！

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

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

Amazon ElastiCache Memcached/Redis: Map IP range to country

按国家/地区查找

查找L1：

查找L2：

查找L3：