Java架构师问题总结

常见面试流程

  1. 技术相关

    • java语言(基本、容器、多线程、异常处理、JVM)
    • 设计模式
    • Spring
    • MySQL、Redis等(JDBC)
    • 前端相关
    • Shell相关
    • 算法题
  2. 项目相关

Java语言基础

面向对象

  1. 绝对不能在构造函数中调用会被Override的函数
  2. QA:builder模式与Config类(InstanceSpec)取舍? builder需要创建静态类
  3. QA:构造函数什么时候可以抛异常?
  4. Q:init私有方法什么时候使用? A:构造方法里面禁止加入任何业务逻辑,如果有初始化逻辑,请放在init方法中

String使用

  1. 判断是否相等绝对不能直接使用”==”进行,可以使用equals方法
  2. 判断是否为空: StringUtils.isBlank()Str.isEmpty()Str.length()==0
  3. 循环体内,字符串的联接方式,使用 StringBuilder的append方法进行扩展

集合使用

  1. Array初始化
    1
    new ArrayList<Element>(Arrays.asList(array))

使用工具类Arrays.asList()把数组转换成集合时,不能使用其修改集合相关的方法,它的add/remove/clear方法会抛出 UnsupportedOperationException异常。

  1. 使用集合转数组的方法,必须使用集合的toArray(T[] array),传入的是类型完全一样的数组,大小就是list.size()

  2. ArrayList的subList结果不可强转成ArrayList,否则会抛出ClassCastException

  3. QA:集合接口的区别 list collection hashmap

  4. 不要在foreach循环里进行元素的remove/add操作。remove元素请使用Iterator方式,如果并发操作,需要对Iterator对象加锁

  5. 高度注意Map类集合 K/V 能不能存储 null 值的情况

    | 集合类 | Key | Value | Super | 说明 |
    | —————– | ——— | ——— | ———– | —– |
    | Hashtable | 不允许为 null | 不允许为 null | Dictionary | 线程安全 |
    | ConcurrentHashMap | 不允许为 null | 不允许为 null | AbstractMap | 分段锁技术 |
    | TreeMap | 不允许为 null | 允许为 null | AbstractMap | 线程不安全 |
    | HashMap | 允许为 null | 允许为 null | AbstractMap | 线程不安全 |

  6. 利用 Set 元素唯一的特性,可以快速对一个集合进行去重操作

Exception处理

  1. 标准Exception分为两种expcetion,一种继承自RunTimeException,不需要方法捕捉,比如NullPointerException,IllegalStateException;另一种必须catch或throws,比如InterruptedException
  2. 推荐使用Preconditions.checkNotNull等工具
  3. catch后的代码仍然会执行,返回值与抛出异常都需要满足匹配,try中抛出的异常就会被对应catch捕获,上一个catch中抛出也会被下一个catch捕获,如果分支继续抛异常来结束那么该分支可以忽略返回值
    处理方法:1. 异常转义;2. 异常链接getCause
  4. 单元测试函数应该抛出任何异常
  5. 利用jdk7新语法自动关闭文件流

    1
    2
    3
    try(InputStream is = new FileInputStream){
    //文件操作
    }
  6. 对No such method error处理:打印出具体绑定类

    1
    <Object>.class.getProtectionDomain();

注释处理

  1. Bean注入
    @Autowired
    ApplicationContext ac;
    lockAnnotation = (LockAnnotation)ac.getBean(“LockAnnotation”)
  2. @Service与@Resouce可以配合使用
    http://bit1129.iteye.com/blog/2114126
  3. AOP
    http://www.xdemo.org/springmvc-aop-annotation/

