MySQL · RocksDB · MANIFEST文件介绍

概述

在RocksDB中MANIFEST保存了存储引擎的内部的一些状态元数据,简单来说当系统异常重启,或者程序异常被退出之后,RocksDB需要有一种机制能够恢复到一个一致性的状态,
而这个一致性的状态就是靠MANIFEST来保证的.

阅读全文

MySQL · RocksDB · WAL(WriteAheadLog)介绍

概述

在RocksDB中每一次数据的更新都会涉及到两个结构,一个是内存中的memtable(后续会刷新到磁盘成为SST),第二个是WAL(WriteAheadLog)。
本篇文章主要就是来介绍WAL.

阅读全文

Lua源码剖析(五)

这次主要来分析lua的gc。

首先lua中的数据类型包括下面9种,ni, Boolean, number, string, table,user data, thread , functions 以及 lightusedata.其中 string, table,thread , function 是会被垃圾回收管理的,其他的都是值存在。

因此我们来看对应的GC数据结构.

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
  
#define CommonHeader GCObject *next; lu_byte tt; lu_byte marked

typedef struct GCheader {

CommonHeader;

} GCheader;

union GCObject {

GCheader gch;

union TString ts;

union Udata u;

union Closure cl;

struct Table h;

struct Proto p;

struct UpVal uv;

struct lua_State th; /\* thread \*/

};

我们可以看到在lua中字符串,userdata, thread, table ,string, thread(以及Upval, proto) 都会被垃圾回收管理。这里比较关键的就是GCheader这个结构体,我们可以看到这个结构体其实就是一个链表,也就是说所有的gc对象都会被链到一个链表中,其中tt表示当前对象的类型,在lua中包括下面这些类型:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
  
#define LUA_TNIL 0

#define LUA_TBOOLEAN 1

#define LUA_TLIGHTUSERDATA 2

#define LUA_TNUMBER 3

#define LUA_TSTRING 4

#define LUA_TTABLE 5

#define LUA_TFUNCTION 6

#define LUA_TUSERDATA 7

#define LUA_TTHREAD 8

而marked表示当前对象的状态(涉及到gc算法,后续会详细分析),状态位包括下面这些:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
  
#define WHITE0BIT 0

#define WHITE1BIT 1

#define BLACKBIT 2

#define FINALIZEDBIT 3

#define KEYWEAKBIT 3

#define VALUEWEAKBIT 4

#define FIXEDBIT 5

#define SFIXEDBIT 6

#define WHITEBITS bit2mask(WHITE0BIT, WHITE1BIT)

阅读全文

Lua源码剖析(四)

前面三篇请看我前面的 blog

这篇主要来分析lua的虚拟机的实现,我看的代码依旧是5.1

因此首先从luaL_loadfile开始,这个函数我们知道是在当前的lua state加载一个lua文件,其中第二个参数就是filename。

其中LoadF结构很简单,它用来表示一个load file:

struct LoadF {
1
2
3
4
5
6
7
8
    
int extraline;

FILE *f;

char buff[LUAL_BUFFERSIZE];

} LoadF;

其中会使用fopen来打开对应的文件名,然后根据第一个字符来判断是否是注释(#),如果是则跳过

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
      
lua_pushfstring(L, "@%s", filename);

lf.f = fopen(filename, "r");

if (lf.f == NULL) return errfile(L, "open", fnameindex);

}

c = getc(lf.f);

if (c == ‘#’) { /\* Unix exec. file? \*/

lf.extraline = 1;

while ((c = getc(lf.f)) != EOF && c != ‘\n’) ; /\* skip first line \*/

if (c == ‘\n’) c = getc(lf.f);

}

阅读全文

Early Retransmit for TCP原理以及实现

Early Retransmit for TCP(ER)是google为了解决快重传的一些局限,从而对快重传(fast retransmit)做出的一些改变,其中ER在linux kernel 3.5进入了内核,他的paper在这里:

http://tools.ietf.org/html/rfc5827

首先我们要知道快重传算法的弱点很多,比如如果发送端接收不到足够数量(一般来说是3个)的ack,那么快重传算法就无法起作用,这个时候就只能等待RTO超时。ER主要就是为了解决这个问题的。在下面的条件下,就会导致收不到足够的ack。

  • 拥塞窗口比较小
  • 窗口中一个很大的段丢失或者在传输的结尾处发生了丢包

阅读全文

linux 内核tcp拥塞处理(二)

这篇接的是我最早在javaeye的那篇blog. http://simohayha.iteye.com/blog/614258

首先我们要知道在linux下分为5个拥塞状态,定义如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
  
enum tcp_ca_state {

TCP_CA_Open = 0,

#define TCPF_CA_Open (1<<TCP_CA_Open)

TCP_CA_Disorder = 1,

#define TCPF_CA_Disorder (1<<TCP_CA_Disorder)

TCP_CA_CWR = 2,

#define TCPF_CA_CWR (1<<TCP_CA_CWR)

TCP_CA_Recovery = 3,

#define TCPF_CA_Recovery (1<<TCP_CA_Recovery)

TCP_CA_Loss = 4

#define TCPF_CA_Loss (1<<TCP_CA_Loss)

}

