CMU15-721-Lecture02笔记

发表于2022-11-05更新于2021-10-05阅读次数

Lec-02 In-memory Databases

video

Disk-oriented DBMS(面向磁盘的数据库)

  • 数据主要是在非易失性存储器中(HDD,SSD),以页或者帧(Page or Frame)为单位做存储

  • 使用在内存中的**缓存池(Buffer Pool)**来将磁盘数据导入内存并在内存中处理，缓存来自磁盘的page

  • 槽(slot) , 数据库的数据存储结构是通过表空间（table space）->段(segment)->区（或者簇extends)->页（page)进行管理, 其中页是最小管理单元，而数据库表的记录在页内保持有序的方法就是槽(slot)管理，以MySQL为例分析：

    • Innodb是多条记录对应一个槽，而槽的作用就是用来在页面内进行数据搜索的，因为查找一条数据时，是用B+tree来保证通过树形结构找到一个记录所在的页，而在页内部真正找到这条记录是通过槽来完成的

    • 在页内部，Innodb划分出一个区域比如10byte，作为槽的区域（当然槽的区域根据使用的大小是可以变化的），一个槽占用2byte。那么现在可以将这个槽看作是长度大小为5的数组。

    • 当我们将一条数据记录写入数据库时，通过数据库的Innodb最终决定写入在这个页内。那么写在这个页的哪里呢？形象的理解就是这个页，就相当于一张A4纸；数据记录就是一条信息，我们写的时候就是从上到下，从左至右的方法去写。Innodb的写入方式基本上也是这样的写入方式，但是这其中有很多问题需要数据库去解决。其中就是写入后数据记录的顺序问题。

    • 模拟数据的写入过程：
      1.写入第1条记录1，该记录在页内偏移量为120，长度为100，则slot[0]=120;
      2.写入第2条记录10，该记录在页内偏移量为220，长度为100，则slot[1]=220;
      3.写入第3条记录5，该记录在页内偏移量为320，长度为100，此时需要移动slot的内容，则slot[1]=320;slot[2]=220;

    • 这样通过 slot的有序性，就保证了写入页内的数据记录的有序性。上面说过，Innodb的槽是多条记录对应一个slot。对于innodb它页内记录通过双向链表相互联接。

      • slot[0]=120对应记录1的偏移量，而记录1有指向记录2的指针，记录2有指向记录3的指针；
      • slot[1]=420对应记录4的偏移量（这里假设每条记录长度为100），记录4有指向记录5的指针，记录5的指向记录6的指针
      • 后面的槽依次类推。slot[2]管理7，8，9三条记录；slot[3]管理10，11，12三条记录；slot[4]管理13，14，15三条记录；

Buffer Pool Issue（缓冲池）

由于引入了缓冲池，磁盘型DB完整过程如下：

  • 完整查询过程：

    1.从数据库索引中查找对应记录的Page ID和slot(数据库页的槽)，如果索引的节点没有加载到内存中，需要从磁盘中加载

    2.去页表中查询该Page是否已经加载到内存

    3.如果没有的话，从磁盘中找到该页，并且复制到缓存池的一帧中(frame)

    4.如果缓存池没有空的frame，则按一定替换原则evict某页(LRU,FIFO,CLOCK)，并且还要更新page table

    5.如果page是dirty的即被修改过，就需要把对应修改后的内容写回磁盘中

    image-20211005210919847

  • 这种架构的坏处：

    Every tuple access has to go through the buffer pool manager regardless of whether that data will always be in memory.

    无论查询元组是否在内存中都需要去buffer pool中查找

Concurrency Control Issue（并发控制）

面向磁盘的数据库假定在尝试访问没有加载到内存的数据的时候，事务会“stall(抛锚，熄火)”

当然系统为了提高性能会允许一个事务stall的时候同时执行其他事务，靠上锁来实现ACID。(原子性（atomicity，或称不可分割性）、一致性（consistency）、隔离性（isolation，又称独立性）、持久性（durability）)

锁存储在in-memory的一个hash-table，叫lock manager,避免锁数据被swap到磁盘上，All the info about lock is in memory!，所有关于锁的信息全部在内存中！

