Responsibilities of the Information Store

The primary responsibility of the Exchange store is to maintain Exchange databases and manage transactions in order to provide other services and messaging clients with access to mailboxes and public folders. The Exchange store is additionally responsible for space management (the management of the physical database files) and buffer management (the management of the Store.exe process memory usage).

Interactivity with other Exchange Services

The Exchange store works in tandem with a number of other services to perform typical Exchange operations. The following table provides a summary of the services essential to typical Exchange operations. Note that the services that are available on a particular Exchange server depend on its configuration.

Services essential to the operations of Exchange Server 2003

Space Management

The two types of space in a database file are owned space and available space. Every table, index, and long-value B-tree has its own list of owned and available pages. Available space is a list of pages that can be used to store new data. Available space is always a subset of owned space.

• Owned space   ESE organizes owned space in a three-level hierarchy. The levels are database root, tables, and indexes and long-values. The database root owns all the space in the database. Tables request chunks of space, which they then own (as does the database root). Index and long-value trees request space from the table that in turn owns a chunk of space from the database root. To reduce the number of requests and to avoid fragmenting the space, requests for more space are made in chunks (normally 16 pages or 64 KB).

• Available space   Available space is slightly different. A page can be available at the database root, at the table level, or as an index or long-value. A page is available only at one level.

Database Defragmentation

Defragmentation is the process whereby ESE traverses the pages at the bottom (the leaf pages) of each B-tree database. ESE determines whether it can merge strings of adjacent pages to a single page. This frees up pages and returns them to the table's available space. The locality and contiguity of related pages inside the database file is maximized where possible.

Defragmentation can be performed in two modes:

• Online defragmentation   This runs as part of system maintenance, which by default is between 1:00 A.M. and 6:00 A.M. If ESE can't complete a full pass through the database, it notes where it stopped and resumes from this point when the next Exchange store maintenance window occurs.

  Online defragmentation has the following limitations:

  • Free space inside the database file (.edb) is not returned to the file system. Instead, after online defragmentation completes, the Microsoft Exchange Information Store service logs an event in the application event log (Event ID 1221) that indicates the amount of available free database space. This free space is used if needed, before the physical database file grows.

  • Available space in a database is in the form of a list of pages that can be used to store new data. The available space is called a space tree. The space tree is held as a B-tree that is searched whenever a block of new data must be added to the database. Space trees are not removed during online defragmentation and remain fragmented until an offline defragmentation is performed.

  • Deleted column IDs and long-value IDs are not reclaimed.

  • Secondary indexes are rearranged but not rebuilt (if there is index corruption, it is not repaired).

  • Vertical merge is not supported in the database file (.edb) (tree levels are not collapsed).

• Offline defragmentation   This is a manual process that is accomplished by an administrator running the ESEUTIL utility against their databases. Eseutil.exe is a command-line utility located in the \Program Files\Exchsrvr\Bin directory.

  Note

  If a mailbox or public folder store is mounted while you try to use ESEUTIL.exe to compact its databases, the error code -1032 (JET_errFileAccessDenied) is returned. Remember to perform a full backup both before and after defragmenting databases offline.

Buffer Management

A fundamental design goal of ESE is to avoid disk access. To do this, ESE uses a comprehensive buffer manager. The buffer manager performs the following two jobs:

• It decides how much memory the buffer cache should use. This is accomplished using an internal feature called Dynamic Buffer Allocation (DBA).

• It decides which pages should remain in the buffer cache. An algorithm named LRU-K makes this decision.

Dynamic Buffer Allocation

Dynamic buffer allocation (DBA), a feature which was first introduced in Exchange Server 5.5, has become a major factor in Microsoft Exchange Information Store service memory usage. ESE monitors the state of the cache continuously. It verifies the system's requirements and makes adjustments to the cache size when necessary.

Dynamic buffer allocation uses four rules to govern how large or small the cache should be:

• The more memory available, the faster the Exchange store's working set grows.

• The more cache memory, the faster the Exchange store's working set shrinks.

• The higher the memory load, the faster the Exchange store's working set grows.

• The higher the available memory load, the faster the Exchange store's working set shrinks.

DBA uses a patented formula to determine how the buffer cache size should grow or shrink over time.

The LRU-K Replacement Algorithm

DBA manages the size of the buffer. With time, the buffer fills with cached database pages. To make room for more pages, earlier pages must be removed from the cache. DBA provides a mechanism to determine which pages stay in the cache. Traditionally, database systems use the least recently used (LRU) algorithm, first described by Denning in 1968 (P. J. Denning, Resource Allocation In Multiprocess Computer Systems, Massachusetts Institute of Technology, Cambridge, MA, 1968). When buffer space is needed, LRU drops from the memory buffer the page that has not been accessed for the longest time.

However, the LRU algorithm has a flaw. It decides what page to drop from memory based only on the time of last reference. Specifically, LRU is unable to differentiate between pages that have relatively frequent references and pages that have very infrequent references. For example, a page may have been accessed 100 times, followed by another page, accessed only a single time. According to LRU, the page accessed 100 times would be dropped, regardless of the fact that this page is more popular than the other page that was only accessed once.

To optimize database disk buffering, the LRU-K algorithm was introduced in 1993 (Elizabeth J. O'Neil, Patrick E. O'Neil, Gerhard Weikum, The LRU-K Page Replacement Algorithm For Database Disk Buffering. SIGMOD Conference 1993). This algorithm surpasses conventional buffering algorithms by discriminating between frequently and infrequently referenced pages. Exchange Server 2003 uses the LRU-K algorithm.

The LRU-K algorithm keeps track of the times of the last K references to memory pages (ESE sets the default value of K to 2) and uses this statistical information to rank-order the pages according to their expected future behavior. Based on this statistical information, ESE can decide which memory-resident page to drop in order to make room for a newly accessed page that must be read into memory. Because statistical information about referenced pages is constantly collected, the LRU-K algorithm adapts in real time to changing patterns of access. This algorithm is fairly simple and incurs little bookkeeping overhead. It uses the last two or more references, generally the last K references, (where K is greater than or equal to 2) for each page to decide which page should be dropped.