jjzjj

c++ - 制作 C++ 哈希表的最佳策略，线程安全

coder 2024-02-02 原文

(我对实现的设计感兴趣，而不是一个可以完成所有工作的现成结构。)

假设我们有一个 HashTable 类(不是作为树实现的哈希映射而是哈希表)
并说有八个线程。
假设读写比约为 100:1 或更好的 1000:1。
情况 A)只有一个线程是写入者，而其他线程(包括写入者)可以从 HashTable 中读取(它们可能简单地遍历整个哈希表)
情况 B)所有线程都是相同的，并且都可以读/写。

有人可以建议最好的策略来使类线程安全并考虑以下因素
1. 最高优先级，最小锁争用
2. 最少锁数的第二优先级

到目前为止，我的理解是:
一个 BIG 读写锁(信号量)。
特殊化信号量，以便在情况 B 中可以有八个实例 writer-resource，其中每个 writer 资源锁定一行(或就此而言的范围)。
(所以我猜 1+8 互斥体)

请让我知道我的想法是否正确，以及我们如何改进此解决方案。

最佳答案

有了如此高的读/写比率，您应该考虑无锁解决方案，例如nbds .

编辑:

一般来说，无锁算法的工作原理如下:

  • 安排您的数据结构，以便对于您打算支持的每个功能，您可以在一个原子操作中确定其结果是否有效(即，其他线程在读取后​​没有改变其输入)并委身于他们；除非您提交，否则不会更改其他线程可见的状态。这将涉及利用特定于平台的功能，例如 Win32 的原子比较和交换或 Cell 的缓存行保留操作码。
  • 每个支持的函数变成一个循环，重复读取输入并尝试执行工作，直到提交成功。

    • 在争用非常低的情况下，这是对锁定算法的性能优势，因为函数大部分都是第一次成功，而不会产生获取锁的开销。随着竞争的增加， yield 变得更加可疑。

    通常可以原子操作的数据量很小 - 32 或 64 位很常见 - 因此对于涉及许多读取和写入的函数，结果算法变得复杂并且可能很难推理。出于这个原因，最好为您的问题寻找并采用成熟的、经过充分测试且易于理解的第三方无锁解决方案，而不是自行解决。

    哈希表的实现细节将取决于哈希表设计的各个方面。我们是否希望能够扩大 table ？如果是这样，我们需要一种方法将大量数据从旧表安全地复制到新表中。我们期望哈希冲突吗？如果是这样，我们需要一些行走碰撞数据的方法。我们如何确保另一个线程不会删除返回它的查找和使用它的调用者之间的键/值对？也许是某种形式的引用计数？ - 但谁拥有引用？ - 或者只是在查找时复制值？ - 但是如果值很大怎么办？

    无锁堆栈很好理解并且实现起来相对简单(从堆栈中删除一个项目，获取当前顶部，尝试用它的下一个指针替换它直到成功，返回它；添加一个项目，获取当前顶部并将其设置为项目的下一个指针，直到您成功将项目的指针写入作为新的顶部；在具有保留/条件写入语义的体系结构上，这就足够了，在仅支持 CAS 的体系结构上，您需要附加一个随机数或版本编号到原子操作的数据以避免 ABA problem )。它们是一种以原子锁自由方式跟踪键/数据的可用空间的方法，允许您将键/值对(实际存储在哈希表条目中的数据)减少到一个或两个指针/偏移量，一个小的足够的数量可以使用您的架构的原子指令进行操作。还有其他人。

    然后读取变成了查找条目的情况，根据请求的键检查 kvp，做任何事情以确保返回值时该值仍然有效(获取拷贝/增加其引用计数)，检查条目是否'自从我们开始读取以来没有被修改，如果是，则返回值，撤消任何引用计数更改，如果不是，则重复读取。
    写入取决于我们对冲突的处理方式；在微不足道的情况下，它们只是找到正确的空槽并写入新的 kvp 的情况。
    以上已大大简化，不足以生成您自己的安全实现，尤其是在您不熟悉无锁/无等待技术的情况下。可能的并发症包括 ABA 问题、优先级反转、特定线程的饥饿；我没有解决散列冲突。

    nbds 页面链接到 excellent presentation在允许增长/碰撞的现实世界方法上。其他存在，一个快速的谷歌发现很多论文。

    无锁和无等待算法是令人着迷的研究领域。我鼓励读者谷歌一下。也就是说，幼稚的无锁实现在很多时候看起来很合理并且行为正确，而实际上却很不安全。虽然牢牢掌握原则很重要，但我强烈建议使用现有的、易于理解和经过验证的实现，而不是滚动自己的实现。

    关于c++ - 制作 C++ 哈希表的最佳策略，线程安全，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/7086267/

    amp43br的sectionc++thread-safetyhashtable

    有关c++ - 制作 C++ 哈希表的最佳策略，线程安全的更多相关文章

    1. ruby-on-rails - 使用 Ruby on Rails 进行自动化测试 - 最佳实践 - 2

      很好奇，就使用ruby​​onrails自动化单元测试而言，你们正在做什么？您是否创建了一个脚本来在cron中运行rake作业并将结果邮寄给您？git中的预提交Hook？只是手动调用？我完全理解测试，但想知道在错误发生之前捕获错误的最佳实践是什么。让我们理所当然地认为测试本身是完美无缺的，并且可以正常工作。下一步是什么以确保他们在正确的时间将可能有害的结果传达给您？ 最佳答案 不确定您到底想听什么，但是有几个级别的自动代码库控制:在处理某项功能时，您可以使用类似autotest的内容获得关于哪些有效，哪些无效的即时反馈。要确保您的提

    2. ruby - 解析 RDFa、微数据等的最佳方式是什么，使用统一的模式/词汇(例如 schema.org)存储和显示信息 - 2

      我主要使用Ruby来执行此操作，但到目前为止我的攻击计划如下:使用gemsrdf、rdf-rdfa和rdf-microdata或mida来解析给定任何URI的数据。我认为最好映射到像schema.org这样的统一模式，例如使用这个yaml文件，它试图描述数据词汇表和opengraph到schema.org之间的转换:#SchemaXtoschema.orgconversion#data-vocabularyDV:name:namestreet-address:streetAddressregion:addressRegionlocality:addressLocalityphoto:i

    3. ruby-on-rails - 如何优雅地重启 thin + nginx？ - 2

      我的瘦服务器配置了nginx，我的ROR应用程序正在它们上运行。在我发布代码更新时运行thinrestart会给我的应用程序带来一些停机时间。我试图弄清楚如何优雅地重启正在运行的Thin实例，但找不到好的解决方案。有没有人能做到这一点？ 最佳答案 #Restartjustthethinserverdescribedbythatconfigsudothin-C/etc/thin/mysite.ymlrestartNginx将继续运行并代理请求。如果您将Nginx设置为使用多个上游服务器，例如server{listen80;server

    4. ruby - 如何使用 Ruby aws/s3 Gem 生成安全 URL 以从 s3 下载文件 - 2

      我正在编写一个小脚本来定位aws存储桶中的特定文件，并创建一个临时验证的url以发送给同事。(理想情况下，这将创建类似于在控制台上右键单击存储桶中的文件并复制链接地址的结果)。我研究过回形针，它似乎不符合这个标准，但我可能只是不知道它的全部功能。我尝试了以下方法:defauthenticated_url(file_name,bucket)AWS::S3::S3Object.url_for(file_name,bucket,:secure=>true,:expires=>20*60)end产生这种类型的结果:...-1.amazonaws.com/file_path/file.zip.A

    5. ruby - 如果指定键的值在数组中相同，如何合并哈希 - 2

      我有一个这样的哈希数组:[{:foo=>2,:date=>Sat,01Sep2014},{:foo2=>2,:date=>Sat,02Sep2014},{:foo3=>3,:date=>Sat,01Sep2014},{:foo4=>4,:date=>Sat,03Sep2014},{:foo5=>5,:date=>Sat,02Sep2014}]如果:date相同，我想合并哈希值。我对上面数组的期望是:[{:foo=>2,:foo3=>3,:date=>Sat,01Sep2014},{:foo2=>2,:foo5=>5:date=>Sat,02Sep2014},{:foo4=>4,:dat

    6. ruby - RuntimeError(自动加载常量 Apps 多线程时检测到循环依赖 - 2

      我收到这个错误:RuntimeError(自动加载常量Apps时检测到循环依赖当我使用多线程时。下面是我的代码。为什么会这样？我尝试多线程的原因是因为我正在编写一个HTML抓取应用程序。对Nokogiri::HTML(open())的调用是一个同步阻塞调用，需要1秒才能返回，我有100,000多个页面要访问，所以我试图运行多个线程来解决这个问题。有更好的方法吗？classToolsController0)app.website=array.join(',')putsapp.websiteelseapp.website="NONE"endapp.saveapps=Apps.order("

    7. ruby - 如何在 Grape 中定义哈希数组？ - 2

      我使用Ember作为我的前端和GrapeAPI来为我的API提供服务。前端发送类似:{"service"=>{"name"=>"Name","duration"=>"30","user"=>nil,"organization"=>"org","category"=>nil,"description"=>"description","disabled"=>true,"color"=>nil,"availabilities"=>[{"day"=>"Saturday","enabled"=>false,"timeSlots"=>[{"startAt"=>"09:00AM","endAt"=>

    8. ruby - 如何安全地删除文件？ - 2

      在Ruby中是否有Gem或安全删除文件的方法？我想避免系统上可能不存在的外部程序。“安全删除”指的是覆盖文件内容。 最佳答案 如果您使用的是*nix，一个很好的方法是使用exec/open3/open4调用shred:`shred-fxuz#{filename}`http://www.gnu.org/s/coreutils/manual/html_node/shred-invocation.html检查这个类似的帖子:Writingafileshredderinpythonorruby?

    9. ruby - 在哈希的键数组中追加元素 - 2

      查看我的Ruby代码:h=Hash.new([])h[0]=:word1h[1]=h[1]输出是:Hash={0=>:word1,1=>[:word2,:word3],2=>[:word2,:word3]}我希望有Hash={0=>:word1,1=>[:word2],2=>[:word3]}为什么要附加第二个哈希元素(数组)？如何将新数组元素附加到第三个哈希元素？ 最佳答案 如果您提供单个值作为Hash.new的参数(例如Hash.new([])，完全相同的对象将用作每个缺失键的默认值。这就是您所拥有的，那是你不想要的。您可以改用

    10. ruby - 使用 `+=` 和 `send` 方法 - 2

      如何将send与+=一起使用？a=20;a.send"+=",10undefinedmethod`+='for20:Fixnuma=20;a+=10=>30 最佳答案 恐怕你不能。+=不是方法，而是语法糖。参见http://www.ruby-doc.org/docs/ProgrammingRuby/html/tut_expressions.html它说Incommonwithmanyotherlanguages,Rubyhasasyntacticshortcut:a=a+2maybewrittenasa+=2.你能做的最好的事情是:

    随机推荐