唐福林 博客雨

Network partitions

bdb replication 的实现可能被网络隔离的问题影响。

例如，考虑replication组有n个成员。网络隔离让master在一边，多于一半（n/2）的站点在另外一边。和master在一边的站点将继续 前进，master继续接受数据库的写请求。不幸的是，隔离在另一边的站点，意思到他们的master不在了，将举行一个选举。这个选举将取得成功，因为 这儿有总数n/2以上的站点在这边，然后这个组内将会有两个master。既然两个master都可能潜在地接受写请求，那么数据库将可能产生分歧，使得 数据不一致。

如果曾经在一个组内发现了多个master，一个master检测到这个问题的时候将会返回DB_REP_DUPMASTER。如果一个应用程序看到这个 返回，它应该重新配置自己作为一个client（通过调用ENV->rep_start），然后发起一场选举（通过调用 DB_ENV->rep_elect）。赢得这次选举的可能是先前的两个master之一，也可能完全就是另外的站点。无论如何，这个胜出的系统将 引导其它系统达到一致。

作为另外一个例子，考虑一个replication组有一个master环境和两个client，A和B，在那A可能会升级为master地位而B不可能。然后，假设client A从其他的两个数据库环境中被隔离出来了，它的数据变的过期。然后假设这个master倒掉了，而且不再上线。随后，网络隔离被修复了，client A和B进行了一次选举。因为client B不能赢得选举，client A将会默认地赢得这次选举，为了重新和B同步，可能在B上提交的事务将不能回滚直到这两个站点能再次地一起前进。

在这两个例子中，都有一步就是新选举出的master引导组内的成员和它自己一致，以便它可以开始发送新信息给它们。这可能会丢失信息，因为以前提交的事务没有回滚。

在体系结构上网络隔离是个问题，应用程序可能想实现一个心跳协议以最小化一个糟糕的网络隔离的影响。只要一个master至少可以和组内一半的站点通信的 时候，就不可能出现两个master。如果一个master不再能和足够的站点取得联系的时候，它应该重新配置自己作为一个client，和举行一次选 举。

这儿有另外一个工具应用程序可以用来最小化网络隔离情况下的损失。通过指定一个 nsites 参数给DB_ENV->rep_elect ，也就是说，比组内的实际成员的数目大，应用程序可以阻止系统宣布他们自己成为master，除非它们可以和组内绝大部分站点通话。例如，如果组内有20 个数据库环境，把参数30指定给DB_ENV->rep_elect方法，那么这个系统至少要和16个站点通话才可以宣布自己为master。

指定一个小于组内世界成员数目的nsites参数给DB_ENV->rep_elect，也有它的用处。例如，考虑一个组有只有两个数据库环境。如果他们被隔离了，其中任何一个都不能取得足够的选票数成为master。一个合理的选择是，指定一个系统的nsites 参数为2，另一个为1。那样，当被隔离的时候，其中一个系统可以赢得选举权，而另一个不能。这能允许当网络被隔离的时候其中一个系统能继续接受写请求。

这些关卡强调了bdb replicated环境中好的网络底层构造的重要性。当replicating数据库环境在严重丢包的网络环境中，最好的解决可能是拣选一个单一的master，只有当人工干涉决定这个被选择的master不能再恢复上线时，才举行选举。

Replication FAQ

• Does Berkeley DB provide support for forwarding write queries from clients to masters?

No, it does not. The Berkeley DB RPC server code could be modified to support this functionality, but in general this protocol is left entirely to the application. Note, there is no reason not to use the communications channels the application establishes for replication support to forward database update messages to the master, since Berkeley DB does not require those channels to be used exclusively for replication messages.

• Can I use replication to partition my environment across multiple sites?

No, this is not possible. All replicated databases must be equally shared by all environments in the replication group.

• I’m running with replication but I don’t see my databases on the client.

This problem may be the result of the application using absolute path names for its databases, and the pathnames are not valid on the client system.

• How can I distinguish Berkeley DB messages from application messages?

There is no way to distinguish Berkeley DB messages from application-specific messages, nor does Berkeley DB offer any way to wrap application messages inside of Berkeley DB messages. Distributed applications exchanging their own messages should either enclose Berkeley DB messages in their own wrappers, or use separate network connections to send and receive Berkeley DB messages. The one exception to this rule is connection information for new sites; Berkeley DB offers a simple method for sites joining replication groups to send connection information to the other database environments in the group (see Connecting to a new site for more information).

• How should I build my send function?

This depends on the specifics of the application. One common way is to write the rec and control arguments’ sizes and data to a socket connected to each remote site. On a fast, local area net, the simplest method is likely to be to construct broadcast messages. Each Berkeley DB message would be encapsulated inside an application specific message, with header information specifying the intended recipient(s) for the message. This will likely require a global numbering scheme, however, as the Berkeley DB library has to be able to send specific log records to clients apart from the general broadcast of new log records intended for all members of a replication group.

• Does every one of my threads of control on the master have to set up its own connection to every client? And, does every one of my threads of control on the client have to set up its own connection to every master?

This is not always necessary. In the Berkeley DB replication model, any thread of control which modifies a database in the master environment must be prepared to send a message to the client environments, and any thread of control which delivers a message to a client environment must be prepared to send a message to the master. There are many ways in which these requirements can be satisfied.

The simplest case is probably a single, multithreaded process running on the master and clients. The process running on the master would require a single write connection to each client and a single read connection from each client. A process running on each client would require a single read connection from the master and a single write connection to the master. Threads running in these processes on the master and clients would use the same network connections to pass messages back and forth.

A common complication is when there are multiple processes running on the master and clients. A straight-forward solution is to increase the numbers of connections on the master — each process running on the master has its own write connection to each client. However, this requires only one additional connection for each possible client in the master process. The master environment still requires only a single read connection from each client (this can be done by allocating a separate thread of control which does nothing other than receive client messages and forward them into the database). Similarly, each client still only requires a single thread of control that receives master messages and forwards them into the database, and which also takes database messages and forwards them back to the master. This model requires the networking infrastructure support many-to-one writers-to-readers, of course.

If the number of network connections is a problem in the multiprocess model, and inter-process communication on the system is inexpensive enough, an alternative is have a single process which communicates between the master the each client, and whenever a process’ send function is called, the process passes the message to the communications process which is responsible for forwarding the message to the appropriate client. Alternatively, a broadcast mechanism will simplify the entire networking infrastructure, as processes will likely no longer have to maintain their own specific network connections.
再次感谢 http://blog.sina.com.cn/dev

Synchronizing with a master

当一个client探测到replication组内一个新的master后，在它能去处理新的数据库变化之前，这个client必须去同步这个新的master。同步是一个重量级操作，它能同时给这个client和master增加负担。这儿有一些措施，一个应用程序可以用来减轻同步的负担：

• 延迟client同步：
  当组内有了一个新的master，不论是被应用程序指定的还是因为选举的结果，所有的clients必须去同步这个新的master。这会使新的 master的资源过度损耗，因为很多clients可能都试图去和它通信和从它那儿取得记录。clients应用程序如果想延迟client的同步，应 该用DB_REP_CONF_DELAYCLIENT标志去调用DB_ENV->rep_set_config 方法。这个配置使得client总从DB_ENV->rep_process_message方法返回DB_REP_NEWMASTER，但是这个 client将不会继续去同步这个新的master。Client端应用程序选择延迟同步，用这种方法，那么将来再用 DB_ENV->rep_sync方法去同步将是可靠的。

• client-to-client的同步：
  Clients可以接受和服务其他clients的请求。Clients请求记录调用这个Client应用程序的传输回调函数。可以由其他Clients 满足的请求，传输函数的标志被设置成DB_REP_ANYWHERE。应用程序可以选择发送这些请求到任意client，或者忽略这个标志，而把请求发送 到这个消息的环境id所指定的站点。
  Client应用程序可以用不管什么算法，它们选择来负载均衡到其它clients的请求。任何client接受到一个它不能满足的请求，都将回复给请求的client，告诉它，自己不能够提供请求的信息，而那个最初的请求者，将重新请求这个信 息。另外，如果这个最初的请求没有到达发要发送给的那个目标client端，这个最初的发送请求的client也将重新请求这个信息。这这些任意一种情况 下，这个重新的请求将把传输函数的标志设置成DB_REP_REREQUEST 。应用程序可能通过把这个请求进一步传递给naster来响应这个DB_REP_REREQUEST 标志（因为是被这个消息的环境id指定的），或继续把这个请求传送给另一个client。
  这延迟的同步和client-to-client的同步特性允许应用程序在replication组内做负载均衡。例如，考虑到一个组内有5个站点， A, B, C, D 和 E，站点E刚刚倒掉了，站点A被选举为master。站点C 和 D 被配置成延迟同步的，当B注意到站点A是一个新master，它立即进行同步。当B完成和master的同步的时候，站点C 和 D 上的应用程序调用 DB_ENV->rep_sync 方法，使它们也进行同步。站点C 和 D (和 E, 当它完成了重新引导) 可以发送他们的请求到站点 B, 而B可以负担因为同步而产生的工作和网络流量的冲击， 使的master，站点A，有空去处理正常的应用程序工作量和由于选举而暂停的写请求。

• 阻塞client的操作：
  Clients在处理和master的同步的时候将阻塞bdb其它的操作。默认的，许多bdb方法将阻塞，直到client同步完成，然后，这些被阻塞的方法才继续调用。
  那些不能等待的Client应用程序，将更愿意立即得到一个错误返回而不是阻塞，那么就应该用DB_REP_CONF_NOWAIT 标志调用DB_ENV->rep_set_config方法。如果这个clinet现在正在同步一个master，这个配置使得bdb方法调用立即返回一个DB_REP_LOCKOUT 错误，而不是阻塞。

• Clients太落伍以至于不能同步：
  Clients试图去和master同步的时候可能会发现，同步是不可能的了，因为client和master 已经失去联系很久了。默认地，client和master自动的检测这个状态和执行clinet内部初始化。因为内部初始化需要传输整个数据库到clinet，这可能会发费一个相对较长的时间，可能需要clinet应用程序的数据库句柄重新被打开。
  那些不能等待的应用程序，更愿意推后内部初始化直到一个更加便利的时间，或者更希望做一个热备份而不是执行内部初始化，应该用REP_CONF_NOAUTOINIT 标志来调用DB_ENV->rep_set_config方法。这个配置使得bdb返回DB_REP_JOIN_FAILURE到应用程序而不是执行内部初始化。
  Client应用程序如果选择了延迟同步，这样就有责任在将来的时间和master进行同步。这可以通过关闭DB_REP_CONF_NOAUTOINIT标志和调用DB_ENV->rep_sync 方法来完成，或通过执行一个热备份。

Initializing a new site

默认地，添加一个新站点到一个replication组，只需要这个client去加入。bdb将自动从master到client给它执行内部初始化， 引导这个client和master同步。尽管如此，还依赖于网络和底层结构，在一些场合下使用“热备份”在组内去初始化一个client还是比较有利 的。Clients不想自动执行内部初始化应该用DB_REP_CONF_NOAUTOINIT标志调用 DB_ENV->rep_set_config 方法。这个配置使得bdb返回DB_REP_JOIN_FAILURE到应用程序的DB_ENV->rep_process_message方法， 而不是执行内部初始化。

为了使用热备份去初始化一个到replication组的clinet，执行下面的步骤：

1. 做个一master环境的档案备份，就像在“数据库和日志文件档案”（Database and log file archival）中描述的那样。这个备份可以是常规的备份或一个热备份。

1. 拷贝这个档案备份到client的一个干净的环境目录中。在client的新环境里执行灾难恢复，就像在恢复程序中描述的那样。

1. 重新配置和重新打开这个环境作为组内的一个client成员。如果拷贝这个备份到client，相对于用db_archive公用程序或用 DB_ENV->log_archive方法再造日志文件的周期来说，发费较长的时间，它可能需要抑制日志再造（reclamation），直到这 个新启动的client已经追上（caught up）和应用了所有在停工期间产生的log记录。

就像任何bdb应用程序一样，当应用程序启动的时候数据库环境必须在一个一致的（consistent）状态。这是可以通过在一个线程或一个进程启动时执 行恢复来最简单的确定的。这是对clients和masters来说无害的，即使它们不是严格的必需的，也就是说即使他们实际上没什么需要恢复的。

Bulk transfer

组内的站点们可能通过用DB_REP_CONF_BULK标志调用DB_ENV->rep_set_config 方法，而把配置成使用批量传输的。当被配置成批量传输，站点们将在一个缓冲区内积聚记录，然后在一次单一的网络传输中把它们传送给另一个站点。配置批量传 输对master来说当然很有意义。另外，使用client-to-client同步的应用程序可能会发现，配置成批量传输对clients站点们来说也 是很有帮助的。

当一个master正在产生新的log记录时，或者，或请求任何master的信息时，如果批量传输被配置，记录将堆积在一个批量缓冲区中。当缓冲区被装 满了或一个永久的记录（例如，一个事务提交或一个检查点记录）被这个client排队等待，批量缓冲区将发送给client。

当一个client在响应另一个client的请求的信息的时候，如果批量传输被配置，记录将在批量缓冲区中堆积。批量缓冲区将发送给client，当缓冲区被装满了或当这个client的请求已经被满足了，再没有特别类型的记录将需要这缓冲区去发送了。批量缓冲区的大小，它自己已经内定了不能被配置。尽管如此，在一次传输数据的总的大小可以通过使用DB_ENV->set_rep_limit方法来限制。

Transactional guarantees

在总的数据库环境的事务保证的上下文中去考虑replication是和重要的。作为简要的回顾，在一个非复制（non-replicated ）中事务保证，是基于写log文件记录到稳定的存储设备上，通常是一个磁盘驱动器。如果应用程序回系统出了故障，bdb的日志信息将在恢复时被回顾，而且数据库被更新，以使已提交的事物的改变部分出现，所有未提交的而改变的部分不出现。在这种情况下，没有信息将会丢失。

如果一个数据库环境不要求当事务提交的时候把log写到稳定存储设备上（使用DB_TXN_NOSYNC标志能以牺牲事务的经久性为代价来增加性 能），bdb恢复将只能把这个存储系统恢复到最后一个提交了的被保存在磁盘上了的状态。在这种情况下，信息可能已经丢失（例如，一些已经由事物提交了的改 变可能在恢复之后不会出现在数据库中）。

