设计题 - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>JobHunting - 待字闺中

设计题

设计题# JobHunting - 待字闺中

g*e2013-02-18 08:02

1 楼

设计一个billing system,每天从数据库里拉出一个用户列表，计算每个用户需要收的
钱，然后charge他们的信用卡。
要求
1. 每个用户每天最多被charge一次
2. No double charge
3. 照顾各种corner case
4. concurrency
简单吧

p*22013-02-18 08:02

2 楼

可以用scala来解吗？

g*e2013-02-18 08:02

3 楼

设计题，跟语言无关

【在 p*****2 的大作中提到】

: 可以用scala来解吗？

p*22013-02-18 08:02

4 楼

这话怎么说呢？设计题怎么会跟语言无关呢？

【在 g**e 的大作中提到】

: 设计题，跟语言无关

g*e2013-02-18 08:02

5 楼

重点是思路和框架，以及照顾到各种corner case。用什么语言并不重要。
比如说为了防止racing condition我要用个lock，你可以用数据库read/write lock，
java synchronized，也可以用AKKA。

【在 p*****2 的大作中提到】

:
: 这话怎么说呢？设计题怎么会跟语言无关呢？

p*22013-02-18 08:02

6 楼

为什么一定要concurrency？

【在 g**e 的大作中提到】

: 重点是思路和框架，以及照顾到各种corner case。用什么语言并不重要。
: 比如说为了防止racing condition我要用个lock，你可以用数据库read/write lock，
: java synchronized，也可以用AKKA。

f*72013-02-18 08:02

7 楼

两个表
一个processing，有isProcessed 标记和 timestamp
一个processed
processing 累计记录当天的各项charge，每天的一个时间段，往processed里写每个
人的总charge，一旦processing的一条记录被processed ，isProcessed set to 'Y',
同时更新time stamp，这样哪怕process 过程中段了，系统也会根据 isProcessed =
'N' and timestamp < current去继续写入

g*e2013-02-18 08:02

8 楼

单线程也行。follow up问题自然是当你的用户有几百万的时候怎么处理，你的单线程
跑了一半死了怎么处理

【在 p*****2 的大作中提到】

:
: 为什么一定要concurrency？

t*n2013-02-18 08:02

9 楼

最先想到的MapReduce. 可是如果按OO 设计的话细节可能比较多。
有几个问题：
1. 如果一个用户昨天买的东西,今天退了。那么可能需要处理向信用卡退钱的情况
2. 一个用户可能用了多张信用卡，如何只charge一个用户一次
几个基本想法，请大牛指教：
用户是一个class, 用观察者模式，设置一个Transaction manager, 当用户状态改时的
调用manager里面的update()方法，处理并行的话可以用synchronized或者加个处理队
列。

p*22013-02-18 08:02

10 楼

能不能多线程，每一个处理一部分用户，这样就不会有race condition了。

【在 g**e 的大作中提到】

: 单线程也行。follow up问题自然是当你的用户有几百万的时候怎么处理，你的单线程
: 跑了一半死了怎么处理

d*x2013-02-18 08:02

11 楼

这东西又不是统计个啥。。为啥要map reduce？

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

: 最先想到的MapReduce. 可是如果按OO 设计的话细节可能比较多。
: 有几个问题：
: 1. 如果一个用户昨天买的东西,今天退了。那么可能需要处理向信用卡退钱的情况
: 2. 一个用户可能用了多张信用卡，如何只charge一个用户一次
: 几个基本想法，请大牛指教：
: 用户是一个class, 用观察者模式，设置一个Transaction manager, 当用户状态改时的
: 调用manager里面的update()方法，处理并行的话可以用synchronized或者加个处理队
: 列。

g*e2013-02-18 08:02

12 楼

不错的想法。几个问题
1. 你是先set isProcessed,还是处理？如果先处理，收了钱set isProcessed失败怎么
办？
如果先set flag，set完了还没收钱程序死了咋办？
2. 如果万一你的程序卡在某个用户很久，系统重新运行，是不是这个用户又被收一次
钱，因为isProcessed='N'？
3. 怎么处理多线程?

',
=

【在 f*******7 的大作中提到】

: 两个表
: 一个processing，有isProcessed 标记和 timestamp
: 一个processed
: processing 累计记录当天的各项charge，每天的一个时间段，往processed里写每个
: 人的总charge，一旦processing的一条记录被processed ，isProcessed set to 'Y',
: 同时更新time stamp，这样哪怕process 过程中段了，系统也会根据 isProcessed =
: 'N' and timestamp < current去继续写入

f*72013-02-18 08:02

13 楼

