问题
假设我们有一张超大的订单表（N亿），里面有order_id、user_id等字段。
- 能通过order_id快速查找对应订单
- 能通过user_id快速查找该用户具有的订单列表
像上面这样的要求改怎样做呢？通过哈希订单ID取模？那如何满足通过用户ID快速查找订单列表呢？
什么是基因算法
理论：
He meant that taking number mod 2^n is equivalent to stripping off all but the n lowest-order (right-most) bits of number
即: 一个数取余2的n次方，那么余数就是这个数的二进制的最后n位数。所有我们可以位操作符把高位清零就可以得到余数.
用户user_id=666 （666的二进制表示为：0000 0010 1001 1010）的用户生成一个订单步骤：
-
使用user_id%16分库，决定这行数据要插入到哪个库中
-
分库基因是user_id的最后4个bit，即1010
-
在生成order_id时，先使用一种分布式ID生成算法生成前60bit（上图中浅灰色部分）
-
将分库基因加入到order_id的最后4个bit（上图中绿色部分）
-
拼装成最终的64bit订单order_id（上图中蓝色部分）
-
这般，保证了同一个用户发布的所有订单的order_id，都落在同一个库上，order_id的最后4个bit都相同，于是：
-
通过order_id%16能够定位到库
-
通过user_id%16也能定位到库
-
Python代码实现
import random
# 假设我们有16个库，每个库有16个表
num_databases = 16
num_tables = 16
# 假设我们有一些用户
user_ids = [random.randint(1, 10000) for _ in range(10)]
def generate_order_id(user_id):
# 使用分布式ID生成算法生成前60bit（这里我们简化为一个随机数）
distributed_id = random.randint(1, 2**60)
# 从 user_id 中提取基因
gene = user_id % 16
# 将基因加入到 order_id 的最后几个bit
order_id = (distributed_id << 4) | gene
return order_id
def get_database_and_table_from_user_id(user_id):
# 使用 user_id 的最后4位作为基因
gene = user_id % 16
# 使用基因决定数据库和表
database = gene % num_databases
table = gene % num_tables
return database, table
def get_database_and_table_from_order_id(order_id):
# 从 order_id 中提取基因
gene = order_id % 16
# 使用基因决定数据库和表
database = gene % num_databases
table = gene % num_tables
return database, table
if __name__ == '__main__':
for user_id in user_ids:
u_database, u_table = get_database_and_table_from_user_id(user_id)
# 生成订单ID
order_id = generate_order_id(user_id)
o_database, o_table = get_database_and_table_from_order_id(order_id)
print(f"user_id: {user_id}, order_id: {order_id} "
f"user database: {u_database}, user table: {u_table} "
f"order database: {o_database} order table: {o_table}")