更进一步。如果这儿有数据库或log文件丢失或腐烂（例如，如果一个磁盘驱动器出了故障），然后灾难恢复将是必要的，bdb恢复将只能把这个系统重新存储到最后一次归档log那儿。在这中情况下，信息仍然可能被丢失。

复制（Replicating）这个数据库环境通过添加一个新的组成到“稳定存储”上扩展了这个模式：这个clinet的replicated信息。如果 一个数据库环境是replicated，在数据库或log丢失的情况下，这儿也不会有信息丢失，因为这个复制系统可以被配置成包含数据库和log记录直到 故障点的全部的设置。一个数据库丢失了一个磁盘驱动器能使这个磁盘被复制，然后，它有能重新加入这个复制（replication）组。

由于这个新的稳定存储的组成部分，指定DB_TXN_NOSYNC到一个复制组将不再牺牲耐久性了，只要具备一个或多个clients有公认的 master所发送消息的收条。因为网络连接通常比本地同步磁盘写的快，replication成为大幅度提高它们的性能和可靠性的一个方法。

应用程序发送函数的返回状态必须被应用程序设置成确保应用程序想要提供的事务保障。无论什么时候，发送函数返回失败，本地数据库环境的log将被刷新 （flushed），以确保任危急到到数据库完整性的信息不被丢失。因为这个刷新是一个昂贵的开销，会影响数据库性能，如果可能的话，应用程序应该避免从 发送函数那返回一个错误信息。

replication事务保障唯一感兴趣的消息类型是当应用程序的发送函数指定了DB_REP_PERMANENT 标志被调用。如果发送函数曾经返回失败这儿将是没有原因的，除非
DB_REP_PERMANENT 标志被指定–消息没有DB_REP_PERMANENT被指定，不会使数据库有明显的改变，而且发送函数可以成功返回到bdb，只要这个消息被发送到client（s），或仅仅被拷贝到本地应用程序内存中预备发送。

当一个client收到一个DB_REP_PERMANENT 消息，这个client将在返回前刷新它的log到稳定存储设备上（除非这个client环境曾经用DB_TXN_NOSYNC 选项配置过）。
如果这个client不能刷新一个全部的事务记录到磁盘，不管什么原因（例如，在被标志的消息前丢失了一个log记录），在client上调用DB_ENV->rep_process_message方法将返回DB_REP_NOTPERM 和在ret_lsnp参数中返回这个记录的LSN到应用程序。

这个应用程序的client或master消息处理的循环应该适当的带些动作以确保在这种情况下的正确的事务保障。当丢失的记录到达，而且允许随后处理这些以前存储的永久记录，在clinet上调用DB_ENV->rep_process_message 方法将返回DB_REP_ISPERM和返回永曾经被刷新到磁盘中的久记录的最大的LSN。Client 应用次序可以用这些LSN决定性的知道是否某些特定的LSN被永久存储了。

一个应用程序依赖于client的能力去成为master，而且保证没有数据曾经被丢失，将需要编写发送函数返回一个错误，无论什么时候它都不能保证将赢得下一次选举的站点会有这个记录。

应用程序不要求这个级别的事务保证将不需要让这发送函数返回失败（除非master的数据库环境用DB_TXN_NOSYNC配置过），因为任何危急到数据库完整性的信息在发送被调用前已经被刷新到本地log文件。

总的来说，发送函数要返回失败的唯一的原因是当master的数据库环境被配置成当事务提交的时候不去刷新log（也就是说，在master上DB_TXN_NOSYNC被配置了）， DB_REP_PERMANENT 标志被指定给消息， 而且发送函数不能决定哪些clients收到了当前的消息（和所有在当前消息之前的消息）。多少clients在发送函数成功返回之前需要接收这个消息那是应用程序的选择（可能不是过多的依赖于特定数目的cleints报告成功作为一个或多个物理上分布式的 clients）。

如果，尽管如此，master上的应用程序确实需要在磁盘上的耐久性，那么这个应用程序应该被配置成当事务提交的时候同步的刷新记录。如果一个 client没被配置成同步刷新log，也就是说，一个client运行的时候DB_TXN_NOSYNC是被被配置的，当它变成master的时候，那 么它将取决于应用程序去适当地重新配置那个client。也就是说，这个应用程序必须明确的调用DB_ENV->set_flags去重新配置这个 新成为master的client，使异步log刷新无效。

当然，确保replicated master和client环境确实是互相独立的很重要。例如，如果master和clients在同一个能源供给上（on the same power supply），一个client承认收到一个消息对事情是没什么帮助的，因为能源供给的失败仍然潜在地会使信息丢失。

配置的你基于replication的应用程序，能事务和性能上找到最佳结合点，是很复杂的。简言之，这儿有一些应用程序可以设置的地方以调节：为 master环境指定DB_TXN_NOSYNC；为client环境指定DB_TXN_NOSYNC；不同的站点一起参加选举的那个优先权；应用程序发 送函数的行为。

首先，在一个replication client中当一个事物提交的时候，写和同步刷新log几乎没什么用处。如果这些系统共享一个资源或多个系统同时出故障也许写和同步刷新log还有点用。默认地，所有的bdb环境，不管是master还是client，当事务提交的时候或预先地，都同步地刷新log。

考虑两个有网络连接的的系统。一个作为master，一个作为只读的client。如果master倒掉了client取代之，在这次故障 后，master又重新加入到replication组。master 和client都被配置成当事务提交的时候不同步刷新日志（也就是说DB_TXN_NOSYNC 在两个系统上都被配置）。这个应用程序的发送函数从不返回失败到bdb库，只个简单的传递消息到这个client（或许基于一个广播机制），而且总是返回 成功。在client上，由client的DB_ENV->rep_process_message方法返回的DB_REP_NOTPERM也将被 忽略。这个系统配置有优秀的性能，但在某些失败的模式下有可能丢失数据。

如果这个master和client都一下子到掉了，就有可能丢失已经提交了的事务，也就是说，事务的耐久性没有被维持。有责任去提高系统的能源供给的独立性和把他们放在物理上隔离的地方。

如果这两个系统间的连接出了故障（或者仅仅是一些消息丢失了），并且随后这个master倒掉了，也有可能失去已提交的事务。又是因为事务的耐久性没有被维护。下面的一些方法中可以提高可靠性：

使用可靠的网络协议（例如，tcp而不是udp）：

增加clients和网络路径的数目，以使消息不太可能被丢失。在这种情况下，确保 client确实收到了这消息以赢得任何随后的选举也是很重要的。 如果一个client没有受到这个消息而赢得了随后的选举，那么数据仍然可能被丢失。

进一步的，系统可能想保证消息交付给了client(s)（例如，去阻止网络连接简单的丢弃消息）。一些系统可能想确保clients从来不返回已过期的 信息，也就是说，一旦事务提交后在master上返回成功，将没有client在响应只读请求时返回旧的信息。下面的改变可能会用来阐述这些观点：

编写应用程序的发送函数，使它们直到一个或多个client承认收到了这个消息时才返回到bdb。这个clients的数目的选择是由应用程序决定的：你 将很可能会想网络隔离（确保每个物理站点的client收到这个消息）和地理上多样性（确保一个client在每条线路“each coast ”上都收到这个消息）。

编写client的消息处理循环，使直到DB_ENV->rep_process_message返回成功的时候才承认收到这条信息。当 DB_ENV->rep_process_message 方法返回DB_REP_NOTPERM 时意味着这个消息不能被刷新到client的磁盘。如果这个client不向master承认收到这个消息直到随后调用的 DB_ENV->rep_process_message方法返回DB_REP_ISPERM而且这个返回的LSN至少和这个消息的LSN一样大， 然后这个master的发送函数将不会返回success到bdb库。这意味着，直到那些经由挑选的clients已经收到了这个消息而且认为完成 了，mastet上正在提交事务的这个线程将才被允许继续下去。

作为选择，client的消息处理循环可以向master承认收到了这个消息，但是用一个错误代码指明那个应用程序的发送函数不要返回到bdb库，直到一个随后的来自同一个client的确认成功。应用程序的发送回调函数被bdb调用包括一个记录的LSN被发送（如果对那个记录来说是适当的）。当DB_ENV->rep_process_message 返回指示一个永久的记录已经被写入，然后它也回返回这个被写入的永久记录的最大LSN 。

这儿最后的两关需要考虑。首先，当应用程序的发送函数被调用的后，事务是不可被中途中断的，因为这个 master可能已经把事物提交日志记录写入磁盘，所以中途中断将不再是一个可选择项。第二，一个相近的问题是，如果发送函数返回失败，尽管这个 master将试图去刷新本地log，这个刷新操作将可能失败（例如，当本地磁盘是满的）。此外，事务不能被中途中断，因为一个或多个clients可能 已经提交了这个事务即使发送函数返回失败。杰出的应用程序可能也忍受不了这些不太可能的失败方式。在那中情况下应用程序可能想：

1，配置这master总去同步本地提交的事务（关闭DB_TXN_NOSYNC 配置项）。这样将对性能有很大的影响，当然（使用replication的其中的一个原因是避免本地磁盘的写操作），在这种配置下，不管什么情况，写本地日志失败将使事务中途中断。

2，在任何情况下都不要从应用程序的发送函数中返回，除非挑选的那些client已经承认了收到那个消息。直到这个发送函数返回到这个bdb库，master上这个正在提交事务的线程都将等待，所以没有应用程序能表现出承认事务已经被提交了。

最后可供牵扯到这些类型的失败的应用程序选择的是使用分布式事务，保证完全的一致性实现全局的事务管理和垮过多bdb环境履行两阶段提交。更多的了解这个可以参见分“the Distributed Transactions”那一章。

参考：http://blog.sina.com.cn/dev

Introduction

bdb包括对构建基于复制（replication）的高可用性应用程序的支持。bdb replication组由一些独立配置的数据库环境组成。组里只有一个master数据库环境和一个或多个client环境。Master环境支持读和写，client环境支持只读。如果master环境倒掉 了，应用程序将可能提升一个client为新的master。数据库环境可能在单独的计算机上，在单独的硬件分区上（partitions）一个不统一的 内存访问系统上，或在一个单独的server的一个磁盘上。唯一的约束就是，replication组的所有的参与者必须在一个字节序 （endianness）相同的机器上（都是大数再前或都是小数在前的操作系统）。我们期望这个约束在以后的版本中会去掉。因为总是用bdb环境，任何数 量的并发进程或线程可能访问一个数据库环境。在master环境中，多个线程可能读写这个环境。在client环境中，多个线程可能要读这个环境。

应用程序可能被编写成在master和clients间提供不同程度的稳固性。系统能同步的运行以便复制品（replicas）能保证是最新的，对应于所 有已提交的事务。但是这样做可能回招致性能上的很大的下降。高性能解决方案有考虑全局的稳固性，允许clients的数据过时一个应用程序可控制的一段时 间。尽管bdb包括必要的构建高可用性数据库环境的底层基础，应用程序仍然必须提供一些鉴定的（critical）组成部分：

• 应用程序有责任提供通信下部构造。应用程序可能用任何适当的通信协议。例如RPC, TCP/IP, UDP, VI或底板（backplane）消息传递。

• 应用程序有责任命名。bdb涉及到一个replication组成员的时候是靠一个应用程序提供的id，应用程序必须映射那个id到一个特殊的数据库环境中或通信通道中。

• 应用程序有责任监视master和clients的状态，和识别任何不可用的（unavailable）数据库环境。应用程序必须提供所有的需要的安全策略。例如，应用程序可能选择去加密数据，用一个安全的套接层，或什么也不做。

• 最后，bdb replication实现还有一个附加的特性去增强可靠性。bdb中的replication实现成执行数据库更新用一个不同的编码路径而不是用标准的。这意味着，有bug的软件的操作可能会毁坏replication master，但不会把clients也毁坏。

Replication和相近的方法的描述：
DB_ENV->rep_elect         举行一个replication竞选
DB_ENV->rep_process_message   处理一个replication消息
DB_ENV->rep_stat           Replication统计
DB_ENV->rep_sync           Replication同步
Replication 配置：
DB_ENV->rep_set_config     配置replication系统
DB_ENV->rep_start         为replication配置一个环境
DB_ENV->set_rep_limit       限制在响应但个消息时的数据发送
DB_ENV->set_rep_transport   配置replication传输

Replication environment IDs

每个在replication组中的数据库环境必须有一个独一无二的标识符，为它自己和其它replication组中的成员都分配一个不同标识符。这些 标识符不必要是全局的，也就是说，每个数据库环境可以分配本地化的标识符给replication组的成员。就是在每数据库环境中都能区分出其他成员就行 了，当然全局统一给指定标识符也不为错，只是非必要的。

应用程序有责任去标志每个进来的传递给DB_ENV->rep_process_message的有适当标识符的replication消息。随后，bdb将用这些相同的标识符去标志发送函数发出去的消息。

负标识符被bdb保留使用，不应该被应用程序指定给那些环境。有两个保留的标识符准备给应用程序使用的是：
DB_EID_BROADCAST：指定一个消息应该被广播给所有replication组中的成员。
DB_EID_INVALID：是一个无效的环境id，可能被用于初始化一些环境id变量，那些变量随后被检查合法性。

Replication environment priorities

每个replication组中的数据库环境变量必须有一个优先权，它指定了在replication组中不同环境间的一个相对的顺序。这个顺序在币桓鰉 aster倒掉，在决定选举哪个环境作为新master的时候的一个重要因素。优先权必须是一个非负的整数，但不必要replication组中是独一无 二的。优先权为0意味着这个系统永远不能成为一个master，是被忽略的。数越大表示优先权越高，例如，如果一个replication组由3个数据库 环境组成，两个由OC3 连接，第三个由T1连接，那么第三个数据库环境就应该被指定一个低点的优先权。

决定哪个client将当选为master时，先看谁有最多的近期的log记录。log记录一样多时，将参考优先权。如果log和优先权一样多时候，将随机选择一个。

Building replicated applications

最简单的方法去构建一个replicatedbdb应用程序，是首先构建（和调试）这个应用程序的一个事务版本。然后，添加一个薄的replication层到这个应用程序。所有高可用性应用程序用下面的附加的四个bdb方法：
DB_ENV->rep_elect,
DB_ENV->rep_process_message,
DB_ENV->rep_start ,
DB_ENV->set_rep_transport,
还有可能用这个配置方法  DB_ENV->set_rep_limit。

