Instagram 的 ID 生成策略是经过精心设计过的。¹ 每一秒 Instagram 都会收到无数用户上传的照片，在内部使用 [[PostgreSQL]] 分片存储到不同的服务器上。

这就产生了一个问题，要设计一个唯一 ID 生成方法用来标记系统中发布的每一张图片。

系统唯一 ID 需要满足如下条件：

• ID 应该是时间有序的，一组照片 ID 列表不再需要外部信息就可以排序（UUID 就不合适，因为完全无序）
• ID 最好是 64bit ，可以节省存储空间，索引也可以更小，也方便存储到 Redis 这样的系统中
• 系统应该尽可能少引入外部依赖 （比如使用 Snowflake，就需要引入 Zookeeper，Snowflake 服务）

所以最后 ID 的构成：

• 41 bit 用来存储毫秒时间（使用自定义 epoch 可以表示 41 年）
• 13 bit 存储逻辑分片 ID
• 10 bit 存储自增序列（对 1024 取模， id%1024），这意味着每一个 shard 每一毫秒可以生成 1024 个 ID

Instagram 在他的API文档和网站地址栏中对同一个 Post，使用了两种不一样的ID。在他们的 API 文档中，ids 类似于 908540701891980503_1639186 ， 但是在网站浏览器中则使用的是 ybyPRoQWzX 这样的ID。如果查看几组 ids，能够确性这两种类型的 ids 之间存在关联，Instagram 内部也不可能为同一个帖子存储两套 ids。

在仔细看一下数字的ID，908540701891980503 显然下划线分割的后面为作者的id，前面18位的id 被转为 ybyPRoQWzX 10 位的长度。URL 中的ID信息的密度显然要比数字的id要高。

如果做一个测试，将数字id由base10转为 base64，就得到

9:0:8:5:4:0:7:0:1:8:9:1:9:8:0:5:0:3_10
50:27:50:15:17:40:16:22:51:23_64

这样两组数据，如果将 base64 的数组和10位的id比较，得到

如果对该映射重新排序，则得到

看到该映射，很容易联想到由 A-Z 和 a-z 的关系

这个表和标准 base64 的加密表几乎一致，除了将 + 和 / 变为了 - 和 _ 。这个变动大概因为 / 在URLs中是特殊字符，而 + 号在 URL 中是特殊的请求字符。

启示

知道了两种ids之间的关系，联系一些已知的事实可以知道

唯一性

Instagram 在全平台使用唯一的ID，在 Web 端是 https://instagram.com/p/ybyPRoQWzX , 而这个 ID 能够被转成数字ID，因此我们也知道这个 ID 也是唯一的。

更加惊奇的是数字ID也能够被用于请求 Instagram 内部的接口，比如查看 Instagram 网站的请求，可以发现请求特定用户的 Posts 的接口为

https://instagram.com/<username>/media/?max_id=<numeric id>

比如说 https://instagram.com/gitamba/media/?max_id=915362118751716223_7985735 而事实上，省略了后面的用户ID 也能更能够照样获得结果。而后面加任意内容都会被忽略

https://instagram.com/gitamba/media/?max_id=915398248830305252_whatever

这个请求的到内容和之前的内容一样。

进一步分析

如果知道 Instagram 产生 posts 的唯一ID 的原理 那么可以从 ID 中获取更多信息。在 Instagram 的文章中，没有提及内部的 epoch 是什么时候，但是可以通过计算来获取一个比较准确的值。

上面是三个已知发布时间的IDs， post 的id 是64bit ，如果转成 64 bits

截取前41bits，表示的从 Instagram 内部 epoch 开始流逝的时间，毫秒

最后在用创建post 的时间 unix time 来减去从 id 中获取的时间，得到

如果计算一切都正确，得到的值应该是相等的。微小的误差来自，创建 post 的时间是秒，而 id中获取的时间是毫秒。

经过一系列计算，大致可以知道 Instagram epoch 时间开始于 1314220021 ，也就是 9:07pm UTC on Wednesday, August 24, 2011 看起来是一个随机的 epoch，但猜测可能是 Instagram 内部将 id 由自增长模式转变为现在模式的时间。

ids for testing

翻译自： https://carrot.is/coding/instagram-ids

iperf 命令是一个网络性能测试工具。iperf 可以测试 TCP 和 UDP 带宽质量。iperf 可以测量最大 TCP 带宽，具有多种参数和 UDP 特性。iperf 可以报告带宽，延迟抖动和数据包丢失。利用 iperf 这一特性，可以用来测试一些网络设备如路由器，防火墙，交换机等的性能。

iperf 在内存中运行，不会涉及到文件系统。iperf 存在非常多的版本，Windows，Linux，Android，iOS 都有对应的版本。可以到官网下载

安装

Linux 下安装：

sudo apt-get install iperf

其他系统到参考官网

iperf 是一个命令行工具，当然如果搜索也能发现 GUI 的工具，比如 jperf, xjerf 等等。不过还是推荐使用命令行。

iperf 使用非常简单的 C/S 架构，client 使用 -c 参数，服务端使用 -s。

实例

宽带测试通常采用 UDP 模式，首先以链路理论带宽作为数据发送速率进行测试，从客户端到服务器之间的链路理论带宽为 100 Mbps，先使用 -b 100M 测试，然后根据测试结果，以实际带宽测试

服务端：

iperf -u -s # UDP 模式

客户端第一种模式

iperf -u -c server_address -b 100M -t 60

在 UDP 模式下，以 100Mbps 为数据发送速率，客户端到 IP 上传带宽测试，测试时间 60 秒。

客户端同时发起 30 个线程连接，以 5Mbps 为数据发送速率

iperf -u -c server_address -b 5M -P 30 -t 60

或者客户端直接进行上下行带宽测试

iperf -u -c server_address -b 100M -d -t 60

