Ryo's blog

首页

关于

归档

MiddlewareRedis

Redis 源码分析(七) :skiplist

一、skiplist由来skiplist本质上也是一种查找结构,用于解决算法中的查找问题(Searching),即根据给定的key,快速查到它所在的位置(或者对应的value)。 我们在《Redis内部数据结构详解》系列的第一篇中介绍dict的时候,曾经讨论过:一般查找问题的解法分为两个大类:一个是基于各种平衡树,一个是基于哈希表。但skiplist却比较特殊,它没法归属到这两大类里面。 这种数据结构是由William Pugh发明的,最早出现于他在1990年发表的论文《Skip Lists: A Probabilistic Alternative to Balanced Trees》。对细节感兴趣的同学可以下载论文原文来阅读。 skiplist,顾名思义,首先它是一个list。实际上,它是在有序链表的基础..

更多
MiddlewareRedis

Redis 源码分析(六) :quciklist

一、什么是quicklist由于考虑到链表adlist的附加空间相对太高,prev和next指针就要占去 16 个字节 (64bit系统的指针是8个字节),另外每个节点的内存都是单独分配,会加剧内存的碎片化,影响内存管理效率。 quicklist是一个3.2版本之后新增的基础数据结构,是redis自定义的一种复杂数据结构,将ziplist和adlist结合到了一个数据结构中。主要是作为list的基础数据结构。在3.2之前,list是根据元素数量的多少采用ziplist或者adlist作为基础数据结构,3.2之后统一改用quicklist,从数据结构的角度来说quicklist结合了两种数据结构的优缺点,复杂但是实用: 链表在插入,删除节点的时间复杂度很低;但是内存利用率低,且由于内存不连续容易产生内存碎片..

更多
MiddlewareRedis

Redis 源码分析(五) :ziplist

一、前言ziplist是redis节省内存的典型例子之一,这个数据结构通过特殊的编码方式将数据存储在连续的内存中。在3.2之前是list的基础数据结构之一,在3.2之后被quicklist替代。但是仍然是zset底层实现之一。 二、存储结构压缩表没有数据结构代码定义,完全是通过内存的特殊编码方式实现的一种紧凑存储数据结构。我们可以通过ziplist的初始化函数和操作api来倒推其内存分布。 #define ZIP_END 255 #define ZIPLIST_BYTES(zl) (*((uint32_t*)(zl))) // 获取ziplist的bytes指针 #define ZIPLIST_TAIL_OFFSET(zl) (*((uint32_t*)((zl)+sizeof(uint..

更多
MiddlewareRedis

Redis 源码分析(四) :intset