多线程

  1. 后台定时任务

    1
    2
    3
    4
    5
    //start
    ScheduledExecutorService excutor = Excutor.newSingleThreadScheduledExecutor();
    excutor.scheduleWithFixedDelay(runnable, time);
    //end
    excutor.shutdown(); //excutor.shutdownNow();
  2. 线程池

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    List<Future<Object>> threads = Lists.newArrayList(); 
    ExcutorService excutor = Excutors.newCachedThreadPool();
    Future<Object> t = executor.submit(new Callable<Object>() {
    @Override
    public Object call() throws Exception {
    //do sth here!
    return null;
    }
    });
    threads.add(t);
    for(Future<Object> t: threads)
    t.get();
  3. CountDownLatch与Semaphore使用

    CountDownLatch设置初始值,调用wait()方法会阻塞直到被notify()方法唤醒;调用countDown()来减少值;创建时不会阻塞,需要调用await()阻塞直至计数值为0;该机制被设计为只会触发一次,因此不会有方法来还原初始值。

    Semaphore设置初始值,调用acquire()方法减少该值否则阻塞直至计数值大于0,调用release(num)来增加值,调用availablePermits()判断是否阻塞

  4. 单例模式注意使用double check方法

1
2
3
4
5
6
7
8
9
10
public Helper getHelper() {
if (helper == null) {
synchronized(this) {
if (helper == null) {
helper = new Helper();
}
}
}
return helper;
}

Q:该模式有失效的可能? A:可参考 The “Double-Checked Locking is Broken” Declaration,推荐问题
解决方案中较为简单一种(适用于 JDK5 及以上版本),将目标属性声明为 volatile 型。

  1. executor 重要的三个参数含义
    corePoolSize, maxmumPoolSize, [keepAliveTime], BlockingQueue

  2. 多线程的方法

JVM

  1. 有哪些垃圾回收器 优缺点
  2. 四种导致full gc场景
  3. 持久代满了,gc不成功则out of memory
  4. 旧生代满了
  5. 新生代向S0和S1转移数据,S0和S1向旧生代转移数据,两边内存都设置较小,持续进行导致
  6. 直接system.gc
  7. Q: 原子变量实现? 设置unsafe 内存交换
  8. 给 JVM 设置-XX:+HeapDumpOnOutOfMemoryError 参数,让 JVM 碰到 OOM 场景时输出 dump 信息。

JDBC

  1. Q: 何时使用乐观锁 悲观锁 出现场景,jdbc事务提交使用哪种锁(一般使用DB的悲观锁)

Spring

调优:tcp窗口,事务大小

  1. 常用模块
    aop, aspects, beans, core, context, expression, orm, jdbc, jms, tx, test, web, webmvc
  2. 主要接口

  3. 五种事务传播性Propagation
    required, supports, mandatory, requires_new, not_supported, never, nested

netty

结构 lf缺陷

MySQL

  1. 设置AUTO_INCREMENT
    http://www.searchdatabase.com.cn/showcontent_38510.htm
  2. 使用datetime或timestamp类型,查询范围写法:send_time <= ‘2015-09-24 15:24:16’

    区别:首先 DATETIM和TIMESTAMP类型所占的存储空间不同,前者8个字节,后者4个字节,这样造成的后果是两者能表示的时间范围不同。前者范围为1000-01-01 00:00:00 ~ 9999-12-31 23:59:59,后者范围为1970-01-01 08:00:01到2038-01-19 11:14:07。所以可以看到TIMESTAMP支持的范围比DATATIME要小,容易出现超出的情况.
    其次,TIMESTAMP类型在默认情况下,insert、update 数据时,TIMESTAMP列会自动以当前时间(CURRENT_TIMESTAMP)填充/更新。
    第三,TIMESTAMP比较受时区timezone的影响以及MYSQL版本和服务器的SQL MODE的影响
    所以一般来说,我比较倾向选择DATETIME,至于你说到索引的问题,选择DATETIME作为索引,如果碰到大量数据查询慢的情况,也可以分区表解决。
    最佳实践: 只要用int类型存格林时间的unix timestamp值就好了,使用TIMESTAMP主要是为了方便记current_timestamp

  3. 使用txt类型取代nvarchar
    SQLserver 中使用nvarchar存储变长unicode字符串

  4. 使用tinyint(8)或bool(1)取代bit类型, int(32), bigint(64)
  5. DEFAULT 为0,则可以查询’’(空字符串);DEFAULT为NULL,则查询’’(空字符串)不匹配
  6. 业务ID自增设计
    insert msgId into [table] value(select max(msgId) from [table] + 1)
    这里max函数会导致锁表
    解决方法:单记一个max version表,利用行锁进行多线程同步
  7. 当发生Too many connections时,即使是DBA也无法登录到数据库,一般的做法是修改配置文件的max_connections参数,然后重启数据库,这样业务就有几秒钟的中断。
    还有一个hack的方法,用过gdb直接修改mysqld内存中max_connections的值,具体做法如下:
    gdb -ex "set max_connections=5000" -batch -p 'pgrep -x mysqld'
  8. 小数类型为 decimal,禁止使用 float 和 double。如果存储的数据范围超过 decimal 的范围,建议将数据拆成整数和小数分开存储。
  9. 表必备三字段:id, gmt_create, gmt_modified。
  10. 不得使用外键与级联,一切外键概念必须在应用层解决。更禁止使用存储过程。

