url排重和bloom filter(转载)

October 11, 2007

from http://blog.csdn.net/accesine960/archive/2007/01/23/1491483.aspx.

误差换效率

google黑板报上一片文章,讲Url排重用到的一个技巧:把平均长度较长的Url转换成平均长度较短的GUID来节省空间。在Url排重方面还有一个常用的算法:Bloom Filter 算法。Bloom Filter 算法是查看元素E是否在集合S中存在的快速算法,典型的应用就是拼写检查spellcheck时,查看某个单词是否在字典中存在。关于查询的算法有很多种了,排序折半、B-Tree、Hash-Code 等等。Bloom Filter 的优点是什么呢?

1、Bloom Filter不存储key-value值,Bloom Filter 用一组Hash算法把集合S中的元素E换算成位表示;

2、查询速度快。

我们知道Hash算法一般都有冲突,在Bloom Filter中的冲突就表现为误差了。

Bloom Filter 是一种常见的算法,现在已经有了 Java , C++ , C# , ruby 等各个版本的算法。当然也有很多变种出现以适应更多的需求。

Bloom Filter 是有误差的,但误差在可控制的程度内。换句话说,大多数的误差的恼人之处在于我们无法衡量它。

参考阅读:

http://blog.likeshow.net/article.asp?id=34

http://blogs.msdn.com/devdev/archive/2006/01/23/516431.aspx

http://en.wikipedia.org/wiki/Type_I_and_type_II_errors

http://en.wikipedia.org/wiki/Bloom_filter

http://jaspell.sourceforge.net/javadocs/index-files/index-2.html

http://blogs.msdn.com/devdev/archive/2005/08/17/452827.aspx

http://www.cc.gatech.edu/fac/Pete.Manolios/research/bloom-filters-verification.html

http://homepages.inf.ed.ac.uk/s9902505/specksim/doc/index-files/index-2.html

http://weblogs.asp.net/dfindley/archive/2004/08/19/217485.aspx

http://www.darkridge.com/~jpr5/archive/dads/HTML/bloomFilter.html

http://loaf.cantbedone.org/


有效运用auto_ptr

October 9, 2007

 

有效运用auto_ptr

auto_ptr是一个类模板,用于生成具体的智能指针,它们知道在用完以后如何清理资源。如:

using std::auto_ptr;

auto_ptr<Shape> aShape(new Circle);

aShape->draw(); //画一个circle

(*aShape).draw(); //再画一个circle

如同所有设计良好的智能指针一样,auto_ptr重载了operator->和operator *,因此通常可以假装自己在处理一个内建的指针。

auto_ptr有很多好处,首先非常高效。其次,当auto_ptr离开作用域时,其析构函数将会释放它所指向的任何东西。在上面的代码片段中,aShape所指向的Circle对象们将会有效地被垃圾收集。再次,在类型转换方面,其行为酷似内建指针。如

auto_ptr<Circle> aCircle(new Circle);

aShape = aCircle;

通过灵活使用模板成员参数,一个auto_ptr可以赋值给另一个,只要相应的内建指针支持这种操作就可。在上面的代码中,一个auto_ptr<Circle>可以赋值给 auto_ptr<Shape>,因为一个Circle*可以赋值给一个Shape*(假定Shape是Circle的一个公有基类)。

auto_ptr不同于普通的智能指针的地方在于其赋值操作。当auto_ptr执行赋值操作时,参与赋值的源值和目标值都受到了影响。

auto_ptr在两个场合应该避免使用。首先,他们永远都不应该被用做容器元素。其次,一个auto_ptr应该指向单个元素,而不该指向一个数组。


sam’s linux study上一篇感慨文章

October 1, 2007

linux工程師悲哀

最近接連的幾個面試

讓我有非常的感觸

其實台灣大多數的軟體工作都是windows為主

linux的工作並不是那麼多

裏面又許多是linux device driver

因此本來linux的軟體工程師在台灣的生存就不容易

最近的面試中

很多面試主管都有一個相同的論調

雖然他們要找會linux的engineer

但是如果不能全面都可以的話

工程師的value就不高

這裡所謂的value又是指”除了linux外, 你還要作windows programming”

這往往讓我十分挫敗

但是我常常想到

往往一整間的windows engineer都不會linux

那個不算value不高….但是linux engineer不熟windows programming就是value不高

這種的評量標準我常常不能接受

或許windows是市佔率最高的OS

但是若你要找的是linux engineer, 為何要為難他不熟windows呢

今天還聽到一個有趣的說法

因為linux是open source的一個產物

任何人都可以拿到source code去看