一、什么是intsetintset是Redis内存数据结构之一,用来实现Redis的Set结构(当集合元素不大于设定值并且元素都是整数时,就会用intset作为set的底层数据结构),它的特点有: 元素类型只能为数字。 元素有三种类型:int16_t、int32_t、int64_t。 元素有序,不可重复。 intset和sds一样,内存连续,就像数组一样。 二、数据结构定义typedef struct intset { uint32_t encoding; // 编码类型 int16_t、int32_t、int64_t uint32_t length; // 长度 最大长度:2^32 int8_t contents[]; // 柔性数组 } intset; enco..

更多
MiddlewareRedis

Redis 源码分析(三) :dict

一、什么是dictdict (dictionary 字典),通常的存储结构是Key-Value形式的,通过Hash函数对key求Hash值来确定Value的位置,因此也叫Hash表,是一种用来解决算法中查找问题的数据结构,默认的算法复杂度接近O(1),Redis本身也叫Remote Dictionary Server(远程字典服务器),其实也就是一个大字典,它的key通常来说是String类型的,但是Value可以是String、Set、ZSet、Hash、List等不同的类型,下面我们看下dict的数据结构定义。 二、Redis Dict数据结构 从上图可以看出与dict相关的关键数据结构有三个,分别是: dict是Redis中的字典结构,包含两个dictht。 dictht表示一个Hash表。 dic..

更多
MiddlewareRedis

Redis 源码分析(二) :ADList

概述ADList(A generic doubly linked list)是 redis 自定义的一种双向链表,广泛运用于 redisClients 、 redisServer 、发布订阅、慢查询、监视器等。(注:3.0及以前还会被运用于list结构中,在3.2以后被quicklist取代)。 链表提供了高效的节点重排能力,以及顺序性的节点访问方式,并且可以通过增删节点来灵活地调整链表的长度。 链表在Redis 中的应用非常广泛,比如列表键的底层实现之一就是链表。当一个列表键包含了数量较多的元素,又或者列表中包含的元素都是比较长的字符串时,Redis 就会使用链表作为列表键的底层实现。 链表结构是 Redis 中一个常用的结构,它可以存储多个字符串 它是有序的 能够存储2的32次方减一个节点(超过 40..

更多
MiddlewareRedis

Redis 源码分析(一) :sds

什么是sds字符串是Redis中最为常见的数据存储类型,其底层实现是简单动态字符串sds(simple dynamic string),是可以修改的字符串。 它类似于Java中的ArrayList,它采用预分配冗余空间的方式来减少内存的频繁分配。 数据结构// 3.0及以前 struct sdshdr { // 记录buf数组中已使用字节数量 unsigned int len; // 记录buf数组中未使用的字节数量 unsigned int free; // 字节数组,存储字符串 char buf[]; }; // >=3.2 struct __attribute__ ((__packed__)) sdshdr5 { unsigned cha..

更多
MiddlewareMySQLBackend

MySQL 索引那些事

1. MySQL 常见几种索引类型1.1 普通索引,是最基本的索引,它没有任何限制。它有以下几种创建方式: (1)直接创建索引 CREATE INDEX index_name ON table(column(length)) (2)修改表结构的方式添加索引 ALTER TABLE table_name ADD INDEX index_name ON (column(length)) (3)创建表的时候同时创建索引 CREATE TABLE `table` ( `id` int(11) NOT NULL AUTO_INCREMENT , `title` char(255) CHARACTER NOT NULL , `conten..

更多
LinuxMemory

内存管理、寻址方式那些事

一、内存1.1 什么是内存  简单地说,内存就是一个数据货架。内存有一个最小的存储单位,大多数都是一个字节。内存用内存地址(memory address)来为每个字节的数据顺序编号。因此,内存地址说明了数据在内存中的位置。内存地址从0开始,每次增加1。这种线性增加的存储器地址称为线性地址(linear address)。   内存地址的编号有上限。地址空间的范围和地址总线(address bus)的位数直接相关。CPU通过地址总线来向内存说明想要存取数据的地址。以英特尔32位的80386型CPU为例,这款CPU有32个针脚可以传输地址信息。每个针脚对应了一位。如果针脚上是高电压,那么这一位是1。如果是低电压,那么这一位是0。32位的电压高低信息通过地址总线传到内存的32个针脚,内存就能把电压高低信息转换成3..

更多
DataStructure

B-Tree、B+Tree、B*Tree

一、B-Tree1.1 什么是B-Tree 1970年,R.Bayer和E.mccreight提出了一种适用于外查找的树,它是一种平衡的多叉树,称为B树,其定义如下 根结点至少有两个子女。 每个中间节点都包含k-1个元素和k个孩子,其中 m/2 <= k <= m 每一个叶子节点都包含k-1个元素,其中 m/2 <= k <= m 所有的叶子结点都位于同一层。 每个节点中的元素从小到大排列,节点当中k-1个元素正好是k个孩子包含的元素的值域分划。 M = 3 1.2 B-Tree 查找假设我们要查找的数据是 5 二、B+Tree2.1 什么是B+TreeB+ 树是一种树数据结构,是一个n叉树,每个节点通常有多个孩子,一棵B+树包含根节点、内部节点和叶子节点。根节点可..

更多
MiddlewareMySQL

MyISAM和InnoDB区别和应用场景

什么是MyISAM 和InnoDB MyISAM是MySQL的默认数据库引擎(5.5版之前),由早期的ISAM所改良。虽然性能极佳,但却有一个缺点:不支持事务处理(transaction)。 InnoDB,是MySQL的数据库引擎之一,为MySQL AB发行binary的标准之一。InnoDB由Innobase Oy公司所开发,2006年五月时由甲骨文公司并购。与传统的ISAM与MyISAM相比,InnoDB的最大特色就是支持了ACID兼容的事务(Transaction)功能,类似于PostgreSQL。 MyISAM:它是基于传统的ISAM类型,ISAM是Indexed Sequential Access Method (有索引的顺序访问方法) 的缩写,它是存储记录和文件的标准方法。不是事务安全的,而且..

更多
Golang

Golang 内存对齐问题

什么是内存对齐?CPU把内存当成是一块一块的,块的大小可以是2,4,8,16字节大小,因此CPU在读取内存时是一块一块进行读取的。块大小成为memory access granularity(粒度)。 假设CPU访问粒度是4,也就是一次性可以读取内存中的四个字节内容;当我们不采用内存对齐策略,如果需要访问A中的b元素,CPU需要先取出0-3四个字节的内容,发现没有读取完,还需要再次读取,一共需要进行两次访问内存的操作;而有了内存对齐,参考左图,可一次性取出4-7四个字节的元素也即是b,这样就只需要进行一次访问内存的操作。所以操作系统这样做的原因也就是所谓的拿空间换时间,提高效率。 为什么要内存对齐?会了关于结构体内存大小的计算,可是为什么系统要对于结构体数据进行内存对齐呢,很明显所占用的空间大小要更多。原..

更多
MiddlewareConsul

服务发现之Consul

consul是一个可以提供服务发现,健康检查,多数据中心,Key/Value存储等功能的分布式服务框架 用于实现分布式系统的服务发现与配置。与其他分布式服务注册与发现的方案,Consul的方案更”一站式”,内置了服务注册与发现框架、分布一致性协议实现、健康检查、Key/Value存储、多数据中心方案,不再需要依赖其他工具(比如ZooKeeper等)。使用起来也较为简单。Consul用Golang实现,因此具有天然可移植性(支持Linux、Windows和Mac OS X);安装包仅包含一个可执行文件,方便部署,与Docker等轻量级容器可无缝配合。 Consul 的使用场景 docker 实例的注册与配置共享 coreos 实例的注册与配置共享 vitess 集群 SaaS 应用的配置共享 与 confd ..

更多
Middleware

分布式id几种生成方案

一、UUIDUUID 是 通用唯一识别码(Universally Unique Identifier)的缩写,是一种软件建构的标准,亦为开放软件基金会组织在分布式计算环境领域的一部分。其目的,是让分布式系统中的所有元素,都能有唯一的辨识信息,而不需要通过中央控制端来做辨识信息的指定。如此一来,每个人都可以创建不与其它人冲突的UUID。在这样的情况下,就不需考虑数据库创建时的名称重复问题。目前最广泛应用的UUID,是微软公司的全局唯一标识符(GUID),而其他重要的应用,则有Linux ext2/ext3文件系统、LUKS加密分区、GNOME、KDE、Mac OS X等等。另外我们也可以在e2fsprogs包中的UUID库找到实现。 UUID的标准形式包含32个16进制数字,以连字号分为五段,形式为8-4-4..

更多
GolangLua

Go 执行Lua脚本和JS脚本测试

最近有个需求需要在Go项目里面执行动态脚本,github上有好几个lua执行解释器,但是有很多要不就很久没维护了,要不就没有什么文档,经过几个对比我最后用的是 https://github.com/yuin/gopher-lua。JS解析器用的github.com/robertkrimen/otto。 具体测试代码如下,给有需求的朋友参考。 github地址 package main import ( "fmt" "github.com/robertkrimen/otto" "github.com/yuin/gluamapper" "github.com/yuin/gopher-lua" "time" ) //function add(a, b) //return..

更多
ProtobufNetHTPP

测试Protobuf在Http传输测试

Demo:https://github.com/fanlv/ProtobufOnHttpGo 一、编写Proto文件syntax = "proto3"; // 生成go代码 //protoc --go_out=. user.proto // 生成oc代码 //protoc --objc_out=. user.proto package user; message LoginRequest { string username = 1; string password = 2; } message BaseResponse{ int64 code = 1; string msg = 2; } message User{ string uid = 1; string..

更多
DataStructure

二叉树、2-3 树、红黑树

有序数组的优势在于二分查找,链表的优势在于数据项的插入和数据项的删除。但是在有序数组中插入数据就会很慢,同样在链表中查找数据项效率就很低。综合以上情况,二叉树可以利用链表和有序数组的优势,同时可以合并有序数组和链表的优势,二叉树也是一种常用的数据结构。 一、满二叉树一个二叉树,如果每一个层的结点数都达到最大值,则这个二叉树就是满二叉树。也就是说,如果一个二叉树的层数为 K,且结点总数是(2^k) -1 ,则它就是满二叉树。 二、完全二叉树若设二叉树的深度为 h,除第 h 层外,其它各层 (1 ~ h-1) 的结点数都达到最大个数,第 h 层所有的结点都连续集中在最左边,这就是完全二叉树。 三、二叉查找树二叉查找树(Binary Search Tree),(又:二叉搜索树,二叉排序树)它或者是一棵空树..

更多
IO

高并发服务器IO模型

服务端IO模型总结 草稿 网络框架视角零、Nginx 一、Netty(主从Reactor)MainReactor负责客户端的连接请求,并将请求转交给SubReactor SubReactor负责相应通道的IO读写请求 非IO请求(具体逻辑处理)的任务则会直接写入队列,等待worker threads进行处理 二、GRPC-GO (Goroutine Per Connection)net.Listen -> Serve() -> lis.Accept() net库的accept -> 一个连接开个一个goroutine -> s.handleRawConn(rawConn) -> newHTTP2Transport(conn, authInfo) -> newH..

更多
iOSGRPC

iOS之GRPC 测试(附代码)

背景最近在用gRPC框架测试,想起去年调研Protocol Buffer在HTTP的时候传输,了解过这个框架,当时没深入。这次做gRPC服务器端,随便看下iOS这边实现方式,附上测试代码。 demo地址: https://github.com/fanlv/gRPCDemo proto文件package user; message LoginRequest { string username = 1; string password = 2; } message BaseResponse{ int64 code = 1; string msg = 2; } message User{ string uid = 1; string name = 2; string ..

更多
GolangHTTP

跨域请求的几种解决方案

需求背景最近做的Apigate优化,前端的同学要求能在配置后台页面上加上一键测试接口的功能,但是由于浏览器的同源策略防止跨域攻击,所以前端的页面默认是不能请求其他域名的接口。 方案一 Nginx配置代理location /proxy { if ($arg_url) { proxy_pass $arg_url?; } } 最开始为了简单就配置了一个简单的代理,通过url传入想要访问的接口例如: http://nginxserver/proxy?url=http://10.23.39.140:8080/app/list 这样前端需要什么测试什么接口只需要通过url传过来,Nginx会方向代理到对应的url上返回结果。 但是这个方法有个问题,url中的地址支持IP访问,不支持域名的..

更多
Probability

概率论基础

样本空间与事件A⊂B 事件 B 包含了事件 A,A 被包含于 B A∩B A 与 B 的交集,表示事件 A 和事件 B 同时发生 A∪B A 与 B 的并集,表示事件 A 或事件 B 或他们二者同事发生 P(A|B) 在事件 B 发生下,事件 A 发生的概率 对偶公式 随机事件运算(1)交换律:A∪B=B∪A、AB=BA (2)结合律:( A∪B )∪C=A∪( B∪C ) (3)分配律:A∪( BC )=( A∪B )( A∪C )A( B∪C )=( AB )∪( AC ) (4)摩根律:A B=A∪B、A ∪ B=A B 概率的三个基本性质 二项系数 蒙特卡罗(Monte Carlo) 乘法公式P(AB)=P(B)P(A|B) = P(A)P(B|A) 全概率公式 贝叶斯公式(Bayes)

更多
Calculus

微积分基础

导数(Derivatives) 导数是函数的局部性质。一个函数在某一点的导数描述了这个函数在这一点附近的变化率。如果函数的自变量和取值都是实数的话,函数在某一点的导数就是该函数所代表的曲线在这一点上的切线斜率。导数的本质是通过极限的概念对函数进行局部的线性逼近。例如在运动学中,物体的位移对于时间的导数就是物体的瞬时速度。 一阶导数为 0 的时候,对应的值不是最大值(局部)就是最小值(局部)。 求导规则加(减)法则:(f+g)'=f'+g' 乘法法则:(f*g)'=f'*g+g'*f 除法法则:(f/g)'=(f'*g-g'*f)/g^2 y = x^n => dy/dx = nx^n-1 y = sin(x) => dy/dx = cos(x) y = e^x => dy/dx = e^..

更多
Statistics

统计学基础

最近休息在家无聊,整理下之前看的统计学的一些基础知识,方便以后查阅吧。 基础名词 均值 (Mean),所有数相加出去数量。 中位数 (Median), 中间一个数,或者是中间的两个数相加除以 2 众数 (Mode),出现次数最多的数。 极差 (Range),最大值减去最小值(Max-Min) 中程数(Mid-Range) (Max+Min)/ 2 样本 (sameple) 总体 (population) 总体的均值 (mean of a population) 𝝻./ 样本的均值 (mean of a sameple) 总体方差 (variance of a population) 样本方差(Sample variance) 基础概念和公式基础概念对应的数学符号: 总体均值(Population Mea..

更多
Note

《四书五经入门》

一、前言儒家学说,简称儒学,它的核心内容是儒家思想,由春秋末期思想家孔子所创立。孔子在总结、概括和继承了夏、商、周三代传统文化的基础上形成了一个完整的思想体系,它的表现形式是一些道德行为准则。 在政治学上,主张仁政、行王道,通过礼来理顺君臣、官民和各种社会关系; 在伦理学上,以“仁”为核心,强调通过提高自身修养来实现人与人之间和谐相处; 在历史学上,注重编修历史,并于记叙中体现微言大义; 在经济学上,主张重义轻利、重官轻商、重本抑末; 在教育学上,格外强调道德培养的重要性。 并把“仁”作为最高道德准则……儒家学说的创立者以孔子和孟子为代表,其中的孔子被尊为一代宗师。后来的各代中虽各有发展,但都以孔子和孟子的思想为核心。 “四书五经”基本上都是由孔子与他的弟子及传袭者编纂完成,所体现的都是孔子所尊创的儒家..

更多
HTTPNet

深入浅出HTTP

深入浅出HTTP一、什么是Http和TCP HTTP(HyperText Transfer Protocol)超文本传输协议,是互联网上应用最为广泛的一种网络协议。所有的WWW文件都必须遵守这个标准。设计HTTP最初的目的是为了提供一种发布和接收HTML页面的方法。1960年美国人Ted Nelson构思了一种通过计算机处理文本信息的方法,并称之为超文本(hypertext),这成为了HTTP超文本传输协议标准架构的发展根基。Ted Nelson组织协调万维网协会(World Wide Web Consortium)和互联网工程工作小组(Internet Engineering Task Force )共同合作研究,最终发布了一系列的RFC,其中著名的RFC 2616定义了HTTP 1.1。 TCP(T..

更多

一些疯言疯语

一、背景最近挺迷茫,迷茫期就会胡思乱想,然后就会有一些疯言疯语,不吐不快。 二、疯言疯语2.1 关于技术、成长我的技术栈是典型的应用(搬砖)工程师的技术栈,最早是用的C#(Win-Server、ASP.NET)然后是Objective-C(iOS)最后是Go,最近在看Rust。Go之前学的开发语言都是闭源的,闭源有个不好的地方,就是代码层面实现对你来说都是黑盒,如果你不主动去探索,或者你的眼界限制了你的探索能力,你的水平永远就停留在搬砖的水平。 拿移动端做例子,90%的做移动端的同学可能会迷茫,觉得自己的工作就是画界面,实际上移动端主要一部分工作也就是画界面做交互,只有字节这样的大厂会有专门的团队去做各种专项的技术优化,比如编译优化(看了移动端几次LLVM编译相关的分享,做的挺牛逼的)、音视频编解码优化、..

更多
HTTPProtobufNet

Protobuf On HTTP 技术预研 (附代码)

Protobuf 技术预研Demo地址:https://github.com/fanlv/ProtobufOnHttp Demo地址:https://github.com/fanlv/ProtobufOnHttpGo 一、背景现在客户端与服务器通讯主要通过Json来做数据交互,本次调研主要比较Protobuf项目中使用的优缺点,和可行性。 二、Protobuf说明2.1 什么是ProtobufProtocolBuffer(以下简称PB)是google 的一种数据交换的格式,它独立于语言,独立于平台。大部分IM通讯协议都是使用PB来传输。具体代表性的有支付宝、微信等App。 说白了,PB就是一种序列化协议,我们开发中想在什么场景中使用Protobuf做为数据交换的序列化协议,取决于自己的业务。 2.2 Pro..

更多
iOS

iOS Cookie 存储相关技术

iOS Cookie 存储相关技术一、什么是Cookie Cookie,有时也用其复数形式 Cookies,指某些网站为了辨别用户身份、进行 session 跟踪而储存在用户本地终端上的数据(通常经过加密)。定义于 RFC2109 和 2965 中的都已废弃,最新取代的规范是 RFC6265 [1] 。(可以叫做浏览器缓存)来自百度百科 说白了Cookie就是提供服务器存储相关数据到客户端的一种解决方案,服务器通过返回的Http头中告知客户端,我设置了Cookie,客户端收到请求以后,会读出Http响应的Header里面把对应的Cookie的key、value值持久化存到本地的Cookie文件,下次再请求服务器相关域名的接口中,会自动带上Cookie相关数据。当然客户端也可以主动设置、读取、删除这些C..

更多
NoteMiddlewareMySQL

《MySQL实战45讲》

binlog && redo log什么是 binlog binlog 是逻辑日志,记录的是这个语句的原始逻辑/变化,比如“给 ID=2 这一行的 c 字段加 1 ”。 binlog 是追加写,不会覆盖之前的数据,可以提供完整的数据归档的能力。 什么是 redo log redo log 是物理日志,记录的是“在某个数据页上做了什么修改”; redo log 提供 crash-safe 能力。 一般只有4G ,4个文件,循环复写。 binlog 和 redo log 不同点因为最开始 MySQL 里并没有 InnoDB 引擎。MySQL 自带的引擎是 MyISAM,但是 MyISAM 没有 crash-safe 的能力,binlog 日志只能用于归档。而 InnoDB 是另一个公司以插..

更多
12