CreateArtTechnology / Blog

  • 背景几个月前在面试小米时,三面面试官问了一个问题:如何快速计算人群的朋友圈子?
    详细描述A与B是朋友,C与D是朋友,E与F是朋友,F与A是朋友,那么我们可以计算出这个朋友圈子 ABEF 和圈子 CD即输入为(A, B) (C, D) (E, F) (F, A),输出为(A, B, E, F)和(C, D)其实这个问题很容易用逻辑推断,只需要利用归并的思想,将多个小圈子逐步合并为大圈子就可以了。但是在深入分析时,会发现其中有很多的坑:
    合并是个复杂的过程,如第一趟遍历合并(E, F)与(F, A),第二趟合并(A, B)与(E, F, A)…… 在极端情况下可能要经历多次循环遍历,时间复杂度为O(n^2)计算集合交集也是一个复杂的过程,每次合并过程中可能需要计算集合1中每个元素在集合2中是否存在,综合第1条复杂度粗略估计整体可能达到O(n^3)数据量较大时矩阵计算空间复杂度很高,S(n^2)
    类似的问题可以推广到很多场景,比如如何将大规模的有向边转为有向无环图,如何计算两种商品之间存在关联……
    刚好,近期的工作就遇到了一个类似的问题:描述:
    集合中有一些点,附带其关联点信息,即(dot -> referDotId);dot带有时间戳修改其中一个点时,需要同时修改这个集合中的所有直接或间接关联点;referDot不一定都在集合中,即关联双方均在集合中的记录点比较稀疏,直接导致高时间复杂度的计算会非常得不偿失
    ......

    共9张

  • 负载均衡算法介绍
     9     2019-05-13 20:19:24

    背景负载均衡的概念实在太普遍了,从Nginx、Haproxy到Dubbo、Thrift、Hessian等到处都能看到,就不多介绍了。
    常用负载均衡算法轮询和加权轮询轮询比较简单,在一个Server列表中请求会按顺序打到不同服务器上。加权轮询也比较简单,即Server列表中权重高的出现的次数更多,参考资料中有提到加权轮询应当注意分散权重高的Server在列表中出现的位置,比如在{a:5, b:1, c:1}的情况下{a, a, b, a, c, a, a}列表会比{a, a, a, a, a, b, c}合理。
    优点
    基本可以保证每个Server负载绝对均衡或加权均衡
    缺点
    请求和处理请求的Server无关,要另外维护Session状态并发情况下需要考虑对下标修改的线程安全问题
    ......


  • 背景近期部门业务遭到分布式拒绝服务攻击(Distributed Denial of Service, DDoS),正常情况下单服务峰值qps约为1200,服务异常期间单服务qps约为3500,导致正常用户无法访问服务。
    现象与原因
    正常用户访问出现白页Tomcat运行正常,AccessLog记录的响应时间提高,Tomcat的Http线程池(最大线程数400)耗尽GC频繁
    业务层有爬虫识别机制,对访问频率过高的IP进行了限制,但对一些知名爬虫和合作方爬虫白名单放行。知名爬虫包括百度、搜狗、各种主流手机浏览器(他们内部做了一些特殊转化)。但是攻击者使用了几千个IP,且UA等特征伪造了知名爬虫的特征,因此我们只能做到将其判断为爬虫,但无法与正常爬虫区分开,也就无法做到针对性的屏蔽。一旦无法针对性屏蔽,放行的爬虫会占用正常用户的资源(比如线程池),导致正常用户访问异常。
    临时策略由于无法从来源区分合法与非法的爬虫,只能另辟蹊径,减少爬虫占用的资源。当爬虫请求过来时,不走任何正常业务逻辑,直接返回异常响应码,减少响应时间。爬虫响应时间减少后,对爬虫请求的处理时间占总的请求处理时间比例下降,Tomcat压力有所减轻。最终上线的临时策略是对所有爬虫返回403响应,无论是否是知名爬虫。
    但是这个策略仍然存在问题:
    ......


  • Snowflake算法介绍
     12     2019-03-15 19:00:15

    算法描述Snowflake算法本身非常简单,一张图即可表示:
    Snowflake算法生成的64bit-id组成
    1bit 始终为0,保证生成的id是正数41bit 时间戳,可以保证生成的id是局部递增10bit 工作机器id,可保证不同机器生成的id分布在不同的区间,绝不重复12bit 序列号,保证单一时间单位内生成的id不重复
    Snowflake的优点算法简单,易实现,易定制几乎使用位操作就可以完成计算。工作机器id可使用6bit,序列号可以使用16bit,单机理论生成总id数会更多,很好定制。
    生成的id局部递增这一点由时间戳和序列号保证。但是多机结果不是单调递增的。
    全局唯一单机情况下每台机器生成的id可以是单调递增的,不会重复。多机情况下,每台机器的生成结果分布在不同空间,不会重复。
    ......