JBOSS

调优方法

  1. connector 改为Nio
  2. 使用G1回收器,+UseG1GC 提供一种计算方法预期最大停止时间
  3. 调整内存使用

Nginx

运用功能 模块实现 核心组件 upstream配置

  1. 高并发服务器建议调小 TCP 协议的 time_wait 超时时间,变更/etc/sysctl.conf 文件:net.ipv4.tcp_fin_timeout = 30

Redis

  1. 连接数
  2. 集群设置 集群算法

Curator

  1. 使用InterProcessMutex中的RevocationListener因为在另一个专用线程因此没法直接调用release释放,Revoke唤醒需要使用对应的lock节点而不是目录
    QA:这个设计很奇怪,按常理revoke应该调用在lock的path上然后自动通知当前获得锁的lock结构,并且应该有方法允许释放【可能状态比较难统一】
  2. 2.9版本之后可以自动清理锁目录,需要设置container.checkIntervalMs
  3. 共享锁实现
    http://www.tuicool.com/articles/yQBVfeA
  4. start方法只能在初始化后调用一次,close调用后只能销毁

Dubbo

  1. 使用transient关键字保证成员不被串行化

实现思路

1. WS服务转RPC

分为两个难点:wsdl信息提取,RPC服务端的API生成
wsdl信息提取:例如从BPM提取出ReceiveMsg方法与参数
RPC服务端API生成:
http://dubbo.io/User+Guide-zh.htm#UserGuide-zh-API%E9%85%8D%E7%BD%AE
API方法所依赖的接口service与实现serviceImpl可以使用通用的泛化实现接口与实现
http://dubbo.io/Generic+Implementation-zh.htm

2. RPC服务转WS

分为两个难点:参考Dubbo客户端实现RPC客户端自动生成,WS服务端API生成
RPC信息提取:
WS服务端API生成:

Open Chain系统设计

OpenChain简介

openchain使用C#开发的分布式总账系统,有比较强的横向扩展能力,并利用比特币的区块链保证不可更改性。

常见问题

  1. openchain是一种区块链吗?
    答:不是,其不使用块这个概念,并直接使用事务链。
  2. openchain是一条侧链吗?
    答:提供了模块将openchain部署为侧链,但并非必要步骤。

部署方法

提供docker方法直接部署openchain的服务器,使用sqlite作为默认存储,运行在.NET Core和.NET Framework上面

系统架构

  1. 事务流
    openchain的服务节点可以分为两种:validator节点、observer节点:前者接收事务并进行验证,只有通过验证的才计入总账(验证规则由管理员配置);后者会下载所有通过验证的事务信息流(形成备份?)
  2. 利用区块链
    即利用公链提交事务形成hash(使用OP_RETURN)
  3. 数据结构
    使用Protocol Buffers进行客户端与服务器之间的编解码操作
  4. 总账结构
    kv结构的有层级的总账

