常见面试流程

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生成：

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最新一期开课啦！

课程安排

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

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最新一期开课啦！

课程安排

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最新一期开课啦！

课程安排

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_tile为shared_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最新一期开课啦！

课程安排

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

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最新一期开课啦！

真是要强烈推荐这门课程：有在线视频，有教案，有作业，甚至还有自动评分工具，除了没老师与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 与还未提交事务判断

本课未学完待补充

All cultures seem to believe the idea that history is a kind of chart that guides its members in to the future. Hitory gets transmitted from generation to generation.

These stories of the past offer the members of a culture part of their identity while highlighting the culture’s origins, what is deemed important, and the most significant starting point of Western civilization, which is the culture that most powerfully shapes not only the west but most of world today. It seems to me to be evident that whatever it’s over characteristics, the West has created institutions of government and law that provide unprecedented freedom for its people. It has also invented a body of natural scientific knowledge and technological achievement that together made possible a level of health and material prosperity undreamed of in earlier times and unknown ouside the West and those places that have been influenced.

Society cannot achieve the full benefits of Western science and technology without commitment to reason and objectivity as essentail of knowledge. The primary of reason and the pursuit of objectivity therefore, both characteristic of the Western experience seem to me to be essential for the achievement of the desired goals almost anywhere in the world. Chance and accident often played a vital part in the material condition of life cannot take root and flourish without reason, although it was employed for all sorts of practical and intellectual purposes in some of these cultures, it still lacked independence from religion and it lacked the high status to challenge the most basic received ideas.

It rest on religious authority, tradition, and power with a painful understanding of the limitations of the greatness and possibilities before man that together, composes the tragic vision of the human condition that characterized classical Greek civilization.

incried at Apollo’s temple at Delphi, “know Thyself” “Nothing in Excess” known your own limitations as a fallible mortal(not divine) to train in virtue of the animals when prefected, so he is the worst when seperated from law and justice. For injustice is most dangerous when it is armed. A religion that worshipped a single all powerful deity, who is sharply seperated from human beings.

#1. 基本理论

#2.
基本分析法：（把握价格走势）证券价值及价格基本要素分析，评估证券投资价值与合理价位，提出投资建议（宏观经济形势/行业特征/上市公司基本财务数据）
技术分析法：（把握局部走势）证券市场过去现在市场行为进行分析，应用数学逻辑探索变化规律来预测未来变化
量化分析法：

静态/动态套期保值，主动/被动套期保值
学术分析：价格偏离信息内容；基本分析：价格偏离价值；技术分析法：市场供求；行为分析：心里及行为不平衡

价值发现型：风险相对分散理念；价值培养型：风险共担理论

#3. 有价证券的价值分析与估值方法
虚拟价值–未来预期收益
市场价值与预期收益多少成正比，与市场利率高低成反比
货币的时间价值、复利、贴现 $ FV = PV(1+i)^n $, $ PV = FV/(1+i)^n$
现金流贴现与净现值：贴现率与现金流（贴现现值）成反比
市盈率(P/E) 周期弱公司，如制造业，服务业
市净率(P/B) 周期型公司
市值回报增长比(PEG) IT公司
权益价值=资产价值-负债价值(即账面价值)
现金流与贴现率：债券必要回报率(债券贴现率) = 真实无风险收益率+预期通货膨胀率+风险溢价(无风险利率)
(1+名义无风险收益率) = (1+真实无风险收益率) * (1+预期通货膨胀率)
零增长模型内部收益率：股票净现值 = 股票内在价值 - 投资成本 = 每期收益/必要收益率 - 投资成本
全价报价缺点含混债券价格涨跌真实原因、净价报价
付息债券定价，累息债券定价
赎回收益率（一般在利率调低时出现）
利率风险结构，期限结构（期限不同，收益率不同）
当期收益率Y=C/P 每年利息收益/债券价格，到期收益率（缺点零息债券不能用），内部报酬率(IRR)
PV=T/U, p理论价格，发行时价格

利息计算：

1. 短期债券ACT 360/180 累计利息 = 面值年利率/每年付息次数ACT/180
2. 中长期 365天(交易所)
3. 贴现式 实际天数计算

期限结构与收益率曲线
内部收益率（报酬率）NPV V(内在价值) P(市价) 关系 V=P则NPV=0
零增长与可变增长模型（股息增长率）

之前总结过Zookeeper的各种设计优点，但是这个系统的缺陷与优点同样突出，本文就是结合自己的使用经验，业界给出的评价对ZK的缺点进行的归纳，一方面归纳使用表现上的不足，另一方面根据个人经验总结出系统本身功能设计时的就存在的缺陷。同时也思考了相应对策与改进的办法，算是本人对ZK设计的完整的思考总结吧。最后还关注了下etcd这个后起之秀的设计，看看它是否已经弥补了ZK的不足，能否担当后继者。

