背景

作为一个电商平台，我们需要有一个统一的地址库，对这个库的配置页面，就落到了我负责的运营平台中了。对于这个库来说，大概的几个需求如下：

1. 以 Entity 维度来区分，例如 Malaysia 和 Taiwan 的数据是不互通的；
2. 每个 Entity 中的数据都是一棵树，一共有四层，分别代表 State、City、District、Street；

3. 需要支持如下操作：

   • 给定一个点，需要能找到从它到根节点的所有点，例如粤海街道上面是南山区、深圳市、广东省；
   • 给定一个点，需要能找到它的所有子孙后代，例如广东省下面有深圳市、广州市、南山区、福田区、粤海街道等等，需要实现分页功能；
   • 对于上面的需求中返回的每条数据，需要完整的显示例如“广东省深圳市南山区粤海街道”，而不能只显示“粤海街道”；
   • 需要支持修改某一节点的信息、通过 Excel 批量新增和修改节点，无需支持删除（业务可以将导入视为超级慢的操作，所以可以写成异步操作）；
   • 行政区的变动被看作是很正常的事情（例如济南吞并莱芜），因此必须支持在导入的时候将某一棵子树挪到另一个节点下。

需求分析

对树的快速查询

我们一致认为对树的查询操作是非常频繁的，但新增单个节点和导入的操作不会太频繁，于是同事决定采用如下的数据库结构：

type Location struct {
    ID         int64 `gorm:"primary_key"`
    LocationID int64
    ParentID   int64
    Lidx       int64
    Ridx       int64
    // ... and actual data like `name`, `country`, etc.
}

其中 Lidx 和 Ridx 是两个索引，分别记录了在深度优先遍历中第一次和最后一次访问到这个节点时的 Index 大小，以下图为例，左边的是 Lidx，右边的是 Ridx：

如果要查询“粤海街道”到根的所有点，只需要这样写：

SELECT * FROM `location_tab` WHERE `lidx` <= 5 AND `ridx` >= 6 ORDER BY `lidx`

如果要查询“广东省”以及其下的全部子孙后代，只需要这样写：

SELECT * FROM `location_tab` WHERE `lidx` >= 2 AND `ridx` <= 15 ORDER BY `lidx`

分页的话，只需要加上 LIMIT 就好啦！

显示完整前缀

如果对于每条数据都执行一遍上面写的“从它到根节点”的 SQL 查询然后拼数据，一个是会特别慢，一个是当数据量大的时候（例如一页展示一百条）后端会向数据库发送一百条查询请求，这对于我来说是不能忍受的，于是稍微想了一下，找到了一个简单的优化方法：尽可能复用之前的信息。

假设我已经确定了某一条需要显示的数据如下：

{
    "locationId": 22,
    "parentId": 20,
    "name": "南山区",
    "fullNames": ["广东省", "深圳市", "南山区"]
}

那么我完全可以确定：深圳市（id = 20）的前缀是 ["广东省", "深圳市"]；假设我找到了另一条 parentId = 20 并且 name = "福田区" 的记录，那它的 fullNames 一定是 ["广东省", "深圳市", "福田区"]。如果没有任何可用的信息，就通过前文的 SQL 查到当前节点的 fullNames，将该节点以及它的父节点的 fullNames 都放到一个缓存中，如果能在缓存中找到它的父节点的信息，就可以直接通过父节点的 fullNames 拼上当前节点的 name 得到当前节点的 fullNames。唯一需要保证的是我们需要按照深度优先遍历的顺序来枚举每个节点，不过这个太简单了，因为在之前的查询中，我们已经按照 lidx 排了序。关键代码如下：

func FillLocationsForEachItem(apiLocations []*Location) []*Location {
    // We need a cache so that we won't have to query in database for each records.
    // The map `resultCache` represents the cached query result for each location.
    // Because the location list has already been ordered by lidx, theoretically we have
    // to query in database at most 4 times (because there're 4 levels, at most 4 locations
    // don't have their parent's result)
    resultCache := make(map[int64][]string)

    for _, location := range apiLocations {
        if cachedResult, ok := resultCache[location.ParentID]; ok {
            // use cached data
            result := make([]string, len(cachedResult), len(cachedResult)+1)
            for index, item := range cachedResult {
                result[index] = item
            }
            result = append(result, location.Name)
            location.FullNames = result
            resultCache[location.LocationID] = result
        } else {
            // directly query result[current] in database and set cache
            result := GetLocationPrefixs(location.LocationID)
            location.FullNames = result
            resultCache[location.LocationID] = result
            // set cache for parent
            parentResult := make([]string, len(result)-1)
            length := len(result)
            for index := 0; index < length-1; index++ {
                parentResult[index] = result[index]
            }
            resultCache[location.ParentID] = parentResult
        }
    }
    return apiLocations
}

