Understanding Linux Network Internals 1.2.2

icedragon

1.2.2. Caching and Hash Tables
It is pretty common to use a cache to increase performance. In the networking code, there are caches for L3-to-L2 mappings (such as the ARP cache used by IPv4), for the routing table cache, etc.
1.2.2. 缓存和Hash表
通常使用一个缓存来提高性能。在网络代码中, 有缓存用于 L3层-到-L2层 映射 (像 IPv4 的用于 ARP 缓存 ),用于路由表缓存, 等等。
Cache lookup routines often take an input parameter that says whether a cache miss should or should not create a new element and add it to the cache. Other lookup routines simply add missing elements all the time.
缓存查询的常规方式通常是输入一个叁数到缓存，来判断缓存是否错过这个参数，如果失败就应该新建一个新的元素而且把它加入到缓存中。 其他的查询方式只是始终添加丢失的元素。
Caches are often implemented with hash tables . The kernel provides a set of data types, such as one-way and bidirectional lists, that can be used as building blocks for simple hash tables.
缓存经常通过Hash表来执行。内核提供一组数据类型, 像是单行道和双向性目录，他们能用来做为构造阻塞通过简易的Hash表
The standard way to handle inputs that hash to the same value is to put them in a list. Traversing this list takes substantially longer than using the hash key to do a lookup. Therefore, it is always important to minimize the number of inputs that hash to the same value.
对相同的值处理的标准方法是操作 Hash 把他们放入一个列表中。通过这个表可以充分持久的使用 Hash key 来做查询。 因此, 最重要的是输入 Hash 表对于同样的值尽可能的少。
When the lookup time on a hash table (whether it uses a cache or not) is a critical parameter for the owner subsystem, it may implement a mechanism to increase the size of the hash table so that the average length of the collision lists goes down and the average lookup time improves. See the section "Dynamic resizing of per-netmask hash tables" in Chapter 34 for an example.
当查询时间在一张 Hash 表 (是否它使用一个缓存) 上是一个临界的叁数对于子系统的拥有者, 它可能实现一个机制去增加 Hash 表的大小以便降低列表内容碰撞的平均长度和改善平均的查询时间。一个例子在第 34 章中 " 由子网掩码动态恢复的Hash表" 。
You may also find subsystems, such as the neighboring layer, that add a random component (regularly changed) to the key used to distribute elements in the cache's buckets. This is used to reduce the damage of Denial of Service (DoS) attacks aimed at concentrating the elements of a hash table into a single bucket. See the section "Caching" in Chapter 27 for an example
你也可能找像邻近层这样的子系统,用来增加一个任意的成份(经常变化的)作为关键(Key)用来分配元素在缓存的桶 。 这用来减少针对集中Hash表的元素进入一个桶子中的拒绝式服务类攻击 (Dos)的损害。 参考 在第 27 章中 " 缓存 " 的例子
/*看不懂这段话意思的朋友 可以参考下HASH的桶概念
散列文件的存储单位称为桶（BUCKET）。假如一个桶能存放m个记录，当桶中已经有m个同义词（散列函数值相同）的记录时，存放第m+1个同义词会发生“溢出”。此时需要将第m+1个同义词存放到另一个“溢出桶”的桶中。相对的，称存放 前m个同义词的桶称为基桶。溢出处桶和基桶大小相同，用指针链接。查找指定元素记录时，首先在基桶中查找。若找到，则成功返回，否则沿指针到益处桶中查找。为了简化起见，散列文件的存储单位以内存单元表示------译者注*/


本文来自ChinaUnix博客，如果查看原文请点：http://blog.chinaunix.net/u/1880/showart_71268.html