LRU 和桶之间的关系

zengmuansha

以下是描述LRU列表 管理数据缓存块 和查找空闲和命中的机制. 好像两种机制各谈各的, 却都是管理同一个对象!

Organization of the Database Buffer Cache 8.2.4.1
The buffers in the cache are organized in two lists: the write list and the least recently used (LRU) list. The write list holds dirty buffers, which contain data that has been modified but has not yet been written to disk. The LRU list holds free buffers, pinned buffers, and dirty buffers that have not yet been moved to the write list. Free buffers do not contain any useful data and are available for use. Pinned buffers are currently being accessed.

When an Oracle process accesses a buffer, the process moves the buffer to the most recently used (MRU) end of the LRU list. As more buffers are continually moved to the MRU end of the LRU list, dirty buffers age toward the LRU end of the LRU list.
　
The first time an Oracle user process requires a particular piece of data, it searches for the data in the database buffer cache. If the process finds the data already in the cache (a cache hit), it can read the data directly from memory. If the process cannot find the data in the cache (a cache miss), it must copy the data block from a datafile on disk into a buffer in the cache before accessing the data. Accessing data through a cache hit is faster than data access through a cache miss.
　
Before reading a data block into the cache, the process must first find a free buffer. The process searches the LRU list, starting at the least recently used end of the list. The process searches either until it finds a free buffer or until it has searched the threshold limit of buffers.


If the user process finds a dirty buffer as it searches the LRU list, it moves that buffer to the write list and continues to search. When the process finds a free buffer, it reads the data block from disk into the buffer and moves the buffer to the MRU end of the LRU list.

If an Oracle user process searches the threshold limit of buffers without finding a free buffer, the process stops searching the LRU list and signals the DBW0 background process to write some of the dirty buffers to disk.
　


数据缓存区的管理方式
数据缓存区（database buffer cache）中的缓冲区（buffer）通过两个列表管理：待写列表（write list）和最近最少使用列表（least recently used（LRU）list）。待写列表中记录的是脏缓冲区（dirty buffer），即其中数据已被修改且尚未写入磁盘的缓冲区。最近最少使用列表中记录的是可用缓冲区（free buffer），锁定缓冲区（pinned buffer），及还没被移入待写列表的脏缓冲区。可用缓冲区内的数据无需继续保留，可以用于存储新数据。而锁定缓冲区是正在被访问的缓冲区。
　
当某个 Oracle 进程访问一块缓冲区时，就会将其移动到 LRU 列表的最近使用（most recently used，MRU）端。随着更多被访问的缓冲区移动到 LRU 列表的 MRU 端，较早前被访问过的脏缓冲区就会逐渐向 LRU 列表的 LRU 端移动。
　
当 Oracle 的用户进程（user process）首次查询某块数据时，她将首先在数据缓存区内进行搜索。如果用户进程在数据缓存区内找到了所需的数据（称为缓存命中（cache hit）），就可以直接从内存中访问数据。如果用户进程不能在数据缓存区中找到所需的数据（称为缓存失效（cache miss）），则需要从磁盘中的数据文件里将相应的数据块复制到缓存中才能进行访问。缓存命中时的数据访问速度远远大于缓存失效时的速度。

　 当用户进程在对 LRU 列表的搜索过程中遇到脏缓冲区时，她会先将此类缓冲区移入待写列表，之后再继续搜索。当用户进程找到了可用缓冲区时，就会将数据块从磁盘写入缓冲区，并将此缓冲区移到 LRU 列表的 MRU 端。

　 用户进程将数据块读入数据缓存区之前首先要准备好可用缓冲区。用户进程从 LRU 列表的 LRU 端开始对其进行搜索。这个搜索过程将一直持续，直到找到可用缓冲区或达到缓存搜索操作的预设限定值为止。





对于Buffer cache管理而言 oracle所需要 解决的问题包括 几个：

1.  如何 快速定位一个data buffer header，因为 Buffer cache中的 data buffer header 是非常多的 ， 若为了找一个data buffer header 而去 对所有的 buffer header都 扫描一遍 ，那将是非常低效的。


举个例子来说 服务进程要 有读取 datafile 5 block 10的需求 ， 这个时候 难道服务进程 一开始就知道 data file 5 的 block 10在   是不是在 Buffer cache中，  在Buffer cache中的哪里？　这些信息　Server process都是不知道的。