如果不加 -u 则使用 TCP 模式

iperf -s

客户端持续 60 秒

iperf -c server_address -t 60

设置服务端端口

使用 -p port 来指定服务端端口，默认是 5201

间隔时间报告

使用 -i interval 参数来表示间隔时间

iperf -c 192.168.2.105(server address) -i 2

表示间隔 2 秒打印结果

iperf 版本区别

iperf 自身存在很多个版本，Ubuntu 默认源中可能有一个叫做 iperf, 也有一个叫做 iperf3, 这两个是不同版本的 iperf, 在使用 iperf 的时候要确保版本一致。不同的版本有不同的架构和不同的特性。

然而这两个版本 iperf3 是不兼容 iperf 2.x 的。可以这么理解 iperf 是内存中的网络性能测试工具，而 iperf3 是从头还是编写的一套新程序，目标是简化代码量，并且设计为工具库，可以嵌入到其他工具中。¹

两者不同的区别

服务端：

客户端：

iperf3 增加了一些额外的功能，比如 -i 模式可以提供 TCP retransit （中继）结果，并且 verbose 模式可以打印更多有效的信息，比如 CPU 利用率等等。

更多的使用可以参考这里

更多 iperf 2.0.5 和 iperf 2.0.8+ 和 iperf 3.1.5+ 的区别可以在这里 查看。

使用

外延

• 另外一个 TCP 性能测试工具 nuttcp

Android

在 Android 手机上可以使用一款叫做 Magic iPerf 的工具来进行测试。

或者使用 Termux 来直接使用命令测试。

reference

• https://youtu.be/W9o7L-GWxNY
• http://man.linuxde.net/iperf

MD5 全称为 Message-Digest Algorithm ，一般用来保证信息传输的完整一致，MD5 的结果是固定长度 128bit 。MD5 算法最开始是为密码学而设计，但是后来被发现有很大的缺陷，所以后来就用来校验文件的完整性（无意识而造成的不完整，比如下载）。MD5 在非密码学领域也有其他用途，比如在一个数据库中快速检查一个 key 是否存在。

密码学的 hash 方法一个最基本的要求是，计算机难以通过计算来找到两个不同的内容拥有同一个 hash 值，MD5 无法满足该基本条件。MD5 算法无法防止碰撞，无法用于安全性验证，对于安全性高的资料，建议使用其他算法。

MD5 是 Ronald Rivest 在 1991 年设计用来代替 MD4, 具体的说明定义在 RFC 1321 中。

MD5 的用途

• 校验文件完整性，比如下载一个文件包，或者发送一个文件，接受者收到之后用提供方提供的 md5 来校验
• 将明文信息 hash 到密文信息，在只需要对比一致性时可以使用，比如密码校验（但一般不建议直接使用 md5 hash 密码）
• git 的 commit ID 也是 MD5，未来可能慢慢被 SHA 代替

原理

MD5 的输入不定长，输出定长 128 bits。MD5 计算方式可以分为几个步骤：

