文章归档

1、spinlock

关于MCS Spinlock的锁释放问题补充一点,关键的问题是,A在判断自己是否是最后一个申请者和如果是的话就释放mcs_lock,这两个操作无法保证原子性(而且必须是原子才行,因为这中间如果出现新的申请者,情况就会变化),所以 才要依赖cmp_and_swap操作。

ticket spinlock和mcs_spinlock其实思路是一样的。

还有很重要的一个就是:申请了锁却忘了释放绝对是致命的

2、RCU

go语言TCPConn.Close()方法处理不当引发的bug

今天服务器引发了一个很罕见的bug。原因是因为TCPConn在Close的时候,把fd给清空掉了,如下:

// Close closes the TCP connection. func (c *TCPConn) Close() error { if !c.ok() { return syscall.EINVAL } err := c.fd.Close() c.fd = nil return err }

而TCPConn是经常在多个goroutine里同时使用的。

// Read implements the Conn Read method. func (c *TCPConn) Read(b []byte) (n int, err error) { if !c.ok() { return 0, syscall.EINVAL } return c.fd.Read(b) }

这样就很有可能当某个goroutine,判断!c.ok(),为真,然后尝试读取数据时。注意,这个过程,中间,if语句之后和Read()数据之前,很可能TCPConn已经被关闭,fd被置为nil了,引发panic

go1版本有这个问题。新版已经fix了。不过我还觉得蛮奇怪的,想不清楚为什么作者要这么写。。。

Open Clound storage service

国庆这几天写的,套用阿里云的名称,就叫开放云存储服务吧,初衷只是想测试一下存储商的速度,后来发觉php写的SpeedTest不太好用,因为要依赖php和其他各个组件。

后来折腾了一下hiphop,这玩意依赖太过分了,用的很不爽,就用go重新实现了一遍存储的SDK。目前OCSS支持四个主流的云存储服务,包括盛大云,阿里云,又拍和七牛。它们的API是一样的(看起来是一样的,呵呵)

数据结构

在package fs里,有Object和Bucket,主要的结构如下,但不同的存储商的SDK又各有一些不同的地方,可看源码

type Object struct { EntryURI string Type string Mtime string Size int64 Body io.ReadWriter } type Bucket struct { EntryURI, Delimiter string Objs []*Object CommonPrefixes []string }

EntryURI通常由Bucket和Key组成,例如"/testbucket/resume.pdf"或者是"/testbucket/music/",Object可以表示一个文件或者目录。Bucket里的Delimiter是用来进行前缀查询的,会一直匹配到Delimiter才结束,然后返回的对象会保存到Objs和CommonPrefixes里,Objs通常可以理解成文件,CommonPrefixes可理解成当前路径下的文件夹名

存储API

所有的SDK都实现了如下的API,用法几乎是完全一样的,当然,还有其他的。

func (s *Service) Get(localfile, entryURI string) (code int, err error) func (s *Service) Put(entryURI, mimeType, localfile string) (code int, err error) func (s *Service) Delete(entryURI string) (code int, err error) func (s *Service) PutObject(o *fs.Object) (code int, err error) func (s *Service) GetObject(o *fs.Object) (code int, err error) func (s *Service) DelObject(o *fs.Object) (code int, err error) func (s *Service) NewBucket(b *fs.Bucket) (code int, err

»» 继续阅读全文

转让两部闲置手机

首先是HTC touch HD,wm 6.1系统,经典机型,已用4年,功能一切正常,是当年买的法国Orange的水货,原价2800,现在200出吧,:-) 其他参数就不说了,喜欢的可自行查一下参数

------- 送给喜欢怀旧的小伙伴们

另外一款就是诺基亚N97,用了不到三年,如下:

SILT: small index and Large table

SILT's multi-store design

The most common approach to build a hign performence key-value storage system uses two components:logstore and sortedstore. But in the implementation of SILT, it add a HashStore for sloving the high write amlication problem when merge logstore into sortedstore by traditional way. how to manage the sortedstore isn't key to performance, i think, just a little infulence.

