EagleBear2002 的博客

\[ % \def\w{mathsf{w}} % \def\r{mathsf{r}} \def\rd{\textcolor{orange}{\overset{rd}\Longrightarrow}} \def\b{\textcolor{green}{\overset{b}\rightsquigarrow}} \def\rf{\textcolor{green}{\mathsf{rf}}} \def\co{\textcolor{orange}{\mathsf{co}}} \def\fr{\textcolor{purple}{fr}} \def\br{\textcolor{purple}{br}} \def\po{\mathsf{po}} \def\porf{\po\rf} \def\init{\mathsf{init}} \def\next{\mathsf{next}} \def\Event{\mathsf{Event}} % \def\wwrr{\mathsf{w+w+rr}} \def\R{\mathsf{R}} \def\W{\mathsf{W}} \def\Previous{\mathsf{Previous}} \]

摘要

动态偏序约简（DPOR）通过探索并发程序的所有交错直至某种等价关系（例如 Mazurkiewicz 迹等价）来验证并发程序。这样做涉及空间和时间之间的复杂权衡。现有的 DPOR 算法要么是探索最优的（即仅精确探索每个等价类的交错），但可能使用程序大小的指数内存，要么保持多项式内存消耗，但可能会探索指数级的许多冗余交错。

在本文中，我们表明可以两全其美：在线性内存消耗的情况下探索每个等价类的确切一个交错。我们的算法 TruSt 在 Coq 中形式化，不仅适用于顺序一致性，还适用于满足一些基本假设的任何弱内存模型，包括 TSO、PSO 和 RC11。此外，TruSt 的可并行性令人尴尬：它的不同探索选项没有共享状态，因此可以完全并行探索。因此，TruSt 在内存和/或时间方面优于最先进的技术。

作者：

摘要

顺序一致性是多处理器内存系统中使用最广泛的正确性条件。本文研究了测试共享内存多处理器的问题，以确定它们是否确实提供了顺序一致的内存。它提出了对该问题的首次正式研究，该研究可应用于测试新的内存系统设计和实现、提供运行时容错以及检测并行程序中的错误。

本文提供了一系列结果来测试各种场景下共享内存的执行，将顺序一致性与线性化（另一个众所周知的正确性条件）进行比较。除了顺序一致性之外，线性化对共享内存施加了额外的限制；这些限制被证明在测试此类记忆时很有用。

摘要

本文介绍了使用 Github Actions 对 Hexo + Github Pages 博客进行自动部署的方案。考虑到几个月以来 Github 对 HTTPS 协议的限制，本文也列举了笔者的一些失败的实验经历，以供避雷。

关键词：Github Actions，Hexo，Github Pages

为什么要自动部署？

将部署任务从 PC 端转移到云端（例如 Github）的好处包括：

摘要

数据库论文中有许多数学表达式和离散数学概念，本文以蚂蚁老师 2021Spring 的离散数学为大纲，总结了常用的离散数学基础知识，以供参考。

离散数学概论

三个公理系统：逻辑、集合论、抽象代数（群论）。

逻辑

\[ \def\Var{\mathsf} \def\Val{\mathsf{Val}} \def\OpId{\mathsf{OpId}} \def\Op{\mathsf{Op}} \def\read{\mathsf{read}} \def\write{\mathsf{write}} \def\reads{\mathsf{reads}} \def\writes{\mathsf{writes}} \def\checkSER{\mathsf{checkSER}} \def\size{\mathsf{size}} \def\width{\mathsf{width}} \def\checkSER{\mathsf{checkSER}} \def\Comm{\mathsf{Comm}} \def\SER{\mathsf{SER}} \def\SI{\mathsf{SI}} \def\PC{\mathsf{PC}} \def\CC{\mathsf{CC}} \def\RC{\mathsf{RC}} \def\RA{\mathsf{RA}} \def\Serialization{\mathsf{Serialization}} \def\po{\mathsf{\textcolor{red}{po}}} \def\so{\mathsf{\textcolor{purple}{so}}} \def\wr{\mathsf{\textcolor{green}{wr}}} \def\co{\mathsf{\textcolor{orange}{co}}} \]

摘要

事务通过启用对共享数据的计算来简化并发编程，这些共享数据与其他并发计算隔离并且对故障具有弹性。现代数据库为事务提供了不同的一致性模型，对应于一致性和可用性之间的不同权衡。在这项工作中，我们研究了检查事务数据库的给定执行是否遵循某种一致性模型的问题。我们证明了诸如读提交、读原子和因果一致性之类的一致性模型是多项式时间可检查的，而前缀一致性和快照隔离通常是 NP 完全的。这些结果补充了先前有关可串行性的 NP 完整性结果。此外，在 NP 完全一致性模型的背景下，我们设计了多项式时间的算法，假设输入执行中的某些参数（例如会话数）是固定的。我们在几个生产数据库的背景下评估这些算法的可扩展性。

笔者修改了 DBCop 的部分代码：https://git.nju.edu.cn/EagleBear/dbcop-verifier

作者：

摘要

大多数数据库教材中明确可重复读（RR）不能防止幻读。在本文中，我们展示了 RR 在幻读下的一些表现，分析了 RR 的实现原理，并论证了为何 MySQL 的 RR 隔离级别下几乎不会出现幻读。本文内容来自南京大学软件学院刘峰老师课程《数据库开发》。

可重复读的实验

上图是可重复读隔离级别下的一个实验，事务 1 的两次查询得到的结果完全相同。看起来在这里可重复读防止了幻读，但我们其实希望读到 Dong 老师的数据。

