算法

Golang websocket结合一致性哈希算法构建高并发推送服务

1 场景介绍 web应用中,常有业务状态需要实时更新的场景。如一个较长的后台任务,从浏览器用户触发执行到执行完成可能需几十秒的时间,这时前端需隔几秒请求一次后台,查询任务执行进度。此种方式是长轮询的方式,是存在一定弊端的,增加了后台服务的负 …

阅读更多

k-d tree算法原理及实现

k-d tree即k-dimensional tree,常用来作空间划分及近邻搜索,是二叉空间划分树的一个特例。通常,对于维度为$k$,数据点数为$N$的数据集,k-d tree适用于$N\gg2^k$的情形。 1)k-d tree算法原理 …

阅读更多

一致性哈希算法与高可用集群代理

假定N为后台服务节点数,当前台携带关键字key发起请求时,我们通常将key进行hash后采用模运算(hash(key)%N)来将请求分发到不同的节点上。 对前台请求于后台无状态服务节点不敏感的场景而言,只要请求key具有一定的随机性,哪怕节 …

阅读更多

根据遍历结果反向构建树

业务中也许会遇到反向构建树的情形,如从外部工具获取到依赖关系、行政区划,组织架构等文本数据时,如何去反向构建树。我们以“获取到了树的深度遍历结果,然后将树结构构建出来,最后用JSON格式输出”,来模拟此类树的反向构建过程。本文采用Ruby作 …

阅读更多