CreateArtTechnology / Blog

  • 背景工作中经常需要跟空间数据打交道,因此频繁使用一个工具类com.vividsolutions.jts.index.strtree.STRtree。STRtree类似于一个集合,向其插入一些带空间信息的数据后可以很便利地按范围查询空间数据,如下图示意。
    范围查询
    由于不清楚STRtree的查询实现逻辑,为探明原因及避免后续踩坑了解了一下,发现STRtree应用了非常精巧且应用广泛的空间索引结构R树(R-Tree)及优秀的批量加载算法STR。下文我们将从R树开始介绍,进一步了解STR算法,并说明一些STRtree相关的注意事项。
    R树是什么
    R树是用来做空间数据存储的树状数据结构。例如给地理位置,矩形和多边形这类多维数据建立索引。R树是由Antonin Guttman于1984年提出的。 …… 可以用它来回答“查找距离我2千米以内的博物馆”,“检索距离我2千米以内的所有路段”(然后显示在导航系统中)或者“查找(直线距离)最近的加油站”这类问题。R树还可以用来加速使用包括大圆距离在内的各种距离度量方式的最邻近搜索。——维基百科
    R树是一种层次数据结构,它是B树在k维空间上的自然扩展,因此和B树一样,R树是一种高度平衡树,在叶结点中包含指向实际数据对象的指针。
    ......

    共11张


  • 引言在生活和工作中经常会遇到一些需要资源分配的时候,例如
    公司发的礼物不喜欢,想跟其他人换在线扭蛋机的交换系统实现求职offer的选择高考投档系统实现
    其中1、2属于单边匹配,匹配由单边期望决定,即“买方”决定;3、4属于双边匹配问题,匹配过程需考虑“买卖双方”的期望。
    在通常情况下,我们期望获得一个尽可能合理而稳定的分配结果,使得最终整体收益最大化。
    罗伊德-沙普利(Lloyd S. Shapley)与他人提出了一系列市场的稳定配置机制,为博弈论和经济学领域做出了巨大的贡献,最终与艾尔文-罗斯(Alvin E. Roth)一同获得2012年获诺贝尔经济学奖。
    背景之前写过在业务中遇到了判定业务,而该判定业务实际上是一组给定对象与另一组给定对象的匹配问题:
    ......

    共11张


  • 背景几个月前在面试小米时,三面面试官问了一个问题:如何快速计算人群的朋友圈子?
    详细描述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张

  • 负载均衡算法介绍
     18     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算法介绍
     20     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可以是单调递增的,不会重复。多机情况下,每台机器的生成结果分布在不同空间,不会重复。
    ......