1.实际使用暴露的不足

尽管ZK已经在工业界大量使用，但实际使用ZK时就会发现自己仍然面临种种问题，这里总结一下实际使用中系统暴露出的种种不足。

1. API使用复杂

   使用ZK最直观的感觉就是客户端API使用起来特别麻烦，因为ZK的实际逻辑模型是文件存储，其他逻辑都需要结合使用临时节点和回调机制来实现，API接口与实际需求之间差距非常大，说白了就是ZK官方提供的API太过底层，而且表现力不足。没有http访问接口，只能通过API访问，导致兼容性与表现各异。比如一个细节很容易坑人：

   >

   ZK不能确保任何客户端能够获取（即Read Request）到一样的数据，需要客户端自己同步：方法是客户端在获取数据之前调用org.apache.zookeeper.Async(Callback.VoidCallback, java.lang.Object) 完成sync操作.

2. 实际客户端逻辑复杂

   因为ZK提供的是非常底层的API，所以要实现一个基础需求，开发者用户自己需要依靠这些底层API在客户端实现并维护一个异常复杂的逻辑，甚至官方自己都一度不能提供正确的逻辑。比如实现分布式锁时，需要开发者自己在客户端处理异步请求锁的时间判断与仲裁，很容易出错。因此实现了多种ZK常用功能的开源项目Curator取代了官方成为ZK事实标准上的客户端了，总算让开发者使用ZK时稍微轻松一些，能够专注到自己的业务逻辑上面。但是Curator方案仍然有问题无法避免。

   而 Curator 这类客户端的复杂性使得支持多语言环境较难，怎样保证两个语言的 recipe 的是行为一致的？基本没有办法通过自动化测试来保证正确性，只能不停地线上踩坑一个个排查。

3. ZK异常状态判断

   比逻辑更复杂的是开发者总是需要自己同时处理ZK通信中的异常状态，需要正确处理CONNECTION LOSS(连接断开) 和 SESSION EXPIRED(Session 过期)两类连接异常。一个典型的难题就是session的超时机制的问题

   The client will stay in disconnected state until the TCP connection is re-established with the cluster, at which point the watcher of the expired session will receive the “session expired” notification.

   甚至需要考虑包括业务方系统load变高，或者发生长时间gc，导致ZK重连甚至session过期的问题。

4. 回调次数限制

   ZK中所有Watch回调通知都是一次性的。同一个ZK客户端对某一个节点注册相同的watch，也只会收到一次通知。节点数据的版本变化会触发NodeDataChanged回调，这导致需要重复注册，而如果节点数据的更新频率很高的话，客户端肯定就无法收到所有回调通知了。

5. Zab协议与全系统的有效性

   实际应用中ZK系统整体可靠性也不一定有保证，比如在跨机房部署方面，由于ZK集群只能有一个Leader，因此一旦机房之间连接出现故障，Leader就只能照顾一个机房，其他机房运行的业务模块由于没有Leader也都只能停掉。于是所有流量集中到有Leader的那个机房，很容易造成系统crash。

   同时ZK对于网络隔离极度敏感，导致系统对于网络的任何风吹草动都会做出激烈反应。这是Zab协议本身的设计，一旦出现网络隔离，ZK就要发起选举流程。悲催的是Zab协议的选举过程比较慢，期间集群没有Leader也不能提供服务。造成本来半秒一秒的网络隔离造成的不可用时间被放大为选举不可用时间。

6. 性能

   ZK本身的性能比较有限。典型的ZK的tps大概是一万多，单个节点平均连接数是6K，watcher是30万，吞吐似乎还可以，但是时延就没那么乐观了。特别

响应时间、网络、缓存

​

1. 服务极限与可扩展性

   ​

2. 存储极限与可扩展性

   ​

2.需求满足缺陷

设计层面上的不足

1. 事务API能力不足
2. 中心无仲裁能力
3. 回调次数
4. 可扩展性
5. Zab协议

3. 怎样更好的设计

1. 更丰富有效的API

   支持多IP，自动处理重连与恢复，服务端可以动态加入移除

2. 委托服务端处理能力
   script能力？像redis支持luaScript
   节点单独超时时间设计
3. 横向可扩展性
4. JVM

4. 继任者etcd？

1. raft协议取代zab
2. go GC
3. restful API

5. 参考资料

1. zookeeper节点数与watch的性能测试
2. 对Zookeeper的一些分析
3. ZooKeeper真的low吗？上千节点场景配置服务讨论
4. Zookeeper常见问题整理
5. ZAB问题总结
6. 剖析etcd