算法

TCP 三次握手和四次挥手

TCP 三次握手和四次挥手

D瓜哥
传输控制协议(英语:Transmission Control Protocol,缩写:TCP)是一种面向连接的、可靠的、基于字节流的传输层通信协议,由 IETF 的 RFC 793 定义。在简化的计算机网络 OSI 模型中,它完成第四层传输层所指定的功能。 毫不夸张地说,TCP 协议是目前整个互联网的基础。它解决了一系列的网络问题。带来的结果,就是协议本身非常复杂。考虑到文章篇幅问题,本文着重说明 TCP 建立连接时的三次握手过程和关闭连接时的四次挥手过程。 三次握手 Figure 1. TCP 三次握手 第一次握手(SYN=1, seq=x): 客户端发送一个 TCP 的 SYN 标志位置 1 的包,指明客户端打算连接的服务器的端口,以及初始序号 x,保存在包头的序列号(Sequence Number)字段里。 发送完毕后,客户端进入 SYN_SEND 状态。 第二次握手(SYN=1、seq=y;ACK=1、ACKnum=x+1): 服务器发回确认包(ACK)应答。即 SYN 标志位和 ACK 标志位均为 1。服务器端选择自己 ISN 序列号,放到包头的序列号(Sequence Number)字段里,同时将确认序号(Acknowledgement Number)设置为客户的 ISN 加 1,即 x+1。 发送完毕后,服务器端进入 SYN_RCVD 状态。 第三次握手(ACK=1,ACKnum=y+1) 客户端再次发送确认包(ACK),SYN 标志位为 0,ACK 标志位为 1,并且把服务器发来 ISN 的序号字段+1,放在确定字段中发送给对方,即数据段放写 y+1。
HikariCP 源码分析 --  FastList

HikariCP 源码分析 -- FastList

