検索

[转]NoSQL数据库的分布式算法

Jun 07, 2016 pm 05:56 PM
nosql配布されたデータベースアルゴリズム

[转]NoSQL数据库的分布式算法 转载一篇很不错的NoSQL数据库分布式算法,内容如下: 本文英文原文发表于知名技术博客《Highly Scalable Blog》,对NoSQL数据库中的 分布式 算法和思想进行了详细的讲解。文章很长,由@juliashine进行翻译投稿。感谢译者的共享

[转]NoSQL数据库的分布式算法

转载一篇很不错的NoSQL数据库分布式算法,内容如下: 

本文英文原文发表于知名技术博客《Highly Scalable Blog》,对NoSQL数据库中的分布式算法和思想进行了详细的讲解。文章很长,由@juliashine 进行翻译投稿。感谢译者的共享精神!

译者介绍:Juliashine是多年抓娃工程师,现工作方向是海量数据处理与分析,关注Hadoop与NoSQL生态体系。

英文原文:《Distributed Algorithms in NoSQL Databases》

译文地址:《NoSQL数据库的分布式算法》

系统的可扩展性是推动NoSQL运动发展的的主要理由,包含了分布式系统协调,故障转移,资源管理和许多其他特性。这么讲使得NoSQL听起来像是一个大筐,什么都能塞进去。尽管NoSQL运动并没有给分布式数据处理带来根本性的技术变革,但是依然引发了铺天盖地的关于各种协议和算法的研究以及实践。正是通过这些尝试逐渐总结出了一些行之有效的数据库构建方法。在这篇文章里,香港服务器租用,我将针对NoSQL数据库的分布式特点进行一些系统化的描述。

接下来我们将研究一些分布式策略,比如故障检测中的复制,这些策略用黑体字标出,被分为三段:

数据一致性

众所周知,分布式系统经常会遇到网络隔离或是延迟的情况,在这种情况下隔离的部分是不可用的,因此要保持高可用性而不牺牲一致性是不可能的。这一事实通常被称作“CAP理论”。然而,一致性在分布式系统中是一个非常昂贵的东西,所以经常需要在这上面做一些让步,不只是针对可用性,还有多种权衡。为了研究这些权衡,我们注意到分布式系统的一致性问题是由数据隔离和复制引起的,免备案空间,所以我们将从研究复制的特点开始:

现在让我们仔细看看常用的复制技术,并按照描述的特点给他们分一下类。第一幅图描绘了不同技术之间的逻辑关系和不同技术在系统的一致性、扩展性、可用性、延迟性之间的权衡坐标。 第二张图详细描绘了每个技术。

复本因子是4。读写协调者可以是一个外部客户端或是一个内部代理节点。

我们会依据一致性从弱到强把所有的技术过一遍:

上面分析中的一些权衡有必要再强调一下:

反熵协议, 谣言传播算法

让我们从以下场景开始:

有许多节点,每条数据会在其中的若干的节点上面存有副本。每个节点都可以单独处理更新请求,每个节点定期和其他节点同步状态,如此一段时间之后所有的副本都会趋向一致。同步过程是怎样进行的?同步何时开始?怎样选择同步的对象?怎么交换数据?我们假定两个节点总是用较新版本的数据覆盖旧的数据或者两个版本都保留以待应用层处理。

这个问题常见于数据一致性维护和集群状态同步(如集群成员信息传播)等场景。虽然引入一个监控数据库并制定同步计划的协调者可以解决这个问题,但是去中心化的数据库能够提供更好的容错性。去中心化的主要做法是利用精心设计的传染协议[7],这种协议相对简单,但是提供了很好的收敛时间,而且能够容忍任何节点的失效和网络隔离。尽管有许多类型的传染算法,虚拟主机,我们只关注反熵协议,因为NoSQL数据库都在使用它。

反熵协议假定同步会按照一个固定进度表执行,每个节点定期随机或是按照某种规则选择另外一个节点交换数据,消除差异。有三种反风格的反熵协议:推,拉和混合。推协议的原理是简单选取一个随机节点然后把数据状态发送过去。在真实应用中将全部数据都推送出去显然是愚蠢的,所以节点一般按照下图所示的方式工作。

