-
Notifications
You must be signed in to change notification settings - Fork 0
/
index.html
296 lines (234 loc) · 39.4 KB
/
index.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
<!DOCTYPE html><html lang="zh-CN" data-theme="light"><head><meta charset="UTF-8"><meta http-equiv="X-UA-Compatible" content="IE=edge"><meta name="viewport" content="width=device-width,initial-scale=1"><title>王家麟's Blog</title><meta name="author" content="王家麟"><meta name="copyright" content="王家麟"><meta name="format-detection" content="telephone=no"><meta name="theme-color" content="#ffffff"><meta property="og:type" content="website">
<meta property="og:title" content="王家麟's Blog">
<meta property="og:url" content="https://wangjialin.club/index.html">
<meta property="og:site_name" content="王家麟's Blog">
<meta property="og:locale" content="zh_CN">
<meta property="og:image" content="https://wangjialin.club/img/avatar.png">
<meta property="article:author" content="王家麟">
<meta name="twitter:card" content="summary">
<meta name="twitter:image" content="https://wangjialin.club/img/avatar.png"><link rel="shortcut icon" href="/img/favicon.ico"><link rel="canonical" href="https://wangjialin.club/"><link rel="preconnect" href="//cdn.jsdelivr.net"/><link rel="preconnect" href="//busuanzi.ibruce.info"/><link rel="stylesheet" href="/css/index.css"><link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/@fortawesome/fontawesome-free/css/all.min.css" media="print" onload="this.media='all'"><script>const GLOBAL_CONFIG = {
root: '/',
algolia: undefined,
localSearch: undefined,
translate: undefined,
noticeOutdate: undefined,
highlight: {"plugin":"highlighjs","highlightCopy":true,"highlightLang":true,"highlightHeightLimit":false},
copy: {
success: '复制成功',
error: '复制错误',
noSupport: '浏览器不支持'
},
relativeDate: {
homepage: false,
post: false
},
runtime: '',
date_suffix: {
just: '刚刚',
min: '分钟前',
hour: '小时前',
day: '天前',
month: '个月前'
},
copyright: undefined,
lightbox: 'fancybox',
Snackbar: undefined,
source: {
jQuery: 'https://cdn.jsdelivr.net/npm/jquery@latest/dist/jquery.min.js',
justifiedGallery: {
js: 'https://cdn.jsdelivr.net/npm/justifiedGallery/dist/js/jquery.justifiedGallery.min.js',
css: 'https://cdn.jsdelivr.net/npm/justifiedGallery/dist/css/justifiedGallery.min.css'
},
fancybox: {
js: 'https://cdn.jsdelivr.net/npm/@fancyapps/fancybox@latest/dist/jquery.fancybox.min.js',
css: 'https://cdn.jsdelivr.net/npm/@fancyapps/fancybox@latest/dist/jquery.fancybox.min.css'
}
},
isPhotoFigcaption: false,
islazyload: false,
isanchor: false
}</script><script id="config-diff">var GLOBAL_CONFIG_SITE = {
isPost: false,
isHome: true,
isHighlightShrink: false,
isToc: false,
postUpdate: '2021-04-10 15:23:30'
}</script><noscript><style type="text/css">
#nav {
opacity: 1
}
.justified-gallery img {
opacity: 1
}
#recent-posts time,
#post-meta time {
display: inline !important
}
</style></noscript><script>(win=>{
win.saveToLocal = {
set: function setWithExpiry(key, value, ttl) {
if (ttl === 0) return
const now = new Date()
const expiryDay = ttl * 86400000
const item = {
value: value,
expiry: now.getTime() + expiryDay,
}
localStorage.setItem(key, JSON.stringify(item))
},
get: function getWithExpiry(key) {
const itemStr = localStorage.getItem(key)
if (!itemStr) {
return undefined
}
const item = JSON.parse(itemStr)
const now = new Date()
if (now.getTime() > item.expiry) {
localStorage.removeItem(key)
return undefined
}
return item.value
}
}
win.getScript = url => new Promise((resolve, reject) => {
const script = document.createElement('script')
script.src = url
script.async = true
script.onerror = reject
script.onload = script.onreadystatechange = function() {
const loadState = this.readyState
if (loadState && loadState !== 'loaded' && loadState !== 'complete') return
script.onload = script.onreadystatechange = null
resolve()
}
document.head.appendChild(script)
})
win.activateDarkMode = function () {
document.documentElement.setAttribute('data-theme', 'dark')
if (document.querySelector('meta[name="theme-color"]') !== null) {
document.querySelector('meta[name="theme-color"]').setAttribute('content', '#0d0d0d')
}
}
win.activateLightMode = function () {
document.documentElement.setAttribute('data-theme', 'light')
if (document.querySelector('meta[name="theme-color"]') !== null) {
document.querySelector('meta[name="theme-color"]').setAttribute('content', '#ffffff')
}
}
const t = saveToLocal.get('theme')
if (t === 'dark') activateDarkMode()
else if (t === 'light') activateLightMode()
const asideStatus = saveToLocal.get('aside-status')
if (asideStatus !== undefined) {
if (asideStatus === 'hide') {
document.documentElement.classList.add('hide-aside')
} else {
document.documentElement.classList.remove('hide-aside')
}
}
})(window)</script><meta name="generator" content="Hexo 5.4.0"></head><body><div id="loading-box"><div class="loading-left-bg"></div><div class="loading-right-bg"></div><div class="spinner-box"><div class="configure-border-1"><div class="configure-core"></div></div><div class="configure-border-2"><div class="configure-core"></div></div><div class="loading-word">加载中...</div></div></div><div id="sidebar"><div id="menu-mask"></div><div id="sidebar-menus"><div class="author-avatar"><img class="avatar-img" src="/img/avatar.png" onerror="onerror=null;src='/img/friend_404.gif'" alt="avatar"/></div><div class="site-data"><div class="data-item is-center"><div class="data-item-link"><a href="/archives/"><div class="headline">文章</div><div class="length-num">11</div></a></div></div><div class="data-item is-center"><div class="data-item-link"><a href="/tags/"><div class="headline">标签</div><div class="length-num">9</div></a></div></div><div class="data-item is-center"><div class="data-item-link"><a href="/categories/"><div class="headline">分类</div><div class="length-num">5</div></a></div></div></div><hr/><div class="menus_items"><div class="menus_item"><a class="site-page" href="/"><i class="fa-fw fas fa-home"></i><span> 首页</span></a></div><div class="menus_item"><a class="site-page" href="/archives/"><i class="fa-fw fas fa-archive"></i><span> 时间轴</span></a></div><div class="menus_item"><a class="site-page" href="/tags/"><i class="fa-fw fas fa-tags"></i><span> 标签</span></a></div><div class="menus_item"><a class="site-page" href="/categories/"><i class="fa-fw fas fa-folder-open"></i><span> 分类</span></a></div></div></div></div><div class="page" id="body-wrap"><header class="full_page" id="page-header" style="background-image: url('https://z3.ax1x.com/2021/04/10/ca0utg.jpg')"><nav id="nav"><span id="blog_name"><a id="site-name" href="/">王家麟's Blog</a></span><div id="menus"><div class="menus_items"><div class="menus_item"><a class="site-page" href="/"><i class="fa-fw fas fa-home"></i><span> 首页</span></a></div><div class="menus_item"><a class="site-page" href="/archives/"><i class="fa-fw fas fa-archive"></i><span> 时间轴</span></a></div><div class="menus_item"><a class="site-page" href="/tags/"><i class="fa-fw fas fa-tags"></i><span> 标签</span></a></div><div class="menus_item"><a class="site-page" href="/categories/"><i class="fa-fw fas fa-folder-open"></i><span> 分类</span></a></div></div><div id="toggle-menu"><a class="site-page"><i class="fas fa-bars fa-fw"></i></a></div></div></nav><div id="site-info"><h1 id="site-title">王家麟's Blog</h1></div><div id="scroll-down"><i class="fas fa-angle-down scroll-down-effects"></i></div></header><main class="layout" id="content-inner"><div class="recent-posts" id="recent-posts"><div class="recent-post-item"><div class="post_cover left_radius"><a href="/2020/01/17/LRU%E7%AE%97%E6%B3%95%E5%8F%8A%E5%85%B6%E4%BC%98%E5%8C%96%E7%AD%96%E7%95%A5%E2%80%94%E2%80%94Redis%E7%AF%87/" title="LRU算法及其优化策略——Redis篇"> <img class="post_bg" src="https://z3.ax1x.com/2021/04/10/casQaV.jpg" onerror="this.onerror=null;this.src='/img/404.jpg'" alt="LRU算法及其优化策略——Redis篇"></a></div><div class="recent-post-info"><a class="article-title" href="/2020/01/17/LRU%E7%AE%97%E6%B3%95%E5%8F%8A%E5%85%B6%E4%BC%98%E5%8C%96%E7%AD%96%E7%95%A5%E2%80%94%E2%80%94Redis%E7%AF%87/" title="LRU算法及其优化策略——Redis篇">LRU算法及其优化策略——Redis篇</a><div class="article-meta-wrap"><span class="post-meta-date"><i class="far fa-calendar-alt"></i><span class="article-meta-label">发表于</span><time datetime="2020-01-17T08:34:00.000Z" title="发表于 2020-01-17 16:34:00">2020-01-17</time></span><span class="article-meta"><span class="article-meta__separator">|</span><i class="fas fa-inbox"></i><a class="article-meta__categories" href="/categories/redis/">redis</a></span></div><div class="content">在上一篇文章中，分享了一些LRU基本算法及优化策略，本篇继续该主题，分享在Redis中LRU算法的使用和优化。
Redis 内存回收策略在介绍Redis的LRU使用之前，我们需要先要了解一下Redis的内存回收策略。
Redis作为一个高性能的内存型的KV数据库，势必需要一个机制来控制Redis的内存占用，避免内存溢出。而和内存占用限制有关的配置即为maxmemory这个参数，通过动态调整该参数即可动态地限制Redis的内存占用。
Redis内存回收策略分为两个方面：
删除过期键
回收策略
删除过期键Redis通过两种手段删除过期键：
惰性删除
对于有过期时间的键，会在键上附加一个过期时间的时间戳，当客户端访问到该键时，会先检查过期时间戳，如果该键值已过期，则返回空，并删除该键。使用惰性删除可以避免维护过期时间的链表，但是如果一个过期键一直没有被访问，则有内存泄漏的问题。
定时任务删除
为了避免惰性删除造成的内存泄漏，Redis会启动一个定时任务，默认为10s运行一次，该定时任务会随机从数据库中选取一些键并删除其中过期的键，如果发现其中超过25%的键都已过期，则重复执行一次该定 ...</div></div></div><div class="recent-post-item"><div class="post_cover right_radius"><a href="/2020/01/16/LFU%E7%AE%97%E6%B3%95%E5%8F%8A%E5%85%B6%E4%BC%98%E5%8C%96%E7%AD%96%E7%95%A5%E2%80%94%E2%80%94%E7%AE%97%E6%B3%95%E7%AF%87/" title="LFU算法及其优化策略——算法篇"> <img class="post_bg" src="https://z3.ax1x.com/2021/04/10/casl5T.png" onerror="this.onerror=null;this.src='/img/404.jpg'" alt="LFU算法及其优化策略——算法篇"></a></div><div class="recent-post-info"><a class="article-title" href="/2020/01/16/LFU%E7%AE%97%E6%B3%95%E5%8F%8A%E5%85%B6%E4%BC%98%E5%8C%96%E7%AD%96%E7%95%A5%E2%80%94%E2%80%94%E7%AE%97%E6%B3%95%E7%AF%87/" title="LFU算法及其优化策略——算法篇">LFU算法及其优化策略——算法篇</a><div class="article-meta-wrap"><span class="post-meta-date"><i class="far fa-calendar-alt"></i><span class="article-meta-label">发表于</span><time datetime="2020-01-16T09:00:00.000Z" title="发表于 2020-01-16 17:00:00">2020-01-16</time></span><span class="article-meta"><span class="article-meta__separator">|</span><i class="fas fa-inbox"></i><a class="article-meta__categories" href="/categories/%E7%AE%97%E6%B3%95/">算法</a></span></div><div class="content">前不久写了LRU算法系列文章，今天来介绍一下和LRU算法并驾齐驱的另一个算法——LFU。
LFU全称是最不经常使用算法（Least Frequently Used），LFU算法的基本思想和所有的缓存算法一样，都是基于locality假设（局部性原理）：
如果一个信息项正在被访问，那么在近期它很可能还会被再次访问。
LFU是基于这种思想进行设计：一定时期内被访问次数最少的页，在将来被访问到的几率也是最小的。
相比于LRU（Least Recently Use）算法，LFU更加注重于使用的频率。
原理LFU将数据和数据的访问频次保存在一个容量有限的容器中，当访问一个数据时：
该数据在容器中，则将该数据的访问频次加1。
该数据不在容器中，则将该数据加入到容器中，且访问频次为1。
当数据量达到容器的限制后，会剔除掉访问频次最低的数据。下图是一个简易的LFU算法示意图。
上图中的LRU容器是一个链表，会动态地根据访问频次调整数据在链表中的位置，方便进行数据的淘汰，可以看到，在第四步时，因为需要插入数据F，而淘汰了数据E。
LFU实现LFU的实现一共有三种方案，但是思想都是一样的，下面我 ...</div></div></div><div class="recent-post-item"><div class="post_cover left_radius"><a href="/2020/01/16/LRU%E7%AE%97%E6%B3%95%E5%8F%8A%E5%85%B6%E4%BC%98%E5%8C%96%E7%AD%96%E7%95%A5%E2%80%94%E2%80%94%E7%AE%97%E6%B3%95%E7%AF%87/" title="LRU算法及其优化策略——算法篇"> <img class="post_bg" src="https://z3.ax1x.com/2021/04/10/casG24.png" onerror="this.onerror=null;this.src='/img/404.jpg'" alt="LRU算法及其优化策略——算法篇"></a></div><div class="recent-post-info"><a class="article-title" href="/2020/01/16/LRU%E7%AE%97%E6%B3%95%E5%8F%8A%E5%85%B6%E4%BC%98%E5%8C%96%E7%AD%96%E7%95%A5%E2%80%94%E2%80%94%E7%AE%97%E6%B3%95%E7%AF%87/" title="LRU算法及其优化策略——算法篇">LRU算法及其优化策略——算法篇</a><div class="article-meta-wrap"><span class="post-meta-date"><i class="far fa-calendar-alt"></i><span class="article-meta-label">发表于</span><time datetime="2020-01-16T09:00:00.000Z" title="发表于 2020-01-16 17:00:00">2020-01-16</time></span><span class="article-meta"><span class="article-meta__separator">|</span><i class="fas fa-inbox"></i><a class="article-meta__categories" href="/categories/%E7%AE%97%E6%B3%95/">算法</a></span></div><div class="content">LRU算法全称是最近最少使用算法（Least Recently Use），广泛的应用于缓存机制中。当缓存使用的空间达到上限后，就需要从已有的数据中淘汰一部分以维持缓存的可用性，而淘汰数据的选择就是通过LRU算法完成的。
LRU算法的基本思想是基于局部性原理的时间局部性：
如果一个信息项正在被访问，那么在近期它很可能还会被再次访问。
所以顾名思义，LRU算法会选出最近最少使用的数据进行淘汰。
原理一般来讲，LRU将访问数据的顺序或时间和数据本身维护在一个容器当中。当访问一个数据时：
该数据不在容器当中，则设置该数据的优先级为最高并放入容器中。
该数据在容器当中，则更新该数据的优先级至最高。
当数据的总量达到上限后，则移除容器中优先级最低的数据。下图是一个简单的LRU原理示意图：
如果我们按照7 0 1 2 0 3 0 4的顺序来访问数据，且数据的总量上限为3，则如上图所示，LRU算法会依次淘汰7 1 2这三个数据。
朴素的LRU算法那么我们现在就按照上面的原理，实现一个朴素的LRU算法。下面有三种方案：
基于数组
方案：为每一个数据附加一个额外的属性——时间戳，当每一次访问 ...</div></div></div><div class="recent-post-item"><div class="post_cover right_radius"><a href="/2020/01/16/LRU%E7%AE%97%E6%B3%95%E5%8F%8A%E5%85%B6%E4%BC%98%E5%8C%96%E7%AD%96%E7%95%A5%E2%80%94%E2%80%94Mysql%E7%AF%87/" title="LRU算法及其优化策略——Mysql篇"> <img class="post_bg" src="https://i.loli.net/2020/01/19/ZT3nUY4RAt9kyV8.jpg" onerror="this.onerror=null;this.src='/img/404.jpg'" alt="LRU算法及其优化策略——Mysql篇"></a></div><div class="recent-post-info"><a class="article-title" href="/2020/01/16/LRU%E7%AE%97%E6%B3%95%E5%8F%8A%E5%85%B6%E4%BC%98%E5%8C%96%E7%AD%96%E7%95%A5%E2%80%94%E2%80%94Mysql%E7%AF%87/" title="LRU算法及其优化策略——Mysql篇">LRU算法及其优化策略——Mysql篇</a><div class="article-meta-wrap"><span class="post-meta-date"><i class="far fa-calendar-alt"></i><span class="article-meta-label">发表于</span><time datetime="2020-01-16T08:34:00.000Z" title="发表于 2020-01-16 16:34:00">2020-01-16</time></span><span class="article-meta"><span class="article-meta__separator">|</span><i class="fas fa-inbox"></i><a class="article-meta__categories" href="/categories/mysql/">mysql</a></span></div><div class="content">在上一篇文章中，介绍了LRU算法在Redis之中的应用，本篇继续给各位道友介绍在Mysql的InnobDB引擎中，是如何使用LRU算法的。
InnoDB缓冲池缓存池简介及内存结构首先来介绍下InnoDB的缓冲池，缓冲池简单来说就是一块内存区域，该区域内缓存着InnoDB访问存储在磁盘的数据和索引信息。缓冲池有两个作用，一是提高了大容量读取操作的效率，二是提高了缓存管理的效率。时调配缓存池参数，使得经常访问的参数能够保留在缓存池中是一个很重要的Mysql优化手段。
一个InnoDB缓存池的内存结构图如下图所示：
图源自《Mysql技术内幕：InnoDB存储引擎》
缓存池状态我们可以通过SHOW ENGINE INNODB STATUS命令来查看缓存池在InnoDB引擎中的表现：
12345678910111213141516----------------------BUFFER POOL AND MEMORY----------------------Total memory allocated 6593445888; // 为缓冲池分配的 ...</div></div></div><div class="recent-post-item"><div class="post_cover left_radius"><a href="/2020/01/01/Dubbo%E6%9C%8D%E5%8A%A1%E6%9A%B4%E9%9C%B2%E6%BA%90%E7%A0%81%E5%88%86%E6%9E%90/" title="Dubbo服务暴露源码分析"> <img class="post_bg" src="https://z3.ax1x.com/2021/04/10/cas3PU.jpg" onerror="this.onerror=null;this.src='/img/404.jpg'" alt="Dubbo服务暴露源码分析"></a></div><div class="recent-post-info"><a class="article-title" href="/2020/01/01/Dubbo%E6%9C%8D%E5%8A%A1%E6%9A%B4%E9%9C%B2%E6%BA%90%E7%A0%81%E5%88%86%E6%9E%90/" title="Dubbo服务暴露源码分析">Dubbo服务暴露源码分析</a><div class="article-meta-wrap"><span class="post-meta-date"><i class="far fa-calendar-alt"></i><span class="article-meta-label">发表于</span><time datetime="2020-01-01T09:00:00.000Z" title="发表于 2020-01-01 17:00:00">2020-01-01</time></span><span class="article-meta"><span class="article-meta__separator">|</span><i class="fas fa-inbox"></i><a class="article-meta__categories" href="/categories/%E7%AE%97%E6%B3%95/">算法</a></span></div><div class="content">本文使用Dubbo源码为2.7.4版本
服务暴露即指服务的提供者（Provider）通过一定的机制向注册中心注册自身提供的服务接口，以方便注册中心向消费者（Consumer）提供可调用的服务提供者的列表（即服务发现）。在Dubbo的官方文档中我们可以看到Dubbo的框架设计。其中0.start即为提供者启动时收集所有提供者服务接口实现并转化的过程，而1.register即是服务注册的一个过程。但是少了一个暴露的过程。
在Dubbo的官方文档中还提供了下面一张服务暴露的流程图，可以看到也是先进行具体服务的收集和转换，之后再进行暴露，但最后的服务注册并没有在图上体现。
所以结合两幅图就是一个完整的服务暴露的流程。本文也是以上面这样大的顺序来组织的，我们下面就开始本文的源码分析。
基本概念这里只是做一些简单的介绍，后面会有深入的讲解。
ServiceConfig
ProxyFactory
Invoker
Protocol
Exporter
服务暴露的入口ServiceBean即为服务暴露的入口。
12345678910111213141516171819// Service ...</div></div></div><div class="recent-post-item"><div class="post_cover right_radius"><a href="/2019/12/31/Dubbo%20SPI%E6%BA%90%E7%A0%81%E5%88%86%E6%9E%90/" title="Dubbo SPI源码分析"> <img class="post_bg" src="https://z3.ax1x.com/2021/04/10/cas8GF.png" onerror="this.onerror=null;this.src='/img/404.jpg'" alt="Dubbo SPI源码分析"></a></div><div class="recent-post-info"><a class="article-title" href="/2019/12/31/Dubbo%20SPI%E6%BA%90%E7%A0%81%E5%88%86%E6%9E%90/" title="Dubbo SPI源码分析">Dubbo SPI源码分析</a><div class="article-meta-wrap"><span class="post-meta-date"><i class="far fa-calendar-alt"></i><span class="article-meta-label">发表于</span><time datetime="2019-12-30T16:14:00.000Z" title="发表于 2019-12-31 00:14:00">2019-12-31</time></span><span class="article-meta"><span class="article-meta__separator">|</span><i class="fas fa-inbox"></i><a class="article-meta__categories" href="/categories/%E5%88%86%E5%B8%83%E5%BC%8F/">分布式</a></span></div><div class="content">在Dubbo的官网上，可以看到这样一句话：
Dubbo具有高度的可扩展能力，遵循微内核+插件的设计原则，所有核心能力如Protocol、Transport、Serialization被设计为扩展点，平等对待内置实现和第三方实现。
对于一个开源的RPC框架，可扩展性是十分重要的，那么Dubbo是怎么来实现这一点的呢，我们可以在Dubbo的源码中随处可以看到下面这样的代码：
1Protocol protocol = ExtensionLoader.getExtensionLoader(Protocol.class).getAdaptiveExtension();
这个ExtensionLoader就是Dubbo扩展能力的基础，也是理解Dubbo运行机制的基石，那么下面我们先来了解了解SPI是什么。
SPI机制SPI(Service Provider Interface)，是一种服务发现机制，Dubbo的SPI是从Java SPI增强而来，Dubbo的文档中给了三个增强的理由：
JDK 标准的 SPI 会一次性实例化扩展点所有实现，如果有扩展实现初始化很耗时，但如果没用上也加载， ...</div></div></div><div class="recent-post-item"><div class="post_cover left_radius"><a href="/2019/06/12/LSM%E6%A0%91%E5%8E%9F%E7%90%86%E6%8E%A2%E7%A9%B6/" title="LSM树原理探究"> <img class="post_bg" src="https://z3.ax1x.com/2021/04/10/casJxJ.jpg" onerror="this.onerror=null;this.src='/img/404.jpg'" alt="LSM树原理探究"></a></div><div class="recent-post-info"><a class="article-title" href="/2019/06/12/LSM%E6%A0%91%E5%8E%9F%E7%90%86%E6%8E%A2%E7%A9%B6/" title="LSM树原理探究">LSM树原理探究</a><div class="article-meta-wrap"><span class="post-meta-date"><i class="far fa-calendar-alt"></i><span class="article-meta-label">发表于</span><time datetime="2019-06-11T16:01:13.000Z" title="发表于 2019-06-12 00:01:13">2019-06-12</time></span><span class="article-meta"><span class="article-meta__separator">|</span><i class="fas fa-inbox"></i><a class="article-meta__categories" href="/categories/%E5%90%8E%E7%AB%AF/">后端</a></span></div><div class="content">前言B+树随着mysql Innodb引擎的广泛推广越来越被大家所熟知，而前不久我在研究Raft算法时，偶然发现了一种和B+树类似的数据结构——LSM树（Log-Structured-Merge-Tree 日志结构合并树），它是Google发表的论文 Big Table 中提到的一种很有趣的文件组织数据结构， 现如今已经被运用在很多工业界的产品之中了：HBase、Cassandra、LevelDB、RocksDB等等。今天就来研究研究LSM树的原理。
LSM树定义LSM树（Log-Structured-Merge-Tree）和B+树类似，它们被设计出来都是为了更好地将数据存储到大容量磁盘中。相对于B+树，LSM树拥有更好的随机写性能。在下面的一个ACM的报告中可以看到：
磁盘顺序写的性能有些颠覆我们的常识的，在上面的例子中，磁盘顺序写的吞吐量甚至能够超过内存随即写的吞吐量。而LSM树正是利用了这一点，它通过将磁盘随机写操作转化为顺序写操作，从而将随机写操作的吞吐量提高了好几个数量级。那么它是如何转换的呢？下面我们先来看看它的基本思想。
LSM树的基本思想LSM树会将所有的数据插入 ...</div></div></div><div class="recent-post-item"><div class="post_cover right_radius"><a href="/2019/05/26/Raft%E7%AE%97%E6%B3%95%E6%B3%A8%E8%A7%A3%E4%B9%9D%E8%AE%B0/" title="Raft算法注解九记"> <img class="post_bg" src="https://z3.ax1x.com/2021/04/10/casNrR.jpg" onerror="this.onerror=null;this.src='/img/404.jpg'" alt="Raft算法注解九记"></a></div><div class="recent-post-info"><a class="article-title" href="/2019/05/26/Raft%E7%AE%97%E6%B3%95%E6%B3%A8%E8%A7%A3%E4%B9%9D%E8%AE%B0/" title="Raft算法注解九记">Raft算法注解九记</a><div class="article-meta-wrap"><span class="post-meta-date"><i class="far fa-calendar-alt"></i><span class="article-meta-label">发表于</span><time datetime="2019-05-26T01:04:57.000Z" title="发表于 2019-05-26 09:04:57">2019-05-26</time></span><span class="article-meta"><span class="article-meta__separator">|</span><i class="fas fa-inbox"></i><a class="article-meta__categories" href="/categories/%E5%88%86%E5%B8%83%E5%BC%8F/">分布式</a></span></div><div class="content">前言
在之前的文章中我分享了个人对于Paxos算法的理解和见解，在文章的末尾引出了Raft算法，今天就来填完Raft算法这个坑。
Raft算法的作者在论文中吐槽了Paxos算法难以以理解且难以实现，所以提出了一个以易于理解且方便构建的分布式一致性算法，而且Raft算法提供了和Paxos算法相同的安全性及相差无几的性能。Raft算法的提出可以说是造福了我们这些智商普通的下里巴人。
个人认为Raft算法最难能可贵的地方就在于采用了一种工程化的思维来设计算法，从而使得Raft算法能够广泛地应用在分布式的领域之中。（etcd、SOFAJRaft、TiKV …）
虽然Raft算法相比于Paxos算法更加容易理解，但是在阅读原论文的时候，我还是在不少地方踩了坑，本文就是疏理和分享我在这些关键点处的疑惑和个人见解。（本文讨论范围仅是Basic Raft算法）
Raft论文的中文翻译版Raft算法动画
一、Raft算法的本质
无论是Raft算法还是Paxos算法，都依赖于复制状态机的模型，复制状态机的模型如下图所示：
简单的描述下这个模型就是：集群的多个节点上都拥有相同的初始状态（state） ...</div></div></div><div class="recent-post-item"><div class="post_cover left_radius"><a href="/2019/05/03/Paxos%E2%80%94%E2%80%94%E5%88%86%E5%B8%83%E5%BC%8F%E4%B8%80%E8%87%B4%E6%80%A7%E7%AE%97%E6%B3%95/" title="Paxos——分布式一致性算法"> <img class="post_bg" src="https://z3.ax1x.com/2021/04/10/castM9.jpg" onerror="this.onerror=null;this.src='/img/404.jpg'" alt="Paxos——分布式一致性算法"></a></div><div class="recent-post-info"><a class="article-title" href="/2019/05/03/Paxos%E2%80%94%E2%80%94%E5%88%86%E5%B8%83%E5%BC%8F%E4%B8%80%E8%87%B4%E6%80%A7%E7%AE%97%E6%B3%95/" title="Paxos——分布式一致性算法">Paxos——分布式一致性算法</a><div class="article-meta-wrap"><span class="post-meta-date"><i class="far fa-calendar-alt"></i><span class="article-meta-label">发表于</span><time datetime="2019-05-03T13:22:03.000Z" title="发表于 2019-05-03 21:22:03">2019-05-03</time></span><span class="article-meta"><span class="article-meta__separator">|</span><i class="fas fa-inbox"></i><a class="article-meta__categories" href="/categories/%E5%88%86%E5%B8%83%E5%BC%8F/">分布式</a></span></div><div class="content">
Google Chubby的作者Mike Burrows说过这个世界上只有一种一致性算法，那就是Paxos，其它的算法都是残次品。
Paxos算法问世已经有将近30年的历史了，是目前公认最有效的解决分布式场景下一致性问题的算法之一，但是缺点是比较难懂，工程化比较难。本文希望能够辅以图例和通俗易懂的实例把Paxos算法讲清楚。
Paxos算法的价值
在分布式系统中，在异步通讯的过程中，总会发生网络波动、机器宕机等情况，那么如何在这样复杂的情况下，快速且安全的就某一数值达成一致呢？Paxos算法主要就是解决此类问题，在布式锁、主从复制、命名服务、分布式协调等常见场景下，Paxos算法都有着广泛的应用。
基本概念
参与角色
在Paxos算法中，所有的参与者被分为了以下几个角色
角色
分工
参与决策
Proposer
提出提案，提案:[编号Id,提议的Value]
√
Acceptor
接收提案，批准/拒绝提案，当提案被大多数的Acceptor(Quorum)批准后即为被选定的提案(Chosen)
√
Learner
学习(Learn)最新被选定的提案
×
...</div></div></div><div class="recent-post-item"><div class="post_cover right_radius"><a href="/2019/04/25/Redis%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E5%8F%8A%E5%AF%B9%E8%B1%A1%EF%BC%88%E4%B8%8B%EF%BC%89/" title="Redis数据结构及对象（下）"> <img class="post_bg" src="https://z3.ax1x.com/2021/04/10/casdVx.jpg" onerror="this.onerror=null;this.src='/img/404.jpg'" alt="Redis数据结构及对象（下）"></a></div><div class="recent-post-info"><a class="article-title" href="/2019/04/25/Redis%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E5%8F%8A%E5%AF%B9%E8%B1%A1%EF%BC%88%E4%B8%8B%EF%BC%89/" title="Redis数据结构及对象（下）">Redis数据结构及对象（下）</a><div class="article-meta-wrap"><span class="post-meta-date"><i class="far fa-calendar-alt"></i><span class="article-meta-label">发表于</span><time datetime="2019-04-25T05:51:10.000Z" title="发表于 2019-04-25 13:51:10">2019-04-25</time></span><span class="article-meta"><span class="article-meta__separator">|</span><i class="fas fa-inbox"></i><a class="article-meta__categories" href="/categories/redis/">redis</a></span></div><div class="content">redisObject结构
实际上每一个redis都是一个redisObject对象。redis对象的类型检查，内存回收，对象共享都是基于redisObject完成的，下面来看一下redisObject的结构。
12345678910111213141516171819typedef struct redisObject { // 类型 unsigned type:4; // 对齐位 unsigned notused:2; // 编码方式 unsigned encoding:4; // LRU 时间（相对于 server.lruclock） unsigned lru:22; // 引用计数 int refcount; // 指向对象的值 void *ptr;} robj;
type：对象类型。
encoding: 对象编码方式。
lru: 对象的最近使用时间，配合内存回收使用 ...</div></div></div><nav id="pagination"><div class="pagination"><span class="page-number current">1</span><a class="page-number" href="/page/2/#content-inner">2</a><a class="extend next" rel="next" href="/page/2/#content-inner"><i class="fas fa-chevron-right fa-fw"></i></a></div></nav></div><div class="aside-content" id="aside-content"><div class="card-widget card-info"><div class="card-info-avatar is-center"><img class="avatar-img" src="/img/avatar.png" onerror="this.onerror=null;this.src='/img/friend_404.gif'" alt="avatar"/><div class="author-info__name">王家麟</div><div class="author-info__description"></div></div><div class="card-info-data"><div class="card-info-data-item is-center"><a href="/archives/"><div class="headline">文章</div><div class="length-num">11</div></a></div><div class="card-info-data-item is-center"><a href="/tags/"><div class="headline">标签</div><div class="length-num">9</div></a></div><div class="card-info-data-item is-center"><a href="/categories/"><div class="headline">分类</div><div class="length-num">5</div></a></div></div><a class="button--animated" id="card-info-btn" target="_blank" rel="noopener" href="https://github.com/wanglaomo"><i class="fab fa-github"></i><span>Follow Me</span></a></div><div class="card-widget card-announcement"><div class="item-headline"><i class="fas fa-bullhorn card-announcement-animation"></i><span>公告</span></div><div class="announcement_content">正是江南好风景 落花时节又逢君</div></div><div class="sticky_layout"><div class="card-widget card-recent-post"><div class="item-headline"><i class="fas fa-history"></i><span>最新文章</span></div><div class="aside-list"><div class="aside-list-item no-cover"><div class="content"><a class="title" href="/2020/01/17/LRU%E7%AE%97%E6%B3%95%E5%8F%8A%E5%85%B6%E4%BC%98%E5%8C%96%E7%AD%96%E7%95%A5%E2%80%94%E2%80%94Redis%E7%AF%87/" title="LRU算法及其优化策略——Redis篇">LRU算法及其优化策略——Redis篇</a><time datetime="2020-01-17T08:34:00.000Z" title="发表于 2020-01-17 16:34:00">2020-01-17</time></div></div><div class="aside-list-item no-cover"><div class="content"><a class="title" href="/2020/01/16/LFU%E7%AE%97%E6%B3%95%E5%8F%8A%E5%85%B6%E4%BC%98%E5%8C%96%E7%AD%96%E7%95%A5%E2%80%94%E2%80%94%E7%AE%97%E6%B3%95%E7%AF%87/" title="LFU算法及其优化策略——算法篇">LFU算法及其优化策略——算法篇</a><time datetime="2020-01-16T09:00:00.000Z" title="发表于 2020-01-16 17:00:00">2020-01-16</time></div></div><div class="aside-list-item no-cover"><div class="content"><a class="title" href="/2020/01/16/LRU%E7%AE%97%E6%B3%95%E5%8F%8A%E5%85%B6%E4%BC%98%E5%8C%96%E7%AD%96%E7%95%A5%E2%80%94%E2%80%94%E7%AE%97%E6%B3%95%E7%AF%87/" title="LRU算法及其优化策略——算法篇">LRU算法及其优化策略——算法篇</a><time datetime="2020-01-16T09:00:00.000Z" title="发表于 2020-01-16 17:00:00">2020-01-16</time></div></div><div class="aside-list-item no-cover"><div class="content"><a class="title" href="/2020/01/16/LRU%E7%AE%97%E6%B3%95%E5%8F%8A%E5%85%B6%E4%BC%98%E5%8C%96%E7%AD%96%E7%95%A5%E2%80%94%E2%80%94Mysql%E7%AF%87/" title="LRU算法及其优化策略——Mysql篇">LRU算法及其优化策略——Mysql篇</a><time datetime="2020-01-16T08:34:00.000Z" title="发表于 2020-01-16 16:34:00">2020-01-16</time></div></div><div class="aside-list-item no-cover"><div class="content"><a class="title" href="/2020/01/01/Dubbo%E6%9C%8D%E5%8A%A1%E6%9A%B4%E9%9C%B2%E6%BA%90%E7%A0%81%E5%88%86%E6%9E%90/" title="Dubbo服务暴露源码分析">Dubbo服务暴露源码分析</a><time datetime="2020-01-01T09:00:00.000Z" title="发表于 2020-01-01 17:00:00">2020-01-01</time></div></div></div></div><div class="card-widget card-categories"><div class="item-headline">
<i class="fas fa-folder-open"></i>
<span>分类</span>
</div>
<ul class="card-category-list" id="aside-cat-list">
<li class="card-category-list-item "><a class="card-category-list-link" href="/categories/mysql/"><span class="card-category-list-name">mysql</span><span class="card-category-list-count">1</span></a></li><li class="card-category-list-item "><a class="card-category-list-link" href="/categories/redis/"><span class="card-category-list-name">redis</span><span class="card-category-list-count">3</span></a></li><li class="card-category-list-item "><a class="card-category-list-link" href="/categories/%E5%88%86%E5%B8%83%E5%BC%8F/"><span class="card-category-list-name">分布式</span><span class="card-category-list-count">3</span></a></li><li class="card-category-list-item "><a class="card-category-list-link" href="/categories/%E5%90%8E%E7%AB%AF/"><span class="card-category-list-name">后端</span><span class="card-category-list-count">1</span></a></li><li class="card-category-list-item "><a class="card-category-list-link" href="/categories/%E7%AE%97%E6%B3%95/"><span class="card-category-list-name">算法</span><span class="card-category-list-count">3</span></a></li>
</ul></div><div class="card-widget card-tags"><div class="item-headline"><i class="fas fa-tags"></i><span>标签</span></div><div class="card-tag-cloud"><a href="/tags/Dubbo/" style="font-size: 1.1em; color: #999">Dubbo</a> <a href="/tags/mysql/" style="font-size: 1.1em; color: #999">mysql</a> <a href="/tags/redis/" style="font-size: 1.3em; color: #99a1ac">redis</a> <a href="/tags/zookeeper/" style="font-size: 1.1em; color: #999">zookeeper</a> <a href="/tags/%E5%88%86%E5%B8%83%E5%BC%8F/" style="font-size: 1.3em; color: #99a1ac">分布式</a> <a href="/tags/%E5%90%8E%E7%AB%AF/" style="font-size: 1.1em; color: #999">后端</a> <a href="/tags/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/" style="font-size: 1.3em; color: #99a1ac">数据结构</a> <a href="/tags/%E6%BA%90%E7%A0%81/" style="font-size: 1.1em; color: #999">源码</a> <a href="/tags/%E7%AE%97%E6%B3%95/" style="font-size: 1.5em; color: #99a9bf">算法</a></div></div><div class="card-widget card-archives"><div class="item-headline"><i class="fas fa-archive"></i><span>归档</span></div><ul class="card-archive-list"><li class="card-archive-list-item"><a class="card-archive-list-link" href="/archives/2020/01/"><span class="card-archive-list-date">一月 2020</span><span class="card-archive-list-count">5</span></a></li><li class="card-archive-list-item"><a class="card-archive-list-link" href="/archives/2019/12/"><span class="card-archive-list-date">十二月 2019</span><span class="card-archive-list-count">1</span></a></li><li class="card-archive-list-item"><a class="card-archive-list-link" href="/archives/2019/06/"><span class="card-archive-list-date">六月 2019</span><span class="card-archive-list-count">1</span></a></li><li class="card-archive-list-item"><a class="card-archive-list-link" href="/archives/2019/05/"><span class="card-archive-list-date">五月 2019</span><span class="card-archive-list-count">2</span></a></li><li class="card-archive-list-item"><a class="card-archive-list-link" href="/archives/2019/04/"><span class="card-archive-list-date">四月 2019</span><span class="card-archive-list-count">2</span></a></li></ul></div><div class="card-widget card-webinfo"><div class="item-headline"><i class="fas fa-chart-line"></i><span>网站资讯</span></div><div class="webinfo"><div class="webinfo-item"><div class="item-name">文章数目 :</div><div class="item-count">11</div></div><div class="webinfo-item"><div class="item-name">本站总字数 :</div><div class="item-count">35.4k</div></div><div class="webinfo-item"><div class="item-name">本站访客数 :</div><div class="item-count" id="busuanzi_value_site_uv"></div></div><div class="webinfo-item"><div class="item-name">本站总访问量 :</div><div class="item-count" id="busuanzi_value_site_pv"></div></div><div class="webinfo-item"><div class="item-name">最后更新时间 :</div><div class="item-count" id="last-push-date" data-lastPushDate="2021-04-10T07:23:30.498Z"></div></div></div></div></div></div></main><footer id="footer"><div id="footer-wrap"><div class="copyright">©2020 - 2021 By 王家麟</div><div class="framework-info"><span>框架 </span><a target="_blank" rel="noopener" href="https://hexo.io">Hexo</a><span class="footer-separator">|</span><span>主题 </span><a target="_blank" rel="noopener" href="https://github.com/jerryc127/hexo-theme-butterfly">Butterfly</a></div></div></footer></div><div id="rightside"><div id="rightside-config-hide"><button id="darkmode" type="button" title="浅色和深色模式转换"><i class="fas fa-adjust"></i></button><button id="hide-aside-btn" type="button" title="单栏和双栏切换"><i class="fas fa-arrows-alt-h"></i></button></div><div id="rightside-config-show"><button id="rightside_config" type="button" title="设置"><i class="fas fa-cog fa-spin"></i></button><button id="go-up" type="button" title="回到顶部"><i class="fas fa-arrow-up"></i></button></div></div><div><script src="/js/utils.js"></script><script src="/js/main.js"></script><script>var preloader = {
endLoading: () => {
document.body.style.overflow = 'auto';
document.getElementById('loading-box').classList.add("loaded")
},
initLoading: () => {
document.body.style.overflow = '';
document.getElementById('loading-box').classList.remove("loaded")
}
}
window.addEventListener('load',preloader.endLoading())</script><div class="js-pjax"></div><script async data-pjax src="//busuanzi.ibruce.info/busuanzi/2.3/busuanzi.pure.mini.js"></script></div></body></html>