当前位置： 首页 > news >正文

【CMU15-445 Part-16】Concurrency Control Theory

news 2026/1/21 1:43:58

Part16-Concurrency Control Theory

架构概念

Untitled

Transcations

txn就是通过在数据库系统中执行一系列操作（sql queries）来执行某种更高级的功能(应用程序所执行的功能)。

Transcations in SQL

一个新的事务开始 with BEGIN，txn结束with COMMIT / ABORT或者ROLLBACK

如果是COMMIT，要么保存事务的所有改变然后commit，或者数据库系统表示不能commit；commit并不意味着你就commit

如果是abort，自begin开始所做的修改都会被回滚。abort可能是自发的self-inflicted 或者DBMS告诉你这个事务需要中止

Correctness Criteria : ACID

  • Atomicity：原子性，事务的所有做要么都发生，要么都不发生
  • Consistency，一致性
  • Isolation：隔离性，txn之间隔离执行
  • Durability：持久性，事务提交，修改保存，不会丢失

Atomicity of TXN

  • commit after completing all actions
  • abort after excuting some actions

确保原子性的方法

  1. Logging，预写日志Write Ahead Logging，DBMS log 所有的actions，在中止的时候来undo这些操作,维护undo records in mm and disk
  2. Shadow Paging：对每个事务在磁盘上制作一份该数据库文件的副本，所有的修改都在副本上执行，事务提交的时候只需要更改指针指向该副本，表示现在这个副本是该数据的主版本。

logging in MM可以很快的恢复，on Disk 可以处理hard crash之后的recovery

Consistency

Database is logically correct → 查询的结果也是txn logically correct

Database Consistency

数据库要对现实世界准确建模通过integrity constraints （完整性约束）来保证一致性

Transaction Consistency

是application的责任，DBMS只能看到read 或者 write

Isolation of Transactions

隔离性为了更好的programming，实现隔离性一般通过并发控制协议

Mechanisms for Ensuring Isolation

pessimistic protocal 悲观协议

optimistic protocal 乐观协议

Untitled

Correctness

如何确保一个schedule是正确的

也就是可串行化：某个schedule的执行结果等同于按顺序执行的结果，那么说这种执行顺序的schedule是正确的，也就是serializable schedule 可串行化的执行计划。

如果T1先执行，后面是T2，T1先被提交，是strict serializeability 严格可串行化。

Interleaved Execution Anomalies

R-W W-R W-W

Unrepeatable Reads

不可重复读：试着去读取同一个对象的时候得到的值并不相同，实际是read-write conflicts

Untitled

Dirty Reads

脏读：read-write冲突，reading uncommitted Data，读未提交，读了脏数据。

Untitled

W-W Conflicts

写写冲突，overwrting uncommitted data，覆写未提交的数据。

Untitled

Conflict Serializability

如果两个schedule被认为是冲突等价conflict equivalent，如果这两个调度涉及相同事务的相同操作，每一对冲突的操作在两个调度中的顺序都相同。

Untitled

冲突等价(ConflictEquivalence) 可串行化调度(Serializable Schedules)_软件工程小施同学的博客-CSDN博客

冲突可串行化调度

通过交换不冲突操作的顺序来弄清楚该schedule是否是冲突可串行化，最终得到一个可顺序执行的调度

Untitled

Dependency Graph

依赖图或者叫precedence graph 优先图，如果一个事务中的某些操作和另外一个事务的操作有冲突，Oi早于Oj，则Ti→Tj是一条边，如果有环则是不可串行化。

并不是conflict serializable，但是仍然能够得到和按顺序执行事务的相同结果和相同的数据库状态，这就是ViewSerializability

Untitled

View Serializability

屏幕打印看到的结果和实际最终的结果不一致，要追求看到的和实际的一致。

从视觉角度上来看 这两种执行顺序所达到的效果是等同的。但是要知道T3最后W（A）

Untitled

相关文章：

【CMU15-445 Part-16】Concurrency Control Theory

Part16-Concurrency Control Theory 架构概念 Transcations txn就是通过在数据库系统中执行一系列操作（sql queries）来执行某种更高级的功能(应用程序所执行的功能)。 Transcations in SQL 一个新的事务开始 with BEGIN，txn结束with COMM…...

编程日记 2023/10/6 23:41:37

软件设计模式系列之二十五——访问者模式

