Redis里dict源码剖析

Redis全名叫做Remote Dictionary Server,从全称就可以看出dict是Redis里重要的数据结构,看了下dict.c里的源码,简单分析下。

dict.c主要是实现了哈希功能,实际上实现哈希(字典)常见的方法有几种:

<1>比如我们数据结构课上学的数组和链表法,但是这种方法适用于元素个数不多的情况下

<2>使用复杂的平衡树(B-等等),性能比较不错,比如MySQL里的索引就使用了这种方法

<3>哈希表,兼顾了高效和简单性,Redis选择了这种方法。

我们就解读下dict.c里源码里的数据结构吧,我们知道hash表的性能由hash表的大小和解决冲突的方法决定。Redis里使用了两个哈希表(ht[0])和哈希表(ht[1]),hash[0]是字典主要使用的hash表,而hash[1]主要对0号哈希表进行rehash时才使用。读者可能不明白这个地方啥意思?其实就是,程序每次申请几个字节(默认为4字节),当key/value数量达到规定时,程序申请的4字节就翻一倍(这里使用了慢迁移),那什么时候rehash呢?我们知道size == used(根据下面的dictht结构体)时,达到最理想状态,所以当used/size > 1时,就进行rehash。我们先看看dict.h里定义的几个结构体吧:

Read More

Letter Combinations of a Phone Number

由于这个月还没写博客,找道题应付下吧,主要原因是自己现在太忙了,得准备找工作啊,唉,弱的惨不忍睹。好吧,不抱怨了,进入正题,LeetCode上面的一道题,题目描述为:

Given a digit string, return all possible letter combinations that the number could represent.

A mapping of digit to letters (just like on the telephone buttons) is given below.

**Input:**Digit string "23"
**Output:** ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].
**
Note:**
Although the above answer is in lexicographical order, your answer could be in any order you want.

其实就是组合问题,如下图所示:

如图所示,遍历完 1,2,3,就把a,d (g,h,i)遍历完了,之后回溯到e,就是个DFS搞定。

Read More

使用python编写简单网络爬虫技巧总结

使用python写过几个小玩具,基本上都与爬虫、Web相关的,自己也积累了下经验,也看过很多文章,一直想总结下,可惜现在要忙于找工作,实验室活也比较多,也就落下了。感觉如果时间长不记录,也就懒散了,并且许多东西我写完过个两天,我自己都记不住当时怎么想的了。

0、HTTP协议

基本上常见的Web开发里,Web内容都是通过HTTP协议进行传输的(虽然咱不懂Web开发,但是基本的计算机网络知识还是了解的),通过TCP连接服务器的80端口,爬虫其实质就是通过模拟浏览器发送HTTP请求,至于HTTP请求相关知识,点击这里

1
2
3
4
HTTP通常通过创建到服务器80端口的TCP连接进行通信
HTTP协议的内容包括请求方式(method), urlheaderbody,通常以纯文本方式发送
HTTP返回内容包括状态码,headerbody,通常以纯文本方式返回
header以及body间以CRLF(\r\n)分割

1、最基础的抓取网站内容

使用python编写一个网络爬虫是非常简单的,如下例所示:

1
2
3
import urllib2
content = urllib2.urlopen('http://armsword.com').read()

Read More

Linux IO复用—select poll 和 epoll

在Socket编程时,为了处理大量客户的连接请求,需要使用非阻塞I/O和端口复用,select、poll和epoll是Linux API提供的I/O复用方式。其实在*nix下的网络并发方法向来不缺,比如典型的Apache模型(Process Per Connection,简称PPC),TPC(Thread Per Connection)模型,这两种模型思想类似,就是利用了多进程、多线程概念,让进来的每一个连接去干别的事情去。但是连接多了以后,首先需要较大的内存,且进程/线程切换开销会非常大,因此这类模型能接受的最大连接数都不会太高。

Linux 2.6中加入了epoll之后(据说Windows下使用的是IOCP,但是我没使用过),在高性能服务器领域中得到广泛的应用,主要原因就是高效。在讲epoll之前,我们先总结下select、poll,因为epoll其实也就是他们的增强版本,比如select是一个系统调用,而epoll是个模块,由三个系统调用组成,内核中由文件系统实现。