• 输入信息被分成每一块 512 bit 长的 (16 个 32 位子分组）组，此时必定有剩余，对剩余部分，先填充一个 1，然后是若干 0，最后预留出 64 位来保存前面信息的长度（这个信息的长度包括若干 512 bit 的区块 + 1 + 若干 0 组成），补充完成后整体一定是 512 bit 的倍数（包括三个部分，原始数据 + 补充数据 + 信息长度）。如果信息的长度超过了 64 位能够表示的范围，则取低 64 位。

• 再得到 N*512 个数据组之后，初始 A B C D 四个 32 bit 长度的变量，里面依次存放十六进制

  A: 01 23 45 67 B: 89 ab cd ef C: fe dc ba 98 D: 76 54 32 10

• 分组处理数据，已经将数据分成了 512 位一组，512 位又可以分成 16 * 32 位，小组中共有 16 个 32 位的子分组，用 M0 到 M15 来表示
• 常数 Ti 是 4294967296*abs(sin(i)）的整数部分，i 取值从 1 到 64

• 接下来定义四个线性函数，每一个方法接受三个 32 位的 word 然后产生一个 32 位的 word

  F(X,Y,Z) = (XY) | (not(X) Z) if X then Y else Z G(X,Y,Z) = (XZ) | (Y not(Z)) if Z then X else Y H(X,Y,Z) = X xor Y xor Z I(X,Y,Z) = Y xor (X | not(Z))

伪代码：

主要分成这几部分，先针对第一个分组，处理 16 个子分组，通过初始 A B C D 计算得到新的 A B C D，然后将新的 A B C D 加到原来的 A B C D 中。如此往复直到计算完所有的分组，最终得到的 ABCD 就是 MD5 的值。

/* Process each 16-word block. */
For i = 0 to N/16-1 do

  /* Copy block i into X. */
  For j = 0 to 15 do
    Set X[j] to M[i*16+j].
  end /* of loop on j */

  /* 另存一份 */
  AA = A
  BB = B
  CC = C
  DD = D

  /* Round 1. */
  /* Let [abcd k s i] denote the operation
       a = b + ((a + F(b,c,d) + X[k] + T[i]) <<< s). */
  /* Do the following 16 operations. */
  [ABCD  0  7  1]  [DABC  1 12  2]  [CDAB  2 17  3]  [BCDA  3 22  4]
  [ABCD  4  7  5]  [DABC  5 12  6]  [CDAB  6 17  7]  [BCDA  7 22  8]
  [ABCD  8  7  9]  [DABC  9 12 10]  [CDAB 10 17 11]  [BCDA 11 22 12]
  [ABCD 12  7 13]  [DABC 13 12 14]  [CDAB 14 17 15]  [BCDA 15 22 16]

  /* Round 2. */
  /* Let [abcd k s i] denote the operation
       a = b + ((a + G(b,c,d) + X[k] + T[i]) <<< s). */
  /* Do the following 16 operations. */
  [ABCD  1  5 17]  [DABC  6  9 18]  [CDAB 11 14 19]  [BCDA  0 20 20]
  [ABCD  5  5 21]  [DABC 10  9 22]  [CDAB 15 14 23]  [BCDA  4 20 24]
  [ABCD  9  5 25]  [DABC 14  9 26]  [CDAB  3 14 27]  [BCDA  8 20 28]
  [ABCD 13  5 29]  [DABC  2  9 30]  [CDAB  7 14 31]  [BCDA 12 20 32]

  /* Round 3. */
  /* Let [abcd k s t] denote the operation
       a = b + ((a + H(b,c,d) + X[k] + T[i]) <<< s). */
  /* Do the following 16 operations. */
  [ABCD  5  4 33]  [DABC  8 11 34]  [CDAB 11 16 35]  [BCDA 14 23 36]
  [ABCD  1  4 37]  [DABC  4 11 38]  [CDAB  7 16 39]  [BCDA 10 23 40]
  [ABCD 13  4 41]  [DABC  0 11 42]  [CDAB  3 16 43]  [BCDA  6 23 44]
  [ABCD  9  4 45]  [DABC 12 11 46]  [CDAB 15 16 47]  [BCDA  2 23 48]

  /* Round 4. */
  /* Let [abcd k s t] denote the operation
       a = b + ((a + I(b,c,d) + X[k] + T[i]) <<< s). */
  /* Do the following 16 operations. */
  [ABCD  0  6 49]  [DABC  7 10 50]  [CDAB 14 15 51]  [BCDA  5 21 52]
  [ABCD 12  6 53]  [DABC  3 10 54]  [CDAB 10 15 55]  [BCDA  1 21 56]
  [ABCD  8  6 57]  [DABC 15 10 58]  [CDAB  6 15 59]  [BCDA 13 21 60]
  [ABCD  4  6 61]  [DABC 11 10 62]  [CDAB  2 15 63]  [BCDA  9 21 64]

  /* Then perform the following additions. (That is increment each
     of the four registers by the value it had before this block
     was started.) */
  A = A + AA
  B = B + BB
  C = C + CC
  D = D + DD

end /* of loop on i */

最后每一轮更新之后进入下一轮更新，最后会在 ABCD 中保存 4 * 32 位最后 Hash 的结果。

检查文件 MD5

128 位的 MD5 一般表示为 32 位的十六进制数。

CyanogenMod 中有一段检查文件 MD5 的代码：

/*
 * Copyright (C) 2012 The CyanogenMod Project
 *
 * * Licensed under the GNU GPLv2 license
 *
 * The text of the license can be found in the LICENSE file
 * or at https://www.gnu.org/licenses/gpl-2.0.txt
 */

package com.cyanogenmod.updater.utils;

import android.text.TextUtils;
import android.util.Log;

import java.io.File;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.InputStream;
import java.math.BigInteger;
import java.security.MessageDigest;
import java.security.NoSuchAlgorithmException;

public class MD5 {
    private static final String TAG = "MD5";

    public static boolean checkMD5(String md5, File updateFile) {
        if (TextUtils.isEmpty(md5) || updateFile == null) {
            Log.e(TAG, "MD5 string empty or updateFile null");
            return false;
        }

        String calculatedDigest = calculateMD5(updateFile);
        if (calculatedDigest == null) {
            Log.e(TAG, "calculatedDigest null");
            return false;
        }

        Log.v(TAG, "Calculated digest: " + calculatedDigest);
        Log.v(TAG, "Provided digest: " + md5);

        return calculatedDigest.equalsIgnoreCase(md5);
    }

    public static String calculateMD5(File updateFile) {
        MessageDigest digest;
        try {
            digest = MessageDigest.getInstance("MD5");
        } catch (NoSuchAlgorithmException e) {
            Log.e(TAG, "Exception while getting digest", e);
            return null;
        }

        InputStream is;
        try {
            is = new FileInputStream(updateFile);
        } catch (FileNotFoundException e) {
            Log.e(TAG, "Exception while getting FileInputStream", e);
            return null;
        }

        byte[] buffer = new byte[8192];
        int read;
        try {
            while ((read = is.read(buffer)) > 0) {
                digest.update(buffer, 0, read);
            }
            byte[] md5sum = digest.digest();
            BigInteger bigInt = new BigInteger(1, md5sum);
            String output = bigInt.toString(16);
            // Fill to 32 chars
            output = String.format("%32s", output).replace(' ', '0');
            return output;
        } catch (IOException e) {
            throw new RuntimeException("Unable to process file for MD5", e);
        } finally {
            try {
                is.close();
            } catch (IOException e) {
                Log.e(TAG, "Exception on closing MD5 input stream", e);
            }
        }
    }
}

reference

• https://en.wikipedia.org/wiki/MD5
• https://tools.ietf.org/html/rfc1321
• https://github.com/CyanogenMod/android_packages_apps_CMUpdater/blob/cm-10.2/src/com/cyanogenmod/updater/utils/MD5.java

nodejs wrapper: https://github.com/Level/levelup

源码: https://github.com/google/leveldb

LevelDB 的原理 介绍 还有 这篇

LevelDB 的 C++ 接口 使用 LevelDB 在 iOS 下的 使用

在分布式系统存在多个 Shard 的场景中, 同时在各个 Shard 插入数据时, 怎么给这些数据生成全局的 unique ID? 在单机系统中 (例如一个 MySQL 实例), unique ID 的生成是非常简单的, 直接利用 MySQL 自带的自增 ID 功能就可以实现.

但在一个存在多个 Shards 的分布式系统 (例如多个 MySQL 实例组成一个集群, 在这个集群中插入数据), 这个问题会变得复杂, 所生成的全局的 unique ID 要满足以下需求:

• 唯一性，保证生成的 ID 全局唯一
• 今后数据在多个 Shards 之间迁移不会受到 ID 生成方式的限制
• 有序性，生成的 ID 中最好能带上时间信息, 例如 ID 的前 k 位是 Timestamp, 这样能够直接通过对 ID 的前 k 位的排序来对数据按时间排序
• 生成的 ID 最好不大于 64 bits
• 可用性，生成 ID 的速度有要求. 例如, 在一个高吞吐量的场景中, 需要每秒生成几万个 ID (Twitter 最新的峰值到达了 143,199 Tweets/s, 也就是 10万+/秒)
• 整个服务最好没有单点

在要满足前面 6 点要求的场景中, 怎么来生成全局 unique ID 呢?

数据库自增ID

数据库单表，使用 auto increment 来生成唯一全局递增ID。

优势是无需额外附加操作，定长增长，单表结构中唯一性，劣势是高并发下性能不佳，生产的上限是数据库服务器单机的上限，水平扩展困难，分布式数据库下，无法保证唯一性。

UUID

如果没有上面这些限制, 问题会相对简单, 例如: 直接利用 UUID.randomUUID() 接口来生成 unique ID (http://www.ietf.org/rfc/rfc4122.txt). 但这个方案生成的 ID 有 128 bits, 另外, 生成的 ID 中也没有带 Timestamp 一般编程语言中自带 UUID 实现， Java 中 UUID.randomUUID().toString() 产生的ID 不依赖数据库实现。

优势是，本地生成ID，无需远程调用，全局唯一，水平扩展能力好。劣势是，ID 有 128 bits 长，占空间大，生成字符串类型，索引效率低，生成的 ID 中没有带 Timestamp 无法保证时间递增。

Flickr 全局主键

Flickr 的做法¹ 是使用 MySQL 的自增ID， 和 replace into 语法。但他这个方案 ID 中没有带 Timestamp, 生成的 ID 不能按时间排序

创建64位自增ID，首先创建表

CREATE TABLE `Tickets64` (
  `id` bigint(20) unsigned NOT NULL auto_increment,
  `stub` char(1) NOT NULL default '',
  PRIMARY KEY  (`id`),
  UNIQUE KEY `stub` (`stub`)
) ENGINE=MyISAM

SELECT * from Tickets64 假设表中有一行

+-------------------+------+
| id                | stub |
+-------------------+------+
| 72157623227190423 |    a |
+-------------------+------+

那么如果需要产生一个新的全局 64 bits 的ID，只要执行 SQL：

REPLACE INTO Tickets64 (stub) VALUES ('a');
SELECT LAST_INSERT_ID();

SQL 返回的ID就是要产生的全局唯一ID。使用 REPLACE INTO 代替 INSERT INTO 的好处是避免表行数太多。 stub 要设为唯一索引。

Flickr 内部运行两台 ticket servers，通过两台机器做主备和负载均衡。

TicketServer1:
auto-increment-increment = 2
auto-increment-offset = 1

TicketServer2:
auto-increment-increment = 2
auto-increment-offset = 2

Twitter Snowflake

Twitter 利用 Zookeeper 实现一个全局的 ID 生成服务 Snowflake: https://github.com/twitter/snowflake

Snowflake 生成的 unique ID 的组成 (由高位到低位):

• 41 bits: Timestamp 毫秒级
• 10 bits: 节点 ID datacenter ID 5 bits + worker ID 5 bits
• 12 bits: sequence number

一共 63 bits ,其中最高位是 0

unique ID 生成过程:

• 41 bits 的 Timestamp: 每次要生成一个新 ID 的时候, 都会获取一下当前的 Timestamp, 然后分两种情况生成 sequence number:

    - 如果当前的 Timestamp 和前一个已生成 ID 的 Timestamp 相同 (在同一毫秒中), 就用前一个 ID 的 sequence number + 1 作为新的 sequence number (12 bits); 如果本毫秒内的所有 ID 用完, 等到下一毫秒继续 (**这个等待过程中, 不能分配出新的 ID**)
    - 如果当前的 Timestamp 比前一个 ID 的 Timestamp 大, 随机生成一个初始 sequence number (12 bits) 作为本毫秒内的第一个 sequence number
  

• 10 bits 的机器号, 在 ID 分配 Worker 启动的时候, 从一个 Zookeeper 集群获取 (保证所有的 Worker 不会有重复的机器号)

整个过程中, 只有在 Worker 启动的时候会对外部有依赖 (需要从 Zookeeper 获取 Worker 号), 之后就可以独立工作了, 做到了去中心化.

异常情况讨论:

在获取当前 Timestamp 时, 如果获取到的时间戳比前一个已生成 ID 的 Timestamp 还要小怎么办? Snowflake 的做法是继续获取当前机器的时间, 直到获取到更大的 Timestamp 才能继续工作 (在这个等待过程中, 不能分配出新的 ID)

从这个异常情况可以看出, 如果 Snowflake 所运行的那些机器时钟有大的偏差时, 整个 Snowflake 系统不能正常工作 (偏差得越多, 分配新 ID 时等待的时间越久)

从 Snowflake 的官方文档 (https://github.com/twitter/snowflake/#system-clock-dependency) 中也可以看到, 它明确要求 “You should use NTP to keep your system clock accurate”. 而且最好把 NTP 配置成不会向后调整的模式. 也就是说, NTP 纠正时间时, 不会向后回拨机器时钟.

下面是 Snowflake 的其他变种， Instagram 产生 ID 的方法也借鉴 Snowflake

雪花算法存在的问题

• 时间拨回问题
• 机器ID 的分配和回收问题
• 机器 ID 的上限问题

Boundary flake

代码地址：https://github.com/boundary/flake

变化:

ID 长度扩展到 128 bits:

• 最高 64 bits 时间戳;
• 然后是 48 bits 的 Worker 号 (和 Mac 地址一样长);
• 最后是 16 bits 的 Seq Number

由于它用 48 bits 作为 Worker ID, 和 Mac 地址的长度一样, 这样启动时不需要和 Zookeeper 通讯获取 Worker ID. 做到了完全的去中心化

基于 Erlang ，这样做的目的是用更多的 bits 实现更小的冲突概率，这样就支持更多的 Worker 同时工作。同时, 每毫秒能分配出更多的 ID。

Simpleflake

源代码：https://github.com/SawdustSoftware/simpleflake

Simpleflake 的思路是取消 Worker 号, 保留 41 bits 的 Timestamp, 同时把 sequence number 扩展到 22 bits;

Simpleflake 的特点:

• sequence number 完全靠随机产生 (这样也导致了生成的 ID 可能出现重复)
• 没有 Worker 号, 也就不需要和 Zookeeper 通讯, 实现了完全去中心化
• Timestamp 保持和 Snowflake 一致, 今后可以无缝升级到 Snowflake

Simpleflake 的问题就是 sequence number 完全随机生成, 会导致生成的 ID 重复的可能. 这个生成 ID 重复的概率随着每秒生成的 ID 数的增长而增长.

所以, Simpleflake 的限制就是每秒生成的 ID 不能太多 (最好小于 100次/秒, 如果大于 100次/秒的场景, Simpleflake 就不适用了, 建议切换回 Snowflake).

Instagram 的做法

Instagram 参考 Flickr 的方案，结合 Twitter 的经验，利用 PostgreSQL 数据库的特性，实现了一个更加简单可靠的 ID 生成服务。 Instagram 的分布式存储方案: 把每个 Table 划分为多个逻辑分片 (logic Shard), 逻辑分片的数量可以很大, 例如 2000 个逻辑分片。然后制定一个规则, 规定每个逻辑分片被存储到哪个数据库实例上面; 数据库实例不需要很多. 例如, 对有 2 个 PostgreSQL 实例的系统 (instagram 使用 PostgreSQL); 可以使用奇数逻辑分片存放到第一个数据库实例, 偶数逻辑分片存放到第二个数据库实例的规则

每个 Table 指定一个字段作为分片字段 (例如, 对用户表, 可以指定 uid 作为分片字段)

插入一个新的数据时, 先根据分片字段的值, 决定数据被分配到哪个逻辑分片 (logic Shard) 然后再根据 logic Shard 和 PostgreSQL 实例的对应关系, 确定这条数据应该被存放到哪台 PostgreSQL 实例上

Instagram 在设计ID时考虑了如下因素：

• 生成的IDs 需要按照时间排序，比如查询一组照片时就不需要额外获取照片更多的信息来进行排序
• IDs 64bits 索引，或者存储在 Redis 中
• The system should introduce as few new ‘moving parts’ as possible — a large part of how we’ve been able to scale Instagram with very few engineers is by choosing simple, easy-to-understand solutions that we trust.

Instagram unique ID 的组成:

• 41 bits 表示 Timestamp (毫秒), 能自定义起始时间 epoch
• 13 bits 表示 每个 logic Shard 的代号 (最大支持 8 x 1024 个 logic Shards)
• 10 bits 表示 sequence number; 每个 Shard 每毫秒最多可以生成 1024 个 ID

假设2011年9月9号下午 5 点钟， epoch 开始于 2011 年 1 月1 号，那么已经有 1387263000 毫秒经过，那么前 41 bits 是

id = 1387263000 <<(64-41)

接下来13位由分片ID决定，假设按照 user ID 来分片，有 2000 个逻辑分片，如果用户的ID 是 31341 ， 那么分片 ID 是 31341%2000 -> 1341 ，所以接下来的13位是：

id |= 1341 <<(63-41-13)

最后，每个表自增来填补剩下的 bits，假设已经为表生成了 5000 个 IDs，那么下一个值是 5001，然后取模 1024

id |= (5001 % 1024)

sequence number 利用 PostgreSQL 每个 Table 上的 auto-increment sequence 来生成。如果当前表上已经有 5000 条记录, 那么这个表的下一个 auto-increment sequence 就是 5001 (直接调用 PL/PGSQL 提供的方法可以获取到) 然后把 这个 5001 对 1024 取模就得到了 10 bits 的 sequence number。

instagram 这个方案的优势在于:

利用 logic Shard 号来替换 Snowflake 使用的 Worker 号, 就不需要到中心节点获取 Worker 号了. 做到了完全去中心化

另外一个附带的好处就是, 可以通过 ID 直接知道这条记录被存放在哪个 logic Shard 上。同时, 今后做数据迁移的时候, 也是按 logic Shard 为单位做数据迁移的, 所以这种做法也不会影响到今后的数据迁移

MongoDB ObjectID

MongoDB 的 ObjectID² 采用 12 个字节的长度，将时间戳编码在内。

• 其中前四个字节时间戳，从标准纪元开始，单位秒，时间戳和后5个字节保证了秒级别的唯一性，保证插入顺序以时间排序。
• 接着前四个字节时间戳的后面三个字节为机器号，这三个字节为所在主机唯一标识，一般为机器名散列值。
• 接着两个字节为PID标识，同一台机器中可能运行多个Mongo实例，用PID来保证不冲突
• 后三个字节为递增序号，自增计数器，来确保同一秒内产生的 ObjectID 不出现冲突，允许 256 的三次方 16777216 条记录。

reference

• https://engineering.instagram.com/sharding-ids-at-instagram-1cf5a71e5a5c
• http://darktea.github.io/notes/2013/12/08/Unique-ID
• http://www.cnblogs.com/flyingeagle/articles/7124233.html

Flower 是一个基于 Web 的监控和管理工具，可以用在 Celery 集群的监控和管理。和 Celery 配合使用非常不错。

Flower 可以查看 Celery 队列中 task 的数量，可以用来监控 worker 的状态并进行简单的管理，比如调整 worker 的 pool size 和 autoscale 设置，可以用来查看当前处理的 tasks， 等等。

安装

使用 pip 安装 Flower

pip install flower

或者安装开发版

pip install https://github.com/mher/flower/zipball/master

使用 #{Usage}

直接使用下面命令开启本地监听 http://localhost:5555

flower -A proj --port=5555

或者从 Celery 中开启

celery flower -A proj --address=127.0.0.1 --port=5555

如果要暴露给外网访问可以 --address=0.0.0.0:

celery flower -A worker --address=0.0.0.0 --port=5555 --basic_auth=name:password

使用 --basic_auth 来开启 HTTP 简单验证

reference

• https://github.com/mher/flower

zip 是一个非常常见的压缩工具，很多平台包括 Unix, VMS, MSDOS, OS/2, Windows 9x/NT/XP, Minix, Atari, Macintosh, Amiga, and Acorn RISC OS 等都有应用。zip 结合了打包和压缩。

基本使用

参数非常多

zip options archive inpath infile
zip [-aABcdDeEfFghjklLmoqrRSTuvVwXyz!@$] [--longoption ...]  [-b path] [-n suffixes] [-t date] [-tt date] [zipfile [file ...]]  [-xi list]

• -h 帮助
• -d 把压缩文件解到指定目录下
• -m 将文件压缩后，删除源文件
• -q 安静模式，压缩时不显示执行的执行过程
• -r 将执行的目录下所有子目录及文件一同处理
• -S 包含系统文件和隐藏文件
• -n 不覆盖已有的文件
• -o 覆盖已存在的文件且不要求用户确认
• -x 文件列表 解压缩文件，但不包括指定的 file 文件
• -v 查看压缩文件目录，但不解压
• -t 测试文件有无损坏，但不解压
• -j 不重建文档的目录结构，把所有文件解压到同一目录下

实例

将文件及文件夹打包到 dest.zip 中。

zip -r dest.zip path/to/folder file
zip dest.zip file1 file2

压缩时排除某些目录

zip -r dest.zip folder -x *.git*

使用密码压缩文件

zip -r -P password dest.zip file folder

解压文件

unzip dest.zip

解压文件到特定文件夹 -d 参数指定

unzip dest.zip -d /path/to/folder

不解压查看压缩包内部内容

unzip -l dest.zip
unzip -v dest.zip

在 Linux 下经常遇到 zip 乱码的情况呢，其实因为 Windows 或者其他系统下生成默认使用 GBK/GB2312 编码，而在 Linux 下默认为 UTF8，所以可以使用 unzip 的 -O 参数，这个参数 只有 unzip 1.6 及以上版本才有。

unzip -O cp936 file.zip -d /path/to/folder

外延

Linux 下经常遇到 tar.gz tar.bz2 这样的压缩包，这个时候可能就需要使用到 tar 这个命令。

reference

• man zip
• man unzip

下面是一次 vim 的组内介绍的大纲。记录一下。

大纲

Vim 多模式编辑器

Normal mode
Insert mode
Visual mode
Command mode

插入模式

i 进入 insert mode，在光标为之前进入插入模式
I 行首非空字符前插入 , I 等同于 `^i`
s 删除光标下字符，并进入 insert mode， 等同于 `cl`
S 删除光标所在一行，并进入 insert mode 行首 , 等同于 `^C`
a 光标之后进入 insert mode
A 光标移动到行尾并进入 insert mode , 等同于 `$a`
o 在光标下一行插入一行，并进入 insert mode , 等同于 `A<CR>`
O 在光标上一行插入新行，并进入 insert mode , O 等同于 `ko`
C 删除光标后到行尾内容，并进入 insert mode , C 其实等同于 `c$`
cc 删除行，并进入插入模式
Esc 退出 Insert 模式

Example: this is a text for testing mode.

移动

h,j,k,l

    k
    ^
h <   > l
    v
    j

H,M,L
w,W,e,E,b,B
%
0,^,$
gg, G
fx,Fx,tx,Tx,
'', g;     move cursor to last edit change

Example: This is a sentence for testing moving with a word and WO-RD test.

编辑

p   光标之后粘贴 (p)aste
P   paste before the cursor
yy  复制当前行
y   Yank 复制。Example: yw (yank word) 光标停留到词第一个字母上 yw 复制单词
y0  copy the data from cursor to begining of the line
y$  copy the data from cursor to end of the line
x   删除光标下单个字符，将其放到粘贴板，剪切
X   向前删除一个字符，相当于 Backspace
dd  删除光标所在一行，并把该行复制
dw  删除光标所在词 (d)elete (w)ord
d0  删除光标到该行最前
d^  删除光标到行首非空白字符
d$  删除光标到该行最后
J   删除光标所在行的换行符
r,R 替换

组合

Operator + Motion = Action

dw      delete word
da'     delete what in ' and include '

Example:
This is an 'example' for "word-to-delete".
add quote to this "word"

搜索

/pattern  - 正向搜索，从光标处开始向文件末搜索
?pattern  - 反向搜索，从光标处开始向文件首搜索
n  - 下一个，往下执行搜索命令
N  - 上一个
*  - Word under cursor - forward (bounded)
#  - Word under cursor - backward (bounded)
:n1, n2s/p1/p2/g - 将第 n1 至 n2 行中所有 p1 均用 p2 替代
:g/p1/s//p2/g - 将文件中所有 p1 均用 p2 替换

替换

:s/p1/p2/g - 将当前行中所有 p1 均用 p2 替代
:%s/old/new/g 全局替换
:'<,'>s/old/new/g 选中之后替换
:g/^$/d 删除所有空行

Example:

Text Object

dit, di', di", di), di}, di],
yi), yi]
vi', vit
ciw, ciw)

macro

qw        开启 record macro, 保存到寄存器 w
q         结束录制

Example:
int a = 1
int b = 2
int c = a+b
print a
print b
print c

register

共有 9 大类寄存器

• The unnamed register “”
• 10 numbered registers “0 to “9 数字寄存器中保存着 yank 的内容
• The small delete register “-
• 26 named registers “a to “z or “A to “Z 可供自定义使用
• four read-only registers “:, “., “% and “#
• the expression register “=
• The selection and drop registers “*, “+ and “~
• The black hole register “_
• Last search pattern register “/

寄存器访问 “a 寄存器前加 “

其他操作

:reg a 查看寄存器
""   noname buffer last dcsxy
"_   blackhole register
"%   filename register
"/   last search register
":   last command
insert mode <C-r> a insert text in register a
"ap  Normal mode paste text in register a

Plugin

surround.vim

cs"'      change surround " to '
cs'<q>    change surround ' to <q>
ds'       delete surround '
ysiw"     add " to word
yss)      add ) to entire line