Logging & Recovery Issue （日志与恢复）

  • 事务提交前，把修改写入Write-Ahead-Log(WAL)，WAL包含undo log 和 redo log
  • 每一个log entry（日志项）包含事务修改前后数据的镜像
  • The DBMS flushes WAL pages to disk separately from corresponding modified database pages, so it takes extra work to keep track of what log record is responsible for what page，DBMS将WAL页面从相应的修改过的数据库页面分别刷新到磁盘，因此需要额外的工作来跟踪日志记录负责哪个页面
  • 在事务提交之前，必须将所有修改刷新到WAL。
  • 需要维护log record是负责哪一个page的信息（利用LSN Log Sequence Number）

开销比较

如果不考虑disk flushing,面向磁盘数据库开销主要花费在：

BUFFER POOL 34%

LATCHING 14% (隔离的是线程,保证并发线程操作临界资源的正确性)

LOCKING 16% (隔离的是事务，一般锁住的是数据库的表，行)

LOGGING 12%

B-TREE KEYS 16% 索引查找时间

CPU 7%

In-memory DBMS(面向内存的数据库)

背景：DRAM的发展，价格和容量足以把整个数据库的数据都存储到内存中

这时候磁盘IO不再是数据库性能的瓶颈,而需要考虑以下可以优化的性能瓶颈

  • Locking/Latching：

    • lock的对象是事务，用来锁定的是数据库中的对象，如表、页、行。并且一般lock的对象仅在事务commit或rollback后进行释放（不同事务隔离级别释放的时间可能不同）。此外，lock，正如在大多数数据库中一样，是有死锁机制的。
    • latch一般称为闩锁（轻量级锁），因为其要求锁定的时间必须非常短。

    20201207103106902

  • Cache-line misses，cache命中

  • Pointer chasing，指针追踪

  • Predicate evaluation，谓词运算

  • Data movement and copying，数据移动和复制

  • Networking ，网络通信

因为所有数据都在内存中，因此不会存在脏页，也不需要维护undo log信息，也不需要LSN机制

与面向磁盘数据库的一些不同

  • Data Organization

    1.从索引Index中查找数据指针所在的Block ID与Offset

    2.根据Block ID与Offset找到数据指针的内存地址,指针存储在Fixed-Length Data Blocks(固定长度数据块)中

    3.根据这个64-bits指针去Variable-Length Data Blocks(可变长度数据块)去寻找真正的数据

微信截图_20200426204351

  • Indexes

    In-memory DBMS并不会记录索引的更新。数据库再重启时，当所有数据加载到内存之后直接在内存中重建这个索引。

  • Query Processing

    由于数据都在内存中，随机访问的速度并不比顺序访问要差

  • Logging & Revocery

    1.仍然需要维护WAL，即修改数据库之前,把修改记录写入WAL然后同步到内存中

    2.使用组提交来提交WAL，分摊fsync系统调用的开销

    3.也可以使用更轻量级的logging策略，只存储redo信息

  • Concurrency control——提供原子性与隔离性

    在面向磁盘的数据库中，锁是存放在另外一个内存中的hash表，与数据记录本身是分开来存储的。因为记录是可能被swap到外存。

    而在IMDB中，由于数据记录一直在内存中，不会swap到外存，因此可以把记录有关的锁的信息与记录一起保存。

    所以尝试取锁的效率=尝试获得数据的效率

    瓶颈在于：多个事务同时尝试访问某个数据，只有一个事务能抢到锁

    如果用mutex实现的话性能太慢，建议用CAS来保证这里的同步

CAS

1
__sync_bool_compare_and_swap(&M, 20, 30);

当且仅当M地址代表的值等于20的时候，把M地址所在的值设为30。否则失败，因为不等于的话说明这个值肯定被别的线程修改了

并发控制

接下来的会详细讨论并发控制的一些策略：

悲观策略——2 PHASE LOCKING 两段锁协议

操作数据之前一定先抢锁

2PL解决死锁两种策略：

  • 1.死锁探测

    维护一个队列，队列存放着拿着锁的事务，一个后台线程周期性扫这个队列的事务，看哪些事务在运行，哪些stall，这就可以找到发生死锁的事务。

  • 2.死锁预防

    在分配锁之前看有没有其他事务已经拿到这把锁，如果这个事务拿不了锁：

    1）等待

    2）自杀

    3）杀死另外一个拿锁的事务