Read More

记录下传输层协议TCP和UDP的一些特性

在TCP/IP中能够实现传输层功能的、具有代表性的协议是TCP和UDP。

TCP

TCP是面向连接的、可靠的流协议。流就是指不间断的数据结构,你可以把它想象成排水道中的水流。当应用程序采用TCP发送消息时,虽然可以保证发送的顺序,但还是犹如没有任何间隔的数据流发送给接收端。TCP充分地实现了数据传输时各种控制功能,可以进行丢包时的重发控制,还可以对次序乱掉的分包进行顺序控制。而这些在UDP中都没有。此外,TCP作为一种面向有连接的协议,只有在确认通信对端存在时才会发送数据,从而可以控制通信流量的浪费。根据TCP的这些机制,在IP这种无连接的网络上也能够实现高可靠性的通信。

TCP为提供可靠性传输,实行“顺序控制”或“重发控制”机制。此外还具备“流控制(流量控制)”、“拥塞控制”、提供网络利用率等众多功能。

TCP通过检验和、序列号、确认应答、重发控制、连接管理以及窗口控制等机制实现可靠性传输。

Read More

实现一个LRU Cache

1.什么是Cache和LRU Cache

狭义的Cache指的是位于CPU和主存间的快速RAM, 通常它不像系统主存那样使用DRAM技术,而使用昂贵但较快速的SRAM技术。 广义上的Cache指的是位于速度相差较大的两种硬件之间, 用于协调两者数据传输速度差异的结构。除了CPU与主存之间有Cache, 内存与硬盘之间也有Cache,乃至在硬盘与网络之间也有某种意义上的Cache── 称为Internet临时文件夹或网络内容缓存等。

CPU中Cache能极大提高存取数据和指令的时间,让整个存储器(Cache和内存)既有Cache的高速度,又能有内存的大容量;操作系统中的内存Page中使用的Cache能使得频繁读取的内存磁盘文件较少的被置换出内存,从而提高访问速度;数据库中数据查询也用到Cache来提高效率;即便是Powerbuilder的DataWindow数据处理也用到了Cache的类似设计。

Cache的算法设计常见的有FIFO(first in first out)和LRU(least recently used)。LRU是Least Recently Used的缩写,意思是最近最少使用,它是一种Cache替换算法。Cache的容量有限,因此当Cache的容量用完后,而又有新的内容需要添加进来时, 就需要挑选并舍弃原有的部分内容,从而腾出空间来放新内容。LRU Cache 的替换原则就是将最近最少使用的内容替换掉。其实,LRU译成最久未使用会更形象, 因为该算法每次替换掉的就是一段时间内最久没有使用过的内容。

Read More

linux内存空间分配和内存管理

前段时间把《程序员的自我修养–链接、装载与库》这本书看完了,期间有些地方不是太明白,当时网络搜索了下,今天把当时看到的东西摘抄下,基本文中大部分内容都是拷贝下面提到的参考链接里的东西,自己在组织下,以备以后需要时查看。

地址分为三类,逻辑地址,线性地址和物理地址。

在《深入理解linux内核》中其把地址分为三类:逻辑地址(汇编语言中操作数地址或指令的地址,对于80x86的CPU,逻辑地址是段+段内偏移地址)、线性地址(也叫虚拟地址)和物理地址。但在Stott Maxwell的《Linux Core Kernel Commentrary》中确是这样分的:逻辑地址(也叫虚拟地址)、线性地址和物理地址。按照386CPU总设计师John Crowford的解释,虚拟地址是保护模式下段和段内偏移量组成的地址,而逻辑地址就是代码段内偏移量,或称进程的逻辑地址。其实对于linux来说,这三种说法都没错,由于linux下并不主张将程序分段,而是主张分页,所以即使是在80x86的体系结构下,段的基地址也是0。因此逻辑地址、线性地址、虚拟地址在linux中其实是相同的。所以对于linux下的ELF可执行文件来说,代码段的起始地址0x08048000既是逻辑地址,也是线性地址也是虚拟地址。

1.X86的物理地址空间布局


以x86_32,4G RAM为例:

Read More