首页 文章 精选 留言 我的

精选列表

搜索[分布式调度],共10000篇文章
优秀的个人博客,低调大师

为自己搭建一个分布式 IM 系统二【从查找算法聊起】

前言 最近这段时间确实有点忙,这篇的目录还是在飞机上敲出来了的。 言归正传,上周更新了 cim 第一版;没想到反响热烈,最高时上了 GitHub Trending Java 版块的首位,一天收到了 300+ 的 star。 现在总共也有 1.3K+ 的 star,有几十个朋友参加了测试,非常感谢大家的支持。 在这过程中也收到一些 bug 反馈,feature 建议;因此这段时间我把一些影响较大的 bug 以及需求比较迫切的 feature 调整了,本次更新的 v1.0.1 版本: 客户端超时自动下线。 新增 AI 模式。 聊天记录查询。 在线用户前缀模糊匹配。 下面谈下几个比较重点的功能。 客户端超时自动下线 这个功能涉及到客户端和服务端的心跳设计,比较有意思,也踩了几个坑;所以准备留到下次单独来聊。 AI 模式 大家应该还记得这个之前刷爆朋友圈的 估值两个一个亿的 AI 核心代码。 和我这里的场景再合适不过了。 于是我新增了一个命令用于一键开启 AI 模式,使用情况大概如下。 欢迎大家更新源码体验,融资的请私聊我🤣。 聊天记录 聊天记录也是一个比较迫切的功能。 使用命令 :q 关键字 即可查询与个人相关的聊天记录。 这个功能其实比较简单,只需要在消息发送及接收消息时保存即可。 但要考虑的一点是,这个保存消息是 IO 操作,不可避免的会有耗时;需要尽量避免对消息发送、接收产生影响。 异步写入消息 因此我把消息写入的过程异步完成,可以不影响真正的业务。 实现起来也挺简单,就是一个典型的生产者消费者模式。 主线程收到消息之后直接写入队列,另外再有一个线程一直源源不断的从队列中取出数据后保存聊天记录。 大概的代码如下: 写入消息的同时会把消费消息的线程打开: 而最终存放消息记录的策略,考虑后还是以最简单的方式存放在客户端,可以降低复杂度。 简单来说就是根据当前日期+用户名写入到磁盘里。 当客户端关闭时利用线程中断的方式停止了消费队列的线程。 这点的设计其实和 logback 写日志的方式比较类似,感兴趣的可以去翻翻 logback 的源码,更加详细。 回调接口 至于收到其他客户端发来的消息时则是利用之前预留的消息回调接口来写入日志。 收到消息后会执行自定义的回调接口。 于是在这个回调方法中实现写入逻辑即可,当后续还有其他的消息处理逻辑时也能在这里直接添加。 当处理逻辑增多时最好是改为责任链模式,更加清晰易维护。 查找算法 接下来是本文着重要讨论的一个查找算法,准确的说是一个前缀模糊匹配的算法。 实现的效果如下: 使用命令 :qu prefix 可以按照前缀的方式搜索用户信息。 当然在命令行中其实意义不大,但是在移动端中确是比较有用的。类似于微信按照用户名匹配: 因为后期打算出一个移动端 APP,所以就先把这个功能实现了。 从效果也看得出来:就是按照输入的前缀匹配字符串(目前只支持英文)。 在没有任何限制的条件下最快、最简单的实现方式可以直接把所有的字符串存放在一个容器中 (List、Set),查询时则挨个遍历;利用 String.startsWith("prefix") 进行匹配。 但这样会有几个问题: 存储资源比较浪费,不管是 list 还是 Set 都会有额外的损耗。 查询效率较低,需要遍历集合后再遍历字符串的 char 数组(String.startsWith 的实现方式)。 字典树 基于以上的问题我们可以考虑下: 假设我需要存放 java,javascript,jsp,php 这些字符串时在 ArrayList 中会怎么存放? 很明显,会是这样完整的存放在一个数组中;同时这个数组还可能存在浪费,没有全部使用完。 但其实仔细观察这些数据会发现有一些共同特点,比如 java,javascript 有共同的前缀 java;和 jsp 有共同的前缀 j。 那是否可以把这些前缀利用起来呢?这样就可以少存储一份。 比如写入 java,javascript 这两个字符串时存放的结构如下: 当再存入一个 jsp 时: 最后再存入 jsf 时: 相信大家应该已经看明白了,按照这样的存储方式可以节省很多内存,同时查询效率也比较高。 比如查询以 jav 开头的数据,只需要从头结点 j 开始往下查询,最后会查询到 ava 以及 script 这两个个结点,所以整个查询路径所经历的字符拼起来就是查询到的结果java+javascript。 如果以 b 开头进行查询,那第一步就会直接返回,这样比在 list 中的效率高很多。 但这个图还不完善,因为不知道查询到啥时候算是匹配到了一个之前写入的字符串。 比如在上图中怎么知道 j+ava 是一个我们之前写入的 java 这个字符呢。 因此我们需要对这种是一个完整字符串的数据打上一个标记: 比如这样,我们将 ava、script、p、f 这几个节点都换一个颜色表示。表明查询到这个字符时就算是匹配到了一个结果。 而查到 s 这个字符颜色不对,代表还需要继续往下查。 比如输入关键字 js 进行匹配时,当它的查询路径走到 s 这里时判断到 s 的颜色不对,所以不会把 js 作为一个匹配结果。而是继续往下查,发现有两个子节点 p、f 颜色都正确,于是把查询的路径 jsp 和 jsf 都作为一个匹配结果。 而只输入 j,则会把下面所有有色的字符拼起来作为结果集合。 这其实就一个典型的字典树。 具体实现 下面则是具体的代码实现,其实算法不像是实现一个业务功能这样好用文字分析;具体还是看源码多调试就明白了。 谈下几个重点的地方吧: 字典树的节点实现,其中的 isEnd 相当于图中的上色。 利用一个 Node[] children 来存放子节点。 为了可以区分大小写查询,所以子节点的长度相当于是 26*2。 写入数据 这里以一个单测为例,写入了三个字符串,那最终形成的数据结构如下: 图中有与上图有几点不同: 每个节点都是一个字符,这样树的高度最高为52。 每个节点的子节点都是长度为 52 的数组;所以可以利用数组的下标表示他代表的字符值。比如 0 就是大 A,26 则是小 a,以此类推。 有点类似于之前提到的布隆过滤器,可以节省内存。 debug 时也能看出符合上图的数据结构: 所以真正的写入步骤如下: 把字符串拆分为 char 数组,并判断大小写计算它所存放在数组中的位置 index。 将当前节点的子节点数组的 index 处新增一个节点。 如果是最后一个字符就将新增的节点置为最后一个节点,也就是上文的改变节点颜色。 最后将当前节点指向下一个节点方便继续写入。 查询总的来说要麻烦一些,其实就是对树进行深度遍历;最终的思想看图就能明白。 所以在 cim 中进行模糊匹配时就用到了这个结构。 字典树的源码在此处: https://github.com/crossoverJie/cim/blob/master/cim-common/src/main/java/com/crossoverjie/cim/common/data/construct/TrieTree.java 其实利用这个结构还能实现判断某个前缀的单词是否在某堆数据里、某个前缀的单词出现的次数等。 总结 目前 cim 还在火热内测中(虽然群里只有20几人),感兴趣的朋友可以私聊我拉你入伙☺️ 再没有新的 BUG 产生前会着重把这些功能完成了,不出意外下周更新 cim 的心跳重连等机制。 完整源码: https://github.com/crossoverJie/cim 如果这篇对你有所帮助还请不吝转发。