因此他是很簡單的

但是windows因為不知道內部如何運作

所以windows的engineer比較厲害

linux的engineer只是去看code而已, windows的engineer卻都是厲害的hacker

我不知道這樣的說法對不對

不過讓我深深的想到

或許我真的不適合當個software engineer吧

認真思考自己的未來…..

———————————————-

感觉作者有些太悲观了,呵呵。做什么工作都会找到用武之地的。


blogspot.com又解除封锁了

October 1, 2007

今天查些资料,google到一篇blogspot.com上的文章,直接点击就进去了,竟然没有用到代理。


Linux kernel map(flash video)

October 1, 2007


Linux2.6 内核的 Initrd 机制解析(from IBM developworks)

September 30, 2007

http://www.ibm.com/developerworks/cn/linux/l-k26initrd/

initrd 的英文含义是 boot loader initialized RAM disk,就是由 boot loader 初始化的内存盘。在 linux内核启动前, boot loader 会将存储介质中的 initrd 文件加载到内存,内核启动时会在访问真正的根文件系统前先访问该内存中的 initrd 文件系统。


将内核数据写到用户空间缓冲区的一般操作

September 29, 2007

内核空间中,不能像写应用程序一样直接把buffer(这是内核的内存)里直接将数据写到另一个缓冲区(用户空间的)里面,或直接从用户空间的缓冲区里读数据。
Linux 里使用FS 寄存器来保存kernel space 和 user space 的切换的状态。所以,如果你想手动的话,可以这样做:

mm_segment_t fs;
fs = get_fs();
set_fs(get_ds());
write_data_to_buf(buf);
set_fs(fs);

也就是先切换到用户空间, 把数据写道buf缓冲区里面,最后再切换回来。

内核的API提供了几个函数来完成切换,就是copy_to_user(), copy_from_user();它们的核心操作都是用汇编实现的代码 ,效率高。


struct sk_buff

September 17, 2007

struct sk_buff结构被网络的各个层所使用,链路层、网络层和传输层都用到了该数据结构。为了增进处理网络数据包的效率,Linux没有使用在各层之间拷贝数据的方式来传输数据,而采用了增加头部信息的方式来处理。在一块缓冲区的前面增加一块空间,只要将指针的值改变一下就好了,内核使用skb_reserve()来实现操作.

当数据向下传递,直至由网络设备把包发送出去之前,每层协议在处理packet时的第一件事情就是调用skb_reserve()。

但是,当数据是向上传递(网络设备接收到了新的数据)时,之前的协议层的信息就没有什么用了,这时只会将指针指向新的协议层,这样是为了节省CPU时间,提高效率。

管理struct sk_buff结构的几个函数:

static inline void skb_reserve(struct sk_buff *skb, unsigned int len);
static inline unsigned char *skb_put(struct sk_buff *skb, unsigned int len);
static inline unsigned char *skb_pull(struct sk_buff *skb, unsigned int len);
static inline unsigned char *skb_push(struct sk_buff *skb, unsigned int len);

skb_reserve()对一个空缓冲区,通过更改skb->tail和skb->data指针,为headroom预留空间。

skb_put()通过改变skb->tail的指针,减小tail域空间,往skb_buff中增加数据,增加到尾部;

skb_push()通过改变skb->data的指针,增加数据到skb_buff的头部。

skb_pull()改变skb->data指针,把缓冲区里面的数据从buffer的开头去除掉。


SKB(struct sk_buff)数据结构的部分分析

September 17, 2007

我参考的原文地址是http://vger.kernel.org/~davem/skb.html,记录在这里主要是为了帮助自己好理解内核中网络部分的代码。