• DB_ENV->set_rep_transport：配置replication系统的通信底层构造。

• DB_ENV->rep_start：配置，或重新配置一个已经存在的数据库环境成为一个master或client.

• DB_ENV->rep_process_message：处理从replication组中别的环境进来的一个消息。对clients来说，它负 责接受log记录和根据master过来的消息更新本地数据库。对master和clients来说，都有责任处理一些行政的功能（例如，处理消息丢失的 协议），和允许新的clients加入到活动的replication组。这个方法只应该在环境已经通过DB_ENV->rep_start被配置 成一个master或client后被调用。

• DB_ENV->rep_elect：使replication组选举一个新的master，它在clients与master失去联系的时候和应用程序想在剩余的站点中选择一个新master的时候被调用。

• DB_ENV->set_rep_limit：在响应一个单独的调用DB_ENV->rep_process_message时，将要发送的 数据量上强加一个上限。当一个客户执行恢复的时候，也就是说，当一个replica站点是同去同步master的时候，clients可能找master 要大量的log记录，那样它将使它们之间在未来一段时间内忙于循环发送大量数据，那么这时候可能就想在失去控制和接受其他正常消息前，用 DB_ENV->set_rep_limit限制master将发送的数据量。

为了把replication添加到应用程序，应用程序初始化必须改变，还有应用程序的通信底层构造必须编写。应用程序初始化改变相对简单，通信底层构造编码可能会很复杂。

由于实现的的原因，所有replicated的数据库必须放在环境指定的数据目录中。如果你的数据库放在默认的环境home目录中，他们必须就放在本目录 中，而不是子目录中。必须注意那些使用相对路径和在打开环境后更改工作目录的应用程序。在这中应用程序中，replication初始化代码将找不到数据 库。而那些改变工作目录的可能需要使用绝对路径。

在应用程序初始化期间，应用程序执行三个附加的任务：第一，当打开它的数据库环境的时候，它必须指定DB_INIT_REP标志。第二，它必须提供关于它的通信底层构造bdb信息。第三，它必须启动bdb replication系统。通常，一个replicated应用程序将做正常的bdb恢复和配置，非常像其他的事务应用程序。然而，一旦数据库环境被打开，它将调用DB_ENV->set_rep_transport方法去配置bdb的replication，and 然后将调用DB_ENV->rep_start方法去加入或创建replication组。

当在应用程序启动时调用DB_ENV->rep_start的时候，应用程序有两个选择：通过配置为组内指定一个master，或者，可选择，配置 所有组内成员为clients然后调用一个选举方法，在它们之间选择一个master。每种方法都只正确的，完全取决于你的应用程序。 DB_ENV->rep_start调用的结果，往往是发现了一个master，或者，声明本地环境作为master。如果在一段可以接受的时间内 还没找出一个作为master，应用程序应该调用DB_ENV->rep_elect搞一次选举。

考虑到多进程或多环境句柄修改在replicated环境中的数据库的情况。所有的修改必须在master环境中完成。第一个进程加入或创建master 环境必须调用DB_ENV->set_rep_transport方法和DB_ENV->rep_start方法，随后的一些 replication进程必须至少DB_ENV->set_rep_transport方法。这些进程有可能调用 DB_ENV->rep_start方法（只要他们使用相同的master或者client参数）。如果多个进程正在修改master环境，这儿必 须有一个统一标准的通信底层构造，以便到达clients的消息有一个单一的master ID。附加地，应用程序必须被构造成以便于所有进来的消息能被一个单一的DB_ENV句柄处理。

请注意，不是所有的运行在replicated环境中的进程都需要调用DB_ENV->set_rep_transport或DB_ENV->rep_start。在master环境中运行的只读进程在任何情况下都不必要配置成replication。那些运行在clients环境中的进程在定义时就是只读的，所以 也不必要配置成replication的（尽管，clients在一些情况下有变成master的可能，通常最简单的是，在进程启动的时候配置成 replication的，而不是当一个clinets变成master的那个时候试图去配置）。很显然，在每个client上至少一个控制线程必须被配 置成replication的，因为消息继续在master和client间被传递。

由于实现的原因，所有的进入的replication消息必须用同一个DB_ENV句柄处理。它不要求一个单一的控制线程处理所有的消息，只要求所有的控制线程用同一个句柄处理消息。

没有附加的要求去调用一个方法关闭一个由多方参加的replication组中数据库环境。应用程序应该像平时一样通过调用DB_ENV->close关闭环境。

Building the communications infrastructure

应用程序具备replication支持，典型的被写成一个或多个控制线程循环在一个或多个通信通道上，接受和发送消息。这些线程为本地数据库环境从远程 环境接受消息，和为远程环境从本地环境接受消息。远程环境消息通过DB_ENV->rep_process_message方法从远程环境被传递到 本地数据库环境。本地环境的消息通过指定给DB_ENV->set_rep_transport方法的回调函数，被发送出去。

那些进程通过调用DB_ENV->set_rep_transport方法建立通信通道。而不管它是运行在client还server环境上。这个 方法指定发送函数，一个bdb用来发送消息给组内的其它数据库环境的回调函数。这个函数携带一个环境id和两个不透明的数据对象。

发送函数有责任根据id传送两个数据对象里的信息到特定的数据库环境，而后，[那边的]接受应用程序调用DB_ENV->rep_process_message方法去处理这个消息。

传输机制的细节完全留给了应用程序；唯一的要求是，每个控制器（进程或线程）的数据缓冲区和大小，和发送站点上传送给发送函数的那些DBT数据结构，通过 调用加以适当的参数调用DB_ENV->rep_process_message被如实的拷贝和交付到接受站点。被广播的消息（无论是被广播媒体广 播还是当直接通过设置DB_ENV->set_rep_transport方法的参数DB_EID_BROADCAST），不应该被消息发送器处 理。在所有的情况下，应用程序的传输媒体或软件必须确保，当打算把一个消息发送给不同的数据库环境的时候从不调用 DB_ENV->rep_process_message，或者，从同一个环境发送的广播消息，在这个环境上 DB_ENV->rep_process_message 将被调用。DB_ENV->rep_process_message方法是免线程的（free-threaded），它可以安全地同时地交付任意数 量的消，这些消息可以是来自这个bdb环境中任意进程或线程的。

这儿有一些DB_ENV->rep_process_message方法返回的信息（返回值）：

DB_REP_DUPMASTER：意味着组内的另一个数据库环境也相信它（另一个环境）自己将成为一个master。这个应用程序应该完成所有活动的事 务，关闭所有打开的数据库句柄，用DB_ENV->rep_start方法重新配置它自己为一个client，然后通过调用 DB_ENV->rep_elect号召一次选举。

DB_REP_HOLDELECTION：意味着组内的另一个环境已经号召了一个选举。这一应用程序应该调用DB_ENV->rep_elect参与选举。

DB_REP_IGNORE：意味着着个消息不能被处理。它一般暗示这个消息跟现在的replication状态不相关，就像一个迟到的过期的老消息。

DB_REP_ISPERM：意味着一个持久的消息，也许是一个以前返回的消息要作为一个记录被写入的。ret_lsnp包含这个永久记录的写入最大LSN。

DB_REP_NEWMASTER：意味着一个新的master已经被选举出来了。这个调用也返回master对应的本地id。如果这个master id改变了，这个应用程序可能需要重新配置自己（例如，更新数据时，直接询问新的master而不是旧的）。如果新master就是本地环境自己，那么这 个应用程序必须调用DB_ENV->rep_start方法，重新配置自己作为一个replication组的master来支持bdb库。

DB_REP_NEWSITE：意味着收到了组内的一个未知成员的消息。应用程序应该重新配置它自己以便它能发送消息到那个站点。

DB_REP_NOTPERM：一个标志着DB_REP_PERMANENT的消息被成功处理，但是没有被写入磁盘。这通常是暗示一个或多个消息本应该在 这个消息之前到达，但没有到。这个操作将被写入磁盘当丢失的消息到达的时候。参数ret_lsnp将包含这条记录的LSN 。这个应用程序应该施行所有认为必要的措施来保持它的可恢复性特征。

DB_REP_STARTUPDONE：意味着client已经完成了他的启动同步活动，现在正在处理来自master的活的日志消息。活的日志消息是指：master正在发送的，将要发送出来的消息，因为反对重新发送那些将由client请求的日志消息。

Connecting to a new site

为了添加一个新站点到replication组，所有需要做的就是，这个client成员的加入。bdb将从master到client自动地执行一个内部初始化，然后，将为刚加入的成员执行恢复，以使它的数据能和master同步。

无论何时，当DB_ENV->rep_process_message返回DB_REP_NEWSITE的时候，连接新的站点到组内将会发生。这个 应用程序应该分配给这个新站点一个本地环境id号，将来所有的来自这个站点的传递给DB_ENV->rep_process_message消息都 应该包含那个环境id号。当然，在DB_ENV->rep_process_message返回之前应用程序就能知道一个新站点也是可能的（例如， 应用次序使用面向连接的协议很有可能立即探测到一个新站点，然而，应用程序使用广播协议就不可能了）。

无论怎样，只要在应用程序中支持动态添加数据库环境到replication组，环境添加到一个已经存在的组可能需要提供联系信息（例如，在一个应用程序 中使用TCP/IP套接字，一个域名或IP地址都将是一些需要提供的合理的值）。这些可以用DB_ENV->rep_start方法的cdata参 数来完成。cdata所引用的信息被预先包装在这个新环境发送的初始的联系信息中，和通过使用 DB_ENV->rep_process_message返回的rec 参数，被提供给组内已存在的成员。如果没有附加的信息被提供给bdb以转交给组内已存在的成员，那么在 DB_ENV->rep_process_message返回DB_REP_NEWSITE之后，传递给 DB_ENV->rep_process_message方法的rec参数的数据域将为NULL。

Elections

应用程序有责任发起选举。举行一次选举将没有任何风险，因为bdb选举步骤保证这儿没有一个以上的master数据库环境。无论何时，当Clients与master环境失去联系的时候，当他们看到DB_ENV->rep_process_message方法返回DB_REP_HOLDELECTION 的时候，或当不管由于什么原因，使他们不知道谁是master的时候，他们都应该发起一次选举 。应用程序不必要在一开始启动的时候就立即举行选举，因为任何已经存在的master将会在调用DB_ENV->rep_start后被发现。如果在一小段等待时间后后没发现master，那么应用程序就应该发起一次选举。

为了使一个client去赢得选举，组内选择必须没有master，而且这个client必须有最多的最近的 log记录，有相同数量记录的，优先权高者获胜。应用程序指定最小量的组内成员必须参与将要要公布胜出者的选举。我们推荐至少((N/2) + 1)个成员参加。如果少于或等于半数参加，将给予一个警告。

如果一个应用程序的策略是这样的：哪一个站点将赢得选举可以在数据库环境信息的条目里参数化的（也就是说，站点的数目，可用log记录，和相对优先权都是 那些参数），那么bdb就可以透明的处理所有的选举。尽管如此，这儿还存在这种情况，就是应用程序完全知道而且需要去干涉选举结果。例如，应用程序可能被 选定去处理master的挑选工作，明确的指明master和clients站点。应用程序在这些情况下，可能永远不需要发起一次选举。作为选择，应用程 序可能会选择使用DB_ENV->rep_elect的参数，去强制正确的选举结果。也就是说，如果一个应用有3个站点，A, B, 和 C,当C倒掉后A必须成为胜出者，应用程序可以通过在选举后指定适当的优先权保证选举的结果：

on A: priority 100, nsites 2
on B: priority 0, nsites 2

用DB_ENV->rep_start方法配置多于一个以上的master是很危险的，应用程序应该小心的不这样做。应用程序应该只配置他们自己作 为master，如果他们是仅有的可能成为master的站点，或者，如果他们赢得了选举。一个应用程序只能知道它赢得了选举，如果 DB_ENV->rep_elect方法返回成功信息，和本地环境的id号成为新的master环境id，或者，如果 DB_ENV->rep_process_message返回DB_REP_NEWMASTER和本地环境的id号成为新的master环境id。

为了添加一个数据库环境到组内，意图成为一个master，首先作为一个client添加它。因为它可能数据过时，还需要考虑现在的master，允许它 从现在的master那里更新自己的数据。然后，关闭现在的master。推测，这刚添加的client将要赢得随后的选举。如果这个client没有赢 得选举，很有可能是没有给它足够的时间从当前的master那去更新它自己的数据。

如果一个client不能找到一个master或赢得一场选举，那意味着，网络被隔离，这儿没有足够的环境一起参与这次选举使得其中一个参与者能够胜出。 在着种情况下，应用程序应该重复地调用B_ENV->rep_start和DB_ENV->rep_elect，交互地尝试去发现一个已存在 的master，和举行一次选举宣布一个新的master。在一个令人绝望的环境中，一个应用程序可能通过调用DB_ENV->rep_start 简单的宣布自己成为master，或通过减少所需的参与者数目去赢得一个选举，直到这个选举胜出。

下面这些解决方案都是不推荐使用的：在网络被隔离的情况下，下面任何一个选择都可能导致组内有两个master，环境中的数据库可能会不可挽救的产生分 歧，因为它们被那些masters以不同的方法修改了。在双系统replication组的情况下，应用程序可能想要求访问一个远程网络站点，或一些其它 外部的加赛（tie-breaker）以允许系统宣布自己为master。

如果好多系统同时倒掉，一个非首选的数据库环境赢得选举也是可能的。因为一个选举的胜出者很快就会被宣布，如果有足够多的环境参与这场选举的话 。在一个速度慢，但是连接良好的机器上的环境，可能会和一个速度快但是连接很糟糕的环境失去联系。在好多环境同时倒掉的情况下（例如，一批 replicated机器在同一个机房），应用程序一开始应该引导这些数据库环境作为clients上线（那样将允许它们立即去处理读请求），然后等足够 的时间后，等稍微慢些的机器都都追赶上之后就举行一场选举。如果，不管什么原因，一个非首选的数据库环境成为了master，在一个replicated 环境中更换master是可能的。例如，首选的master倒掉了，组内一个client成员成为了新master。为了使首选的master再恢复到它 master的地位，跟着下面的做就可以：

