律所网站建设建议,门户网站系统设计,做程序题的国外网站,如何知道网站什么时候做的设计 Pastebin.com 设计 Bit.ly 是一个类似的问题#xff0c;区别是 pastebin 需要存储的是 paste 的内容#xff0c;而不是原始的未短化的 url. 怎么处理这个问题#xff1f;
第一步#xff1a;概述用例和约束 收集这个问题的需求和范畴。问相关问题来明确用例和约束区别是 pastebin 需要存储的是 paste 的内容而不是原始的未短化的 url. 怎么处理这个问题
第一步概述用例和约束 收集这个问题的需求和范畴。问相关问题来明确用例和约束讨论一些假设。 我们把问题的范畴定在如下用例
用户输入一段文本然后得到一个随机生成的链接
过期设置 默认的设置是不会过期的 可以选择设置一个过期的时间
用户输入一个 paste 的 url 后可以看到它存储的内容用户是匿名的Service 跟踪页面分析
一个月的访问统计
Service 删除过期的 pastesService 需要高可用
超出范畴的用例
用户可以注册一个账户
用户通过验证邮箱
用户可以用注册的账户登录
用户可以编辑文档
用户可以设置可见性用户可以设置短链接
约束和假设
状态假设
访问流量不是均匀分布的打开一个短链接应该是很快的pastes 只能是文本页面访问分析数据可以不用实时一千万的用户量每个月一千万的 paste 写入量每个月一亿的 paste 读取量读写比例在 10:1
计算使用 向面试官说明你是否应该粗略计算一下使用情况
每个 paste 的大小
每一个 paste 1 kbshortlink - 7 bytesexpiration_length_in_minutes - 4 bytescreated_at - 5 bytespaste_path - 255 bytes 总共 ~1.27 kb
每个月新的 paste 内容在12.7 GB
(1.27 * 10000000) kb / 月的 paste三年将近 450 GB 的新 paste 内容三年内 3.6 亿短链接假设大部分都是新的 paste, 而不是需要更新已存在的 paste
平均 4 paste/s 的写入速度平均 40 paste/s 的读取速度
简单的转换指南
2.5 百万 req/s
1 req/s 2.5 百万 req/m
40 req/s 1 亿 req/m
400 req/s 10 亿 req/m第二步创建一个高层次设计 概述一个包括所有重要的组件的高层次设计 第三步设计核心组件 深入每一个核心组件的细节 用例用户输入一段文本然后得到一个随机生成的链接
我们可以用一个 关系型数据库 作为一个大的哈希表用来把生成的 url 映射到一个包含 paste 文件的文件服务器和路径上。 为了避免托管一个文件服务器我们可以用一个拖管的对象存储比如 Amazon 的 S3 或者 NoSQL文档类型存储。 作为一个大的哈希表的关系型数据库的替代方案我们可以用 NoSQL键值存储。我们需要讨论选择 SQL 和 NoSQL 之间的权衡。
客户端发送一个创建 paste 的请求到作为一个反向代理启动的服务器Web 服务器转发请求给写接口服务器写接口服务器执行如下操作
生成一个唯一的 url
检查这个 url 在 SQL 数据库里面是否唯一如果这个 url 不是唯一的生成另外一个 url如果我们支持自定义 url,我们可以使用用户提供的 url
把生成的 url 存储到 SQL 数据库的 pastes 表中存储 paste 的内容数据到对象存储中返回生成的 url 向面试官阐明你需要写多少代码 paste 表可以有如下结构
shortlink char(7) NOT NULL
expiration_length_in_minutes int NOT NULL
created_at datetime NOT NULL
paste_path varchar(255) NOT NULL
PRIMARY KEY(shortlink)我们将在 shortlink 字段和 created_at 字段上创建一个数据库索引用来提高查询的速度避免因为扫描全表导致的长时间查询并将数据保存到内存中从内存里面顺序读取 1MB 的数据需要大概 250 微秒而从 SSD 上读取则需要花费 4 倍的时间从磁盘上则需要花费 80 倍的时间。
为了生成唯一的 url, 我们可以
使用 MD5 来哈希用户的 IP 地址 时间戳
MD5 是一个普遍用来生成一个 128 bit长度的hash值的一种hash办法MD5 是一致分布的或者我们也可以用MD5 哈希一个随机生成的数据
用 Base 62编码 MD5 哈希值
对于 urls使用 Base 62编码[a-zA-Z0-9]是比较合适的对于每一个原始输入只会有一个 hash 结果 Base62是不确定的Base 64 是另外一个流行的编码方案但是对于 urls会因为额外的 和 - 字符串而产生一些问题
def base_encode(num, base62):digits []while num 0remainder modulo(num, base)digits.push(remainder)num divide(num, base)digits digits.reverse取输出的前7个字符结果会有63*7个可能的值应该足以满足在3年内处理3.6亿个短视频的约束
url base_encode(md5(ip_addresstimestamp))[:URL_LENGTH]我们将会用一个公开的 REST 风格接口
curl -X POST --data {expiration_length_in_minutes:60,\paste_contents:Hello World} https://pastebin.com/api/v1/paste于内部通信我们可以用 RPC。
用例用户输入一个 paste 的 url 后可以看到它存储的内容
客户端 发送一个获取 paste 请求到 Web ServerWeb Server 转发请求给 读取接口 服务器读取接口 服务器执行如下操作 在 SQL 数据库 检查这个生成的 url 如果这个 url 在 SQL 数据库 里面则从 对象存储 获取这个 paste 的内容否则返回一个错误页面给用户
REST API
curl https://pastebin.com/api/v1/paste?shortlinkfoobarResponse:
{paste_contents: Hello World,created_at: YYYY-MM-DD HH:MM:SS,expiration_length_in_minutes: 60
}用例 服务跟踪分析页面
因为实时分析不是必须的所以我们可以简单的 MapReduce Web Server 的日志用来生成点击次数。
class HitCounts(MRJob):def extract_url(self, line):Extract the generated url from the log line....def extract_year_month(self, line):Return the year and month portions of the timestamp....def mapper(self, _, line):Parse each log line, extract and transform relevant lines.Emit key value pairs of the form:(2016-01, url0), 1(2016-01, url0), 1(2016-01, url1), 1url self.extract_url(line)period self.extract_year_month(line)yield (period, url), 1def reducer(self, key, values):Sum values for each key.(2016-01, url0), 2(2016-01, url1), 1yield key, sum(values)用例 服务删除过期的 pastes
为了删除过期的 pastes我们可以直接搜索 SQL 数据库 中所有的过期时间比当前时间更早的记录 所有过期的记录将从这张表里面删除或者将其标记为过期。
第四步扩展这个设计
