算法

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 两种模式。

动态规划入门

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