Algorithm
import (
"sort"
)
func combinationSum(candidates []int, target int) (result [][]int) {
sort.Ints(candidates)
path := []int{}
dfs(candidates, target, 0, path, &result)
return
}
func dfs(candidates []int, target int, idx int, path []int, result *[][]int) {
// fmt.Printf("target:%v,idx:%v,path:%v,result:%v\n", target, idx, path, result)
if idx == len(candidates) {
return
}
if target == 0 {
currentPath := append([]int{}, path...)
*result = append(*result, currentPath)
// fmt.Printf("target is 0! target:%v,idx:%v,path:%v,result:%v\n", target, idx, path, result)
return
}
for i := idx; i < len(candidates); i++ {
if target-candidates[i] >= 0 {
path = append(path, candidates[i])
dfs(candidates, target-candidates[i], i, path, result)
path = path[:len(path)-1]
}
}
}
Review
How to Structure a Golang Project
作者讲述了他自己怎么组织Go后端项目，可以参考下。
TIP
这周在开发工单系统的过程中调研并了解了EAV（entity-attribute-value）模型，并计划在工单系统中落地。
需求
工单系统的主要实体（entity）就是工单。工单有一个特点就是除了一些常用的basic属性（工单ID、标题、内容、经办人等）外用户经常会提出需求一些定制化的属性。比如用户A希望他的工单能增加一个git仓库地址的属性字段，用户B希望他的工单增加一个工单所属服务名的属性字段。
数据库设计难点
那么问题来了，这时候mysql数据库要怎么设计才能满足这种可预知的扩展需求呢？大家经常采用的设计模式有：
| 策略 | 好处 | 问题 |
|---|---|---|
| 预留一个extra字段，内容为json | 扩容方便，新增加的属性在业务代码中转换为json内容后写入extra字段 | 低版本mysql不支持json类型、json字段不能加索引也不能做表关联、扩展字段的搜索不方便 |
| 预留多个varchar extra字段 | 具有一定的扩展性、extra字段可以加索引和其他联表、搜索操作 | 不能无限扩容，当自定义字段超过原本预留的属性上限之后还是有问题、造成空间浪费，有些工单只需要基本属性却要占用多个自定义字段、预留的字段类型类型单一 |
EAV模式
可以看到以上常用的预留字段模式都存在一定的局限性，但是EAV模式能够较好的解决自定义扩展字段的数据库设计问题。
废话不多说直接上举例子来说明
entity表
| ID | title | oprator |
|---|---|---|
| 1 | 工单1 | linhuaqing1@bytedance.com |
| 2 | 工单2 | linhuaqing2@bytedance.com |
Attribute表
| ID | attribute_name | type |
|---|---|---|
| 1 | git地址 | varchar |
| 2 | level | int |
value表
value_varchar
| ID | entity_id | attribute_id | value |
|---|---|---|---|
| 1 | 1 | 1 | https://linhuaqing0928.github.io/ |
value_int
| ID | entity_id | attribute_id | value |
|---|---|---|---|
| 1 | 1 | 2 | 1 |
不同类型的扩展字段各自对应一个value表
EAV模式的优缺点
通过上面的几个数据库表设计，大家应该很容易理解eav其实就是把原来的扩展字段从列转换为行。大大提升了扩展性。
优点
- 扩展性很高，可以说是无限扩展。
- 扩展字段也支持索引、联表、搜索等等。
- 数据库空间基本不会浪费。
缺点
- 工单查询变得非常复杂，每一个简单的工单查询都需要关联至少3个以上的表进行join操作。并且联表查询的结果还需要在业务代码中进行一系列操作和转换才能得到前端需要的工单字段样式。 如果qps比较大的情况下数据库可能会扛不住，这时候可能就需要引入缓存机制来减少数据库的查询压力，当然一旦加入缓存就又会引入缓存一致性的问题这就是后话了。
- 业务DAO层的复杂度和学习曲线大大上升。
Share
几种缓存和数据库的同步策略，及其优缺点
对比
| 策略 | 并发场景 | 潜在问题 | 应对方案 |
|---|---|---|---|
| 更新数据库+更新缓存 | 写+读 | 线程A未更新完缓存之前，线程B的读请求会短暂读到旧值 | 可以忽略 |
| 更新数据库+更新缓存 | 写+写 | 更新数据库的顺序是先A后B，但更新缓存时顺序是先B后A，数据库和缓存数据不一致 | 分布式锁（操作重） |
| 更新缓存+更新数据库 | 无并发 | 线程A还未更新完缓存但是更新数据库可能失败 | 利用MQ确认数据库更新成功（较复杂） |
| 更新缓存+更新数据库 | 写+写 | 更新缓存的顺序是先A后B，但更新数据库时顺序是先B后A | 分布式锁（操作很重） |
| 删除缓存值+更新数据库 | 写+读 | 写请求的线程A删除了缓存在更新数据库之前，这时候读请求线程B到来，因为缓存缺失，则把当前数据读取出来放到缓存，而后线程A更新成功了数据库 | 延迟双删（但是延迟的时间不好估计，且延迟的过程中依旧有不一致的时间窗口） |
| 更新数据库+删除缓存值 | 写+读（缓存命中） | 线程A完成数据库更新成功后，尚未删除缓存，线程B有并发读请求会读到旧的脏数据 | 可以忽略 |
| 更新数据库+删除缓存值 | 写+读（缓存不命中） | 读请求不命中缓存，写请求处理完之后读请求才回写缓存，此时缓存不一致 | 分布式锁（操作重） |
具体方案
- 延迟双删策略：既然可能因为读请求把一个旧的值又写回去，那么我在写请求处理完之后，等到差不多的时间延迟再重新删除这个缓存值。
- 缓存设置过期时间：给缓存设置expire时间，在异常情况下可以保障脏数据不会永远存在。
- 引入消息中间件：在缓存更新操作失败的特殊情况下可以通过利用消息中间件的retry特性来让操作最终成功。
- 订阅 MySQL binlog 的方式处理缓存：把缓存更新或者删除的操作从业务逻辑中移除，保证业务逻辑的纯粹性。