一，首选的master应该重新启动，重新作为一个client加入到组内。
二，一旦首选的master追赶上了组内的进度（数据同步的进度），当前的master应该完成所有当前的活动的事务，然后重新用DB_ENV->rep_start方法配置自己成为一个client上线。
三，然后，当前的master，或那个首选的master应该用DB_ENV->rep_elect方法发起一次选举。

  施聪
高级程序员、网络设计师
2005 年 4 月

   BerkeleyDB是历史悠久的嵌入式数据库系统，主要应用在UNIX/LINUX操作系统上，其设计思想是简单、小巧、可靠、高性能。本文是对DB开 发的一个入门级指南，重点讨论了DB的核心数据结构和数据访问算法，并通过实际的代码演示如何使用DB。最后有一个对DB的简单总结，并提出作者对工具选 择的一些感想。
前言
UNIX/LINUX平台下的数据库种类非常多，参考资料1中 列举了其中的大部分。通常，我们在设计UNIX/LINUX平台下的应用软件时，如果数据种类繁多,数据与数据之间关系比较复杂，就会选用一些大型的企业 级数据库系统，如DB2，ORACLE、SYBASE等，如果软件规模不大，就倾向选用如MYSQL、POSTGRESQL等中小型数据库。例如使用 PHP/PERL +MYSQL/POSTGRESQL设计网站基本上是一个很常规的做法。但是，当应用软件管理的数据类型较少（特别注意：这并不是说需要管理的数据量 小），数据管理本身不复杂，且对数据操作要求高效率，则由大名鼎鼎的Berkeley（美国加州大学伯克利分校）开发的 BerkeleyDB可能是一个很明智的选择。

DB综述
DB最初开发的目的是以新的HASH访问算法来代替旧的hsearch函数和大量的dbm实现（如AT&T的dbm，Berkeley的 ndbm，GNU项目的gdbm）,DB的第一个发行版在1991年出现，当时还包含了B+树数据访问算法。在1992年，BSDUNIX第4.4发行版 中包含了DB1.85版。基本上认为这是DB的第一个正式版。在1996年中期，Sleepycat软件公司成立，提供对DB的商业支持。在这以后，DB得到了广泛的应用，当前最新版本是4.3.27。

DB支持几乎所有的现代操作系统，如LINUX、UNIX、WINDOWS等，也提供了丰富的应用程序接口，支持C、C++、JAVA、PERL、TCL、PYTHON、PHP等。DB的应用十分广泛，在很多知名的软件中都能看到其身影。例如参考资料2中作者谈到利用DB在LINUX下实现内核级文件系统；参考资料3中通过实际测试数据说明DB提高了OPENLDAP的效率。LINUX下的软件包管理器RPM也使用DB管理软件包相关数据，可以使用命令file查看RPM数据目录/var/lib/rpm下的文件,则有形式如下的输出：

Dirnames: Berkeley DB (Btree, version 9, native byte-order)
Filemd5s: Berkeley DB (Hash, version 8, native byte-order)

值得注意的是DB是嵌入式数据库系统，而不是常见的关系/对象型数据库，对SQL语言不支持，也不提供数据库常见的高级功能，如存储过程，触发器等。
DB的设计思想
DB 的设计思想是简单、小巧、可靠、高性能。如果说一些主流数据库系统是大而全的话，那么DB就可称为小而精。DB提供了一系列应用程序接口（API），调用 本身很简单，应用程序和DB所提供的库在一起编译成为可执行程序。这种方式从两方面极大提高了DB的效率。第一：DB库和应用程序运行在同一个地址空间， 没有客户端程序和数据库服务器之间昂贵的网络通讯开销，也没有本地主机进程之间的通讯；第二：不需要对SQL代码解码，对数据的访问直截了当。

DB对需要管理的数据看法很简单，DB数据库包含若干条记录，每一个记录由关键字和数据（KEY/VALUE）构成。数据可以是简单的数据类型，也可以是 复杂的数据类型，例如C语言中结构。DB对数据类型不做任何解释,完全由程序员自行处理，典型的C语言指针的”自由”风格。如果把记录看成一个有n个字段 的表，那么第1个字段为表的主键，第2–n个字段对应了其它数据。DB应用程序通常使用多个DB数据库，从某种意义上看，也就是关系数据库中的多个表。 DB库非常紧凑，不超过500K，但可以管理大至256T的数据量。

DB的设计充分体现了UNIX的基于工具的哲学，即若干简单工具的组合可以实现强大的功能。DB的每一个基础功能模块都被设计为独立的,也即意味着其使用 领域并不局限于DB本身。例如加锁子系统可以用于非DB应用程序的通用操作，内存共享缓冲池子系统可以用于在内存中基于页面的文件缓冲。

DB核心数据结构
数据库句柄结构DB：包含了若干描述数据库属性的参数，如数据库访问方法类型、逻辑页面大小、数据库名称等；同时，DB结构中包含了大量的数据库处理函数指针，大多数形式为 （*dosomething）(DB *, arg1, arg2,…)。其中最重要的有open,close,put,get等函数。

数据库记录结构DBT：DB中的记录由关键字和数据构成，关键字和数据都用结构DBT表示。实际上完全可以把关键字看成特殊的数据。结构中最重要的两个字段是 void * data和u_int32_t size，分别对应数据本身和数据的长度。

数据库游标结构DBC：游标（cursor）是数据库应用中常见概念，其本质上就是一个关于特定记录的遍历器。注意到DB支持多重记录（duplicate records），即多条记录有相同关键字，在对多重记录的处理中，使用游标是最容易的方式。

数据库环境句柄结构DB_ENV：环境在DB中属于高级特性，本质上看，环境是多个数据库的包装器。当一个或多个数据库在环境中打开后，环境可以为这些数据库提供多种子系统服务，例如多线/进程处理支持、事务处理支持、高性能支持、日志恢复支持等。

DB中核心数据结构在使用前都要初始化，随后可以调用结构中的函数（指针）完成各种操作，最后必须关闭数据结构。从设计思想的层面上看，这种设计方法是利用面向过程语言实现面对对象编程的一个典范。

DB数据访问算法
在数据库领域中,数据访问算法对应了数据在硬盘上的存储格式和操作方法。在编写应用程序时，选择合适的算法可能会在运算速度上提高1个甚至多个数量级。大 多数数据库都选用B+树算法，DB也不例外，同时还支持HASH算法、Recno算法和Queue算法。接下来，我们将讨论这些算法的特点以及如何根据需 要存储数据的特点进行选择。

B+树算法：B+树是一个平衡树，关键字有序存储，并且其结构能随数据的插入和删除进行动态调整。为了代码的简单，DB没有实现对关键字的前缀码压缩。B+树支持对数据查询、插入、删除的常数级速度。关键字可以为任意的数据结构。

HASH算法：DB中实际使用的是扩展线性HASH算法（extended linear hashing），可以根据HASH表的增长进行适当的调整。关键字可以为任意的数据结构。

Recno算法： 要求每一个记录都有一个逻辑纪录号，逻辑纪录号由算法本身生成。实际上，这和关系型数据库中逻辑主键通常定义为int AUTO型是同一个概念。Recho建立在B+树算法之上，提供了一个存储有序数据的接口。记录的长度可以为定长或不定长。

Queue算法：和Recno方式接近, 只不过记录的长度为定长。数据以定长记录方式存储在队列中，插入操作把记录插入到队列的尾部，相比之下插入速度是最快的。

对算法的选择首先要看关键字的类型，如果为复杂类型，则只能选择B+树或HASH算法，如果关键字为逻辑记录号，则应该选择Recno或Queue算法。 当工作集关键字有序时，B+树算法比较合适；如果工作集比较大且基本上关键字为随机分布时，选择HASH算法。Queue算法只能存储定长的记录，在高的 并发处理情况下，Queue算法效率较高；如果是其它情况，则选择Recno算法，Recno算法把数据存储为平面文件格式。

DB常用函数使用范例

#include <db.h>

#include <stdio.h>

#include <stdlib.h>

#include <pthread.h>

/* DB的函数执行完成后，返回0代表成功，否则失败 */

void print_error(int ret)

{

 if(ret != 0)

                printf("ERROR: %s\n",db_strerror(ret));

}

/* 数据结构DBT在使用前，应首先初始化，否则编译可通过但运行时报参数错误  */

void init_DBT(DBT * key, DBT * data)

{

 memset(key, 0, sizeof(DBT));

        memset(data, 0, sizeof(DBT));

}

void main(void)

{

      DB *dbp;

 DBT key, data;

      u_int32_t flags;

  int ret;

        char *fruit = "apple";

      int number = 15;

    typedef struct customer

     {

           int  c_id;

          char name[10];

              char address[20];

           int  age;

   } CUSTOMER;

 CUSTOMER cust;

     int key_cust_c_id = 1;

  cust.c_id = 1;

      strncpy(cust.name, "javer", 9);

     strncpy(cust.address, "chengdu", 19);

       cust.age = 32;

  /* 首先创建数据库句柄 */

    ret = db_create(&dbp, NULL, 0);

 print_error(ret);

    /* 创建数据库标志 */

        flags = DB_CREATE;

  /* 创建一个名为single.db的数据库，使用B+树访问算法，本段代码演示对简单数据类型的处理 */

     ret = dbp->open(dbp, NULL, "single.db", NULL, DB_BTREE, flags, 0);

      print_error(ret);

       init_DBT(&key, &data);

    /* 分别对关键字和数据赋值和规定长度 */

      key.data = fruit;

   key.size = strlen(fruit) + 1;

       data.data = &number;

    data.size = sizeof(int);

        /* 把记录写入数据库中，不允许覆盖关键字相同的记录 */

        ret = dbp->put(dbp, NULL, &key, &data,DB_NOOVERWRITE);

  print_error(ret);

/* 手动把缓存中的数据刷新到硬盘文件中，实际上在关闭数据库时，数据会被自动刷新 */

dbp->sync()；

init_DBT(&key, &data);

      key.data = fruit;

   key.size = strlen(fruit) + 1;

    /* 从数据库中查询关键字为apple的记录 */

     ret = dbp->get(dbp, NULL, &key, &data, 0);

       print_error(ret);

       /* 特别要注意数据结构DBT的字段data为void *型，所以在对data赋值和取值时，要做必要的类型转换。 */

     printf("The number = %d\n", *(int*)(data.data));

    if(dbp != NULL)

             dbp->close(dbp, 0);

 ret = db_create(&dbp, NULL, 0);

 print_error(ret);

       flags = DB_CREATE;

  /* 创建一个名为complex.db的数据库，使用HASH访问算法，本段代码演示对复杂数据结构的处理 */

    ret = dbp->open(dbp, NULL, "complex.db", NULL, DB_HASH, flags, 0);

      print_error(ret);

       init_DBT(&key, &data);

  key.size = sizeof(int);

     key.data = &(cust.c_id);

    data.size = sizeof(CUSTOMER);

       data.data = &cust;

  ret = dbp->put(dbp, NULL, &key, &data,DB_NOOVERWRITE);

   print_error(ret);

    memset(&cust, 0, sizeof(CUSTOMER));

    key.size = sizeof(int);

     key.data = &key_cust_c_id;

  data.data = &cust;

      data.ulen = sizeof(CUSTOMER);

      data.flags = DB_DBT_USERMEM;

    dbp->get(dbp, NULL, &key, &data, 0);

     print_error(ret);

    printf("c_id = %d name = %s address = %s age = %d\n",

              cust.c_id, cust.name, cust.address, cust.age);

    if(dbp != NULL)

             dbp->close(dbp, 0);

}

DB游标使用范例
游标是依赖于数据库句柄的，应用程序代码框架如下：

     /* 定义一个游标变量 */

      DBC * cur;

  /* 首先打开数据库，再打开游标 */

    dbp->open(dbp, ……);

    dbp->cursor(dbp, NULL, &cur, 0);

    /* do something with cursor */

  /* 首先关闭，在关闭数据库 */

        cur->c_close(cur);

       dbp->close(dbp, 0);

      

在游标打开后，可以以多种方式遍历特定记录。

             Memset(&key, 0, sizeof(DBT));

   Memset(&data, 0, sizeof(DBT));

      /* 因为KEY和DATA为空，则游标遍历整个数据库记录 */

   While((ret = cur->c_get(cur, &key, &data, DB_NEXT)) == 0)

        {

           /* do something with key and data */

        }

   

当想查询特定关键字对应的记录，则应对关键字赋值，并把cur->c_get()函数中标志位设置为DB_SET。例如：

             key.data = "xxxxx";

 key.size =  XXX;

    While((ret = cur->c_get(cur, &key, &data, DB_SET)) == 0)

 {

           /* do something with key and data */

        }

   

游标的作用还有很多，如查询多重记录，插入/修改/删除记录等。

DB环境使用范例
本文前面已说明环境是DB数据库的包装器，提供多种高级功能。应用程序代码框架如下：

             /* 定义一个环境变量，并创建 */

      DB_ENV *dbenv;

      db_env_create(&dbenv, 0);

/* 在环境打开之前，可调用形式为dbenv->set_XXX()的若干函数设置环境 */

 /* 通知DB使用Rijndael加密算法（参考资料4）对数据进行处理 */

dbenv->set_encrypt(dbenv, "encrypt_string", DB_ENCRYPT_AES);

       /* 设置DB的缓存为5M */

dbenv->set_cachesize(dbenv, 0, 5 * 1024 * 1024, 0);

/* 设置DB查找数据库文件的目录 */

        dbenv->set_data_dir(dbenv, "/usr/javer/work_db");

    /* 打开数据库环境，注意后四个标志分别指示DB启动日志、加锁、缓存、事务处理子系统 */

  dbenv->open(dbenv,home,DB_CREATE|DB_INIT_LOG|DB_INIT_LOCK| DB_INIT_MPOOL|DB_INIT_TXN, 0)；

    /* 在环境打开后，则可以打开若干个数据库，所有数据库的处理都在环境的控制和保护中。注意db_create函数的第二个参数是环境变量 */

db_create(&dbp1, dbenv, 0)；

dbp1->open(dbp1, ……);

db_create(&dbp2, dbenv, 0)；

