• 2014-03-14

    C++ STL 迭代器的失效原则

    Views: 12604 | No Comments

    有一段时间, 我对 STL 的容器有一些疑惑, 那便是如何快速将地将给定的元素从容器中删除. 例如 std::list 是链表, 本应支持快速的 O(1) 的删除操作, 但给定的 remove() 方法是 O(n) 成本的. 后来, 我才明白, C++ STL 的迭代器(iterator)不仅仅用来遍历容器, 它们的另一作用便是实现那些不是很直观的操作.

    先举一个 C 语言链表的例子, 节点的结构体一般这样定义:

    struct Node{
    	struct Node *prev, *next;
    	Item item;
    };
    

    Continue reading »

    Posted by ideawu at 2014-03-14 09:50:51
  • 2014-03-08

    有趣的 main 函数参数

    Views: 10815 | 6 Comments

    大家都知道, C 语言可执行程序的入口是 main 函数, main 函数的原型是这样:

    int main(int argc, char **argv);
    

    编译程序生成可执行文件后, 从命令行运行, 参数 argc 是指命令行参数的个数(包括程序本身), 而参数 argv 则是所有参数字符串.

    你有没有想过, 为什么 argv 的类型是 char**, 而不是 const char** 呢? 难道 argv 的内容也可以被修改? 没错! 命令行传过来的参数是可以被修改的. 而修改后能带来什么好处呢? 其实, 你可以通过修改 argv 来更改进程在 top/ps 中的显示. 例如, 如果你的可执行文件是 a.out, 那么你可以让它在 top/ps 显示成 abc, 也就是修改进程的名字.

    Continue reading »

    Posted by ideawu at 2014-03-08 11:35:23
  • 2014-02-15

    长连接技术的应用

    Views: 16555 | 2 Comments

    Web 技术太流行而且太强大了, 以至于我们在开发任何应用时, 都会想到利用 Web 技术. Apache, PHP, Java, HTTP, JSON, ... 只需要简单且流行的技术, 就能搭建一个系统.

    但是, 对于另一类重要的需要服务器向客户端推送数据的应用, 传统的 Web 技术就不适用了, 因为 Web 的基础网络协议 HTTP 是请求响应模式, 一旦客户端不请求, 服务器就无法将数据推送给客户端. 而如果客户端的请求太过频繁(轮询), 那么就会对服务器造成巨大的压力.

    为此, 需要有一种被称为长连接服务的技术. 长连接技术包含客户端和服务器两部分, 可以看成是传统的 Client-Server 架构. 而对应的长连接服务器, 就提供了网络连接管理和消息发送的功能. 比较有意思的是, 长连接技术也被应用到了 Web 领域, 实现所谓的"服务器推"技术, 也称 Comet 技术.

    Continue reading »

    Posted by ideawu at 2014-02-15 14:53:50 Tags:
  • 2014-02-10

    百行代码实现一个简单的Zset(SortedSet)

    Views: 22195 | 5 Comments

    排序的集合(Zset, SortedSet)是这样的一种集合数据结构, 集合中的元素不可重复, 而且元素之间根据每一个元素的权重来排序. Zset 是一种非常重要和应用广泛的数据结构, 是 Redis 数据库所支持的最核心一种. Zset 可用于排行榜, 好友列表, 去重, 历史记录等业务需求. 你可以理解一个 Zset 是一个下面结构的数据库表:

    item,   score
    UNIQUE, INDEX(int)
    

    Item 列被加了 UNIQUE 约束, 所以可以去重. Score 列是加了索引的整数列, 可用于排序.

    如果要在内存中实现一个 Zset 数据结构, 我们可以看 Redis 的源码.

    Continue reading »

    Posted by ideawu at 2014-02-10 20:28:11 Tags:
  • 2014-02-10

    Mac 奇怪的打开文件操作变复制打开文件操作

    Views: 7197 | No Comments

    最近, 我的 Mac 操作遇到一个诡异的行为. 有一个文件, 每次我在 Finder 里双击打开它时, 都会在同目录下生成一个新的 Copy 文件, 相当于打开操作变成了复制并打开.

    我尝试改文件名, 更改打开方式, 都不行. 后来在文件信息里发现"样板"(Stationery pad)这个选项是选中状态的. 将这个选中去掉, 就OK了.

    在网上一查, 原来这个选项就是把文件变成模板, 双击打开时, 就是复制出一个新的文件, 然后再打开. 这其实是一个毫无意义的功能.

    Posted by ideawu at 12:32:06
  • 2014-02-10

    结合IO多路复用的多线程服务器模型

    Views: 24399 | 3 Comments

    IO 多路复用技术, 就是常说的 select/epoll/kqueue 等处理文件描述符相关的函数. 在高性能高并发网络服务器的实现时, IO 多路复用技术可以用来处理多个 socket 连接的读写 IO 操作, 避免了传统的每一个 socket 连接分配一个单独的线程的低效的多线程技术.

    虽然多线程在处理高并发网络 IO 方面是低效的, 但是, 多线程在处理业务相关的逻辑方面是有优势的, 而且多线程能利用多核 CPU.

    所以, 一个高性能高并发的网络服务器, 应该是结合了 IO 多路复用技术和多线程技术的.

    IO 多路复用技术用于处理网络 IO, 而多线程用于处理业务逻辑. 那么, 这两种技术是如何结合的呢?

    整个服务器的流程是这样的: IO 多路复用接口层从客户端 socket 中读取了完整的请求报文之后, 便将请求报文转交给线程池, 线程处理完业务逻辑, 生成响应报文, 转交给 IO 多路复用接口层, 发送给客户端. 示意图如下:

            bytes                         packet
    Client ------- IO Multiplexing Layer -------- Thread Pool
    

    这样, 一个重要的问题就来了. 线程池和 IO 多路复用层之间的交互是报文(其实就是内存操作), 但是, IO 多路复用层只能处理文件描述符, 也就是 read()/write() 系统调用. 因此, 两者的交互必须从报文传递转换成文件描述符的操作. 所以, 我们需要一个可以 select/epoll/kqueue 的队列.

    为此, 我用管道(pipe)封装了一个 SelectableQueue 类, 可以和 IO 多路复用层无缝结合. 这个技术已经在 SSDB 数据库服务器中使用了, 感兴趣的朋友可以获取 SSDB 的源码看看.

    唯一的不足是, 管道通信在 10us 左右的延时, 所以会影响单个请求的处理时间, 但是, 对于高并发的网络服务器来说, 单个请求的处理时间的微小增加, 并不会对整个服务器的吞吐量有明显影响, 所以整个服务器的处理能力仍然非常高.

    Posted by ideawu at 10:54:31
|<<<123456789>>>| 4/12 Pages, 71 Results.