D瓜哥
在前面的文章 HikariCP 源码分析 — ConcurrentBag 中,D瓜哥分析了一下 HikariCP 中一个非常重要的数据结构 ConcurrentBag。 今天,继续再介绍 HikariCP 中另一个很关键的数据结构: FastList。 FastList 本身的实现非常简单,要理解它的奥秘,就需要结合 Java 原生集合类的 ArrayList 来比较性地看。 构造函数 先来对比一下两者的构造函数。先来看看 FastList: FastList public final class FastList<T> implements List<T>, RandomAccess, Serializable { private static final long serialVersionUID = -4598088075242913858L; private final Class<?> clazz; private T[] elementData; private int size; / * Construct a FastList with a default size of 32. * @param clazz the Class stored in the collection */ @SuppressWarnings("unchecked") public FastList(Class<?
Redis 核心数据结构(二)

Redis 核心数据结构(二)

D瓜哥
在上一篇文章: Redis 核心数据结构(1) 中,介绍了链表、ziplist、quicklist 数据结构。这篇文章,来介绍一下 skiplist、dict。 skiplist 跳跃表是一种有序数据结构,支持平均 O(logN)、最坏 O(N) 复杂度的节点查找;大部分情况效率可以和平衡树相媲美,实现却比平衡树简单。 跳跃表就是 Redis 中有序集合键的底层实现之一。 server.h typedef struct zskiplistNode { sds ele; double score; struct zskiplistNode backward; struct zskiplistLevel { struct zskiplistNode forward; unsigned long span; } level[]; } zskiplistNode; typedef struct zskiplist { struct zskiplistNode header, tail; unsigned long length; int level; } zskiplist; typedef struct zset { dict dict; zskiplist zsl; } zset; skiplist,顾名思义,首先它是一个list。实际上,它是在有序链表的基础上发展起来的。
Redis 核心数据结构(一)

Redis 核心数据结构(一)

D瓜哥
Redis 目前是使用最广泛的缓存中间件。其突出特点就是支持多种常见的数据结构。对比 JDK 集合类的实现,Redis 的实现表现出很多独到之处,很多地方设计得别具匠心。下面就来简要介绍一下。 linkedlist Redis 底层也有很多地方使用到 linkedlist,并且也是双向链表。 adlist.h typedef struct listNode { struct listNode *prev; struct listNode *next; void *value; } listNode; typedef struct listIter { listNode *next; int direction; } listIter; typedef struct list { listNode *head; listNode *tail; void *(*dup)(void *ptr); void (*free)(void *ptr); int (*match)(void *ptr, void *key); unsigned long len; } list; Redis 的 linkedlist 实现特点是: 双向:节点带有前后指针; 无环:首尾没有相连,所以没有构成环状;

负载均衡算法及实践

D瓜哥
前几天在看一个资料时,看到关于负载均衡算法的介绍。最近也在研究 Spring Cloud 和 Apache Dubbo 等微服务框架。正好负载均衡是微服务框架中一个很重要的知识点。就动手做个整理和总结。方便后续学习。 听朋友建议,这篇文章还可以在算法对比,客户端负载均衡与服务端负载均衡区分等两方面做些补充。这些内容后续再补充加入进来。 常见的负载均衡算法 轮询(Round Robin)法 轮询选择指的是从已有的后端节点列表中按顺序依次选择一个节点出来提供服务。 优点:试图做到请求转移的绝对均衡。实现简单,使用广泛。 加权轮询(Weighted Round Robin)法 实际使用中各个节点往往都带有不同的权重,所以一般都需要实现带权重的轮询选择。 权重高的被选中的次数多,权重低的被选中的次数少。 优点:是 轮询(Round Robin)法 改良版。适用于服务器配置不一致时,可以将配置好的服务器多干活,配置差的服务器少干活以使机器的负载达到相同的水平。 静态轮询(Static Round Robin)法 HAProxy 中实现的一个负载均衡算法。 没有后台服务器的限制,服务器启动时,修改权重也不会生效。增删服务器时,服务器准备就绪后,会立即加入到服务队列中。 随机(Random)法 通过随机函数,根据后端服务器列表的大小值来随机选择其中一台进行访问。由概率统计理论可以得知,随着调用量的增大,其实际效果越来越接近于平均分配流量到每一台后端服务器,也就是轮询的效果。 加权随机(Weighted Random)法 与加权轮询法类似,加权随机法也是根据后端服务器不同的配置和负载情况来配置不同的权重。不同的是,它是按照权重来随机选择服务器的,而不是顺序。 原地址哈希(IP Hashing)法 源地址哈希的思想是获取客户端访问的IP地址值,通过哈希函数计算得到一个数值,用该数值对服务器列表的大小进行取模运算,得到的结果便是要访问的服务器的序号。 优点:保证了相同客户端 IP 地址将会被哈希到同一台后端服务器,直到后端服务器列表变更。根据此特性可以在服务消费者与服务提供者之间建立有状态的 Session 会话。 URI 哈希(URI Hashing)法 HAProxy 中实现的一个负载均衡算法。支持部分 URI(问号之前)和完整 URI 两种模式。
HikariCP 源码分析 --  ConcurrentBag

HikariCP 源码分析 -- ConcurrentBag

D瓜哥
以前无意间搜资料了解到 HikariCP,一下子就被它的简洁代码和卓越性能吸引住了。以前也有翻过它的代码,但是不是很系统,最近再次翻阅,正好做些笔记,方便以后学习。 D瓜哥最近在学习 Java 并发知识。那就从 HikariCP 自定义的并发集合 ConcurrentBag 开始学习。 在 HikariCP 的 Wiki 中,有 Down the Rabbit Hole · ConcurrentBag 的章节来专门介绍 ConcurrentBag: ConcurrentBag 的灵感借鉴自 C# .NET 的 ConcurrentBag 类。但是实现却是完全不同的。这里的 ConcurrentBag 有如下特性: A lock-free design ThreadLocal caching Queue-stealing Direct hand-off optimizations 下面,通过代码来对此做个说明。 在 ConcurrentBag 类的定义中,声明了集合元素必须是 IConcurrentBagEntry 的子类。先来看看这个接口的定义: public interface IConcurrentBagEntry { int STATE_NOT_IN_USE = 0; int STATE_IN_USE = 1; int STATE_REMOVED = -1; int STATE_RESERVED = -2; boolean compareAndSet(int expectState, int newState); void setState(int newState); int getState(); } 接下来,看一下成员变量:

动态规划入门

D瓜哥
Tip 本篇文章是 D瓜哥 读《算法导论》的读书笔记。记录下来是为了方便整理思路,以便啃下“动态规划”这块骨头。 目前侧重记录书中关于“动态规划原理”的介绍。接下来会把书中的例子结合 Java 代码演绎一遍。后续会根据D瓜哥的学习和理解,逐步完善。最终希望达到通过这一篇文章,就能学会、理解动态规划。 山高水远,道阻且长,愿一起努力!  — 2020年01月23日 动态规划(dynamic programming)与分治方法相似,都是通过组合子问题的解来求解原问题(在这里,“programming”指的是一种表格法,并非编写计算机程序)。 分治方法将问题划分为互不相交的子问题,递归地求解子问题,再将它们的解组合起来,求出原问题的解。 动态规划应用于子问题重叠的情况,即不同的子问题具有公共的子子问题(子问题的求解是递归进行的,将其划分为更小的子子问题)。 在这种情况下,分治算法会做许多不必要的工作,它会反复地求解那些公共子问题。 动态规划算法对每个子子问题只求解一次,将其解保存在一个表格中,从而无需每次求解一个子子问题时都重新计算,避免了不必要的计算工作。 动态规划方法通常用来求解最优化问题(optimization problem)。 设计一个动态规划算法的步骤: 刻画一个最优解的结构特征。 递归地定义最优解的值。 计算最优解的值,通常采用自底向上的方法。 利用计算出的信息构造一个最优解。 算法原理 适合应用动态规划方法求解的最优化问题应该具备的两个要素:最优子结构和子问题重叠。 最优子结构 用动态规划方法求解最优化问题的第一步就是刻画最优解的结构。如果一个问题的最优解包含其子问题的最优解,则称此问题具有最优子结构性质。因此,某个问题是否适合应用动态规划算法,它是否具有最优子结构性质是一个好线索。 发掘最优子结构性质的通过模式 证明问题最优解的第一个组成部分是做出一个选择。做出这次选择会产生一个或多个待解的子问题。 对于一个给定问题,在其可能的第一步选择中,你假定已经知道哪种选择才会得到最优解。你现在并不关心这种选择具体是如何得到的,只是假定已经知道了这种选择。 给定可获得最优解的选择后,你确定这次选择会产生哪些子问题,以及如何最好地刻画子问题空间。 利用“剪切-粘贴”(cut-and-paste)技术证明:作为构造原问题最优解的组成部分,每个子问题的解就是它本身的最优解。证明这一点是利用反证法:假定子问题的解不是其自身的最优解,那么我们就可以从原问题的解中“剪切”掉这些非最优解,将最优解“粘贴”进去,从而得到原问题一个更优的解,这与最初的解是原问题最优解的前提假设锚段。