dbp1->open(dbp2, ……);

 /* do something with the database */

    /* 最后首先关闭打开的数据库，再关闭环境 */

  dbp2->close(dbp2, 0);

    dbp1->close(dbp1, 0);

    dbenv->close(dbenv, 0);

  

DB软件的安装和编译
从DB的官方站点http://www.sleepycat.com/下载最新的软件包db-4.3.27.tar.gz，解压到工作目录，进入该目录，依次执行下列三条命令即可。

../dist/configure

make

make install

执行make uninstall，则可卸载已安装的DB软件。

DB缺省把库和头文件安装在目录/usr/local/BerkeleyDB.4.3/下，使用gcc test.c -ggdb-I/usr/local/BerkeleyDB.4.3/include/ -L/usr/local/BerkeleyDB.4.3/lib/-ldb -lpthread就可正确编译程序。如果读者的测试主机操作系统为REDHAT9,则安装的DB版本可能是4.0。特别要注意到这两个版本的库是不兼容 的。例如打开数据库函数DB->open(),在4.0版本中入参为6个，而在4.3版中则为7个（可自行比较两个库的头文件db.h中 DB->open函数的定义）。因为在DB相关的应用程序中，open函数基本上都是要执行的，所以如果函数和版本不匹配，编译肯定会出错。当然， 编译完成后，可以使用命令ldd查看库的依赖关系。

总结
DB是一个具有工业强度的嵌入式数据库系统，数据处理的效率很高。DB功能的稳定性历经时间的考验，在大量应用程序中使用便是明证。可以想见，在同等代码 质量的条件下，软件的BUG数和代码的长度是成正比的，相对几十兆、几百兆大型数据库软件，DB的只有不到500K的大小！

从实现功能上看,DB是轻量级数据库系统，或可称为”极”轻量级数据库系统。但是，我认为不能因此而心存轻视之意，所谓”尺有所短，寸有所长”，以绝对角 度比较工具之间的好坏是没有什么意义的，关键在于对工具的选择和运用（似乎可以参考一下极限编程的思想）。也许，正确的”表达范式”应该是：在当前应用背 景下，选择这种工具是最合适的。

来源：http://www-128.ibm.com/developerworks/cn/linux/l-embdb/ 

译者： zhuyubing@gmail.com

这里告诉你怎么开始实验 SQLite ，这里没有长长的说明和配置。

下载代码
http://www.sqlite.org/download.html
目前的最新版本： http://www.sqlite.org/sqlite-3.4.0.tar.gz

取得一份二进制拷贝, 或者是源代码并自己编译它. 关于下载页（download） 的更多信息.

    ./configure      ;#  Run the configure script
make                     ;#  Run the makefile.
make install

创建一个新数据库

在命令行下, 输入: “sqlite3 test.db”. 将创建一个新的数据库文件名叫”test.db”. (你可以使用不同的名字)

输入 SQL 命令在提示符下创建和写入新的数据.

$ sqlite3 ex1
SQLite version 3.3.10
Enter “.help” for instructions
sqlite> create table tbl1(one varchar(10), two smallint);
sqlite> insert into tbl1 values(’hello!’,10);
sqlite> insert into tbl1 values(’goodbye’, 20);
sqlite> select * from tbl1;
hello!|10
goodbye|20
sqlite>.q

下面是一个C程序的例子，显示怎么使用 sqlite 的 C/C++ 接口. 数据库的名字由第一个参数取得且第二个参数或更多的参数是 SQL 执行语句. 这个函数调用sqlite3_open() 在 22 行打开数据库, sqlite3_exec() 在 27 行执行 SQL 命令, 并且sqlite3_close() 在 31 行关闭数据库连接.

代码:

#include <stdio.h>
#include <sqlite3.h>

static int callback(void *NotUsed, int argc, char **argv, char **azColName){
int i;
for(i=0; i<argc; i++){
printf(”%s = %s\n”, azColName[i], argv[i] ? argv[i] : “NULL”);
}
printf(”\n”);
return 0;
}

int main(int argc, char **argv){
sqlite3 *db;
char *zErrMsg = 0;
int rc;

if( argc!=3 ){
fprintf(stderr, “Usage: %s DATABASE SQL-STATEMENT\n”, argv[0]);
exit(1);
}
rc = sqlite3_open(argv[1], &db);
if( rc ){
fprintf(stderr, “Can’t open database: %s\n”, sqlite3_errmsg(db));
sqlite3_close(db);
exit(1);
}
rc = sqlite3_exec(db, argv[2], callback, 0, &zErrMsg);
if( rc!=SQLITE_OK ){
fprintf(stderr, “SQL error: %s\n”, zErrMsg);
}
sqlite3_close(db);
return 0;
}

将上面的文件保存为test.c
编译:

# gcc -o test test.c -lsqlite3

执行：

#./test ex1 “select * from tbl1″

 不使用回调查询数据库

上面介绍的 sqlite3_exec 是使用回调来执行 select 操作。还有一个方法可以直接查询而不需要回调。但是，我个人感觉还是回调好，因为代码可以更加整齐，只不过用回调很麻烦，你得声明一个函数，如果这个函数是类成员函数，你还不得不把它声明成 static 的（要问为什么？这又是C++基础了。C++成员函数实际上隐藏了一个参数：this，C++调用类的成员函数的时候，隐含把类指针当成函数的第一个参数传递进去。结果，这造成跟前面说的 sqlite 回调函数的参数不相符。只有当把成员函数声明成 static 时，它才没有多余的隐含的this参数）。

虽然回调显得代码整齐，但有时候你还是想要非回调的 select 查询。这可以通过 sqlite3_get_table 函数做到。

int sqlite3_get_table(sqlite3*, const char *sql, char ***resultp, int *nrow, int *ncolumn, char **errmsg );

第1个参数不再多说，看前面的例子。

第2个参数是 sql 语句，跟 sqlite3_exec 里的 sql 是一样的。是一个很普通的以结尾的char *字符串。

第3个参数是查询结果，它依然一维数组（不要以为是二维数组，更不要以为是三维数组）。它内存布局是：第一行是字段名称，后面是紧接着是每个字段的值。下面用例子来说事。

第4个参数是查询出多少条记录（即查出多少行）。

第5个参数是多少个字段（多少列）。

第6个参数是错误信息，跟前面一样，这里不多说了。

下面给个简单例子:

int main( int , char ** )
{
sqlite3 * db;
int result;
char * errmsg = NULL;
char **dbResult; //是 char ** 类型，两个*号
int nRow, nColumn;
int i , j;
int index;

result = sqlite3_open( “c:\\Dcg_database.db”, &db );
if( result != SQLITE_OK )
{
//数据库打开失败
return -1;
}

//数据库操作代码
//假设前面已经创建了 MyTable_1 表
//开始查询，传入的 dbResult 已经是 char **，这里又加了一个 & 取地址符，传递进去的就成了 char ***
result = sqlite3_get_table( db, “select * from MyTable_1”, &dbResult, &nRow, &nColumn, &errmsg );

if( SQLITE_OK == result )
{
//查询成功
index = nColumn; //前面说过 dbResult 前面第一行数据是字段名称，从 nColumn 索引开始才是真正的数据
printf( “查到%d条记录\n”, nRow );
for(  i = 0; i < nRow ; i++ )
{
printf( “第 %d 条记录\n”, i+1 );
for( j = 0 ; j < nColumn; j++ )
{
printf( “字段名:%s  ?> 字段值:%s\n”,  dbResult[j], dbResult [index] );
++index; // dbResult 的字段值是连续的，从第0索引到第 nColumn - 1索引都是字段名称，从第 nColumn 索引开始，后面都是字段值，它把一个二维的表（传统的行列表示法）用一个扁平的形式来表示
}
printf( “——-\n” );
}
}

//到这里，不论数据库查询是否成功，都释放 char** 查询结果，使用 sqlite 提供的功能来释放
sqlite3_free_table( dbResult );
//关闭数据库
sqlite3_close( db );
return 0;
}

例子二：

#include <stdio.h>
#include <sqlite3.h>
int main(int argc, char **argv){
sqlite3 *db;
char *zErrMsg = 0;
int rc;
char ** azResult;
int nrow,ncolumn;
int k;
if( argc!=3 ){
fprintf(stderr, “Usage: %s DATABASE SQL-STATEMENT\n”, argv[0]);
exit(1);
}
rc = sqlite3_open(argv[1], &db);
if( rc ){
fprintf(stderr, “Can’t open database: %s\n”, sqlite3_errmsg(db));
sqlite3_close(db);
exit(1);
}
//rc = sqlite3_exec(db, argv[2], callback, 0, &zErrMsg);
rc = sqlite3_get_table(db, argv[2], &azResult, &nrow, &ncolumn, &zErrMsg);

if( rc!=SQLITE_OK ){
fprintf(stderr, “SQL error: %s\n”, zErrMsg);
} else {
for ( k = 1; k <= nrow; k++ )
{
printf(azResult[k*ncolumn]);
printf(azResult[k*ncolumn+1]);
}
}
sqlite3_close(db);
return 0;
}

简介

C APIs包含在mysqlclient库文件当中与MySQL的源代码一块发行，用于连接到数据库和执行数据库查询。有一些例子在MySQL原代码的clients目录里。

MySQL C 变量类型

以下变量类型在MySQL的库当中定义。我们需要这些变量是为了使用MySQL的函数。这些变量有详细的解释，但是这些解释对于写代码来说并不重要。

MYSQL

要连接MYSQL，必须建立MYSQL实例，通过mysql_init初始化方能开始进行连接。

typedef struct st_mysql {
NET           net;            /* Communication parameters */
gptr          connector_fd;   /* ConnectorFd for SSL */
char          *host,*user,*passwd,*unix_socket,
*server_version,*host_info,*info,*db;
unsigned int  port,client_flag,server_capabilities;
unsigned int  protocol_version;
unsigned int  field_count;
unsigned int  server_status;
unsigned long thread_id;      /* Id for connection in server */
my_ulonglong affected_rows;
my_ulonglong insert_id;       /* id if insert on table with NEXTNR */
my_ulonglong extra_info;              /* Used by mysqlshow */
unsigned long packet_length;
enum mysql_status status;
MYSQL_FIELD   *fields;
MEM_ROOT      field_alloc;
my_bool       free_me;        /* If free in mysql_close */
my_bool       reconnect;      /* set to 1 if automatic reconnect */
struct st_mysql_options options;
char          scramble_buff[9];
struct charset_info_st *charset;
unsigned int  server_language;
} MYSQL;

MYSQL_RES

这个结构代表返回行的一个查询的(SELECT, SHOW, DESCRIBE, EXPLAIN)的结果。返回的数据称为“数据集”，在C的API里对应的就是MYSQL_RES，从数据库读取数据，最后就是从MYSQL_RES中读取数据。

typedef struct st_mysql_res {
my_ulonglong row_count;
unsigned int  field_count, current_field;
MYSQL_FIELD   *fields;
MYSQL_DATA    *data;
MYSQL_ROWS    *data_cursor;
MEM_ROOT      field_alloc;
MYSQL_ROW     row;            /* If unbuffered read */
MYSQL_ROW     current_row;    /* buffer to current row */
unsigned long *lengths;       /* column lengths of current row */
MYSQL         *handle;        /* for unbuffered reads */
my_bool       eof;            /* Used my mysql_fetch_row */
} MYSQL_RES;

MYSQL_ROW

这是一个行数据的类型安全(type-safe)的表示。当前它实现为一个计数字节的字符串数组。（如果字段值可能包含二进制数据，你不能将这些视为空终止串，因为这样的值可以在内部包含空字节) 行通过调用mysql_fetch_row()获得。

typedef char **MYSQL_ROW;

MYSQL_FIELD

这个结构包含字段信息，例如字段名、类型和大小。其成员在下面更详细地描述。你可以通过重复调用mysql_fetch_field()对每一列获得MYSQL_FIELD结构。字段值不是这个结构的部分；它们被包含在一个MYSQL_ROW结构中。

typedef struct st_mysql_field {
char *name;                   /* Name of column */
char *table;                  /* Table of column if column was a field */
char *def;                    /* Default value (set by mysql_list_fields) */
enum enum_field_types type;   /* Type of field. Se mysql_com.h for types */
unsigned int length;          /* Width of column */
unsigned int max_length;      /* Max width of selected set */
unsigned int flags;           /* Div flags */
unsigned int decimals;        /* Number of decimals in field */
} MYSQL_FIELD;

my_ulonglong
typedef unsigned long my_ulonglong;

该类型用于行编号和mysql_affected_rows()、mysql_num_rows()和mysql_insert_id()。这种类型提供 0到1.84e19的一个范围。在一些系统上，试图打印类型my_ulonglong的值将不工作。为了打印出这样的值，将它变换到unsigned long并且使用一个%lu打印格式。例如：

printf (”Number of rows: %lu\n”, (unsigned long) mysql_num_rows(result));

连接MySQL，查询数据

MySQL的库文件在mysqlclient，因此在编译MySQL程序的时候有必要加上-lmysqlclient编译选项。
MySQL 的头文件在/usr/include/mysql目录下(根据Linux的发行版本的不同，这个目录也有所不同)，因此你的程序头部看起来有点这个样子：

#include <mysql.h>

MySQL的变量类型和函数都包含在这个头文件当中

然后，我们需要创建连接数据库的变量，可以简单地这么做：

MYSQL mysql;

在连接数据库之前，先调用以下函数初始化这个变量：

mysql_init(&mysql);

然后，调用mysql_real_connect函数：

MYSQL *         STDCALL mysql_real_connect(MYSQL *mysql, const char *host,
const char *user,
const char *passwd,
const char *db,
unsigned int port,
const char *unix_socket,
unsigned int clientflag);

该函数被调用连接到数据库。host是MySQL服务器的主机名，user是登录的用户名，passwd是登录密码，db是要连接的数据库，port是 MySQL服务器的TCP/IP端口，unix_socket是连接类型，clientflag是MySQL运行成ODBC数据库的标记。连接寻建立后，这个函数返回0。

现在可以连接数据库，进行查询了：

char *query;

使用这个字符串我们可以创立任何SQL查询语句进行查询。执行这个查询的函数是：

int STDCALL mysql_real_query(MYSQL *mysql, const char *q, unsigned int length);