节点A作为同步发起者准备好一份数据摘要,里面包含了A上数据的指纹。节点B接收到摘要之后将摘要中的数据与本地数据进行比较,并将数据差异做成一份摘要返回给A。最后,A发送一个更新给B,B再更新数据。拉方式和混合方式的协议与此类似,就如上图所示的。

反熵协议提供了足够好的收敛时间和扩展性。下图展示了一个在100个节点的集群中传播一个更新的模拟结果。在每次迭代中,每个节点只与一个随机选取的对等节点发生联系。

可以看到,拉方式的收敛性比推方式更好,这可以从理论上得到证明[7]。而且推方式还存在一个“收敛尾巴”的问题。在多次迭代之后,尽管几乎遍历到了所有的节点,但还是有很少的一部分没受到影响。与单纯的推和拉方式相比, 混合方式的效率更高,所以实际应用中通常使用这种方式。反熵是可扩展的,因为平均转换时间以集群规模的对数函数形式增长。

尽管这些技术看起来很简单,仍然有许多研究关注于不同约束条件下反熵协议的性能表现。其中之一通过一种更有效的结构使用网络拓扑来取代随机选取 [10] 。在网络带宽有限的条件下调整传输率或使用先进的规则来选取要同步的数据 [9]。摘要计算也面临挑战,数据库会维护一份最近更新的日志以有助于摘要计算。

最终一致数据类型Eventually Consistent Data Types

在上一节我们假定两个节点总是合并他们的数据版本。但要解决更新冲突并不容易,让所有副本都最终达到一个语义上正确的值出乎意料的难。一个众所周知的例子是Amazon Dynamo数据库[8]中已经删除的条目可以重现。

我们假设一个例子来说明这个问题:数据库维护一个逻辑上的全局计数器,每个节点可以增加或者减少计数。虽然每个节点可以在本地维护一个自己的值,但这些本地计数却不能通过简单的加减来合并。假设这样一个例子:有三个节点A、B和C,每个节点执行了一次加操作。如果A从B获得一个值,并且加到本地副本上,然后C从B获得值,然后C再从A获得值,那么C最后的值是4,而这是错误的。解决这个问题的方法是用一个类似于向量时钟[19]的数据结构为每个节点维护一对计数器[1]:

class Counter { int[] plus int[] minus int NODE_ID increment() { plus[NODE_ID]++ } decrement() { minus[NODE_ID]++ } get() { return sum(plus) – sum(minus) } merge(Counter other) { for i in 1..MAX_ID { plus[i] = max(plus[i], other.plus[i]) minus[i] = max(minus[i], other.minus[i]) } } }

Cassandra用类似的方法计数[11]。利用基于状态的或是基于操作的复制理论也可以设计出更复杂的最终一致的数据结构。例如,[1]中就提及了一系列这样的数据结构,包括:

最终一致数据类型的功能通常是有限的,还会带来额外的性能开销。

数据放置

这部分主要关注控制在分布式数据库中放置数据的算法。这些算法负责把数据项映射到合适的物理节点上,在节点间迁移数据以及像内存这样的资源的全局调配。

均衡数据
声明
この記事の内容はネチズンが自主的に寄稿したものであり、著作権は原著者に帰属します。このサイトは、それに相当する法的責任を負いません。盗作または侵害の疑いのあるコンテンツを見つけた場合は、admin@php.cn までご連絡ください。
MySQL:世界で最も人気のあるデータベースの紹介MySQL:世界で最も人気のあるデータベースの紹介Apr 12, 2025 am 12:18 AM

MySQLはオープンソースのリレーショナルデータベース管理システムであり、主にデータを迅速かつ確実に保存および取得するために使用されます。その実用的な原則には、クライアントリクエスト、クエリ解像度、クエリの実行、返品結果が含まれます。使用法の例には、テーブルの作成、データの挿入とクエリ、および参加操作などの高度な機能が含まれます。一般的なエラーには、SQL構文、データ型、およびアクセス許可、および最適化の提案には、インデックスの使用、最適化されたクエリ、およびテーブルの分割が含まれます。