看了一些回复，真的是不同的人想到的切入点是不同的
但是面试时不管想的多好，没有和面试官的想法达成一致，也白搭了吧。。。
但是怎么能达到面试官的expected answer呢？

t*n2013-02-18 08:02

14 楼

map reduce 的话可能在并行处理大量交易的时候比较有用。当然我这学期正在学这门
课可能理解不够。
感觉就是一个 map{user, transaction} reduce{user, sum{transaction}} 的过程
。仅仅是并行处理较快而已。

【在 d**********x 的大作中提到】

: 这东西又不是统计个啥。。为啥要map reduce？

g*e2013-02-18 08:02

15 楼

简单情况
1. 不存在退货
2. 一张卡
update()跑一半程序死了咋办, 到底是收到还是没收到钱？

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

f*72013-02-18 08:02

16 楼

g*e2013-02-18 08:02

17 楼

不管是单线程还是多线程，还是分布在不同的机器上跑，最终有两个问题要解决
1. 如果保证idempotence. 同一个transaction（每天收钱一次）只处理一次
2. 程序在任何情况下中断，stuck，机器down掉。回复运行以后继续正确处理
bottom line: 一个用户可以今天不扣钱(比如程序今天出了问题)，明天再把两天的帐
一起算。但是不能double charge，也不能一天收钱两次（即使是正确的）。

线程

【在 p*****2 的大作中提到】

:
: 能不能多线程，每一个处理一部分用户，这样就不会有race condition了。

p*22013-02-18 08:02

18 楼

我怎么记得actor不怕crash呢。晚上睡觉之前再看看。

【在 g**e 的大作中提到】

: 不管是单线程还是多线程，还是分布在不同的机器上跑，最终有两个问题要解决
: 1. 如果保证idempotence. 同一个transaction（每天收钱一次）只处理一次
: 2. 程序在任何情况下中断，stuck，机器down掉。回复运行以后继续正确处理
: bottom line: 一个用户可以今天不扣钱(比如程序今天出了问题)，明天再把两天的帐
: 一起算。但是不能double charge，也不能一天收钱两次（即使是正确的）。
:
: 线程

f*72013-02-18 08:02

19 楼

那可能就需要两个标记了 beginProcessing, endProcessing
有这么几个情况 Y N , 中断情况，重新启动系
统需要从这里开始
Y Y，成功情况，这是时insert to
processed table
多线程时，线程 only pick up beginProcessing = 'N' and endProcessing = 'N'

【在 g**e 的大作中提到】

: 不错的想法。几个问题
: 1. 你是先set isProcessed,还是处理？如果先处理，收了钱set isProcessed失败怎么
: 办？
: 如果先set flag，set完了还没收钱程序死了咋办？
: 2. 如果万一你的程序卡在某个用户很久，系统重新运行，是不是这个用户又被收一次
: 钱，因为isProcessed='N'？
: 3. 怎么处理多线程?
:
: ',
: =

g*e2013-02-18 08:02

20 楼

交流，从用户出发，了解用户需求，怎样是对用户最好的，怎样是最简单有效的。再往
上就是考虑availability, scalability
btw 这是一个非常实际的题目，很多project有类似需求，我并没有最佳答案，求大牛
解惑。

【在 f*******7 的大作中提到】

: 看了一些回复，真的是不同的人想到的切入点是不同的
: 但是面试时不管想的多好，没有和面试官的想法达成一致，也白搭了吧。。。
: 但是怎么能达到面试官的expected answer呢？

t*n2013-02-18 08:02

21 楼

象数据库一样使用Log记录所有操作和在log记录的时间的总营业额，当一个操作失败的
时候就根据记录从失败的地方开始。检查最后的总营业额来看收没收到钱？

【在 g**e 的大作中提到】

: 简单情况
: 1. 不存在退货
: 2. 一张卡
: update()跑一半程序死了咋办, 到底是收到还是没收到钱？

g*e2013-02-18 08:02

22 楼

Y/N 中断重新开始，这个transaction到底是处理了还是没处理呢，收到钱了吗
多线程的时候如何保证N/N的一个记录一定只被一个线程获取？用一台机器的时候可以
用semaphore, synchronized解决(虽然效率不高)，多台机器多线程的时候呢

to
怎么
一次

【在 f*******7 的大作中提到】

: 那可能就需要两个标记了 beginProcessing, endProcessing
: 有这么几个情况 Y N , 中断情况，重新启动系
: 统需要从这里开始
: Y Y，成功情况，这是时insert to
: processed table
: 多线程时，线程 only pick up beginProcessing = 'N' and endProcessing = 'N'