乐观策略——Timestamp Ordering 时间戳排序

操作数据不抢锁，事务提交的时候比较时间戳，以时间为序，按每个transaction的时间来排谁先执行

参考资料：CMU Database Systems - Timestamp Ordering Concurrency Control - fxjwind - 博客园 (cnblogs.com)

Basic T/O Protocol

首先每个txn(事务，Transaction)需要有一个独一无二的timestamp，这个在单机很容易实现；其次，Timestamp必须是单调递增的，最后，不同的schema会选择在不同的时间给txn打上timestamp，可能是txn刚到的时候，也可能是txn执行完的时候。

txn是transaction的简写，ts为timestamp

每一个事务txn都会分配一个时间戳，每一个记录的头部维护上一次事务操作的时间戳。然后事务对时间戳进行操作的时候，比较现在事务的时间戳与记录头部当前的时间戳。

img

以课程案列，首先，给每个object加上读时间戳和写时间戳，表示最后一次读写该对象的时间，如图，对象A,B分别加上读写时间戳，均为10000，然后对图中事务txn的每个读写操作进行时间戳比对

image-20211005214323198
  • 读Object操作：拿当前事务ts和Object的写ts比较，如果Object的写ts比较新，那么读需要abort，因为，你不能读一个未来的值
image-20211005214627964

可以看到，案例txn中READ(A)首先将本事务ts=10001对象A的写ts=10000比较，本txn的ts更新，因此READ(A)操作合法，并将对象A的读时间戳更新为max(R−ts(A),ts(txn))max(R-ts(A),ts(txn)),这里将A读ts改为10001

img image-20211005215134735

写Object操作：要同时将本txn的ts和该对象的读、写ts进行比较，比较对象写是因为你不能用过去的值覆盖未来的值，比较对象读是因为如果有未来的txn读过这个值，你就不能再更新。即事务txn的时间戳要大于对象的读和写时间戳才可以进行操作，操作后，需要更新对象的写时间戳

image-20211005215251726 img

课程案例中，假设本txn在省略号部分处理其他事情，无读写操作，此时另一个时间戳为10005的txn进行了对对象A的写操作，A的写ts修改为10005，当本txn其他事情完成，继续后续另一个的WRITE(A)操作时：

image-20211005215739487

进行ts比较，此时txn ts=10001< Object A write ts=10005，操作不合法，事务无法提交，处理失败，回滚

乐观并发控制
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
1. Read Phase: Transaction’s copy tuples accessed to private work space to ensure repeatable reads, and
keep track of read/write sets.

2. Validation Phase: When the transaction invokes COMMIT, the DBMS checks if it conflicts with other
transactions. Parallel validation means that each transaction must check the read/write set of other
transactions that are trying to validate at the same time. Each transaction has to acquire locks for its
write set records in some global order. Original OCC uses serial validation.
The DBMS can proceed with the validation in two directions:
? Backward Validation: Check whether the committing transaction intersects its read/write sets
with those of any transactions that have already committed.
? Forward Validation: Check whether the committing transaction intersects its read/write sets with
any active transactions that have not yet committed.

3. Write Phase: The DBMS propagates the changes in the transactions write set to the database and
makes them visible to other transactions’ items. As each record is updated, the transaction releases
the lock acquired during the Validation Phase

具体可以参考slides的过程

时间戳的分配策略
  • 基于互斥量：并发性能低
  • 原子加操作: CAS操作去维护一个全局计数器
  • 批量原子加操作
  • 硬件CLOCK: Intel CPU only
  • 硬件计数器: 尚未有硬件实现

并发控制的性能瓶颈

  • Lock Thrashing 锁抖动

    Each transaction waits longer to acquire locks, causing other transaction to wait longer to acquire
    locks.

    Can measure this phenomenon by removing deadlock detection/prevention overhead.

    solution： force txns to acquire locks in primary key order

  • Memory Allocation 内存分配

    Copying data on every read/write access slows down the DBMS because of contention on the memory
    controller.

    Default libc malloc is slow. Never use it

  • Timestamp Allocation 时间戳分配