Redis设计与实现-基本数据结构

SDS(简单动态字符串)

Redis只使用C字符串作为字面量,其他地方都使用SDS来表示字符串,定义如下:

1
2
3
4
5
6
// 简单动态字符串
struct sdshdr {
int len; // buf已用字节数,也是字符串长度
int free; // buf未用字节数
char buf[];// 保存字节的数组
};
  • SDS与C字符串类似,以’\0’结尾,但len不计’\0’的长度;
  • SDS和C字符串相比:
    1. 有了len字段,可以常数时间获得字符串长度;
    2. 有了free字段,可以避免缓冲区溢出;
    3. 可以减少内存重分配的次数:
      1. 空间预分配:当需要扩展buf空间时,为buf分配额外的空间。修改后的len如果小于1MB,就分配和len相同大小的额外空间,大于1MB则分配1MB的额外空间;
      2. 惰性空间释放:当SDS长度缩短时,并不立刻回收内存,而是先用free记录空闲的空间,当必要时才释放空闲空间;
    4. 有了len字段,SDS也是二进制安全的,因为SDS使用len而不是’\0’来判断字符串结束;
    5. 由于SDS以’\0’结尾,所以兼容部分C字符串函数;
  • 总结一下:
C字符串 SDS
获取strlen为O(N) 获取strlen为O(1)
API不安全,缓冲区可能溢出 API安全,缓冲区不会溢出
修改字符串N次必然需要N次内存重分配 修改字符串N次最多需要N次内存重分配
只能保存文本数据 可以保存文本或二进制数据
可以使用所有\<string.h>函数 可以使用部分\<string.h>函数
阅读更多
说说我对Haskell的执念

先放上我个人认为很帅的图标:
个人认为很帅气的图标

谈到Haskell,当时我只是在网上偶然看到函数式编程,便起了兴趣,想去了解一下,毕竟大学时间比较多,多了解一些东西也是好的。经过知乎上一番搜索,最后是选择了Haskell来了解函数式语言,因为它比较(然而我现在也没接触过其他函数式语言,Lisp,Scala等,也不太懂到底怎么纯的……)。

既然想学,就要去搜一些Haskell的学习资料啦,现在让我来推荐的话,《Learn You a Haskell for Great Good!》、《Haskell WikiBook》、《Real World Haskell》大概是这三本,然后做做H-99: Ninety-Nine Haskell Problems就差不多入门了吧,然而我只看了第一本,初步领略了一下函数式编程的乐趣(?)就没再看了。

阅读更多
负载均衡是什么

什么是负载均衡

我们都知道,当我们上网时,服务器无时无刻工作着,为我们提供服务。随着互联网的发展,业务流量越来越大且业务逻辑越来越复杂,单机服务器的性能已无法满足业务要求,为此,我们需要多台服务器进行性能的水平拓展,但如何平均地将流量分发到多台服务器上呢?这就是负载均衡。

负载均衡的方法

负载均衡整体上分为两大类:

  • 四层负载均衡:在OSI的前四层进行负载均衡,根据报文的目的地址和端口号,决定提供服务的服务器;
  • 七层负载均衡:在OSI的整七层进行负载均衡,主要是在应用层,通过报文中的内容来决定提供服务的服务器;

阅读更多
浅谈Google C++代码风格

C++作为一门极其复杂的语言,使用好它是十分困难的,C++的灵活语法和复杂特性使得C++变得无比强大,但这也导致它变得十分复杂,曾经我觉得使用越多高级特性的代码就越厉害,而现在我无法赞同,绝大多数情况下,代码的可读性和可维护性是第一位的,而C++正是因此而变成了“最难”的语言,不同人、团队的C++代码风格相差甚远,各种技巧用得飞起,在这种情况下,如果能有一个规范,使得代码尽量统一,就能在一定程度上解决C++代码难以维护的问题。

尽管Google C++代码风格是针对Google自身情况制定的,限制和禁止了很多特性(由于历史原因等),但对于我这种新手,仍十分有帮助。

头文件

  • 一个头文件要自给自足,使用者没有义务知道头文件是否依赖其他的头文件并自行包含。
  • 根据#include头文件的原理,头文件的确是可以用来插入文本的,学习一下。
  • 防止多次包含是常识。
  • 超过10行、递归、含有循环和switch的函数不应内联。
阅读更多
APUE-IPC部分

进程间通信

管道

1
int pipe(int fd[2]);
  • 管道是半双工的,且只能在有公共祖先的两个进程之间使用;
  • fd[0]可读,fd[1]可写;
  • 通常用法是先pipe,然后fork,这样父子进程就可以通信:

    fork后的管道

  • 读一个写端已关闭的管道,在所有数据都读取后,read返回0,表示文件结束;

  • 写一个读端已关闭的管道,会产生SIGPIPE,write返回-1,errno设置为EPIPE;
  • 若多个进程同时写管道,且写字节数超过PIPE_BUF,则数据可能相互交叉;
阅读更多
APUE-高级I/O部分

高级IO

非阻塞IO

对于可能使进程永远阻塞的系统调用,如果不想进程一直阻塞,可以将系统调用设为非阻塞:

  • open时指定O_NONBLOCK标志;
  • fcntl对一个打开的描述符设置O_NONBLOCK标志;

这样,如果系统调用无法满足要求,会立刻返回并设定相应错误标志。

记录锁

记录锁保证不会有多个进程同时修改一个文件的同一区域,设置记录锁的POSIX方法是通过fcntl:

  • cmd为F_GETLK, F_SETLK, F_SETLKW, arg是指向flock结构的指针;
阅读更多
APUE-线程部分

线程

线程特点

  • 可以简化异步代码;
  • 共享进程资源;
  • 自身仍有线程ID,寄存器,栈,调度信息,信号屏蔽字,errno,线程私有数据;
  • 需要同步,一个线程异常会导致整个进程异常;

线程创建

1
2
3
4
5
int pthread_equal(pthread_t tid1, pthread_t tid2);
pthread_t pthread_self(void);

int pthread_create(pthread_t *thread, const pthread_attr_t *attr,
void *(*start_routine) (void *), void *arg);
  • tid存入thread指向空间;
  • attr定义线程属性:
    • 初始化一个属性对象传入;
    • 通过pthread_attr_setdetachstate()设置detachstate属性可使线程创建时就是detach态;
  • 线程从start_routine地址开始运行,参数为arg。
阅读更多
APUE-信号部分

信号

什么是信号

信号提供的是一种处理异步事件的方法,有很多种信号,很多条件可以产生信号,对于进程来说,信号何时发生是无法预测的,进程只能保证当信号发生时做什么,有下面三种做法:

  1. 忽略信号:SIGKILL和SIGSTOP无法忽略;
  2. 捕捉信号:捕捉信号并调用指定函数,SIGKILL和SIGSTOP无法捕捉;
  3. 执行系统默认动作;

中断的系统调用

当执行一个慢速系统调用——可能使进程永远阻塞的系统调用——阻塞时,若捕捉到信号,则此系统调用被中断,出错返回并设置EINTR,有的系统调用会自动重启,有的不会,请注意。

阅读更多