MySQLの重要性:データストレージと管理MySQLの重要性:データストレージと管理Apr 12, 2025 am 12:18 AM

MySQLは、データストレージ、管理、クエリ、セキュリティに適したオープンソースのリレーショナルデータベース管理システムです。 1.さまざまなオペレーティングシステムをサポートし、Webアプリケーションやその他のフィールドで広く使用されています。 2。クライアントサーバーアーキテクチャとさまざまなストレージエンジンを通じて、MySQLはデータを効率的に処理します。 3.基本的な使用には、データベースとテーブルの作成、挿入、クエリ、データの更新が含まれます。 4.高度な使用には、複雑なクエリとストアドプロシージャが含まれます。 5.一般的なエラーは、説明ステートメントを介してデバッグできます。 6.パフォーマンスの最適化には、インデックスの合理的な使用と最適化されたクエリステートメントが含まれます。

なぜMySQLを使用するのですか?利点と利点なぜMySQLを使用するのですか?利点と利点Apr 12, 2025 am 12:17 AM

MySQLは、そのパフォーマンス、信頼性、使いやすさ、コミュニティサポートに選択されています。 1.MYSQLは、複数のデータ型と高度なクエリ操作をサポートし、効率的なデータストレージおよび検索機能を提供します。 2.クライアントサーバーアーキテクチャと複数のストレージエンジンを採用して、トランザクションとクエリの最適化をサポートします。 3.使いやすく、さまざまなオペレーティングシステムとプログラミング言語をサポートしています。 4.強力なコミュニティサポートを提供し、豊富なリソースとソリューションを提供します。

InnoDBロックメカニズム(共有ロック、排他的ロック、意図ロック、レコードロック、ギャップロック、次のキーロック)を説明します。InnoDBロックメカニズム(共有ロック、排他的ロック、意図ロック、レコードロック、ギャップロック、次のキーロック)を説明します。Apr 12, 2025 am 12:16 AM

INNODBのロックメカニズムには、共有ロック、排他的ロック、意図ロック、レコードロック、ギャップロック、次のキーロックが含まれます。 1.共有ロックにより、トランザクションは他のトランザクションが読み取らないようにデータを読み取ることができます。 2.排他的ロックは、他のトランザクションがデータの読み取りと変更を防ぎます。 3.意図ロックは、ロック効率を最適化します。 4。ロックロックインデックスのレコードを記録します。 5。ギャップロックロックインデックス記録ギャップ。 6.次のキーロックは、データの一貫性を確保するためのレコードロックとギャップロックの組み合わせです。

貧弱なMySQLクエリパフォーマンスの一般的な原因は何ですか?貧弱なMySQLクエリパフォーマンスの一般的な原因は何ですか?Apr 12, 2025 am 12:11 AM

MySQLクエリのパフォーマンスが低いことの主な理由には、インデックスの使用、クエリオプティマイザーによる誤った実行計画の選択、不合理なテーブルデザイン、過剰なデータボリューム、ロック競争などがあります。 1.インデックスがゆっくりとクエリを引き起こし、インデックスを追加するとパフォーマンスが大幅に向上する可能性があります。 2。説明コマンドを使用してクエリ計画を分析し、オプティマイザーエラーを見つけます。 3.テーブル構造の再構築と結合条件を最適化すると、テーブルの設計上の問題が改善されます。 4.データボリュームが大きい場合、パーティション化とテーブル分割戦略が採用されます。 5.高い並行性環境では、トランザクションの最適化とロック戦略は、ロック競争を減らすことができます。

複数の単一列インデックスに対して複合インデックスをいつ使用する必要がありますか?複数の単一列インデックスに対して複合インデックスをいつ使用する必要がありますか?Apr 11, 2025 am 12:06 AM

