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

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

现在注册

已注册用户请登录

• 请不要在回答技术问题时复制粘贴 AI 生成的内容

这是一个创建于 3566 天前的主题，其中的信息可能已经有所发展或是发生改变。

需求

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

域名使用哈希, 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

5 条回复 • 2015-03-26 10:51:36 +08:00

zhicheng

2015-03-25 18:27:38 +08:00 via Android

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

GeekGao

2015-03-25 19:15:59 +08:00

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

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

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

lincanbin

2015-03-25 20:12:50 +08:00

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

yadam

2015-03-26 10:30:59 +08:00

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

zhicheng

2015-03-26 10:51:36 +08:00 via Android

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