算法

细说编码与字符集

细说编码与字符集

D瓜哥
文章还没写完,提前放出防止出现 404。稍后慢慢更新,敬请期待: 细说编码与字符集 - "地瓜哥"博客网 文章还没写完,提前放出防止出现 404。稍后慢慢更新,敬请期待: 细说编码与字符集 - "地瓜哥"博客网 文章还没写完,提前放出防止出现 404。稍后慢慢更新,敬请期待: 细说编码与字符集 - "地瓜哥"博客网 前段时间要研究 Hessian 编码格式,为了搞清楚 Hessian 对字符串的编码,就顺路查了好多编码和字符集的工作,理清了很多以前模糊的知识点。下面整理一下笔记,也梳理一下自己的思路和理解。 ASCII 码 计算机起源于美国,他们对英语字符与二进制位之间的对应关系做了统一规定,并制定了一套字符编码规则,这套编码规则被称为 American Standard Code for Information Interchange,简称为 ASCII 编码 其实,ASCII 最早起源于电报码。最早的商业应用是贝尔公司的七位电传打字机。后来于 1963 年发布了该标准的第一版。在网络交换中使用的 ASCII 格式是在 1969 年发布的,该格式在 2015 年发展成为互联网标准。点击 RFC 20: ASCII format for network interchange,感受一下 1969 年的古香古色。 ASCII 编码一共定义了128个字符的编码规则,用七位二进制表示(0x00 - 0x7F), 这些字符组成的集合就叫做 ASCII 字符集。完整列表如下: ASCII 码可以说是现在所有编码的鼻祖。 编码乱战及 Unicode 应运而生 ASCII 编码是为专门英语指定的编码标准,但是却不能编码英语外来词。比如 résumé,其中 é 就不在 ASCII 编码范围内。
Raft 论文摘要(二)

Raft 论文摘要(二)

D瓜哥
在上一篇文章中,通过阅读 《In Search of an Understandable Consensus Algorithm》 前三节的内容,对论文的大致内容做了简介,简单说明了一下 Replicated state machines 的用途以及 Paxos 本身存在的问题。 4. Designing for understandability several goals in designing Raft: it must providea complete and practical foundation for system building; it must be safe under all conditions and available under typical operating conditions; it must be efficient for common operations. Our most important goal — and most difficult challenge — was understandability. 从这里可以看出,Raft 设计的初衷就是为了易于理解和便于构建。 There were numerous points in the design of Raft where we had to choose among alternative approaches.
Raft 论文摘要(一)

Raft 论文摘要(一)

D瓜哥
前一段时间,在一次开组会的时候,给小组成员简单介绍了一下 Raft 协议。大概四年前读过 Raft 的论文,这次分享的时候,好多好多细节都忘了。所以,再次把 《In Search of an Understandable Consensus Algorithm》 这篇论文找出来,重读一遍,做个笔记和摘要,方便后续学习和复习。 Abstract Raft is a consensus algorithm for managing a replicated log. 开篇摘要就点出了 Raft 的特点: Raft 是一种管理复制日志的共识算法。 In order to enhance understandability, Raft separates the key elements of consensus, such as leader election, log replication, and safety, and it enforcesa stronger degree of coherency to reduce the number of states that must be considered. 为了增强可理解性,Raft 将共识分解成几个关键元素,例如 Leader 选举,日志复制,以及安全性等;同时,为了降低需要考虑的状态的数量,还强制实施了更强的一致性。
TCP 三次握手和四次挥手

TCP 三次握手和四次挥手