Example:
"Hello world!"  and other strings

start

vimutor

总结

更快的编码效率

Charles 是Mac上一款非常流行的抓包软件 ， 但其实各大平台上 Charles 都有安装包。这篇文章主要就是讲一下在 Linux 平台上（Debian/Ubuntu) 系上安装 Charles 。

使用 APT 源安装

Charles 拥有 APT 源，首先安装 PGP 公钥，当前公开的秘钥为 1AD28806， 他的 fingerprint 为 4BA7 DB85 7B57 0089 7420 96E1 5F16 B97C 1AD2 8806：

wget -q -O - https://www.charlesproxy.com/packages/apt/PublicKey | sudo apt-key add -

或者

sudo apt-key adv --keyserver pgp.mit.edu --recv-keys 1AD28806

然后添加源

sudo sh -c 'echo deb https://www.charlesproxy.com/packages/apt/ charles-proxy main > /etc/apt/sources.list.d/charles.list'

最后更新源并安装

sudo apt-get update && sudo apt-get install charles-proxy

安装完成之后会在 /usr/bin 下安装可执行二进制，该源中还包含 beta 版本的 Charles，可以通过包名 charles-proxy-beta 来安装。

使用文件安装

在官方下载最新的安装包: https://www.charlesproxy.com/download/latest-release/

