DB_Reading

Posted on Edited on

存储结构

  • 磁头浮在盘片上不接触盘片（否则会出现盘片损坏）
  • remapping of bad sectors, 若出现坏块且尝试写这个坏块时，可以重映射到别的物理块。
  • 性能指标: I/O operations per second(IPOS), mean time to failure(MTTF)
  • FLASH: NOR FLASH、NAND FLASH
  • SSD are built using NAND flash
  • physical page需要定期擦除
  • hot data & cold data
  • flash translation layer
  • flash支持I/O并行请求
  • Hybird disk drives: 在磁盘中使用SSD作为cache缓存数据
  • 数据库被映射到一些操作系统管理的文件中。
  • 大多数db默认使用4到8k的block大小
  • 一个block中可能包含多个records
  • 要求records完整地包含在一个block中(即不能即包含在一个block又包含在另一个block中)，这样能加快访问数据的速度

    Fixed-Length Records

  • 可以将最后插入的record放入被删除的record的位置，而不是整体移动插在最后(这样会移动很多次)
  • 在文件起始位置分配一定数量的file header, 可以记录第一个被删除record的地址，然后第一个被删除的record位置又记录着第二个被删除的record的位置。这样就形成了free list
  • 当插入records时，找到free list的最后一个位置将record插入

    Variable-Length Records

  • page layout:slotted-pages, log-structured
  • varchar类型<偏移量，长度>
  • 变长记录的空位图记录哪一个属性是空值
  • 分槽的页结构，块头记录条目的个数，块中空闲空间的末尾处, 即尾部的开始处（方便插入），包含记录位置和大小的记录条目组成的数组

other

  • 如果数据库的页超过操作系统的标准页(4KB)DBMS将需要利用额外的手段来确保数据页原子写(在系统出现崩溃的时候)
  • 如果两个表相关，DBMS会’pre-join’这样可以使得两个表在同一个页上，效率更高

Log-Structure Storage

  • slotted-pages的一些缺点: Fragmentation、Unless Disk I/O、Random Disk I/O
  • 每一个log record包含一个独立的标识符
  • DB可以将log压缩到一个表中，称为SSTable(Sorted String Table)
  • write amplification: 不断写同样的数据

Data Representation

  • 在tuple中的数据本质上是字节数组，DBMS将这些字节数组解释为什么属性取决于数据的表示
  • 五种高级数据类型: integers, variable-precision numbers, fixed-point precision numbers, variable length values, and date/times.
  • 整型数(INTEGER, BIGINT, SMALLINT, TINYINT)
  • 可变精度数字(FLOAT, REAL)
  • 定点精度数字(NUMERIC, DECIMAL)
  • 可变长度值(VARCHAR, VARBINARY, TEXT, BLOB)。
    • 比较典型的是存在头部储一个跟踪长度的属性，方便跳到下一个值；其中可能也包括校验和
    • 大多数DBMS不允许tuple的大小超过一个页，因此当tuple过大时，数据会存储在”overflow pages”中，并且tuple中会有到overflow pages的引用。
    • 一些系统也会允许将数据存储在外部文件上，但DBMS不能操纵这些数据，同时这些数据也不具有持久性和事务保护。
  • 日期和时间(TIME, DATE, TIMESTAMP)
    • 可以表示从unix epoch开始的时间
  • System catalogs
    • 为了解析tuple的内容，DBMS维护了一个内部目录来说明数据库的元数据。这些元数据包括表中的哪一列的类型和值是什么等信息。

Database Workloads

  • OLTP(Online Transaction Processing)。OLTP一般处理更多的写相比于读
  • OLAP(Online Analytical Processing)。分析现有的数据并产生新的数据

Storage Models

  • N-Ary Storage Model(NSM)。对于一个tuple的所有属性都在一个页里，适配OLTP
    • 优点：更快地插入，更新，删除；对需要整个tuple的查询有利
    • 缺点：不利于扫描表的大部分或者属性的子集
  • Decomposition Storage Model(DSM)。就是所谓的列存储，将一个属性列存储在一个块中，所有块连续存放。适配OLAP
    • 优点：减少大量的I/O，因为DBMS在查询中只读数据；更好的查询处理和数据压缩
    • 缺点：点查询，插入，更新和删除变慢，因为tuple中的属性分离
    • 将属性列还原成原来的行存储有两种方法:
      • 每一列有同样的长度和offset
      • 使用嵌入的tuple ids(如主键)。但这种方法会造成大量的存储开销

Database Compression

  • 压缩可以提高性能，尤其是对于那些只读的分析负载
  • 压缩和解压也需要开销
  • 如果数据集是完全的随机bit，将不能压缩
  • 压缩策略：
    • 必须产生固定长度的值，唯一的例外，可变长度数据存储在分离的pools里
    • 允许DBMS在查询执行过程中推迟解压
    • 必须是无损的策略，任何有损的压缩将在应用级执行
  • 压缩粒度：
    • Block Level: 压缩同一个表中的元组块
    • Tuple Level: 压缩整个tuples的内容(仅支持NSM)
    • Attribute Level: 压缩一个tuple的一个属性值，也可以针对同一个tuple的多个属性
    • Columnar Level: 压缩多个tuples中的多个属性值(仅支持DSM)

Memory Management

  • Spacial Control: 页被写到磁盘的哪个位置，应该保证页在磁盘尽可能物理上地紧挨着
  • Temporal Control: 合适将页读到内存中，何时将页写到磁盘中，目标是为了减少从磁盘读页造成的停顿
  • Locks vs. Latches: lock是高级原语用于保证的数据库内容(e.g. tuples, databases, tables)不受其他事务的影响；latch是低级原语，用于内部数据结构(e.g., hash tables, regions of memory)的临界区
  • Buffer Pool是磁盘页在内存中的缓存
    • 元数据: page table(类似于os的page table)，注意与page directory的区别，page directory映射页id到数据库文件中的页的位置，对page directory的所有改变都必须记录在磁盘上，以便DBMS重启时能找到。page table的每一页还可能包含:脏位，pin计数等元数据
    • 内存分配策略：全局(对于整个工作负载有利)和局部(对于单个查询或事务有利)策略。tradeoff，大多数系统一般组合它们使用
    • 优化：pre-fetching