Algorithm
62. 不同路径
// f(m,n) = f(m-1,n) + f(m,n-1)
func uniquePaths(m int, n int) int {
results := make([][]int, m)
for i := 0; i < m; i++ {
results[i] = make([]int, n)
}
results[0][0] = 1
for i := 0; i < m; i++ {
for j := 0; j < n; j++ {
if i == 0 && j == 0 {
continue
}
if i == 0 {
results[i][j] = results[i][j-1]
continue
}
if j == 0 {
results[i][j] = results[i-1][j]
continue
}
if i > 0 && j > 0 {
results[i][j] = results[i-1][j] + results[i][j-1]
}
}
}
return results[m-1][n-1]
}
Review
medium每个月可读文章额度用光了，本周跳过review，需要想办法开一个visa卡冲会员了。
TIP
这周为了指导新同学，深入看了下公司的配置中心的SDK源码，一个get操作大概包含如下操作：
- 首先SDK在init的时候会初始化一个localcache，这个localcache为一个map数据结构。为了保证并发安全localcache带上了sync.RWMutex，同时map里面的每个配置都会维护一个expired值（time.Time）。
- 用户调用get操作的时候，SDK会先尝试从localcache中获取值（需要先抢到RWMutex锁），如果值不为空并且不过期（expire不比time.Now早）则直接返回缓存中的值。
- 如果缓存中的值为空或者过期或者报错了，则发起网络请求拿到配置中心服务端的值（这里底层其实就是一个etcdClient）。
- 拿到服务端的值之后，会将这个值赋值给localcache（同样需要先抢到RWMutex锁，同时还会把这个值的expired值设置为time.Now().Add(过期时间)），然后再返回给用户。
学到的东西：
- SDK确实和我之前猜的一样维护了一个localcache，并且为了安全加上读写锁。
- 我之前猜的解决方案是SDK每隔一段时间定期从服务端get数据（或者长链接服务端主动push）然后更新localcache。公司的配置中心SDK是采取懒汉模式的方式，也就是需要的时候先从缓存中取，取不到的时候再去服务端拿数据。这样子的好处是简单且省IO。
Share
学习“数据密集型应用系统设计”
第一章 可靠性、可扩展性、可维护性
- 延迟和响应时间：延迟（latency） 和 响应时间（response time） 经常用作同义词，但实际上它们并不一样。响应时间是客户所看到的，除了实际处理请求的时间（ 服务时间（service time） ）之外，还包括网络延迟和排队延迟。延迟是某个请求等待处理的持续时长，在此期间它处于 休眠（latent） 状态，并等待服务。
- 长尾效应：一个缓慢的调用就可以使整个最终用户请求变慢。即使只有一小部分后端调用速度较慢，如果最终用户请求需要多个后端调用，则获得较慢调用的机会也会增加，因此较高比例的最终用户请求速度会变慢。
- 一个Twitter浏览时间线的例子，如何通过增加缓存来解决读请求压力大的问题。
- 每个follower维护自己的缓存队列，队列里面塞自己关注的人发布的消息内容。
- 而每个followee在每次发布消息的时候，都需要往自己的follower的缓存队列里面塞入对应的内容。
- 这里遇到的一个问题就是如果有一个超级大博主（有上千万的粉丝），这时候这个博主发布的每一条博客都会导致一个瞬时上千万量级的缓存更新操作。针对这种情况可以采用大博主发布消息的时候只写入数据库不更新关注着缓存队列的方式来解决写放大的问题，而在读的时候也针对大博主做特殊操作（读取DB的方式）。