In fact, SILT isn't a generic key-value store because of its keys are uniformly distributed 160bit hash value(e.g., pre-hashed key with SHA-1), but doing it fixed length as SILT have done here is so much convenient for compressing

»» 继续阅读全文

Libtask: c和linux/unix下的协程库

实现协程核心的文件只有几个,其中*-ucontext.h是特定平台上下文切换功能的实现,是几个用户态的API。以386平台为例:

extern int swapcontext(ucontext_t*, const ucontext_t*); extern void makecontext(ucontext_t*, void(*)(), int, ...); extern int getmcontext(mcontext_t*); extern void setmcontext(const mcontext_t*);

task.c/task.h是调度器的实现。其实明白上面这几个API,基本上就可以知道协程是怎么干活的了。下面主要分析task.c代码。

使用libtask构建程序不需要显式地使用main函数,只需一个taskmain即可,因为main函数是在task.c里实现的,也就是libtask的调度。

----- task.c ------ int main(int argc, char **argv) { .... taskcreate(taskmainstart, nil, mainstacksize); taskscheduler(); .... }

taskcreate创建了第一个协程,这个协程就是用户的taskmain函数,将其加入调度队列,然后进入调度函数taskscheduler(),taskscheduler()不会返回

static void taskscheduler(void) { int i; Task *t; for(;;){ if(taskcount == 0) exit(taskexitval); t = taskrunqueue.head; if(t == nil){ fprint(2, "no runnable tasks! %d tasks stalled\n", taskcount); exit(1); } deltask(&taskrunqueue, t); t->ready = 0; taskrunning = t; tasknswitch++; contextswitch(&taskschedcontext, &t->context); taskrunning = nil; if(t->exiting){ if(!t->system) taskcount--; i = t->alltaskslot; alltask[i] = alltask[--nalltask]; alltask[i]->alltaskslot = i; free(t); } } }

contextswitch切换到到协程t去执行了,从t返回的情况有两种,要么是协程执行完毕了,要么是用户主动的yield,然后等待下次继续被执行。

<busying, todo...>

LIRS缓存

参考文献:LIRS: An Efficient Low Inter-reference Recency Set Replacement Policy to Improve Buffer Cache Performance

LIRS算法主要计算两个参数,IRR和Recency,IRR表示一个页面最近两次被访问访问间隔,Recency表示页面最近一次被访问到现在的访问间隔。IRR越小,表明最近可能经常被访问,Recency越大,表明最近很久没被访问。IRR和Recency的计算方法如下:

这就是LIRS的理论模型,在任何一个时刻,缓存中的每个页面都会有一个IRR值和Recency值。LIRS的核心思想是,如果一个页面当前的IRR越大,将来的IRR会更大。

论文中没有对LIRS的实现作过多的描述,只是简单提到了一个基于Stack的实现方法。

一、替换规则

和LRU不同的是,就是当缓存达到阈值时

  1. 如果是LRU,就会将Recency值最大的那个页面剔除出去,因为这个页面是最近最久没有被访问的
  2. 如果是LIRS,优先剔除IRR值最大的页面,因为IRR越大,说明这个页面过去很少被访问,理所当然认为它在将来可能不会再被访问或者相对其他页面来说最不可能再被访问到。如果有两个页面的IRR相同,则剔除Recency值最大的页面。

显然,LIRS只是一个多了IRR参数的LRU

(待)

linear counting algorithm

最近看了篇文章:Big Data Counting: How to count a billion distinct objects using only 1.5KB of Memory

比较感兴趣,于是找了原论文来看看:A Linear-Time Probabilistic Counting Algorithm for Database Applications / HyperLogLog : the analysis of a near-optimal cardinality estimation algorithm. 无奈hyperloglog实在复杂,难以理解,哪天看懂了再分享吧。