CMU课程15-721数据库系统设计(第三周)

CMU课程15-721最新一期开课啦!

课程安排

索引技术课程(三节)介绍的技术实际跟并发控制结合很紧密,接下来讨论查询相关技术(穿插了日志技术内容)

Query Execution & Scheduling

重点介绍查询执行与调度,特别是多用户DB中查询如何并行执行

处理进程模型:

  • 进程-woker 依赖OS调度,使用共享内存,例:DB2、Postgres、Oracle;还是因为当时没有linux设计
  • 进程池 CPU缓存支持不好
  • 线程-worker DB管控调度,新DB都用这个模型规避共享内存

利用多核并发加速执行:

  • Intra-Operator 在子集上独立运行相同函数(mapreduce)
  • Inter-Operator 运行类似流水线,做一部分工作(stream)

个人补充:MySQL仍然是一个线程完成一个work

补充一点内存访问架构(实际是体系结构中重要部分,由硬件设计决定)

  • UMA:多cpu与多内存都必须走中心bus
  • NUMA:几个cpu之间组成bus,cpu与内存一一对应(目前常用架构!)

数据分配策略:

  • 内存分配与cpu绑定,参考linux的move_pages
  • 使用malloc

将查询语句变为可调度的执行计划,OLTP简单,OLAP比较难。Hyper就是一个NUMA架构下多核横向分布动态调度架构:

Morsel-Driven Parallelism: A NUMA-Aware Query Evaluation Framework for the Many-Core Age

每个核分配一个worker(并行),pull接收分配的任务,数据分布采用RR算法

Join Alogrithms I — Hashing

原先不懂为何hash join算法作为第一个项目作业,而不是在介绍这个之后再布置。后来发现实际上这里讲解的是最新研究的多核版本算法

Join Alogrithms II — Sort-Merge

Logging & Recovery I — Physical Logging

传统DB磁盘日志基于ARIES算法,使用fuzzy cp规则,管理Active Transan Table与Dirty Page Table,赋予LSN并在易失与非易失中都要维护,过程为:analysis,redo,undo。最慢的过程发生在其他事务等待log刷到磁盘。

mem DB就不需要维护Dirty Page Table,因为所有数据都在内存。undo记录也没必要存储。

实例是Silo系统,其将log,cp,恢复操作都并行化优化,论文将这些设计考虑与最终选择都讲解的非常清晰。

该系统假设每个CPU socket对应有一个存储设备。每个设备分配一个日志线程,CPU socket对应一组工作线程。日志线程每10个epoch创建一个文件,将旧日志文件重命名并记录最大epoch。日志维护两个队列:Free Buffers与Flushing Buffers。会有一个特殊日志线程跟踪最新已经持久化的epoch(即各个日志线程中持久化的epoch最大值),小于此epoch的事务信息才可以丢弃。

每个disk对应一个cp线程,该线程有可能因为分区而写多个文件(voltDB甚至直接使用MVCC的version来做cp),cp的频率。恢复也可以并行进行。使用YCSB和TPC-C测试,吞吐率损失10%,lantency没有统计。

Logging & Recovery II — Alternative Methods

讨论一下逻辑日志,内存checkpoint以及Facebook的快速恢复方法(共享内存恢复)。

OLTP中节点失效很少见(数据不大,通常<10个节点),因此比较适合使用逻辑日志,记录格式通常包括(存储方法名,输入参数,额外安全检测信息),注意逻辑日志协议设计要满足可确定性,因此需要:

  • 事务执行前顺序已经固定
  • 事务逻辑是确定的

voltDB设计日志协议:在事务运行前日志就已经记录命令,且此时顺序已经分配完毕(个人理解类似MySQL),cp操作由特殊事务进行并将系统切换为COW模式,另一个特殊线程负责扫描表并制作快照,无视cp发起后的所有变化操作;DBMS同步不需要2PC协议