charles.jar 路径

charles.jar 文件在三大平台上的位置如下：

Mac: /Applications/Charles.app/Contents/Java/charles.jar
Windows: C:\Program Files\Charles\lib\charles.jar
Linux: /usr/lib/charles-proxy/charles.jar

计算机中通常所说的寄存器 Register 一般指的是 CPU 中的寄存器，用来暂存 CPU 处理所需要的指令，数据等等。 Vim 中同样也有寄存器的概念，使用的方式和概念也和 CPU 是非常类似的。

Vim 的寄存器可以看成 Vim 中额外用来存储信息的区域，虽然看不见，但是如果使用 x, s, y, p 等等命令的时候都无意识的使用到了 Vim 的寄存器 (register).

Vim 中每一个 register 都可以通过添加双引号的方式来访问，比如 "a 来访问 a 寄存器。

可以通过选择然后使用 y 来将内容放到寄存器中，比如 "ay 来将选择的内容 yank 复制到 "a 寄存器。 可以使用 "ap 来粘贴 a 寄存器中的内容。

同样可以再 Insert mode 下使用 Ctrl + r 再加 a 寄存器名字来插入。这会将寄存器内容粘贴进当前编辑位置。

可以使用 :reg 命令来查看所有寄存器及其内容，或者直接在后面添加寄存器名字来查看关心的内容 :reg a b c

