海量 URL 排重算法

原创
2013/11/15 12:51
阅读数 4K

早上看到@皇甫君威朋友提出一个问题 :检查用户名重复,当数据是海量,怎么保证速度;看大家讨论的很积极;这个问题应用场景很广;在各种系统和软件中:用户名、产品名、URL等等都需要排重;下面我就以URL 排重来说明一下这个问题;希望对朋友有帮助。

论题假设:

假设只有两台8G 内存的机器。总共会有6亿个URL(每个url长度约为100; 总共长为600亿;大约需要60个G 的空间); 现在有一URL; 需要算法得出,系统中是否存在此URL;如果不存在、就保存到系统中。

使用传统方法直接在数据库建索引:查询会很慢、而且如果多个查询进来;这个方案就死了。

如果使用hash md5(URL) 保存到缓存: 6亿* 18 /1024/1024/1024  ~= 10个G 。单个机器这么大的缓存系统。得使用分布式缓存系统,而且速度而很大影响;新记录的插入、查询压力也很大。

那,如何合理利用这16个G的缓存系统;进行排重运算呢?

第一步:我们在每台机器缓存中建立10000个hash表;那么每个hash 表就只保存 6W条记录;

第二步:我们使用一致性哈希算法,确定URL指向那个hash表 A

第三步:在指定的hash表A中查询URL是否存在,如果不存在、直接将URL 插入hash表A

以上理论实现了URL的快速排重;至于实现代码,下次附上;

kpages 中的python 代码

# -*- coding -*-
"""
    author comger@gmail.com
    一致性哈希算法
    提供分布式缓存、数据库等负载均衡的解决算法
"""
from hashlib import md5
from bisect import bisect_right

class ConsistentHash(object):
    """
    算法思路:
    1. 在N个机器中、每台M个节点、N*M 个节点形成节点环
    2. 计算每个机器拥有的节点Node
    3. 新内容key添加时,get_node(key)获取key被分配的node;及get_host(key)获取key 被分配到的机器
    
    * 节点的引入:保存每台机器负载均衡
    """
    def __init__(self, hosts, replicas = 10):
        self._hoss = {}
        self._ring = []
    
    def _build(self, hosts, replicas):
        for host in hosts:
            for i in xrange(relicas):
                key = "{0}_{1}".format(host,i)
                hsh = self._hash(key)
                
                self._hosts[str(hsh)] = host
                self._ring.insert(bisect_right(self._ring, hsh), hsh)


    def _hash(self,s):
        """
        md5 取模运算
        """
        return hash(md5(s).digest()) % 10000

    
    def get_node(self, key):
        """
        获取key 将分配的节点位置
        """
        hsh = self._hash(key)
        index = bisect_right(self._ring, hsh)
        if index >= len(self._ring): index = 0

        return self._ring[index]

    def get_host(self, key):
        """
        获取key 将被分配到的机器
        """
        return self._hosts(str(self.get_node(key)))

    
    




展开阅读全文
打赏
0
38 收藏
分享
加载中
过来学习一下
2014/07/09 16:17
回复
举报
comger博主

引用来自“java10001”的评论

引用来自“well”的评论

为什么不用 bloom filter?

我也建议使用这个。

这只是基本算法,各种实现都可以的
2014/01/15 08:13
回复
举报

引用来自“well”的评论

为什么不用 bloom filter?

我也建议使用这个。
2014/01/15 00:50
回复
举报
comger博主

引用来自“九月”的评论

用数据库一样的很快 PgSQL hash索引

可以测试对比一下。
2013/11/15 20:34
回复
举报
comger博主

引用来自“well”的评论

为什么不用 bloom filter?

原理有点相似、但这个效率和准确率会比较高。
2013/11/15 20:33
回复
举报
用数据库一样的很快 PgSQL hash索引
2013/11/15 20:17
回复
举报
为什么不用 bloom filter?
2013/11/15 19:26
回复
举报
希望楼主尽快放上代码分享,谢谢
2013/11/15 18:37
回复
举报
更多评论
打赏
8 评论
38 收藏
0
分享
返回顶部
顶部