Please enable JavaScript.

Coggle requires JavaScript to display documents.

Database (:moneybag:恢复机制 (:moneybag:事件 (:moneybag:元素 (:explode…

- - - - :explode:事务自身运行错误而引起的故障
      - :moneybag:恢复
        
        :explode:Redo/Undo
    - - :explode:掉电或非正常关机等所引起的故障(内存数据丢失)
      - :moneybag:恢复
        
        :explode:运行日志 #
    - - :explode:磁盘介质损坏引起的故障
      - :moneybag:恢复
        
        :explode:副本 #
  - - - :moneybag:检查点
        
        :explode:定期强制缓冲区内容与磁盘内容保持一致,运行日志会记录这个时间点.恢复的时候不用从运行日志的最开始恢复,而是从检查点开始恢复
        
        :moneybag:恢复
        
        :explode:检查点到故障点完成的事务按日志redo,故障点内没完成的事务要undo
        
        :recycle:是否要暂停系统
        
        :one:静止检查点
        
        :moneybag:设置
        
        :explode:停止接收新的事务,等到所有当前活跃事务commit/abort,并在日志中写入记录后,将日志刷新到磁盘,写入日志记录<CKPT>,并再次刷新日志
        
        :explode:周期性地对日志设置检查点
        
        :two:非静止检查点
        
        :moneybag:设置
        
        :explode:不用停止接收新事务,而是写<START CKPT(T1,T2,...Tk)>,记录当前活跃的事务,直到T1,..Tk都完成,就写<END CKPT>
        
        :warning::one:从最后一个START CKPT开始redo :two:undo要进行到最后一个checkpoint包含的活跃且需要undo的事务的最早start
        
        :explode::one:因为对于redo来说,CKPT之前的都已经写入磁盘了,所以不用自己再去操作 :two:对于undo来说,CKPT前面写入磁盘的是多余的结果,所以要恢复一直到CKPT前面,到事务的start处才停止
      - :recycle:Redo/Undo
        
        :two:Redo型日志
        
        :moneybag:信息
        
        :one:<T,X,v>
        
        :explode:v表示事务T处理元素X后的值
        
        :three:OUTPUT
        
        :two:<COMMIT T>
        
        :zero:<START T>
        
        :warning:UndoOC,RedpCO
        
        :explode::one:如果从t start开始能找到commit/abort,说明事务完成了 :two:对于完成(有commit/abort)的事务,从日志的起始位置开始,处理每一条记录,重做完成事务的所有修改
        
        :key:内存来不及写入(commit的了)到磁盘就挂了
        
        :three:Undo/Redo型日志
        
        :moneybag:信息
        
        :one:<T,X,u, v>
        
        :explode:u表示事务T处理元素X前的值v表示事务T处理元素X后的值
        
        :two::three:OUTPUT/<COMMIT T>
        
        :zero:<START T>
        
        :explode:不要颠倒顺序.从后开始undo,从前开始redo
        
        :moneybag:追加的log
        
        :explode::one:Redo不用追加(上面的log已经表明做了) :two:undo要追加(因为要用abort闭合start才行,并且只用记录一个值<T, A, 100>这样子)
        
        :one:Undo型日志
        
        :moneybag:信息
        
        :one:<T,X,v>
        
        :explode:v表示事务T处理元素X前的值
        
        :two:OUTPUT
        
        :three:<COMMIT T>/<ABORT T>
        
        :zero:<START T>
        
        :explode::one:如果从t start开始能找到commit/abort,说明事务完成了 :two:对于没有完成的事务(没有ABORT也没有COMMIT),从日志的尾部开始,处理每一条记录,撤销未完成事务的所有修改
        
        :key:内存多余的东西(没有commit的)写入到磁盘了
      - :moneybag:故障点没有结束的事务可以撤销
      - :question:如何根据日志文件进行故障恢复
    - - :explode:在某一时刻,将数据库的记录备份到另一个介质存储上.如果发生介质故障,可以利用该副本代替
      - :warning:介质故障可能内存数据也丢失
        
        :moneybag:转储点
        
        :explode:备份的时刻.只能恢复到这个时刻.
        
        :explode:转储点到故障点的内容要依据运行日志恢复
      - :moneybag:备份周期
        
        :explode:和运行日志的大小保持协调.运行日志必须覆盖到转储点之前
    - - :explode:事务故障通过重做事务和撤销事务;系统故障使用运行日志;
  - - - :explode:通常为1磁盘块/1内存页,也可以是1记录或1关系
  - - - :moneybag:缓冲区处理
        
        :one:Force
        
        :explode:只要commit就把缓冲区写入磁盘
        
        :two:No steal
        
        :explode:不允许在commit之前将内存写入到磁盘
        
        :three:No force
        
        :explode:内存中的数据后可以一直保留,commit之后过一段时间再写入磁盘
        
        :question:发生系统故障怎么办
        
        :explode:Redo
        
        :fire::one:读写性能高 :two:需要redo,因为有些commit数据还没写入到磁盘
        
        :four:Steal
        
        :explode:内存中的事务commit之前把内存中的数据写入磁盘
        
        :question:系统崩溃
        
        :explode:Redo
        
        :fire::one:读写性能高 :two:需要undo,因为有些没commit数据写入到了磁盘
        
        :key:内存中的数据和磁盘中的数据不一致
    - - :question:在事务中,如果A写入磁盘而B来不及写入怎么办
  - - - :one:Dirty Page Table(DPT)
        
        :explode:记录所有已经完成,却还没有写入到磁盘的事务
        
        :moneybag:内容
        
        :explode:每个事务最小的LSN
        
        :star:DPT记录下一条LSN,方便向下重做
      - :two:Active Transaction List(ATL)
        
        :explode:记录所有未完成却已经写入到磁盘的事务
        
        :moneybag:内容
        
        :explode:事务的最后一条LSN
        
        :star:ATL记录上一条LSN,从而方便向上回滚
    - - :fast_forward:ARIES数据库恢复算法
    - - :one:分析
        
        :explode:遍历log,获取DPT和ATL
      - :two:重做
        
        :explode::one:先根据DPT找到最小的LSN,再遍历log重做 :two:如果这个事务在DPT里面,但是它的LSN小于记录在DPT里的LSN,那么说明已经落盘,不用重做,否则redo
      - :three:回滚
        
        :explode:根据ATL undo,利用记录中的上个LSN,不断回滚.并记录CLR,结束事务后记录END CLR
    - - :explode:Log Sequence Number.日志的序列号,标记时间顺序
    - - :one:记录
        
        :explode:<LSN，事务ID，页ID，Redo，Undo，前一SN>
      - :two:CLR(补偿log)
        
        :explode:<LSN，事务ID，页ID，重做，前一SN>
      - :star:因为只记录前一个LSN,所以利用它可以undo,而不能redo
- - - - :moneybag:基本操作
        
        :explode::one:并 :two:差 :three:积 :four:选择 :five:投影
      - :moneybag:定理
        
        :one:并与并,积与积,交与交,连接与连接的交换律
        
        :two:连接与连接,积与积的结合律
        
        :three:投影串接律
        
        :star:投影的属性扩展便于投影移动
        
        :four:选择串接律
        
        :star:有利于选择的移动(尤其是移动到乘积的前面)
        
        :five:选择和投影交换律
        
        :explode:保证选择的属性都在的情况下.先选后投或者先投后选都没关系.也可以和投影串接律结合
        
        :six:选择和积的交换律
        
        :explode:选择如果只涉及其中一个项,就可以交换了
        
        :seven:投影和积的交换律
        
        :explode:笛卡尔乘积前,两个项都保留需要的属性就行了
        
        :eight:选择和并的交换律
        
        :explode:无条件
        
        :nine:选择和差的交换律
        
        :explode:无条件
        
        :one::zero:投影和并的交换律
        
        :explode:无条件
    - - :explode:(:zero:随时合并/拆分投影) :one:拆分选择 :two:选择下移 :three:投影下移 :four:分组程序实现
      - :warning:一元操作如选择和投影,不用分顺序.因为都同时进行
  - - - :explode:参考我们的查询实现算法中的全内存算法等
    - - :two:选择
        
        :one:等于
        
        :explode:T(R)/V(R,A)或1/10
        
        :moneybag:V(R,A)
        
        :explode:A这个属性在关系R中出现的不同值的数目
        
        :two:<
        
        :explode:1/3
        
        :three:and
        
        :explode:乘积
        
        :four:or
        
        :explode:1-(1-左边的概率)*(1-右边的概率)
      - :three:自然连接
        
        :explode:T(Res)=T(R)T(S)/MAX(V(R,Y),V(S,Y))
        
        :snowflake:S=R(X,Y) natural join S(Y,Z)
        
        :star:如果Y是R->S的外键,那么结果是T(R).如果Y是R的主键,那么结果是T(S)
      - :one:投影
        
        :explode:不变
      - :explode:估计某个操作后的元组数量
  - - - :one:手动写代码
      - :two:触发器
      - :three:增量的视图维护
        
        :moneybag:根据视图的获得方式进行增量
        
        :one:自然连接
        
        :explode:插入/删除的元组集和另一个关系进行自然连接,然后额外添加/删除到原来的视图结果里
        
        :two:选择
        
        :explode:只判断插入/删除的元组集,如果ok就加入到视图结果
        
        :explode:更新分为删除并插入.从而我们只要根据插入/删除的元组,再利用关系代数,确认新视图和旧视图的差,然后补足就可以了
    - - :one:查询优化
        
        :one:如果用户有某个操作,是和之前的物化视图一样的查询方式,则可以直接利用物化视图
        
        :two:如果对物化视图本身查询,而物化视图通过自己定义拆分出来可以加速原来的查询,那么就可以优化了
    - - :explode:选择的物化视图应该能使系统查询和更新的总耗费时间最短
  - - - :explode::one:对于子查询单独的谓词(即不和外层的关系有联系的话),就可以先查出这个表,记住t1 :two:将t1放在外层from里面,这样另外的谓词放在外层where里,这样就ok了
- - - - :explode:有了S后,能读不能写
    - - :explode:有了X后,能读写
    - - :moneybag:意向锁表示有意加锁,并且如果上了意向锁后,接下来就一定会上锁.意向锁可以分为IS和IX,表明其后代存在S锁/X锁
      - :moneybag:兼容矩阵
        
        :arrow_right:MySQL 共享锁、排他锁、意向锁解析
        
        :fire::one:IS和IX都兼容,因为都是有意,而不是真干 :two:IX和X不兼容,因为如果上了IX,就有可能X和X冲突
      - :zap:行锁和表锁
        
        :explode:锁定了整张表,自然就不能操作行了
      - :question:如何锁定一个node
        
        :explode::one:兼容 :two:父节点都被锁上了 :three:只有父节点是IX或IS,才可以上S/IS :four:只有父节点是IX,SIX,才可以上X,SIX,IX
        
        :star:加锁自上而下,解锁自下而上
        
        :bulb:和Tree Protocol不一样,后者解锁时孩子可以不用解锁
      - :fire::one:增强并发性 :two:降低加锁开销
  - - - :explode:如果一个item被上了S.我要X的话,就要等它释放.但是其他人可能也要S,由于都是S,不用等待,所以他们都上了S.而我可能要一直等下去.(一本笔记书大家都能看,我得等所有人都看完才能看笔记本)
      - :maple_leaf:授予lock的时候:one:兼容 :two:没有其他事务在等待授权
  - - - :explode:一个事务,先全部加锁,处理完后,再全部解锁.即,一个事务是Two-Phase Locking,只要它满足可划分成两个阶段,一个阶段只有加锁,一个阶段只有解锁
      - :fire::check:可串行=>数据一致性 :red_cross:防止死锁
        
        :moneybag:串行化
        
        :explode:只要这个并发算法和某一种串行结果相同,就能说是可串行的
        
        :moneybag:冲突可串行化
        
        :explode:不同事务同时读写或写写会产生冲突,如果一个schedule能将冲突的操作调节成类似串行的操作的话,就是冲突可串行化
        
        数据库事物之冲突可串行化、优先图、视图等价和视图可串行化
        
        冲突可串行的判定
        
        :key:只有串行调度是正确的.并发结果只有与串行调度一致才是正确的
        
        如何判断冲突可串行化？
        
        :warning:即使不同顺序串行结果都不一样,这些结果也都是正确结果,除此以外的结果都是错误的
        
        :moneybag:冲突操作
        
        :warning:针对同一数据item而言
        
        :one:同一事务不同操作是冲突的
        
        :two:不同事务的只要读写或写写操作是冲突的
        
        数据库冲突可串行化前趋图画法
      - :moneybag:死锁
        
        :zap::zero:T1转账,T2计算A+B的总和 :one:T1要处理itemA和B,那么先加锁A,进行处理 :two:此时T2要加锁B,读取B :three:T2要继续加锁A才能读取,而T1要加锁B才能转账=>死锁
        
        :maple_leaf:rollback
        
        :explode:选择一个合适的事务rollback
        
        :one:整个事务/事务部分
        
        :two:不要总是一个事务rollback(会导致starvation)
        
        :fire:死锁不会影响数据一致性
      - :moneybag:Lock Conversion
        
        :explode::one:加锁阶段可以S=>X :two:解锁阶段可以X=>S
    - - :explode::one:必须父节点上锁我才能被上锁 :two:我随时都能解锁 :three:第一次上锁随便你 :four:同一个人不要重复操作
      - :fire::one:可串行化 :two:解决了死锁
  - - - :explode:根据item名哈希运算的哈希表.记录granted locks以及lock类型和pending requests
      - :moneybag:unlock
        
        :explode:自己从请求队列中离开
      - :moneybag:lock
        
        :explode:加入到请求队列中,如果前面和我都是兼容的,那我就可以直接读书了~
      - :question:怎么看图
        
        :explode::one:事务是下面的,item是上面的 :two:黑色表示granted,白色表示waiting :three:画图,所有白色的指向左边最后一个黑色的 :four:画出来的图中,循环的是死锁
        
        :question:如果有死锁,怎么rollback
        
        :explode:挑一个在循环里的就行了
        
        :question:怎么画rollback后的Lock Table图
        
        :explode::one:事务如果是白色就直接删掉,后面跟进 :two:黑色就删掉后,后面如果白色的话变黑跟进,黑色的话直接跟进
- - - - :explode:=存储单元的地址=内存地址=页面:页面偏移量
      - :warning:页(Page)=块(Block)
  - - - :explode:cluster=block=多个sectors
      - :warning::one:磁盘的多个块通过链表的形式存起来 :two:文件和这些块的对应关系记录在操作系统的FAT表中
    - - :one:平均寻道时间1-20(9.1)ms
      - :two:平均旋转等待时间0-10(4.17)ms
      - :three:数据传输速率13MB/s
      - :star:磁盘时间:内存时间=10,000:1
  - - - :moneybag:RAID技术
        
        :one:并行处理
        
        :one:比特级拆分
        
        :two:块级拆分
        
        :two:可靠性
        
        :explode:奇偶校验
        
        :one:扇区/块读写
        
        :two:磁盘间读写校验:
  - - - :two:变长记录
        
        :maple_leaf::one:使用分隔符 :two:指针
        
        :two:指针处理变长记录
        
        :question:那么一个块里存放多少个是不是也是确定的
        
        :moneybag:Slotted-Page Structure
        
        :explode:一个块中存储变长记录的方法.分为header,free space,records
        
        :one:header
        
        3 more items...
        
        :moneybag:删除
        
        2 more items...
        
        :tornado:orris/database/storage/slotted_page.png
        
        1 more item...
        
        :maple_leaf:确定的
        
        :question:假设指针对占4个字节,那么由于变长的最大值确定,所以我们可以确定一个块中可以放多少个记录.然后是不是比如说记录大小为N,那么我们就在0,N,2N,..的地方存,而不是说紧挨着存
        
        :moneybag:<offset,length>
        
        :question:长度为多少
        
        :explode:长度为4只是假定每个是2字节
        
        :explode:指针就是在原来的记录位置不存真实数据,而是存放说明位置的指针.比如说'Bill'本来该存在这个位置,结果我存<20,4>(<offset,length>)表明'Bill'存放在偏移位置为20的地方,长度为4
        
        :moneybag:null bitmap
        
        :explode:第几个属性是null的话,就在表示null bitmap的数字的第几个位上记作1
        
        :moneybag:长度
        
        :explode:根据属性多少决定,一般为1
        
        :moneybag:记录中的位置
        
        :explode::one:定长区与变长区之间 :two:记录的开头
        
        :two::moneybag:记录的开头
        
        1 more item...
      - :one:定长记录
        
        :moneybag:free list
        
        :explode:Lazy Deletion中在存储的文件设置一个文件头,指向第一个空闲记录,然后这个空闲记录指向下一个空闲记录.从而形成free list
      - :question:跨块存储
        
        :maple_leaf:不允许跨块存储
    - - :fire:更新效率高,检索低
      - :maple_leaf:定时前移记录(数据库重组)(解决lazy deletion的空间浪费)
    - - :fire:按排序字段检索的话检索效率高,更新效率低
      - :maple_leaf:溢出文件保留新记录.溢出文件是无序的.如果溢出文件太大的话,顺序记录就无意义.所以要定时数据库重组
    - - :explode:根据记录的散列值确定存储位置
      - :moneybag:链接法处理桶满的问题.多的桶使用溢出桶.
    - - :explode:将具有相同/相似属性值的记录存放于连续的磁盘簇块中
      - :fire:根据某一字段,比如在同一系的教师记录,连续存储
- - - - :explode:迭代器算法
        
        :two:流水线计算策略:check:
        
        :explode:结合所有操作处理一个记录
        
        :one:物化计算操策略
        
        :explode:获得完整结果
        
        :moneybag:迭代器
        
        :explode:对每个表设置一个迭代器,可以迭代所有元组,并且只能判断下一个元组是不是在下一个block里
        
        :moneybag:示例
        
        :one:R并S
        
        :two:SELECTION
        
        :three:PROJECTION
        
        :warning:这里的都是用运算来构造下一个迭代器.所以上面的结果都是新的迭代器
        
        :four:Join(R,S)
        
        :explode::one:利用迭代器得到R的第i个元组 :two:利用迭代器得到S的第j个元组 :three:如果i和j可以连接就返回,不能连接的话,S继续向下迭代 :four:如果S返回了NotFound,那么就下移R :five:如果R返回NotFound,那么就整体返回NotFound,否则就重新S.open(),然后继续对R的这个记录迭代S的所有记录
        
        :fast_forward:orris/database/query/iterator_join.png
    - - :one:一趟扫描算法
      - :two:两趟算法扫描
        
        :explode:内存不够用
      - :three:多趟扫描算法
      - :moneybag:排序散列索引
      - :fire:DISTINCT,GROUP BY,SORTING
  - - - :two:Block Nested-Loop Join
        
        :one:假如内存只能放三个page(基本实现算法)(Worst Case)
        
        :star:\(B^R\)+\(B^R\)*\(B^S\)次IO操作,中间的内存操作可以忽略不计
        
        :explode::one:按块来读取R和S :two:先读取R的所有块,共\(B^R\)个 :three:对于R的每个块,读取S的所有块,然后直接在内存中比较完这些块的内容,一个块共需要读\(B^S\)个
        
        :fast_forward:orris/database/query/natural_join.png
        
        :two:内存都可以装下(全内存实现算法)(Best Case)
        
        :explode:直接都压入内存,并且遍历元组
        
        :three:内存只能装下一个表(半内存实现算法)
        
        :explode:装入R,对S就一个块一个块地读取,然后每个块都和R的所有元组遍历
        
        :star:\(B^R\)+\(B^S\)次IO操作
        
        :zap:第一次载入整个R时,和后面的载入S
        
        :four:内存不能放下任何一个表(大关系实现算法)(Fixed Buffer Size Cases)
        
        :explode::one:M-2个依次放R :two:剩下两个block一个存S,一个存结果 :three:对于载入内存的M-2个block的R,依次和S的每个Block做计算
        
        :star:R的总块数+ceiling(R的总块数/(内存能放的最大块数-2))*S的总块数
      - :three:Indexed Nested-Loop Join
        
        :explode:如果有一个表S在连接属性上存在索引,那么我们可以遍历表R的每个元组,在这个元组上利用索引查找表S中符合要求的元组
        
        :moneybag:Cost
      - :one:Nested-Loop Join
        
        :explode:二次循环所有元组
      - :four:Merge Join
        
        :explode:如果R和S都在连接属性上按顺序存储(我们也可以先排序),那么只需要两边同时向下边移动边比较就行了
        
        :moneybag:Cost
        
        :one:Best: \(B^R\)+\(B^S\)
      - :five:Hash Join
        
        :explode:在连接属性上将R和S都哈希到各自的哈希表中,这个哈希表的下标是哈希值,存储的是元组的位置.从而我们遍历R,获得这个元组的哈希值h1,然后在S的哈希数组中找到该h1位置,它里面记录的元组位置就是我们需要找的最小范围
- - - - :one:HTTP连接8083
      - :two:输入命令influx进入交互界面
      - :star:常用组合:Sensu+InfluxDB+Grafana
- - - - :explode:多个事务在宏观上是并行执行的,微观上,这些基本操作都是交叉执行的
      - :moneybag:可串行性的
        
        :explode:如果这个并行调度的结果和某一个串行调度相同,这称这个调度是可串行化的
        
        :checkered_flag:判断并行调度是否正确
        
        :warning:正确的并行调度不一定是可串行的,但可串行的一定是正确的调度
        
        :moneybag:冲突可串行化
        
        :moneybag:冲突
        
        :explode:一对连续的操作,如果改变顺序,就会导致结果不一致
        
        :tornado::one:同一事务的不同操作冲突 :two:不同事务的读写/写写操作冲突
        
        :explode:一个调度,如果通过交换相邻两个无冲突的操作,能够转换到偶一个串行的调度,则称此调度为冲突可串行化的调度
        
        :moneybag:判断一个调度是否是冲突可串行化的
        
        :one:手动交换位置
        
        :warning:不同数据item可以交换顺序
        
        :arrow_forward:orris/database/concurrency_control/conflict_serializable.png
        
        :two:前驱图
        
        :explode::one:如果Ti与Tj操作冲突,并且Ti发生在Tj前面,则Ti指向Tj,表示Ti要在Tj前执行 :two:节点为事务 :three:如果没有环,说明冲突可串行化
        
        :arrow_forward:orris/database/concurrency_control/conflict_serializable2.png
        
        :warning::one:T1指向T2说明T1要先于T2执行 :two:最好将调度根据item分开写,这样看的容易点 :three:不只有相邻的画边,只要在同一个数据项,并且我在你前面而冲突的,都要画线
        
        :moneybag:练习题
        
        :arrow_forward:Assignment 4 Solution:
        
        :warning::one:冲突可串行化比可串行化严格.所以:冲突可串行化=>可串行化 :two:调度的正确性不好判断,所以我们判断是否可串行化;因为可串行化不好判断,所以我们判断是否冲突可串行化