h*******e
发帖数: 1377 | |
l**********i
发帖数: 12 | 2 说个hash真不知道是什么意思
首先弄清楚
1. 要不要支持自定义的shorten url
2. 任何人都可以生成shorten url呢还是只有登录的用户才可以
3. 一样的full url要不要给一样的shorten url
然后最基本的
1. shorten url是什么形式，多长，为什么，encode id to base 62?
2. 如何维护shorten url -> full url的mapping，id => full url?
3. 如何生成id? 会不会有collision, 如何解决
再说几点吧
1. 如何防止生成的url被scan，比如我知道某id=abc是合法的，然后试id-1 和id+1 不
应该被猜中
2. 如果要求随机猜N个url都未命中的概率大于99.99%，如何做到
3. 如果有人随机猜url 对你的系统有什么影响，如果你是persistant storage+cache
的架构 会有什么问题
4. 如何distribute到多机器 service和storage 都谈谈
5. 如何要限制单个用户的rps，用什么策略，如何实现
欢迎补充 |
h*******e
发帖数: 1377 | 3 请问第一和 第二个附加问题防止被猜中有什么方法么，在hash 出来的id 后面 随机
pigback 一个 rand(10000)的数么。。可是这样又怎么能防止两次产生不同的数呢。。
。或者 可以pigback 一个数根据前面的hash 计算出来的一个 0 10000之间分布均匀的
数。是这样子么。
请问多个机器应该怎样呢。。是不是hash 时候 加lock呢。分布系统我不是特别熟悉的
。 |
l*****a
发帖数: 14598 | 4 这个题常见解法不是hash
直接把URL插入数据库，用DB中index生成tiny URL
【在 h*******e 的大作中提到】
: 请问第一和 第二个附加问题防止被猜中有什么方法么，在hash 出来的id 后面 随机
: pigback 一个 rand(10000)的数么。。可是这样又怎么能防止两次产生不同的数呢。。
: 。或者 可以pigback 一个数根据前面的hash 计算出来的一个 0 10000之间分布均匀的
: 数。是这样子么。
: 请问多个机器应该怎样呢。。是不是hash 时候 加lock呢。分布系统我不是特别熟悉的
: 。
|
h*******e
发帖数: 1377 | 5 db index方法可以解决冲突问题哦 而且还可以保证 这个全局index不断增长，这样就
加个读写lock防止并发访问就行了吧。。
【在 l*****a 的大作中提到】
: 这个题常见解法不是hash
: 直接把URL插入数据库，用DB中index生成tiny URL
|
y***n
发帖数: 1594 | 6 多个DB呢？
【在 l*****a 的大作中提到】
: 这个题常见解法不是hash
: 直接把URL插入数据库，用DB中index生成tiny URL
|
l*****a
发帖数: 14598 | 7 URL开头几位可以作为DB索引
或者弄2级URL
a.com/***/***
a.com/***/***
【在 y***n 的大作中提到】
: 多个DB呢？
|
k*****t
发帖数: 161 | 8 DB的index具体是什么意思？是序列号吗？比如当前的序列号是999，下一个序列号就是
1000？
【在 l*****a 的大作中提到】
: 这个题常见解法不是hash
: 直接把URL插入数据库，用DB中index生成tiny URL
|
l***u
发帖数: 26081 | 9 用DB index怎么判断一个原始长url是否已经在数据库中？
【在 l*****a 的大作中提到】
: 这个题常见解法不是hash
: 直接把URL插入数据库，用DB中index生成tiny URL
|
m******e
发帖数: 82 | 10 防止被scan，可以打乱字母表，同时将auto ID各个bit打乱 |
|
|
j**********3
发帖数: 3211 | 11 我完全搞不清楚这个怎么设计。。。看了那3个link还是没理解。。。
之前有个人写了个抛砖引玉的，没来得及看就删了。。 |
g***j
发帖数: 1275 | 12 那为啥就不能scan了 人家可以随机替换字幕啊
比如abcde 改成abdde之类的 总可以蒙对几个？
【在 m******e 的大作中提到】
: 防止被scan，可以打乱字母表，同时将auto ID各个bit打乱
|
l*****f
发帖数: 259 | |
a******0
发帖数: 67 | 14 请问，如果用Hash，有collision怎么办？
谢谢啊。 |
g*****g
发帖数: 34805 | 15 我老提供个思路吧。从尾部截取一个固定长度，比如最长1K，以md5做hash，以hash值
为key放入Cassandra DB，原始url为column name，column name是排序好的. 产生一个
UUID来作为tinyurl的索引。Quorum Read/Write
也就是说用hash粗比较，用原始url在相同hash里面做两分比较。这是个分布式数据库
，整个架构可以linear scaleout。
另外，既然是公开的服务，被猜到索引并不是问题，也不会是要求。 |
a******0
发帖数: 67 | 16 谢谢啊；再帮个忙，能推荐几个link或paper吗？我想再细细消化您上面所说的hash方
法。
非常感谢！
【在 g*****g 的大作中提到】
: 我老提供个思路吧。从尾部截取一个固定长度，比如最长1K，以md5做hash，以hash值
: 为key放入Cassandra DB，原始url为column name，column name是排序好的. 产生一个
: UUID来作为tinyurl的索引。Quorum Read/Write
: 也就是说用hash粗比较，用原始url在相同hash里面做两分比较。这是个分布式数据库
: ，整个架构可以linear scaleout。
: 另外，既然是公开的服务，被猜到索引并不是问题，也不会是要求。
|
h*******e
发帖数: 1377 | 17 db index方法 的函数 db record id 和 生成的字符串 有互逆函数。
【在 h*******e 的大作中提到】
: db index方法可以解决冲突问题哦 而且还可以保证 这个全局index不断增长，这样就
: 加个读写lock防止并发访问就行了吧。。
|
m**p
发帖数: 189 | 18 我觉得你说的靠谱，比那个什么数据库的强。
怎么解决scan的问题？
【在 l**********i 的大作中提到】
: 说个hash真不知道是什么意思
: 首先弄清楚
: 1. 要不要支持自定义的shorten url
: 2. 任何人都可以生成shorten url呢还是只有登录的用户才可以
: 3. 一样的full url要不要给一样的shorten url
: 然后最基本的
: 1. shorten url是什么形式，多长，为什么，encode id to base 62?
: 2. 如何维护shorten url -> full url的mapping，id => full url?
: 3. 如何生成id? 会不会有collision, 如何解决
: 再说几点吧
|
g*****g
发帖数: 34805 | 19 公开资源还要防止被 scan就是搞笑，真要安全，应该是所有 url产生的 shorten url
互相独立，加密码。也不用算什么 hash.
【在 m**p 的大作中提到】
: 我觉得你说的靠谱，比那个什么数据库的强。
: 怎么解决scan的问题？
|
h*******e
发帖数: 1377 | 20 hash冲突怎么办呢， 一个key hash值对应两个column name(url)了就
这里的索引UUID似乎没有用到的阿.
【在 g*****g 的大作中提到】
: 我老提供个思路吧。从尾部截取一个固定长度，比如最长1K，以md5做hash，以hash值
: 为key放入Cassandra DB，原始url为column name，column name是排序好的. 产生一个
: UUID来作为tinyurl的索引。Quorum Read/Write
: 也就是说用hash粗比较，用原始url在相同hash里面做两分比较。这是个分布式数据库
: ，整个架构可以linear scaleout。
: 另外，既然是公开的服务，被猜到索引并不是问题，也不会是要求。
|
|
|
g*****g
发帖数: 34805 | 21 如果你不懂得C*怎么存数据的，想象一下这相当于一个hash后面带了一整个bucket，自
然不会冲突。你把UUID值存在这里，再建个UUID->url的索引就行了。把UUID拿出来做
Shorten URL。
建立新URL查第一个表，访问shorten URL查第二个表。
一个HashMap是个人都懂，差别在于C*这样的数据库能提供分布式存取。
【在 h*******e 的大作中提到】
: hash冲突怎么办呢， 一个key hash值对应两个column name(url)了就
: 这里的索引UUID似乎没有用到的阿.
|
m**p
发帖数: 189 | 22 二楼的问题问的很好，很多时候不是问题难，而是后面的follow up 看水平。所以有很
多题觉得会了，真正遇到了follow up才知道理解的不对。
url
【在 g*****g 的大作中提到】
: 公开资源还要防止被 scan就是搞笑，真要安全，应该是所有 url产生的 shorten url
: 互相独立，加密码。也不用算什么 hash.
|
p****6
发帖数: 724 | 23
能不能再讲讲UUID到底怎么实现？ 给定一个tinyURL，当我还原成UUID的时候，如何
map回原始URL？
【在 g*****g 的大作中提到】
: 如果你不懂得C*怎么存数据的，想象一下这相当于一个hash后面带了一整个bucket，自
: 然不会冲突。你把UUID值存在这里，再建个UUID->url的索引就行了。把UUID拿出来做
: Shorten URL。
: 建立新URL查第一个表，访问shorten URL查第二个表。
: 一个HashMap是个人都懂，差别在于C*这样的数据库能提供分布式存取。
|
g*****g
发帖数: 34805 | 24 time based uuid有标准实现，可以狗。从 uuid到 url就是建一个索引就可以了。
【在 p****6 的大作中提到】
:
: 能不能再讲讲UUID到底怎么实现？ 给定一个tinyURL，当我还原成UUID的时候，如何
: map回原始URL？
|
s****n
发帖数: 220 | 25 第二个table是以UUID作为primary key的，所以直接查询就可以了吧。
【在 p****6 的大作中提到】
:
: 能不能再讲讲UUID到底怎么实现？ 给定一个tinyURL，当我还原成UUID的时候，如何
: map回原始URL？
|
e******0
发帖数: 291 | 26 以前学生时候做SoC上面闪存卡读写也是这么个机制，一个硬件卡上先索引block，在
block里面再搜ID就好了。 上升到数据库，数据库内部其实也是这么实现的，先block
再定位具体ID。 再到分布式数据，貌似也就是之前软件层分成block变成了一个个物
理分割的database instance而已，只不过又往上再打包了一层？
【在 g*****g 的大作中提到】
: time based uuid有标准实现，可以狗。从 uuid到 url就是建一个索引就可以了。
|
