Posts

“分布式协调组件” 常用的分布式协调组件有 全局功能数据存储/有功能的组件: K-V类: redis、memcache Zookeeper 消息队列 配置中心: Spring Cloud Config等 持久数据存储: MySQL MongoDB 分布式协调组件应用场景: (类比单机中多线程并发安全变量的操作) 分布式session 分布式计数器 分布式锁 分布式队列 先入先出队列 要等所有队列元素聚集之后才能统一安排执行的Barrier模型队列 分布式配置 分布式协调 / 通知 数据发布、订阅 软负载均衡: 域名 -> IP和端口号配置 命名服务: 在分布式环境中，上层应用需要一个全局唯一的名字，类似于数据库中的主键 集群管理: 集群监控 (进群运行时状态收集) 集群控制 (对集群进行操作和控制) Master选举 https://zhuanlan.zhihu.com/p/50901935

“CR3控制寄存器” CR3用来存放页目录表物理内存基地址，每当进程切换时，Linux 就会把下一个将要运行进程的页目录表物理内存基地址等信息存放到CR3寄存器中。 https://blog.csdn.net/SweeNeil/article/details/106171361

“分布式事务 2PC, 3PC, TCC” 数据库事务的概念 在讲述分布式事务的概念之前，我们先来回顾下事务相关的一些概念。 事务的基本概念: 就是一个程序执行单元，里面的操作要么全部执行成功，要么全部执行失败，不允许只成功一半另外一半执行失败的事情发生。例如一段事务代码做了两次数据库更新操作，那么这两次数据库操作要么全部执行成功，要么全部回滚。 事务的基本特性: 我们知道事务有4个非常重要的特性，即我们常说的 (ACID) 。 Atomicity (原子性) :是说事务是一个不可分割的整体，所有操作要么全做，要么全不做；只要事务中有一个操作出错，回滚到事务开始前的状态的话，那么之前已经执行的所有操作都是无效的，都应该回滚到开始前的状态。 Consistency (一致性) : 是说事务执行前后，数据从一个状态到另一个状态必须是一致的，比如A向B转账 (A、B的总金额就是一个一致性状态) ，不可能出现A扣了钱，B却没收到的情况发生。 Isolation (隔离性) : 多个并发事务之间相互隔离，不能互相干扰。关于事务的隔离性，可能不是特别好理解，这里的并发事务是指两个事务操作了同一份数据的情况；而对于并发事务操作同一份数据的隔离性问题，则是要求不能出现脏读、幻读的情况，即事务A不能读取事务B还没有提交的数据，或者在事务A读取数据进行更新操作时，不允许事务B率先更新掉这条数据。而为了解决这个问题，常用的手段就是加锁了，对于数据库来说就是通过数据库的相关锁机制来保证。 Durablity (持久性) : 事务完成后，对数据库的更改是永久保存的，不能回滚。 关于数据库事务的基本概念大家可以去网上搜一下，这里只是给大家回顾下事务的基本概念及特性，诸如事务并发问题、事务隔离级别等大家如有遗忘可以去回顾下 (tips: 面试经常会问到的问题哦) 。 3 什么是分布式事务 以上内容我们回顾了下事务的基本概念，那么分布式事务又是个什么概念呢？它与数据库事务之间又有什么区别呢？ 其实分布式事务从实质上看与数据库事务的概念是一致的，既然是事务也就需要满足事务的基本特性 (ACID) ，只是分布式事务相对于本地事务而言其表现形式有很大的不同。举个例子，在一个JVM进程中如果需要同时操作数据库的多条记录，而这些操作需要在一个事务中，那么我们可以通过数据库提供的事务机制 (一般是数据库锁) 来实现。 而随着这个JVM进程 (应用) 被拆分成了微服务架构，原本一个本地逻辑执行单元被拆分到了多个独立的微服务中，这些微服务又分别操作不同的数据库和表，服务之间通过网络调用。 举个例子: 服务A收到一笔购物下单请求后，需要调用服务B去支付，支付成功则处理购物订单为待发货状态，否则就需要将购物订单处理为失败状态。 (如图所示) 640?wx_fmt=png 在上面这个例子中会不会出现服务B支付成功了，但是由于网络调用的问题没有通知到服务A，导致用户付了钱，但是购物订单无法显示支付成功的状态呢？ 答案是这种情况是普遍存在的，因为服务B在处理成功后需要向服务A发送网络请求，而这个过程是极有可能失败的。那么如何确保“服务A->服务B”这个过程能够组成一个事务，要么全部成功、要么全部失败呢？而这就是典型的需要通过分布式事务解决的问题。 分布式事务是为了解决微服务架构 (形式都是分布式系统) 中不同节点之间的数据一致性问题。这个一致性问题本质上解决的也是传统事务需要解决的问题，即一个请求在多个微服务调用链中，所有服务的数据处理要么全部成功，要么全部回滚。当然分布式事务问题的形式可能与传统事务会有比较大的差异，但是问题本质是一致的，都是要求解决数据的一致性问题。 而分布式事务的实现方式有很多种，最具有代表性的是由Oracle Tuxedo系统提出的XA分布式事务协议。XA协议包括两阶段提交 (2PC) 和三阶段提交 (3PC) 两种实现，接下来我们分别来介绍下这两种实现方式的原理。 两阶段提交 (2PC) 分布式事务的解决方案 两阶段提交/XA 两阶段提交，顾名思义就是要分两步提交。存在一个负责协调各个本地资源管理器的事务管理器，本地资源管理器一般是由数据库实现，事务管理器在第一阶段的时候询问各个资源管理器是否都就绪？如果收到每个资源的回复都是 yes，则在第二阶段提交事务，如果其中任意一个资源的回复是 no, 则回滚事务。 大致的流程: 第一阶段 (prepare) : 事务管理器向所有本地资源管理器发起请求，询问是否是 ready 状态，所有参与者都将本事务能否成功的信息反馈发给协调者； 第二阶段 (commit/rollback): 事务管理器根据所有本地资源管理器的反馈，通知所有本地资源管理器，步调一致地在所有分支上提交或者回滚。 ...