mysql是我们前面用过的变量，q是SQL查询语句，length是这个查询语句的长度。如果查询成功，函数返回0。

查询之后，我们要到一个MYSQL_RES变量来使用查询的结果。以下这行创立这个变量：

MYSQL_RES *res;

然后

 res = mysql_store_result(&mysql);

对客户端而言，有两种方法处理结果集合。一种方法是通过调用mysql_store_result()立刻检索全部结果。该函数从服务器获得查询返回的所有行，并将他们存储在客户端。第二种方法是对客户通过调用mysql_use_result()初始化一个一行一行地结果集合的检索。该函数初始化检索，但是实际上不从服务器获得任何行。

在两种情况中，你通过mysql_fetch_row()存取行。用mysql_store_result()、mysql_fetch_row()储存取已经从服务器被取出的行。用mysql_use_result()、mysql_fetch_row()实际上从服务器检索行。调用 mysql_fetch_lengths()可获得关于每行中数据值尺寸的信息。

在你用完一个结果集合以后，调用mysql_free_result()释放由它使用的内存。

两种检索机制是互补的。客户程序应该选择最适合他们的要求的途径。在实践中，客户通常更愿意使用mysql_store_result()。

该函数读出查询结果。

尽管可以很容易地查询了，要用这个查询的结果还要用到其它的函数。第一个是：

 MYSQL_ROW STDCALL mysql_fetch_row(MYSQL_RES *result);

该函数把结果转换成“数组”。你可能注意到了，该函数返回的是MYSQL_ROW变量类型。以下语句创立那样的变量：

 MYSQL_ROW row = mysql_fetch_row(res)

如前所解释的，变量row是一个字符串数组。也就是说，row[0]是数组的第一个值，row[1]是数组的第二个值…当我们用mysql_fetch_row的时候，接着变量row会取得结果的下一组的数据。当到了结果的尾部，该函数返回一负值。

使用数据集结束后，记得释放数据集，否则会发生内存泄漏，释放数据集函数如下：

void mysql_free_result(MYSQL_RES *result)

释放由mysql_store_result()、mysql_use_result()、mysql_list_dbs()等为一个结果集合分配的内存。当你用完了一个结果集合时，你必须调用mysql_free_result()来释放它使用的内存。

最后我们要关闭这个连接：

mysql_close(&mysql);

例子程序

执行一个select操作，从数据库中取数据，并执行一个insert操作，往数据库中插入数据，根据这两个操作你可以自由的扩展为任意数据库操作，
准备条件

1、已经安装mysql，上有数据库test，如果没有执行Create Databse test

建立数据库

2、test数据库上有表t1，如果没有，执行CREATE TABLE `t1` (
`id` int(11) default NULL,
`name` varchar(100) default NULL
)

建立表t1
testsql.c：

  #include <mysql.h>
#include <stdio.h>
int main(){
MYSQL mysql;     // need a instance to init
MYSQL_RES *res;
MYSQL_ROW row;
char *query;
int t,r;
// connect the database
mysql_init(&mysql);
if (!mysql_real_connect(&mysql,”localhost”, “mmim”, “mmim”, “test”,0,NULL,0))
{
printf( “Error connecting to database: %s\n”,mysql_error(&mysql));
}
else printf(”Connected…\n”);

// get the result from the executing select query
query = “select * from t1″;

t = mysql_real_query(&mysql,query,(unsigned int) strlen(query));
if (t)
{
printf(”Error making query: %s\n”,
mysql_error(&mysql));
}
else printf(”[%s] made…\n”, query);
res = mysql_store_result(&mysql);
while(row = mysql_fetch_row(res))
{
for(t=0;t<mysql_num_fields(res);t++)
{
printf(”%s “,row[t]);
}
printf(”\n”);
}

printf(”mysql_free_result…\n”);
mysql_free_result(res);     //free result after you get the result

sleep(1);

// execute the insert query
query = “insert into t1(id, name) values(3, ‘kunp’)”;
t = mysql_real_query(&mysql,query,(unsigned int) strlen(query));
if (t)
{
printf(”Error making query: %s\n”,
mysql_error(&mysql));
}
else printf(”[%s] made…\n”, query);

mysql_close(&mysql);

return 0;
}

编译

假定mysql的头文件在/usr/include/mysql，库文件在/usr/lib/mysql，执行下列命令进行编译：
gcc testsql.c -I/usr/include/mysql -L/usr/lib/mysql -lmysqlclient

引用：http://www.wikilib.com/wiki?title=DHT%E7%BD%91%E7%BB%9C

分布式散列表（英语：Distributed Hash Table，简称DHT）是分布式计算系统中的一类，用来将一个关键值（key）的集合分散到所有在分布式系统中的节点，并且可以有效地将讯息转送到唯一一个拥有查询者提供的关键值的节点（Peers）。这里的节点类似散列表中的储存位置。分布式散列表通常是为了拥有极大节点数量的系统，而且在系统的节点常常会加入或离开（例如网络断线）而设计的。在一个结构性的延展网络（overlay network）中，参加的节点需要与系统中一小部份的节点沟通，这也需要使用分布式散列表。分布式散列表可以用以建立更复杂的服务，例如分布式档案系统、点对点技术档案分享系统、合作的网页快取、多播、任播（anycast）、网域名称系统以及即时通讯等。
目录

* 1 发展背景
* 2 性质
* 3 结构
o 3.1 关键值空间分割
o 3.2 延展网络
* 4 范例
o 4.1 分布式散列表实作与协定
o 4.2 分布式散列表的应用
* 5 参见
* 6 参考资料
* 7 外部链接

 发展背景

研究分布式散列表的主要动机是为了开发点对点系统，像是Napster、Gnutella及Freenet。这些系统得益于使用分散在因特网上的各项资源以提供实用的应用，特别在带宽及硬盘储存空间上，他们所提供的档案分享功能因此得到最大的好处。

这些系统使用不同的方法来解决如何找到拥有某资料的节点的问题。Napster 使用中央的索引服务器：每个节点加入网络的同时，会将他们所拥有的档案列表传送给服务器，这使得服务器可以进行搜寻并将结果回传给进行查询的节点。但中央索引服务器让整个系统易受攻击，且可能造成法律问题。于是，Gnutella 和相似的网络改用大量查询模式（flooding query model）：每次搜寻都会把查询讯息广播给网络上的所有节点。虽然这个方式能够防止单点故障（single point of failure），但比起 Napster 来说却极没效率。

最后，Freenet 使用了完全分布式的系统，但它建置了一套使用经验法则的基于关键值的转送方法（key based routing）。在这个方法中，每个档案与一个关键值相结合，而拥有相似关键值的档案会倾向被相似的节点构成的集合所保管。于是查询讯息就可以根据它所提供的关键值被转送到该集合，而不需要经过所有的节点。然而，Freenet 并不保证存在网络上的资料在查询时一定会被找到。

分布式散列表为了达到 Gnutella 与 Freenet 的分散性（decentralization）以及 Napster 的效率与正确结果，使用了较为结构化的基于关键值的转送方法。不过分布式散列表也有个 Freenet 有的缺点，就是只能作精确搜寻，而不能只提供部份的关键字；但这个功能可以在分布式散列表的上层实做。

最初的四项分布式散列表技术——内容可寻址网络（Content addressable network，CAN）、Chord（Chord project）[1]、Pastry（Pastry (DHT)），以及 Tapestry (DHT)（Tapestry (DHT)）皆同时于2001年发表。从那时开始，相关的研究便一直十分活跃。在学术领域以外，分布式散列表技术已经被应用在BitTorrent及CoralCDN（Coral Content Distribution Network）等。

 性质

分布式散列表本质上强调以下特性：

* 分散性：构成系统的节点并没有任何中央式的协调机制。
* 规模性：即使有成千上万个节点，系统仍然应该十分有效率。
* 容错：即使节点不断地加入、离开或是停止工作，系统仍然必须达到一定的可靠度。

要达到以上的目标，有一个关键的技术：任一个节点只需要与系统中的部份节点沟通。一般来说，若系统有n 个节点，那麽只有 Θ(logn) 个节点是必须的（见后述）。因此，当成员改变的时候，只有一部分的工作（例如资料或关键值的传送，散列表的改变等）必须要完成。

有些分布式散列表的设计寻求能对抗网络中恶意的节点的安全性，但仍然保留参加节点的匿名性。在其他的点对点系统（特别是档案分享）中较为少见。参见匿名点对点技术。

最后，分布式散列表必须处理传统分布式系统可能遇到的问题，例如负载平衡、资料完整性，以及效能问题（特别是确认转送讯息、资料储存及读取等动作能快速完成）。

 结构

分布式散列表的结构可以分成几个主要的元件[2][3]。其基础是一个抽象的关键值空间（keyspace），例如说所有160位元长的字符串集合。关键值空间分割（keyspace partitioning）将关键值空间分割成数个，并指定到在此系统的节点中。而延展网络则连接这些节点，并让他们能够借由在关键值空间内的任一值找到拥有该值的节点。

当这些元件都准备好后，一般使用分布式散列表来储存与读取的方式如下所述。假设关键值空间是一个160位元长的字符串集合。为了在分布式散列表中储存一个档案，名称为 filename 且内容为 data，我们计算出 filename 的 SHA1 散列值——一个160位元的关键值 k——并将讯息 put(k,data) 送给分布式散列表中的任意参与节点。此讯息在延展网络中被转送，直到抵达在关键值空间分割中被指定负责储存关键值 k 的节点。而 (k,data) 即储存在该节点。其他的节点只需要重新计算 filename 的散列值 k，然后送出讯息 get(k) 给分布式散列表中的任意参与节点，以此来找与 k 相关的资料。此讯息也会在延展网络中被转送到负责储存 k 的节点。而此节点则会负责传回储存的资料 data。

以下分别描述关键值空间分割及延展网络的基本概念。这些概念在大多数的分布式散列表实作中是相同的，但设计的细节部份则大多不同。

 关键值空间分割

大多数的分布式散列表使用某些稳定散列（consistent hashing）方法来将关键值对应到节点。此方法使用了一个函数 δ(k1,k2) 来定义一个抽象的概念：从关键值k1 到 k2 的距离。每个节点被指定了一个关键值，称为ID。ID 为 i 的节点拥有根据函数 δ 计算，最接近 i 的所有关键值。

例：Chord 分布式散列表实作将关键值视为一个圆上的点，而 δ(k1,k2) 则是沿著圆顺时钟地从 k1 走到 k2 的距离。结果，圆形的关键值空间就被切成连续的圆弧段，而每段的端点都是节点的ID。如果 i1 与 i2 是邻近的 ID，则 ID 为 i2 的节点拥有落在 i1 及 i2 之间的所有关键值。

稳定散列拥有一个基本的性质：增加或移除节点只改变邻近ID的节点所拥有的关键值集合，而其他节点的则不会被改变。对比于传统的散列表，若增加或移除一个位置，则整个关键值空间就必须重新对应。由于拥有资料的改变通常会导致资料从分布式散列表中的一个节点被搬到另一个节点，而这是非常浪费带宽的，因此若要有效率地支援大量密集的节点增加或离开的动作，这种重新配置的行为必须尽量减少。

 延展网络

每个节点保有一些到其他节点（它的邻居）的连结。将这些连结总合起来就形成延展网络。而这些连结是使用一个结构性的方式来挑选的，称为网络拓撲。

所有的分布式散列表实作拓撲有某些基本的性质：对于任一关键值 k，某个节点要不就拥有 k，要不就拥有一个连结能连结到距离较接近 k 的节点。因此使用以下的贪心算法即可容易地将讯息转送到拥有关键值 k 的节点：在每次执行时，将讯息转送到 ID 较接近 k 的邻近节点。若没有这样的节点，那我们一定抵达了最接近 k 的节点，也就是拥有 k 的节点。这样的转送方法有时被称为“基于关键值的转送方法”。

除了基本的转送正确性之外，拓撲中另有两个关键的限制：其一为保证任何的转送路径长度必须尽量短，因而请求能快速地被完成；其二为任一节点的邻近节点数目（又称最大节点度（Degree (graph theory)））必须尽量少，因此维护的花费不会过多。当然，转送长度越短，则最大节点度越大。以下列出常见的最大节点度及转送长度（n 为分布式散列表中的节点数）

* 最大节点度 O(1)，转送长度 O(logn)
* 最大节点度 O(logn)，转送长度 O(logn / loglogn)
* 最大节点度 O(logn)，转送长度 O(logn)
* 最大节点度 O(n1 / 2)，转送长度 O(1)

第三个选择最为常见。虽然他在最大节点度与转送长度的取舍中并不是最佳的选择，但这样的拓撲允许较为有弹性地选择邻近节点。许多分布式散列表实作利用这种弹性来选择延迟较低的邻近节点。

最大的转送长度与直径有关：最远的两节点之间的最短距离。无疑地，网络的最大转送长度至少要与它的直径一样长，因而拓撲也被最大节点度与直径的取舍限制住[4]，而这在图论中是基本的性质。因为贪婪算法(Greed Method)可能找不到最短路径，因此转送长度可能比直径长[5]。

 范例

分布式散列表实作与协定

* Bamboo[6]
* Bunshin[7]
* 内容可寻址网络 (Content Addressable Network)
* Chord
* DKS系统[8]
* Kademlia
* Leopard
* MACE[9]
* Pastry
* P-Grid
* Tapestry

分布式散列表的应用

* BitTorrent：档案分享应用。BitTorrent 可以选用DHT作为分布式Tracker。
* Warez P2P：档案分享应用。
* The Circle：档案分享应用与聊天。
* CSpace：安全的沟通系统。
* Codeen：网页快取。
* CoralCDN
* Dijjer
* eMule：档案分享应用。
* I2P：匿名网络。
* JXTA：开放原始码的点对点平台。
* NEOnet：档案分享应用。
* Overnet：档案分享应用。

参见

* memcached：一个高效能、分布式的物件快取系统。

参考资料

