c*******a
发帖数: 1879 | 1 【 以下文字转载自 JobHunting 讨论区 】
发信人: centralla (central LA), 信区: JobHunting
标 题: 弯曲大火导致这个网站QPS跟不上了
发信站: BBS 未名空间站 (Thu Oct 12 12:21:28 2017, 美东)
码农就知道刷题，
解决实际问题的能力如0 ，设计问题也根本不行
https ： //airnow . gov/ |
|
a**d
发帖数: 85 | 2 之前面的一个题，现在又重新看了一下。之前有大神说用network的leaky bucket.试着
写了一个简单的，这样合理吗？
interface RateLimit {
/** Sets the rate, from 1 to 1000000 queries per second */
void setQPS(int qps);
/** accept or reject a request, called when request is received */
boolean allowThisRequest();
}
brief example:
server instantiates your object, calls setQPS(1)
at at time t, user1 makes a request, allowThisRequest() returns true
at time t+0.01 sec, user2 makes a request, allowThisRequest() returns false
at at time ... 阅读全帖 |
|
E***X
发帖数: 885 | 3 I am posting the jobs for one of the best recruiters I have worked with.
Please contact Kathleen directly as following:
Kathleen Mitchell
Executive Recruiter
f******************[email protected]
Contact : 201 468 0519
High Frequency Connectivity Developer
The Quantitative Prime Services team is part of the Equities Technology
organization at Barclays Capital.
This team is responsible for the development and maintenance of a low
latency trading platform that
caters to clients engaged in high-frequency ... 阅读全帖 |
|
k******a
发帖数: 44 | 4 这个要求是一个大量读，很少写的案例。
对于并发这么高的要求，10000 qps + 10ms latency， 那么一定得上partition/shard。
我觉得按照dynamo的思路，用consistent hashing做key的partition, 每个node用
Redis + Mysql Engine.
然后可以开始扯consistent hashing, gossip, redis, innodb.
对于key, 根据consistent hashing选择对应node, 再node内，查redis或mysql engine
。redis本身很快，10K qps也可以，但是如果不在redis，mysql engine不会很快。假
定每个shard支持1K qps， 那么需要10个shard. 每个shard有3个node, 每个node支持
333 qps。利用virtual node, 分布30个node到10台服务器。
利用gossip广播membership状态和key space分布。 |
|
E***X
发帖数: 885 | 5 I am posting the jobs for one of the best recruiters I have worked with.
Please contact Kathleen directly as following:
Kathleen Mitchell
Executive Recruiter
f******************[email protected]
Contact : 201 468 0519
High Frequency Connectivity Developer
The Quantitative Prime Services team is part of the Equities Technology
organization at Barclays Capital.
This team is responsible for the development and maintenance of a low
latency trading platform that
caters to clients engaged in high-frequency ... 阅读全帖 |
|
发帖数: 1 | 6 鍛靛懙 鐙楃殑qps鍜岄噾铻峲ps 鐢靛晢qps浜嬩竴鏍风殑鍚條ol
銆鍦chefscut(jerk) 鐨勫ぇ浣滀腑鎻愬埌: 銆br />
: 杩欓兘鏄簲鐢ㄩ鐨勩
澶у璋佷篃涓嶏拷9锟璋佺銆傜嫍瀛愮殑QPS锛屽摢瀹朵腑鍥藉叕鍙镐篃鎼炰笉
瀹氥
: 浣嗘槸濡傛灉鍝涓浗鍏徃鏈夌嫍瀛愮殑娴侀噺鐓ф牱鎼炲緱濂姐
|
|
N*D
发帖数: 3641 | 7 放内存还是放硬盘，交给storage layer决定，不是你app layer考虑的问题。
最后还是一句话：需求不明，没发设计。
数据量多大？1GB？1TB？1PB？
访问量多大？读多少？写多少？1 qps，还是100qps，还是100k qps，还是10m qps
Latency要求？1ms？10ms？100ms？1s？
然后use case：需要给短的读长的？需要给长的读短的？
然后各种细节：一个长的缩成固定的短的？同一个用户short一个长的consistently产
生一个短的？不同用户short一个长的产生几个短的？
等把问题弄清楚，面试就差不多结束了。 |
|
h******e
发帖数: 52 | 8 你这个算法有点问题吧？
1M - DAU，每人每天3次请求, 峰值按10倍， 应该是30M requests / (24*3600) = 347
qps in total, 34 write qps, 313 read qps
数巨量： 10% * 3M * (200bytes for long + short URL) / day => 60M / day
和你算的有出入呀？ |
|
s****r
发帖数: 68 | 9 复杂性在于super high qps，人可接受的response time，和transaction。当然如果不
进入购物车，显示的一个商家的信息可能略微stale。
就不要纠结磁盘了。你去看看提供人可接受的响应时间的系统，serving side critial
path的数据有几家还用磁盘的。最多SSD。去看看google，fb，amazon。现在所谓的
database已经不是传统的database了。
QPS and response time就是复杂性，reliable（不crash）就是做得不错。
看的
了。 |
|
b*******d
发帖数: 750 | 10 给出了incoming entry的distribution的曲线，qps是几千这样子。这个system有三个
api：
1）getTopTenMillionInPast24Hour()
2) isInTopTenMilionInPast24Hour()
3) notifyWhenJoinOrRemovedFromTopTenMillionInPast24Hour()
自己来architect系统，定义service能提供数据的精度。
我当时给的是个多台机器的架构。我觉得是旧data每秒钟都在产生（任何当前时间进行
的api call，准确来说，1小时零1秒前的数据都是旧的，对算
top10millioninPast24Hour没有意义），但几乎没有任何系统在一秒钟内可以purge掉
这么多的旧数据，所以就要定义一个精度。比如，semantics是“我能保证给结果是精
确的，但是有个最多20分钟的delay”，或者“我不能保证结果是100%精确的，但是我
能最新的query能够实时的反应在结果中，并且返回的结果和真值有90%的重合”。
其实就是说consistency，availabi... 阅读全帖 |
|
b*****n
发帖数: 618 | 11 6.首先讨论qps多高，load多高，讨论结果是其实系统要求根本没那么高。。因为每首
歌假设4分钟，不吃不喝每天每个人最多也就听360首歌，一个周也就2520首，这个计算
放memory里面也基本上完全无压力。qps更是很低，根本不用做太复杂的design。。
其实还是kv store，HBase刚好比较适合记录user的一系列的action，因为每个cell有
timestamp做key。
想要速度快的话，可以加各层cache，用来buffer写操作和加快读操作。
最后讨论的点转移到其他东西上去了，比如这个东西用Java写会有什么问题，我答GC，
然后开始讨论各种GC，然后又扯到HBase如何failover，如何保证data consistency
7.貌似前面说过了。。 |
|
T*******e
发帖数: 4928 | 12 I don't remember how to count qps that low. Are you sure about 10 qps?
In one city or region or total? |
|
s**x
发帖数: 7506 | 13
16万个司机同时在线，一分钟update 一下位置，就是差不多3000 QPS。
用户更多。当然Qps跟GF不是一个量级的。U这种公司，技术不是难点，难点是流程管理
，包括司机注册，费用管理，用户管理等等。这些流程需要经常改动。 |
|
s**x
发帖数: 7506 | 14 昨晚又想到一个trick, 直接秒杀 这种high concurrency but tiny data set 系统。
就是合理的分流加aggregation.
分流可以按车次，前台 10000 web server, 后台 10000台server 自带任何一种数据库
就好了，一台server 负责几个车次。
Each web server aggregate all the requests to the same 车次 in one second,
后台能处理 10000 QPS 就行了。
貌似连多级cache，mem only db 之类的都是杀鸡用牛刀。
联票web server 并行锁票。
支付额外sever 异步处理。
Fault tolerance 多种方案。
Simple, easy and fast, 系统QPS 100m.
估计三个普通码工三个月轻松写完。 |
|
p**r
发帖数: 5853 | 15 你要明白一个事情，这世界上90%的企业都不需要高大上。
内部app的qps<50，public的site基本也是qps<100
这种项目用微软开发很方便，
基本一天做一个项目还有半天可以灌水。 |
|
m***i
发帖数: 2480 | 16 可能网站有qps throttling.你要降qps.或者从google web cache抓
response |
|
k*******r
发帖数: 90 | 17 因为这个版上二把刀太多
也不能怪他们
计算机这门科学好多半道出家的以为学点皮毛就以为可以关公耍大刀
殊不知很多时候能知其所以然都做不到
的确，如果计算机的频率一直往上跑， 1M qps并不是什么大不了的问题
但是关键是现在频率没法加了，多核的情况下不是简单的堆机器就能搞定 1M qps
teacherwei还说什么一个核处理网络，一个核处理订票
一看就是完全不懂其中的利害的
一个系统调用就能超过1微秒，还一个核搞定 |
|
L*******k
发帖数: 42 | 18 题外话。你们这样一会儿go一会儿coroutine的搞高并发是不是在钻牛角尖走火入魔？
就算是你
们看不上的java+thread，拿台c3.2xlarge也随便处理几个K的qps啊。问题是你能有几
个K的qps？几十个K？又换句话说你都几十个K的在线业务量级了，公司起码也是若干B
的市值了吧，你拿go折腾来折腾去一年能省多少几块钱下来。
说白了就是钻技术不要太深，还是要最终outcome/impact为主导。
话说我们公司前几年就有个部门的一帮人装逼用Go写rpc server，结果问题一大堆，
跟公司其他Java为主的后端工程开发格格不入，怨声载道。 |
|
c*******a
发帖数: 1879 | 19 【 以下文字转载自 JobHunting 讨论区 】
发信人: centralla (central LA), 信区: JobHunting
标 题: 国庆时候故宫，黄山之类的门票是怎么在网上销售的？
发信站: BBS 未名空间站 (Sun Oct 1 20:15:35 2017, 美东)
什么样的服务器可以满足这种QPS要求的？
如果让你设计， 你会考虑哪些因素？门票会面对全国各地的游客网上购买。
假设： 高峰期可能有几亿人在抢几十个剩余门票的可能。 |
|
|
|
发帖数: 1 | 22 这都是应用逼的。大家谁也不谁笨。狗子的QPS，哪家中国公司也搞不定。
但是如果哪家中国公司有狗子的流量照样搞得好。 |
|
发帖数: 1 | 23 你金融银行系统？
知道金融银行系统百万级qps什么意思么lol
一个写网站的还装起什么百万级的逼来lol
: 你是白痴吗 谁规定你连一个server的了
: [在 eschew (echo) 的大作中提到：]
: :Lol maoxian老将果然自证自己什么都不懂吹牛逼
: :知道c10k 么 看看什么时候解决的就觉得lol https://en.m.wikipedia.
org/
wiki/
: C10k_problem
: :还百万级lol
: : |
|
发帖数: 1 | 24 我做web portal 至少一百万人同时注册新用户。
你有啥意见
[在 eschew (echo) 的大作中提到：]
:你金融银行系统？
:知道金融银行系统百万级qps什么意思么lol
:<br>: 你是白痴吗 谁规定你连一个server的了
:<br>: [在 eschew (echo) 的大作中提到：]
:<br>: :Lol maoxian老将果然自证自己什么都不懂吹牛逼
:<br>: :知道c10k 么 看看什么时候解决的就觉得lol https://en.m.
wikipedia.org/
:wiki/
:<br>: C10k_problem
:<br>: :还百万级lol
:<br>: : |
|
发帖数: 1 | 25 牛逼啊100w人同时注册lolololol
假设你家公司一天只有三秒100w人同时注册 这样就有300w新增用户
每天新增用户怎么也有1000w吧
曹10天用户过亿
100天过10亿
现在哪个公司不请你真是她损失a
: 我做web portal 至少一百万人同时注册新用户。
: 你有啥意见
: [在 eschew (echo) 的大作中提到：]
: :你金融银行系统？
: :知道金融银行系统百万级qps什么意思么lol
: : |
|
发帖数: 1 | 26 大哥你吹牛逼放屁也打点草稿
你知道什么叫每秒处理10亿transaction么lololol
股沟qps你每天也才6-7亿
哪家银行有 或者用得到每秒1b transaction 的系统lol
吹牛打点草稿
: 这种transaction 有何技术含量？10亿/秒的量级10年前就作到了。
|
|
b********n
发帖数: 38600 | 27 【 以下文字转载自 USANews 讨论区 】
发信人: Sharon1 (), 信区: USANews
标 题: 华人的困境：刀把子，笔杆子，钱袋子
发信站: BBS 未名空间站 (Wed Feb 14 20:28:30 2018, 美东)
华人的困境：刀把子，笔杆子，钱袋子
Original 2018-02-15 雷尼尔 西雅图雷尼尔
历史背影中的华人
我很久之前写过一篇文章《历史背影中的美国华人》，主要讲述的是西雅图地区华人的
命运。
西雅图地区和加州地区一样都是华人非常早就参与开发的领地，当时华盛顿州还不是美
国的州，还只是美国的领地。华人为太平洋铁路的铺设和华盛顿州的开发，立下了汗马
功劳。值得指出的是早期的美国社会对华人还是非常欢迎，只干活，不吭声，任劳任怨。
1886年华州州长向美国内政部所做关于排华运动的报告节选
在报告中，州长也承认了华人在修建铁路方面所起到的作用。但是报告中也说到了，这
个只是在当时的情况，无法找到其他劳力所替代。
报告中也提到了华人这个群体的特征，其中最重要的一点是：“他们从来不把他们自己
认为是这个国家的永久居民。”
在大部分铁路修建完毕之后，... 阅读全帖 |
|
s****r
发帖数: 68 | 28 你以为是数cycle呢。这是transaction吧。技术上当然是世界领先啊。我以前就说过，
中国的网络软件处理的QPS比很多美国应用大不少，有需求软件技术自然就上去了。
可怜几个对软硬件基本不懂的政屁在那里硬扭。 |
|
s*****l
发帖数: 7106 | 29 廊庑
google的平均qps是多少你有数么
bat用的infra多少是来自美国的开源解决方案
你有数么
bat双11的时候多少人睡在warroom随时人工分流你知道么
bat技术水平最好的说就是接近flag
别说二线公司
巴马的垃圾网站是tmd关系户回扣
跟iowa caucus一样都是垃圾猪党丢人现眼
但土鳖现在敢质疑美帝的高科技了？
笑话 |
|
发帖数: 1 | 30 华人的困境：刀把子，笔杆子，钱袋子
Original 2018-02-15 雷尼尔 西雅图雷尼尔
历史背影中的华人
我很久之前写过一篇文章《历史背影中的美国华人》，主要讲述的是西雅图地区华人的
命运。
西雅图地区和加州地区一样都是华人非常早就参与开发的领地，当时华盛顿州还不是美
国的州，还只是美国的领地。华人为太平洋铁路的铺设和华盛顿州的开发，立下了汗马
功劳。值得指出的是早期的美国社会对华人还是非常欢迎，只干活，不吭声，任劳任怨。
1886年华州州长向美国内政部所做关于排华运动的报告节选
在报告中，州长也承认了华人在修建铁路方面所起到的作用。但是报告中也说到了，这
个只是在当时的情况，无法找到其他劳力所替代。
报告中也提到了华人这个群体的特征，其中最重要的一点是：“他们从来不把他们自己
认为是这个国家的永久居民。”
在大部分铁路修建完毕之后，加上积怨已久的其他族裔移民与华裔移民间的矛盾。1886
年前后西雅图地区发生了大规模的排华行动，随后引发的整个美国的大规模的排华行动
，西雅图地区的华人一扫而空。
被遗忘的华人历史
即便如此，漏网之鱼的华人，犹如石头缝里的小草，顽强地生长。在华盛... 阅读全帖 |
|
|
|
b*******d
发帖数: 750 | 33 哥也被问到这道题了，略有不同，给出了incoming query的distribution的曲线，qps
是几千这样子。这个system有三个api：
1）getTopTenMillionInPastHour()
2) isInTopTenMilionInPastHour()
3) notifyWhenJoinOrRemovedFromTopTenMillionInPastHour()
自己来architect系统，定义service能提供数据的精度。
我当时给的是个多台机器的架构。我觉得是旧data每秒钟都在产生（任何当前时间进行
的api call，准确来说，1小时零1秒前的数据都是旧的，对算top10millioninPastHour
没有意义），但几乎没有任何系统在一秒钟内可以purge掉这么多的旧数据，所以就要
定义一个精度。比如，semantics是“我能保证给结果是精确的，但是有个最多20分钟
的delay”，或者“我不能保证结果是100%精确的，但是我能最新的query能够实时的反
应在结果中，并且返回的结果和真值有90%的重合”。
其实就是说consistency，a... 阅读全帖 |
|
t*****e
发帖数: 53 | 34 Can you explain more detail about your system? Particularly, how you can get
the 90% accuracy?
qps
top10millioninPastHour |
|
y*******g
发帖数: 6599 | 35 不是 就是平时minotor site, load balance qps, 各种ab testing什么 |
|
y*******g
发帖数: 6599 | 36 mobile的好处就是自己能动手啊 又不需要自己架个集群或者需要多少qps |
|
i*******e
发帖数: 29 | 37 公司名称adap.tv，位处湾区San Mateo,风景宜人，气候舒适。公司近几年发展非常迅
速，open position也非常多：
http://www.adap.tv/careers/openings
为本组做一下广告：
backend server side in c/c++, processes a sustained 70,000 QPS. With our
own framework.
frontend video application in Flash(actionscript)/JS/Mobile, loaded hundreds
of millions of times a day.
最后，fresh grads friendly： e-verify,支持opt extension。3个月内可以办h1b。
工作1年可以办绿卡。
可以直接在公司网站上申请。需要refer的话请把简历发到我的邮箱：angeloyu@gmail.
com。
谢谢！ |
|
l***b
发帖数: 125 | 38 发信站: BBS 未名空间站 (工作这么多年，似乎就2次稍微有点复杂些的算法。一是设计过一个ranking function
，为了提高效率，用DP。再有是在一个系统里，要控制用户访问量，需要滑动窗口记录
过去一天之内的QPS。 |
|
r****c
发帖数: 2585 | 39 恩 其实有些physical limit不能老靠db解决，如日你一个single shared counter，又
要写在数据库里，又要支持几万qps，就要另想法子了，在application level上解决。 |
|
a**d
发帖数: 85 | 40 肯定跪了。
interface RateLimit {
/** Sets the rate, from 1 to 1000000 queries per second */
void setQPS(int qps);
/** accept or reject a request, called when request is received */
boolean allowThisRequest();
}
brief example:
server instantiates your object, calls setQPS(1)
at at time t, user1 makes a request, allowThisRequest() returns true
at time t+0.01 sec, user2 makes a request, allowThisRequest() returns false
at at time t+1, user4 makes a request, allowThisRequest() returns tru... 阅读全帖 |
|
w*****t
发帖数: 485 | 41 1) RateLimit大体思路：
use window rolling, 用一个队列，保存request的请求时间
新来一个请求时，先根据当前时间(如 123.45)，减去1秒(122.45), 然后将队列头部所
有小于122.45的request出队，再判断队列长度是否还小于qps，是的话插入新的
request，并返回true，否则返回false。
2) encode/decode:
用一个任意的字符来分割list, 比如用'#'，如果原string中有该分隔符，就
double一个，
比如："abc,de#,hij" -> "abc#de###hij#"
"abc,d#f,hij" -> "abc#d##f#hij#"
decode时，若只有单独一个分隔符，直接分割，若有两个或以上的连续分隔符，去掉一
个保留一个，再继续处理后面的字符串。。。 |
|
g*****g
发帖数: 212 | 42 可以用queue（也可以循环数组实现），每个元素是当前时间戳
每次request，从队头remove超时的
比较size， 如果超过qps return false
否则，入队，return true |
|
f******h
发帖数: 45 | 43 也找工作了一段时间了，从版上学了很多，上周G家面完了，求个bless。
之前的一些都挂了，还在继续找其他的。等定下来之后一定发面经回报本版。
谢谢大家啦！！
1. http://www.mitbbs.com/article_t/JobHunting/32005597.html
1) Implement a simple calculator (+,-,*,/);
2) Implement "+1" for a large integer;
3) How to match Ads to users;
4) How to extract useful information from a forum webpage (list all
kinds of useful signal you can think of)
5) How to detect the duplicate HTML pages (large scale);
6) Find all the paths between two places on Google map;
7)... 阅读全帖 |
|
i**d
发帖数: 357 | 44 我删文是觉得和你argue这个问题很没有意义。
fanout或者不fanout和你有什么db没有本质关系。你doc-based和无非就是节约写的
cost而牺牲读。你写不用fanout，你读需要fanout了。这个和你的读写qps的pattern有
关。还是那句话，规模大了以后都会出现问题。至于会出现什么问题，我觉得你可以去
看看twitter VP的一个关于fanout的talk。这种问题其实不是一句话两句话可以说清楚
的。一直争论下去只是耽误你我的时间，不如花点时间来好好学习一下这些公司的架构
，来充实自己。 |
|
s*w
发帖数: 729 | 45 显然是错了，没有把过期的count给减掉
比如 qps rate 是２ per second, 你的query 发生在 0.1, 0.9, 1.2 秒, 都应该接
受；你的程序会 reject 第三个， 以为 count=2 |
|
b*****n
发帖数: 618 | 46 前段时间骑驴找马终于告一段落，感觉本版的技术贴和面经贴帮助非常之大，也非常感
谢共享资源的各路大牛。希望提供一些信息和个人感受给还在找工的童鞋，有帮助最好
，但是毕竟本人资历尚浅，如果有不对的地方也请轻喷。
背景：
ms毕业不到两年
主要申请公司：
offer：facebook，google，uber，palantir，sumo logic，walmartlab，yahoo，
amazon，apple
reject：dropbox
主要几个包裹：
U： 145k base + 25k股 RSU
F： 150k base + 40k signon + 10%bonus + 260k美元 RSU
W： 165k base + 50k signon + 20%bonus + 35k美元 RSU每年（
这个略复杂，相当于每年35k美元RSU的refresh，但是每次refresh分四年给）
再上各个公司的面经和感受：
Yahoo：
最早面的公司，面的是Flurry Team，Yah... 阅读全帖 |
|
f*******r
发帖数: 976 | 47 恭喜，都是好包袱！
关键字: 面经
发信站: BBS 未名空间站 (Sat Jun 13 17:27:31 2015, 美东)
前段时间骑驴找马终于告一段落，感觉本版的技术贴和面经贴帮助非常之大，也非常感
谢共享资源的各路大牛。希望提供一些信息和个人感受给还在找工的童鞋，有帮助最好
，但是毕竟本人资历尚浅，如果有不对的地方也请轻喷。
背景：
ms毕业不到两年
主要申请公司：
offer：facebook，google，uber，palantir，sumo logic，walmartlab，yahoo，
amazon，apple
reject：dropbox
主要几个包裹：
U： 145k base + 25k股 RSU
F： 150k base + 40k signon + 10%bonus + 260k美元 RSU
W： 165k base + 50k signon + 20%bonus + 35k美元 RSU每年（
这个略复杂，相当于每年35k美元RSU的refres... 阅读全帖 |
|
b*****n
发帖数: 618 | 48 个人认为这个是must，不是optional，我指的是每个number的数量级，不用具体多少精
确到小数点后面xx位。
面试中可能不会直接问你这些数字，但是这个是所有design的最根本的出发点。
比如你需要设计一个kv store能handle 1M qps, key，value都是长度大概是100byte的
blob，99percentile 1ms latency，假设只考虑single cluster。
没有上面那些number是根本无从下手来设计的，你怎么设计这个系统别人一看就知道你
有没有经验。 |
|
|
p****6
发帖数: 724 | 50
即使不是互联网公司你有server architecture就可以扯了，避免谈qps，你可以扯如何
放上云端。 |
|
