数据库事务模型分析(2)—— 等价关系

在本节中,基于上一节的页模型,提出并发执行正确性的概念,并建立多个事务在时间上交叉执行的模型,提出有关并发事务调度的概念。首先要明确的是,事务的执行是高度动态的,完全建模会带来巨大的理解成本,实际上,当事务到来,并发控制需要对该事务做出执行决定,并使能其和系统中正在运行的事务正确同步。其次,需要考虑执行失败而被终止的事务,在正常执行的路径中,包含提交终止。这些操作的处理方式和直觉很不一样。

并发执行的事务之间的数据访问操作存在潜在的冲突,比如“修改后丢失”、“读不一致”、“脏读”等问题,作为事务执行顺序的保证来说,这些异常都是要避免的,给外部执行一致的印象。

为了判断事务执行时,何种情况是期望的,何种情况是应该避免的,调度器需要在线的应用这些规则。首先,本文假定调度中包含了事务结束标志成功或者不成功,具体的,一个事务成功的结束使用$c$表示,即事务在没有被中断的情况下完成了内部所有的数据操作,而失败事务的结束使用$a$表示,一个被终止的事务不应该对底层数据产生任何影响,这由恢复过程保证。

阅读更多

数据库事务模型分析(1)—— 计算模型

事务服务的计算模型可以通过多种方法精确创建,和抽象程度有关,而建模数据库事务服务的系统需要遵循一些基本的方法论以及相关实际因素,本系列所作的建模一般分为以下5个步骤:

  1. 首先定义数据对象的基础操作,这些操作被认为是原子的,并且独立于其他操作,这一步并没有明确定义什么是数据对象以及需要考虑什么类型数据的基础操作。因此本系列定义两种不同的计算模型:页模型和对象模型
  2. 对事务以及事务执行顺序建模,将其视为在数据对象上基础操作的一个(全/偏)序列;
  3. 本系列使用调度或者历史的概念作为对事务执行并发的抽象;
  4. 在所有句法正确的调度中,必须从中识别出保证ACID“正确”的调度;
  5. 需要“算法”或者“协议”来即时地创建事务正确的调度,当事务提交之后,可以被动态执行;

上述的“页模型”是一个非常简单的模型,可以观察在存储层中,数据页是如何被事务优雅的读写的。接下来可以看到这个模型以一种非常优雅的方式建模了并发控制事务恢复的实现,并且可以描述非常多(但不是全部)系统实现中的重要语义。
“对象模型”是预留给数据库的上层操作,比如访问层或者查询处理层的操作,很容易想到把上层数据应用的业务数据对象考虑在内,可以推导出更复杂的对抽象数据结构ADT的语义,借由ADT来执行下层数据对象的操作。

阅读更多

DuckDB-源码分析(1)背景与应用

2019年,CWI发表了一篇关于DuckDB的论文:《DuckDB: an Embeddable Analytical Database》,旨在OLAP领域构建一个嵌入式的数据库,解决单点交互式数据分析的问题,并给边缘计算提供除SQLite之外的更优选择。在论文中,作者们总结DuckDB为在一个进程内的SQL OLAP DBMS,这句话至少有两个解读点:

  1. DuckDB的工作方式应该和SQLite一致,即在进程内部运行,并不需要类似MySQL或者PG的等单独起一个数据库服务;
  2. 作为AP系统,可以支撑一定复杂的数据分析和查询任务。

SQLite是在全球运行最多的关系型数据库管理系统,每个浏览器和操作系统以及各种嵌入式设备都能找到该数据库使用的痕迹。但是SQLite更多为TP任务服务,很难利用向量化、内存加速来提高数据分析的速度。所以DuckDB弥补了SQLite这方面的空白。

阅读更多

多线程共享与伪共享检测

多线程/进程之间使用缓存一致性协议来保证每个包含独立缓存对象的核心在共享使用内存数据时的一致性,缓存一致性协议保证了缓存实体中的任何更新都会对相同位置的其他缓存进行全部更新。MESI协议是最著名的一致性协议,支持现代CPU中缓存回写。通过监控内存事务保持一致性,一致性问题可以得到缓解,但是是有代价的,导致CPU访存空转,浪费系统带宽,两种具有代表性的内存一致性问题是“真共享”和“伪共享”。

阅读更多

现代 C++ 分享(1)—— 生命周期、所有权和资源管理

这是整个现代 C++ 分享系列第一篇,关于生命周期、所有权和资源管理。主题包括但不限于指针、智能指针、引用、类型系统、移动语义以及完美转发和引用折叠相关的主题。

C++ 在演进过程中逐渐增强和扩展了对类型处理的能力:

  1. C++11 中引入右值引用,通过重新定义值类别对表达式进行分类,右值引用能表达移动语义,解决了 C++11 之前产生的中间临时对象需要多次拷贝的问题;
  2. C++11 中引入 auto 关键字,对初始化变量进行推导,并且引入 decltype 关键字,通过已有对象、变量获得类型;
  3. C++17 引入 optional 类型表达对象是否存在,并且引入 variant 作为类型安全的 union,类型表达更灵活。
  4. C++20 中引入 concept 特性对类型在编译期做约束,增强类型的表达和检查能力。

在 C++ 中,容器和指针抽象后想要被正确且高效的使用,在工程中通常需要封装一组数据及函数来访问和操作。举例来说,指针是通用和有效抽象的机器地址,但正确使用指针来表示资源的所有权是非常困难的,因此标准库提供了智能指针类管理资源和生命周期。指针的更泛化的概念是,任何允许我们引用对象并根据其类型访问。

阅读更多
Your browser is out-of-date!

Update your browser to view this website correctly.&npsb;Update my browser now

×