CMU课程15-721数据库系统设计(第二个项目)

CMU课程15-721最新一期开课啦!

课程安排

Project #2 - Concurrent Index

实现一个支持无锁并发的BW树作为索引底层数据结构

  • PID到指针的映射表
  • 改动链
  • split/merge
  • 动态垃圾回收

论文中几个奇怪概念:

  • install CAS 即使用CAS操作来替换映射表中的项目
  • epoch机制 即使用版本号保证没有其他操作正在进行(可以执行物理删除)

实现要求:

  • 支持重复key且可以配置,如果配置为不允许则InsertEntry插入重复key的索引条目时返回false,且DeleteEntry只删除完全匹配的索引条目
  • 支持consolidation,需要考虑阈值
  • 支持split与merge,特别是并发插入与删除的情况
  • 应该有工具函数帮助测试结构完整性并可以修复,类似fsck
  • 支持动态垃圾回收,调用Cleanup函数进行物理释放,会使用GetMemoryFootprint统计内存情况
  • 支持reverse iterators并保证concurrent mutators正常工作

Profile方法

profile工具使用valgrind或perf

  1. valgrind

使用memcheck或callgrind动态检查:valgrind --tool=callgrind --trace-children=yes ./build/src/peloton -D data &> /dev/null&

  1. perf

通过收集linux的cpu周期计数实现,也支持收集其他事件
perf record -e cycles:u -c 2000

CMU课程15-721数据库系统设计(第一个项目)

CMU课程15-721最新一期开课啦!

课程安排

Project #1 - Hash Join Operator

做这个项目前必须了解几个join算法,问题是这些算法在本次课程里都没有讲解过。

1.嵌套循环连接(Nested Loops)

适用范围两个表, 一个叫外部表, 一个叫内部表。如果外部输入非常小,而内部输入非常大并且已预先建立索引,那么嵌套循环联接将特别有效率。循环嵌套连接查找内部循环表的次数等于外部循环的行数,当外部循环没有更多的行时,循环嵌套结束。

2.合并联接(Merge)

指两个表在on的过滤条件上都有索引, 都是有序的, 这样join时, sql server就会使用性能更好的Merge join算法。如果一个有索引,一个没索引,则会选择Nested Loops join算法。首先从两个输入集合中各取第一行,如果匹配,则返回匹配行。假如两行不匹配,则有较小值的输入集合+1。

3.哈希联接(Hash)

如果两个表在on的过滤条件上都没有索引, 则就会使用Hash join算法。也就是说, 使用Hash join算法是由于缺少现成的索引。

哈希匹配分为两个阶段,分别为生成和探测阶段:首先是生成阶段,将输入源中的每一个条目经过散列函数的计算都放到不同的Hash Bucket中;接下来是探测阶段,对于另一个输入集合,同样针对每一行进行散列函数,确定其所应在的Hash Bucket,在针对这行和对应Hash Bucket中的每一行进行匹配,如果匹配则返回对应的行。

同时做这个项目需要了解Peloton tile-based架构几个关键数据结构:

logical_tile设计 [backend/executor/logical_tile]

其中

  • position_lists_vector<vector<oid_t>> 用来描述tiles/colums, 例(1,2,3),(1,1,1)
  • schema_vector<LogicalTile::ColumnInfo> 用来描述logical tile的表字段组合, 会存在position_list_idx与position list对应, 例(Tile A-1 ATTR1, Tile A-1 ATTR2), (Tile A-1 ATTR3, Tile A-2 ATTR1)
  • visible_rows_vector<bool>用来描述position lists中每一行的可见性

ColumnInfo设计 [backend/executor/logical_tile]

在logical tile中用来描述一组表字段信息, 例如(Tile A-1 ATTR1, Tile A-1 ATTR2), 其中

  • position_list_idx 指回Position Lists中对应编号
  • base_tileshared_ptr<storage::Tile>指向存储Tile,直接使用指针而不是oid
  • origin_column_id 存储Tile中选择的表字段编号