1.  （英文） Hari Balakrishnan, M. Frans Kaashoek, David Karger, Robert Morris 与 Ion Stoica, Looking up data in P2P systems. 于 Communications of the ACM, 2003年1月
2. （英文） Moni Naor 与 Udi Wieder. Novel Architectures for P2P Applications: the Continuous-Discrete Approach. Proc. SPAA, 2003年
3. （英文） Gurmeet Singh Manku. Dipsea: A Modular Distributed Hash Table. 博士论文 （史丹佛大学），2004年8月
4. （英文） http://maite71.upc.es/grup_de_grafs/table_g.html
5. （英文） Gurmeet Singh Manku, Moni Naor, and Udi Wieder. Know thy Neighbor’s Neighbor: the Power of Lookahead in Randomized P2P Networks. Proc. STOC, 2004.
6.  http://www.bamboo-dht.org/
7.  http://planet.urv.es/bunshin/
8.  http://dks.sics.se
9.  http://mace.ucsd.edu

外部链接

• （英文） Distributed Hash Tables, Part 1 由 Brandon Wiley 所著。
• （英文） Distributed Hash Tables links Carles Pairot 的 DHT 与 P2P 研究网页。
• （英文） Sloppy Hashing and Self-Organizing Clusters由CoralCDN专案提供的著作。
• （英文） Tangosol Coherence 介绍一个类似 DHT 的架构，但所有节点都知道网络中其他参与者的资讯。

-------------------------------------------------------------------------
SED单行脚本快速参考（Unix 流编辑器）                       2005年12月29日

英文标题：USEFUL ONE-LINE SCRIPTS FOR SED (Unix stream editor)
原标题：HANDY ONE-LINERS FOR SED (Unix stream editor)

整理：Eric Pement  - 电邮：pemente[at]northpark[dot]edu         版本5.5
译者：Joe Hong     - 电邮：hq00e[at]126[dot]com

在以下地址可找到本文档的最新（英文）版本：
   http://sed.sourceforge.net/sed1line.txt
   http://www.pement.org/sed/sed1line.txt

其他语言版本：
  中文          - http://sed.sourceforge.net/sed1line_zh-CN.html
  捷克语        - http://sed.sourceforge.net/sed1line_cz.html
  荷语          - http://sed.sourceforge.net/sed1line_nl.html
  法语          - http://sed.sourceforge.net/sed1line_fr.html
  德语          - http://sed.sourceforge.net/sed1line_de.html
<!--   意大利语      - http://sed.sourceforge.net/sed1line_it.html -->
  葡语          - http://sed.sourceforge.net/sed1line_pt-BR.html
<!--   西班牙语      - http://sed.sourceforge.net/sed1line_es.html -->

文本间隔：
--------

 # 在每一行后面增加一空行
 sed G

 # 将原来的所有空行删除并在每一行后面增加一空行。
 # 这样在输出的文本中每一行后面将有且只有一空行。
 sed '/^$/d;G'

 # 在每一行后面增加两行空行
 sed 'G;G'

 # 将第一个脚本所产生的所有空行删除（即删除所有偶数行）
 sed 'n;d'

 # 在匹配式样“regex”的行之前插入一空行
 sed '/regex/{x;p;x;}'

 # 在匹配式样“regex”的行之后插入一空行
 sed '/regex/G'

 # 在匹配式样“regex”的行之前和之后各插入一空行
 sed '/regex/{x;p;x;G;}'

编号：
--------

 # 为文件中的每一行进行编号（简单的左对齐方式）。这里使用了“制表符”
 # （tab，见本文末尾关于'\t'的用法的描述）而不是空格来对齐边缘。
 sed = filename | sed 'N;s/\n/\t/'

 # 对文件中的所有行编号（行号在左，文字右端对齐）。
 sed = filename | sed 'N; s/^/     /; s/ *\(.\{6,\}\)\n/\1  /'

 # 对文件中的所有行编号，但只显示非空白行的行号。
 sed '/./=' filename | sed '/./N; s/\n/ /'

 # 计算行数 （模拟 "wc -l"）
 sed -n '$='

文本转换和替代：
--------

 # Unix环境：转换DOS的新行符（CR/LF）为Unix格式。
 sed 's/.$//'                     # 假设所有行以CR/LF结束
 sed 's/^M$//'                    # 在bash/tcsh中，将按Ctrl-M改为按Ctrl-V
 sed 's/\x0D$//'                  # ssed、gsed 3.02.80，及更高版本

 # Unix环境：转换Unix的新行符（LF）为DOS格式。
 sed "s/$/`echo -e \\\r`/"        # 在ksh下所使用的命令
 sed 's/$'"/`echo \\\r`/"         # 在bash下所使用的命令
 sed "s/$/`echo \\\r`/"           # 在zsh下所使用的命令
 sed 's/$/\r/'                    # gsed 3.02.80 及更高版本

 # DOS环境：转换Unix新行符（LF）为DOS格式。
 sed "s/$//"                      # 方法 1
 sed -n p                         # 方法 2

 # DOS环境：转换DOS新行符（CR/LF）为Unix格式。
 # 下面的脚本只对UnxUtils sed 4.0.7 及更高版本有效。要识别UnxUtils版本的
 #  sed可以通过其特有的“--text”选项。你可以使用帮助选项（“--help”）看
 # 其中有无一个“--text”项以此来判断所使用的是否是UnxUtils版本。其它DOS
 # 版本的的sed则无法进行这一转换。但可以用“tr”来实现这一转换。
 sed "s/\r//" infile >outfile     # UnxUtils sed v4.0.7 或更高版本
 tr -d \r <infile >outfile        # GNU tr 1.22 或更高版本

 # 将每一行前导的“空白字符”（空格，制表符）删除
 # 使之左对齐
 sed 's/^[ \t]*//'                # 见本文末尾关于'\t'用法的描述

 # 将每一行拖尾的“空白字符”（空格，制表符）删除
 sed 's/[ \t]*$//'                # 见本文末尾关于'\t'用法的描述

 # 将每一行中的前导和拖尾的空白字符删除
 sed 's/^[ \t]*//;s/[ \t]*$//'

 # 在每一行开头处插入5个空格（使全文向右移动5个字符的位置）
 sed 's/^/     /'

 # 以79个字符为宽度，将所有文本右对齐
 sed -e :a -e 's/^.\{1,78\}$/ &/;ta'  # 78个字符外加最后的一个空格

 # 以79个字符为宽度，使所有文本居中。在方法1中，为了让文本居中每一行的前
 # 头和后头都填充了空格。 在方法2中，在居中文本的过程中只在文本的前面填充
 # 空格，并且最终这些空格将有一半会被删除。此外每一行的后头并未填充空格。
 sed  -e :a -e 's/^.\{1,77\}$/ & /;ta'                     # 方法1
 sed  -e :a -e 's/^.\{1,77\}$/ &/;ta' -e 's/\( *\)\1/\1/'  # 方法2

 # 在每一行中查找字串“foo”，并将找到的“foo”替换为“bar”
 sed 's/foo/bar/'                 # 只替换每一行中的第一个“foo”字串
 sed 's/foo/bar/4'                # 只替换每一行中的第四个“foo”字串
 sed 's/foo/bar/g'                # 将每一行中的所有“foo”都换成“bar”
 sed 's/\(.*\)foo\(.*foo\)/\1bar\2/' # 替换倒数第二个“foo”
 sed 's/\(.*\)foo/\1bar/'            # 替换最后一个“foo”

 # 只在行中出现字串“baz”的情况下将“foo”替换成“bar”
 sed '/baz/s/foo/bar/g'

 # 将“foo”替换成“bar”，并且只在行中未出现字串“baz”的情况下替换
 sed '/baz/!s/foo/bar/g'

 # 不管是“scarlet”“ruby”还是“puce”，一律换成“red”
 sed 's/scarlet/red/g;s/ruby/red/g;s/puce/red/g'  #对多数的sed都有效
 gsed 's/scarlet\|ruby\|puce/red/g'               # 只对GNU sed有效

 # 倒置所有行，第一行成为最后一行，依次类推（模拟“tac”）。
 # 由于某些原因，使用下面命令时HHsed v1.5会将文件中的空行删除
 sed '1!G;h;$!d'               # 方法1
 sed -n '1!G;h;$p'             # 方法2

 # 将行中的字符逆序排列，第一个字成为最后一字，……（模拟“rev”）
 sed '/\n/!G;s/\(.\)\(.*\n\)/&\2\1/;//D;s/.//'

 # 将每两行连接成一行（类似“paste”）
 sed '$!N;s/\n/ /'

 # 如果当前行以反斜杠“\”结束，则将下一行并到当前行末尾
 # 并去掉原来行尾的反斜杠
 sed -e :a -e '/\\$/N; s/\\\n//; ta'

 # 如果当前行以等号开头，将当前行并到上一行末尾
 # 并以单个空格代替原来行头的“=”
 sed -e :a -e '$!N;s/\n=/ /;ta' -e 'P;D'

 # 为数字字串增加逗号分隔符号，将“1234567”改为“1,234,567”
 gsed ':a;s/\B[0-9]\{3\}\>/,&/;ta'                     # GNU sed
 sed -e :a -e 's/\(.*[0-9]\)\([0-9]\{3\}\)/\1,\2/;ta'  # 其他sed

 # 为带有小数点和负号的数值增加逗号分隔符（GNU sed）
 gsed -r ':a;s/(^|[^0-9.])([0-9]+)([0-9]{3})/\1\2,\3/g;ta'

 # 在每5行后增加一空白行 （在第5，10，15，20，等行后增加一空白行）
 gsed '0~5G'                      # 只对GNU sed有效
 sed 'n;n;n;n;G;'                 # 其他sed

选择性地显示特定行：
--------

 # 显示文件中的前10行 （模拟“head”的行为）
 sed 10q

 # 显示文件中的第一行 （模拟“head -1”命令）
 sed q

 # 显示文件中的最后10行 （模拟“tail”）
 sed -e :a -e '$q;N;11,$D;ba'

 # 显示文件中的最后2行（模拟“tail -2”命令）
 sed '$!N;$!D'

 # 显示文件中的最后一行（模拟“tail -1”）
 sed '$!d'                        # 方法1
 sed -n '$p'                      # 方法2

 # 显示文件中的倒数第二行
 sed -e '$!{h;d;}' -e x              # 当文件中只有一行时，输入空行
 sed -e '1{$q;}' -e '$!{h;d;}' -e x  # 当文件中只有一行时，显示该行
 sed -e '1{$d;}' -e '$!{h;d;}' -e x  # 当文件中只有一行时，不输出

 # 只显示匹配正则表达式的行（模拟“grep”）
 sed -n '/regexp/p'               # 方法1
 sed '/regexp/!d'                 # 方法2

 # 只显示“不”匹配正则表达式的行（模拟“grep -v”）
 sed -n '/regexp/!p'              # 方法1，与前面的命令相对应
 sed '/regexp/d'                  # 方法2，类似的语法

 # 查找“regexp”并将匹配行的上一行显示出来，但并不显示匹配行
 sed -n '/regexp/{g;1!p;};h'

 # 查找“regexp”并将匹配行的下一行显示出来，但并不显示匹配行
 sed -n '/regexp/{n;p;}'

 # 显示包含“regexp”的行及其前后行，并在第一行之前加上“regexp”所
 # 在行的行号 （类似“grep -A1 -B1”）
 sed -n -e '/regexp/{=;x;1!p;g;$!N;p;D;}' -e h

 # 显示包含“AAA”、“BBB”或“CCC”的行（任意次序）
 sed '/AAA/!d; /BBB/!d; /CCC/!d'  # 字串的次序不影响结果

 # 显示包含“AAA”、“BBB”和“CCC”的行（固定次序）
 sed '/AAA.*BBB.*CCC/!d'

 # 显示包含“AAA”“BBB”或“CCC”的行 （模拟“egrep”）
 sed -e '/AAA/b' -e '/BBB/b' -e '/CCC/b' -e d    # 多数sed
 gsed '/AAA\|BBB\|CCC/!d'                        # 对GNU sed有效

 # 显示包含“AAA”的段落 （段落间以空行分隔）
 # HHsed v1.5 必须在“x;”后加入“G;”，接下来的3个脚本都是这样
 sed -e '/./{H;$!d;}' -e 'x;/AAA/!d;'

 # 显示包含“AAA”“BBB”和“CCC”三个字串的段落 （任意次序）
 sed -e '/./{H;$!d;}' -e 'x;/AAA/!d;/BBB/!d;/CCC/!d'

 # 显示包含“AAA”、“BBB”、“CCC”三者中任一字串的段落 （任意次序）
 sed -e '/./{H;$!d;}' -e 'x;/AAA/b' -e '/BBB/b' -e '/CCC/b' -e d
 gsed '/./{H;$!d;};x;/AAA\|BBB\|CCC/b;d'         # 只对GNU sed有效

 # 显示包含65个或以上字符的行
 sed -n '/^.\{65\}/p'

 # 显示包含65个以下字符的行
 sed -n '/^.\{65\}/!p'            # 方法1，与上面的脚本相对应
 sed '/^.\{65\}/d'                # 方法2，更简便一点的方法

 # 显示部分文本——从包含正则表达式的行开始到最后一行结束
 sed -n '/regexp/,$p'

 # 显示部分文本——指定行号范围（从第8至第12行，含8和12行）
 sed -n '8,12p'                   # 方法1
 sed '8,12!d'                     # 方法2

 # 显示第52行
 sed -n '52p'                     # 方法1
 sed '52!d'                       # 方法2
 sed '52q;d'                      # 方法3, 处理大文件时更有效率

 # 从第3行开始，每7行显示一次
 gsed -n '3~7p'                   # 只对GNU sed有效
 sed -n '3,${p;n;n;n;n;n;n;}'     # 其他sed

 # 显示两个正则表达式之间的文本（包含）
 sed -n '/Iowa/,/Montana/p'       # 区分大小写方式