“ent” ent 是由 Facebook Connectivity 团队创建的 ORM 框架。迫于 Go 社区中缺少能够像图一样查询数据的工具,同时也缺少 100% 类型安全的 ORM https://entgo.io/

Pulsar Pulsar [ˈpʌlsɑːr] Apache Pulsar (孵化器项目）是一个企业级的发布订阅 (pub-sub）消息系统，最初由 Yahoo 开发，并于 2016 年底开源 https://www.infoq.cn/article/2017/11/apache-pulsar-brief-introduction

IPA, International Phonetic Alphabet, 国际音标 元音字母, 辅音字母 5个元音字母和21个辅音字母组成。 5个元音字母分别为：a[ei]、e[i:]、i[ ai]、o[eu]、u[ju:]; 元音, 辅音 48个英语音标表：20个元音+28个辅音 一、单元音12个 短元音： [i] [ə] [ɒ] [u] [Λ] [æ] [e] 长元音： [i:] [ə:] [ɔ:] [u:] [ɑ:] 二、双元音8个 [ai] [ei] [ɔi] [au] [əu] [iə] [eə] [uə] 三、清浊成对的辅音10对 清辅音：[p] [t] [k] [f] [θ] [s] [tr] [ts] [∫] [t∫] 浊辅音：[b] [d] [g] [v] [ð] [z] [dr] [dz] [ʒ] [dʒ] 四、其他辅音8个 [h] [m ] [n] [ŋ] [l] [r] [w] [j] the在元音前读[ði],在辅音前读[ðə]，而元辅音的判断不是第一个单词，而是第一个音素，或说发音。 元音 [æ], half, sat, laugh, cat [ɑ], lock, what, hard, article [ʌ] cut, son, flood ...

celery https://github.com/celery/celery celery 是一个基于分布式消息传输的异步任务队列，它专注于实时处理，同时也支持任务调度。它的执行单元为任务（task），利用多线程， 如 Eventlet，gevent等，它们能被并发地执行在单个或多个职程服务器（worker servers）上。任务能异步执行（后台运行）或同步执行（等待任务完成）。 # install rabbitmq https://wangyue.dev/rabbitmq # install celery pip install celery # 添加用户跟密码, rabbitmqctl add_user test test123 rabbitmqctl add_user user0 password0 # 添加虚拟主机 rabbitmqctl add_vhost test_vhost rabbitmqctl add_vhost vhost0 # 为用户添加标签, rabbitmqctl set_user_tags test test_tag rabbitmqctl set_user_tags user0 tag0 # 设置用户权限, rabbitmqctl set_permissions -p test_vhost test ".*" ".*" ".*" rabbitmqctl set_permissions -p vhost0 user0 ".*" ".*" ".*" # run celery server celery -A tasks worker --loglevel=INFO ———————————————— 版权声明：本文为CSDN博主「吴秋霖」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。 原文链接：https://blog.csdn.net/qiulin_wu/article/details/106119757 ...

rabbitmq nerdctl # nerdctl, network: host nerdctl run -d --hostname host0 --name rabbitmq --network host --memory 2g -p 15672:15672 -p 5672:5672 -e RABBITMQ_SERVER_ADDITIONAL_ERL_ARGS="-rabbit consumer_timeout 50000" rabbitmq:3.8.18-management # docker with timeout config docker run -d --hostname host0 --name rabbitmq -p 15672:15672 -p 5672:5672 -e RABBITMQ_SERVER_ADDITIONAL_ERL_ARGS="-rabbit consumer_timeout 50000" rabbitmq:3.8.18-management # 查看 版本 rabbitmqctl status docker run -d --hostname host0 --name rabbitmq -p 15672:15672 -p 5672:5672 rabbitmq:3.11.10-management docker run -d --hostname host0 --name rabbitmq -p 15672:15672 -p 5672:5672 rabbitmq:3.8.18-management podman run -d --hostname host0 --name rabbitmq -p 15672:15672 -p 5672:5672 rabbitmq:3.11.10-management rabbitmqctl list_connections rabbitmqctl list_queues rabbitmqctl list_channels rabbitmqctl list_users rabbitmqctl cluster_status # 查看 consumer_timeout 的值 rabbitmqctl eval 'application:get_env(rabbit, consumer_timeout).' 管理页面 使用：http://宿主ip:15672 访问管理页面，默认用户名密码：guest/guest ...

“sasl” SASL - 简单认证和安全层 身份验证是很多C/S模式应用协议的通用需求，为了避免每个协议都单独实现一套验证逻辑，SASL(Simple Authentication and Secure Layer)被提出了, 它定位成为基于可靠连接的应用协议提供身份验证和数据安全服务的通用框架。SASL定义了通用的身份验证信息交换的流程, 并且包含一系列验证机制。这些验证机制完成具体的身份验证逻辑。这样，SASL就成为了一个将应用协议和验证机制相连接的抽象层，如下图所示。 +----+ +----+ +----+ +-------------------+ |SMTP| |LDAP| |XMPP| |Other protocols ...| +--+-+ +--+-+ +--+-+ +--+----------------+ | | | | | | | | ------+--------+---------+--------+------------------ SASL abstraction layer ------+--------+---------+--------+------------------ | | | | | | | | +-----+--+ +--+---+ +--+--+ +--+-----------------+ |EXTERNAL| |GSSAPI| |PLAIN| |Other machanisms ...| +--------+ +------+ +-----+ +--------------------+ 任何应用协议都可以使用任何验证机制，而具体使用哪个机制则由应用协议的客户端和服务器进行协商。 分别以”C:”和”S:”代表客户端和服务端，SASL规定的验证信息交换的基本流程为: C: 请求验证交换 S: 最初的挑战码 C: 最初的响应消息 <额外的挑战码/响应消息> S: 身份验证结果 根据机制不同，流程略有差异。 ...

“tesla” 基础版辅助驾驶 (BAP/AP 增强版自动辅助驾驶 (EAP) EAP Enhanced Autopilot，增强型自动驾驶 和完全自动驾驶 (FSD) FSD Full Self-Driving 完全自动驾驶 EAP 自动辅助导航驾驶: 自动驶入和驶出高速公路匝道或立交桥岔路口，超过行驶缓慢的车辆。 自动辅助变道: 在高速公路上自动辅助变换车道。 自动泊车: 平行泊车与垂直泊车。 智能召唤: 在合适的场景下，停在车位的车辆会响应您的召唤，驶出车位并前往您所在的位置。 FSD NOA Navigate on Autopilot自动辅助导航驾驶 (简称NOA) 启动车辆即启动, 开启该选项后，在具备NOA使用条件的路段，Model 3将自动开启NOA功能。 根据速度变道 (即自动超车) 特斯拉官方称之为速控变道，在行驶中存在两种普遍情况，一种是本车道内行驶时前方有慢车阻挡，需要变道超车；另一种是正常行驶中，有慢车从前方进入到本车道，此时需要变道以保持车速。该功能有三种变道模式: 柔和、普通、极速。柔和可以理解为以最保守的变道方式，极速则最激进的变道模式。 要求变道确认 开启这一功能后，当NOA驾驶中，Model 3判断需要变线时，将提醒驾驶员打转向灯进行确认，然后才能执行变线操作。而选择“否”，关闭这一功能后，Model 3将自动变线，而不再要求打转向灯进行确认。 变道提醒 开启后，在自动变道时，Model 3会通过蜂鸣或振动方式提醒驾驶员即将进行变道操作。

“中间件, Middleware” 中间件 中间件一词的由来中间件这个术语第一次出现是 1968 年在德国加尔米施帕滕基兴举办的 NATO 软件工程大会 结束后发表的一份报告中。这届大会正式确定了软件工程(Software Engineering)的概念，同时还探讨了软件设计、生产和分发等主题。 中间件的定义 中间件 (英语: Middleware) ，又译中间件、中介层，是一类提供系统软件和应用软件之间连接、便于软件各部件之间的沟通的软件，应用软件可以借助中间件在不同的技术架构之间共享信息与资源。中间件位于客户机服务器的操作系统之上，管理着计算资源和网络通信。 – 维基百科什么不是中间件我们按照类别来看一些经常会遇到的一些不是中间件的概念- 业务平台不是中间件，业务平台是从服务的视角抽象的能同时支撑多个业务，业务之间的信息能形成交互和增强的平台。- 营销工具不是中间件，营销工具是直接作用于最终消费者用户的软件或者插件服务。- 二方/三方工具包不是中间件，二方/三方工具包是在各种场景的程序开发过程中沉淀的一些常用工具类(功能)的集合，包含于软件代码本身。- SaaS 不是中间件，SaaS(Software as a Service) 更多的是一种软件交付模式，无需用户安装，通过网络在线访问的一种服务模式。- PaaS 不是中间件，PaaS(Platform as a Service) 将软件研发的平台做为一种服务，提供软件部署平台(强调的是屏蔽系统和软件细节的runtime平台)。评判关键从定义可以总结出评判的几个地方 性质: 中间件是软件。 作用层级: 系统软件和应用软件之间、软件各部件之间；管理客户机与系统软件之间的计算资源和网络通信。 服务对象: 中间件为应用软件服务，应用软件为最终用户服务，最终用户并不直接使用中间件。 中间件的好处 中间件能给客户带来什么？为上层应用软件的开发提供便捷的、开箱即用的服务交互和计算的能力，缩短开发周期；屏蔽底层runtime的差异；节省应用本身的系统资源，减少运行成本。 中间件分类 什么时候使用中间件 基于中间件的定义我们知道中间件是连接软件与系统之间的服务，那么我们什么时候使用了中间件，在哪些地方用到了中间件了。我们不妨假设一个http请求过程来窥视一番。当你在浏览器中输入一个网址时，它会通过 DNS 解析到目标服务注册的公网IP地址请求到达目标服务的 web 反向代理服务器 Tengine 之后，经过一定的过滤转发到目标服务A上服务A通过 RPC框架 Dubbo 请求服务B的结果做中间计算，并且从 Tair 缓存中读取计算因子，计算结果服务A接着使用 Druid 通过 TDDL 写入计算结果到 MySQL Master 节点然后返回结果异步过程中 Canal 通过模拟 Binlog 主从复制的原理，迅速将这条 Binlog 消费并下发到消息队列 RocketMQ服务C通过 RocketMQ 消费到事件之后，通过配置中心 ConfigServer 拉取到的策略进行对应策略的事件处理。这个过程中我们使用了一系列的中间件来协同各个微服务完成整个流程，如web反向代理服务器 Tengine、RPC框架 Dubbo、缓存 Tair、连接池 Driud、数据库代理层 TDDL、Binlog 同步工具 Canal、消息队列 RocketMQ、配置中心 ConfigServer。 ...

负载均衡 负载均衡 load balancing 何为负载均衡？顾名思义就是让系统的负载根据一定的规则均衡地分配在所有参与工作的服务器上，从而最大限度地提升系统整体的运行效率。 LVS、Nginx 当前大多数的互联网系统都使用了服务器集群技术，集群是将相同服务部署在多台服务器上构成一个集群整体对外提供服务，这些集群可以是 Web 应用服务器集群，也可以是数据库服务器集群，还可以是分布式缓存服务器集群等等。 在实际应用中，在 Web 服务器集群之前总会有一台负载均衡服务器，负载均衡设备的任务就是作为 Web 服务器流量的入口，挑选最合适的一台 Web 服务器，将客户端的请求转发给它处理，实现客户端到真实服务端的透明转发。 最近几年很火的「云计算」以及分布式架构，本质上也是将后端服务器作为计算资源、存储资源，由某台管理服务器封装成一个服务对外提供，客户端不需要关心真正提供服务的是哪台机器，在它看来，就好像它面对的是一台拥有近乎无限能力的服务器，而本质上，真正提供服务的，是后端的集群。 LVS、Nginx、HAProxy 是目前使用最广泛的三种软件负载均衡软件。 一般对负载均衡的使用是随着网站规模的提升根据不同的阶段来使用不同的技术。具体的应用需求还得具体分析，如果是中小型的 Web 应用，比如日 PV 小于1000万，用 Nginx 就完全可以了；如果机器不少，可以用 DNS 轮询，LVS 所耗费的机器还是比较多的；大型网站或重要的服务，且服务器比较多时，可以考虑用 LVS。 目前关于网站架构一般比较合理流行的架构方案: Web 前端采用 Nginx/HAProxy+Keepalived 作负载均衡器；后端采用 MySQ L数据库一主多从和读写分离，采用 LVS+Keepalived 的架构。 LVS LVS 是 Linux Virtual Server 的简称，也就是 Linux 虚拟服务器。现在 LVS 已经是 Linux 标准内核的一部分，从 Linux2.4 内核以后，已经完全内置了 LVS 的各个功能模块，无需给内核打任何补丁，可以直接使用 LVS 提供的各种功能。 LVS 自从1998年开始，发展到现在已经是一个比较成熟的技术项目了。 LVS 的体系结构 LVS 架设的服务器集群系统有三个部分组成: (1) 最前端的负载均衡层，用 Load Balancer 表示 (2) 中间的服务器集群层，用 Server Array 表示 ...

“Java NIO Channel, buffer” Channel Channel Characteristics Java NIO Channel Classes buffer 什么是缓冲区？ 缓冲区类型 缓冲区内部细节 NIO Buffer Characteristics How to Read from NIO Buffer How to Write to NIO Buffer Java NIO 读写文件实例程序 Channel Java NIO中，channel用于数据的传输。类似于传统IO中的流的概念。channel的两端是buffer和一个entity，不同于IO中的流，channel是双向的，既可以写入，也可以读取。而流则是单向的，所以channel更加灵活。我们在读取数据或者写入数据的时候，都必须经过channel和buffer，也就是说，我们在读取数据的时候，先利用channel将IO设备中的数据读取到buffer，然后从buffer中读取，我们在写入数据的时候，先将数据写入到buffer，然后buffer中的数据再通过channel传到IO设备中。 image.png 我们知道NIO的特点就是将IO操作更加类似于底层IO的流程。 我们可以通过底层IO的机制更好的理解channel。 所有的系统I/O都分为两个阶段: 等待就绪和操作。 等待就绪就是从IO设备将数据读取到内核中的过程。 操作就是将数据从内核复制到进程缓冲区的过程。 channel就可以看作是IO设备和内核区域的一个桥梁，凡是与IO设备交互都必须通过channel，而buffer就可以看作是内核缓冲区。这样整个过程就很好理解了。 我们看一下读取的过程 先从IO设备，网卡或者磁盘将内容读取到内核中，对应于NIO就是从网卡或磁盘利用channel将数据读到buffer中 然后就是内核中的数据复制到进程缓冲区，对应于就是从buffer中读取数据 写入的过程则是: 先从进程将数据写到内核中，对应于就是进程将数据写入到buffer中， 然后内核中的数据再写入到网卡或者磁盘中，对应于就是，buffer中的数据利用channel传输到IO设备中。 image.png 以上其实就是NIO基本的利用channel和buffer进行读取和写入的流程。 Channel Characteristics 与传统IO中的流不同，channel是双向的，可读可写 channel从buffer中读取数据，写入数据也是先写入到buffer channel可以实现异步读写操作 channel可以设置为阻塞和非阻塞的模式 非阻塞模式意味着，当读不到数据或者缓冲区已满无法写入的时候，不会把线程睡眠 只有socket的channel可以设置为非阻塞模式，文件的channel是无法设置的。文件的IO一定是阻塞的 如果是文件channel的话，channel可以在channel之间传输数据 Java NIO Channel Classes channel主要有两大类，四个具体的类 FileChannel 文件的读写是不可以设置为非阻塞模式 SocketChannel 根据tcp和udp，服务端和客户端，又可以分为, SocketChannel, ServerSocketChannel and DatagramChannel.它们是可以设置为非阻塞模式的 buffer 什么是缓冲区？ Buffer 是一个对象， 它包含一些要写入或者刚读出的数据。 在 NIO 中加入 Buffer 对象，体现了新库与原 I/O 的一个重要区别。在面向流的 I/O 中，您将数据直接写入或者将数据直接读到 Stream 对象中。 在 NIO 库中，所有数据都是用缓冲区处理的。在读取数据时，它是直接读到缓冲区中的。在写入数据时，它是写入到缓冲区中的。任何时候访问 NIO 中的数据，您都是将它放到缓冲区中。 缓冲区实质上是一个数组。通常它是一个字节数组，但是也可以使用其他种类的数组。但是一个缓冲区不 仅仅 是一个数组。缓冲区提供了对数据的结构化访问，而且还可以跟踪系统的读/写进程。 ...

“SkipList, 跳表, 跳跃表” SkipList SkipList(跳表)这种数据结构是由 William Pugh 于1990年在在 Communications of the ACM June 1990, 33(6) 668-676 发表了Skip lists: a probabilistic alternative to balanced trees，在其中详细描述了他的工作。由论文标题可知，SkipList 的设计初衷是作为替换 平衡树 的一种选择。 我们都知道，AVL树有着严格的O(logN)的查询效率，但是由于插入过程中可能需要多次旋转，导致插入效率较低，因而才有了在工程界更加实用的红黑树。 但是红黑树有一个问题就是在并发环境下使用不方便，比如需要更新数据时，SkipList 需要更新的部分比较少，锁的东西也更少，而红黑树有个平衡的过程，在这个过程中会涉及到较多的节点，需要锁住更多的节点，从而降低了并发性能。 SkipList还有一个优势就是实现简单，SkipList的实现只花了2个小时，而红黑树，我可能得2天。 时隔将近三十多年，SkipList 这种数据结构仍在许多途径有用武之地，比如Redis, 还有Google的著名项目 Bigtable, leveldb 原理及实现 其实跳表就是在普通单向链表的基础上增加了一些索引，而且这些索引是分层的，从而可以快速地查的到数据。 比如我们要查找key为19的结点，那么我们不需要逐个遍历，而是按照如下步骤: 从header出发，从高到低的level进行查找，先索引到9这个结点，发现9 < 19,继续查找(然后在level==2这层)，查找到21这个节点，由于21 > 19, 所以结点不往前走，而是level由2降低到1 然后索引到17这个节点，由于17 < 19, 所以继续往后，索引到21这个结点，发现21>19, 所以level由1降低到0 在结点17上，level==0索引到19,查找完毕。 如果在level==0这层没有查找到，那么说明不存在key为19的节点，查找失败 https://zhuanlan.zhihu.com/p/33674267 skiplist, 红黑树 skiplist 的复杂度和红黑树一样，而且实现起来更简单。 在并发环境下红黑树在插入和删除时需要 rebalance，性能不如跳表。 http://www.cnblogs.com/xuqiang/archive/2011/05/22/2053516.html

“平衡二叉树, 平衡树, AVL树” 平衡树, 平衡二叉树 AVL树 树堆 (Treap) 伸展树 (Splay tree) 红黑树 (Red–black tree) 加权平衡树 (Weight balanced tree) 2-3树 AA树 替罪羊树 AVL树 AVL树是带有平衡条件的二叉查找树，一般是用平衡因子差值判断是否平衡并通过旋转来实现平衡，左右子树树高不超过1，和红黑树相比，AVL树是严格的平衡二叉树，平衡条件必须满足 (所有节点的左右子树高度差的绝对值不超过1) 。不管我们是执行插入还是删除操作，只要不满足上面的条件，就要通过旋转来保持平衡，而旋转是非常耗时的，由此我们可以知道AVL树适合用于插入与删除次数比较少，但查找多的情况 局限性 由于维护这种高度平衡所付出的代价比从中获得的效率收益还大，故而实际的应用不多，更多的地方是用追求局部而不是非常严格整体平衡的红黑树。当然，如果应用场景中对插入删除不频繁，只是对查找要求较高，那么AVL还是较优于红黑树。 AVL 树是一种平衡二叉树，得名于其发明者的名字 ( Adelson-Velskii 以及 Landis) 。 1: 定义 父节点的左子树和右子树的高度之差不能大于1，也就是说不能高过1层，否则该树就失衡了，此时就要旋转节点，在 编码时，我们可以记录当前节点的高度，比如空节点是-1，叶子节点是0，非叶子节点的height往根节点递增，比如在下图 中我们认为树的高度为h=2。 旋转 节点再怎么失衡都逃不过4种情况，下面我们一一来看一下。 ① 左左情况 (左子树的左边节点) 我们看到，在向树中追加“节点1”的时候，根据定义我们知道这样会导致了“节点3"失衡，满足“左左情况“，可以这样想，把这 棵树比作齿轮，我们在“节点5”处把齿轮往下拉一个位置，也就变成了后面这样“平衡”的形式，如果用动画解释就最好理解了。 ② 右右情况 (右子树的右边节点) 同样，”节点5“满足”右右情况“，其实我们也看到，这两种情况是一种镜像，当然操作方式也大同小异，我们在”节点1“的地方 将树往下拉一位，最后也就形成了我们希望的平衡效果。 ③左右情况 (左子树的右边节点) 从图中我们可以看到，当我们插入”节点3“时，“节点5”处失衡，注意，找到”失衡点“是非常重要的，当面对”左右情况“时，我们将 失衡点的左子树进行"右右情况旋转"，然后进行”左左情况旋转“，经过这样两次的旋转就OK了，很有意思，对吧。 ④右左情况(右子树的左边节点) 这种情况和“情景3”也是一种镜像关系，很简单，我们找到了”节点15“是失衡点，然后我们将”节点15“的右子树进行”左左情况旋转“， 然后进行”右右情况旋转“，最终得到了我们满意的平衡。 添加 如果我们理解了上面的这几种旋转，那么添加方法简直是轻而易举，出现了哪一种情况调用哪一种方法而已。 删除 删除方法跟添加方法也类似，当删除一个结点的时候，可能会引起祖先结点的失衡，所以在每次”结点“回退的时候计算结点高度。 https://www.cnblogs.com/huangxincheng/archive/2012/07/22/2603956.html https://blog.csdn.net/u010899985/article/details/80981053 https://cloud.tencent.com/developer/article/1177129

“二叉树” 二叉树 (Binary Tree) 二叉树 (Binary Tree) 是包含n个节点的有限集合，该集合或者为空集 (此时，二叉树称为空树) ，或者由一个根节点和两棵互不相交的、分别称为根节点的左子树和右子树的二叉树组成。 二叉树中的节点至多包含两棵子树，分别称为左子树和右子树，而左子树和右子树又分别至多包含两棵子树。由上述的定义，二叉树的定义是一种递归的定义。 @startuml circle 1 circle 2 circle 3 circle 4 circle 5 circle 7 circle 10 circle 11 circle 14 1 -- 2 1 -- 3 2 -- 4 2 -- 5 3 -- 7 5 -- 10 5 -- 11 7 -- 14 @enduml 满二叉树 Full Binary Tree 对于一棵二叉树，如果每一个非叶子节点都存在左右子树，并且二叉树中所有的叶子节点都在同一层中，这样的二叉树称为满二叉树。 ...

“redis pipeline” why pipeline ? Redis 客户端与 server 的请求/响应模型 前面的文章 Redis 底层协议RESP详解 ，介绍到 redis 客户端与 redis-server 交互通信，采用的 TCP 请求/响应模型; 我们通过 Redis 客户端执行命令，如set key value，客户端遵循RESP协议，将命令的协议串发送给redis-server执行，redis-server执行完成后再同步返回结果。 手写Redis客户端-实现自己的Jedis 对这一过程进行了重点分析，并遵循RESP实现了自己简易版的Redis客户端。 Redis客户端与server通信，使用的是客户端-服务器 (CS) 模式；每次交互，都是完整的请求/响应模式。 这意味着通常情况下一个请求会遵循以下步骤: 客户端连接服务端，基于特定的端口，发送一个命令，并监听Socket返回，通常是以阻塞模式，等待服务端响应。 服务端处理命令，并将结果返回给客户端。 很显然，我们使用jedis或lettuce执行Redis命令，每次都是建立socket连接，并等待返回。 每个命令底层建立TCP连接的时间是省不掉的，即使我们都是在内网使用Redis，内网快但请求/响应的往返时间是不会减少的。 当需要对一组kv进行批量操作时，这组命令的耗时=sum(N*(建立连接时间+发送命令、返回结果的往返时间RTT))，随批量操作的key越多，时间累加呈线性增长。 顺理成章的，就出现了像数据库连接池等池化思想的衍生，redis连接也进行“池化”，如JedisPool。 JedisPool就足够了？ 池化connection后，每次执行命令都从池子里“借”，用完之后再将connection“还”到池子。只是节省了创建TCP连接的时间； 当需要对一组kv进行批量操作时，JedisPool池子里的connection连接、极端情况都被用完了，怎么办？ ——需要等待JedisPool池里有可复用的connection才能继续执行； redis.clients.jedis.exceptions.JedisConnectionException: Could not get a resource from the pool … Caused by: java.util.NoSuchElementException: Timeout waiting for idle object at org.apache.commons.pool2.impl.GenericObjectPool.borrowObject(GenericObjectPool.java:449) 如果在指定的等待时间内没有等到idle空闲连接，就报异常了。 尽管使用了池化、将connection进行复用，但不可避免的带来其他问题: https://jjlu521016.github.io/2018/12/09/JedisPool常见问题.html 除了池化的connection会被瞬间用完，Redis官网还给出了另外一个性能损耗的原因: It’s not just a matter of RTT https://redis.io/topics/pipelining 虽然池化的connection，节省了建立连接的时间，但多条命令(发送命令到sever、server返回结果)分别执行多次socket网络IO，涉及到read()和write() syscall系统调用，这意味着从用户态到内核态。上下文切换是巨大的速度损失。 ...

“Cuckoo filter, 布谷过滤器” 过滤器系列 (二) —— Cuckoo filter 这一篇讲的是布谷过滤器(cuckoo fliter)，这个名字来源于更早发表的布谷散列(cuckoo hash)，尽管我也不知道为什么当初要给这种散列表起个鸟名=_= 由于布谷过滤器本身的思想就源自于布谷散列，那么我们就从布谷散列开始说它的设计思想。产生布谷散列表的一个重要背景是人们对于球盒问题的分析: 给定N个球，随机的放在N个盒子里，在装球最多的盒子里，球的个数的期望是多少？答案是Θ(logN/loglogN)，这个问题其实就是散列表装填因子为1时的情况分析。后来有一天，人们发现: 每次放球的时候，如果随机选择两个盒子，将球放到当时较空的那个盒子里，那么这个期望就变成了Θ(loglogN)，这个界小于之前的界，这给了布谷散列表作者启发。 一个布谷散列表通常有两张 (一般来说) 表，分别有一个对应的Hash函数，当有新的项插入的时候，它会计算出这个项在两张表中对应的两个位置，这个项一定会被存在这两个位置之一，而具体是哪一个却不确定。 下图是一个布谷散列表的初始化示意图: image 现在我们假设有一些项要存入散列表，其每个项都有其对应的两个位置，先插入第一项A image 由于插入A的时候其两个候选位置 (0,2) 都没有占用，所以选择第一张表或者是第二张表都可以，我们在这里默认先选择第一张表，然后插入第二项B image 我们看到原来的A的位置被B占用，而A被“踢”到它的备选位置表二的2号位置上了，这就是当发生位置冲突时，布谷散列表的处理逻辑，后来的数据项将会把之前占用的项踢到另一个位置上。我们接下来插入第三项C image 没有冲突，顺利搞定，接着插入D image D成功的把C踢走了，其实看到这里读者应该在猜想，会不会有一种情况，即被踢走的数据的另一个备选位置也被占用了，这样怎么办？答案是继续踢，一个踢一个，直到大家都找到自己合适的归宿为止。那么如果发现出现了循环怎么办？答案是GG，这代表布谷散列表走到了极限 image 插入E image 这里就发生了多次替换的情况，F代替了E，E代替了A，A代替了B，B找到了空余的位子 读者可以考虑一下，如果这个时候要想插入一个“G”，其备选位置是1,2，这样的话会出现什么情况？ 好了，布谷散列表大概介绍完了，现在该布谷过滤器了。布谷过滤器的主要也是通过布谷散列来实现的，其主要变化是: 1.我们不将原来的数据完整的存进来，作为过滤器，当然要省点空间，选用的办法设计一个指纹，将比较大的原数据变成了一个个指纹串，这样就大大节省了空间。 2.由于第一点所说，存储的不是原数据，那么在替换位置的时候，我们需要再次计算原来的数据的备选位置，这样一来布谷散列表的方法就失效了。在这里，作者设计了一个方法，他将两个Hash函数变成了一个Hash函数，第一张表的备选位置是Hash(x),第二张表的备选位置是Hash(x)⊕hash(fingerprint(x))，即第一张表的位置与存储的指纹的Hash值做异或运算。这样做的优点就是不用再另外存储元素的备选位置，在替换时，可以直接用异或来计算出其另一个备选位置。 (读者可以想想如何通过表二的位置计算出元素在表一中的位置) 3.插入时，优先选择空位置，而不是尽可能的踢走其他元素。 插入伪代码如下: Copy Algorithm 1: Insert(x) f = fingerprint(x) i1 = hash(x) i2 = i1 xor hash(f) if bucket[i1] or bucket[i2] has an empty entry then //只要有空位就先插入空位里 add f to that bucket return Done i = randomly pick i1 or i2 for n=0;n<MaxNumKicks;++n randomly select an entry e from bucket[i]; swap f and the fingerprint stored in entry e; i = i xor hash(f) if bucket[i] has an empty entry then add f to bucket[i] return Done return Failure // 已经出现循环情况了 查找伪代码如下: ...

Vim 光标移动 搜索结果之间跳转 文件之间移动 Vim 最大的特征与最大的困难就是键盘操作，所以快速移动光标是 Vim 的最基本技能。光标移动可以配合其他快捷键使用，比如 y, x, d, v，更好地掌握了光标移动也就更好地掌握了其他编辑技能。 上下左右：以字符为单位 进入 Vim 的 normal 模式（如果你在 visual 模式或者 insert 模式，可以按若干次 Esc 回到 normal 模式）。 h 向左移动一个字符。 j 向下移动一个字符。 k 向上移动一个字符。 l 向右移动一个字符。 和其他快捷键一样，可以配合数字来移动多个字符，比如 5l 向左移动 5 个字符。 以单词为单位移动 多数情况下单词移动比字符移动更加高效，比如要走到当前变量名前加一个 let。 w 移动到下一个单词的词首。 b 移动到上一个单词的词首。 e 移动到下一个单词的结尾。 单词移动同样支持数字前缀，比如 4w 可以向后移动 4 个单词。此外大写的 W, B, E 具有同样的功能，只不过小写用标点符号来分隔单词，大写用空格来分隔单词，更适合在代码里移动。 以行为单位移动 ^ 移动到行首第一个词的首字母。 | 移动到行首第一个字符。 $ 移动到行尾。 j 移动到下一行。 k 移动到上一行。 :10 移动光标到文件第 10 行。可以 :set number 来让 vim 显示行号。 gg 移动到文件首行。 G 移动到文件尾行。 上下行移动的命令同样可以加数字，比如 10j 向下移动 10 行。 ...

“延时队列” https://zhuanlan.zhihu.com/p/266156267 延迟队列 首先，队列这种数据结构相信大家都不陌生，它是一种先进先出的数据结构。普通队列中的元素是有序的，先进入队列中的元素会被优先取出进行消费； 延时队列相比于普通队列最大的区别就体现在其延时的属性上， 普通队列的元素是先进先出，按入队顺序进行处理， 而延时队列中的元素在入队时会指定一个延迟时间，表示其希望能够在经过该指定时间后处理。从某种意义上来讲，延迟队列的结构并不像一个队列，而更像是一种以时间为权重的有序堆结构。 应用场景 我在开发业务需求时遇到的使用场景是这样的，用户可以在小程序中订阅不同的微信或者 QQ 的模板消息，产品同学可以在小程序的管理端新建消息推送计划，当到达指定的时间节点的时候给所有订阅模板消息的用户进行消息推送。 这里不太懂…. 把要发送的模板消息加到延时队列里？ 如果仅仅是服务单一的小程序，那也许起个定时任务，或者甚至人工的定时去执行能够最便捷最快速的去完成这项需求，但我们希望能够抽象出一个消息订阅的模块服务出来给所有业务使用，这时候就需要一种通用的系统的解决方案，这时候便需要使用到延迟队列了。 除了上述我所遇到的这样的典型的需求以外，延迟队列的应用场景其实也非常的广泛，比如说以下的场景: 新建的订单，如果用户在 15 分钟内未支付，则自动取消。 公司的会议预定系统，在会议预定成功后，会在会议开始前半小时通知所有预定该会议的用户。 安全工单超过 24 小时未处理，则自动拉企业微信群提醒相关责任人。 用户下单外卖以后，距离超时时间还有 10 分钟时提醒外卖小哥即将超时。 对于数据量比较少并且时效性要求不那么高的场景，一种比较简单的方式是轮询数据库，比如每秒轮询一下数据库中所有数据，处理所有到期的数据，比如如果我是公司内部的会议预定系统的开发者，我可能就会采用这种方案，因为整个系统的数据量必然不会很大并且会议开始前提前 30 分钟提醒与提前 29 分钟提醒的差别并不大。 但是如果需要处理的数据量比较大实时性要求比较高，比如淘宝每天的所有新建订单 15 分钟内未支付的自动超时，数量级高达百万甚至千万，这时候如果你还敢轮询数据库怕是要被你老板打死，不被老板打死估计也要被运维同学打死。 按时间戳排序，每秒查询15分钟之内创建的订单? 这种场景下，就需要使用到我们今天的主角 —— 延迟队列了。延迟队列为我们提供了一种高效的处理大量需要延迟消费消息的解决方案。那么话不多说，下面我们就来看一下几种常见的延迟队列的解决方案以及他们各自的优缺点。 实现方案 Redis ZSet 我们知道 Redis 有一个有序集合的数据结构 ZSet，ZSet 中每个元素都有一个对应 Score，ZSet 中所有元素是按照其 Score 进行排序的。 那么我们可以通过以下这几个操作使用 Redis 的 ZSet 来实现一个延迟队列: 入队操作: ZADD KEY timestamp task, 我们将需要处理的任务，按其需要延迟处理时间作为 Score 加入到 ZSet 中。Redis 的 ZAdd 的时间复杂度是O(logN)，N是 ZSet 中元素个数，因此我们能相对比较高效的进行入队操作。 起一个进程定时 (比如每隔一秒) 通过 ZRANGEBYSCORE 方法查询 ZSet 中 Score 最小的元素，具体操作为: ZRANGEBYSCORE KEY -inf +inf limit 0 1 WITHSCORES ...