:reg a b c
--- Registers ---
"a   register a content
"b   register b content
"c   register c content

默认寄存器

Vim 有自己的 unnamed （无名寄存器）或者说默认寄存器，可以通过 "" 来访问。任何被 d, c, s, x 删除或者 y 复制的内容都会被存放在该寄存器中，使用 p 粘贴时也是中该寄存器中粘贴内容。直接使用 p 其实等效于 ""p 。

有名寄存器

Vim 提供 26 个英文字母命名的有名寄存器 (:h quote_alpha)。这就意味着可以

• 剪切 "ad{motion}
• 复制 "ay{motion}
• 粘贴 "ap or "aP

多达 26 段文本。

数字寄存器

当使用 yank 复制一些内容，然后又执行了 d 命令，会发现粘贴时，当时 yank 的内容被 d 命令中的内容替换了，这是 Vim 非常常见的一个问题，然而问题并不在 Vim，而是 Vim 把 yank 的内容 ，delete 的内容都放到了 unnamed register 中了，但是复制的内容并没有丢失，并不需要再次回到想要复制的地方再次 yank 一遍。

这里就要介绍 Vim 的另外一种寄存器 —- 数字寄存器 numbered registers , 正如他的名字一样，数字寄存器的名字就是 "0 到 "9 。