在Linux内核中,socket buffer(SKB)是Linux内核网络协议代码中最重要的基础。每一个发送或者接收的packet的处理都需要用到该数据结构。
下面结合其数据结构的各成员变量来说明其组成元素和在网络处理过程中发挥的作用:

     struct sk_buff {

/* These two members must be first. */

struct sk_buff *next;

struct sk_buff *prev;

struct sk_buff_head *list;

next 和prev是用来实现list链表的功能。packets在许多类型的链表list和队列queues中出现,比如一个TCP socket的发送队列。list参数来指明当前这个packet是在哪个队列之上。

     struct sock *sk;     

sk用来记录与SKB相关的socket.当一个packet到来或者要被发送出去的时候,与它相关的内存必须传给该socket来进行合适的内存计数。

     struct timeval stamp;     

stamp用来记录其时间戳,或者是到来时候的时间或者是发送出去的时间。但是计算时间的耗费是很大的,因此能避免就避免,除非有必要。net_enable_timestamp()和net_disable_timestamp()是与它相关的两个函数。
stamp在截包进行分析时很有用,还有可以用来实现一些特定的socket选项,还有一些net filter模块也会用到stamp。

     struct net_device *dev;

struct net_device *input_dev;

struct net_device *real_dev;

这三个变量用来帮助记录与该包相关的设备。之所以有这三个不同的网络设备来记录,是因为通过一个虚拟设备的时候,skb->dev可能会被改变。
因此,如果从一个设备A接收到packet,而这个设备A是一个绑定设备实例的一部分,(这个地方没理解作者原文的意思-_-!)。开始的时候skb->dev指向这个设备A,然后会把skb->dev赋给skb->real_dev,而skb->dev会更新为真正被帮定的设备。
同样的,当物理设备收到一个包的时候,它会将自己记录为skb->input_dev。这样,不管虚拟设备存在多少layers,skb->input_dev都能够被找到并确认为从网络上接收数据的真正设备。

     union {

struct tcphdr *th;

struct udphdr *uh;

struct icmphdr *icmph;

struct igmphdr *igmph;

struct iphdr *ipiph;

struct ipv6hdr *ipv6h;

unsigned char *raw;

} h;

union {

struct iphdr *iph;

struct ipv6hdr *ipv6h;

struct arphdr *arph;

unsigned char *raw;

} nh;

union {

unsigned char *raw;

} mac;     

这里保存的是各个协议层的头指针,在构造发送的包和解析接收到的包的时候极其有用。比如,skb->mac.raw被eth_type_trans()设置,当一个ethernet包被接收到的时候。然后我们就可以用skb->mac.raw来确定起mac地址的头。

     struct dst_entry *dst;     

dst是用来记录该包相关的路由。它告诉我们怎样将一个包送到最终目的地;它记录的不仅仅是输入所需的路由,也包括输出的。该数据结构同样复杂,暂不详述。

     struct sec_path *sp;     

不理解,不解释。

     char cb[40];     

它是SKB的控制块。它属于不透明的存储块(private_data?), 经常被协议和一些设备驱动程序用来存储与每个包相关的私有数据。比如,TCP利用它来存储序列号和帧的重传状态。

     unsigned int len,

data_len,

mac_len,

csum;     

len是指整个packet的大小。data_len是指当SKB是由多个页面缓冲组成的时候,在页面缓冲区域的字节总数(现在还没有研究它的具体意思,因此理解的不清楚,可能是错误的)。
mac_len保存的是MAC头的长度。一般来说它是没有必要维护的,只有在一些特殊的处理时才需要,比如IPSEC。
csum记录着该包的checksum。当我们构建一个往外发的packet的时候,先把数据从userpaace得到数据,然后计算checksum,它被累计在skb->csum中。这能够帮助我们计算最终的checksum。有时候可以忽略,当硬件设备来完成包的checksum时。
在处理输入的情况时,csum可以用来存储由设备计算出来的checksum值。如果设备提示 skb->ip_summed = CHECKSUM_HW,意味着csum是记录从skb->data开始的数据区域的checksum值。

     unsigned char local_df,

cloned:1,

nohdr:1,

pkt_type,

ip_summed;     

cloned用来得到对SKB数据的快速的索引,Linux建立起了cloned的概念。
pkt_type存储了该packet的类型信息,如PACKET_*,它的定义在linux/if_packet.h中。包括,PACKET_HOST, PACKET_BOARDCAST, PACKET_MULTICAST等等。
ip_summed记录进行checksum的方式.

     __u32 priority;     

它被用来实现QoS.

     unsigned short protocol,     security;     

protocol域是由像eth_type_trans()这样的方法来初始化的,它被赋予一个类诉ETH_P_*的值,在头文件linux/if_ether.h中有描述。

     void (*destructor)(struct sk_buff *skb);

//...

unsigned int truesize;     

这两个域用来做socket buffer的计数。

     atomic_t users;     

我们使用users域来记录SKB对象的引用情况。相关的函数有skb_get();kfree_skb();


unsigned char *head,

*data,

*tail,

*end;     

这4个指针是用来管理一个SKB包的线性存储空间的核心.它们表示了SKB缓冲区和数据部分的边界。

对应区域如下图所示:

+——–+ <—– head
|headroom|
|        |
+——–+ <—– data
|  data  |
|        |
|        |
|        |
+——–+ <—– tail
|tailroom|
|        |
+——–+ <—– end


packet在Kernel的TCP/IP栈中的数据流向图

September 10, 2007