The Paper List on Design and Implmentation of System Software
I am interested in the intersection of machine learning and systems. Welcome to submit a pull request!
The workload features include workload types, workload shifts, workload patterns (e.g., periodic pattern and arrival patterns), and the performance is measured by one of the metrics (response time, throughput, reliability, etc.) or their combination. And I think workload pattern should includes workload access pattern. Therefore, I have collected and organized the following list, and will analyze these papers in detail later.
our approach uses the logical composition of queries in the workload rather than the amount of physical resources used for query execution. - Query-based Workload Forecasting for Self-Driving Database Management Systems. (So, this means that workload has twofolds: 1. the logical composition of workload; 2. the resources used for query execution)
Workload features may include:
Tasks include for demonstrate workload model effectiveness:
Tiresias: enabling predictive autonomous storage and indexing VLDB 2022 CCF A 🌟🌟🌟🌟🌟
MorphoSys: Automatic Physical Design Metamorphosis for Distributed Database Systems PVLDB 2020 CCF A 🌟🌟🌟🌟🌟
Proteus: Autonomous Adaptive Storage for Mixed Workloads SIGMOD 2022 CCF A 🌟🌟🌟🌟🌟
Workload Time Series Analysis
Morkov Modeling for Workload Shift 🌟 ❌
Encoder to Vector 🌟🌟🌟🌟🌟
Workload Synthesis 🌟🌟
Next Query
Workload Arrival rate and Trend Pattern Forecasting 🌟🌟🌟🌟🌟🌟🌟
Intelligent Automated Workload Analysis for Database Replatforming SIGMOD 2022 Indursty track CCF A 🌟🌟 Expert Experience + Feature Cost Modeling
Active Learning for ML Enhanced Database Systems SIGMOD 2020 research paper CCF A
SWIRL: Selection of Workload-aware Indexes using Reinforcement Learning EDBT 2022 research paper CCF B
Facilitating SQL Query Composition and Analysis SIGMOD 2020 CCF A
Performance and Resource Modeling in Highly-concurrent OLTP Workload
APOLLO: Automatic Detection and Diagnosis of Performance Regressions in Database Systems PVLDB 2019 CCF A
Diagnosing Root Causes of Intermittent Slow Queries in Cloud Databases PVLDB 2020 CCF A
SQLCheck: Automated Detection and Diagnosis of SQL Anti-Patterns SIGMOD 2020 CCF A
A Top-Down Approach to Achieving Performance Predictability in Database Systems SIGMOD 2017 CCF A
DBSherlock: A Performance Diagnostic Tool for Transactional Databases SIGMOD 2016 CCF A
Adaptive Data Storage and Placement
Index
data storage format
Weaving Relations for Cache Performance 本文充分吸取了 NSM 和 DSM 数据组织模型的优势,提出了对缓存更加友好的 page 内数据组织方式 PAX,该部分 story 参见 https://github.com/Ethanzjp/DBMSology/blob/master/PAXStory.md
F1 Lighting: HTAP as a Service
Sorting
Architecture
Are You Sure You Want to Use MMAP in Your Database Management System? andy 在 2020 年的讲座中说自己要写一篇关于 MMAP 的文章,2 年后终于见面了,文章发表在 CIDR 2022 上,7 页很短,但是内容很丰富,结论是 不要在数据库中使用 mmap 代替手动 buffer pool 管理。PPT
To BLOB or Not To BLOB: Large Object Storage in a Database or a Filesystem?
本文主要讲述对于Binary Lager OBject(BLOB)究竟应该存储在database中使用DBMS管理还是应该用Filesystem来管理,即究竟BLOB应该作为一个数据库record还是file?
文章支持当文件系统是NTFS,DBMS是SQL Server 2005时,当文件大小下雨256KB时,DBMS管理更加高效,当对象大于1MB时,采用filesystem管理更加高效。文章还提出数据库
设计者应该考虑加入文件系统的碎片整理过程。注:现今,当我们在存储视频等比较大的文件时,尽量不要直接用BLOB存储在数据库中,而是应该用filesystem管理,在数据库中可用只存储文件链接。
Architecture of database system
数据库体系结构最好的文章。作者图灵奖得主Stonebraker。包括processes model、query processing、storage and transaction、others,其中的事务存储部分严格区分了lock和latch,一个是higher level的概念,一个是lower lavel的概念。这两个改变在实现buffer pools时非常重要,latch在使用上,实际上用mutex来实现。lock是higher level事务层面用到的抽象。
The Snowflake Elastic Data Warehouse (sigmod 2016)
本文是一种标准的shared disk的架构。体现在两个方面:1、(1)整体架构分为三层:Storage layer由Amazon S3提供,仅仅能够提供put、get、delete操作,并且put操作只能是全量(in full)操作。get操作可以指定文件读取的范围。(2)stateless VM是,之所以说该层是stateless是因为:实际上该层的disk是cache的作用,用于系统的冷启动问题。该层可以和storage层独立扩展。(3)cloud service层,该层提供传统的数据库服务:事务管理、元数据管理(元数据持久到S3上),查询解析,查询优化等数据库传统的功能,但是不提供索引。列存数据库的列其实本身就是索引。底层为了避免全文件扫描,还实现了zone map(google、oracle对zone map可能拥有商标权)可以实现skip scan。该层也是stateless。2、online-upgrade时,实际上VMs层也是shard disk的架构,这样能够保证不同版本的系统在读取数据时,能够访问到相同的热数据。snonflaker实现了很多数据库中的经典技术,如MVCC并发控制方法(请注意MVCC不是并发控制协议,它需要和其它的如2PC、TO结合才能称为协议)、time travelling这是数据仓库中比较有用的技术,能够访问指定时间段的数据,snowflake指定只能访问90天以内的数,不过你能够自行实现backup、基于MVCC的SI隔离级别,在此基础之上保证了ACID事务等等。
FlashKV Accelerating KV Performance with Open-Channel SSDs (2017)
MapReduce:Simplified Data Processing on Large Clusters
MapReduce一文确实是一篇极好的文章,按照其思想,它的输入输出全部存储在GFS(开源实现下,将数据存储在HDFS之上)上。从用户的角度看,不需要考虑load balance、communication等,只需要写业务
端程序,也就是只需要设计合适的map和reduce函数即可,当然为了减少network communication代价,也可以写combiner function,实际上map和reduce阶段的操作就是两次hash。map tasks+reduce tasks= job,
也就是说多个map tasks 和 多个reduce tasks构成一个job,map生成的intermmidiate key/values会存储在当前map节点的non-volatile存储设备上。接着master会调度将这些结果重新shuffle,然后将结果
调度给reduce tasks,尽量保证不同reduce任务之间减少network communication。
GFS: The Google file system
Google经典三篇文章之一,GFS是google真正对工业界在数以千计的廉价商业化机器上实现的分布式文件系统,其设计包含一个master节点(为了保证reliable等特性,该机器通常会有replicas),一次写操作
成功不仅需要在所有的chunkserver上写入数据,还需要master节点的operation logs落盘,master节点与传统单机DBMS的设计一样。master节点不真实存储任何client数据,client数据全部存储在chunkserver上,
master节点保存三件事情:(1)filename -> array of chunk handler, (2)chunkhandler -> list of chunkserver, (3)logs and checkpoints,可以看出第一点和第二点主要是为了能够找到文件的真实位置,
第三点主要是为了实现可靠性和可恢复性。当client节点将请求发送到master之后,master会将用户请求的所在的chunkserver位置发送给client,并且client端会缓存这些信息,以便于当client再次请求相同的数据时,
不需要再次请求master,那么此时就有一个数据的一致性问题,一旦映射关系发生变化(比如某个chunkserver fails),这个cache信息就会失效,或者设计一个lease,给定时间窗口内有效,一旦过时cache就立即
停止服务。在GFS中假设发生追加写操作的可能性远远大于随机写操作。
Bigtable: A Distributed Storage System for Structured Data
Google经典三篇文章之一,在Bigtable基础之上,Google实现了leveldb。bigtable实际上是一张”宽表“,我们知道,在经典的关系数据库范式理论中,首先数据库的表设计应该满足第一范式,也就是表中的属性不能再分,
但是Bigtable使用了column family的特性,使得表的列属性实际上是可分的,同一个column family中可以有多个不同的列,这样子构成了bigtable的宽表模式。row-key按照字典序排序,并且row-key组合成了bigtable的tablet,每个tablet中
可能包含很多个row-key,然后这些在内存中被组织成为memtale,当memtable达到一定的大小以后,就变为immutable memtable,接着被compaction成为SSTable,SSTtable也会被major compaction,当生成更大的SSTable之后,就会删除
原来的SSTable,所以这个过程实际上存在非常多的写放大。为了出现fails时能够恢复,还存在了redo log,这一设计完全是从关系数据库的ARIES中迁移而来。最后还介绍了不少优化,我认为想要真正读懂这个文章
的所有优化,尽量结合着leveldb的源码,并做一些实验。
Dynamo: Amazon’s Highly Available Key-value Store
Dynamo是Amazon在2007年SOSP上发表的关于键值对存储的分布式系统,主要强调高可用、强扩展,使用读操作之后的最终一致性方案,这在2020年看来并不是一个好的选择,
强一致性仍然是当前的需求。但是这不影响Dynamo成为高引用文章,其中很多的技术都成为很多数据库设计的规范。Dynamo的强扩展性(scale-out)采用了consistent hashing,
当在其中增加或者删除node时,不要执行reshuffle(rehash)的操作,当然consistent hasing不是Dynamo提出的技术,早在2000年就提出consistent hashing。
读操作和写操作都松散的希望能得到系统中至少半数点的回应,但是考虑到可能存在网络分区等错误,所以仅仅是一个松散的建议,在写操作时,如果某个ring中的节点失去了联系,
那么就讲备份数据写到下一个ring中,并记录好,等待该节点恢复后,再将数据拷贝过去。
Dynamo在读操作也希望能有半数以上的节点返回数据,读出的数据会带有数据版本(文章中称为vector clock),如果发现数据不一致,允许在系统层面进行规约,但是不强制,
因为Dynamo允许业务逻辑层处理数据的不一致性(比如在Amazon中,用户的购物车可以由用户自己来维护其一致性)。其中Grossip-based的协议实现信息在节点中的传播,
这些古老的技术都在Dynamo得到了很好的应用。可以说Dynamo是结合了很多优秀实现技术的一个原型产品,堪称教科书式的实现。
Amazon DynamoDB: A Scalable, Predictably Performant, and Fully Managed NoSQL Database Service
(SPARK)Resilient Distributed Datasets:A Fault-Tolerant Abstraction for In-Memory Cluster Computing
Granularity of Locks and Degrees of Consistency in a Shared Data Base
jim gray首次在提出granularity of lockable object,也就是被锁对象的粒度,粒度这个词很抽象,在这里granularity = size指的是被锁对象的大小。该文提出了intension lock,使得在系统的并发度和overhead of lock manager
上做了trade-off,本质上,在被锁对象层次结构下,意向锁的提出了解决了这样两个问题:(1)如果low level层次对象加了锁,那么其祖先节点现在想要做某个查询,如何快速判断是否能够获取到锁执行相应的操作?(2)如果high level
节点获取了某种锁,接着另外一个事务想要在其孩子节点上做某些操作,是否能够直接获取到某种锁并执行相应的操作?因为本文提出了意向锁+root到leaf的加锁顺序,规范了整个lock protocol。
Spark SQL: Relational Data Processing in Spark
Spanner: Google’s Globally-Distributed Database
Spanner: Becoming a SQL System
F1: A Distributed SQL Database That Scales
Amazon Aurora: Design Considerations for High Throughput Cloud-Native Relational Databases
HadoopDB: An Architectural Hybrid of MapReduce and DBMS Technologies for Analytical Workloads or Integration of LargeScale Data Processing Systems and Traditional Parallel Database Technology
Soft Updates: A Solution to the Metadata Update Problem in File Systems
Rethinking Database High Availability with RDMA Networks
CockroachDB: The Resilient Geo-Distributed SQL Database (SIGMOD 2020)
C-Store: A Column-oriented DBMS
Consistency or (consensus)
Time, Clocks and Ordering of events
Lock-free data structure
Query processing or query plan
Benchmark
Recovery
NUMA
Serverless
In-memory database
Survey
Transactions
Architecture
Properties of Optane DIMM
Multi-Version Concurrency Control of Main-Memory DBMS(Protocols)
MISC Code As Design