Closed neverchanje closed 5 years ago
Efficient Distributed Memory Management with RDMA and Caching:
GAM:使用 RDMA 实现的 shared memory 系统,与 shared nothing 相对。 unique memory model 能够让开发者不需要重写代码。
snooping-based cache coherence: https://www.wikiwand.com/en/Bus_snooping directory-based cache coherence: https://www.wikiwand.com/en/Directory-based_cache_coherence
Scalable Replay-Based Replication For Fast Databases
对高性能数据库做 replication 的优化。内存型数据库通常能支撑超高 TPS,但 backup 节点可能会跟不上,另外考虑到一个背景:磁盘的升级往往很容易,网络的升级通常很困难;所以 replication 应该尽可能减少 network traffic。
优化1. 事务如何写日志?oltp 下 input 通常远小于 output,所以 replication 只发 input。
SQL Statement Logging for Making SQLite Truly Lite
使 SQLite 的 IO 开销更小。
[Stylus: A Strongly-Typed Store for Serving Massive RDF Data]
RDF 是 schemaless 的。Stylus 使用强类型存储模型使得 RDF 的存储和查询更高效。
Experimental Analysis of Distributed Graph Systems
对几个图数据库进行对比评测(Hadoop, HaLoop, Vertica, Giraph, GraphLab (PowerGraph), Blogel, Flink Gelly, and GraphX (SPARK))。
Streaming Graph Partitioning: An Experimental Study
现有对图计算进行分片的方法是先离线处理图结构,之后再进行分片。由于离线处理对近实时业务不友好,领域内对流式图分片有需求,但该问题尚未被探索。
Exploiting Coroutines to Attack the “Killer Nanoseconds”
Analyzing the Impact of System Architecture on the Scalability of OLTP Engines for High-Contention Workloads
顾名思义,研究系统架构对 OLTP 事务引擎在高并发场景(in-memory OLTP)下的影响。 这其中的系统架构包括了:
share-everything:事务处理需要有全局唯一锁(悲观锁),或者是全局时间戳,这种方案可扩展性差
Data oriented transaction execution (DORA):建立 data->thread 的唯一映射,想要访问某个数据,就必须去相对应的线程下执行。(pegasus hashkey,但需要维护)
Partitioned Serial Execution:数据被分成多个 partitions,对一个 partition 的每次请求,都只会由一个 cpu core 处理,所以能保证单 partition 事务不加锁,跨 partition 的事务(multi-sited transaction)使用锁。
Delegation:在 Partitioned Serial Execution 的基础上更为激进,各节点的元数据也是 share-nothing 的,即使在同一 server 进程内,各 partition 也被视作独立的分布式节点,节点间通信使用 message passing(Anna,但 Anna 是 kv 系统)
需要注意的是,其中所谓 share-nothing 的架构通常针对的是 Transaction Manager (TM) 与 Process Manager (PM) 两个模块,其他模块并不一定是 share-nothing,例如 Client Communications Manager (CCM),即 server 的请求分派器(replica_stub) 和 the Relational Query Processor (QP)。 上面这些名词来自著名 paper:Architecture of a Database System.
replica_stub
Trireme, 同时实现四种 OLTP 引擎,用于比较它们的性能。然而作为极致的理论研究, malloc 并非是 share-nothing 的。为此 Trireme 也实现了 per-thread-heap。
malloc
使用 YCSB 作为 benchmark 方案。
Interleaving with Coroutines: A Practical Approach for Robust Index Joins
在 SAP HANA 上使用 coroutines 优化 index join。
Filter Before You Parse: Faster Analytics on Raw Data with Sparser 在 mison 的基础之上做的研究。 Mison: A Fast JSON Parser for Data Analytics mison 来自 vldb 2017,本质思想在于 “push down both projections and filters into the parser”,即一边解析 json,一边进行查询,换句话说就是,不完全解析 json 数据就能够查询特定项,从而加速数据分析的效率。 开源实现有:pikkr: https://github.com/pikkr/pikkr
PolarFS: An Ultra-low Latency and Failure Resilient Distributed File System for Shared Storage Cloud Database
结合 RDMA,NVMe, SPDK + Parallel Raft 的分布式文件系统,写延时几乎与本地 SSD 文件系统持平。PolarFS 是 PolarDB 的 “存储计算分离” 架构中的存储层。
如果 GFS 教会我们如何实现 Scalability,PolarFS 则教会我们如何实现 low latency。
低延时
FusionInsight LibrA: Huawei’s Enterprise Cloud Data Analytics Platform
华为的 FI-MPPDB,5 年前(14年)从原型起步至今广泛应用,面对中国市场设计,用户需求驱动。
F1 Query: Declarative Querying at Scale
F1 已经从一个只支持 Spanner 和 Mesa 的 SQL 查询引擎进化到了能同时支持 OLAP,OLTP,ETL,并且同时支持多种存储引擎(Spanner,BigTable,Google Spreadsheets)的 SQL 查询平台。新的名字叫 F1 Query。
得益于 Google Jupiter 数据中心网络,F1 能够将存储与计算分离,同时又保证访问远程存储的延时与吞吐与本地存储基本一致。
查询分为
多存储支持
成熟的系统
Accordion: Better Memory Organization for LSM Key-Value Stores Accordion 手风琴
它同时也是一个已经登陆 HBase 2.0 的新 feature: In-Memory Compaction。
很多时候写吞吐过大,memtable 的 GC 会阻塞写,形成 ”write stall“。但如果不做 GC,读性能有又会受影响。因为每次读都需要扫所有 memtable 和 L0。
Accordion 的解决方案是在 memtable flush 之前,提前做 compaction。这样既能够容忍大量写吞吐,读路径也能缩短。
active segment | flat segment 1 | flat segment 2 | flat segment 3 |
OLTPShare: The Case for Sharing in OLTP Workloads 在 OLTP 上做资源共享(resource sharing)。
Bubble Execution: Resource-aware Reliable Analytics at Cloud Scale
Query Execution 领域内一直有两种方案:Batch Execution 和 Gang Execution。
Efficient Distributed Memory Management with RDMA and Caching:
GAM:使用 RDMA 实现的 shared memory 系统,与 shared nothing 相对。 unique memory model 能够让开发者不需要重写代码。
snooping-based cache coherence: https://www.wikiwand.com/en/Bus_snooping directory-based cache coherence: https://www.wikiwand.com/en/Directory-based_cache_coherence
Scalable Replay-Based Replication For Fast Databases
对高性能数据库做 replication 的优化。内存型数据库通常能支撑超高 TPS,但 backup 节点可能会跟不上,另外考虑到一个背景:磁盘的升级往往很容易,网络的升级通常很困难;所以 replication 应该尽可能减少 network traffic。
优化1. 事务如何写日志?oltp 下 input 通常远小于 output,所以 replication 只发 input。
SQL Statement Logging for Making SQLite Truly Lite
使 SQLite 的 IO 开销更小。
[Stylus: A Strongly-Typed Store for Serving Massive RDF Data]
RDF 是 schemaless 的。Stylus 使用强类型存储模型使得 RDF 的存储和查询更高效。
Experimental Analysis of Distributed Graph Systems
对几个图数据库进行对比评测(Hadoop, HaLoop, Vertica, Giraph, GraphLab (PowerGraph), Blogel, Flink Gelly, and GraphX (SPARK))。
Streaming Graph Partitioning: An Experimental Study
现有对图计算进行分片的方法是先离线处理图结构,之后再进行分片。由于离线处理对近实时业务不友好,领域内对流式图分片有需求,但该问题尚未被探索。
Exploiting Coroutines to Attack the “Killer Nanoseconds”
Analyzing the Impact of System Architecture on the Scalability of OLTP Engines for High-Contention Workloads
顾名思义,研究系统架构对 OLTP 事务引擎在高并发场景(in-memory OLTP)下的影响。 这其中的系统架构包括了:
share-everything:事务处理需要有全局唯一锁(悲观锁),或者是全局时间戳,这种方案可扩展性差
Data oriented transaction execution (DORA):建立 data->thread 的唯一映射,想要访问某个数据,就必须去相对应的线程下执行。(pegasus hashkey,但需要维护)
Partitioned Serial Execution:数据被分成多个 partitions,对一个 partition 的每次请求,都只会由一个 cpu core 处理,所以能保证单 partition 事务不加锁,跨 partition 的事务(multi-sited transaction)使用锁。
Delegation:在 Partitioned Serial Execution 的基础上更为激进,各节点的元数据也是 share-nothing 的,即使在同一 server 进程内,各 partition 也被视作独立的分布式节点,节点间通信使用 message passing(Anna,但 Anna 是 kv 系统)
需要注意的是,其中所谓 share-nothing 的架构通常针对的是 Transaction Manager (TM) 与 Process Manager (PM) 两个模块,其他模块并不一定是 share-nothing,例如 Client Communications Manager (CCM),即 server 的请求分派器(
replica_stub
) 和 the Relational Query Processor (QP)。 上面这些名词来自著名 paper:Architecture of a Database System.Trireme, 同时实现四种 OLTP 引擎,用于比较它们的性能。然而作为极致的理论研究,
malloc
并非是 share-nothing 的。为此 Trireme 也实现了 per-thread-heap。使用 YCSB 作为 benchmark 方案。
Interleaving with Coroutines: A Practical Approach for Robust Index Joins
在 SAP HANA 上使用 coroutines 优化 index join。
Filter Before You Parse: Faster Analytics on Raw Data with Sparser 在 mison 的基础之上做的研究。 Mison: A Fast JSON Parser for Data Analytics mison 来自 vldb 2017,本质思想在于 “push down both projections and filters into the parser”,即一边解析 json,一边进行查询,换句话说就是,不完全解析 json 数据就能够查询特定项,从而加速数据分析的效率。 开源实现有:pikkr: https://github.com/pikkr/pikkr
工业论文
PolarFS: An Ultra-low Latency and Failure Resilient Distributed File System for Shared Storage Cloud Database
结合 RDMA,NVMe, SPDK + Parallel Raft 的分布式文件系统,写延时几乎与本地 SSD 文件系统持平。PolarFS 是 PolarDB 的 “存储计算分离” 架构中的存储层。
如果 GFS 教会我们如何实现 Scalability,PolarFS 则教会我们如何实现 low latency。
低延时
FusionInsight LibrA: Huawei’s Enterprise Cloud Data Analytics Platform
华为的 FI-MPPDB,5 年前(14年)从原型起步至今广泛应用,面对中国市场设计,用户需求驱动。
F1 Query: Declarative Querying at Scale
F1 已经从一个只支持 Spanner 和 Mesa 的 SQL 查询引擎进化到了能同时支持 OLAP,OLTP,ETL,并且同时支持多种存储引擎(Spanner,BigTable,Google Spreadsheets)的 SQL 查询平台。新的名字叫 F1 Query。
得益于 Google Jupiter 数据中心网络,F1 能够将存储与计算分离,同时又保证访问远程存储的延时与吞吐与本地存储基本一致。
查询分为
多存储支持
成熟的系统
Accordion: Better Memory Organization for LSM Key-Value Stores Accordion 手风琴
它同时也是一个已经登陆 HBase 2.0 的新 feature: In-Memory Compaction。
很多时候写吞吐过大,memtable 的 GC 会阻塞写,形成 ”write stall“。但如果不做 GC,读性能有又会受影响。因为每次读都需要扫所有 memtable 和 L0。
Accordion 的解决方案是在 memtable flush 之前,提前做 compaction。这样既能够容忍大量写吞吐,读路径也能缩短。
OLTPShare: The Case for Sharing in OLTP Workloads 在 OLTP 上做资源共享(resource sharing)。
Bubble Execution: Resource-aware Reliable Analytics at Cloud Scale
Query Execution 领域内一直有两种方案:Batch Execution 和 Gang Execution。