访问者模式（Visitor Pattern）是一种强大的行为型设计模式，它允许你在不改变被访问对象的类的前提下，定义新的操作和行为。本文将详细介绍访问者模式，包括其定义、举例说明、结构、实现步骤、Java代码实现、典型应用场景…...

编程日记 2023/10/6 23:40:36

国庆看坚如磐石

坚如磐石上映了，可以在爱奇艺观看。 而博主在使用蓝牙耳机连接电脑的过程中，发现没有蓝牙开启选项，并且在服务的设备管理器中也没有找到，很明显这是缺少驱动导致的，因此便去联想官方网站下载对应的驱动。 这里可以输入…...

编程日记 2023/10/6 23:37:33

代码随想录Day59 | 647. 回文子串 | 516. 最长回文子序列

647. 回文子串 class Solution { public:int countSubstrings(string s) {int sum0;int ns.size();vector<vector<int>> f(n1,vector<int>(n1,0));//表示区间范围[i,j] &#xff08;注意是左闭右闭&#xff09;的子串是否是回文子串。初始值为0.for(int i n…...

编程日记 2023/10/6 23:35:31

为什么InnoDB选择B+树而不是红黑树作为索引结构？

在数据库管理系统中&#xff0c;索引结构的选择对于数据库的性能和效率至关重要。MySQL的InnoDB存储引擎是一个广泛使用的数据库引擎&#xff0c;它选择了B树作为索引结构&#xff0c;而不是像红黑树那样的其他数据结构。本文将探讨为什么InnoDB选择B树&#xff0c;并解释B树与…...

编程日记 2023/10/6 23:34:30

【c++_containers】10分钟带你学会list

前言 链表作为一个像是用“链子”链接起来的容器&#xff0c;在数据的存储等方面极为便捷。虽然单链表单独在实际的应用中没用什么作用&#xff0c;但是当他可以结合其他结构&#xff0c;比如哈希桶之类的。不过今天学习的list其实是一个带头双向链表。 言归正传&#xff0c;让…...

编程日记 2023/10/6 23:33:29

LeetCode 0714. 买卖股票的最佳时机含手续费

【LetMeFly】714.买卖股票的最佳时机含手续费 力扣题目链接&#xff1a;https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-with-transaction-fee/ 给定一个整数数组 prices&#xff0c;其中 prices[i]表示第 i 天的股票价格 &#xff1b;整数 fee 代表了交易股…...

编程日记 2023/10/6 23:32:27

cartographer-(0)-ubuntu(20.04)-环境安装

1.安装 ROS wiki.ros.org 1.1修改镜像源&#xff1a; 到网站上找与操作系统相匹配的镜像源 ubuntu | 镜像站使用帮助 | 清华大学开源软件镜像站 | Tsinghua Open Source Mirror # 默认注释了源码镜像以提高 apt update 速度&#xff0c;如有需要可自行取消注释 deb htt…...

编程日记 2023/10/6 23:31:26

MIT 6.S081学习笔记（第二章）

〇、前言 本文主要完成MIT 6.S081 实验二&#xff1a;system call 一、Using gdb (easy) Question requirements In many cases, print statements will be sufficient to debug your kernel, but sometimes being able to single step through some assembly code or inspe…...

编程日记 2023/10/6 23:30:24

L958. 二叉树的完全性检验 java

从1开始当下标&#xff0c;最后节点下标节点总数&#xff1f;true&#xff1a;false&#xff1b; /*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode() {}* TreeNode(int val) { …...

编程日记 2023/10/6 23:29:23

阿里云对象存储OSS SDK的使用

官方文档 https://help.aliyun.com/zh/oss/developer-reference/java 准备工作 windows安装好JDK&#xff0c;这里使用JDK1.8为例 windows安装好IDEA&#xff0c;这里使用IDEA2022 登录阿里云控制台&#xff0c;通过免费试用OSS或开通OSS 步骤 配置访问凭证 有临时和长期…...

编程日记 2023/10/6 23:28:22

二、互联网技术——网络协议

文章目录 一、OSI与TCP/IP参考模型二、TCP/IP参考模型各层功能三、TCP/IP参考模型与对应协议四、常用协议与功能五、常用协议端口 一、OSI与TCP/IP参考模型 二、TCP/IP参考模型各层功能 三、TCP/IP参考模型与对应协议 例题&#xff1a;TCP/IP模型包含四个层次&#xff0c;由上至…...

编程日记 2023/10/6 23:27:21

初赛错题集

MPEG属于视频文件格式. UNIX,Mac OS属于操作系统. 中国计算机协会成立于&#xff08;&#xff09;年。 A. 1961 B. 1962 C. 1971 D. 1972 Ans:B 五个本质不同的点在没有重边或者自环的情况下&#xff0c;组成不同的无向图的个数是: A. 10 B. 1024 C. 15 D. 120 Ans:B 解析&…...

编程日记 2023/10/6 23:26:20

Java Thread类详解

&#x1f648;作者简介&#xff1a;练习时长两年半的Java up主 &#x1f649;个人主页&#xff1a;程序员老茶 &#x1f64a; ps:点赞&#x1f44d;是免费的&#xff0c;却可以让写博客的作者开兴好久好久&#x1f60e; &#x1f4da;系列专栏&#xff1a;Java全栈&#xff0c;…...

编程日记 2023/10/6 23:24:18

3_使用传统CNN网络训练图像分类模型

使用传统CNN网络训练图像分类模型 1. MNIST 首先，定义一下超参数等 import torch# dataset input_shape = 28 num_classes = 10# hyper batch_size = 64 num_epochs = 5 learning_rate = 1e-3# gpu device = torch.device(cuda...

编程日记 2023/10/6 23:22:17

Java 创建线程的方法

&#x1f648;作者简介&#xff1a;练习时长两年半的Java up主 &#x1f649;个人主页&#xff1a;程序员老茶 &#x1f64a; ps:点赞&#x1f44d;是免费的&#xff0c;却可以让写博客的作者开兴好久好久&#x1f60e; &#x1f4da;系列专栏&#xff1a;Java全栈&#xff0c;…...

编程日记 2023/10/6 23:21:16

基于安卓android微信小程序的旅游app系统

项目介绍 随着人民生活水平的提高,旅游业已经越来越大众化,而旅游业的核心是信息,不论是对旅游管理部门、对旅游企业,或是对旅游者而言,有效的获取旅游信息,都显得特别重要.自助定制游将使旅游相关信息管理工作规范化、信息化、程序化,提供旅游景点、旅游线路,旅游新闻等服务本…...

编程日记 2023/10/6 23:17:12

C++设计模式-单件（Singleton）

目录 C设计模式-单件&#xff08;Singleton&#xff09; 一、意图 二、适用性 三、结构 四、参与者 五、代码 C设计模式-单件&#xff08;Singleton&#xff09; 一、意图 保证一个类仅有一个实例&#xff0c;并提供一个访问它的全局访问点。 二、适用性 当类只能有一…...

编程日记 2023/10/6 23:16:11

想做好接口测试，先把这些概念搞清楚了

接口一般来说有两种&#xff0c;一种是程序内部的接口&#xff0c;一种是系统对外的接口。 系统对外的接口 比如你要从别的网站或服务器上获取资源或信息&#xff0c;别人肯定不会把数据库共享给你&#xff0c;他只能给你提供一个他们写好的方法来获取数据&#xff0c;你引用…...

编程日记 2023/10/6 23:15:10

通过融合UGV的地图信息和IMU的惯性测量数据，实现对车辆精确位置和运动状态的估计和跟踪研究（Matlab代码实现）

&#x1f4a5;&#x1f4a5;&#x1f49e;&#x1f49e;欢迎来到本博客❤️❤️&#x1f4a5;&#x1f4a5; &#x1f3c6;博主优势&#xff1a;&#x1f31e;&#x1f31e;&#x1f31e;博客内容尽量做到思维缜密&#xff0c;逻辑清晰&#xff0c;为了方便读者。 ⛳️座右铭&a…...

编程日记 2023/10/6 23:14:10

[2025CVPR]DeepVideo-R1：基于难度感知回归GRPO的视频强化微调框架详解

突破视频大语言模型推理瓶颈，在多个视频基准上实现SOTA性能 一、核心问题与创新亮点 1.1 GRPO在视频任务中的两大挑战 ​安全措施依赖问题​ GRPO使用min和clip函数限制策略更新幅度，导致： 梯度抑制：当新旧策略差异过大时梯度消失收敛困难：策略无法充分优化# 传统GRPO的梯…...

编程新知 2025/8/19 23:46:57

java_网络服务相关_gateway_nacos_feign区别联系

1. spring-cloud-starter-gateway 作用&#xff1a;作为微服务架构的网关&#xff0c;统一入口&#xff0c;处理所有外部请求。 核心能力&#xff1a; 路由转发&#xff08;基于路径、服务名等&#xff09;过滤器&#xff08;鉴权、限流、日志、Header 处理&#xff09;支持负…...

编程新知 2025/11/28 2:51:33

【快手拥抱开源】通过快手团队开源的 KwaiCoder-AutoThink-preview 解锁大语言模型的潜力

引言&#xff1a; 在人工智能快速发展的浪潮中&#xff0c;快手Kwaipilot团队推出的 KwaiCoder-AutoThink-preview 具有里程碑意义——这是首个公开的AutoThink大语言模型&#xff08;LLM&#xff09;。该模型代表着该领域的重大突破&#xff0c;通过独特方式融合思考与非思考…...

编程新知 2026/1/15 10:59:06

【SQL学习笔记1】增删改查+多表连接全解析（内附SQL免费在线练习工具）

可以使用Sqliteviz这个网站免费编写sql语句&#xff0c;它能够让用户直接在浏览器内练习SQL的语法&#xff0c;不需要安装任何软件。 链接如下&#xff1a; sqliteviz 注意&#xff1a; 在转写SQL语法时&#xff0c;关键字之间有一个特定的顺序&#xff0c;这个顺序会影响到…...

编程新知 2026/1/15 4:57:52

C++ 求圆面积的程序（Program to find area of a circle）

给定半径r&#xff0c;求圆的面积。圆的面积应精确到小数点后5位。 例子&#xff1a; 输入&#xff1a;r 5 输出&#xff1a;78.53982 解释&#xff1a;由于面积 PI * r * r 3.14159265358979323846 * 5 * 5 78.53982&#xff0c;因为我们只保留小数点后 5 位数字。 输…...

编程新知 2026/1/14 18:39:34

Java面试专项一-准备篇

一、企业简历筛选规则 一般企业的简历筛选流程&#xff1a;首先由HR先筛选一部分简历后&#xff0c;在将简历给到对应的项目负责人后再进行下一步的操作。 HR如何筛选简历 例如&#xff1a;Boss直聘&#xff08;招聘方平台&#xff09; 直接按照条件进行筛选 例如&#xff1a…...

编程新知 2026/1/20 18:34:05

AspectJ 在 Android 中的完整使用指南

一、环境配置&#xff08;Gradle 7.0 适配&#xff09; 1. 项目级 build.gradle // 注意&#xff1a;沪江插件已停更&#xff0c;推荐官方兼容方案 buildscript {dependencies {classpath org.aspectj:aspectjtools:1.9.9.1 // AspectJ 工具} } 2. 模块级 build.gradle plu…...

编程新知 2025/7/7 22:33:57

Maven 概述、安装、配置、仓库、私服详解

目录 1、Maven 概述 1.1 Maven 的定义 1.2 Maven 解决的问题 1.3 Maven 的核心特性与优势 2、Maven 安装 2.1 下载 Maven 2.2 安装配置 Maven 2.3 测试安装 2.4 修改 Maven 本地仓库的默认路径 3、Maven 配置 3.1 配置本地仓库 3.2 配置 JDK 3.3 IDEA 配置本地 Ma…...

编程新知 2026/1/20 10:36:47

均衡后的SNRSINR

本文主要摘自参考文献中的前两篇&#xff0c;相关文献中经常会出现MIMO检测后的SINR不过一直没有找到相关数学推到过程&#xff0c;其中文献[1]中给出了相关原理在此仅做记录。 1. 系统模型 复信道模型 n t n_t nt​ 根发送天线&#xff0c; n r n_r nr​ 根接收天线的 MIMO 系…...

编程新知 2026/1/19 6:30:25

云原生玩法三问：构建自定义开发环境

云原生玩法三问&#xff1a;构建自定义开发环境 引言 临时运维一个古董项目&#xff0c;无文档&#xff0c;无环境&#xff0c;无交接人&#xff0c;俗称三无。 运行设备的环境老&#xff0c;本地环境版本高&#xff0c;ssh不过去。正好最近对 腾讯出品的云原生 cnb 感兴趣&…...

编程新知 2026/1/19 6:53:03