ContainerTuple设计 [backend/expression/container_tuple]

用于包装logical tile中元组, 传入LogicalTile指针与元组行id(logical_tile, row_idx)

HashMapType 设计 [backend/executor/hash_executor]

用于定义hash表结构unordered_map<expression::ContainerTuple<LogicalTile>, unordered_set<pair<size_t, oid_t>, boost::hash<pair<size_t, oid_t>>>, expression::ContainerTupleHasher<LogicalTile>, expression::ContainerTupleComparator<LogicalTile>>
其中pair 表示

使用类型为vector<unique_ptr<executor::LogicalTile>>left_result_tiles_right_result_tiles_缓存
最终hash操作返回结果为vector<LogicalTile *> result使用BuildOutputLogicalTile方法(主要调用BuildSchema方法得到表字段组合)返回得到unique_ptr<LogicalTile>

CMU课程15-721数据库系统设计(第二周)

CMU课程15-721最新一期开课啦!

课程安排

并发控制课程(一共三节)已经结束,但具体细节需要结合索引技术(仍然是三节)进行讲解

Indexes I — Locking & Latching

本节就是对应用在传统B树索引上的各种锁和latch技术进行讲解

技术总结信息来自这篇文章:A Survey of B-Tree Locking Techniques

在讲解锁相关技术前,需要把B树家族的各个数据结构先总结说明一下。

B树(键值都在) -> B+树(值都在叶子节点) 其中B+树设计选择有:

  • Non-Unique索引 实现方法有1.允许键重复 2.值list
  • 变长键 实现方法有1.指针 2.节点长度可变 3.key map(即slot pages)

其他变形:

  • T-tree, 基于AVL树(不存key直接存指针),用于内存DB
  • Skip List, MemSQL完全使用以替代B+结构,实现上为一组多层list,最低层为排序单链key,每层key减半,插入时几率插入每一层;优势是省空间,无需额外平衡操作,易并发;缺点是反向查找复杂
  • Radix Tree 基树
  • MassTree
  • Fractal Tree

对索引加锁需要注意索引结构可能变化

  • lock: 事务粒度上保护索引逻辑,txn duration,可以回滚,(ex,sh,up,i)
  • latch: 线程粒度上保护索引内部实现,op duration,不需要回滚,(r,w)

因此lock-free index可以为no lock(MVCC)或no latch(cow,shadow page)

索引锁类型

  • predicate lock 在where条件上加锁,不好实现
  • key-value lock 在B树key上加锁
  • gap lock 在B树key后面gap上加锁
  • key-range lock 在B树key及后面gap上加锁
  • hierachical lock 一组key-range lock纵向上组合(IX, EX)

Indexes II — OLTP

本节先关注latch实现方法:

  • Compare&Swap CAS操作,使用__sync_bool_compare_and_swap(&M, 20, 30) 是其他实现的基础
  • Os Mutex 使用pthread_mutex_t (,about 25ns invocation)
  • Test&Set spinlock 使用std::atomic_flag(non-scalable, cpu缓存不友好)
  • Queue spinlock 使用std::atomic_flag(比mutex性能好,cpu缓存友好) lock chain
  • rw locks 可以使用spin lock实现

其中non-scalable指锁阻塞后性能不能线性增长
详细解释

个人补充:工程实践中共享对象的读写一致性方案(读写锁,COW与引用计数),引用计数并发可以使用HazardPointer解决
个人补充:spinlock vs mutex

重点讲解几个典型mem DB中OLTP索引设计:

  1. BW树(Hekaton)
  • latch free B+树
  • deltas 没有直接修改(使用额外record或info,物理page上挂链表),建少cpu缓存失效,使用epoch方便垃圾回收
  • mapping table 树所有都使用pid,需要维护pid到page物理位置的指针表,CAS使用在该指针上