摘要

本文介绍了在 Linux 和 Windows 系统下修改 ssh 配置文件使 ssh 协议访问 Github 时通过代理的解决方案。该方案同样适用于 ssh 访问其他网站时。

问题背景

从前天开始，Linux 台式机和 Windows 笔记本都不能对 Github 仓库进行 clone 和 push，表现为 clone 和 push 时链接超时。推测是网络环境发生变化导致网路不通。但浏览器此时可以正常访问 Github 和 google 等网站。

Github 目前已经不支持通过 http 协议进行 clone，只有 ssh 协议可行。笔者尝试使 ssh 协议通过代理。

摘要

IPADS 发表了与 Ad Hoc 事务相关的文章共三篇，内容基本相同。其中第三篇内容最为详细。

1. Ad Hoc Transactions in Web Applications: The Good, the Bad, and the Ugly | Proceedings of the 2022 International Conference on Management of Data (acm.org)
2. Ad Hoc Transactions: What They Are and Why We Should Care | ACM SIGMOD Record
3. Ad Hoc Transactions through the Looking Glass: An Empirical Study of Application-Level Transactions in Web Applications | ACM Transactions on Database Systems

为什么需要临时事务

数据库事务无法满足 Web 应用的要求：

摘要

Web 应用程序中的许多事务都是在应用程序代码中临时构建的。例如，开发人员可能会显式地使用锁定原语或验证程序来协调关键的代码片段。我们将应用程序代码协调的数据库操作称为临时事务。到目前为止，人们对它们知之甚少。本文介绍了对临时事务的第一个综合研究。通过研究 8 个流行的开源 Web 应用程序中的 91 个临时事务，我们发现（i）每个研究的应用程序都使用临时事务（每个应用程序最多 16 个），其中 71 个扮演关键角色；（ii）与数据库事务相比，临时事务的并发控制更具灵活性；（iii）临时事务容易出错——其中 53 个具有正确性问题，其中 33 个由开发人员控制；（iv）临时事务通过利用访问模式等应用程序语义来提高争议工作负载的性能的潜力。基于这些信息，我们讨论了临时事务对数据库研究界的影响。

INTRODUCTION

今天，web 应用程序通常使用数据库系统来持久化大量数据，因此需要协调并发数据库操作以正确性。一种常见的方法是使用数据库事务。Transactions 通过将并发数据库操作封装成单独的工作单元来隔离并发数据库操作。另一种广泛采用的方法是使用对象关系映射（ORM）框架提供的不变验证 API（例如，来自 Active Record [98] 的验证关键字）。使用这样的 API，开发人员在应用程序代码和 ORM 框架中明确指定不变量，例如列值的唯一性报告不变违规的错误。到目前为止，已经做了很多工作来研究和改进这两种方法[8，9，25，31，39，65，66，79，97，117，118，122]。

摘要

工程化软件开发需要对软件开发整个过程进行有效的组织和管理，由此产生了一系列软件开发组织和管理方法，其主要目的是形成一种载体，用以积累和传递关于软件开发的经验教训。然而，由于软件开发的一些天然特性（比如复杂性和不可见性）的存在，使得描述软件开发过程的软件开发与组织方法也天然地带着一定的抽象性。由此带来了很多概念上的误导和实践中的争论，影响了上述目的的达成。例如，对于究竟该如何选择和定义合适的软件开发过程以更好地满足某个特定项目的要求，目前仍然缺少可靠的手段。甚至有些面向工业界的调研报告表明：在实际软件项目开发中，过程改进（例如引入新的工具或者方法）的主要驱动力是佚闻。试图厘清软件组织与管理话题的若干核心概念，系统梳理软件组织和管理方法的特征，并且以软件发展的历史为主线，介绍软件组织与管理方法的历史沿革，整理出这种历史沿革背后的缘由。在此基础上，讨论和总结若干发现，以期为研究者和实践者提供参考。

原文链接：https://www.jos.org.cn/html/2019/1/5645.htm

背景与概念介绍

一个完整的计算机系统通常是由硬件以及运行其上的软件所组成。这其中，软件从诞生开始，其规模以及在一个完整计算机系统中所占的比重一直呈现上升趋势。类似硬件产品的“摩尔定律”（即：硬件产品的性能，每隔约 18 个月性能翻番，成本下降），软件产业也有一个类似的“摩尔定律”，即：类似功能的软件产品的规模每隔 18 个月，其规模（比如代码行）会翻倍，而用户获取该软件或者服务的代价将会下降[1]。Humphrey 收集整理了一些典型软件产品中规模（单位为千行代码）随着时间推移的变化趋势（如图 1 所示）[2]。我们从中可以发现：在一些系统软件产品（例如，IBM 的软件产品和微软 NT 产品）和应用软件产品（例如，航空领域软件系统和电视机中的嵌入式软件系统）中，软件系统的规模都随着时间的推移呈现出明显的上升趋势。“摩尔定律”给软件系统的开发和维护带来很多负面影响：首先，软件规模的不断扩大，会使得软件开发益发困难，由此带来成本超支、交付延后以及质量低劣等问题；其次，为了缓解摩尔定律的影响，尤其为了尽可能地避免收益下降，软件供应商还需尽快交付产品或者服务，这将使得前述由于规模扩大所带来的影响更加突出。此外，如果考虑到软件在一个计算机系统中的比重也在不断增加，那么软件行业的“摩尔定律”对整个计算机系统的研发和交付的影响也将逐渐增加，进而对由“软件定义的世界”的社会生活各个方面带来巨大影响。