优秀的个人博客,低调大师

分布式架构高可用架构_Keepalived+Nginx实现高可用Web负载均衡

参考视频教程:http://www.roncoo.com/course/view/7036eec04d734b2f95e544562e24c7c4 一、场景需求 二、Keepalived 简要介绍Keepalived 是一种高性能的服务器高可用或热备解决方案,Keepalived 可以用来防止服务器单点故障的发生,通过配合 Nginx 可以实现 web 前端服务的高可用。Keepalived 以 VRRP 协议为实现基础,用 VRRP 协议来实现高可用性(HA)。VRRP(VirtualRouterRedundancy Protocol)协议是用于实现路由器冗余的协议,VRRP 协议将两台或多台路由器设备虚拟成一个设备,对外提供虚拟路由器 IP(一个或多个),而在路由器组内部,如果实际拥有这个对外 IP 的路由器如果工作正常的话就是 MASTER,或者是通过算法选举产生,MASTER 实现针对虚拟路由器 IP 的各种网络功能,如 ARP 请求,ICMP,以及数据的转发等;其他设备不拥有该虚拟 IP,状态是 BACKUP,除了接收 MASTER 的VRRP 状态通告信息外,不执行对外的网络功能。当主机失效时,BACKUP 将接管原先 MASTER 的网络功能。VRRP 协议使用多播数据来传输 VRRP 数据,VRRP 数据使用特殊的虚拟源 MAC 地址发送数据而不是自身网卡的 MAC 地址,VRRP 运行时只有 MASTER 路由器定时发送 VRRP 通告信息,表示 MASTER 工作正常以及虚拟路由器 IP(组),BACKUP 只接收 VRRP 数据,不发送数据,如果一定时间内没有接收到 MASTER 的通告信息,各 BACKUP 将宣告自己成为 MASTER,发送通告信息,重新进行 MASTER 选举状态。 三、方案规划 四、安装 Nginx 1、安装编译Nginx 所需的依赖包 Connecting to 192.168.1.121:22...Connection established.To escape to local shell, press 'Ctrl+Alt+]'.Last login: Sat Apr 16 17:55:20 2016 from 192.168.1.61[root@edu-proxy--01 ~]#yum install gcc gcc-c++ make automake autoconf libtool pcre pcre-devel zlib zlib-devel openssl openssl-devel 2、上传Nginx(nginx-1.6.2.tar.gz)到/usr/local/src目录 3、编译安装Nginx [root@edu-proxy--01 ~]#cd /usr/local/src/[root@edu-proxy--01 src]# lskeepalived-1.2.18.tar.gz nginx-1.6.2.tar.gz[root@edu-proxy--01 src]# tar -zxvf nginx-1.6.2.tar.gz [root@edu-proxy--01 src]# cd nginx-1.6.2[root@edu-proxy--01 nginx-1.6.2]#./configure --prefix=/usr/local/nginx [root@edu-proxy--01 nginx-1.6.2]#make && make install [root@edu-proxy--01 nginx-1.6.2]#vi /usr/local/nginx/conf/nginx.conf user root;worker_processes 1;#error_log logs/error.log;#error_log logs/error.log notice;#error_log logs/error.log info;#pid logs/nginx.pid;events { worker_connections 1024;}http { include mime.types; default_type application/octet-stream; #log_format main '$remote_addr - $remote_user [$time_local] "$request" ' # '$status $body_bytes_sent "$http_referer" ' # '"$http_user_agent" "$http_x_forwarded_for"'; #access_log logs/access.log main; sendfile on; #tcp_nopush on; #keepalive_timeout 0; keepalive_timeout 65; #gzip on; server { listen 88; server_name localhost; #charset koi8-r; #access_log logs/host.access.log main; location / { root html; index index.html index.htm; } #error_page 404 /404.html; # redirect server error pages to the static page /50x.html error_page 500 502 503 504 /50x.html; location = /50x.html { root html; } }} 修改 Nginx欢迎首页内容(用于后面测试,用于区分两个节点的 Nginx): vi /usr/local/nginx/html/index.html 192.168.1.121 中的标题加1 Welcome to nginx!1 192.168.1.122 中的标题加2 Welcome to nginx!2 5、系统防火墙打开对应的端口88 vi /etc/sysconfig/iptables -A INPUT -m state --state NEW -m tcp -p tcp --dport88-j ACCEPT service iptables restart 6、测试Nginx 是否安装成功 /usr/local/nginx/sbin/nginx -t nginx: the configuration file /usr/local/nginx/conf/nginx.conf syntax is oknginx: configuration file /usr/local/nginx/conf/nginx.conf test is successful 7、启动Nginx /usr/local/nginx/sbin/nginx 重启 /usr/local/nginx/sbin/nginx -s reload 8、设置Nginx 开机启动 vi /etc/rc.local 加入 /usr/local/nginx/sbin/nginx 分别访问两个nginx nginx1 2.nginx2 五、安装 Keepalived(http://www.keepalived.org/download.html) 1、上传或下载keepalived(keepalived-1.2.18.tar.gz)到/usr/local/src目录 2、解压安装 cd /usr/local/src tar -zxvf keepalived-1.2.18.tar.gz cd keepalived-1.2.18 ./configure --prefix=/usr/local/keepalived make && make install 3、将keepalived 安装成Linux 系统服务: 因为没有使用 keepalived的默认路径安装(默认是/usr/local),安装完成之后,需要做一些工作 复制默认配置文件到默认路径 mkdir /etc/keepalived cp /usr/local/keepalived/etc/keepalived/keepalived.conf /etc/keepalived/ 复制 keepalived服务脚本到默认的地址 cp /usr/local/keepalived/etc/rc.d/init.d/keepalived /etc/init.d/ cp /usr/local/keepalived/etc/sysconfig/keepalived /etc/sysconfig/ ln -s /usr/local/sbin/keepalived /usr/sbin/ ln -s /usr/local/keepalived/sbin/keepalived /sbin/ 设置 keepalived服务开机启动 chkconfig keepalived on 4、修改Keepalived 配置文件 注意,如果linux用的网卡是eth0,interface就要写成eth1,用的是eth1就要写成eth1 (1) MASTER 节点配置文件(192.168.1.121) vi /etc/keepalived/keepalived.conf ! Configuration File for keepalivedglobal_defs { router_id edu-proxy-01}vrrp_script chk_nginx { script "/etc/keepalived/nginx_check.sh" interval 2 weight -20}vrrp_instance VI_1 { state MASTER interface eth0 virtual_router_id 51 mcast_src_ip192.168.1.121 priority 100 nopreempt advert_int 1 authentication { auth_type PASS auth_pass 1111 } track_script { chk_nginx } virtual_ipaddress { 192.168.1.120 } BACKUP节点配置 (192.168.1.122) ! Configuration File for keepalivedglobal_defs { router_id edu-proxy-02}vrrp_script chk_nginx { script "/etc/keepalived/nginx_check.sh" interval 2 weight -20}vrrp_instance VI_1 { state BACKUP interface eth0 virtual_router_id 51 mcast_src_ip192.168.1.122 priority 90 advert_int 1 authentication { auth_type PASS auth_pass 1111 } track_script { chk_nginx } virtual_ipaddress { 192.168.1.120 }} 5.编写Nginx状态检测脚本/etc/keepalived/nginx_check.sh(keepalived.conf中配置) 脚本要求:如果nginx停止运行,尝试启动,如果无法启动则杀死本机的keepalived进程,keepaied将虚拟ip绑定到BACKUP机器上,内容如下 #!/bin/bashA=`ps -C nginx –no-header |wc -l`if [ $A -eq 0 ];then /usr/local/nginx/sbin/nginx sleep 2 if [ `ps -C nginx --no-header |wc -l` -eq 0 ];then killall keepalived fi fi 保存后给脚本授邓权限 chmod -x /etc/keepalived/nginx_check.sh 6.启动keepalived serivce keepalived start 我们在cmd中查看arp 在edu-proxy-01 [root@edu-proxy--01 keepalived]# ip add 这里我们访问192.168.1.120:88 7.Keepalived+nginx的高可用测试 (1)关闭192.168.1.121的Nginx,Keepalived会将它重新启动 [root@edu-proxy--01 keepalived]# /usr/local/nginx/sbin/nginx -s stop (2)关闭192.168.1.121中的Keepalived,VIP会切换到192.168.1.122中 [root@edu-proxy--01 keepalived]#service keepalived stop root@edu-proxy-02 keepalived]#ip add 查看虚拟ip 说明此时VIP已经漂移到主机192.168.1.122上了 再能过VIP来访问Nginx集群,访问到的也是192.168.1.122 (3)重新启动192.168.1.121中的Keepalived,VIP又会切回到192.168.1.121中来 [root@edu-proxy--01 keepalived]# service keepalived start 查看虚拟机IP ip add Keepalived启动后,网络接口上又会创建出VIP192.168.1.120 Keepalived服务管理命令: 停止: service keepalived stop 启动: service keepalived start 重启: service keepalived restart 查看状态: service keepalived status 其他参考资料: keepalived之vrrp_script总结:http://my.oschina.net/hncscwc/blog/158746 keepalived双机热备实现故障时发送邮件通知:http://www.2cto.com/os/201407/317795.html 基于keepalived实现VIP转移,lvs,nginx的高可用;:http://www.tuicool.com/articles/eu26Vz 扫码关注龙果官方公众号