D瓜哥
传输控制协议(英语:Transmission Control Protocol,缩写:TCP)是一种面向连接的、可靠的、基于字节流的传输层通信协议,由 IETF 的 RFC 793 定义。在简化的计算机网络 OSI 模型中,它完成第四层传输层所指定的功能。 毫不夸张地说,TCP 协议是目前整个互联网的基础。它解决了一系列的网络问题。带来的结果,就是协议本身非常复杂。考虑到文章篇幅问题,本文着重说明 TCP 建立连接时的三次握手过程和关闭连接时的四次挥手过程。 三次握手 图 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。 发送完毕后,客户端进入 ESTABLISHED 状态,当服务器端接收到这个包时,也进入 ESTABLISHED 状态,TCP 握手结束。 SYN Flood 攻击 在三次握手过程中,服务器发送 SYN-ACK 之后,收到客户端的 ACK 之前的 TCP 连接称为半连接(half-open connect)。此时服务器处于 SYN_RCVD 状态。当收到 ACK 后,服务器才能转入 ESTABLISHED 状态.
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。实际上,它是在有序链表的基础上发展起来的。 当我们想查找数据的时候,可以先沿着跨度大的链进行查找。当碰到比待查数据大的节点时,再回到跨度小的链表中进行查找。 skiplist正是受这种多层链表的想法的启发而设计出来的。按照上面生成链表的方式,上面每一层链表的节点个数,是下面一层的节点个数的一半,这样查找过程就非常类似于一个二分查找,使得查找的时间复杂度可以降低到 O(logN)。但是,存在的一个问题是:如果插入新节点后就会打乱上下相邻两层节点是 2:1 的对应关系。如果要维持,则需要调整后面所有的节点。
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 实现特点是: 双向:节点带有前后指针; 无环:首尾没有相连,所以没有构成环状; 链表保存了首尾指针; 多态:可以保存不同类型的值,这里成为泛型也许更符合 Java 中的语义。 Redis 在 2014 年实现了 quicklist,并使用 quicklist 代替了 linkedlist。所以,现在 linkedlist 几乎已经是废弃状态。
题解:找到二叉搜索树中两个错误的节点

题解:找到二叉搜索树中两个错误的节点

D瓜哥
题目描述 一棵二叉树原本是二叉搜索树,但是其中有两个节点调换了位置,使得这棵二叉树不再是二叉搜索树,请按升序输出这两个错误节点的值。(每个节点的值各不相同) 思路分析 一棵二叉搜索树,如果是中序遍历,那么,其序列正好是一个升序序列。如果序列中间出现了降序,那么就是树中错误的节点。这里有两种情况需要考虑: 如果两个节点正好相邻,那么降序的两个节点就是题目要求的节点。 如果两个节点不相邻,就会出现两次降序。很容易想到,“大”的元素跑前面,“小”的元素跑后面。在进行比较的时候,第一个降序时,前面大的元素是错误节点;第二次降序时,则是后面小的元素是错误节点。 有了上面的分析,就可以写代码了。 解题代码 中序遍历,可以用栈,也可以使用 Morris 遍历。前面正好学习了一下 Morris(详情请看: 神奇的 Morris 树遍历),借此机会练练手: public static TreeNode[] getErrs(TreeNode head) { TreeNode[] result = new TreeNode[2]; TreeNode curr = head; TreeNode mostRight = null; TreeNode prior = null; while (curr != null) { mostRight = curr.left; if (mostRight != null) { while (mostRight.right != null && mostRight.right != curr) { mostRight = mostRight.right; } if (mostRight.right == null) { mostRight.

负载均衡算法及实践

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 两种模式。 这个算法可以把同一个 URI 的访问发送到同一台服务器上,以最大程度提高缓存命中率。 该算法支持两个可选参数 len 和 depth,后跟一个正整数。仅在需要基于URI的开头来平衡服务器时,这些选项可能会很有用。 len 参数指示算法仅应考虑URI开头的许多字符来计算哈希。请注意,将 len 设置为 1 几乎没有意义,因为大多数URI都以前导 / 开头。 depth 参数指示用于计算哈希的最大目录深度。请求中的每个斜杠都计为一个级别。如果同时指定了两个参数,则在达到任意一个参数时都将停止评估。 哈希算法也有很多中,而且不同算法各有优缺。回头单独开篇整理吧。 URL 参数(URL Parameter)法 HAProxy 中实现的一个负载均衡算法。根据 URL 参数的哈希值来选择服务器。