140:. The extent in which these problems manifest or even occur at all depends on the implementation of the concurrent hash table; specifically which operations the table allows to be run concurrently, as well as its strategies for mitigating problems associated with contention. When handling contention, the main goal is the same as with any other concurrent data structure, namely ensuring correctness for every operation on the table. At the same time, it should naturally be done in such a way as to be more efficient than a sequential solution when used concurrently. This is also known as
121:
194:, operations trying to concurrently access the table or values within it can be handled in a way that ensures correct behavior. This can however lead to negative performance impacts, in particular when the locks used are too restrictive, thus blocking accesses that would otherwise not contend and could execute without causing any problems. Further considerations have to be made to avoid even more critical problems that threaten correctness, as with livelocks, deadlocks or
207:
17:
1058:
351:
for concurrency control restricting contending accesses. The resulting overhead causes worse performance than that of the ideal sequential version. In spite of this, concurrent hash tables still prove invaluable even in such high contention scenarios when observing that a well-designed implementation can still achieve very high speedups by leveraging the benefits of concurrency to read data concurrently.
167:, problems caused by contention can be reduced by ensuring that an access is completed before another access has the chance to interfere. Operations such as compare-and-swap often present limitations as to what size of data they can handle, meaning that the types of keys and values of a table have to be chosen or converted accordingly.
96:
When hash tables are not bound in size and are thus allowed to grow/shrink when necessary, the hashing algorithm needs to be adapted to allow this operation. This entails modifying the used hash function to reflect the new key-space of the resized table. A concurrent growing algorithm is described by
78:
As with their sequential counterpart, concurrent hash tables can be generalized and extended to fit broader applications, such as allowing more complex data types to be used for keys and values. These generalizations can however negatively impact performance and should thus be chosen in accordance to
87:
When creating concurrent hash tables, the functions accessing the table with the chosen hashing algorithm need to be adapted for concurrency by adding a conflict resolution strategy. Such a strategy requires managing accesses in a way such that conflicts caused by them do not result in corrupt data,
369:
Ultimately the resulting performance of a concurrent hash table depends on a variety of factors based upon its desired application. When choosing the implementation, it is important to determine the necessary amount of generality, contention handling strategies and some thoughts on whether the size
350:
As expected low contention leads to positive behavior across every operation, whereas high contention becomes problematic when it comes to writing. The latter however is a problem of high contention in general, wherein the benefit of concurrent computation is negated due to the natural requirement
420:
interface. Included within are the concurrent unordered multimaps, which allow multiple values to exist for the same key in a concurrent unordered map. Additionally, concurrent hash maps are provided which build upon the concurrent unordered map and further allow concurrent erasure and contain
92:
algorithm - can be adapted for concurrent use. Fan et al. further describe a table access scheme based on cuckoo hashing that is not only concurrent, but also keeps the space efficiency of its hashing function while also improving cache locality as well as the throughput of insertions.
432:
implementation. Based on this non-growing implementation, a variety of different growing hash tables is given. These implementations allow for concurrent reads, inserts, updates (notably updating values based on the current value at the key) and removals (based upon updating using
255:
Maier et al. perform a thorough analysis on a variety of concurrent hash table implementations, giving insight into the effectiveness of each in different situations that are likely to occur in real use-cases. The most important findings can be summed up as the following:
242:
Naturally, concurrent hash tables find application wherever sequential hash tables are useful. The advantage that concurrency delivers herein lies within the potential speedup of these use-cases, as well as the increased scalability. Considering hardware such as
67:- the way and scope in which the table can be concurrently accessed differs depending on the implementation. Furthermore, the resulting speed up might not be linear with the amount of threads used as contention needs to be resolved, producing processing
88:
while ideally increasing their efficiency when used in parallel. Herlihy and Shavit describe how the accesses to a hash table without such a strategy - in its example based on a basic implementation of the
128:
As with any concurrent data structure, concurrent hash tables suffer from a variety of problems known in the field of concurrent computing as a result of contention. Examples for such are the
354:
However, real use-cases of concurrent hash tables are often not simply sequences of the same operation, but rather a mixture of multiple types. As such, when a mixture of
879:
304:
High speedups reached, high contention becomes problematic when keys can hold more than one value (otherwise inserts are simply discarded if key already exists)
967:
214:
A phase concurrent hash table groups accesses by creating phases in which only one type of operation is allowed (i.e. a pure write-phase), followed by a
247:
that become increasingly more capable of concurrent computation, the importance of concurrent data structures within these applications grow steadily.
179:
929:
619:
Li, Xiaozhou; Andersen, David G.; Kaminsky, Michael; Freedman, Michael J. (2014). "Algorithmic
Improvements for Fast Concurrent Cuckoo Hashing".
318:
Both overwrites and modifications of existing values reach high speedups when contention is kept low, otherwise performs worse than sequential
848:
683:
636:
592:
466:
on the basis of atomic operations to ensure thread-safety for any given member function of the table. The library is available on GitHub.
1083:
962:
952:
872:
215:
733:
Chu, Ching-Hsing; Potluri, Sreeram; Goswami, Anshuman; Venkata, Manjunath
Gorentla; Imam, Neenaand; and Newburn, Chris J. (2018) "
957:
362:
operations is used the speedup and resulting usefulness of concurrent hash tables become more obvious, especially when observing
734:
112:, Mega-KV was pushed to another high record of the throughput in 2018 (up to 888 millions of key-value operations per second).
104:
is used and the KV indexing is massively parallelized in batch mode by GPU. With further optimizations of GPU acceleration by
902:
156:
72:
38:
26:
1028:
1088:
1062:
865:
452:
195:
746:
1038:
1023:
1018:
801:
381:
137:
1013:
912:
406:
153:
53:
395:
721:
527:
Maier, Tobias; Sanders, Peter; Dementiev, Roman (March 2019). "Concurrent Hash Tables: Fast and
General(?)!".
1043:
434:
341:
191:
218:
of the table state across all threads. A formally proven algorithm for this is given by Shun and
Blelloch.
109:
290:
Very high speedups both when successful and unsuccessful unique finds, even with very high contention
888:
735:
Designing High-performance in-memory key-value operations with persistent GPU kernels and OPENSHMEM".
244:
175:
171:
68:
57:
907:
141:
64:
769:
Threading
Building Blocks concurrent_unordered_map and concurrent_unordered_multimap documentation
708:
nsdi'13: Proceedings of the 10th USENIX conference on
Networked Systems Design and Implementation
552:
476:
387:
42:
839:
Herlihy, Maurice; Shavit, Nir (2008). "Chapter 13: Concurrent
Hashing and Natural Parallelism".
674:
Herlihy, Maurice; Shavit, Nir (2008). "Chapter 13: Concurrent
Hashing and Natural Parallelism".
234:(RCU) is especially useful in cases where the number of reads far exceeds the number of writes.
120:
60:
which allow multiple threads to more efficiently cooperate for a computation among shared data.
71:. There exist multiple solutions to mitigate the effects of contention, that each preserve the
844:
679:
632:
588:
577:
SPAA '14: Proceedings of the 26th ACM symposium on
Parallelism in algorithms and architectures
544:
370:
of the desired table can be determined in advance or a growing approach must be used instead.
661:
USENIXATC'11: Proceedings of the 2011 USENIX conference on USENIX annual technical conference
977:
944:
624:
580:
536:
231:
206:
160:
934:
924:
720:
Zhang, Kai; Wang, Kaibo; Yuan, Yuan; Guo, Lei; Lee, Rubao; and Zhang, Xiaodong (2015). "
1033:
575:
Shun, Julian; Blelloch, Guy E. (2014). "Phase-concurrent Hash Tables for
Determinism".
133:
101:
89:
455:
writers. As stated on its GitHub page, this library provides useful functionality for
413:
which allow concurrent insertion and traversal and are kept in a similar style to the
332:
Phase concurrency reached highest scalability; Fully concurrent implementations where
1077:
992:
972:
164:
46:
703:
656:
556:
982:
722:
Mega-KV: a case for GPUs to maximize the throughput of in-memory key-value stores".
227:
16:
1008:
704:"MemC3: Compact and Concurrent MemCache with Dumber Caching and Smarter Hashing"
129:
779:
768:
29:
548:
843:. San Francisco, CA, USA: Morgan Kaufmann Publishers Inc. pp. 299–328.
678:. San Francisco, CA, USA: Morgan Kaufmann Publishers Inc. pp. 316–325.
628:
584:
438:
657:"Resizable, Scalable, Concurrent Hash Tables via Relativistic Programming"
757:
481:
456:
403:
allowing concurrent reads and writes. The library is available on GitHub.
462:
Junction provides several implementations of concurrent hash tables for
446:
414:
857:
823:
63:
Due to the natural problems associated with concurrent access - namely
790:
105:
812:
540:
399:
486:
205:
119:
15:
987:
621:
Proceedings of the Ninth European Conference on Computer Systems
100:
Mega-KV is a high performance key-value store system, where the
861:
802:
GitHub page for implementation of concurrent hash maps in folly
655:
Triplett, Josh; McKenney, Paul E.; Walpole, Jonathan (2011).
178:, ensuring atomicity. An example of HTM in practice are the
780:
Threading Building Blocks concurrent_hash_map documentation
724:
Proceedings of the VLDB Endowment, Vol. 8, No. 11, 2015.
702:
Fan, Bin; Andersen, David G.; Kaminsky, Michael (2013).
124:
Concurrent accesses causing contention (marked in red).
710:. Berkeley, CA: USENIX Association. pp. 371–384.
174:(HTM), table operations can be thought of much like
1001:
943:
895:
424:growt provides concurrent growing hash tables for
441:are provided. The library is available on GitHub.
210:Concurrent accesses grouped into distinct phases.
663:. Berkeley, CA: USENIX Association. p. 11.
386:, concurrent hash maps are provided based upon
623:. EuroSys '14. New York: ACM. Article No. 27.
393:libcuckoo provides concurrent hash tables for
873:
37:is an implementation of hash tables allowing
8:
451:ensuring wait-free readers and lock-based,
20:Concurrent accesses to the same hash table.
880:
866:
858:
650:
648:
444:folly provides concurrent hash tables for
535:(4). New York, NY, USA: ACM. Article 16.
437:). Beyond that, variants on the basis of
522:
258:
180:Transactional Synchronization Extensions
520:
518:
516:
514:
512:
510:
508:
506:
504:
502:
498:
52:Concurrent hash tables represent a key
570:
568:
566:
529:ACM Transactions on Parallel Computing
409:provide concurrent unordered maps for
841:The Art of Multiprocessor Programming
697:
695:
676:The Art of Multiprocessor Programming
267:
264:
261:
79:the requirements of the application.
7:
747:Java ConcurrentHashMap documentation
614:
612:
610:
608:
606:
604:
579:. New York: ACM. pp. 96–107.
14:
1057:
1056:
758:GitHub repository for libcuckoo
1063:Category: Concurrent computing
824:GitHub repository for Junction
428:on the basis of the so-called
1:
75:of operations on the table.
1024:Dining philosophers problem
813:GitHub repository for folly
791:GitHub repository for growt
1105:
1084:Hash-based data structures
913:Concurrent data structures
1052:
1029:Producer–consumer problem
1014:Cigarette smokers problem
407:Threading Building Blocks
170:Using so called Hardware
54:concurrent data structure
388:concurrent map interface
1044:Sleeping barber problem
1039:Readers–writers problem
629:10.1145/2592798.2592820
585:10.1145/2612669.2612687
226:Widely used within the
918:Concurrent hash tables
211:
125:
110:Oak Ridge National Lab
21:
245:multi-core processors
209:
176:database transactions
123:
19:
1089:Concurrent computing
889:Concurrent computing
344:were closely behind
251:Performance analysis
172:Transactional Memory
58:concurrent computing
908:Concurrency control
148:Atomic instructions
142:concurrency control
116:Contention handling
35:concurrent hash map
477:Parallel computing
418:std::unordered_map
212:
126:
83:Concurrent hashing
22:
1071:
1070:
850:978-0-12-370591-4
685:978-0-12-370591-4
638:978-1-4503-2704-6
594:978-1-4503-2821-0
421:built-in locking.
366:heavy workloads.
348:
347:
202:Phase concurrency
190:With the help of
39:concurrent access
1096:
1060:
1059:
1002:Classic problems
978:Ambient calculus
925:Concurrent users
882:
875:
868:
859:
854:
826:
821:
815:
810:
804:
799:
793:
788:
782:
777:
771:
766:
760:
755:
749:
744:
738:
731:
725:
718:
712:
711:
699:
690:
689:
671:
665:
664:
652:
643:
642:
616:
599:
598:
572:
561:
560:
524:
419:
365:
361:
357:
339:
335:
325:
311:
297:
283:
259:
232:read-copy-update
222:Read-copy-update
161:compare-and-swap
1104:
1103:
1099:
1098:
1097:
1095:
1094:
1093:
1074:
1073:
1072:
1067:
1048:
997:
945:Process calculi
939:
935:Linearizability
891:
886:
851:
838:
835:
833:Further reading
830:
829:
822:
818:
811:
807:
800:
796:
789:
785:
778:
774:
767:
763:
756:
752:
745:
741:
732:
728:
719:
715:
701:
700:
693:
686:
673:
672:
668:
654:
653:
646:
639:
618:
617:
602:
595:
574:
573:
564:
541:10.1145/3309206
526:
525:
500:
495:
473:
417:
376:
374:Implementations
363:
359:
355:
337:
333:
323:
309:
295:
281:
253:
240:
224:
216:synchronization
204:
188:
150:
134:race conditions
118:
85:
12:
11:
5:
1102:
1100:
1092:
1091:
1086:
1076:
1075:
1069:
1068:
1066:
1065:
1053:
1050:
1049:
1047:
1046:
1041:
1036:
1034:Race condition
1031:
1026:
1021:
1016:
1011:
1005:
1003:
999:
998:
996:
995:
990:
985:
980:
975:
970:
965:
960:
955:
949:
947:
941:
940:
938:
937:
932:
927:
922:
921:
920:
910:
905:
899:
897:
893:
892:
887:
885:
884:
877:
870:
862:
856:
855:
849:
834:
831:
828:
827:
816:
805:
794:
783:
772:
761:
750:
739:
726:
713:
691:
684:
666:
644:
637:
600:
593:
562:
497:
496:
494:
491:
490:
489:
484:
479:
472:
469:
468:
467:
460:
442:
422:
404:
391:
375:
372:
346:
345:
342:dummy-elements
330:
328:
326:
320:
319:
316:
314:
312:
306:
305:
302:
300:
298:
292:
291:
288:
286:
284:
278:
277:
274:
270:
269:
266:
263:
252:
249:
239:
236:
223:
220:
203:
200:
187:
184:
149:
146:
117:
114:
102:cuckoo hashing
90:Cuckoo hashing
84:
81:
13:
10:
9:
6:
4:
3:
2:
1101:
1090:
1087:
1085:
1082:
1081:
1079:
1064:
1055:
1054:
1051:
1045:
1042:
1040:
1037:
1035:
1032:
1030:
1027:
1025:
1022:
1020:
1017:
1015:
1012:
1010:
1007:
1006:
1004:
1000:
994:
993:Join-calculus
991:
989:
986:
984:
981:
979:
976:
974:
971:
969:
966:
964:
961:
959:
956:
954:
951:
950:
948:
946:
942:
936:
933:
931:
930:Indeterminacy
928:
926:
923:
919:
916:
915:
914:
911:
909:
906:
904:
901:
900:
898:
894:
890:
883:
878:
876:
871:
869:
864:
863:
860:
852:
846:
842:
837:
836:
832:
825:
820:
817:
814:
809:
806:
803:
798:
795:
792:
787:
784:
781:
776:
773:
770:
765:
762:
759:
754:
751:
748:
743:
740:
736:
730:
727:
723:
717:
714:
709:
705:
698:
696:
692:
687:
681:
677:
670:
667:
662:
658:
651:
649:
645:
640:
634:
630:
626:
622:
615:
613:
611:
609:
607:
605:
601:
596:
590:
586:
582:
578:
571:
569:
567:
563:
558:
554:
550:
546:
542:
538:
534:
530:
523:
521:
519:
517:
515:
513:
511:
509:
507:
505:
503:
499:
492:
488:
485:
483:
480:
478:
475:
474:
470:
465:
461:
458:
454:
450:
448:
443:
440:
436:
431:
427:
423:
416:
412:
408:
405:
402:
401:
397:
392:
389:
385:
383:
378:
377:
373:
371:
367:
352:
343:
331:
329:
327:
322:
321:
317:
315:
313:
308:
307:
303:
301:
299:
294:
293:
289:
287:
285:
280:
279:
275:
272:
271:
260:
257:
250:
248:
246:
237:
235:
233:
229:
221:
219:
217:
208:
201:
199:
197:
193:
185:
183:
181:
177:
173:
168:
166:
165:fetch-and-add
162:
158:
155:
147:
145:
143:
139:
135:
131:
122:
115:
113:
111:
107:
103:
98:
97:Maier et al.
94:
91:
82:
80:
76:
74:
70:
66:
61:
59:
55:
50:
48:
47:hash function
44:
40:
36:
32:
31:
28:
18:
983:API-Calculus
917:
840:
819:
808:
797:
786:
775:
764:
753:
742:
729:
716:
707:
675:
669:
660:
620:
576:
532:
528:
463:
445:
429:
425:
410:
394:
380:
368:
353:
349:
254:
241:
238:Applications
228:Linux kernel
225:
213:
189:
169:
157:instructions
151:
127:
99:
95:
86:
77:
62:
51:
41:by multiple
34:
25:
23:
1009:ABA problem
903:Concurrency
265:Contention
130:ABA problem
73:correctness
56:for use in
1078:Categories
973:Ď€-calculus
493:References
435:tombstones
262:Operation
196:starvation
65:contention
30:hash table
27:concurrent
549:2329-4949
449:and later
439:Intel TSX
138:deadlocks
1019:Deadlock
557:67870641
482:Liveness
471:See also
457:Facebook
430:folklore
159:such as
69:overhead
45:using a
896:General
453:sharded
186:Locking
43:threads
1061:
847:
682:
635:
591:
555:
547:
379:Since
356:insert
338:update
334:delete
324:delete
310:update
296:insert
268:Notes
154:atomic
152:Using
136:, and
106:Nvidia
968:LOTOS
553:S2CID
487:Ctrie
447:C++14
415:C++11
340:with
336:uses
276:High
192:locks
988:PEPA
845:ISBN
680:ISBN
633:ISBN
589:ISBN
545:ISSN
382:Java
364:find
360:find
358:and
282:find
273:Low
108:and
963:ACP
958:CCS
953:CSP
625:doi
581:doi
537:doi
464:C++
426:C++
411:C++
400:C++
384:1.5
163:or
33:or
1080::
706:.
694:^
659:.
647:^
631:.
603:^
587:.
565:^
551:.
543:.
531:.
501:^
230:,
198:.
182:.
144:.
132:,
49:.
24:A
881:e
874:t
867:v
853:.
737:.
688:.
641:.
627::
597:.
583::
559:.
539::
533:5
459:.
398:/
396:C
390:.
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