"0 寄存器永远保存着 yank 的最新内容，其他寄存器保存这历史 9 个内容，从 1 到 9 从新到老。如果复制了新的文字，永远可以通过 "0p 来粘贴。

事实上不经 yank 的内容在 "" 中，x, s,c{motion}, d{motion} 命令操作的内容都会在该寄存器中保存。

复制专用寄存器

正因为所有的 yank 内容都会自动被保存在 "0 寄存器中，所以数字寄存器 "0 也被称为 yank register.

只读寄存器

Vim 中有四个只读寄存器 "., "%, ":, "# .

最后插入文本 last inserted text “.

最后插入的文字被保存在 ". 中，如果想要在其他地方使用刚刚输入的文字，非常方便。

当前文件名 name of the current file “%

"% 保存 Vim 最早开始打开时，当前文件的完整路径。最常用的组合就是将当前的路径放到粘贴板

:let @+=@%

let 命令用来向寄存器写入， "+是粘贴板寄存器，将 "% 内容写入粘贴板

最后执行的 Ex 命令 last Ex command “:

": 是最近执行命令寄存器。如果最近保存过文件 :w ，那么 Ex 命令 w 会保存在寄存器中。可以使用 @: 来执行前一次命令。再比如使用替换命令替换了一行中的内容 :s/foo/bar ，那么将光标移动到另一行再次使用 @: 就能够再次替换。