理论上来说，只要返回的数据是连续的，就只需要最多四次数据库查询——因为树最多只有四层，意味着最多在处理四个元素的时候找不到父节点的信息。例如上图中，我分页之后的数据是粤海街道、宝安区、福田区、广州市，那么我只需要在一开始查一遍粤海街道，在宝安区的时候查一下深圳市，在广州市的时候查一下广东省，只需要查询三次数据库就可以将所有需要的前缀填满了。

导入操作

最后考虑导入操作，由于对树的修改非常复杂，因此与产品沟通后决定：同一时间只允许一个人导入，若提交导入任务时有任务正在进行，不会将新任务放到队列，而是直接报错。当然，批量导入是一定要写 Transaction 的。

“同一时间只允许一个人导入”本质相当于给某个函数加锁，但不能简单的用一个 Mutex 来解决，因为按照需求，假如有一个请求过来的时候正在锁着，应当立即返回报错信息而不是阻塞，而 Go 的 Mutex 没有 IsLocked 之类的方法。就算有也不行，下面是一个错误的示范（假设 lock.IsLocked() 表示获取锁的状态）：

var lock sync.Mutex

func ImportLocations(c *gin.Context) {
    if lock.IsLocked() {
        c.String(http.StatusBadRequest, "Another process is running")
    } else {
        lock.Lock()
        defer lock.Unlock()
        // import something asynchronously...
        c.String(http.NoContent, "Success")
    }
}

当两个请求几乎同时到达时，可能会出现这样的问题：

• A: lock.IsLocked() == false
• B: lock.IsLocked() == false
• A: lock.Lock()
• A: Import data
• A: lock.Unlock()
• B: lock.Lock()
• B: Import data
• B: lock.Unlock()

这不就完蛋了么！所以肯定是不行的。正确的做法是这样：

var isBusy bool
var lock sync.Mutex

// tryToWrite trys to get the control for write operation
// returns false if it failes
func tryToWrite() bool {
    lock.Lock()
    defer lock.Unlock()
    if isBusy {
        return false
    }
    isBusy = true
    return true
}

// finishWrite will finish the write operation
// returns false if there's already no write operation
func finishWrite() bool {
    lock.Lock()
    defer lock.Unlock()
    if !isBusy {
        return false
    }
    isBusy = false
    return true
}

func ImportLocations(c *gin.Context) {
    if tryToWrite() {
        defer finishWrite()
        // import something asynchronously...
        c.String(http.StatusNoContent, "")
    } else {
        c.String(http.StatusBadRequest, "Another process is running")
    }
}

额外设置一个 isBusy 变量，把对这个变量本身的读写操作都做成原子性的，这样就不会出现问题了。

修改树结构

如果只是新增一个节点，那只需要三句 SQL，例如我要在广东省下面插入一个清远市，已知广东省的 locationId 是 10，ridx 是 15，那么我们只需要执行：

UPDATE `location_tab` SET `lidx` = `lidx` + 2 WHERE `lidx` >= 15
UPDATE `location_tab` SET `ridx` = `ridx` + 2 WHERE `ridx` >= 15
INSERT INTO `location_tab` (`name`, `parent_id`, `lidx`, `ridx`, ...) VALUES ('清远市', 10, 15 + 1, 15 + 2, ...)

但前两条都是批量更新，如果运气不好，很可能会直接修改掉大半张表，而且由于导入操作除了会有大量节点的增加以外，还可能有大量的挪动子树的操作，所以跟物流组的大佬商量了一番之后，决定直接在内存中建出整棵树、做对应的增加操作，最后直接重建索引、更新数据库，这样就是对于每条数据单独修改了。虽然导入是个耗时操作，但我也不想每次导入都向数据库发送上万条查询来更新数据，这可能会导致不可接受的延迟，甚至有数据库被拖垮的风险。于是我想了一个办法：记录一下每个节点（id）对应的 lidx 和 ridx 的变化量（deltaL、deltaR），然后分别按照 Delta 分组，搞成两个 map[int64][]int64，最后 for dl, lids := range deltaL、for dr, rids := range deltaR 批量更新：

UPDATE `location_tab` SET `lidx` = `lidx` + [dl] WHERE `id` IN ([lids])
UPDATE `location_tab` SET `ridx` = `ridx` + [dr] WHERE `id` IN ([rids])

虽然查询执行的还是很慢，但由于发送请求的数量大大减少，延迟应该可以忍受了。毕竟，导入是个异步操作。

Update 20190323

修正了对并发请求时执行流程分析的错误。