当键在范围内而不是单个值时，如何内存缓存或存储键值对

Question

我们的数据库中有一个表，其中包含城市及其ip地址的静态ip范围。它看起来像：

---

IP-TO，IP-FROM，城市

100110，

11168，B

9651000，Z

我已经提到了样本数据。实际数据是巨大的，表中几乎有64k行。

对于我们网站上的每个用户，我们通过在sql express服务器上执行sql查询，根据他们的IP地址来确定他们的城市。

由于数据是静态的，例如，每个IP在100到110范围内的用户都属于城市A，因此我们每次都不必要地访问数据库。

我们正在考虑缓存每一次独特的ip访问。例如：IP-100映射到AIP-101映射到A。。。IP-110映射到

但这将在memcache中创建64k个密钥，当我们知道范围时，我觉得存储多个具有相同值的密钥是没有意义的。

我们能以更好的方式做到这一点吗？即通过最小内存缓存密钥或完全使用不同的方法？

Answer 1

可以对IP地址列表进行排序（因为它们本质上是数字）。如果您有一个很大的IP范围的非重叠列表，您可以将它们排序为一个大列表。如果你有一个大的、排序的值列表，你可以对它进行二进制搜索。对于64k个项目，你可以在大约16次比较中搜索整个列表（几乎是即时的）。

有了正确的索引和查询，您的数据库可能能够为您做到这一点。如果你认为用另一种方式可能会更快（提示：使用评测来确定它是否真的是！）或者担心额外的数据库访问，你可以将整个表的数据缓存在内存中，然后搜索列表。高级术语：

public class IPRangeCache
{
    private List<IPRangeRecord> sortedRangeRecords = null; // get from database
    public string GetCity(IPAddress ip) {
        // binary search to find from sortedRangeRecords
    }
}

二进制搜索需要同时考虑起始数字和结束数字。自定义比较器或自定义二进制搜索应该可以实现这一点。这应该很快。

你也可以尝试在字典中缓存最后几分钟的IP地址，但我认为这不太可能更快。

Answer 2

我们可以使用C#通用字典。

我们创建了一个包含IP范围的类。这个类将充当字典的键。

class IP_Range 
{
    public int MinIP { get; set; }
    public int MaxIP { get; set; }
}

然后，我们必须创建一个比较器类，它将有助于比较字典的键。

class IP_RangeComparer : IEqualityComparer<IP_Range>
{
    public bool Equals(IP_Range r1, IP_Range r2)
    {
        return (r1.MinIP == r2.MinIP && r1.MaxIP == r2.MaxIP);
    }
    public int GetHashCode(IP_Range r)
    {
        return r.MinIP.GetHashCode();
    }
}

然后我们可以创建一个通用字典，并按如下方式使用它：

IDictionary<IP_Range, string> myCache = new Dictionary<IP_Range, string>(new IP_RangeComparer());
// Adding entries
myCache.Add(new IP_Range() { MinIP = 100, MaxIP = 110 }, "A");
myCache.Add(new IP_Range() { MinIP = 111, MaxIP = 168 }, "B");
myCache.Add(new IP_Range() { MinIP = 169, MaxIP = 200 }, "C");
// Reading the dictionary
string city = myCache[new IP_Range() { MinIP = 169, MaxIP = 200 }];

请参阅本文以获得进一步的解释。

注意：要找到要搜索的特定IP的密钥，您必须遍历myCache.Keys集合。

Answer 3

您可以根据该值创建IpAddress类的实例，然后只使用其中一个字节作为缓存键。这样一来，对于001.xxx.xxx.xxx，只需要一次数据库，对于002.xxx.xxxx.xxx，等等，

var address = new IPAddress(value);
var bytes = address.GetAddressBytes(); //an array of four bytes