|
|
很久以前翻译的 现在觉得里面写的都不错
拿出来与大家分享
其中会有翻译不好的地方
欢迎指正
dali是bell实验室的内存数据库产品
里面有很多新特性
如支持大于内存的数据库容量等
| 无双 回复于：2003-07-01 21:59:25
| The Architecture of the Dalí Main Memory Storage Manager
DALI SYSTEM DESIGNED INFOMATION
DALI SYSTEM DESIGNED INFOMATION 1
Abstract 1
1。INTRODUCTION 2
2．ARCHITECTURE 5
2．1 Layers of Abstraction 6
2．2 Pointers and Offsets 7
2．3 Storage Allocation 8
3TRANSACTION MANAGEMENT IN DALI 9
3．3 Transactions and Operations 12
3．4 Logging Model 13
3．5 Ping-pong Checkpointing 14
3．6 Abort Processing 16
3．7 Recovery 16
4 FAULT TOLERANCE 18
4．1 Protection from Bad Writes 18
4．2 Protection from Process Death 20
5 COLLECTIONS AND INDEXES 21
5．2 Extendible Hash 22
5．3 T-tree Indexes 23
6 DALI RELATIONAL MANAGER 24
7 CONCLUSION 25
7．1 Acknowledgments 25
THE ARCHITECTURE OF THE DALI MAIN MEMORY STORAGE MANAGER 26
9 Dali: Motivation and Principles 26
Motivation 26
Principles 26
Transactional Model 27
Build A High-Perfomance Application 28
| | 无双 回复于：2003-07-01 22:00:32
| Abstract
The performance needs of many database applications require that the entire database be stored in main memory. The Dalí system is a main memory storage manager designed to provide the persistence(持久) (that is, the retention of data after a crash), availability, and safety guarantees（保证） that users typically expect from a disk-resident保留 database, including support for transactions. Because it is tuned to support in-memory data, Dalí offers very high performance. User processes map the entire database into their address space and access data directly, thereby avoiding expensive remote procedure calls and buffer manager interactions typical of accesses in the disk-resident commercial systems available today. Dalí recovers from a system or process failure by restoring the database to a consistent state. It also provides unique concurrency control and memory protection features, as well as index management and a relational application programming interface.
用户进程直接把整个数据库映射到它们的地址空间并直接访问数据。因此避免了在当今典型磁盘商用数据库中的昂贵的远程过程调用和缓冲区管理器之间的交互。Dalí可以像索引管理器和关系应用程序接口一样提供唯一的并发控制和内存保护特征，
缩写与术语ATT 活动事务表CLR 补偿日志记录Free tree 存储自由内存空间的树Latch 一种短期锁，通过高速的相互排斥的机制实现Logical undo log record 一种记录，包含怎样取消操作的描述Physical undo log record 一种记录，包含怎样取消物理改变S 共享模式SQL 结构化查询语言X 排斥模式
| | 无双 回复于：2003-07-01 22:01:10
| 1。INTRODUCTION
A number of database applications particularly in the telecommunications industry and other industries involved in real-time content delivery require very high performance access to data. Such applications typically need high transaction rates, coupled with very low latency for transactions, and they impose stringent durability and availability requirements. Consider, for example, a real phone-company application in which phone call data is recorded and queries can be issued against the data. The application must be able to process several thousand (albeit small) requests (lookups/updates) per second, with less than 50 milliseconds latency for lookups and less than a few minutes of down time per year.
大量的数据库应用研究，特别是在电信工业和其它工业，对实时内容交付要求对数据的访问有很高性能。这些应用要求有很高的传输率，加上低的传输延迟，他们要求有严格的持久性和高的可靠性。考虑一下，例如在一个实时的电话公司应用中，电话数据可以与数据传送一样的速度被记录和查询。这个应用要求必须每秒可以处理几千个请求，并要求有少于50毫秒的延迟和一年低于几分钟的停机时间。
The increasing availability of large, relatively cheap memory suggests that more database applications could reside entirely or almost entirely in main memory. The performance of these types of applications will benefit from having data cached in main memory. If, in addition, the storage manager supporting such applications is tailored to main memory, performance can be increased significantly, as shown in Lehman et al.1
不断增加的可以得到的大量廉价的内存使更多的应用程序可以全部或是几乎全部放在内存中这引起类型的程序将可以因为数据放在内存中而获得性能的提高。
The storage manager of a database system provides its core functionality, such as concurrency control, recovery mechanisms, storage allocation/free space management, transaction management, and index management. Numerous storage managers have been implemented for disk-resident data, including the storage managers of Exodus2 and Starburst.1 With the exception of the Starburst main-memory storage component, 1 however, we are not aware of any storage manager that is tailored for main-memory resident data. (System M, described by Salem and Garcia-Molina,3 is a transaction processing testbed for memory-resident data, but it is not a full-feature storage manager.)
数据库系统的存储管理器提供数据库的核心功能，如并发控制，恢复机制，存储空间的分配/释放，事务管理和索引管理。在数据保留在磁盘上的数据库系统中已有无数的存储管理器，如Exodus2和Starburst.1
| | 无双 回复于：2003-07-01 22:01:34
| The Dalí system4 named in honor of Salvadore Dalí, for his famous painting, The Persistence of Memory is a storage manager implemented at Bell Labs. It was developed and optimized for environments in which the database resides in the main memory. A number of principles that have evolved with Dalí over the past three years now guide its design and evolution, including:
持久内存系统是在BELL LAB实现的一个存储管理器。它为整个数据库保存在内存中而开发并优化。在过去的三年中大量的定理已被发明并用于指导DALI的开发。
· Direct access to data, 直接访问数据
· No interprocess communication, 内有进程间通信
· Fault tolerance, and 容错性和
· Consistency of response time. 一致的返回时间
| | 无双 回复于：2003-07-01 22:01:54
| The first of these principles is direct access to data. Dalí uses a memory-mapped architecture in which the database is mapped into the virtual address space of the process. This allows the user to acquire pointers directly to information stored in the database. A related principle is "no interprocess communication" for basic system services. All concurrency control and logging services are provided through shared memory rather than communication with a server.
Another guiding principle of Dalí is its ability to create fault-tolerant applications. This is best exemplified by its use of the transactional paradigm, the dominant technology for providing fault tolerance in critical applications. In fact, Dalí provides an advanced, explicitly multilevel transaction model that has facilitated the production of high-concurrency indexing and storage structures. To help ensure the integrity of data stored in shared memory, Dalí also supports recovery from process and system failures and helps prevent corruption of data through its use of code words and memory protection.
第一个定理是直接访问数据。DALI使用内存映射体系，把整个数据库映射到进程的虚地址空间。这使用户可以直接通过指针访问储存在MMDB中的信息。相关的定理是基本的系统服务没有内部进程间通信。所有的并发控制和日志服务通过共享内存而不是与服务器进行内部通信。
另一个指导方向是DALI可以创建容错性应用。这方面最好的例子是在事务方面使用的范例，有显见的技术在严格的应用中提供容错性应用。事实上DALI提供一个高级的、明确的具有易用的高并发性的索引和存储结构的产品的多级事务模型。为了帮助确认数据完整的保存在共识内存中，DALI同样支持从进程失败和系统失败中恢复数据，并使用关键字和内存保存来阻止脏数据。
A key requirement for applications that expect to store all their data in main memory is consistency of response time. Dalí also supports consistency by providing fine-grained concurrency control and minimal interference with the checkpointer owing to latching. Other principles that have guided Dalí's implementation have been a toolkit approach and support for multiple interface levels. The toolkit approach implies, for example, that logging facilities can be turned off if data does not need to be persistent and that locking can be turned off if data is private to a process. To optimize critical application components with special implementations, Dalí exposes low-level components to the user. The developers of most applications, however, will prefer the high-level relational interface.
应用程序的一个关键需求是希望它所有保存在内存中的数据可以有一致的访问时间。DALI通过提供细粒度的并发性控制和由于有锁机制的检查点的最小接口支持一致性。其它引导DALI实现的定理已经成为一个工具箱方法并支持多接口层。例如在工具箱方法实现中，如果数据不需要有持久性的话日志机制可以被关闭，如果数据只是一个进程私有的话那么锁机制也可以关闭。在特定实现中为了为严格应用优化，DALI提供低层组件给用户，但是对多数应用，可以更会对高层的关系接口更感兴趣。
| | 无双 回复于：2003-07-01 22:02:23
| Although Dalí can be used in systems where the database is larger than its main memory (as long as the database fits in the virtual address space of the process), the architecture of Dalí from storage allocation and indexing to its recovery facilities has been designed to deliver high performance when the database fits into the physical main memory of the computer.
尽管DALI可以在数据库比内存大[最大值可以等于虚地址窨]的情况下使用，但是但是DALI的存储分配和恢复机制的索引体系是为数据库放在主存中进行优化的。
This paper provides a brief overview of the components that constitute the Dalí storage manager. We provide a more detailed description of Dalí's architecture in Bohannon et al.5 and on our Web page at http://www.bell-labs.com/org/project/dali. DataBlitz, a new product based on the Dalí system, will become available in March 1997.
这篇论文提供对DALI系统存储管理器的一个简要描述，在我们的网站http://www.bell-labs.com/org/project/dal上提供更多的设计思想
| | 无双 回复于：2003-07-01 22:43:37
| 2．ARCHITECTURE
The database in the Dalí architecture consists of one or more database files and a special system database file. User data is stored in database files, but all data related to database support, such as log and lock data, is stored in the system database file. This enables the uniform use of storage allocation routines[常规,] for (persistent) user data, as well as (nonpersistent) system data such as locks and logs. The system database file also stores information about the other database files in the system.
在DALI系统中数据库可以看成是由一个或多个数据文件和一个特殊的系统文件组成。用户数据保存在数据文件中，但所有与数据库支持相关的数据，如日志和锁数据，保存在系统数据文件中。这可以对持久的用户数据和非持久性的系统数据[如锁和日志]一致使用常规的存储分配器。系统数据文件同样保存系统中其它数据文件的信息。
Database files opened by a process are directly mapped into the address space of that process, as shown in Figure 1 . In Dalí, either memory-mapped files or shared-memory segments can be used to provide this mapping. Different processes may map different sets of database files and may map the same database file to different locations in their address space. This flexibility[适应性] precludes[阻止] using virtual memory addresses as physical pointers to data in database files, but it does provide two important benefits. First, a database file can be resized easily. Second, the total active database space on the system may exceed the addressing space of a single process. This is useful on machines with 32-bit addressing in which physical memory can significantly exceed the amount of memory addressable by a single process (for example, Sun's SPARCCenter product line).
正如图1所示，被进程打开的数据库文件被直接映射到进程的地址空间。在DALI中，内存映射文件或者共识内存段都可以提供这个映射。不同的进程可以映射数据库文件中不同的集合，并且可以映射相同的数据文件到它们自己的不同的进程空间中。这种适应性阻止使用虚地址空间作为物理指针指向数据库文件中的数据，但是它确实提供两个重要的利益：第一个，数据库文件可以很容易的改变大小。2系统中活动的数据库总空间可超过单进程的地址空间。这对32位内存寻址空间的机器来说可以显著超过单个进程总共可以使用的地址空间。
However, using Dalí in a 64-bit machine may significantly change both of these considerations, leading us to consider using physical addressing. If a single database file can be limited to something like 64 GB, then each process could still map close to a billion database files, which can be expected to far exceed the total database space.
然而，在64位机器上使用DALI时在这些方面必须有显著的改变，让我们考虑使用物理地址空间。如果单个数据文件可以限制到64GB，那么每一个进程仍然可以紧密映射到上万个数据库文件，而这些文件远超过总的数据库空间。
|
| | 无双 回复于：2003-07-01 22:44:31
| 2．1 Layers of Abstraction
Dalí's architecture, illustrated in Figure 2 , is organized in multiple layers of abstraction to support the toolkit approach discussed earlier. At the highest level, users can interact with Dalí's relational manager. Below that level is what we call the heap-file/indexing layer, which provides support for fixed-length and variable-length collections, as well as template-based indexing abstractions. In general, at this level, a user does not need to interact with individual locks or latches. (A latch is a short-term lock implemented by a high-speed mutual[相互的] exclusion [排它] mechanism.) Instead, the user specifies a policy such as "no locking" or "lock-plus-handle-phantoms" to the lower level.
如图2所示，为了支持早些时候讨论过的工具箱，DALI的结构由多个抽象层组成。在最高层，用户可以与DALI的关系管理器交互。下一层我们叫它堆文件/索引层，这一层提供定长和变长记录的收集，同时也提供对基于模板的索引的抽象。通常在这一层，用户不需要与不同的锁和临时锁[latches]进行交互（一个latches是一种短期锁，通过高速的互斥机制实现）。相反，在更低一层用户必须指定“不用锁”或“加强锁并处理幻象”策略。
Services for logging, locking, latching, multilevel recovery, and storage allocation are exposed at the lowest level. New indexing methods can be built on this layer, as can special-purpose data structures for either an application or a database management system. By definition, this level has the most complex user interface, but it has proven[证明] itself during the creation of the higher-level interfaces and database systems described above.
日志，锁，短期锁（latching），多层恢复，存储分配机制这些服务出现在最底层。因此可以为一个程序或一个数据库管理系统指定特殊的数据结构。通过定义，这一层拥有最复杂的用户接口，可以通过它创建高层接口和以上描述的数据库系统。
|
| | 无双 回复于：2003-07-01 22:44:50
| 2．2 Pointers and Offsets
It is crucial[紧要的] to the performance of Dalí that database pointers be mapped efficiently to virtual memory addresses. In Dalí, each process maintains a database-offset table, which specifies the location in memory where each database file is mapped. The table is implemented as an array indexed by the (integer) database file identifier.
数据库指针被高效的映射到虚拟内存中对DALI的性能是很紧要的。在DALI中，每个进程维护一个数据库借助偏移表，该表指定每个数据库文件映射到内存中的位置。这个表用数据实现，并用数据库文件描述符作索引。
The primary type of database pointer in Dalí contains a database file identifier and an offset within the database file. Dereferencing a database pointer p simply involves adding the offset contained in p to the virtual memory address at which the database file is mapped, looked up from the offset table. A second form of database pointer is available if the database file is known from context. For example, all pointers from a certain index might reside in a particular database file. In this case, we may store just the offset within the database file as the pointer. Both offsets and full pointers are implemented as simple C++ template classes, which allow them to be used as "smart pointers."
DALI中的原始数据库指针保持着数据库文件的描述符和在数据库文件中的偏移。
| | 无双 回复于：2003-07-01 22:45:31
| 2．3 Storage Allocation
This section describes the Dalí storage allocation mechanism. Each database file in Dalí is composed组成[ of segments, which are contiguous page-aligned units of allocation, similar to clusters in a file system. As Figure 3 illustrates, a chunk [大块]is a collection of segments. Recovery characteristics[描述] of memory (transient[临时的], zeroed[为零的], or persistent[持久的]) are specified on a per-chunk basis when a chunk is created. Zeroed memory remains allocated on recovery, but each byte is set to zero. The data in transient memory is no longer allocated on recovery. Users allocate memory within a chunk, but they do not specify a particular segment. Because segments can be arbitrarily large (within the size of the database), equally large objects can be stored contiguously. When allocating space within a chunk, the system returns a standard Dalí pointer to the space, which specifies the offset within the file. The elements shown linking together segments in a chunk are themselves stored in a special chunk used for control information. Storing control information separately from the data reduces the likelihood that it will be corrupted by stray application pointers.
本单讨论DALI的存储分配机制，DALI中每一个数据库文件都是由段组成，段是连续的页面对齐的单元，与文件系统中的簇相似。在图3的图解中，大块是段的集合。当每个大块建立时，内存[临时的，为零的，持久的]的恢复描述就会在每个块的开始处指定。零内存保留用于恢复的内存，但是它是全零的。临时内存中的数据不再出现在恢复内存中。用户在块内分配央存，但他们没有指定一个特定的段。因为段可以任意大[在数据库的最大容量内]。相同的大对象可以连接的保存。当在块内分配空间，系统返回一个标准的DALI指针指向该对象，该指针描述了在文件内的偏移。在块中显示为互相连接的段的元素是自己保存在一个特殊的块用于保存控制信息。把箜制信息与数据信息分开保存减少它被错误的应用程序指针干扰的机会。
Within a chunk, various types of allocators are available as tradeoffs for speed, safety, and size. To avoid excessive overhead for small items, no record of allocated space is retained in any allocator; therefore, the user must keep track of the size of the allocated data. If a record of space is required, the user must specify a layer above the allocator. The currently defined and implemented allocators in Dalí are:
在块中，为了在速度、安全性、尺寸大小的折衷，可以使用不同的内存分配器。为了避免过多的头部，在任何分配器中都没有保存已分配的空间的记录。因此，用户必须跟踪已分配数据的大小。如果需要分配一个记录的空间，用户必须指定在分配器上的层。当前在DALI中已定义和实现的分配器是：
The power-of-two allocator, which assigns storage in buckets of size 2i * m, where m is some minimum item size; and
2的N方分配器，分配器按2i * m桶进行分配。M是最小单元的大小
The coalescing allocator, which allocates exact amounts of space and merges adjacent free space using a free tree.
接合分配器，分配准确的空间并使用自由树接合邻近的自由空间
|
| | 无双 回复于：2003-07-01 22:45:49
| 3TRANSACTION MANAGEMENT IN DALI
This section describes how Dalí achieves transaction atomicity, isolation, and durability. In Dalí, transaction management is based on principles of multilevel recovery.6 Dalí is one of the few implementations of explicit[外在的, 清楚的, 直率的, (租金等)直接付款的] multilevel recovery reported to date and, to our knowledge, is the only implementation of multilevel recovery for main memory.
这一章讨论DALI怎样达到事务的原子性、一致性和持久性。在DALI中，事务模型基于多层恢复定理。DALI是少数使用清楚的多层恢复机制的数据库，同时它也是唯一实现多层恢复机制的MMDB。
In our recovery scheme, data is logically organized into regions. A region is a unit of physical locking for recovery, not directly related to the concepts of segments or chunks. A region, therefore, can be a tuple or an object that fits in a single segment, or it can be an arbitrary data structure like a list or a tree, possibly comprising an entire chunk. Each region has a single associated lock with exclusive (X) and shared (S) modes. Referred to as the region lock, it guards accesses and updates to the region.
在我们的恢复机制中，数据是逻辑组织到区域中，一个区域是一个有用于恢复的锁的物理单元，与段或块的概念没有直接的关联。因此一个区域，可以是一个tuple或是一个使用一个记录的对象，也可以是一个任意的数据结构，如树或是链表，由整个块组成。每一个区域有个相关的锁，这个锁有排它X和共识S两种模式。可以通过访问区域锁来对区域进行更新。
| | 无双 回复于：2003-07-01 22:46:04
| 3．1 Multilevel Recovery
Multilevel recovery provides recovery support for enhanced concurrency based on the semantics[语义] of operations. It allows weaker operation locks to be used in place of stronger shared/exclusive region locks.
多层恢复为增加的并发性提供操作语义上的恢复支持。它允许在使用强的在会谈中锁/排它锁的地方使用弱的操作锁代替。
A common example of the need for multilevel recovery occurs in index management, where holding region locks until transaction commit leads to unacceptably low levels of concurrency. If undo logging (explained later, in the section titled "Logging Model") has been performed physicallysuch as recording exactly which bytes were modified to insert a key into the indexthen the transaction management system must ensure that these physical undo descriptions are valid until transaction commit. Because the descriptions refer to specific updates at specific positions, this typically implies that the region locks on updated index nodes are retained to ensure correct recovery, even though they are no longer needed for correct concurrent access to the index.
要使用多层恢复的常见例子是索引管理器，在这里保持区域锁直到事务完成，这导致不可接受的低层次的并发性。如果UNDO日志（在后面的"Logging Model"会有解释）记录已以被物理的执行的日志，如准确到为了插入索引记录哪个字节被修改 ，那么事务管理系统必须保证这些物理UNDO描述在事务在更新索引提交前是可以变长的。因为描述指定了对特定位置的特定更新，这意味着在更新索引节点时的区域锁为了正确恢复必须被保留，尽管它们在正确的并发性访问不不再需要。
The multilevel recovery approach replaces these low-level physical-undo log records with higher-level logical-undo log records, which contain undo descriptions at the level of operations. For an insert operation, a physical-undo record would be replaced by a logical-undo record to indicate that the inserted key must be deleted. Once this replacement is made, the region locks can be released and replaced by less restrictive operation locks. For example, the region locks can be released on nodes involved in an insert, whereas an operation lock is retained on the newly inserted key, to prevent the key from being accessed or deleted.
多层UNDO系统使用高层的逻辑ONDO日志记录代替物理UNDO日志记录，逻辑UNDO日志记录保存当前层次的UNDO描述。在INSERT操作中，物理UNDO记录将用该记录必须被删除的逻辑UNDO记录代替。一旦这个代替完成，区域锁次被释放并用更少约束的操作锁代替。例如，在一个包括插入的操作中区域锁可以被释放，但是一个包括新插入的键的操作锁将被保持，用于防止这个键被访问或是删除。
| | 无双 回复于：2003-07-01 22:47:21
| 3．1 Multilevel Recovery
Multilevel recovery provides recovery support for enhanced concurrency based on the semantics[语义] of operations. It allows weaker operation locks to be used in place of stronger shared/exclusive region locks.
多层恢复为增加的并发性提供操作语义上的恢复支持。它允许在使用强的在会谈中锁/排它锁的地方使用弱的操作锁代替。
A common example of the need for multilevel recovery occurs in index management, where holding region locks until transaction commit leads to unacceptably low levels of concurrency. If undo logging (explained later, in the section titled "Logging Model") has been performed physicallysuch as recording exactly which bytes were modified to insert a key into the indexthen the transaction management system must ensure that these physical undo descriptions are valid until transaction commit. Because the descriptions refer to specific updates at specific positions, this typically implies that the region locks on updated index nodes are retained to ensure correct recovery, even though they are no longer needed for correct concurrent access to the index.
要使用多层恢复的常见例子是索引管理器，在这里保持区域锁直到事务完成，这导致不可接受的低层次的并发性。如果UNDO日志（在后面的"Logging Model"会有解释）记录已以被物理的执行的日志，如准确到为了插入索引记录哪个字节被修改 ，那么事务管理系统必须保证这些物理UNDO描述在事务在更新索引提交前是可以变长的。因为描述指定了对特定位置的特定更新，这意味着在更新索引节点时的区域锁为了正确恢复必须被保留，尽管它们在正确的并发性访问不不再需要。
The multilevel recovery approach replaces these low-level physical-undo log records with higher-level logical-undo log records, which contain undo descriptions at the level of operations. For an insert operation, a physical-undo record would be replaced by a logical-undo record to indicate that the inserted key must be deleted. Once this replacement is made, the region locks can be released and replaced by less restrictive operation locks. For example, the region locks can be released on nodes involved in an insert, whereas an operation lock is retained on the newly inserted key, to prevent the key from being accessed or deleted.
多层UNDO系统使用高层的逻辑ONDO日志记录代替物理UNDO日志记录，逻辑UNDO日志记录保存当前层次的UNDO描述。在INSERT操作中，物理UNDO记录将用该记录必须被删除的逻辑UNDO记录代替。一旦这个代替完成，区域锁次被释放并用更少约束的操作锁代替。例如，在一个包括插入的操作中区域锁可以被释放，但是一个包括新插入的键的操作锁将被保持，用于防止这个键被访问或是删除。
| | 无双 回复于：2003-07-01 22:47:49
| 3．2 System Overview
Figure 4 presents an overview of the structures used for recovery. The database is mapped into the address space of each process, as described earlier in "Architecture." (The database here represents a single database file. In fact, different database files can be checkpointed at different times, and transactions can span database files arbitrarily. The generalization[一般化] for multiple database files is straightforward, but it is omitted[忽略] for clarity[透明] and space.) Two checkpoint images of the database, Ckpt_A and Ckpt_B , reside on disk. Also stored on disk are cur_ckpt , an "anchor" pointing to the most recent valid checkpoint image for the database, as well as a single system log containing redo information, with its tail in memory. The variable end_of_stable_log stores a pointer in the system log to indicate that all records before the pointerin both time and position in the loghave been flushed to the stable system log.
图4介绍了恢复中使用的结构。正如早期讨论的那样数据库被映射到每个进程的地址空间，（这里的数据库表示单个数据文件，事实上，不同的数据库文件可以在不同时候产生检查点，事务可以任意跨越数据库文件。多数据库文件的一般化是直接的，但是它忽略了透明性和空间）数据库的两个检查点映象Ckpt_A and Ckpt_B在磁盘上。同样保存在磁盘上的是当前检查点cur_ckpt,一个锚点，记录当前数据库的不同检查点，同样也记录了保持有REDO信息的单个系统信息的系统日志。不同的end_of_stable_log保存不同的指针，这些指针指向的位置表示该位置前的所有记录已被写到磁盘上的系统日志同一时间和日志位置中。
A single active transaction table (ATT), stored in the system database, contains separate redo and undo logs for each active transaction. A dirty page table, dpt , is maintained for the database (also in the system database); it records the pages that have been updated since the last checkpoint. The ATT (with undo logs) and the dirty page table are also stored with each checkpoint. The dirty page table in a checkpoint is referred to as ckpt_dpt .
单个活动事务表(ATT)，保存在系统数据库中，保存着每个事务独立的REDO和UNDO日志。脏页表dpt保存在数据库中（它同样出现在系统数据库中）。它记录自从上次检查点后被更新的页。ATT（带有UNDO日志）和脏页表同样保存在每个检查点。脏页表中的检查点被ckpt_dpt引用。
| | 无双 回复于：2003-07-01 22:48:09
| 3．3 Transactions and Operations
In our model, transactions consist of a sequence of operations. We assume, as did Lomet,7 that each operation has a level Li associated with it. An operation at level Li can consist of a sequence of operations at level Li-1. Transactions, assumed to be at level Ln, call operations at level Ln-1. Physical updates to regions are level L0 operations. For transactions, we distinguish between pre-commit and commit. When a transaction pre-commits, the commit record enters the system log in memory, establishing a point in the serialization order. Transactions commit when the commit record reaches the stable log (on disk). We use the same terminology for operations, where only the pre-commit point is meaningful, although this is sometimes referred to as "operation commit" in this paper.
在我们的模型中，事务认为一一系列的操作。我们假定，如Lomet,7 中一样，每个操作有与它相连的Li 层。在Li 层的操作可以看成是一系列的Li-1 层的操作。事务假定在Ln 层，它调用Ln-1 层的操作。区域的物理更新是L0 层的操作。对于事务来说，我们的区别是未提交和提交。当一个事务未提交，已提交的记录保存在内存中的系统日志中，并按连接的顺序分配一个指针。当已提交的记录写到可靠的日志时（在磁盘上）事务提交。我们对操作也的术语。仅未提交的指针是有意义的，虽然在这篇论文中有时引用“操作提交“。
A transaction obtains an operation lock before executing an operation (the lock is granted to the transaction if it commutes交换 with other operation locks held by active transactions). L0 operations are required to obtain[获得] region locks. The locks on the region are released as soon as the L1 operation pre-commits; in general, an operation lock at level Li is held until the transaction or the containing operation (at level Li+1) pre-commits. All the locks acquired by a transaction are released as soon as the transaction pre-commits. A deadlock is handled by checking for a cycle in the wait-for graph after a transaction has waited a certain amount of time for a lock. The multilevel variation[变化] of two-phase locking described above guarantees[保证] isolation[隔离] of a transaction (operation) from other transactions (operations).
在执行一个操作前一个事务维护一个操作锁（如果锁与其它活动事务中拥有的操作锁交换，那么它也被事务承认）。L0操作要获得操作锁。区域锁在在L1层操作预提交时被释放。通常，当事务或是包含该操作的操作（在Li+1层）预提交时在L1层的操作锁会被释放。当事务预提交时事务拥有的所有锁都会被释放。如果一个事务等待锁足够的时间后仍然没有得到那么这个锁当成死锁，被定时锁检查进程处理。以上讨论的两阶段上锁的多层模型变化保证一个事务/操作与其它事务/操作隔离。
| | 无双 回复于：2003-07-01 22:48:28
| 3．4 Logging Model
Dalí uses logging to implement the atomicity and durability of transactions. Undo logs ensure that incomplete transactions (operations) can be rolled back in case the transaction (operation) is aborted, while redo logs ensure durability in the face of system failure. The recovery algorithm maintains separate undo and redo logs in memory for each transaction. These are stored as linked lists off the entry for the transaction in the ATT. Each update (to a part of a region) generates physical undo and redo log records that are appended to the transaction's undo and redo logs, respectively.
DALI使用日志实现原子性和持久性。UNDO日志确定未完成的事务在事务退出时可以被回滚，REDO日志保证在系统错误时可以保证数据的持久性。恢复机制为每个事务保在内存中持着独立的UNDO和REDO日志，它们作为链表，保存在ATT表的事务入点处。每次更新（对区域的一部分）产生物理的UNDO和REDO日志，并分别被添加到事务的UNDO和REDO日志。
When a transaction/operation pre-commits, all the log records in the transaction's redo log are appended to the system log, and the logical-undo description for the operation is included in the operation commit log record within the system log. With the exception of these logical-undo descriptors, only redo records are written to the system log during normal processing. When an operation pre-commits, two things happen: the undo log records for its suboperations/updates are deleted (from the transaction's undo log), and a logical-undo log record containing the undo description for the operation is appended to the transaction's undo log. Undo logs of transactions already in memory that have pre-committed are deleted, because they are not required again. Locks acquired by an operation/transaction are released as soon as they pre-commit.
当一个事务/操作预提交时，事务REDO日志中所有日志记录被添加到系统日志中，操作的逻辑UNDO描述被包括在操作的提交日志中，并包含在系统日志中。除了这些逻辑UNDO日志，在普通的进程中仅REDO记录被写到磁盘上。当一个进程预提交时会发生两件事情：子操作/更新的UNDO日志从事务UNDO日志中删除，描述该操作的逻辑UNDO日志添加到事务的UNDO日志。已预提交的事务中已在内存中的UNDO日志被删除，因为它们已不再需要。操作/事务申请的锁在预提交时也会被释放。
When a transaction decides to commit, the system log is flushed to disk, ensuring the durability of committed transactions. The flushing procedure marks as dirty those pages updated by a redo log record written to disk in the dirty page table, dpt . In our recovery scheme, update actions do not obtain latches on pages; instead, region locks ensure that updates do not interfere with each other.
当一个事务决定提交时，系统日志被刷新到磁盘上，保证已提交事务的持久性。脏页表中被 写到磁盘上的REDO日志 更新的页面被刷新进程标志为脏页面。在我们的恢复机制中，更新操作不包括页面上的锁，相反，区域锁保证更新没有相互干扰。
| | 无双 回复于：2003-07-01 22:48:47
| 3．5 Ping-pong Checkpointing
Checkpointing ensures that only a final portion of the log is needed for recovery. To implement checkpointing in Dalí, two copies of the database image are stored on disk, and alternate checkpoints write dirty pages to alternate copies. This strategy（策略） is called ping-pong checkpointing (see, for example, Salem and Garcia-Molina3). The ping-pong checkpointing strategy permits a checkpoint being created to be temporarily inconsistent, that is, updates may have been written out before corresponding undo records have been written. After dirty pages are written out, however, a sufficient amount of redo and undo log information is written out to bring the checkpoint to a consistent state. If a failure occurs while one checkpoint is being created, the other checkpoint is still consistent and can be used for recovery.
检查点确认只有最后一部分日志需要进行恢复。为了在Dalí中实现检查点，数据库的两个影像被保存在磁盘上。这个策略叫做乒乓检查点（例如Salem and Garcia-Molina3）。乒乓检查点允许检查点在不一致的情况下临时创建。就是说，在相应的UNDO日志写出前更新可以被写出，然而在脏页表写出后，足够的REDO和UNDO日志信息被写到磁盘上，保证检查处于一个一致的状态。当在检查点创建的过程中产生系统失败，那么其它检查点仍然处于一致恹并可以用于恢复。
Before writing any dirty data to disk, the checkpoint notes the current end of the stable log in the variable end_of_stable_log , which will be stored with the checkpoint. This variable indicates where to start scanning the system log to recover from a crash. Next, the contents of the (in-memory) ckpt_dpt are set to those of the dpt , and the dpt is zeroed (noting of end_of_stable_log and zeroing of dpt are performed atomically with respect to flushing). The pages written out are those that were either dirty in the ckpt_dpt of the last completed checkpoint, or dirty in the current (in-memory) ckpt_dpt , or both. In other words, all pages that were modified since the current checkpoint image was last written, namely, pages that were dirtied since the last-but-one checkpoint, are written out. This ensures that updates described by log records preceding the current checkpoint's end_of_stable_log are included in the database image in the current checkpoint.
在写任何脏数据到磁盘前，检查点用变量end_of_stable_log标志当胶可靠日志的结束，这与检查点一起保存。这个变量表明在系统崩溃后恢复时应该从什么地方开始扫描日志，然后内存中的ckpt_dpt内容被设置成dpt内容，dpt内容被清0（在刷新到磁盘上时标志end_of_stable_log和把dpt清0是一个原子操作）。被写到磁盘上的页面是那些自从上次检查点后在ckpt_dpt中为脏的页面，或是在当前内存中ckpt_dpt中为脏的页面，或两者都是。换句话说，从当前检查点后，在上一次写回磁盘后，所有被修改的页面被写回磁盘。这确认日志记录中的更新在当前检查点的end_of_stable_log前，被当前检查点的数据库映象包括。
Checkpoints write out dirty pages without obtaining any latches and do not, therefore, interfere with normal operations. This fuzzy checkpointing is possible because physical-redo log records are generated by all updates; these are used during restart recovery and their effects are idempotent[幂等的]. After the database image has been written, undo log records are written out to disk for any uncommitted update whose effects have made it to the checkpoint image. This is performed by checkpointing the ATT after checkpointing the data; the checkpoint of the ATT writes out undo log records, as well as some other status information.
检查点写出的脏页表不包含任何锁，因此不干扰当前任何操作。因为物理REDO日志被所有的更新产生，它们在重起后的恢复中被使用，他们的影响是幂等的，所以这种模糊检查点是可行的。在数据库映象被写出后，其它未提交的更新的UNDO日志记录被写出，因为它们已影响了检查点映象。在对数据执行检查点完后在对ATT执行检查点时执行，对ATT执行检查点时写出UNDO日志记录，同时也会写出一些其它的状态信息。
After checkpointing is performed, a log flush must be done before declaring the checkpoint completed (and consistent) by toggling cur_ckpt to point to the new checkpoint. Undo logs are deleted on transaction or operation pre-commit, which may happen before the checkpoint of the ATT. If the checkpoint completes but the system fails before a log flush, the checkpoint may contain uncommitted updates for which no undo information exists. The log flush ensures that the transaction or operation has committed, so the updates will not have to be undone (except perhaps by a compensating operation, for which undo information will be present in the log).
在检查点执行完后，日志刷新必须在定义检查点完成前完成，（并一致性）通过把cur_ckpt指向新检查点。UNDO日志在事务或操作预提交时被删除，这可能出现在对ATT执行检查点前。如果检查点完成但是系统在刷新日志前崩溃，检查点可能会包含没有UNDO信息的未完成的更新，日志刷新确认更务或更新已提交，因此更新不必进行UNDO（除了对那些日志中包含UNDO信息的记录对可能通过补偿操作）
| | 无双 回复于：2003-07-01 22:49:03
| 3．6 Abort Processing
When a transaction abortsthat is, does not successfully complete executionupdates/operations described by log records in the transaction's undo log are undone by traversing the undo log sequentially from the end. The transaction is aborted by executing, in reverse order, every undo record just as if the execution were part of the transaction. Correct abort processing, even in the face of system failure, ensures the atomicity of transactions in Dalí.
当一个事务退出，就是说没有成功完成，事务UNDO日志记录中的更新/操作描述被从尾到头的顺序执行。每个UNDO记录的执行看成是事务的一部分。纠正退出进程，甚至在系统崩溃后也一样，这样来保证DALI的事务原子性。
Following the philosophy of repeating history, 6 new physical-redo log records are created for each physical-undo record encountered during the abort. Similarly, for each logical-undo record encountered, a new "compensation" or "proxy" operation is executed based on the undo description. Log records for updates performed by the operation are generated as they are during normal processing. Furthermore, when the proxy operation commits, the aborting transaction deletes all the proxy operation's undo log records and the logical-undo record for the operation that was undone. The commit record for the proxy operation serves a purpose similar to that served by compensation[补偿] log records (CLRs) in ARIES.6 During restart recovery, when the commit record for the proxy operation is encountered, the logical-undo log record for the operation that was undone is deleted from the transaction's undo log, preventing it from being undone again.
与哲学上的重复历史一样，在退出过程中，新的物理UNDO日志为每个物理UNDO日志创建，同样，每遇到一个逻辑UNDO记录，一个新的补偿或是代理操作将基于UNDO描述执行。更新过程中执行的日志记录和正常操作一样被产生，进一步的说，当代理操作完成后，退出事务删除所有代理操作的日志和已完成的逻辑UNDO日志。当代理操作提交日志服务的目的与在ARIES.6 中的补偿日志服务一样。在重起恢复机制在，当遇到代理操作提交记录时，已UNDO完毕的操作的逻辑UNDO记录被从事务UNDO日志中删除，阻止它被再次UNDO。
| | 无双 回复于：2003-07-01 22:49:22
| 3．7 Recovery
Recovery refers to the actions taken after a system fails to return the database to a transaction-consistent state, which reflects exactly the effects of those transactions that have committed. Recovery uses the stable log, which has been flushed to disk, as well as information stored in the last checkpoint. A checkpoint is taken when the database is created, and others may be taken later, so recovery is described based on the last completed checkpoint.
恢复用于系统崩溃后把数据库带到事务一致的状态，这将准确的反应已提交的事务。恢复使用可靠的日志，这些日志是磁盘上的，保存有最近一次检查点的信息。当数据库创建时产生一个检查点，其它的将会在后面创建，因此恢复根据最后的完整检查点。
As part of the checkpoint operation, the end-of-the-system log on disk is noted before the database image is checkpointed; this becomes the "begin-recovery point" for this checkpoint as soon as the checkpoint has completed. All updates described by log records preceding this point are guaranteed to be reflected in the checkpointed database image. After initializing the ATT and transaction undo logs with the copy of the ATT and undo logs stored in the most recent checkpoint, restart recovery loads the database image and sets dpt to zero. It then "rolls forward" the portion of the system log following the begin-recovery point by applying all redo log records to the checkpoint image. (Appropriate pages in dpt are set to dirty for each log record.) During the application of redo log records, any actions necessary are taken to keep the checkpointed image of the ATT consistent with the log applied so far. These actions mirror those taken during normal processing. For example, when an operation commit log record is encountered, lower-level log records in the transaction's undo log for the operation are replaced by a higher-level undo description.
作为检查点操作的一部分，磁盘上的end-of-the-system日志标识在数据库映象被执行检查点前。在检查点操作完成后这些点将成为“开始恢复点“。在这点前日志记录中所有更新的描述保证反应被检查的数据库映象。在初始化ATT表，并用保存在ATT和多数最近检查点中的UNDO日志进行UNDO后，重起恢复过程，并把dpt清0。然后，通过向检查点映象应用日志中所有REDO日志记录把系统日志位置前滚到开始恢复点。（对每个记录dpt中对应页会变脏）。在应用REDO日志记录过程中，任何必须的动作被用于保证ATT的检查点映象与已应用的日志相一致。这些动作映象在普通进程中进行，如，当一个操作提交日志记录时，ATT事务表中的低层UNDO日志记录被高层的描述所代替。
As soon as all the redo log records have been applied, the active transactions are rolled back. To do this, all completed operations that have been invoked directly by the transaction or have been directly invoked by an incomplete operation have to be rolled back. However, the order in which operations of different transactions are rolled back is very important, to ensure that an undo at level Li sees data structures that are consistent.7 First, all operations (across all transactions) at L0 that must be rolled back are rolled back, followed by all operations at level L1, then L2, and so on.
当所有的REDO日志完成后，活动事务被回滚。为了实现，所有直接被事务调用的或被未完成操作调用的已完成的操作，必须回滚。然而，为了保证在Li层的UNDO看到的数据结构是一致的，不同事务中操作的回滚顺序很是重要。首先，在L0层所有要回滚的操作（穿越所有事务）被回滚，然后是在L1,层的操作，然后是L2,层，依此类推。
| | 无双 回复于：2003-07-01 22:49:41
| 4 FAULT TOLERANCE
This section presents techniques other than those provided directly by transaction management for fault-tolerant programming in Dalí. These techniques help cope with process failure scenarios. The first and second techniques help detect and recover from user programs with "stray pointers, " which might corrupt persistent data stored in shared memory. The third technique returns the system to a fully available state if a process dies with transactions in progress.
本章介绍DALI中由事务管理器直接提供的容错性程序设计技术。这些技术用于应付进程失败情况。第一个和第二个技术帮助检测和恢复有错误指针的用户程序，这种程序将会破坏共识内存中的持久数据。第三个技术在一个事务正在处理时如果进程死亡，那么要把系统带到一个完全可用的状态。
| | 无双 回复于：2003-07-01 22:50:00
| 4．1 Protection from Bad Writes
The direct access principle of Dalí implies that at least some user application code will be linked directly with Dalí libraries to access the data stored in the database through shared memory. This scenario brings with it the inevitable[不可避免的, 必然的] possibility that an application error will lead to "bad writes" through uninitialized or corrupt[误用的] pointers, which can cause persistent data to become corrupted. Dalí provides two mechanismsmemory protection and code wordsto minimize the probability that such errors will cause this problem.
DALI的直接访问定理意味着一些用户程序代码将通过与DALI库相连接，来访问共享内存中数据库的数据。这种情况不可避免的使数据库可能会被错误的应用程序“错误写”，通过未初始化的指针或是误用的指针。这种情况会把一致的数据变成错误的。Dalí提供两种机制来减少这种错误出现的可能性，这两种方法是内存保护和关键字。
Memory protection. Applications that want to prevent corruption from stray pointers can map a database file in a special protected mode. Dalí uses the mprotect system call to disable the updates by a particular process to a protected database file. Before a page is updated, the page is unprotected. At the end of the transaction, all the unprotected pages are reprotected. An erroneous update would probably try to update a protected page, resulting in a protection violation. Although this scheme detects erroneous writes immediately and the writes can be traced to their source using a debugger, the system calls used by this scheme decrease performance significantly. As a result, this scheme is more beneficial for use in debugging applications and for read-only databases or databases with low update rates.
内存保护。为了防止被错误的指针破坏，应用程序可以把数据文件映射到一个特殊的保护状态。Dalí使用mprotect系统调用来禁止特殊进程对一个受保护的数据库的更新。在一个页面更新前，页面是未保护的，事务结束后，所有未保护的页面被重保护。当一个错误的更新企图更新一个受保护的页面时，会产生一个违反保护的结果。虽然这种机制可以直接检测到错误写，并且写的代码可以通过调试器检测到，但是它显著降低了数据库的性能。因此，这种机制对调试应用程序代码、只读性数据库、低写比率的数据库更为有利。
Code words. An alternate technique for bad write detection is to associate a logical parity word, or code word, with each page of data. Whenever data is updated using valid Dalí system calls, the code word is updated accordingly. An erroneous write will update only the physical data and not the code word. We then use the strategy of protecting the checkpoint image on disk. Before a page is written to a checkpoint, its contents are verified against the code word for that page. If a mismatch is detected, access to that database is restricted to read-only while the physical image is recovered from the last checkpoint (in-progress transactions are aborted).
代码字。一个替换错误写检测的技术与每个页面数据的逻辑奇偶字，也称为关键字相关。当数据使用合法的DALI系统调用更新数据时，关键字也会因此而更新。一个错误写将只会更新物理数据而不会更新关键字。因此我们可以使用策略保护磁盘上的检查点映象。在页面被写到磁盘上前，它包含的关键字将会被检验。如果不匹配，那么在数据库从上次检查点恢复完成前，对数据库的访问将会是只读的，正在进程的事务也会退出。
Our current implementation of code words, based on page-level latching, is as follows. Each page has an associated latch and code word. While a page is being updated, its latch is held in shared mode by the updater. At the end, the change to the page's code word is computed from the current contents of the updated region and the contents of the region before the update took place (which is determined from the physical undo log record for the update). A short-term exclusive latch on the code word table is then obtained[获得] to apply the computed change to the code word value for the page. The latch ensures that concurrent updaters to different regions on a page do not install an incorrect value for the code word. As a page is being checkpointed, the checkpointer obtains an exclusive latch on the page long enough to copy the page and the code word associated with it to a separate area. The code word for the copy is then computed and compared with the value from the table.
我们当前实现的关键字，基于页级别的锁，如下所示。每一个页面有一个相关的锁和关键字。当一个页被更新时，它的锁被更新者以S模式持有。结束后，页面的关键字将会从更新的区域和旧区域（可以从更新产生的物理UNDO日志计算）的关键字重新计算产生。在关键字表上的一个短期排它锁保持着该页的关键字值计算的改变。锁确定对一个页不同区域的并发更新不会产生一个错误的关键字值。在一个页面被检查点时，检查点执行者获得页面的排它锁，直到把页面和它的关键字复制到一个独立的区域。关键字被计算并与表中值计算。
| | 无双 回复于：2003-07-01 22:50:27
| 4．2 Protection from Process Death
Process death may be caused if the process violates hardware protection, such as attempting to access invalid memory, or if a process is killed by an operator. A Dalí system process known as the cleanup server is primarily responsible for cleaning up dead processes.
When a dead process is uncovered, the cleanup process determines which low-level latches, if any, were held by the crashed process. Whenever a process acquires a latch, an entry is made for the process in an active process table. The cleanup process consults this table to determine if the process was holding a latch. Detecting a held latch is complicated[复杂的, 难解的] because in many machine architectures it is not possible to atomically acquire a spin-lock and register ownership. Dalí has implemented a solution for this problem, described in Bohannon et al.8 If the dead process held any system latches, the process may have left system structures in an inconsistent state because of partial updates. In these cases, the entire system is recovered as if a system crash had taken place. If the dead process did not hold any latches, the cleanup server scans the transaction table and aborts in-progress transactions owned by the dead process.
如果进程触发硬件保护的话，如企图访问非法内存，或是被操作员KILL，那么可能会产生进程死亡。因为cleanup server主要是清除死亡的进程，所以DALI的服务进程可以知道进程已死亡。
当一个死亡的进程是未保险时，清除进程要决定崩溃的进程拥有的任何低层锁。无论何时一个进程申请一个锁，在活动进程表中该进程表项都会有一个入口。清除进程检查这个表来确定该进程是不是保持一个锁。因为在许多机器的结构体系中，获得一个自旋锁并注册拥有者不可能是一个原子操作，所以检查一个持有的锁是复杂的，DALI为这个问题提供了一个解决方案，在 Bohannon et al.8中有描述。如果一个死去的进程持有任何系统锁，那么由于奇偶更新的原因，进程将会使系统结构处于一种不一致的状态。这个时候，整个系统就按系统崩溃的方法进行处理。如果死的进程没有持有任何锁，那么清除服务进程扫描事务表并死进程拥有的正在进行的事务。
| | 无双 回复于：2003-07-01 22:50:48
| 5 COLLECTIONS AND INDEXES
The storage allocator provides a low-level interface for allocating and freeing data items. Dalí also provides higher-level interfaces for grouping related data items and performing scans, as well as associative access (via indexes) on data items in a group.
存储分配器为分支的分配和释放提供一个低层的接口。和有关联的访问组中分支数据（通过索引）一样，DALI同样为组相关数据分支和进行的扫描提供高层接口。
| | 无双 回复于：2003-07-01 22:51:21
| 5．1 Heap File
The heap file is Dalí's abstraction for handling a large number of fixed-length data items. It is implemented as a thin layer on top of the power-of-two allocator. In addition to inserting and deleting data items, the heap file supports locking and an unordered scan of items. Item locks are obtained transparently when items are inserted, deleted, updated, or scanned. Scans are supported through a bit map stored in a segment header for the items in a segment.
堆文件是DALI处理大量定长数据分支的抽象。它的实现是在2 的乘方分配器上的一个薄层。除了插入和删除数据分支，堆文件支持锁和对分支进行未排序的扫描。当分支被插入、删除、更新、扫描时分支锁是显然拥有的。扫描通过分支所在段段头中的位图实现。
|
| | 无双 回复于：2003-07-01 22:51:40
| 5．2 Extendible Hash
Dalí includes a variation on extendible hashing, as described in Fagin et al.9 Figure 5 shows an overview of our structure, which matches the structure shown in Fagin et al.,9 except that the bucket concept from standard extendible hashing is broken into a hash header and a list of key entries. Each directory entry points to a hash header, and multiple directory entries can point to a single hash header. A variable i is maintained with the hash index, and the first i bits of the computed hash value for a key are used to determine the directory entry for the key (the directory itself contains 2i entries). Allowing multiple directory entries to point to the same bucket prevents too many hash headers from being allocated for directory entries to which very few key values have hashed.
DALI包括由Fagin et al.9设计的扩展HASH的一个变种。图5显示了我们结构的概要，它符合Fagin et al.9设计的结构，除了桶的概念。传统的扩展HASH中桶分为HASH头和键列表入口。每个目录入口指向HASH头，多层目录入口可以指向单个HASH头。变量I保存HASH的索引，计算出的HASH值中前I位用于键的目录入口（目录自己包含有2i个入口）。允许多个目录入口指向同一个桶是为了阻止太多的HASH头，在很少有键值可以HASH的情况下。
Searching for a key value is a fairly straightforward process; it involves searching for the key value in the list of key entries pointed to by the directory entry for the key. Insertions, however, are more complex. They may involve splitting individual key entry lists and, in certain cases, doubling the entire directory. The algorithm attempts to keep lists below a specified size threshold[开始, 开端, 极限]. To prevent interference [冲突, 干涉] between searches and inserts, a lock is maintained with each hash header. The lock is obtained in shared mode by searches traversing the list of key entries for the header, and in exclusive mode by inserters inserting into the list. Although our scheme permits a high degree of concurrency, allowing searches and inserts with different hash headers to execute concurrently, it blocks both searches and splits while a directory is being resized.
查找一个键值很少是一个前向的过程，它包括通过键的目录入口，从键入口列表中查询指向的键值。然而插入更加复杂。他们可能包括分开独立的键入口列表，并且在通常情况下，加倍目录入口。算法尝试保持以下列表在一个尺寸的极限中。为了阻止查询和插入的冲突，每个HASH头都有一个锁。当查询者遍历头部的键入口列表时，锁的拥有模式为S，当向列表中插入时，拥有模式为X。虽然我们的机制保证高度的并发性，允许对不同HASH头的查询和插入并行的执行，但在目录大小改变时它阻止查询和分裂。
| | 无双 回复于：2003-07-01 22:52:00
| 5．3 T-tree Indexes
Lehman and Carey10 proposed T-trees as a storage-efficient data structure for main memory databases. T-trees are based on AVL trees proposed by Adel'son Vel'skii and Landis.11 As in AVL trees, the height of left and right subtrees of a T-tree may differ by, at most, one. Unlike AVL trees, each node in a T-tree stores multiple key values in a sorted order rather than a single key value. To keep occupancy high, every internal node must contain a minimum number of key values (typically k&2, if k is the maximum number of keys that can be stored in a node).
Lehman and Carey10建议把T 树作为MMDB高效的存储数据结构。T树是基于Adel'son Vel'skii and Landis.11的AVL树。与在AVL树中一样，T树的左子树和右子树高多数情况下可以相差1。但和AVL树不同，T树的每个结点保存有序的多个键值而不是单个键值。为保证高利用率，每个内部节点必须包含最小数目的键值（典型的是k&2，如果K是一个节点能最大容纳的键值数）
Searching for a key value in a T-tree is a relatively straightforward process. For every node, a check is made to determine if the key value is bounded by the leftmost and the rightmost key values in the node; if this is the case, then the key value is returned if it is contained in the node. (If the key value is not returned, it is not contained in the tree.) If the key value is less than the leftmost key value, then the search moves to the left child; otherwise, the right child node is searched. The process is repeated until either the key is found or the node to be searched is null .
在T树中查找一个键值是一个相关的前向过程，对每个节点，要检查键值是不是在该节点中最左和最右的键值之间。如果是，并且包含该键值，那么直接返回键值。（如果键值没有返回，表示键值不包含在这棵树中）如果键值小于最左的键值，那么查询将对左子树进行，否则，将对右子树进行。这个过程将一直重复到键值疗找到或是查找的节点为空为止。
Insertions and deletions into the T-tree are a bit more complicated. In both cases, first a variant of the search described above is used to find the node that bounds the key value to be inserted/deleted. If there is room in the node for insertions, the key is placed in the node; otherwise, a new node is allocated for the key. For deletions, the key is deleted from the node, and the node itself is deallocated if:
向T树中插入和删除会复杂一点，在两种情况下，首先，使用与上面讨论不同的查找方法查询包含要插入/删除的键值取值范围的节点。如果在这个节点中有空间插入，那么键值写入这个节点中。否则，创建一个新的节点来保存这个键值。如果是删除，键从节点中删除，如果发生以下情况，节点自己将会被重分配空间：
The node becomes empty, or 节点变空
The number of keys in the node falls below the specified minimum and keys in the node can be accommodated in a different node. 该节点中键的数目低于键的下限值，这个节点中的键可以向其它节点调节。
Deletions from interior nodes may require keys to be moved up from lower nodes to ensure that occupancy requirements are met. In both insertions and deletions, allocation and deallocation of a node may unbalance the tree, making it necessary to perform rotations (RR, RL, LL, LR), as described in Lehman and Carey.10
删除内部节点时，为了保证利用率，可能会把键从低层的节点中向上移。在插入或者是删除时，节点的分配和再分配可能会导致树的不平衡，因此要进行适当的旋转(RR, RL, LL, LR)，这和Lehman and Carey.10讨论的一样。
Our T-tree implementation supports next-key locking12 to avoid the phantom phenomenon. It also provides high concurrency by requiring operations on the T-tree to obtain a T-tree latch only for the duration of the operation, not the transaction. Insertions and deletions obtain the latch in X mode, while search operations obtain the latch in S mode.
我们的平衡树支持下一键锁定，这样可以避免幻象。通过要示对T树进行的操作要操作（而不是事务）期间必须拥有一个T树锁，它同样提供高并发性，插入和删除拥有X模式的锁，查询操作拥有S模式的锁。
| | 无双 回复于：2003-07-01 22:52:15
| 6 DALI RELATIONAL MANAGER
The Dalí relational manager is a C++ class library interface to a relational system. Access to data is through C++ language classes, corresponding to such tools as tables, iterators, and search criteria, with Structured Query Language (SQL) support limited to data definition statements声明. Schema information is stored in tables, and limited views (project select joins) are allowed. Indexes may be created on arbitrary subsets of the attributes in a table. The Dalí relational manager also supports referential integrity (foreign key constraints), null values, and navigation through interators over a single table. A conjunctive query may be specified for the iterator[重申, 重述], and automatic index selection is performed.
DALI关系管理器是C++类型的关系管理器库接口，访问数据通过C++语言类，相应的这些工具如表、迭代器，和带有SQL支持的对数据定义声明的查询标准。计划信息保存在表中，有限的视图（project select joins）也允许，索引可以在表属性的任意子集创建。DALI关系管理器同样支持参考完整性（外键约束），空值，还有通过对interator<迭代器？>单表进行导航。一个连接的查询可以为一个迭代器指定，自动索引选择也是允许的。
The one extension to the relational model is its ability to store intertable joins in the schema. From one open iterator, a new iterator on the matching tuples in the other table may be opened easily. As an option, physical information (pointers) can be stored to represent the join relationship, leading to underlying pointer list structures similar to a network database. This last feature enables the relational manager to perform high-speed navigation, which competes with object-oriented models without requiring explicit pointer types.
关系模型的一个扩展是它可以保存一个加入计划折内部表。从一个开放的迭代器中，建立在其它表的tuples上的一个新的迭代器可以容易的打开。作为一个选项，物理信息（指针）可以为了表现加入关系而保存，这将导致与网络数据库一样的基本指针列表。最后一个特征使关系管理器能执行高速导航，与面向对象模型相比不需要直接的指针类型。
| | 无双 回复于：2003-07-01 22:52:30
| 7 CONCLUSION
In this paper, we presented an overview of the architecture of the Dalí main memory storage manager. To our knowledge, Dalí contains the only explicit implementation of multilevel recovery for main memory, and one of very few for disk-based systems. We described Dalí's storage architecture, the implementation of the T-tree and extendible hash index structures, its extensive features for detecting bad writes by processes, and the procedure for recovering from process failure.
在本论文中，我们介绍一对DALI内存数据库存储管理器。据我们了解，DALI是唯一包含清楚的多层恢复机制的MMDB，这对磁盘数据库来说也是少数。我们讨论了DALI的存储管理器结构，还有T树和HASH索引结构的实现，以及它在进程的错误写检测、从进程失败过程中恢复的广大的特性。
We are working on a number of additional features for the Dalí storage manager in its product form as DataBlitz. These include support for hot spares that can take over processing if the primary server fails; nonblocking read transactions that use sophisticated version-based concurrency control schemes; and on-line schema evolution, which will enable attributes to be dropped/added to a relation as access to the relation continues.
我们同时也在通过使用DALI存储管理器产品DataBlitz的其它特性。这些包括对热备份的支持，热备份可以在主服务器失败时接管进程，对使用复杂的基于版本的并发箜制机制可以非阻塞的读事务。还有在线计划演变，这允许不中断关系的情况下增加/减少关系。
| | 无双 回复于：2003-07-01 22:52:46
| 7．1 Acknowledgments
Dalí represents a substantial effort, during several years, by many people. We would like to thank H. V. Jagadish, of AT&T, for significant early contributions to Dalí. Dan Lieuwen of Bell Labs also made significant early contributions and has offered several valuable suggestions concerning process failure and the organization of the heap file. S. Seshadri, a consultant to Lucent Technologies when this work was performed and a member of the faculty at the Indian Institute of Technology in Bombay, helped develop the T-tree concurrency algorithm and the relational interface. Steve Coomer of Network Systems suggested the strategy of using code words to protect checkpoint images on disk. The design for the structure used in the coalescing allocator was suggested by Dennis Leinbaugh, also of Network Systems. We would also like to thank Jerry Baulier of Lucent's Advanced Technologies, project manager for DataBlitz, for his support of the project. Many other talented individuals contributed to the design and implementation of specific systems in Dalí during the last three years, including Sandeep Joshi, Mike Nemeth, and James Parker of Lucent Technologies, and Soumya Chakraborty, Ajay Deshpande, Sadanand Gogate, Chandra Gupta, Amit Khivesara, Sekhara Muddana, and Yogesh Wagle, current or former contractors at Lucent.
THE ARCHITECTURE OF THE DALI MAIN MEMORY STORAGE MANAGER
Figure 1.
Architecture of the Dalí system.
Figure 2.
Layers of abstraction in the Dalí system.
Figure 3.
Segments and chunks.
Figure 4.
Overview of recovery structures.
Figure 5.
Extendible hashing in the Dalí system.
| | 无双 回复于：2003-07-01 22:53:07
| 9 Dali: Motivation and Principles
Motivation
The initial interest in a main memory storage manager arose out of research into recovery techniques for main memory databases. While the first prototype was being created, however, it was realized that a significant need existed for storage management tools within AT&T.
在内存数据库存储管理器方面最初的兴趣是对我们MMDB恢复机制的研究。然而，当第一个原型被创建后，它被创建成一个AT—T的存储管理器产品，并有明显的存在需求：
To provide a high performance transaction processing micro-kernel
supporting main-memory database platforms and performance-critical
applications throughout AT&T.
为了提供一个高性能的事务模型的微内核，在整个AT&T中支持MMDB平台和严格环境下的应用。
| | 无双 回复于：2003-07-01 22:53:25
| Principles
This remainder of this page presents principles which have guided Dali's development.
这篇论文讨论了指导MMDB开发的定理。
Main Memory Assumption 内存假设
While Dali can handle databases larger than main memory, it is designed and optimized for the case where all data fits in RAM. Compared to a disk-based database which has sufficient main memory for all its data, Dali uses less space to store the data and provides faster access .
DALI可以处理比主存大的数据库，然而它是为所有数据保存在RAM中设计和优化的。与有足够内存保存所有数据到内存的磁盘数据库相比，DALI使用更少的内存和更快的数据访问。
Transactional Model 事务模型
Much of Dali is based on a transaction model, with the normal ACID properties (Atomicity, Consistency一, Isolation独立性, Durability持久性). Disk storage is used to ensure Durability through logging and checkpointing. (However, normal data access need not access the disk.) DALI的许多方面基于ACID[原子性，一致性，独立性，持久性]事务模型，磁盘存储器通过日志和检查点保证数据的持久性（然而，通常的数据访问不需要访问磁盘）
No Inter-Process Communication 没有内部通信
Modern relational databases provide data to the application only through an SQL interface. This interface typically uses some form of remote procedure call to an SQL server process, which returns the data or performs the update. While efficient for bulk[大小, 体积, 大批, 大多数, 散装] activities, small transactions doing point-lookups and updates pay an enormous[巨大] cost for each access due to this IPC. In Dali, a user process contacts the server only twice: once at startup and again when it stops using the database. To avoid the IPC, data is stored in shared memory , and most Dali code is directly linked with the application.
现代的关系型数据库仅通过SQL接口向应用程序提供数据，这些接口通常使用一些形式的远程过程调用调用SQL服务器进程，从而查询数据或是进行更新。在大的活动有效的执行时，小事务却因为进行指针查找和更新访问会花费巨大的开支。在DALI，一个用户进程仅与服务器连接两次：一次在开始，另一次是在它停止使用数据库时。多类DALI代码是直接与用户程序相连接LINK
Direct Access To Data 直接访问数据
In most databases, one or more data copies are required before a user can directly access the data. Dali always allows the option of direct access to data, avoiding the cost of the copy.
在多数数据库中，在用户可以直接访问数据前需要一个或多个数据复本。DALI总是允许直接访问数据，避免复制的代价。
Fault Tolerance 容错性
While access to data via shared memory is inherently risky[危险], Dali provides many features to mitigate[.减轻] his risk. Different features are specifically designed to protect against System Faliure, Process Death, and Application Errors.
访问共享内存中的数据有因有的危险性，DALI提供许多特征来减轻这种危险性。不同的特征为阻止系统失败、进程死亡、应用程序错误而设计。
Real Time Performance 实时性能
Dali's maintenance[维护, 保持, 生活费用, 扶养] activities have little or no interference [.冲突, 干涉]with on-going transaction processing. Coupled with the lack of disk activity, this provides high performance with tight bounds.
DALI保持活动与正在进行的事务进程没有冲突。加上没有磁盘活动，可以提供更严格的性能上升。
Toolkit Approach 工具箱
Dali is designed to allow the application to turn off features that it doesn't need, and avoid paying the performance penalty those features entail. For example, one application may need to access data concurrently in shared memory, but have no need to recover in case of a system crash. This application should not pay the cost of logging for recovery. Another application may need recovery, but be single threaded. This application should not pay the cost of locking.
在DALI设计中，允许应用程序关闭它不需要的特征，避免在这些方面浪费性能。例如，一个应用程序可能要一致的访问共享内存中的数据，但在系统崩溃时不需要恢复它。这个应用程序不用在日志和恢复中浪费性能。另一个应用程序可能要恢复，但是是单线程的，这个程序也不用为锁浪费性能。
Multiple Interface Levels 多接口层
Dali provides different interface levels which trade off simplicity for flexibility[弹性, 适应性, 机动性, 挠性] and performance. At the lowest level, memory is allocated directly by the application and it is responsible[有责任的, 可靠的, 可依赖的, 负责的] for designing a locking strategy[策略] and making calls to Dali to perform all logging. At higher levels, the interface becomes more powerful, providing abstractions of collections and indices. The newest and highest level of these interfaces is the Dali Relational Manager.
DALI提供不同接口层，可交替使用简单的有弹性的，或是性能好的。在低层中，内在直接被应用程序分配，对设计一个锁策略和调用DALI接口执行所有日志时，它是可靠的。在高层，接口变得更强大，提供收集和索引的接口。最新的和最高的接口是DALI的关系管理器。
Build A Database Manager 创建一个数据库管理器
If a database management system is drawn showing layers of functionality, the center is typically memory management, transaction processing and indexing. These are exactly the features provided by Dali. By using these features, a main memory database can be built far more quickly and easily than starting from scratch. An object-oriented database system, which is built on top of Dali is MM-Ode<Dali>.
如果一个计划中的数据管理系统显示功能层，中心仍是典型的内存管理系统，事务处理和索引。这正是DALI提供的特征。通过使用这些特征，一个内存数据库可以被更快创建并比开始乱写更容易。一个面向对象系统，在DALI上的是MM-Ode<Dali>.
Build A High-Perfomance Application 创建一个高性能应用
For applications which absolutely require high performance, Dali's lower level interfaces allow custom data structures and concurrency control to be crafted by the application developer. While these interfaces are more complex than the higher levels, they compare very well with creating an application-specific concurrency control and recovery system.
对那些完全需要高性能的应用，DALI的低层接口允许程序开发者开发通用的数据结构和并发控制。虽然这些接口比高层接口更复杂，他们在创建特殊应用的并发控制的恢复系统时仍然表现得很好。
| | 无双 回复于：2003-07-01 22:55:43
| MMDB比内存数据库要简单多
如MMDB不需要为了提高IO性能而使用缓存管理
以及指针混写也不用 因为记录都在内存中
但是里面的许多原理都是公用的
如树等
另外内存的高效分配与管理方面也是一个需要深入研究的方面
| | loader99 回复于：2003-07-02 15:29:41
| 据我所知. 现在数据库学术界一个重要的研究课题就是在大容量内寸(G/T)的环境中的树结构及其相应的算法.
因为以前和目前的树结构和算法的设计多针对优化I/O调度(内寸不够).
| | 无双 回复于：2003-07-02 18:19:19
| 这是一个方面
主要是对大二进制数据的存储进行优化
以前在这方面需求不大
现在许多媒体应用如网络电影等都有这个需求
另一个可能就是对象数据库了吧
就是直接按OO方法设计数据库
但这方面一直没有很关心所以不是注意
| |
|
关闭本页 |
|
|
|
|
|
|
|
| | | | | | | |