TCP_CA_OPEN这个就是初始状态,也就是没有检测到任何拥塞的情况.

TCP_CA_Disorder 顾名思义,这个状态就是当第一次由于收到SACK或者重复的ack而检测到拥塞时,就进入这个状态.

TCP_CA_CWR 由于一些拥塞通知事件而导致拥塞窗口减小,然后就会进入这个状态。比如ECN,ICMP,本地设备拥塞。

TCP_CA_Recovery 当CWND减小

TCP_CA_Loss 超时或者SACK被拒绝,此时表示数据包丢失,因此进入这个状态.

阅读全文

tcp拥塞算法vegas分析

tcp的vegas算法是基于delay的一个拥塞控制算法,所谓基于delay也就是说窗口的变化只和RTT的变化相关。而传统的基于丢包的算法是窗口的变化和丢包相关.

先来看原理,paper地址在这里(94年提出来的),基本上linux的实现就是按照paper来实现的,注意Vegas它是第一个基于delay的拥塞算法.

http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.100.9587&rep=rep1&type=pdf

它的主要思想是估计一段时间能够发送的数据量,然后和最终发送的数据量比较。如果预测要发送的数据没有被发送,那么就会被认为可能出现拥塞状况,如果这个状态持久,那么就减慢发送速度,并且这个算法不仅作用于拥塞避免状态,而且还作用于slow start状态。

不过vegas的缺点也是很明显.那就是他会被欺骗,也就是说本身这个正向的延迟就是比它期待的高,比如在tcp中,有可能正向反向做的不是相同的路径,那么当反向有拥塞的时候,就有问题了。也就是数据包ack返回给发送端的就是延迟的。此时就会导致Vegas降低拥塞窗口。这个问题就是基于延迟的拥塞算法的一个陷阱。不过在linux下vegas算法被打开,只有是正常状态才会被打开,而只要遇到异常(丢包/快重传..)就会使用经典的newreno算法.

并且如果连接都是Vegas算法,那么这些连接就是公平的,而如果有些是,有些不是,那么就不是公平的了,因此经典的tcp发送者是会尝试填满网络中的队列,而Vegas是尝试着保持队列为空。因此最终就会导致使用经典tcp拥塞算法的,发送的数据包越来越多,而Vegas的就会越来越慢。

阅读全文

tcp中RTO的计算以及linux下的实现

计算RTT以及RTO的代码比较简单,我们先来看原理,首先相关的rfc有两篇分别是rfc793以及rfc6298,而相关的paper有一篇,那就是Van Jacobson和Michael J. Karels的 Congestion Avoidance and Control这篇paper,这篇1988年的paper中描述的RTT计算方法,就是我们当前所使用的计算方法,可能有的操作系统有一点修改,不过基本的东西都一样。

首先RTT是什么,RTT简单来说,就是我发送一个数据包,然后对端回一个ack,那么当我接到ack之后,就能计算出从我发送出包到接到过了多久,这个时间就是RTT。RTT的计算是很简单的,就是一个时间差。

而RTO呢,RTO也就是tcp在发送一个数据包之后,会启动一个重传定时器,而RTO就是这个定时器的重传时间,那么这个时候,就有问题了,由于RTO是指的这次发送当前数据包所预估超时时间,那么RTO就需要一个很好的统计方法,来更好的预测这次的超时时间。

我们所能想到的最简单的方法,那就是取平均数,比如第一次RTT是500毫秒,第二次是800毫秒,那么第三次发送的时候,RTO就应该是650毫秒。其实经典的RTO计算方法和取平均有点类似,只不过因子不太一样,取平均的话,也就是老的RTO和新的RTT都是占50%的权重,而在经典的RTO计算中就有些变化了。

阅读全文

nginx least_conn 模块源码剖析

nginx在1.3.1添加了一个新模块 least_conn,也就是我们常说的最少连接负载均衡算法,简单来说就是每次选择的都是当前最少连接的一个server(这个最少连接不是全局的,是每个进程都有自己的一个统计列表)。

在看最少连接模块之前需要对round robin模块有一定的了解,这里我就不对round robin模块进行分析了,想要看这块代码,可以去我们组 卫岳的blog的这篇文章

http://blog.sina.com.cn/s/blog_7303a1dc01014i0j.html

ok,接下来就来看这个模块,首先来看如何打开least_conn模块:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
  
static ngx_command_t ngx_http_upstream_least_conn_commands[] = {

{ ngx_string("least_conn"),

NGX_HTTP_UPS_CONF|NGX_CONF_NOARGS,

ngx_http_upstream_least_conn,

0,

0,

NULL },

ngx_null_command

};

阅读全文

打开tcp_tw_recycle引起的一个问题

今天普空说了一个问题就是如果设置了tcp_tw_recycle ,那么如果客户端是NAT出来的,那么就可能会出现连接被直接rst的情况。然后我google了下,在内核列表也有人说了这个问题 https://lkml.org/lkml/2008/11/15/67

The big problem is that both are incompatible with NAT. So if you

ever talk to any NATed clients don’t use it.

阅读全文