如果 data buffer header被 使用 普通的双向链表组织，那么 如果要确定一个 data buffer是否在 Buffer Cache中，那么需要把 这个双向链表上所有的buffer header都查看一遍， 这是十分低效的。

2.  对 data buffer header 高效的并发管理 ，避免出现 争用。



为了 实现 高效管理 data buffer header的目的 ， oracle 使用 hash buckets的结构来 组织 data buffer header， 通过对 data buffer header 的 不同 rdba 和 class 做HASH 算法 来实现 对 buffer header的高效管理，  通俗来说 HASH做的就是一件事  ，  例如 data file 4 上的 block 18 和 block 19是 应用经常要访问的热快， 经过HASH算法之后 这2个块 就不会落在同一个HASH Buckets中，这样避免了对 同一条hash chain的争用。   


oracle又通过  hash chains( cache buffer chain) 将一个bucket 上的buffer header串起来 ，  注意 同一个data block在oracle中可能会有 多个buffer ， 分别对应为一个 current block 和可能的多个 cr block， 这些block都同一条 cache buffer chains上。


为了实现 对cache buffer chains的并发控制 需要用到 latch来管理 ， 所以会有 cache buffer chains latch。


CBC 的latch管理是 Buffer cache Internal的主要部分，值得研究 但是并非 一段文字所能全部描述。

你也可以参考下面 这个图示：

Maclean Liu(刘相兵

你的具体问题是什么？

zengmuansha

Maclean Liu(刘相兵 发表于 2013-2-19 15:49
你的具体问题是什么？

我问LRU 和 桶管理 buffer  之间应该有关联吧

LRU查找数据块是否在内存中 要扫描整个列表. 而桶管理挂着很多缓存冲块,定位非常方便的.

Maclean Liu(刘相兵

我问LRU 和 桶管理 buffer  之间应该有关联吧

===》仔仔细细看下这个大图吧！！

zengmuansha

晕! 这样的数据结构  LRU 要访问 BUFFER HEADER 需要获得 HASH LATCH 锁 ?
比如要找某个块是否在内存中 是从头遍历LRU尾 , 还是计算HASH值, 获得LATCH,进入BUCKET HASH CHAIN链表 找到对应的块?

wind

zengmuansha 发表于 2013-2-20 10:06
晕! 这样的数据结构  LRU 要访问 BUFFER HEADER 需要获得 HASH LATCH 锁 ?
比如要找某个块是否在内存中 是 ...

我的理解是计算HASH值, 获得LATCH,进入BUCKET HASH CHAIN链表 找到对应的块。

lru链表是来管理空闲，或者是备用块~~的链表


另外，在内存遍历很快的，不需要太担心。

zengmuansha

wind 发表于 2013-2-20 15:22
我的理解是计算HASH值, 获得LATCH,进入BUCKET HASH CHAIN链表 找到对应的块。

lru链表是来管理空闲，或 ...

LRU 是什么结构?  concept 上说是 The buffers in the cache are organized in two lists: the write list and the least recently used (LRU) list

LIST 是数组结构 还是 指针链表结构  在大学数据结构里介绍?

另外 LRU是独立的 结构  还是 内嵌到 BUCKET 关联的 CHAINS?

比如说 有个 LRU 头部和尾部指针 指向 BUCKET CHAINS

BUCKET CHAINS 的是双向指针链表  

wind

zengmuansha 发表于 2013-2-21 09:37
LRU 是什么结构?  concept 上说是 The buffers in the cache are organized in two lists: the write lis ...

lru也是双向指针链表。我的理解他是独立的。从图上看也是这样的。


另外，英文原文我没有见过“bucket chain”的说法，我觉得cbc (cache buffers chains)是正确的说法，求证。

zengmuansha

wind 发表于 2013-2-23 21:20
lru也是双向指针链表。我的理解他是独立的。从图上看也是这样的。

按照刘大 提供的图表  LRU 不是独立的  LRU的两端确实是独立的,好比大学里的指针头和尾两部分.
而它的身体部分 指向的是 cache buffers chains 中的 buffer hadler

buffer handler  结构体
struct buffer handler
{

chains prev point,
chains next point,
lru prev point
lru next point
buffer addres
}

wind

zengmuansha 发表于 2013-2-25 11:13
按照刘大 提供的图表  LRU 不是独立的  LRU的两端确实是独立的,好比大学里的指针头和尾两部分.
而它的身 ...

这段结构体哪里抄来的？: D