Algorithm

39. 组合总和

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数据库要怎么设计才能满足这种可预知的扩展需求呢？大家经常采用的设计模式有：

EAV模式

可以看到以上常用的预留字段模式都存在一定的局限性，但是EAV模式能够较好的解决自定义扩展字段的数据库设计问题。

废话不多说直接上举例子来说明

entity表

Attribute表

value表

value_varchar

value_int

不同类型的扩展字段各自对应一个value表

EAV模式的优缺点

通过上面的几个数据库表设计，大家应该很容易理解eav其实就是把原来的扩展字段从列转换为行。大大提升了扩展性。

优点

1. 扩展性很高，可以说是无限扩展。
2. 扩展字段也支持索引、联表、搜索等等。
3. 数据库空间基本不会浪费。

缺点

1. 工单查询变得非常复杂，每一个简单的工单查询都需要关联至少3个以上的表进行join操作。并且联表查询的结果还需要在业务代码中进行一系列操作和转换才能得到前端需要的工单字段样式。 如果qps比较大的情况下数据库可能会扛不住，这时候可能就需要引入缓存机制来减少数据库的查询压力，当然一旦加入缓存就又会引入缓存一致性的问题这就是后话了。
2. 业务DAO层的复杂度和学习曲线大大上升。

Share

几种缓存和数据库的同步策略，及其优缺点

对比

具体方案

1. 延迟双删策略：既然可能因为读请求把一个旧的值又写回去，那么我在写请求处理完之后，等到差不多的时间延迟再重新删除这个缓存值。
2. 缓存设置过期时间：给缓存设置expire时间，在异常情况下可以保障脏数据不会永远存在。
3. 引入消息中间件：在缓存更新操作失败的特殊情况下可以通过利用消息中间件的retry特性来让操作最终成功。
4. 订阅 MySQL binlog 的方式处理缓存：把缓存更新或者删除的操作从业务逻辑中移除，保证业务逻辑的纯粹性。

原文：挑战大型系统的缓存设计——应对一致性问题