10包子求一个AF 25%的code - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>Fashion - 美丽时尚

10包子求一个AF 25%的code

10包子求一个AF 25%的code# Fashion - 美丽时尚

t*u2012-02-12 08:02

1 楼

要create一个tinyUrl一般的做法都是生成一个数字的ID，然后把这个数字转换成[0-9]
[a-z][A-Z]的shortUrl
问题是如何生成这个数字ID呢？可以维持一个counter每次create tinyUrl就加1。但是
这样的话怎样distribute create到很多server上？
求大神指点

t*a2012-02-12 08:02

2 楼

Thanks!

z*82012-02-12 08:02

3 楼

timestamp + machine id + local counter + anything else appropriate

i*o2012-02-12 08:02

4 楼

还要吗?还要的话,我就站内信给你. 2/11 - 2/22 有效的.

t*u2012-02-12 08:02

5 楼

这样的话会是一个很长的id，怎样把它转成一个7-8个char的shortUrl呢？

【在 z*********8 的大作中提到】

: timestamp + machine id + local counter + anything else appropriate

d*y2012-02-12 08:02

6 楼

我也有，要的话,站内信联系哦！

w*12012-02-12 08:02

7 楼

7-8个char组合起来数值很大的，62 base，这样做问题不大

【在 t*******u 的大作中提到】

:
: 这样的话会是一个很长的id，怎样把它转成一个7-8个char的shortUrl呢？

z*82012-02-12 08:02

8 楼

事实上这是个很常见的follow up：对于1 billion requests, 以上每个segment大概
需要多少位数？合并之后什么数据类型可以hold？转化为62进制后需要几个字符？

【在 t*******u 的大作中提到】

:
: 这样的话会是一个很长的id，怎样把它转成一个7-8个char的shortUrl呢？

l*u2012-02-12 08:02

9 楼

为什么是62 base啊？大写26+小写26+数字10？
url一般都是case sensitive吧，比如这个网站上生成的tiny url，替换大小写也work
http://tinyurl.com/

t*u2012-02-12 08:02

10 楼

1 billion request大概是10K rps，可以分到50个partition上，每个200rps
所以可以用3个digit来表示partition id。
timestamp大概10个digit。
这样的话就13个digit了，可以用string来hold。但是还没加local counter。
62进制8字符大概14digit，这样就没有local counter的空间了。
为什么一定要加time stamp呢？不能直接就partition id + local counter吗？

【在 z*********8 的大作中提到】

: 事实上这是个很常见的follow up：对于1 billion requests, 以上每个segment大概
: 需要多少位数？合并之后什么数据类型可以hold？转化为62进制后需要几个字符？

z*82012-02-12 08:02

11 楼

timestamp， machine id， local counter都是数字，为什么要用string来hold呢？
不能直接就partition id + local counter的原因：因为机器或者local counter
process会crash，所以local counter会reset，从而返回同样的值

【在 t*******u 的大作中提到】

:
: 1 billion request大概是10K rps，可以分到50个partition上，每个200rps
: 所以可以用3个digit来表示partition id。
: timestamp大概10个digit。
: 这样的话就13个digit了，可以用string来hold。但是还没加local counter。
: 62进制8字符大概14digit，这样就没有local counter的空间了。
: 为什么一定要加time stamp呢？不能直接就partition id + local counter吗？

z*82012-02-12 08:02

12 楼

是case sensitive的，所以大小写就有52种可能，这是w3定义的： https://www.w3.
org/TR/WD-html40-970708/htmlweb.html

work

【在 l****u 的大作中提到】

: 为什么是62 base啊？大写26+小写26+数字10？
: url一般都是case sensitive吧，比如这个网站上生成的tiny url，替换大小写也work
: http://tinyurl.com/

t*u2012-02-12 08:02

13 楼

明白了
那这样的话就用long来hold。10个digit的timestamp + 3个digit的partition id +
local counter4个digit，一共17个，需要10个char的shorturl。这样算对吗？

【在 z*********8 的大作中提到】

: timestamp， machine id， local counter都是数字，为什么要用string来hold呢？
: 不能直接就partition id + local counter的原因：因为机器或者local counter
: process会crash，所以local counter会reset，从而返回同样的值

m*e2012-02-12 08:02

14 楼

50年后的今天timestamp=1576800000，2进制31位即可表示
1. 如果tiny url只有6个字符，最多能表示56800235584种可能，2进制大概36位，用5
位表示partition id+local counter，貌似不充裕
2. 7个字符，2进制42位，除去timestamp还有11位，就是说每秒支持2046个url，差不多
3. 8个字符，2进制48位，除去timestamp还有17位，每秒支持131072，完全充足了

【在 t*******u 的大作中提到】

:
: 明白了
: 那这样的话就用long来hold。10个digit的timestamp + 3个digit的partition id +
: local counter4个digit，一共17个，需要10个char的shorturl。这样算对吗？

a*02012-02-12 08:02

15 楼

1 billion request和10k是什么关系?

【在 t*******u 的大作中提到】

:
: 明白了
: 那这样的话就用long来hold。10个digit的timestamp + 3个digit的partition id +
: local counter4个digit，一共17个，需要10个char的shorturl。这样算对吗？

y*g2012-02-12 08:02

16 楼

多个server的话在shorturl左边多加一位用来标定server
long-》short 用一个hash%62来决定这一位存在对应的server
short-》long 根据这一位找到对应的server做查询

9]

【在 t*******u 的大作中提到】

: 要create一个tinyUrl一般的做法都是生成一个数字的ID，然后把这个数字转换成[0-9]
: [a-z][A-Z]的shortUrl
: 问题是如何生成这个数字ID呢？可以维持一个counter每次create tinyUrl就加1。但是
: 这样的话怎样distribute create到很多server上？
: 求大神指点

s*12012-02-12 08:02

17 楼

多个server要用consistent hash
这两篇写的比较清楚
http://www.learn4master.com/interview-questions/system-design/system-design-interview-tinyurl-service
http://www.learn4master.com/interview-questions/system-design/system-design-interview-consistent-hash

j*32012-02-12 08:02

18 楼

现在不流行考这个了吧？

c*t2012-02-12 08:02

19 楼

换成String才是short url啊
对timestamp不太明白，加上了timestamp以后，还怎么用tiny url search original
url呢？

【在 z*********8 的大作中提到】