d*x2013-02-18 08:02

23 楼

我觉得是否收到钱这个问题，要从银行那边来查询。transaction如果没有完成，要去
找银行问问，然后该退款退款。

动系
insert
N'

【在 g**e 的大作中提到】

: Y/N 中断重新开始，这个transaction到底是处理了还是没处理呢，收到钱了吗
: 多线程的时候如何保证N/N的一个记录一定只被一个线程获取？用一台机器的时候可以
: 用semaphore, synchronized解决(虽然效率不高)，多台机器多线程的时候呢
:
: to
: 怎么
: 一次

w*x2013-02-18 08:02

24 楼

这种atomic机制肯定要依赖于数据库本身的存储过程，trigger一个存储过程，至少数
据库可以保证存储过程的原子性

【在 g**e 的大作中提到】

g*e2013-02-18 08:02

25 楼

good. 假设每个transaction我们都生成一个unique ID，收钱的时候把ID传给银行，交
易成功以后银行会返回一个他们的unique confirmation ID. 有这两个ID就保证收到了
钱。
现在如果只有我们自己的ID，没有conf ID，我们可以通过查询银行来得知是否收到了
钱。
下面的问题是，我们的这个unique ID如何生成？
1. 每笔交易每次计算的都生成一个不同的UUID
2. 每个用户每天的交易生成同样的unique ID
我个人倾向第二种方法，因为这样直接能够避免一部分的racing condition(一部分是
因为无法避免两个线程同时提交的情况)

可以
'
失败
被收

【在 d**********x 的大作中提到】

: 我觉得是否收到钱这个问题，要从银行那边来查询。transaction如果没有完成，要去
: 找银行问问，然后该退款退款。
:
: 动系
: insert
: N'

f*72013-02-18 08:02

26 楼

Y/N 的时候没有被处理，也没有收到钱，重新启动时重新处理这个点
一旦一个线程pick up一条记录了，立即set beginProcessing to 'Y'
但是如果两个或多个线程恰好恰好同一个timestamp去pick up，这种情况的概率存在吗
？

【在 g**e 的大作中提到】

g*e2013-02-18 08:02

27 楼

stroe proc确实能达到ACID，不过不好scale啊

【在 w****x 的大作中提到】

:
: 这种atomic机制肯定要依赖于数据库本身的存储过程，trigger一个存储过程，至少数
: 据库可以保证存储过程的原子性

g*e2013-02-18 08:02

28 楼

当你收到钱，准备set endProcessing的时候，线程挂了，这时候不就还是Y/N吗。怎么
会没收到钱呢。
两个线程同时pickup的几率可不小，嘿嘿

可以

【在 f*******7 的大作中提到】

: Y/N 的时候没有被处理，也没有收到钱，重新启动时重新处理这个点
: 一旦一个线程pick up一条记录了，立即set beginProcessing to 'Y'
: 但是如果两个或多个线程恰好恰好同一个timestamp去pick up，这种情况的概率存在吗
: ？

w*x2013-02-18 08:02

29 楼

多分几个数据库是不是可以，这个问题没那么容易啊。
实在不行只有设两个字段或两个数据库，如果出了问题只有互相对比判断到底收钱了没

【在 g**e 的大作中提到】

: stroe proc确实能达到ACID，不过不好scale啊

l*h2013-02-18 08:02

30 楼

Mark一下，等我有空来做

【在 g**e 的大作中提到】

: 设计一个billing system,每天从数据库里拉出一个用户列表，计算每个用户需要收的
: 钱，然后charge他们的信用卡。
: 要求
: 1. 每个用户每天最多被charge一次
: 2. No double charge
: 3. 照顾各种corner case
: 4. concurrency
: 简单吧

c*t2013-02-18 08:02

31 楼

1. 每个用户每天最多被charge一次
unique transaction id from bank 是个好主意
2. No double charge
same as 1
3. 照顾各种corner case
after recovery, check all starting charge but not finished users, use unique
id to ask bank if charged or not, to determine charge again or done.
4. concurrency
我觉得可以Syncronized with user as resource. But develop a method that any
new thread can pick the next not-started-yet user to process can reduce
waiting time.

【在 g**e 的大作中提到】

s*02013-02-18 08:02

32 楼

大牛试着用akka来解一下？

【在 p*****2 的大作中提到】

: 可以用scala来解吗？

s*02013-02-18 08:02

33 楼

并且，mapreduce适合处理offline的东西。在这里如果mapreduce过程用的数据和最新
情况不一致，咋整？

【在 d**********x 的大作中提到】

: 这东西又不是统计个啥。。为啥要map reduce？