l********e
发帖数: 103 | 1 面试时候
被问到 写个 多线程的hash table
hash table我用linked list解决collision 问题
加lock的时候 我说 要用read write lock
hash table insert 时候用write lock
get的时候用read lock
然后 面试官跟我说
get的时候 不用加任何lock
大不了 get的值是旧的
（我当时 没说话 心想 只要 让我过 你说什么都好）
不过 我不明白为什么get不用加任何lock
如果 一个现在正在更改 一个值 改着一半的时候
正好另一个线程过来读 这时候 岂不是 读出来的值 一般旧一半新
请问各位大侠 我哪里对多线程理解错了？
请指点
谢谢 |
g*********e
发帖数: 14401 | 2 Use copy on write, create new value object each time and atomically swap
with old one |
l*********r
发帖数: 105 | 3 哥们在哪家公司高就？这种设计每一秒钟都在生产corrupted data。
如果有2个以上的thread同时写一个object，比如20个，或者200个，你不用lock？
如果这个object是个计数器，那就真是彻底完蛋了。
Lock striping是最好的方法。
【在 g*********e 的大作中提到】
: Use copy on write, create new value object each time and atomically swap
: with old one
|
d****n
发帖数: 12461 | 4 其实面试官的理解可能有问题。
不过这个查一下数据库的isolation level就可以了。你相当于要read committed，这
要read lock。面试官只要read uncommitted。
【在 l********e 的大作中提到】
: 面试时候
: 被问到 写个 多线程的hash table
: hash table我用linked list解决collision 问题
: 加lock的时候 我说 要用read write lock
: hash table insert 时候用write lock
: get的时候用read lock
: 然后 面试官跟我说
: get的时候 不用加任何lock
: 大不了 get的值是旧的
: （我当时 没说话 心想 只要 让我过 你说什么都好）
|
l********e
发帖数: 103 | 5 那要是 创建一个新node加到linked list的尾部呢？
感觉 atomically swap 和read write lock 没什么区别啊
都是写的时候 不能读啊
再请问一下 如果有个thread正在读着一半
另一个thread 过来要写呢？
这个atomically swap 怎么保证不读错呢
【在 g*********e 的大作中提到】
: Use copy on write, create new value object each time and atomically swap
: with old one
|
l********e
发帖数: 103 | 6 这里没有数据库
就是 让我写个 用于多线程的hash table
【在 d****n 的大作中提到】
: 其实面试官的理解可能有问题。
: 不过这个查一下数据库的isolation level就可以了。你相当于要read committed，这
: 要read lock。面试官只要read uncommitted。
|
d****n
发帖数: 12461 | 7 但是你看一下isolation level会有帮助。
【在 l********e 的大作中提到】
: 这里没有数据库
: 就是 让我写个 用于多线程的hash table
|
l********e
发帖数: 103 | 8 你说的lock striping是在hash table 的每个slot加个read write lock吗？
我就是这样说的 然后
面试官 要求更好的performance
然后他就提到get不用任何lock...
【在 l*********r 的大作中提到】
: 哥们在哪家公司高就？这种设计每一秒钟都在生产corrupted data。
: 如果有2个以上的thread同时写一个object，比如20个，或者200个，你不用lock？
: 如果这个object是个计数器，那就真是彻底完蛋了。
: Lock striping是最好的方法。
|
l*********r
发帖数: 105 | 9 这个面试的哥们基本的概念都错了。很常见，因为这些面试的人自己也搞不清楚这里面
的东西。他自己出去面试未必能找到工作。
凡是同时读写同一个数据，必须要用locking(操作系统底层里是指monitor)来协调。这
是最基本的常识。 |
l********e
发帖数: 103 | 10 多谢 大侠指点
【在 l*********r 的大作中提到】
: 这个面试的哥们基本的概念都错了。很常见，因为这些面试的人自己也搞不清楚这里面
: 的东西。他自己出去面试未必能找到工作。
: 凡是同时读写同一个数据，必须要用locking(操作系统底层里是指monitor)来协调。这
: 是最基本的常识。
|
|
|
E*********8
发帖数: 99 | |
l********e
发帖数: 103 | 12 是啊。。。
很大的有名刷题公司。。。
我要是因为这个 lock的问题被拒 真是冤死我了。。。
【在 E*********8 的大作中提到】
: 能问下楼主面的什么公司吗？ 是刷题公司吗
|
P******r
发帖数: 1342 | 13 至少得说清楚需求吧。。。有些系统读到过时的数据问题不大，有些读到过时数据就完
蛋啊 |
l********e
发帖数: 103 | 14 就是实现一个thread safe的hash table...
提供像标准库函数一样的api
没别的了
【在 P******r 的大作中提到】
: 至少得说清楚需求吧。。。有些系统读到过时的数据问题不大，有些读到过时数据就完
: 蛋啊
|
w****h
发帖数: 15 | 15 面试的人可能bare in mind 某个特定的应用场景，read 不用lock。 |
g*********e
发帖数: 14401 | 16 What corrupt data? The reference swap is atomic.
You either see v1 or v2. You don't write to the same object.
Certainly if you want to do a counter this won't work.
【在 l*********r 的大作中提到】
: 哥们在哪家公司高就？这种设计每一秒钟都在生产corrupted data。
: 如果有2个以上的thread同时写一个object，比如20个，或者200个，你不用lock？
: 如果这个object是个计数器，那就真是彻底完蛋了。
: Lock striping是最好的方法。
|
g*********e
发帖数: 14401 | 17 1 reader thread reads the object o0
2 writer creates another object o1
3 writer makes that hash bucket point to o1 (atomic, no need lock)
4 reader is still reading o0
5 future reader reads o1
【在 l********e 的大作中提到】
: 那要是 创建一个新node加到linked list的尾部呢？
: 感觉 atomically swap 和read write lock 没什么区别啊
: 都是写的时候 不能读啊
: 再请问一下 如果有个thread正在读着一半
: 另一个thread 过来要写呢？
: 这个atomically swap 怎么保证不读错呢
|
o*******r
发帖数: 73 | |
m**********s
发帖数: 518 | 19 你还是不要再写code了
什么时候hash table是个single object了？
Key points to a list of nodes for the sake of possible hash collision
你能atomic的copy一个list？
【在 g*********e 的大作中提到】
: 1 reader thread reads the object o0
: 2 writer creates another object o1
: 3 writer makes that hash bucket point to o1 (atomic, no need lock)
: 4 reader is still reading o0
: 5 future reader reads o1
|
g*********e
发帖数: 14401 | 20 Of course you can atomically swap an element in a list, use your brain.
Another scenario is to use probing instead of chaining, in which case each
bucket has only single kv pair.
Btw concurrentmap mentioned above still use regional locks to some extent,
if it's java.
【在 m**********s 的大作中提到】
: 你还是不要再写code了
: 什么时候hash table是个single object了？
: Key points to a list of nodes for the sake of possible hash collision
: 你能atomic的copy一个list？
|
|
|
l*********r
发帖数: 105 | 21 哥们，hashtable每个bucket里面是一个linked list。multithreading的时候一大堆读
thread在里面，怎么可以变动underlying datastructure? 整个linkedlist锁住才能写
(写操作包括change value, delete/add/change nodes)， in practise至少要锁住一
个或者多个bucket。
【在 g*********e 的大作中提到】
: Of course you can atomically swap an element in a list, use your brain.
: Another scenario is to use probing instead of chaining, in which case each
: bucket has only single kv pair.
: Btw concurrentmap mentioned above still use regional locks to some extent,
: if it's java.
|
p******a
发帖数: 130 | 22 Bucket 里存指向linked list的指针，有thread在读的时候swap指针没什么问题，只要
保证读写这个指针是原子的。
[在 linuxhacker (linuxhacker) 的大作中提到：]
:哥们，hashtable每个bucket里面是一个linked list。multithreading的时候一大堆
读thread在里面，怎么可以变动underlying datastructure? 整个linkedlist锁住才能
写(写操作包括change value, delete/add/change nodes)， in practise至少要锁住一
:个或者多个bucket。 |
l*********r
发帖数: 105 | 23 前面那哥们的问题在于不知道concurrency的情况下read/write都要同步，要锁住整个
linkedlist才能写。
你的问题是不知道copy on write有多么expensive。假设一个bucket的linked list有
100个element, 每秒有1000个写操作，那么就是每秒10万次copy。类似数量级的的例如，
realtime streaming price for all the tickers in nasdaq+nyse+lse，或者100万辆
路上行驶的汽车每秒报告一次位置。
正确的方法是locking，而不是copy on write。copy on write仅仅适用于的rarely
writes, many reads的特殊情况。一旦traffic变了，这都有可能crash JVM。
面试的时候提到copy on write一定要提到expensive。如果你回答说copy on write非
常高速，然后带着神秘的微笑看着面试的那哥们，不管面试的那哥们有多么菜鸟，都会
低头看看你的简历，搞清楚你到底干了几年，心里盘算着怎么据掉你。
住一
【在 g*********e 的大作中提到】
: Of course you can atomically swap an element in a list, use your brain.
: Another scenario is to use probing instead of chaining, in which case each
: bucket has only single kv pair.
: Btw concurrentmap mentioned above still use regional locks to some extent,
: if it's java.
|
j***a
发帖数: 1100 | 24 要锁住整个linkedlist才写也可以，
你看某家的网站那么慢，估计就是这逼实现的。
如，
【在 l*********r 的大作中提到】
: 前面那哥们的问题在于不知道concurrency的情况下read/write都要同步，要锁住整个
: linkedlist才能写。
:
: 你的问题是不知道copy on write有多么expensive。假设一个bucket的linked list有
: 100个element, 每秒有1000个写操作，那么就是每秒10万次copy。类似数量级的的例如，
: realtime streaming price for all the tickers in nasdaq+nyse+lse，或者100万辆
: 路上行驶的汽车每秒报告一次位置。
: 正确的方法是locking，而不是copy on write。copy on write仅仅适用于的rarely
: writes, many reads的特殊情况。一旦traffic变了，这都有可能crash JVM。
: 面试的时候提到copy on write一定要提到expensive。如果你回答说copy on write非
|
G********f
发帖数: 17 | 25 别被误导，linuxhacker明显不懂底层的东西，glowinglake is right
【在 l********e 的大作中提到】
: 多谢 大侠指点
|
r*******g
发帖数: 1335 | 26 hash table read的话确实可以做到不用lock。
就好比A->B->C
你现在新加入一个D进来，那么先D->C，然后内存sig_atomic或者database atomic操作
让B的next指向D，只要这个操作不影响read，那read就无需lock了，重点是先放好data
然后再链接起来。 |
w***x
发帖数: 105 | 27 lock free有很多种实现，glowinglake说的类似kernel里用的rcu，不过面试与其说考
lockfree，还不如考考简单的multi-threading的常识问题，lockfree的水很深，有些
问题可以复杂到深不见底的程度，所以真遇到个明白人，这种面试官其实是自取其辱。 |
g*********e
发帖数: 14401 | 28 有些人面试就是开放性的，探探interviewee水有多深。一直到either interviewer问
不下去或者interviewee答不下去为止。也没啥到不了的，又不是考试背答案，只是一
个交流的过程。言之有理能自圆其说即可
【在 w***x 的大作中提到】
: lock free有很多种实现，glowinglake说的类似kernel里用的rcu，不过面试与其说考
: lockfree，还不如考考简单的multi-threading的常识问题，lockfree的水很深，有些
: 问题可以复杂到深不见底的程度，所以真遇到个明白人，这种面试官其实是自取其辱。
|
l********e
发帖数: 103 | 29 多谢各位指点
我面试的时候 面试官 说写是用mutex, read不用lock...
不过 大家讨论后 我觉得这肯定不对
看了好几处CAS的介绍 都是说要update的时候 先和原来的值比较 如果相同则update
不过 没有说会不会影响 只读的线程
我想确认一下 CAS , RCU这种atomic的命令都是 在all pre-existing read-side
critical sections complete后 锁住bus,然后才update的吧？
不然读的线程 就都读出乱码了
我的理解对吗？
谢谢 |
T*****g
发帖数: 1306 | 30 这俩不是一个层面的吧
CAS是CPU instruction不存在read side critical section吧，你之前拿到了旧的
pointer那就是可以reference旧的object，具体到硬件
实现上有不同的办法，但是语义是一样的
RCU会有一个quiescent period来确保所有的read side critical section都结束，在
user space的implementation里好像是靠拿到每个worker的mutex来实现
★ 发自iPhone App: ChineseWeb 16
【在 l********e 的大作中提到】
: 多谢各位指点
: 我面试的时候 面试官 说写是用mutex, read不用lock...
: 不过 大家讨论后 我觉得这肯定不对
: 看了好几处CAS的介绍 都是说要update的时候 先和原来的值比较 如果相同则update
: 不过 没有说会不会影响 只读的线程
: 我想确认一下 CAS , RCU这种atomic的命令都是 在all pre-existing read-side
: critical sections complete后 锁住bus,然后才update的吧？
: 不然读的线程 就都读出乱码了
: 我的理解对吗？
: 谢谢
|
|
|
T*****g
发帖数: 1306 | 31 +1
glowinglake是对的
这么简单的ht，thead safety实现的方式太多了，靠mutex是最基本的，lockfree肯定
也是可行的
★ 发自iPhone App: ChineseWeb 16
【在 G********f 的大作中提到】
: 别被误导，linuxhacker明显不懂底层的东西，glowinglake is right
|
l********e
发帖数: 103 | 32 CPU instruction?
更糊涂了。。。
我说的是这个， https://en.wikipedia.org/wiki/Compare-and-swap
compare-and-swap (CAS) is an atomic instruction used in multithreading to
achieve synchronization.
不是CPU 指令吧...
【在 T*****g 的大作中提到】
: 这俩不是一个层面的吧
: CAS是CPU instruction不存在read side critical section吧，你之前拿到了旧的
: pointer那就是可以reference旧的object，具体到硬件
: 实现上有不同的办法，但是语义是一样的
: RCU会有一个quiescent period来确保所有的read side critical section都结束，在
: user space的implementation里好像是靠拿到每个worker的mutex来实现
:
: ★ 发自iPhone App: ChineseWeb 16
|
p******a
发帖数: 130 | 33 推荐你看看 c++ concurrency in action, 看完就不糊涂了。
[在 ladyAthene (ladyAthene) 的大作中提到：]
:CPU instruction?
:更糊涂了。。。
:我说的是这个， https://en.wikipedia.org/wiki/Compare-and-swap
:compare-and-swap (CAS) is an atomic instruction used in multithreading to
:achieve synchronization.
:不是CPU 指令吧... |
T*****g
发帖数: 1306 | 34 这个问题...怎么说呢...synchronization primitive是一层一层往上build的。。。
最底层的就是一些CPU atomic instruction，atomic load / store, CAS, TAS, 基于
这些CPU instruction可以build出各种锁（spin mutex, rwlock, MCS lock）,还有RCU
（本质是用atomic operation来做atomic publish）以及其他的一些primitive
楼下有人建议你看看那本书，我没读过，不过感觉应该对你理解这些有帮助
【在 l********e 的大作中提到】
: CPU instruction?
: 更糊涂了。。。
: 我说的是这个， https://en.wikipedia.org/wiki/Compare-and-swap
: compare-and-swap (CAS) is an atomic instruction used in multithreading to
: achieve synchronization.
: 不是CPU 指令吧...
|
T*****g
发帖数: 1306 | 35 哥们你做过synchronization相关的工作么？你知道你一个bucket有100个element，多
线程同时写在mutex上要等多久么？不过你提的这个throughput可能用mutex也能达到，
只能说你是没见过高性能的salable hashtable
不要误导人了，谁告诉你要copy一整条bucket来做copy on write？（有人提到RCU了，
RCU就可以做）。RCU的难点只在于resize的时候不好处理，不过已经有人把这个问题解
决了。
如，
【在 l*********r 的大作中提到】
: 前面那哥们的问题在于不知道concurrency的情况下read/write都要同步，要锁住整个
: linkedlist才能写。
:
: 你的问题是不知道copy on write有多么expensive。假设一个bucket的linked list有
: 100个element, 每秒有1000个写操作，那么就是每秒10万次copy。类似数量级的的例如，
: realtime streaming price for all the tickers in nasdaq+nyse+lse，或者100万辆
: 路上行驶的汽车每秒报告一次位置。
: 正确的方法是locking，而不是copy on write。copy on write仅仅适用于的rarely
: writes, many reads的特殊情况。一旦traffic变了，这都有可能crash JVM。
: 面试的时候提到copy on write一定要提到expensive。如果你回答说copy on write非
|
T*****g
发帖数: 1306 | 36 为什么不能？
我拿到了list里一个node的reference，只要这个node不被free我的access就不会有
segfault，同时我读到的数据是point-in-time consistent的（是在我拿到reference
的时候的snapshot）
change value可以copy-on-write, add / change node我用atomic pointer可以很容易
实现，然后等所有拿到这个node 的reference的reader都退出的时候就可以free掉了。
free这部分要避免segfault可以用最简单的ref count pointer来实现，当然RCU更好，
因为更scalable。
【在 l*********r 的大作中提到】
: 哥们，hashtable每个bucket里面是一个linked list。multithreading的时候一大堆读
: thread在里面，怎么可以变动underlying datastructure? 整个linkedlist锁住才能写
: (写操作包括change value, delete/add/change nodes)， in practise至少要锁住一
: 个或者多个bucket。
|
l********e
发帖数: 103 | |
j**********r
发帖数: 3798 | 38 你应该问清楚应用场景，不同场景的解决方案不同。
从Collections.synchorizeMap, ConcurrentMap到Guava，distributed cache, DB,
Zookeeper. 有各种不同的解法。 |
l********e
发帖数: 103 | 39 就是实现一个类似于标准library里的thread safe hash table,
也是单机上的
没别的了。。。
【在 j**********r 的大作中提到】
: 你应该问清楚应用场景，不同场景的解决方案不同。
: 从Collections.synchorizeMap, ConcurrentMap到Guava，distributed cache, DB,
: Zookeeper. 有各种不同的解法。
|
j**********r
发帖数: 3798 | 40 那这个就可以了，反正没有性能要求。
Collections.synchorizedMap. 要从头实现一遍也很简单，直接找JDK源码。
http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/6-b14/java/util/Collections.java#Collections.SynchronizedMap
【在 l********e 的大作中提到】
: 就是实现一个类似于标准library里的thread safe hash table,
: 也是单机上的
: 没别的了。。。
|
|
|
l********e
发帖数: 103 | |
l*********r
发帖数: 105 | 42 这就是一个单机版的题目，凡是提到数据库的都会被fail掉。
我给你几个面试的哥们会追问的常规hash table问题吧：
1. 如果有大量的写入新value，如何保证concurrency和efficiency
2. 如果有大量的写入新key
3. 如果有大量的写new key/删除new key
4. 如果有大量的读和少量的写
千万不要提copy-on-write。必废。
看看concurrenthashmap，这是提问的人想要你回答的方向。不要看Collections.
synchronousXXX，必废，几乎没有人敢在production用这个。 |
l********e
发帖数: 103 | 43 这个面经宝贵～
我会去看 相关内容
不过 能说说 一般这些问题 怎么回答能过呢？
我觉得如果要用 锁 希望效率高 就要在每个slot上都有一个独立的锁
1. 如果有大量的写入新value，如何保证concurrency和efficiency 除了用每个
slot用独立一个锁 增大array size, 不要产生长linked list, 还能什么别的方法来效
率高呢？
2. 如果有大量的写入新key ：用很大的array, 减少冲突，减少expand的情况？
3. 如果有大量的写new key/删除new key 同上（感觉和上一个区别不大。。。）
4. 如果有大量的读和少量的写 ：用读写锁？
好像答的都差不多呢。。。
【在 l*********r 的大作中提到】
: 这就是一个单机版的题目，凡是提到数据库的都会被fail掉。
: 我给你几个面试的哥们会追问的常规hash table问题吧：
: 1. 如果有大量的写入新value，如何保证concurrency和efficiency
: 2. 如果有大量的写入新key
: 3. 如果有大量的写new key/删除new key
: 4. 如果有大量的读和少量的写
: 千万不要提copy-on-write。必废。
: 看看concurrenthashmap，这是提问的人想要你回答的方向。不要看Collections.
: synchronousXXX，必废，几乎没有人敢在production用这个。
|
l*********r
发帖数: 105 | 44 我一直强调的是绝对不可以在hashtable的设计(尤其在面试的时候)用copy-on-write，
一定要用lock。
第一点：最基本的常识，只能有一个thread来写，比如hashtable的值用作counter。用
copy-on-write，立马废掉。
第二点: 更进一步的synchronization，是要保证global ordering。比如狗家股票real
time streaming, 绝对不可以11:11:11.002的报价先写入，然后11:11:11.000的报价
后写入。这就有不少的实现方法。这个已经超出了hashtable面试的范围，但是如果你
想exceed expectation，mention this.
很多刚毕业的菜鸟喜欢在面试的时候胡吹一些"advanced technology"以达到shock-and
-owe的效果，use it wisely。比如下面这个就非常的un-wise：
“你知道你一个bucket有100个element，多线程同时写在mutex上要等多久么？不过你
提的这个throughput可能用mutex也能达到”
听着都能让人笑出来，你想证明copy-on-write比mutext快吗？显然不可能。
你想说明你懂得mutex和同步吗？看着不像啊，我要是面试官就直接问你“你知道一个
100个element的链表，找到正确的elemen要多长时间？你准备从mutex那里省多少时间
？”，然后就直接问mutex/semahpore/monitor的区别。你如果不提lock这个字，直接
废掉。
最后一点给刚毕业的菜鸟的忠告，你也许看了很多paper，但是99%都是theoretical
junk。在向面试官解释一个新的革命性成果之前，一定要tune down a little bit,并
且附上RFC link:
https://www.kernel.org/doc/Documentation/RCU/whatisRCU.txt
a. Remove pointers to a data structure, so that subsequent
readers cannot gain a reference to it.
b. Wait for all previous readers to complete their RCU read-side
critical sections.
c. At this point, there cannot be any readers who hold references
to the data structure, so it now may safely be reclaimed
(e.g., kfree()d).
然后自然地就问了，你这b和c，和locking有什么区别，有什么显著的提高。然后你提
不出任何依据。
最后面试官失望地说，扯了半天忘了最重要的事，你说说re-hash吧。然后你说，re-
hash有啥重要的？面试官低头看了看简历，决心把你废掉。
【在 T*****g 的大作中提到】
: 哥们你做过synchronization相关的工作么？你知道你一个bucket有100个element，多
: 线程同时写在mutex上要等多久么？不过你提的这个throughput可能用mutex也能达到，
: 只能说你是没见过高性能的salable hashtable
: 不要误导人了，谁告诉你要copy一整条bucket来做copy on write？（有人提到RCU了，
: RCU就可以做）。RCU的难点只在于resize的时候不好处理，不过已经有人把这个问题解
: 决了。
:
: 如，
|
T*****g
发帖数: 1306 | 45 算了，你还是活在自己的世界里吧
real
★ 发自iPhone App: ChineseWeb 16
【在 l*********r 的大作中提到】
: 我一直强调的是绝对不可以在hashtable的设计(尤其在面试的时候)用copy-on-write，
: 一定要用lock。
: 第一点：最基本的常识，只能有一个thread来写，比如hashtable的值用作counter。用
: copy-on-write，立马废掉。
: 第二点: 更进一步的synchronization，是要保证global ordering。比如狗家股票real
: time streaming, 绝对不可以11:11:11.002的报价先写入，然后11:11:11.000的报价
: 后写入。这就有不少的实现方法。这个已经超出了hashtable面试的范围，但是如果你
: 想exceed expectation，mention this.
: 很多刚毕业的菜鸟喜欢在面试的时候胡吹一些"advanced technology"以达到shock-and
: -owe的效果，use it wisely。比如下面这个就非常的un-wise：
|
l*********r
发帖数: 105 | 46 http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/6-b14/java/util/concurrent/ConcurrentHashMap.java
仔细研究一下source code，Java在近乎30年的历史里为generic的hashmap选择了lock
striping的解决方法，java是如何做rehashing, 如何做striping的。其他一些类似于
lady gaga的花招就没必要研究了。
【在 l********e 的大作中提到】
: 这个面经宝贵～
: 我会去看 相关内容
: 不过 能说说 一般这些问题 怎么回答能过呢？
: 我觉得如果要用 锁 希望效率高 就要在每个slot上都有一个独立的锁
: 1. 如果有大量的写入新value，如何保证concurrency和efficiency 除了用每个
: slot用独立一个锁 增大array size, 不要产生长linked list, 还能什么别的方法来效
: 率高呢？
: 2. 如果有大量的写入新key ：用很大的array, 减少冲突，减少expand的情况？
: 3. 如果有大量的写new key/删除new key 同上（感觉和上一个区别不大。。。）
: 4. 如果有大量的读和少量的写 ：用读写锁？
|
l********e
发帖数: 103 | 47 我觉得 面试的时候
可能根据面试人水平 面的东西 有不同侧重
我这样菜鸟 估计就问问lock
楼上各位大牛 也许就问lock free的东东了。。。
不同level 问不同的东西
反正 知识都是对的～ 呵呵 |
g******o
发帖数: 6 | 48 在这里争哪种实现效率更好没有意义，不如约战github，想用rcu的用rcu，用CoW的用
CoW，用锁的用锁，各自实现几个，然后跑个分，talk is cheap, show LZ the code |
j**********r
发帖数: 3798 | 49 面试就是要多问清楚了再答。不是上来什么都用斧头。如果单机没有性能要求自然
mutex锁全部是可行的。什么产品环境不能用就是扯蛋，人又没说产品环境什么要求。
没准要求是所有变化序列化可见，ConcurrentMap就不行。
real
and
【在 l*********r 的大作中提到】
: 我一直强调的是绝对不可以在hashtable的设计(尤其在面试的时候)用copy-on-write，
: 一定要用lock。
: 第一点：最基本的常识，只能有一个thread来写，比如hashtable的值用作counter。用
: copy-on-write，立马废掉。
: 第二点: 更进一步的synchronization，是要保证global ordering。比如狗家股票real
: time streaming, 绝对不可以11:11:11.002的报价先写入，然后11:11:11.000的报价
: 后写入。这就有不少的实现方法。这个已经超出了hashtable面试的范围，但是如果你
: 想exceed expectation，mention this.
: 很多刚毕业的菜鸟喜欢在面试的时候胡吹一些"advanced technology"以达到shock-and
: -owe的效果，use it wisely。比如下面这个就非常的un-wise：
|
N*****m
发帖数: 42603 | 50 op，下次碰到这种题，如果是Java的话，起码提一下NonBlockingHashMap
【在 l********e 的大作中提到】
: 面试时候
: 被问到 写个 多线程的hash table
: hash table我用linked list解决collision 问题
: 加lock的时候 我说 要用read write lock
: hash table insert 时候用write lock
: get的时候用read lock
: 然后 面试官跟我说
: get的时候 不用加任何lock
: 大不了 get的值是旧的
: （我当时 没说话 心想 只要 让我过 你说什么都好）
|
|
|
N*****m
发帖数: 42603 | 51 这是重复设计轮子
lock-free的hashmap早就有了，如果没有性能优势，吃饱了设计这个
【在 g******o 的大作中提到】
: 在这里争哪种实现效率更好没有意义，不如约战github，想用rcu的用rcu，用CoW的用
: CoW，用锁的用锁，各自实现几个，然后跑个分，talk is cheap, show LZ the code
|
g******o
发帖数: 6 | 52 现在评论区争论的是能不能用CoW实现， 以及效率怎么样， 让linuxhacker和Touareg
各自按照自己的思路实现一下对比一下就完了，光说谁都说不过谁。再说了，面试被问
到这种问题不也就是在问轮子怎么设计的么，你能怼面试官一句“这是重复设计轮子”？
【在 N*****m 的大作中提到】
: 这是重复设计轮子
: lock-free的hashmap早就有了，如果没有性能优势，吃饱了设计这个
|
H**********5
发帖数: 2012 | 53 好帖，报上应该多些这种帖子。
多线程是必考题。 |
N*****m
发帖数: 42603 | 54 说的就是实现早就有了，自己去看好了
面试和版上讨论是一码事吗？
Touareg
”？
【在 g******o 的大作中提到】
: 现在评论区争论的是能不能用CoW实现， 以及效率怎么样， 让linuxhacker和Touareg
: 各自按照自己的思路实现一下对比一下就完了，光说谁都说不过谁。再说了，面试被问
: 到这种问题不也就是在问轮子怎么设计的么，你能怼面试官一句“这是重复设计轮子”？
|
g******o
发帖数: 6 | 55 这种开放性的设计类面试跟版上讨论有啥区别？
【在 N*****m 的大作中提到】
: 说的就是实现早就有了，自己去看好了
: 面试和版上讨论是一码事吗？
:
: Touareg
: ”？
|
N*****m
发帖数: 42603 | 56 当然有，面试是回答问题，版上就自己去学了再来说。
自己不学，还要人去github写code，这不是搞笑嘛
【在 g******o 的大作中提到】
: 这种开放性的设计类面试跟版上讨论有啥区别？
|
j**********r
发帖数: 3798 | 57 当然，能知道啥场景用啥轮子就好了。问我轮子咋设计，当然让他读JDK源码。如果不
服，让面试官写一个看看能不能bug free.
Touareg
”？
【在 g******o 的大作中提到】
: 现在评论区争论的是能不能用CoW实现， 以及效率怎么样， 让linuxhacker和Touareg
: 各自按照自己的思路实现一下对比一下就完了，光说谁都说不过谁。再说了，面试被问
: 到这种问题不也就是在问轮子怎么设计的么，你能怼面试官一句“这是重复设计轮子”？
|
N*****m
发帖数: 42603 | 58 而且，真能把轮子说出来，至少说明他多少了解一些。
【在 j**********r 的大作中提到】
: 当然，能知道啥场景用啥轮子就好了。问我轮子咋设计，当然让他读JDK源码。如果不
: 服，让面试官写一个看看能不能bug free.
:
: Touareg
: ”？
|
g******o
发帖数: 6 | 59 不是学不学的问题，争来争去谁也说服不了谁，不拿代码说话怎么办？
【在 N*****m 的大作中提到】
: 当然有，面试是回答问题，版上就自己去学了再来说。
: 自己不学，还要人去github写code，这不是搞笑嘛
|
l*********r
发帖数: 105 | 60 我看了看RCU，哥们你真是胆子大，居然敢在面试的时候拿这个出来，
However,RCU does not have any write side primitive which looks traditional
write lock. That is, their update side primitives need other locks to keep
threads safe.
http://www.cs.nyu.edu/~lerner/spring11/proj_rcu.pdf page 6 & 7
就是说，RCU只允许一个写线程，一个一个地写。如果有多于一个的写线程，必须要使
用另外的锁进行同步。具体的source code这个slide里面都有。
所以RCU依赖于其他的resource锁定方式，根本不可能是lock free的。我一直说，有些
theoretical junk是依赖于unreal的假设，根本不实用。
"
我一直强调的是绝对不可以在hashtable的设计(尤其在面试的时候)用copy-on-write，
一定要用lock。
第一点：最基本的常识，只能有一个thread来写，比如hashtable的值用作counter。用
copy-on-write，立马废掉。
第二点: 更进一步的synchronization，是要保证global ordering。比如狗家股票real
time streaming, 绝对不可以11:11:11.002的报价先写入，然后11:11:11.000的报价
后写入。这就有不少的实现方法。这个已经超出了hashtable面试的范围，但是如果你
想exceed expectation，mention this.
"
如果你一开始就胡说八道什么RCU高性能hashtable, lock free之类，把面试官唬住了
。这哥们回办公桌上一查(我也就花了20分钟不到)，我靠这哥们给我废话了一堆，立马
火上心头，废了。 |
|
|
g*********e
发帖数: 14401 | 61 面试本身，就是一个考察设计轮子能力的过程。
用轮子没什么可以问的，也没什么区分度，轮子那么多，未必都听说过。设计的理念却
是万变不离其宗的，都是基于os computer的基本概念。
起码要问轮子的internal大致原理。 |
w***x
发帖数: 105 | 62 其实折腾一圈下来你会发现又回到了r/w mutex而已。
reference
【在 T*****g 的大作中提到】
: 为什么不能？
: 我拿到了list里一个node的reference，只要这个node不被free我的access就不会有
: segfault，同时我读到的数据是point-in-time consistent的（是在我拿到reference
: 的时候的snapshot）
: change value可以copy-on-write, add / change node我用atomic pointer可以很容易
: 实现，然后等所有拿到这个node 的reference的reader都退出的时候就可以free掉了。
: free这部分要避免segfault可以用最简单的ref count pointer来实现，当然RCU更好，
: 因为更scalable。
|
w***x
发帖数: 105 | 63 rcu设计本来就是一个w，多个r，这种情况下确实是lockfree，无论w还是r。
不过我一直不清楚user mode下怎么实现。
【在 l*********r 的大作中提到】
: 我看了看RCU，哥们你真是胆子大，居然敢在面试的时候拿这个出来，
: However,RCU does not have any write side primitive which looks traditional
: write lock. That is, their update side primitives need other locks to keep
: threads safe.
: http://www.cs.nyu.edu/~lerner/spring11/proj_rcu.pdf page 6 & 7
: 就是说，RCU只允许一个写线程，一个一个地写。如果有多于一个的写线程，必须要使
: 用另外的锁进行同步。具体的source code这个slide里面都有。
: 所以RCU依赖于其他的resource锁定方式，根本不可能是lock free的。我一直说，有些
: theoretical junk是依赖于unreal的假设，根本不实用。
: "
|
w***x
发帖数: 105 | 64 “user space的implementation里好像是靠拿到每个worker的mutex来实现”， 那这个
就没什么意义了吧？也就不是lockfree了。
【在 T*****g 的大作中提到】
: 这俩不是一个层面的吧
: CAS是CPU instruction不存在read side critical section吧，你之前拿到了旧的
: pointer那就是可以reference旧的object，具体到硬件
: 实现上有不同的办法，但是语义是一样的
: RCU会有一个quiescent period来确保所有的read side critical section都结束，在
: user space的implementation里好像是靠拿到每个worker的mutex来实现
:
: ★ 发自iPhone App: ChineseWeb 16
|
T*****g
发帖数: 1306 | 65 rwlook 不scale啊，你CPU core一多，到2个socket或者4个，你就会发现问题了
rwlock的问题在于reader虽然只读，但是还是会往shared memory里写东西（update
reader count），这就是scalability bottleneck了。。。
【在 w***x 的大作中提到】
: 其实折腾一圈下来你会发现又回到了r/w mutex而已。
:
: reference
|
T*****g
发帖数: 1306 | 66 RCU的user space 实现比kernel space实现overhead要高，但是还是非常scalable，比
rwlock之类的强多了啊
其实主要的优势在于不modify的时候不往shared memory写数据，避免cache line
bouncing
当然这些偏底层了，不做这个的人估计理解起来有点困难
【在 w***x 的大作中提到】
: “user space的implementation里好像是靠拿到每个worker的mutex来实现”， 那这个
: 就没什么意义了吧？也就不是lockfree了。
|
T*****g
发帖数: 1306 | 67 呵呵，这个就不必了吧，写了好几年的scalable data structure，这里只是分享一下
自己的理解，约这种东西，实在是没时间
就像楼下说的，开源代码太多，有兴趣自己去找来写个benchmark比一比，做做
profiling大概就能知道性能瓶颈在哪里，有条件最好试试多一点CPU，比如NUMA，就能
理解到这些synchronization mechanism的优劣了
【在 g******o 的大作中提到】
: 在这里争哪种实现效率更好没有意义，不如约战github，想用rcu的用rcu，用CoW的用
: CoW，用锁的用锁，各自实现几个，然后跑个分，talk is cheap, show LZ the code
|
T*****g
发帖数: 1306 | 68 利用RCU的idea可以做很多拓展，你要想multi-writer是可以自己做的，不要被最基本
的RCU的定义给限制了
放狗搜一下，你就明白了
【在 l*********r 的大作中提到】
: 我看了看RCU，哥们你真是胆子大，居然敢在面试的时候拿这个出来，
: However,RCU does not have any write side primitive which looks traditional
: write lock. That is, their update side primitives need other locks to keep
: threads safe.
: http://www.cs.nyu.edu/~lerner/spring11/proj_rcu.pdf page 6 & 7
: 就是说，RCU只允许一个写线程，一个一个地写。如果有多于一个的写线程，必须要使
: 用另外的锁进行同步。具体的source code这个slide里面都有。
: 所以RCU依赖于其他的resource锁定方式，根本不可能是lock free的。我一直说，有些
: theoretical junk是依赖于unreal的假设，根本不实用。
: "
|
N*****m
发帖数: 42603 | 69 首先能说出轮子，就已经比根本不知道轮子的强了
其次，我是建议与其在本版低水平的争吵，不如去看看轮子都是怎么写的
跟面试谈当然是两码事
【在 g*********e 的大作中提到】
: 面试本身，就是一个考察设计轮子能力的过程。
: 用轮子没什么可以问的，也没什么区分度，轮子那么多，未必都听说过。设计的理念却
: 是万变不离其宗的，都是基于os computer的基本概念。
: 起码要问轮子的internal大致原理。
|