选择性地删除特定行：
--------

 # 显示通篇文档，除了两个正则表达式之间的内容
 sed '/Iowa/,/Montana/d'

 # 删除文件中相邻的重复行（模拟“uniq”）
 # 只保留重复行中的第一行，其他行删除
 sed '$!N; /^\(.*\)\n\1$/!P; D'

 # 删除文件中的重复行，不管有无相邻。注意hold space所能支持的缓存
 # 大小，或者使用GNU sed。
 sed -n 'G; s/\n/&&/; /^\([ -~]*\n\).*\n\1/d; s/\n//; h; P'

 # 删除除重复行外的所有行（模拟“uniq -d”）
 sed '$!N; s/^\(.*\)\n\1$/\1/; t; D'

 # 删除文件中开头的10行
 sed '1,10d'

 # 删除文件中的最后一行
 sed '$d'

 # 删除文件中的最后两行
 sed 'N;$!P;$!D;$d'

 # 删除文件中的最后10行
 sed -e :a -e '$d;N;2,10ba' -e 'P;D'   # 方法1
 sed -n -e :a -e '1,10!{P;N;D;};N;ba'  # 方法2

 # 删除8的倍数行
 gsed '0~8d'                           # 只对GNU sed有效
 sed 'n;n;n;n;n;n;n;d;'                # 其他sed

 # 删除匹配式样的行
 sed '/pattern/d'                      # 删除含pattern的行。当然pattern
                                       # 可以换成任何有效的正则表达式

 # 删除文件中的所有空行（与“grep '.' ”效果相同）
 sed '/^$/d'                           # 方法1
 sed '/./!d'                           # 方法2

 # 只保留多个相邻空行的第一行。并且删除文件顶部和尾部的空行。
 # （模拟“cat -s”）
 sed '/./,/^$/!d'        #方法1，删除文件顶部的空行，允许尾部保留一空行
 sed '/^$/N;/\n$/D'      #方法2，允许顶部保留一空行，尾部不留空行

 # 只保留多个相邻空行的前两行。
 sed '/^$/N;/\n$/N;//D'

 # 删除文件顶部的所有空行
 sed '/./,$!d'

 # 删除文件尾部的所有空行
 sed -e :a -e '/^\n*$/{$d;N;ba' -e '}'  # 对所有sed有效
 sed -e :a -e '/^\n*$/N;/\n$/ba'        # 同上，但只对 gsed 3.02.*有效

 # 删除每个段落的最后一行
 sed -n '/^$/{p;h;};/./{x;/./p;}'

特殊应用：
--------

 # 移除手册页（man page）中的nroff标记。在Unix System V或bash shell下使
 # 用'echo'命令时可能需要加上 -e 选项。
 sed "s/.`echo \\\b`//g"    # 外层的双括号是必须的（Unix环境）
 sed 's/.^H//g'             # 在bash或tcsh中, 按 Ctrl-V 再按 Ctrl-H
 sed 's/.\x08//g'           # sed 1.5，GNU sed，ssed所使用的十六进制的表示方法

 # 提取新闻组或 e-mail 的邮件头
 sed '/^$/q'                # 删除第一行空行后的所有内容

 # 提取新闻组或 e-mail 的正文部分
 sed '1,/^$/d'              # 删除第一行空行之前的所有内容

 # 从邮件头提取“Subject”（标题栏字段），并移除开头的“Subject:”字样
 sed '/^Subject: */!d; s///;q'

 # 从邮件头获得回复地址
 sed '/^Reply-To:/q; /^From:/h; /./d;g;q'

 # 获取邮件地址。在上一个脚本所产生的那一行邮件头的基础上进一步的将非电邮
 # 地址的部分剃除。（见上一脚本）
 sed 's/ *(.*)//; s/>.*//; s/.*[:<] *//'

 # 在每一行开头加上一个尖括号和空格（引用信息）
 sed 's/^/> /'

 # 将每一行开头处的尖括号和空格删除（解除引用）
 sed 's/^> //'

 # 移除大部分的HTML标签（包括跨行标签）
 sed -e :a -e 's/<[^>]*>//g;/</N;//ba'

 # 将分成多卷的uuencode文件解码。移除文件头信息，只保留uuencode编码部分。
 # 文件必须以特定顺序传给sed。下面第一种版本的脚本可以直接在命令行下输入；
 # 第二种版本则可以放入一个带执行权限的shell脚本中。（由Rahul Dhesi的一
 # 个脚本修改而来。）
 sed '/^end/,/^begin/d' file1 file2 ... fileX | uudecode   # vers. 1
 sed '/^end/,/^begin/d' "$@" | uudecode                    # vers. 2

 # 将文件中的段落以字母顺序排序。段落间以（一行或多行）空行分隔。GNU sed使用
 # 字元“\v”来表示垂直制表符，这里用它来作为换行符的占位符——当然你也可以
 # 用其他未在文件中使用的字符来代替它。
 sed '/./{H;d;};x;s/\n/={NL}=/g' file | sort | sed '1s/={NL}=//;s/={NL}=/\n/g'
 gsed '/./{H;d};x;y/\n/\v/' file | sort | sed '1s/\v//;y/\v/\n/'

 # 分别压缩每个.TXT文件，压缩后删除原来的文件并将压缩后的.ZIP文件
 # 命名为与原来相同的名字（只是扩展名不同）。（DOS环境：“dir /b”
 # 显示不带路径的文件名）。
 echo @echo off >zipup.bat
 dir /b *.txt | sed "s/^\(.*\)\.TXT/pkzip -mo \1 \1.TXT/" >>zipup.bat

使用SED：Sed接受一个或多个编辑命令，并且每读入一行后就依次应用这些命令。
当读入第一行输入后，sed对其应用所有的命令，然后将结果输出。接着再读入第二
行输入，对其应用所有的命令……并重复这个过程。上一个例子中sed由标准输入设
备（即命令解释器，通常是以管道输入的形式）获得输入。在命令行给出一个或多
个文件名作为参数时，这些文件取代标准输入设备成为sed的输入。sed的输出将被
送到标准输出（显示器）。因此：

 cat filename | sed '10q'         # 使用管道输入
 sed '10q' filename               # 同样效果，但不使用管道输入
 sed '10q' filename > newfile     # 将输出转移（重定向）到磁盘上

要了解sed命令的使用说明，包括如何通过脚本文件（而非从命令行）来使用这些命
令，请参阅《sed & awk》第二版，作者Dale Dougherty和Arnold Robbins
（O'Reilly，1997；http://www.ora.com），《UNIX Text Processing》，作者
Dale Dougherty和Tim O'Reilly（Hayden Books，1987）或者是Mike Arst写的教
程——压缩包的名称是“U-SEDIT2.ZIP”（在许多站点上都找得到）。要发掘sed
的潜力，则必须对“正则表达式”有足够的理解。正则表达式的资料可以看
《Mastering Regular Expressions》作者Jeffrey Friedl（O'reilly 1997）。
Unix系统所提供的手册页（“man”）也会有所帮助（试一下这些命令
“man sed”、“man regexp”，或者看“man ed”中关于正则表达式的部分），但
手册提供的信息比较“抽象”——这也是它一直为人所诟病的。不过，它本来就不
是用来教初学者如何使用sed或正则表达式的教材，而只是为那些熟悉这些工具的人
提供的一些文本参考。

括号语法：前面的例子对sed命令基本上都使用单引号（'...'）而非双引号
（"..."）这是因为sed通常是在Unix平台上使用。单引号下，Unix的shell（命令
解释器）不会对美元符（$）和后引号（`...`）进行解释和执行。而在双引号下
美元符会被展开为变量或参数的值，后引号中的命令被执行并以输出的结果代替
后引号中的内容。而在“csh”及其衍生的shell中使用感叹号（!）时需要在其前
面加上转义用的反斜杠（就像这样：\!）以保证上面所使用的例子能正常运行
（包括使用单引号的情况下）。DOS版本的Sed则一律使用双引号（"..."）而不是
引号来圈起命令。

'\t'的用法：为了使本文保持行文简洁，我们在脚本中使用'\t'来表示一个制表
符。但是现在大部分版本的sed还不能识别'\t'的简写方式，因此当在命令行中为
脚本输入制表符时，你应该直接按TAB键来输入制表符而不是输入'\t'。下列的工
具软件都支持'\t'做为一个正则表达式的字元来表示制表符：awk、perl、HHsed、
sedmod以及GNU sed v3.02.80。

不同版本的SED：不同的版本间的sed会有些不同之处，可以想象它们之间在语法上
会有差异。具体而言，它们中大部分不支持在编辑命令中间使用标签（:name）或分
支命令（b,t），除非是放在那些的末尾。这篇文档中我们尽量选用了可移植性较高
的语法，以使大多数版本的sed的用户都能使用这些脚本。不过GNU版本的sed允许使
用更简洁的语法。想像一下当读者看到一个很长的命令时的心情：

   sed -e '/AAA/b' -e '/BBB/b' -e '/CCC/b' -e d

好消息是GNU sed能让命令更紧凑：

   sed '/AAA/b;/BBB/b;/CCC/b;d'      # 甚至可以写成
   sed '/AAA\|BBB\|CCC/b;d'

此外，请注意虽然许多版本的sed接受象“/one/ s/RE1/RE2/”这种在's'前带有空
格的命令，但这些版本中有些却不接受这样的命令:“/one/! s/RE1/RE2/”。这时
只需要把中间的空格去掉就行了。

速度优化：当由于某种原因（比如输入文件较大、处理器或硬盘较慢等）需要提高
命令执行速度时，可以考虑在替换命令（“s/.../.../”）前面加上地址表达式来
提高速度。举例来说：

   sed 's/foo/bar/g' filename         # 标准替换命令
   sed '/foo/ s/foo/bar/g' filename   # 速度更快
   sed '/foo/ s//bar/g' filename      # 简写形式

当只需要显示文件的前面的部分或需要删除后面的内容时，可以在脚本中使用“q”
命令（退出命令）。在处理大的文件时，这会节省大量时间。因此：

   sed -n '45,50p' filename           # 显示第45到50行
   sed -n '51q;45,50p' filename       # 一样，但快得多

如果你有其他的单行脚本想与大家分享或者你发现了本文档中错误的地方，请发电
子邮件给本文档的作者（Eric Pement）。邮件中请记得提供你所使用的sed版本、
该sed所运行的操作系统及对问题的适当描述。本文所指的单行脚本指命令行的长
度在65个字符或65个以下的sed脚本〔译注1〕。本文档的各种脚本是由以下所列作
者所写或提供：

 Al Aab                               # 建立了“seders”邮件列表
 Edgar Allen                          # 许多方面
 Yiorgos Adamopoulos                  # 许多方面
 Dale Dougherty                       # 《sed & awk》作者
 Carlos Duarte                        # 《do it with sed》作者
 Eric Pement                          # 本文档的作者
 Ken Pizzini                          # GNU sed v3.02 的作者
 S.G. Ravenhall                       # 去html标签脚本
 Greg Ubben                           # 有诸多贡献并提供了许多帮助
-------------------------------------------------------------------------

译注1：大部分情况下，sed脚本无论多长都能写成单行的形式（通过`-e'选项和`;'
号）——只要命令解释器支持，所以这里说的单行脚本除了能写成一行还对长度有
所限制。因为这些单行脚本的意义不在于它们是以单行的形式出现。而是让用户能
方便地在命令行中使用这些紧凑的脚本才是其意义所在。

通过日志来查看 squid 的一些基本的运行状态：

1. access.log

配置语句：

logformat combined %>a %ui %un [%tl] “%rm %ru HTTP/%rv” %Hs %<st “%{Referer}>h” “%{User-Agent}>h” %Ss:%Sh:%tr
cache_access_log /data1/logs/access.log combined

打下的log格式为：

125.71.196.17 - - [14/May/2008:12:16:13 +0800] “GET http://you.video.sina.com.cn/b/13441121-1212188024.html HTTP/1.1″ 200 8820 “http://you.video.sina.com.cn/” “Mozilla/4.0 (compatible; MSIE 6.0; Windows NT 5.1; SV1)” TCP_MEM_HIT:NONE:21089

可以通过脚本查看一些统计信息，如各种反应状态所占的比例，通常较好的情况下HIT所占的比例（应该就是所谓的命中率）可以在70%~80%

Continue reading »

C、传统 C++

#include <assert.h>　　　　//设定插入点
#include <ctype.h>　　　　 //字符处理
#include <errno.h>　　　　 //定义错误码
#include <float.h>　　　　 //浮点数处理
#include <fstream.h>　　　 //文件输入／输出
#include <iomanip.h>　　　 //参数化输入／输出
#include <iostream.h>　　　//数据流输入／输出
#include <limits.h>　　　　//定义各种数据类型最值常量
#include <locale.h>　　　　//定义本地化函数
#include <math.h>　　　　　//定义数学函数
#include <stdio.h>　　　　 //定义输入／输出函数
#include <stdlib.h>　　　　//定义杂项函数及内存分配函数
#include <string.h>　　　　//字符串处理
#include <strstrea.h>　　　//基于数组的输入／输出
#include <time.h>　　　　　//定义关于时间的函数
#include <wchar.h>　　　　 //宽字符处理及输入／输出
#include <wctype.h>　　　　//宽字符分类

//////////////////////////////////////////////////////////////////////////

标准 C++　（同上的不再注释）

#include <algorithm>　　　 //STL 通用算法
#include <bitset>　　　　　//STL 位集容器
#include <cctype>
#include <cerrno>
#include <clocale>
#include <cmath>
#include <complex>　　　　 //复数类
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>　　　　　 //STL 双端队列容器
#include <exception>　　　 //异常处理类
#include <fstream>
#include <functional>　　　//STL 定义运算函数（代替运算符）
#include <limits>
#include <list>　　　　　　//STL 线性列表容器
#include <map>　　　　　　 //STL 映射容器
#include <iomanip>
#include <ios>　　　　　　 //基本输入／输出支持
#include <iosfwd>　　　　　//输入／输出系统使用的前置声明
#include <iostream>
#include <istream>　　　　 //基本输入流
#include <ostream>　　　　 //基本输出流
#include <queue>　　　　　 //STL 队列容器
#include <set>　　　　　　 //STL 集合容器
#include <sstream>　　　　 //基于字符串的流
#include <stack>　　　　　 //STL 堆栈容器
#include <stdexcept>　　　 //标准异常类
#include <streambuf>　　　 //底层输入／输出支持
#include <string>　　　　　//字符串类
#include <utility>　　　　 //STL 通用模板类
#include <vector>　　　　　//STL 动态数组容器
#include <cwchar>
#include <cwctype>

using namespace std;

//////////////////////////////////////////////////////////////////////////

C99 增加

#include <complex.h>　　 //复数处理
#include <fenv.h>　　　　//浮点环境
#include <inttypes.h>　　//整数格式转换
#include <stdbool.h>　　 //布尔环境
#include <stdint.h>　　　//整型环境
#include <tgmath.h>　　　//通用类型数学宏