系统设计实践(01) - 短链服务 (2)

恶意用户可能会请求占用当前系统中所有URL键,从而让我们的业务失去新建短链的能力。为了防止滥用,我们可以通过api_dev_key来限制用户。每个api_dev_key可以被限制在一段时间特定数量的URL创建和重定向。

五. 数据库设计

在早期阶段定义DB模式将有助于理解不同组件之间的数据流,并在之后帮助我们处理数据分区。

关于我们将要存储数据的性质的一些观察

我们需要存储数十亿条记录

我们存储的每个对象都很小(小于1K)。

除了存储哪个用户创建了URL之外,记录之间没有任何关系。

我们的服务读请求量很大。

数据库模型

我们需要两个表。一个用于存储关于URL映射的信息,另一个用于创建短链接的用户数据。

URL User
[PK] Hash: varchar(16)   [PK] UserID: int  
OriginalURL: varchar(512)   Name: varchar(20)  
CreationDate: datetime   Email: varchar(20)  
ExpirationDate: datatime   CreationDate: datetime  
  LastLoginDate: datetime  
我们应该使用什么样的数据库?

因为我们预期存储数十亿行数据,而且我们不需要使用对象之间的关系,像DynamoDB这样的NoSQL键值存储,Cassandra或Riak是一个更好的选择。选择NoSQL也更容易扩展。请参阅SQL vs NoSQL了解更多细节

六. 基本系统设计与算法

我们在这里要解决的问题是,如何为给定的URL生成一个简短且唯一的主键。

在第一节为什么我们需要URL短链示例中,缩短的 URL 是。 这个 URL 的最后六个字符就是我们要生成的主键。

我们将在这里探索两种解决方案。

方案一. 编码URL

我们可以计算给定URL的唯一哈希值(例如,MD5或SHA256等)。然后可以对哈希进行编码以用于显示。

编码方式可以是base36 ([a-z,0-9])或base62 ([A-Z, a-z, 0-9]),如果加上-和.我们可以使用base64编码。问题是,短键的长度应该是多少?

使用 base64 编码,一个 6 字母长的密钥将产生 64^6 = ~687 亿个可能的字符串,一个 8 字母长的密钥将产生 64^8 = ~281 万亿个可能的字符串。

68.7B唯一的字符串对于我们的系统来说就足够了,所以我们可以使用6个字母的键。

如果我们使用 MD5 算法作为我们的哈希函数,它将产生一个 128 位的哈希值。 base64 编码后,我们将得到一个超过 21 个字符的字符串(因为每个 base64 字符编码 6 位哈希值)。 既然我们每个快捷键只有8个字符的空间,那么我们将如何选择我们的密钥呢? 我们可以取前 6 个(或 8 个)字母作为密钥。 不过,这可能会导致密钥重复,在此基础上我们可以从编码字符串中选择一些其他字符或交换一些字符。

该解决方案有哪些不同的问题?

我们的编码方案有以下几个问题

如果多个用户输入相同的URL,他们会得到相同的缩短URL,这是不可接受的。

如果 URL 的一部分是 URL 编码的怎么办? 例如,?id=design 和 %3Fid%3Ddesign

解决方法

我们可以向每个输入URL添加递增的序列号,使其惟一,然后生成它的散列。我们不需要把这个序列号存储在数据库中。这种方法可能存在的问题是不断增加的序列号它会溢出,附加递增的序列号也会影响服务的性能。

另一种解决方案是在输入URL中附加用户id(它应该是唯一的)。但是,如果用户还没有登录,我们就必须要求用户选择惟一密钥。即使在这之后如果我们有冲突,我们必须不断生成一个密钥,直到我们得到一个唯一的密钥。

方案二. 离线生成密钥

我们可以有一个独立的密钥生成服务(KGS),它事先生成随机的6个字母字符串,并将它们存储在一个数据库中(我们称之为Key-db)。当我们想要缩短一个URL时,我们只需要一个已经生成的键并使用它。这种方法将使事情变得非常简单和快速。我们不仅没有对URL进行编码,而且还不必担心重复或冲突。KGS将确保插入到key-DB中的所有键都是唯一的。

并发性问题

一旦密钥被使用,就应该在数据库中进行标记,以确保不会再次使用。如果有多个服务器并发地读取密钥,我们可能会遇到两个或更多服务器试图从数据库读取相同密钥的场景。我们如何解决这个并发问题?

内容版权声明:除非注明,否则皆为本站原创文章。

转载注明出处:https://www.heiqu.com/zzdgsf.html