资源下载

更多资源
Mario

Mario

马里奥是站在游戏界顶峰的超人气多面角色。马里奥靠吃蘑菇成长,特征是大鼻子、头戴帽子、身穿背带裤,还留着胡子。与他的双胞胎兄弟路易基一起,长年担任任天堂的招牌角色。

Nacos

Nacos

Nacos /nɑ:kəʊs/ 是 Dynamic Naming and Configuration Service 的首字母简称,一个易于构建 AI Agent 应用的动态服务发现、配置管理和AI智能体管理平台。Nacos 致力于帮助您发现、配置和管理微服务及AI智能体应用。Nacos 提供了一组简单易用的特性集,帮助您快速实现动态服务发现、服务配置、服务元数据、流量管理。Nacos 帮助您更敏捷和容易地构建、交付和管理微服务平台。

Spring

Spring

Spring框架(Spring Framework)是由Rod Johnson于2002年提出的开源Java企业级应用框架,旨在通过使用JavaBean替代传统EJB实现方式降低企业级编程开发的复杂性。该框架基于简单性、可测试性和松耦合性设计理念,提供核心容器、应用上下文、数据访问集成等模块,支持整合Hibernate、Struts等第三方框架,其适用范围不仅限于服务器端开发,绝大多数Java应用均可从中受益。

WebStorm

WebStorm

WebStorm 是jetbrains公司旗下一款JavaScript 开发工具。目前已经被广大中国JS开发者誉为“Web前端开发神器”、“最强大的HTML5编辑器”、“最智能的JavaScript IDE”等。与IntelliJ IDEA同源,继承了IntelliJ IDEA强大的JS部分的功能。

用户登录
用户注册