linear counting的作用就是统计集合的容量。算法思想和bloom-filter差不多,很多时候精确计算是很难做到的,但是可以允许一定的误差,从而通过这个误差的概率分析来折射整个全局的概貌。

  1. Algorithm Basic Linear Counting:
  2. Let key_{i} = the key for the ith tuple in the relation.
  3. Initialize the bit map to "0"s.
  4. for i = 1 to q do
  5. hash_value = hash( key_{i} )
  6. bit map(hash_value) = "1"
  7. end for
  8. U_{n} = number of "0"s in the bit map
  9. »» 继续阅读全文

zeroqp, make the server network programming sample and interesting.

zeroqp 是我这两天做的一个小东西。将传统的服务器网络编程转为服务化。zeroqp适合特定的场景,比如我自身的需求。所以zeroqp不是万能的。在其他更多的场合可能反而会令程序变得更加蹩脚。用自己的工具,解决自己的问题。好吧。我承认我又在意淫了。。。

zeroqp 主要有三个简单的API,zeroqp_open(), zeroq_ctl(), zeroqp_wait()

zeroqp_open() 会返回一个专用的描述符,但是并不是一个真正的文件句柄,自然不能用read() write()等系统调用去操作它。zeroqp_ctl() 函数用来向系统注册一个服务,或者删除一个服务。而只要 zeroqp_wait() 一旦执行,系统就会处于监听状态。zeroqp 会启动所有的服务并打开相应的端口,等待客户端进行链接。我们需要做的,仅仅是在zeroqp_wait()启动之前注册一些服务而已。

  1. int32_t zeroqp_ctl(int32_t zfd, int32_t op, struct zeroqp_service *zs);
  2. #define ZEROQP_CTL_ADD 0x01
  3. #define ZEROQP_CTL_DEL 0x02

服务是由结构提 struct zeroqp_service 装载的,在安装服务之前需要一些服务的基本信息,struct zeroqp_service 的结构如下,

  1. struct zeroqp_service {
  2. int8_t inet_addr[INET_ADDRSTRLEN];
  3. int32_t inet_port;
  4. int8_t zqp_srv[ZQPS_NAMESTRLEN];
  5. _srv_callback *zqp_cbfunc;
  6. }

inet_addr 字段,保存的是IP地址串,可以是IPv4也可以是IPv6,inet_port为该服务器上的某个端口,zqp_srv是需要注册的服务名字,是zeroqp_service的唯一标识。zqp_cbfunc是服务的回调函数。

zeroqp 所有的服务都是异步执行的,单线程,适合快速响应的需求,如IO密集型服务,不适合计算密集型的场景。不过大家可以改成自己的,分享一下就更好了。

举个简单的例子来描述一下zeroqp的用途:

某个公司有个客服部门,主要的工作就是向客户提供服务。至于提供什么服务,是由公司来决定的。比如客户需要维修电脑,会先打个电话给该公司的客服部门,该公司的客服部门接受到需求之后,先分析这个服务是不是我们可以提供的,如果可以,就转交到相应的人员去处理,如果不是,这个过程就结束了。

在这里,公司就是使用zeroqp的开发人员,你可以给你的server定制各种服务,接受服务请求是epoll来异步通知的。struct zeroqp_service 结构的作用是相当于告诉操作系统,我需要在某个IP地址和端口上打开一条热线电话。实际上tcp_listen()了一个监听端口。然后在这个端口上绑定各种定制的服务。

zeroqp 允许你在同一个IP地址和端口上安装不同的服务。

zeroqp 同样允许你在不同的IP地址和端口上安装相同的服务。

甚至,zeroqp 允许你在相同的IP地址和不同的端口上安装相同的服务。。。哈哈,混乱了吧。。。

其实我知道你只有一个IP,所以zeroqp就是说,让你在不同的端口安装不同的服务,每个端口有自己的服务队列,不同端口的服务之间是相互独立的,不受影响的。