データベースの最適化では、クエリ要件に従ってインデックス作成戦略を選択する必要があります。1。クエリに複数の列が含まれ、条件の順序が固定されている場合、複合インデックスを使用します。 2。クエリに複数の列が含まれているが、条件の順序が修正されていない場合、複数の単一列インデックスを使用します。複合インデックスは、マルチコラムクエリの最適化に適していますが、単一列インデックスは単一列クエリに適しています。

MySQLでスロークエリを識別して最適化する方法は? (スロークエリログ、Performance_schema)MySQLでスロークエリを識別して最適化する方法は? (スロークエリログ、Performance_schema)Apr 10, 2025 am 09:36 AM

MySQLスロークエリを最適化するには、slowquerylogとperformance_schemaを使用する必要があります。1。LowerQueryLogを有効にし、しきい値を設定して、スロークエリを記録します。 2。performance_schemaを使用してクエリの実行の詳細を分析し、パフォーマンスのボトルネックを見つけて最適化します。

MySQLおよびSQL:開発者にとって不可欠なスキルMySQLおよびSQL:開発者にとって不可欠なスキルApr 10, 2025 am 09:30 AM

MySQLとSQLは、開発者にとって不可欠なスキルです。 1.MYSQLはオープンソースのリレーショナルデータベース管理システムであり、SQLはデータベースの管理と操作に使用される標準言語です。 2.MYSQLは、効率的なデータストレージと検索機能を介して複数のストレージエンジンをサポートし、SQLは簡単なステートメントを通じて複雑なデータ操作を完了します。 3.使用の例には、条件によるフィルタリングやソートなどの基本的なクエリと高度なクエリが含まれます。 4.一般的なエラーには、SQLステートメントをチェックして説明コマンドを使用することで最適化できる構文エラーとパフォーマンスの問題が含まれます。 5.パフォーマンス最適化手法には、インデックスの使用、フルテーブルスキャンの回避、参加操作の最適化、コードの読み取り可能性の向上が含まれます。

See all articles

ホットAIツール

Undresser.AI Undress

Undresser.AI Undress

リアルなヌード写真を作成する AI 搭載アプリ

AI Clothes Remover

AI Clothes Remover

写真から衣服を削除するオンライン AI ツール。

Undress AI Tool

Undress AI Tool

脱衣画像を無料で

Clothoff.io

Clothoff.io

AI衣類リムーバー

AI Hentai Generator

AI Hentai Generator

AIヘンタイを無料で生成します。

ホットツール

SublimeText3 Linux 新バージョン

SublimeText3 Linux 新バージョン

SublimeText3 Linux 最新バージョン

mPDF

mPDF

mPDF は、UTF-8 でエンコードされた HTML から PDF ファイルを生成できる PHP ライブラリです。オリジナルの作者である Ian Back は、Web サイトから「オンザフライ」で PDF ファイルを出力し、さまざまな言語を処理するために mPDF を作成しました。 HTML2FPDF などのオリジナルのスクリプトよりも遅く、Unicode フォントを使用すると生成されるファイルが大きくなりますが、CSS スタイルなどをサポートし、多くの機能強化が施されています。 RTL (アラビア語とヘブライ語) や CJK (中国語、日本語、韓国語) を含むほぼすべての言語をサポートします。ネストされたブロックレベル要素 (P、DIV など) をサポートします。

AtomエディタMac版ダウンロード

AtomエディタMac版ダウンロード

最も人気のあるオープンソースエディター

DVWA

DVWA

Damn Vulnerable Web App (DVWA) は、非常に脆弱な PHP/MySQL Web アプリケーションです。その主な目的は、セキュリティ専門家が法的環境でスキルとツールをテストするのに役立ち、Web 開発者が Web アプリケーションを保護するプロセスをより深く理解できるようにし、教師/生徒が教室環境で Web アプリケーションを教え/学習できるようにすることです。安全。 DVWA の目標は、シンプルでわかりやすいインターフェイスを通じて、さまざまな難易度で最も一般的な Web 脆弱性のいくつかを実践することです。このソフトウェアは、

VSCode Windows 64 ビットのダウンロード

VSCode Windows 64 ビットのダウンロード

Microsoft によって発売された無料で強力な IDE エディター