该技术来自微软Hekaton的这篇文章:The Bw-Tree: A B-tree for New Hardware

  1. Concurrent skip list(MemSQL), latch free
    仅使用CAS操作实现insert与update无锁化

该技术来自这篇文章:Concurrent Maintenance of Skip Lists

  1. Adaptive基树(Hyper)

Indexes III — OLAP

OLAP的不同在于可以drill down、roll up、slice、pivot等维度变化操作,本节主要讲解OLAP中列索引设计

个人补充:很多需要数据库行转列操作

Star Schema vs Snowflake Schema (分层级关系表) 使用B+树结构因为数据重复会导致大量的空间浪费,OLAP更适合采用列数据库模式(方便压缩)

SQL Server的列索引设计(如何在行存储上实现列索引):最初设计表必须是只读的, 实现结构为segment directory即blob storage with dictionary/delta encode & compress 针对不同数据类型采用不同编码方法;新版支持insert/update/delete, 采用delta store支持插入更新,bitmap实现删除

bitmap索引技术:每个attr使用一个bitmap表示每个tuple的值(估算10million tuple, 43000个zip codes则需要额外53.75GB,原因是zip作为attr数量太大),需要考虑压缩方法

Storage Models & Data Layout

主要mem DB的数据存储模型,注意C++使用reinterpret_cast在编译期强制转换类型,需要注意缓存对齐中的按字对齐(e.g. 64-bit word)

Null处理:定义特殊值, Bitmap表示, Null Flag

存储模型分为:

  • N-ary Storage Model(NSM) 适合OLTP,insert-heavy,物理上使用堆组织或索引组织元组(比如使用聚族索引)
  • Decomposition Storage Model(DSM) 行存储又叫纵向扩展,适合OLAP,元组物理上使用固定长度或嵌入元组id
  • Hybrid Model 可以切换或同时适配

可以观察到刚插入的数据一般都比较活跃,时间推移后期一般变成只读数据,OLTP通过ETL过程进入OLAP数据仓库

CMU课程15-721数据库系统设计(第一周)

CMU课程15-721最新一期开课啦!

真是要强烈推荐这门课程:有在线视频,有教案,有作业,甚至还有自动评分工具,除了没老师与TA之外真的分享了几乎所有的课程资源,完全可以让我们这种墙内的后进生们自学。

课程安排

Course Introduction and History of Database Systems

以回顾数据库历史的方式串讲了数据库系统设计中的难点,也就是以后的课程内容目录:

  1. 并发控制
  2. 索引
  3. 存储模型,压缩
  4. join算法
  5. 日志与恢复
  6. 查询优化
  7. 新存储器件

未来所有作业与项目都是用C++11写的(牛逼!),准备好调试多线程
推荐每次上课前写一篇本次课阅读paper的心得,包括:主题思想(两句话)、系统使用与修改情况(一句话)、负载测试情况(一句话)

In-Memory Databases

因为新型存储器件的飞速发展导致内存数据库(其实还有内存文件系统)需求越来越强烈,原始基于硬盘为主存储结构的数据库设计因此会有哪些变化呢?

总结下传统硬盘数据库设计特点为:

  1. 使用内存做缓存池(涉及内存与磁盘上以“页”为单位的数据同步)
  2. 页为单位的索引数据组织(页号、slot号、header、tuple、blob等概念设计)
  3. 所有请求都会先经过缓存池(worker线程需要pin住该页防止被swap到磁盘)
  4. 并发控制保证事务可以等待磁盘数据读取时间,同时锁(lock)要保存到其他数据结构(非页结构)中防止被swap
  5. 使用WAL处理日志与恢复问题
  6. CPU时间统计:30%缓存池、30%锁、28%日志、12%真正操作

设计内存数据库,首先不要考虑使用mmap,缺点:内存操作无法非阻塞了、内存结构与磁盘必须相同、数据库系统不知道哪些页实际在内存中(说白了就是操作系统通用设计不可能比数据库架构师专业设计更好!)

