limen_posts.tar

_posts/0000755000175300017540000000000012775644345011672 5ustar  limdev-super_posts/mongodb-or-mysql.md0000644000175300017540000000264312775644210015416 0ustar  limdev-super---
title: MongoDB还是MySQL？
date: 2016/09/17
tags: [数据库]
---
# 应用场景
用户发布一条动态，动态中可以包含由“##”包裹的话题内容。

一条动态可以包含多个话题，一个话题可以关联多个动态。

# 数据结构

**话题表**

+ 话题id
+ 话题内容
+ 创建话题的用户id

**动态话题关联表**

+ 话题id
+ 动态id

DBA看到创建数据表的邮件后发问，为什么用MySQL，而不用MongoDB？

**他的理由**

+ MongoDB在文档数达到上亿时仍能保持良好性能，MySQL没有这么强大

**我为什么采用MySQL？**

+ 两张表的schema是比较固定的
+ 两张表通过话题id构成关联关系，MySQL支持关联查询，MongoDB不支持
+ MySQL按照表的schema对写操作进行约束，MongoDB相反，因为MongoDB的特点就是schemaless

# 关于数据量的问题

在我的另一篇文章[数据库设计的重要性与原则](http://www.jianshu.com/p/4cdb59716483 "")，根据其中的**适度超前**原则，从目前的每日动态发布量来看，这两张表的数据量在5年内不会达到上亿。

如果达到上亿的数据量，是否真的需要切换到MongoDB？我看没这个必要。即使是MongoDB，数据量达到一定的量之后，读写性能也会急剧下降。

我们有更好的方案来解决读写性能下降的问题，但这是另外一个话题了。
_posts/red-envelope-assignment-algorithm.md0000644000175300017540000000545312775644231020734 0ustar  limdev-super---
title: 一种红包分配算法及其实现
date: 2016/09/29
tags: [算法]
---
该算法适用于多人抢红包的场景，可动态调整红包分配的均匀程度。红包余额需大于红包剩余份数，分配的金额为整数，如果需要分配成小数，将红包余额乘以100，分配结果除以100即可。

## 算法概述

红包余额R，红包剩余份数D，离散程度N（取值范围[0,1)）,分配金额G

1. D=1，G=R
2. D>1，按(R/D) + random(-(R/D)\*N, (R/D)\*N)将R分解为一个列表，random方法取[a,b]范围的随机值
3. 从第2步得到的列表中随机选择一个作为G

容易看出

+ N取0时，每个人分配到的金额相等，都是R/D（最后一份可能不等于该值）
+ N取1时，可能出现分配金额为0的情况，所以N的取值应小于1
+ N的值越大，分配金额的分布越不平均
+ 第3步使得分配金额与抢红包的先后顺序无关

## Python实现

```python
import random

def avg(remain, dv):
    return remain / dv

def randNoise(noise, expected = 0):
    return random.randint(expected - noise, expected + noise)

def divideToList(remain, dv, noiseRate):
    divided = []
    while dv > 0:
        if dv == 1:
            get = remain
        else:
            av = avg(remain, dv)
            get = av + randNoise(int(av * noiseRate))
        divided.append(get)
        dv = dv - 1
        remain = remain - get
    return divided

def assignToList(remain, dv, noiseRate):
    L = []
    while dv > 0:
        div = divideToList(remain, dv, noiseRate)
        g = random.choice(div)
        L.append(g)
        dv = dv-1
        remain = remain - g
    return L

```

## 测试代码

```python
import sys

def testAssignment(L, dv):
    if len(L) != dv:
        print 'Bad #not average'
        return False
    for i in L:
        if i <= 0:
            print 'Bad #negative or zero'
            return False
    return True
        
remain = int(sys.argv[1])
dv = int(sys.argv[2])
noiseRate = float(sys.argv[3])
testTimes = int(sys.argv[4])
    
while testTimes > 0:
    L = assignToList(remain, dv, noiseRate)
    if testAssignment(L, dv) == True:
        print 'Good'
    print L
    testTimes = testTimes - 1

```

**输出**
```bash
# python red_env.py 500 10 0.9 10
Good
[33, 94, 62, 9, 42, 39, 19, 77, 83, 42]
Good
[27, 38, 37, 133, 10, 48, 54, 113, 21, 19]
Good
[42, 84, 71, 61, 47, 51, 36, 59, 14, 35]
Good
[74, 38, 17, 94, 59, 65, 100, 8, 11, 34]
Good
[31, 44, 46, 60, 43, 38, 16, 64, 112, 46]
Good
[12, 30, 43, 109, 29, 43, 51, 22, 140, 21]
Good
[27, 81, 143, 36, 12, 12, 6, 63, 20, 100]
Good
[13, 16, 18, 96, 8, 65, 63, 55, 12, 154]
Good
[36, 49, 60, 62, 87, 53, 16, 32, 70, 35]
Good
[98, 17, 43, 61, 38, 57, 63, 77, 43, 3]

```
_posts/database-design-principles.md0000644000175300017540000001226512775644101017371 0ustar  limdev-super---
title: 数据库设计的重要性与几个原则
date: 2016/09/15
tags: [数据库]
---
随着工作经验的积累，我日益感觉到，对一名程序员来说，拥有良好的数据库设计能力是很重要的，甚至是最重要的。

程序员界有一句著名的话
> Talk is cheap, show me the code

把这句话演变一下，就成了
> Code is boring, show me the data structure

数据库的种类很多，对于像作者这样的web后端程序员来说，可以把范围缩小到关系型数据库、非关系型数据库与NoSQL数据库。

# 数据结构为何如此重要
**一切代码都是围绕数据结构运行的。**
客户端展现的动态数据，都是存储在数据库中，这对程序员来说一定是常识了。拿你正在浏览的这个页面为例，文章的作者、标题、正文、评论、喜欢等等，只要你打开任意两篇文章，两个页面不一样的地方，几乎都是因为在数据库中存储的内容不同。

良好的数据结构可以提升性能，使代码变得简单、清晰。数据结构清晰了，围绕着数据运行的代码自然就清晰了。

# 数据库设计需考虑的因素
提到数据库设计原则，首先会想到第一、第二、第三范式，这些理论能了解最好，但这不是本文探讨的主题。

面对一个具体的应用场景，设计数据库时应考虑哪些因素？为了能够言之有物，我们拿[简书](www.jianshu.com "")的文章页面来现身说法。

### 当前可用性
数据结构的设计要能达到应用场景的要求，这是最基本的。举个例子，这篇文章的正文存储在了数据表中的某个字段，该字段的长度被设定为1000字，这显然不能满足应用场景的要求，文章写到这里已经超过了1000字（估计的，我没有数）。

### 适当超前
超前到什么程度需要根据对应用的预期来定。拿QQ来说，马化腾最初肯定预见不到QQ能有目前的用户量与活跃度，毕竟那是近20年前的事情了。

对于本文设定的应用场景，我们把超前设定为网站的文章数量达到了千万级。这时如果只把文章存在一张数据表里，读写性能必然是会急剧下降的，这必然会导致用户体验变差，用户流失。老板不能容忍，DBA也不能容忍。

合理的解决方案之一是分为两张数据表，一张存储热门文章，另一张存储非热门文章。毕竟热门文章占少数，热门文章的加载速度相对就更快了。还有别的解决方案吗？肯定有，留给您自己思考。

### 分离易变与不易变部分
对于一篇文章来说，哪些是易变的，哪些是不易变（不变）的？
#### 不易变（不变）
+ 作者
+ 标题
+ 正文（字数）
+ 发布时间
+ 更新时间

#### 易变
+ 阅读次数
+ 评论
+ 喜欢该文章的用户与数量

拆分的好处在于，首先数据结构更清晰了，其次可以提高读写性能，当文章有了新评论，只需更新存放评论的数据表。如果不拆分，需要更新的记录占用的磁盘空间很大，这对磁盘IO速度是个考验。

对于拆分出的部分，可以继续运用这些原则进行设计。

### 应对可能出现的新需求
互联网应用的迭代周期很短，设计数据结构时应考虑到可能出现的新需求。拿喜欢该文章的用户与数量举例。

为了达到应用的要求，最简单的方式是将这些用户放在一条记录里，存储的字段可以是数组类型。这样设计，喜欢文章的用户信息与用户数量都能轻易获取，读写性能也很好。

某天，产品经理找到了你：“商量个新需求呗”，在文章下方加个模块，就叫“喜欢该文章的人还喜欢了”。你就懵逼了，没法破，除非重新设计数据结构，然后就带来了迁移数据一系列事情。其实这个需求挺合理的，说得高大上一点，这叫“精准推荐”。

很明显，将用户放在数组里只能支持“查询喜欢某文章的用户”，不支持“查询某用户喜欢的文章”。

### 适当的冗余
或许你已经注意到了，文章的标题下面有这篇文章的字数。计算文章的字数，有两个时机：

+ 保存文章时
+ 读取文章时

后者的优势在于数据表中少了一个字段，而且这个字段不是必需的。哪个时机更好？个人觉得前者更好，理由如下：

+ 计算长篇文章的字数是比较耗时的，应尽量减少计算次数
+ 总体来看，文章的保存次数远小于读取次数

如果能够提高应用的性能，适当的冗余是必要的。

# 结尾
本文总结了设计数据库时需遵守的几个原则
* 可用性
* 适当超前
* 应对新需求
* 分离易变与不易变部分
* 适当冗余

因为自知还未达到数据库专家的水准，写出的内容肯定有不准确的地方，欢迎批评指正。

写这篇文章的想法酝酿很久了，但一直没时间动笔。适逢中秋佳节，上海下着大雨，不便出门行走，便安坐在电脑前敲下了这千八百字，前后花了两个多小时。如果喜欢就点赞，能指出不足或提出意见就更好了。
_posts/quick-sort-and-its-testing.md0000644000175300017540000001015012775644164017321 0ustar  limdev-super---
title: 快速排序算法及其测试算法的原理与实现
date: 2016/09/27
tags: [算法]
---
## 快速排序简介

快速排序是一种分治的排序算法，是实践中最快的排序算法，理论上的时间复杂度为O(N*lgN)，最差情况的时间复杂度为O(N^2)，但稍加努力就可避免这种情况。

快速排序的步骤

1. 如果列表中的元素为0或1个，则返回
2. 选取标记值p
3. 将列表分为两部分s1、s2，需满足条件：s1中的元素均小于或等于p，s2中的元素均大于等于p，得到s1+p+s2
4. 对s1、s2重复2、3步骤，最终得到排序结果

从上面的步骤可以看出，快速排序需要递归运算。

## Python实现

采用三值取中间值的方法选取标记值，从而避免最差情况。

```python
def median3(L,a,b,c):
    if L[a] >= L[b] and L[b] >= L[c]:
        mid = L[b]
        i = b
    elif L[a] <= L[b] and L[b] <= L[c]:
        mid = L[b]
        i = b
    elif L[b] >= L[a] and L[a] >= L[c]:
        mid = L[a]
        i = a
    elif L[b] <= L[a] and L[a] <= L[c]:
        mid = L[a]
        i = a
    else:
        mid = L[c]
        i = c
    return [mid,i]  

def swap(L, i, j):
    tmp = L[i]
    L[i] = L[j]
    L[j] = tmp

def quickSort(L, low, high):
    if low < high:
        i = low
        j = high
        meta = median3(L, i, (i+j)/2, j)
        pivot = meta[0]
        pivotPos = meta[1]
        # move pivot to the right end
        swap(L, pivotPos, high) 
        
        while i < j:
            # pivot on the right end, starting from left
            while i < j and L[i] <= pivot:
                i = i+1
            while j > i and L[j] >= pivot:
                j = j-1
            swap(L, i, j)
        # move pivot to right position
        swap(L, i, high)
        
        quickSort(L, low, i-1)
        quickSort(L, i+1, high)

```

## 测试算法

排序结果正确，需满足条件

1. 列表除元素顺序变化外，没有别的变化
2. 列表中的元素是有序的

条件2容易实现，重点关注条件1

**如何确保列表除元素顺序变化外，没有别的变化？**

列表L1、L2满足以下三个条件即可

1. L1、L2中的元素数量相同
2. L1、L2的元素组成的集合相同（L1中的元素都在L2中，反之也成立）
3. L1、L2中元素的和相同

例如，列表L1=[2,3,2,2,3]，顺序打乱后得到L2=[2,2,3,3,2]，此时L1、L2满足以上三个条件。如果对L2进行以下操作，均会使其中的一个或多个条件不成立。

+ 添加/删除元素
+ 修改元素值

## 测试算法实现

```python
import sys
import random
import copy

# condition 2
def diff2List(l1,l2):
    diff = [val for val in l1 if val not in l2]
    for v in [val for val in l2 if val not in l1]:
        diff.append(v)
    return diff

def isListSorted(L):
    i = 0
    while i < len(L) - 2:
        if L[i] <= L[i+1]:
            i = i+1
        else:
            return [i, L[i], L[i+1]]
    return True

# condition 3
def sumList(L):
    sum = 0
    for i in L:
        sum = sum + i
    return sum

def randomList(length, maximum):
    l = []
    i = 0
    while i < length:
        l.append(random.randint(0, maximum))
        i = i+1
    return l

#
# Test usage: python <script_path> <test_times> <min_list_length> <max_list_length> <max_list_element_value>
#

testTimes = int(sys.argv[1])
minLength = int(sys.argv[2])
maxLength = int(sys.argv[3])
maxValue = int(sys.argv[4])

for i in range(testTimes):
    L = randomList(random.randint(minLength, maxLength), maxValue)
    print 'Test round #' + str(i)
    # original
    print L
    # deep copy for test
    tmpList = copy.deepcopy(L)
    quickSort(L, 0, len(L) - 1)
    if len(L) != len(tmpList) or diff2List(L, tmpList) != [] or sumList(L) != sumList(tmpList):
        print 'Bad #not coherent'
        break
    else:
        sorted = isListSorted(L)
        if sorted != True:
            print 'Bad #not sorted'
            print sorted
            break
    # after sort
    print L

```
_posts/refactor-decouple.md0000644000175300017540000000757512775644345015635 0ustar  limdev-super---
title: 代码重构之解耦合
date: 2016/08/23
tags: [重构]
---
最近在对业务代码进行重构，遇到了一些比较典型的“散发着难闻味道”的代码，可以用又臭又长来形容。

这部分的业务是发布动态，包括以下步骤：

+ 敏感词过滤
+ 话题提取
+ 动态数据入库
+ 敏感词记录
+ 话题及话题动态关联关系入库

之所以说重构前的代码“又臭又长”，首先最直观的一点，方法的行数超过了200行，其次上面四个步骤的逻辑全都写在了一起，没有按功能模块拆分，这也是方法过长的原因。

如果按功能划分，发布动态包含三个模块：

+ 敏感词模块
+ 动态模块
+ 话题模块

其中的**敏感词模块**和**话题模块**都是为**动态模块**服务的。一个动态可以有敏感词，也可以没有敏感词，比如用户分享一个链接，这就不需要做敏感词过滤与记录了，所以敏感词模块与动态模块应该是“**松耦合**”的。同样，一个动态可以包含话题，也可能不包含，所以话题模块与动态模块也应该是松耦合的。

既然敏感词模块与话题模块都是为动态模块服务的，动态模块就有必要与这两个服务模块建立一个**服务约定**：

+ 我需要什么样的服务
+ 我们之间如何建立耦合关系

## 我需要什么样的服务

在编程的世界里，约定可以抽象成接口
```php
interface PublishContract
{
    // Call this method before publishing
    public function beforePublish();
    
    // Call this method after publishing
    public function afterPublish();
}
```

对于敏感词模块和话题模块，只需要实现该接口，动态模块就可以根据约定调用它们提供的服务。

```php
class SensitiveWords implements PublishContract
{
    public function beforePublish()
    {
        // 
    }
    
    public function afterPublish()
    {
        //
    }
}
```
```php
class TopicObserver implements PublishContract
{
    public function beforePublish()
    {
        // 
    }
    
    public function afterPublish()
    {
        //
    }
}
```

这样动态模块就知道，在动态入库前调用服务模块的beforePublish服务，入库后调用服务模块的afterPublish服务。

## 我们如何建立耦合

耦合关系的建立应该由动态发布的调用方决定，动态模块需提供相应的接口，
```php
class Feeds
{
    // PublishContract[]
    protected $serviceModules = [];
    
    public function addServiceModule(PublishContract $service)
    {
        $this->serviceModules[get_class($service)] = $service;
    }
    
    public function removeServiceModule($serviceClassName)
    {
        unset($this->serviceModules[$serviceClassName]);
    }
    
    public function publish()
    {
        foreach ($this->serviceModules as $service) {
            $service->beforePublish();
        }
        
        // do something about publishment
        
        foreach ($this->serviceModules as $service) {
            $service->afterPublish();
        }
    
    }
}
```

这样，动态发布的调用方可以通过addServiceModule/removeServiceModule动态地添加/删除服务模块。

## UML图
![[from processon.com](https://www.processon.com/i/5429053c0cf2e6eabf125bb8 "")](http://upload-images.jianshu.io/upload_images/920803-890e52a28616f911?imageMogr2/auto-orient/strip%7CimageView2/2/w/1240)

## 重构带来的好处

### 松耦合
服务模块与核心模块是独立的，通过接口建立松耦合的关系；可动态添加/删除服务模块。

### 易于维护
服务模块的修改不会直接影响核心模块。

### 易于扩展
如果需要添加其它服务模块，只需实现服务约定的接口，并将新的服务模块动态添加到核心模块即可。
_posts/database-outernal-cache-and-read-speed-improvement.md0000644000175300017540000000251612775644117023763 0ustar  limdev-super---
title: 为数据库添加外部缓存带来的性能提升分析
date: 2016/07/29
tags: [数据库,缓存]
---
## 数据库
指持久化数据库，如

+ mysql
+ mongodb

## 缓存
指内存型的数据存储，如

+ redis
+ memcached


一个良好的缓存策略需兼顾

+ 命中率
+ 缓存数据与数据库数据的一致性


## 对命中率的兼顾

多大的命中率是好的？

用数学知识来分析这个问题，先设定几个关键的参数

+ T(c)：读一次缓存所需时间
+ T(d)：读一次数据库所需时间
+ G：缓存命中率

一次数据读取所需的时间的期望值为：
```c
T(c)*G + (T(c)+T(d))*(1-G)
```

增加数据库缓存的目标为提高数据读取速度，可以归结为一个表达式
```c
T(c)*G + (1-G)*(T(c)+T(d)) < T(d)
```
等同于
```c
T(c) - T(d)*G < 0
```
读取速度提升的比值为
```c
(T(d)*G - T(c))/T(d)
```
假如，T(d)=50ms，T(c)=10ms，G=0.6，读取速度提升比值为
```c
(50*0.6 - 10)/50 = 0.4
```
化为百分比也就是40%。

假如，T(d)=50ms，T(c)=10ms，G的值必须大于
```c
G = T(c)/T(d) = 0.2
```
才能期望读取速度得到提升。

可以看出

> 加入缓存不一定能够提升读取性能，这取决于缓存读取速度、数据库读取速度以及缓存的命中率。