key-value 存储数据的方法问题,求助

[yadam]

需求

想在内存里面key-value存储数据: 用户源IP的所属分组+域名 => A记录(一个int)
查找速度要快

• 域名大概1K条
• 分组大概50K

想法

• 域名使用哈希, google了一下, 找到了 FDH 这个关键字
  Wikipedia: Full Domain Hash
  stackoverflow: Building a google analytics domain hash
  不懂原理,用了sf中的方法测试了一下,结果没有冲突,觉着还挺合适, 例如

33560995
8779575
178167015
11007734
94446796
55930089
48267748
126538255
61265326
31084477
268173580
29247422
2099762

• 分组没有想好

求助

1. 整体上怎么设计比较好?
2. 域名的哈希有没有什么方法收敛到更小的范围?

[zhicheng]

查两次，普通的 hash 表就可以了，性能杠杠的。
如果需要持久化存储且数据不多，可以试一下我给一个DNS系统开发的 存储引擎。
http://github.com/zhicheng/db

[GeekGao]

直接存到Redis、ssdb是很快的。

分组存成:
group:[Name] => [Uniq Number of Group]

分组的
[Uniq Number of Group]:[Full Domain Hash] => [A record]

[lincanbin]

数据量真少，可以直接存MySQL里作数据持久化，然后用Memcached加一层key-value的临时缓存。

[yadam]

@zhicheng 使用用户IP查找所在分组的话有啥好方法没?
我现在是这样: 红黑树存储网络号, 将用户IP从偏移1开始左移, 从树里面看是否存在, 直到找到, 感觉有点儿拧巴.
另外一个想法就是模仿dpdk的lpm库

[zhicheng]

关键词 “trie 树”。
如果量比较小，或者数据库比较详细，直接 hash 表按位查就行了，最多查 32 次没找到。
如果IP数据库不需要修改，可以生成一个完美 hash 函数，查询操作是 O(1)。