内存数据库IO问题退居二线(DRAM 60ns, SSD 25000~30000ns),需要考虑其他性能问题:

  1. lock/latch
  2. cache-line miss
  3. pointer chasing
  4. predicate evaluations
  5. data move
  6. network

总结下设计特点为:

  1. 不需要缓存池和页结构(直接用指针取代id索引?定长或变长数据?但是一定得使用checksum保证数据正确)
  2. 获得锁时间跟获得数据时间一样!导致可能允许牺牲一点并发度(coarse-grained locking因为数据IO足够快)并且可以将锁信息与数据信息一起保存(增加CPU cache locality,mutex相对太慢,一定改用CAS)
  3. 索引设计问题凸显(需要多考虑一下CPU cache)
  4. 查询处理方式巨大改变(不需要顺序扫描,传统一次处理一个tuple方式相对太慢),考虑vector-at-a-time
  5. 仍然需要WAL,可能可以简化;仍然需要checkpoint操作

内容基本出自92年的文章: High-Performance Concurrency Control Mechanisms for Main-Memory Databases

发布第一次项目作业,等本人做完了另找时间写文章说明。

Concurrency Control I

介绍各种事务模型:nested trx、saga trx(其实在《事务处理》一书里面都已经见识过)

介绍各种并发控制方式:
Two-Phase Locking 和死锁避免方法

  • DL_DETECT
  • NO_WAIT
  • WAIT_DIE

Timestamp Ordering及优化方法

  • Basic T/O
  • MVCC
  • OCC
  • H-STORE

测试结果出自14年的文章: Staring into the Abyss: An Evaluation of Concurrency Control with One Thousand Cores

个人补充:MC涉及多线程访问内存值,CC解决多CPU副本一致性

Memory Consistency和Cache Coherence

Concurrency Control II — Multi-versioning

详细介绍隔离级别:比可串行化级别低一些的级别,包括REPEATABLE_READS, READ_COMMITTED

  • Dirty Read 脏读(提前读到后面修改的内容)
  • Unrepeatable Read 不可重复读(事务里两次读操作,后一次读的不同)
  • Phantom Read 幻读(读到其他事务插入或删除的数据)

产品方面voltDB完美支持可串行化,oracle11g最高支持SNAPSHOT_ISOLATION级别,新增两种级别:

  • CURSOR_STABILITY 内部cursor持有锁,有时防止Lost Update(写操作覆盖顺序不对)

  • SNAPSHOT_ISOLATION 保证事务所见snapshot相同(不能强化到可串行化级别 2009新paper有可串行化snapshot方案),防止Write Skew(部分写更新)

下面介绍多版本MVCC现代实现方法(timestamp-ordered好处在于不需要lock!)

mvcc设计考虑:

  • version chains(oldest-to-newest[w],newest-to-oldest[r])
  • version storage(全量或delta存[回滚段])
  • garbage collection(额外线程或合作,GC在重写负载造成15%额外负载])

Hekaton(SQL Server)

事务开始结束都赋予时间戳, 为每个tuple维护版本链(BEGING, END, POINTER),维护全局事务状态图(ACTIVE, VALIDATING[precommited,2PL不需要这个状态,因为锁即可保证]),事务维护元数据(Read set,Write set,Scan set[避免幻读],Commit dependency),乐观事务在多核表现下明显好于悲观事务

实现方面仅使用lock-free数据结构(没有latch或spin lock,使用bw-tree和skiplist,CAS)

该系统设计11年论文:High-Performance Concurrency Control Mechanisms for Main-Memory Databases

Concurrency Control III — Optimistic

首先讨论存储过程,产生于解决使用交互API问题(可以减少网络通信次数与等待)

  • ODBC/JDBC
  • DBMS wire protocols

存储过程的问题:不好版本控制与调试,不好移植

Optimistic方法 其中validation步骤:(可以并发进行)

  • backword 与已经提交的事务判断
  • forword 与还未提交事务判断

本课未学完待补充

本站总访问量