这是一个创建于 3335 天前的主题，其中的信息可能已经有所发展或是发生改变。
需求
想在内存里面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
zhicheng 2015-03-25 18:27:38 +08:00 via Android  1
|
 |
2
GeekGao 2015-03-25 19:15:59 +08:00 1
直接存到Redis、ssdb是很快的。
分组存成: group:[Name] => [Uniq Number of Group] 分组的 [Uniq Number of Group]:[Full Domain Hash] => [A record] |
 |
3
lincanbin 2015-03-25 20:12:50 +08:00 1
数据量真少，可以直接存MySQL里作数据持久化，然后用Memcached加一层key-value的临时缓存。
|
 |
4
yadam OP @zhicheng 使用用户IP查找所在分组的话有啥好方法没?
我现在是这样: 红黑树存储网络号, 将用户IP从偏移1开始左移, 从树里面看是否存在, 直到找到, 感觉有点儿拧巴. 另外一个想法就是模仿dpdk的lpm库 |
|
5
zhicheng 2015-03-26 10:51:36 +08:00 via Android
关键词 “trie 树”。
如果量比较小，或者数据库比较详细，直接 hash 表按位查就行了，最多查 32 次没找到。 如果IP数据库不需要修改，可以生成一个完美 hash 函数，查询操作是 O(1)。 |
Select Language