轮换文件名 name of the alternate file “#

"# 保存 alternative file 名字。大致可以理解为 Vim 中编辑的上一个文件，可以通过 :h alternate-file 来查看更多。当使用 Ctrl + ^ 来切换文件时，使用的就是这个寄存器保存的文件名。同样可以使用 :e Ctrl-r # 来做同样的事情。不常用。

表达式寄存器

"= 用来处理表达式结果，如果在 Insert Mode 使用 Ctrl+r+= ，然后输入 2+2<Enter> ，结果 4 会显示出来。也可以用来执行外部命令，比如 Ctrl - r = 之后输入 system('ls') <enter> 来显示 ls 的结果。

搜索寄存器

"/ 这个寄存器保存最近搜索过的内容，包括 /, ?, *, # 的内容。比如说最近搜索过 /example ，想要替换成 another， 可以使用

:%s/<Ctrl-r/>/another/g

输入 :%s/ 只有按下 Ctrl + r 再按 / 会自动插入寄存器保存的内容。

搜索寄存器也是可以写的，可以使用 let 命令写入：

:let @/="keywords"

寄存器和宏 Macro 的关系

或许很多不熟悉 Vim 寄存器的用户曾经使用过 Vim 的 Macro， Vim 可以使用 Macro 来录制一连串命令，然后重复。（可以使用 :h recording 来查看更多）。

Vim 使用寄存器来保存 Macro 的命令。比如使用 qw 来录制 Macro ，寄存器 "w 会被用来记录所有录制的内容，所有的内容都有文本的形式存放。

更加 Cool 的事情就是，因为所有的内容都以文本的形式存在寄存器中，我们可以轻易的修改其中的内容，而不至于因为一个疏忽录制错误，而重新录制整个操作。

比如忘记了给文字最后添加分号，可以

:let @W='i;'

来修改录制的内容，注意 W 是大写，这是追加到寄存器的意思，插入 i; 进入插入模式并输入 ; 。

再比如如果需要直接修改 register 的内容，可以使用

:let @w='<Ctrl-r w>

然后修改需要修改的内容，然后以 ' 结束。

另外一个 Cool 的事情就是，因为所有的命令都是以文本的形式保存的，所以可以轻易的将录制的 macro 移动到另外的寄存器中，或者将录制的 macro 分享给其他人。

比如将录制在 w 寄存器中的内容复制给粘贴板寄存器，然后就能在其他 Vim 中使用。

黑洞寄存器

黑洞寄存器 "_ 放入该寄存器的内容都会被吞噬掉，不会有任何返回。所以不想污染 yank register 的时候可以手动的将内容导入到该寄存器中，比如数字 0 寄存器已经有了想要粘贴的内容，这时想要删除一些内容，粘贴数字 0 寄存器中的内容，那么就可以：

"_diw

删除该单词，并将内容放到 black hole register 中，再使用

P

来粘贴即可。

系统粘贴板

系统粘贴板寄存器 "+ 当 Vim 要和外部程序或者系统交互时用那些 Vim 自身的寄存器就不管用了，Vim 的 plus register 指向的是系统粘贴板，用 "+ 来表示。

如果想要在 Vim 中粘贴系统剪贴板内容，那么需要使用 "+p （或者在插入模式下 <C-r>+ ).

反之如果要 yank 或者 delete 内容到粘贴板需要使用 "+

在 X11 系统中还有一个粘贴板，被称为 primary, 所以 Vim 对应一类寄存器 "* ，一般被鼠标中间按键使用。

在 Windows 和 Mac OS X 中没有 primary clipboard 所以 "+ 和 "* 可以混用。

Vim 可以在编译时选择是否支持 X11 粘贴板，可以使用 :version 来查看 xterm_clipboard 查看是否支持。如果前缀是一个 - 减号，那么表示该版本的 Vim 不支持该特性。+ 加号表示支持特性。

将内容复制到指定寄存器

看到上面这么多寄存器，不免就要思考，不如想要把当前单词复制到指定的寄存器中该怎么办。其实非常简单，在命令前加上寄存器的名字，比如要将单词保存到寄存器 "a

• "ayiw

或者复制该行到寄存器 b

• "byy

如果要将寄存器内容粘贴到文本，可以

• "ap

除了上面普通模式的命令，Vim 也有删除、复制与粘贴的 Ex 命令，比如将当前行剪切到寄存器 c

• :delete c

将寄存器内容粘贴到当前光标所在行

• :put c

总结

Vim 中的寄存器一共分为 9 大类：

1. The unnamed register “”
2. 10 numbered registers “0 to “9
3. The small delete register “-
4. 26 named registers “a to “z or “A to “Z
5. four read-only registers “:, “., “% and “#
6. the expression register “=
7. The selection and drop registers “*, “+ and “~
8. The black hole register “_
9. Last search pattern register “/

其中大部分的寄存器上文都有涉及，其中为涉及到的 selection and drop registers 和 GUI 中选取的内容有关系。

black hole register 是一个黑洞寄存器，当写入 black hole register 时，nothing happens . 像黑洞一样吞掉所有的输入，可以用来在大量删除文本时不影响任何寄存器。

reference

• http://www.brianstorti.com/vim-registers/
• http://vimdoc.sourceforge.net/htmldoc/change.html#registers