Algorithm
- 本周根据分类，完成3道动态规划。
- 通过把原问题分解为相对简单的子问题的方式求解复杂问题。动态规划常常适用于有重叠子问题和最优子结构性质的问题。
minimum-path-sum
class Solution { public int minPathSum(int[][] matrix) { int m = (matrix.length); int n = matrix[0].length; if ((m < 1) || (n < 1)) { return 0; } int[][] sum = new int[m][n]; sum[0][0] = matrix[0][0]; for (int i = 1; i < m; i++) { sum[i][0] = sum[i-1][0] + matrix[i][0]; } for (int j = 1; j < n; j++) { sum[0][j] = sum[0][j-1] + matrix[0][j]; } for (int i = 1; i < m; i++) { for (int j = 1; j < n; j++) { sum[i][j] = matrix[i][j] + Math.min(sum[i][j - 1], sum[i - 1][j]); } } return sum[m-1][n-1]; }}复制代码 climbing-stairs
class Solution { public int climbStairs(int n) { if (n == 1) return 1; int[] a = new int[n]; a[0] = 1; a[1] = 2; for (int i = 2; i < n; i++) { a[i] = a[i-1] + a[i-2]; } return a[n-1]; }}复制代码 decode-ways
- 该实现的一个小技巧是申请数据组长度为 字符串长度+1，方便逻辑统一处理。
class Solution { public int numDecodings(String s) { if (s.length() < 1) { return 0; } int[] a = new int[s.length() + 1]; int n = s.length(); a[n] = 1; a[n - 1] = s.charAt(n-1) == '0' ? 0 : 1; for (int i = n-2; i >= 0; i--) { if (s.charAt(i) == '0') { continue; } else if (Integer.parseInt(s.substring(i, i+2)) <= 26) { a[i] = a[i+1] + a[i+2]; } else { a[i] = a[i+1]; } } return a[0]; }}复制代码 Review
文章清晰的描述了paxos协议在读过程，写过程，序号生成及比较策略，提案的发起，响应，通知过程。 处理要点如下。
概述
Paxos is an algorithm to solve the consensus problem. a majority of the members of the system must agree that a particular value is in fact “the one true” value to then report it as such.
Paxos is only a small piece of building a distributed database: it only implements the process to write exactly one new thing to the system
All below procedure accomplishes one thing: one durable write. Paxos itself has many variants that make it faster, introduce the ideas of masters, sacrifice pure fault tolerance for more speed, and tonnes of layers built on top which use it as a primitive to implement an actual database.
read.
To read a value from the basic Paxos system, a client asks all the processes in the system what they have stored for the current value, and then takes the value that the majority of the processes in the system hold. If there is no majority or if not enough processes respond, the read fails. To the left you can see a client asking the nodes what their value is, and them returning the value to the client. When the client gets a majority of responses agreeing on a value, it has successfully read it and keeps it handy.
there are much better ways of doing reads when implementing a system using Paxos that don’t require contacting every node for every read, but they extend beyond the original Paxos algorithm.
write
Paxos makes a guarantee that clients can send their write requests to any member of the Paxos cluster, so for the demos here the client picks one of the processes at random. This property is important and neat: it means that there is no single point of failure, which means our Paxos governed system can continue to be online (and useful) when any node goes down for whatever unfortunate yet unavoidable reason. If we designated one particular node as “the proposer”, or “the master” or what have you, then the whole system would grind to a halt if that node failed.
sequence number
When implementing Paxos, these globally unique and sortable sequence numbers are usually derivatives of precise system time and node number in the cluster so they grow over time and are never the same.
When implementing Paxos, these globally unique and sortable sequence numbers are usually derivatives of precise system time and node number in the cluster so they grow over time and are never the same.
PROMISES
after the proposing process has sent out it’s proposal, the processes check the proposal’s sequence number against the highest they’ve ever seen, and if it is the highest, they can make a promise to not accept any proposals older than this new threshold sequence number. This promise is returned as a message sent from the promising process to the one that is proposing a new value, as thing a promise message.
ACCEPTANCE
This bad state is often corrected in real implementations by either repeating the accept phase to get more nodes and eventually a majority.
Tip
- 刷题时可以先刷简单的问题，然后按类别刷medium的问题。
- Mysql技术内幕-InnoDb存储引擎 这本书不错，讲解事务隔离级别及其实现原理非常清楚。
Share
事务隔离级别
第二类丢失更新：
在InnoDB存储引擎中，通过使用Next-Key Lock算法来避免不可重复读的问题，在Mysql 官方文档中将不可重复读的问题定义为Phantom Problem 。 在Next-Key Lock算法下对于索引的扫描，不仅是锁住扫描到的索引， 而且还锁住这些索引覆盖的范围。 因此在这个范围内的插入都是不允许的。 这就避免了另外的事务在这个范围内插入数据导致的不可重复读的问题。因此，InnoDB存储引擎的默认事务级别是RR， 采用Next-Key Lock算法。
第一类丢失更新 在当前数据库的任何隔离级别下 都不会导致数据库理论意义上的丢失更新问题。这是因为， 即使是Read Uncommitted 隔离级别，对于行的DML操作，需要对行或者其他粗粒度级别的对象加锁。
脏读的一个场景
- replication环境中的slave节点，在该slave节点上查询并不需要特别精确的返回值。
事务隔离性通过锁来实现。
三种行锁算法：
- Record Lock
- Gap Lock
- Next-Key Lock ： Gap + Record lock
用户可以通过两种方式显示关闭Gap Lock。
- 将事务隔离级别设置为RC
- 将参数innodb_locks_unsafe_for_binlog设置为1
加锁规则
若将上锁的对象看成一棵树，那么对最下层的对象上锁，也就是对最细粒度的对象进行上锁，那么首先需要对粗粒度的对象上锁。 例： 如果需要对页上的记录r 上x锁，那么分别需要对数据库A，表，页 上意向锁IX， 最后对记录上X锁。若其中任何一部分导致等待，那么该操作需要等待粗粒度锁的完成。
支持意向锁设计比较简练，其意向锁即为表级别的锁。设计目的主要是为了在一个事务中揭示下一行将被请求的锁类型。其支持两种意向锁。：
- 意向共享锁 事务想要获得一张表某几行的共享锁
- 意向排它锁 事务想要获得一张表中某几行的排它锁。
由于InnoDB存储引擎支持的是行级别的锁，因此意向锁实际不会阻塞全表扫以外的任何请求。
幻读：
phantom problem是指在同一事务下，连续执行两次同样的sql语句可能导致不同的结果，第二次的SQL可能会返回之前不存在的行。
一致性非锁定读。
consistent nonlocking read 是指innodb存储引擎通过mvcc的方式读取数据。 通过undo段完成。
快照数据其实就是当前行数据之前的历史版本，每行记录可能有多个版本。 在事务隔离级别RC 和RR下，InnoDB存储引擎使用非锁定的一致性读， 然而对于快照数据的定义却不相同。在RC事务隔离级别下， 对于快照数据，非一致性读总是读取被锁定行的最后一份快照数据。在RR下，对于快照数据 非一致性读总是读取事务开始时的行数据版本。
一致性锁定读。
在某些情况下 用户需要显式对数据库读取操作进行加锁以保证数据逻辑的一致性。 InnoDB存储引擎对于select语句支持两种一致性的锁定读： select for update。 select lock in share mode。
其他
- select @@tx_isolation; 查看事务隔离级别
- 锁加在索引上，如有多个索引，则每个索引都加锁。
原子性 一致性 持久性实现原理
- 通过redo log和undo log来完成。
- redolog 用来保证事务的原子性和持久性。
- undo log用来保证事务的一致性。
redo log
- 通常是事务日志。记录的是页的物理操作。
- redolog由2部分组成 redolog buffer redo logfile。 commit时 将该事务的所有日志 写入到redo
- logfile进行持久化。
- redo log基本上顺序写。
- relog都是以512字节进行存储的，这意味着重做日志缓存 重做日志都是以块的方式保存的，称作重做日志块。
- redo log是幂等的。 而 binlog不是幂等的。
undo log
- undo是逻辑日志 根据每行进行记录。
- undo log帮助事务回滚及mvcc功能。
- 随机读写。
- undo log也会产生redo log。 需要持久性的保护。
binary log
- 二进制日志只在事务提交完成后进行一次写入。
- innodb redolog是物理格式日志记录的是每个页的修改。
问题排查
- infomation_schema库下表innodb_trx, innodb_locks, innodb_lock_waits。通过这三张表用户可以更简单的监控当前事务并分析可能存在的锁问题。