_srv_callback *zqp_cbfunc; zqp_cbfunc是服务执行的回调函数,就是说如果某个客户端链接上来了,需要请求某个服务,就执行这个callback function()。zeroqp 会自动分析和提取客户端提供的各种参数,然后通过 _srv_callback 的入口 argc 和 argv 传入给 cbfunc。

_srv_callback(int32_t fd, int32_t argc, slice **argv);

比如说,我在server上安装了一个名为 sum 的服务,专门负责计算各个参数的和。然后客户端链接server,需要使用这种服务,client提供了三个参数 23,43,33,当server检测到有需求请求时,分析这个请求是哪个服务的然后转向执行相应的回调函数,也就是上面的_srv_callback实例对象。client提供的参数会通过字符串传入 _srv_callback 里。在这里 argc = 3, argv[0]->data = "23",argv[1]->data =

»» 继续阅读全文

猜解leveldb写性能

如题,猜测。

我们知道leveldb的很出色,随机读写的性能可以分别达到 164,000 ops/sec 和 129,000 ops/sec,这是官方的Benchmarks数据。

leveldb最关键的核心技术在于基于level思想的sstable文件compact策略,因为这种设计,大大的改善了Random Writes的性能。levledb的memtable/immutable是一个skiplist链表,而skiplist insert的时间复杂度是O(logn),也就是说,insert的时间复杂度是随着问题规模的增长而线性上升的,呵呵,不知到大家注意到没。

高性能kv的实现现在跑的比较火的就数lsm-tree,主要的思路就是先在内存里cache到某个阀值然后dump到磁盘,再由其他线程或者进程来进行compact操作,于是首先会引出的第一个问题是:

1、sstable文件的管理以及如何执行compact的操作,这个地方直接影响到读性能,这也是为什么采用lsm-tree的key-value存储引擎读性能一直提升不上去的原因,尤其是一些老旧数据的检索。

我当初也主要没考虑过在skiplist这一部分做过优化,毕竟skiplist主要还是内存操作。

但是leveldb的作者可不是这么想的,这种想法可真是so easy但是又很难引起大家的注意:就是靠缩小问题的规模来达到提升insert性能的目的。我今晚在食堂吃饭,想到这点的时候就没差点笑喷了,有意思,哈哈 ^_^

但是如果这样做的话会导致sstable文件会非常的多,而且会产生大量的小文件,所以如果没有一套非常优秀的compact策略的话只有傻子才会这样做,我当初在研究lsm论文后,采用的思想是直接dump大sstable文件,sstable文件量小,容易管理,查询性能也比较好,当然后来也意识到很多问题,这是后话了。

所以Jeff Dean和Sanjay Ghemawat设计了一种基于level的compact策略,然后让memtable达到一个非常小的阀值后直接dump成小文件,由后台进程来进行compact管理。memtable的阀值由 write_buffer_size(include/leveldb/options.h)控制,默认是4mb左右,假设key是20bytes,value是80bytes,这个阀值可以容纳4w个entries左右。

根据skiplist的查找时间复杂度O(logn),我在本机上做了一个简单的测试,主要计算随着规模的增长每随机插入一条数据的开销。

测试环境:

Date: Tue Apr 17 23:45:07 2012 CPU: 2 * Pentium(R) Dual-Core CPU T4400 @ 2.20GHz CPUCache: 1024 KB System: Centos Linux 2.6.32-220.el6.i686 #1 SMP Tue Dec 6 16:15:40 GMT 2011 i686 i686 i386 GNU/Linux

实际上只使用了一个CPU,测试结果

测试代码:https://github.com/pipul/coutune/tree/master/skiplist

很明显,随着skiplist的cardinality不断变大,插入每条数据的开销越来越多,不过当n趋向无穷大的时候,这种变化会渐趋不明显。而在刚开始的时候,insert开销抖增。所以,想要获得最好的random writes性能,skiplist的cardinality尽量控制到百万级别以下

第 10 页,共 13 页« 最新...89101112...最旧 »