ぶんぷがたロック実装原理
まず、一般的なロックの種類を振り返ってみましょう.
1スピンロック
スピンロックが他のスレッドによって取得された場合、呼び出し者は、スピンロックの保持者がロックを解放したかどうかを確認するためにループし続け、「スピン」という言葉がそのために名付けられた.スピンロックは非ブロックロックであり、すなわち、あるスレッドがスピンロックを取得する必要があるが、そのロックが他のスレッドに占有されている場合、スレッドは掛けられず、CPUを消費する時間がかかり続け、スピンロックを取得しようとする.
2反発ロック(Mutex Lock)反発ロックはブロックロックであり、私たちが最もよく使うロックでもあります.あるスレッドが反発ロックを取得できない場合、このスレッドは直接掛けられ、CPU時間を消費しません.他のスレッドが反発ロックを解放すると、オペレーティングシステムはその掛けられたスレッドを呼び覚ますことができます.ブロッキングロックは、スレッドをブロッキング状態にして待機させ、対応する信号(起動、時間)を取得すると、スレッドの準備完了状態に入ることができ、準備完了状態のすべてのスレッドを準備し、競争を通じて運転状態に入ることができると言える.その利点は,ブロックされたスレッドがCPU時間を占有せず,CPU占有率が高すぎることはないが,スピンロックよりも進入時間および回復時間がやや遅いことである.競合が激しい場合、ブロッキングロックの性能はスピンロックよりも明らかに高い.上記の2つのロックは、マルチコアプロセッサの場合、スレッドがロックを待機する時間が短く、スレッドの2回のコンテキスト切替時間よりも短い場合、スピンロックを使用するとお得です.マルチコアプロセッサの場合、スレッドがロックを待つ時間が長いと予想される場合は、少なくとも2回のスレッドコンテキストの切り替えよりも長い場合は、反発ロックを使用することをお勧めします.シングルコアプロセッサの場合は、スピンロックは使用しないことが一般的です.同じ時間に1つのスレッドだけが実行状態にあるため、実行スレッドがロックを取得できないことに気づいたら、ロック解除を待つしかないが、自身が掛けないため、そのロックを取得したスレッドは実行状態に入ることができず、実行スレッドがシステムに割り当てられたタイムスライスを使い切るまで待つしかない.この場合,スピンロックを用いるコストが高い.ロックされたコードが頻繁に呼び出されるが、競合が少ない場合は、スピンロックの使用を優先すべきであり、スピンロックのオーバーヘッドは比較的小さく、反発量のオーバーヘッドが大きい.
3 Reentrant Lockは、デッドロックを発生させることなく、同じスレッドで複数回取得できる特殊な反発ロックです.まず、反発ロックです.任意の時点で、スレッドロックが1つしかありません.すなわち,Aスレッドがロックを取得したと仮定し,Aスレッドがこのロックを解放するまでBスレッドはこのロックを取得できず,Bがこのロックを取得するとブロック状態になる.次に、同じスレッドで複数回保持できます.すなわち、Aスレッドがこのロックを取得したと仮定し、Aスレッドがロックを解除する前に再びこのロックの取得を要求すれば、成功することができる.
他にも珍しいもの、偏向ロック、重量級ロックなどがあります.https://www.cnblogs.com/charlesblc/p/5994162.htmlああ、これらのロックはjavaで実現されたロックのはずですが、アマチュアのjava開発者としてはちょっと寡聞ですね.ここにリンクを書きましょう.
2分散ロックとは
分散ロックは、分散システム間の共有リソースへの同期アクセスを制御する方法です.分散システムでは、動作を調整する必要があることが多い.異なるシステムまたは同じシステムの異なるホスト間で1つまたは複数のリソースが共有されている場合、これらのリソースにアクセスする際には、互いに干渉しないように反発して一貫性を保証する必要があり、この場合、分散ロックを使用する必要があります.
分散ロックの本質は特殊な一般ロックと見なすことができ、その競合者は普通のプロセスとスレッドではなく、その競合者は異なるホストに分布し、ネットワークを通じて相互に通信する必要があり、異なるホストの分布とネットワークの不確実性は分散ロックの実現と普通のロックに大きな違いを与えている.
現在一般的な分散ロックの実装には、データベースベース、キャッシュベース、zonkeeperベースの3つがあります.https://www.cnblogs.com/austinspark-jessylu/p/8043726.htmlああ、ここではredisで簡単に実現します.
redisに基づいて分散ロックを実現するのは簡単で、1つのコマンドsetnx(set if no exist)を通過する.keyが存在しない場合にのみsetが1を返すことに成功し、そうでなければ失敗0を返すが、意外な状況を考慮するには厳密な論理が必要である.
注意:これはredisを使用して分散ロックを実現する基本原理にすぎません.この実装は単一のredisにのみ適用され、それ自体にいくつかの欠点があります.
ロックのタイムアウトの問題:
クライアント1はロックを取得しました.クライアント1は共有リソースにアクセスします.クライアント1は、ロックを解除するために、「GET」操作を実行してランダム文字列の値を取得する.クライアント1は、ランダム文字列の値を判断し、予想される値と等しい.クライアント1は、何らかの理由で長い間ブロックされていた.期限が切れたので、ロックが自動的に解放されました.クライアント2は、同じリソースに対応するロックを取得する.クライアント1は、ブロックから復帰し、DEL操作を行い、クライアント2が保持するロックを解除する.
セカンダリコピー
クライアント1はMasterからロックを取得する.Masterがダウンし、ストレージロックのkeyがSlaveに同期できない.SlaveはMasterにアップグレードされた.クライアント2は、同じリソースに対応するロックを新しいMasterから取得する.
上記の問題を解決するために、redlockというアルゴリズムが公式に与えられ、clientは現在の時間(ミリ秒数)を取得してN個のRedisノードに順次取得ロックの操作を実行する.この取得操作は、ランダム文字列my_を含む前の単一Redisノードに基づく取得ロックの処理と同様であるrandom_valueは、有効期限(例えばPX 30000、すなわちロックの有効時間)も含む.あるRedisノードが使用できないときにアルゴリズムが実行されることを保証するために、このロックを取得する操作には、ロックの有効時間(数十ミリ秒レベル)よりもはるかに小さいタイムアウト時間(time out)がある.クライアントは、あるRedisノードへのロックの取得に失敗した後、すぐに次のRedisノードを試行する必要があります.ここでの失敗には、Redisノードが使用できない場合や、Redisノードのロックが他のクライアントによって保持されている場合など、任意のタイプの失敗が含まれるべきです(注:Redlock原文では、Redisノードが使用できない場合のみが記載されていますが、他の失敗も含まれるべきです).ロックを取得するプロセス全体にどれくらいの時間がかかったかを計算します.計算方法は、現在の時間からステップ1のレコードを減算する時間です.クライアントがほとんどのRedisノード(>=N/2+1)からロックを正常に取得し、ロックを取得するのに消費される時間がロックの有効時間を超えていない場合、クライアントは最終的にロックを取得したと判断する.そうでなければ、最終的にロックの取得に失敗したと考えられます.最終的にロックの取得に成功した場合、このロックの有効時間は、最初のロックの有効時間から3ステップ目に計算されたロックの取得に消費された時間を減算することに等しい再計算されるべきである.最終的にロックの取得に失敗した場合(ロックを取得したRedisノードの個数がN/2+1未満であるか、またはロックの取得プロセス全体で消費された時間がロックの最初の有効時間を超えている可能性がある)、クライアントは直ちにすべてのRedisノードにロックの解除操作(すなわち、前述のRedis Luaスクリプト)を開始するべきである.
しかし、このようにして私に与えられた感じは効率が低すぎて、redisノードがますます多くなると、ロックの消費がますます大きくなり、このような実現には依然として欠点があり、Martin Kleppmannの観点を引用して、彼のロックの用途の区別を引用します.彼は鍵の用途を2つに分けた.
1効率性(efficiency)のために、各クライアントを調整して重複作業を避ける.ロックがたまに失効しても、いくつかの操作をもう一度行う可能性があるだけで、他の不良結果は発生しません.例えば同じメールを繰り返し送信しました.2正確性のために(correctness).ロックが無効になることは、発生すると、データの不一致(inconsistency)、データの損失、ファイルの破損、またはその他の深刻な問題を意味する可能性があるため、いかなる場合でも許可されません.最後に、Martinは、効率のために分散ロックを使用し、ロックの偶発的な失効を許容する場合、単一Redisノードを使用するロックスキームで十分であり、簡単で効率的であると結論した.Redlockは過重な実装である.正確性(correctness)のために厳粛な場合に分散ロックを使用する場合は、Redlockは使用しないでください.非同期モデルに構築された十分なアルゴリズムではなく,システムモデルの仮定に多くの危険成分(timing)が含まれている.さらに、fencing tokenを提供するメカニズムはありません.では、どんな技術を使うべきですか.Martin氏は、Zookeeperのようなシナリオや、トランザクションをサポートするデータベースを考慮すべきだと考えています.
次の2つの文章を詳しく見てみましょう.
Redisベースの分散ロックはいったい安全ですか(上)?
Redisベースの分散ロックはいったい安全ですか(下)?
1スピンロック
スピンロックが他のスレッドによって取得された場合、呼び出し者は、スピンロックの保持者がロックを解放したかどうかを確認するためにループし続け、「スピン」という言葉がそのために名付けられた.スピンロックは非ブロックロックであり、すなわち、あるスレッドがスピンロックを取得する必要があるが、そのロックが他のスレッドに占有されている場合、スレッドは掛けられず、CPUを消費する時間がかかり続け、スピンロックを取得しようとする.
2反発ロック(Mutex Lock)反発ロックはブロックロックであり、私たちが最もよく使うロックでもあります.あるスレッドが反発ロックを取得できない場合、このスレッドは直接掛けられ、CPU時間を消費しません.他のスレッドが反発ロックを解放すると、オペレーティングシステムはその掛けられたスレッドを呼び覚ますことができます.ブロッキングロックは、スレッドをブロッキング状態にして待機させ、対応する信号(起動、時間)を取得すると、スレッドの準備完了状態に入ることができ、準備完了状態のすべてのスレッドを準備し、競争を通じて運転状態に入ることができると言える.その利点は,ブロックされたスレッドがCPU時間を占有せず,CPU占有率が高すぎることはないが,スピンロックよりも進入時間および回復時間がやや遅いことである.競合が激しい場合、ブロッキングロックの性能はスピンロックよりも明らかに高い.上記の2つのロックは、マルチコアプロセッサの場合、スレッドがロックを待機する時間が短く、スレッドの2回のコンテキスト切替時間よりも短い場合、スピンロックを使用するとお得です.マルチコアプロセッサの場合、スレッドがロックを待つ時間が長いと予想される場合は、少なくとも2回のスレッドコンテキストの切り替えよりも長い場合は、反発ロックを使用することをお勧めします.シングルコアプロセッサの場合は、スピンロックは使用しないことが一般的です.同じ時間に1つのスレッドだけが実行状態にあるため、実行スレッドがロックを取得できないことに気づいたら、ロック解除を待つしかないが、自身が掛けないため、そのロックを取得したスレッドは実行状態に入ることができず、実行スレッドがシステムに割り当てられたタイムスライスを使い切るまで待つしかない.この場合,スピンロックを用いるコストが高い.ロックされたコードが頻繁に呼び出されるが、競合が少ない場合は、スピンロックの使用を優先すべきであり、スピンロックのオーバーヘッドは比較的小さく、反発量のオーバーヘッドが大きい.
3 Reentrant Lockは、デッドロックを発生させることなく、同じスレッドで複数回取得できる特殊な反発ロックです.まず、反発ロックです.任意の時点で、スレッドロックが1つしかありません.すなわち,Aスレッドがロックを取得したと仮定し,Aスレッドがこのロックを解放するまでBスレッドはこのロックを取得できず,Bがこのロックを取得するとブロック状態になる.次に、同じスレッドで複数回保持できます.すなわち、Aスレッドがこのロックを取得したと仮定し、Aスレッドがロックを解除する前に再びこのロックの取得を要求すれば、成功することができる.
他にも珍しいもの、偏向ロック、重量級ロックなどがあります.https://www.cnblogs.com/charlesblc/p/5994162.htmlああ、これらのロックはjavaで実現されたロックのはずですが、アマチュアのjava開発者としてはちょっと寡聞ですね.ここにリンクを書きましょう.
2分散ロックとは
分散ロックは、分散システム間の共有リソースへの同期アクセスを制御する方法です.分散システムでは、動作を調整する必要があることが多い.異なるシステムまたは同じシステムの異なるホスト間で1つまたは複数のリソースが共有されている場合、これらのリソースにアクセスする際には、互いに干渉しないように反発して一貫性を保証する必要があり、この場合、分散ロックを使用する必要があります.
分散ロックの本質は特殊な一般ロックと見なすことができ、その競合者は普通のプロセスとスレッドではなく、その競合者は異なるホストに分布し、ネットワークを通じて相互に通信する必要があり、異なるホストの分布とネットワークの不確実性は分散ロックの実現と普通のロックに大きな違いを与えている.
現在一般的な分散ロックの実装には、データベースベース、キャッシュベース、zonkeeperベースの3つがあります.https://www.cnblogs.com/austinspark-jessylu/p/8043726.htmlああ、ここではredisで簡単に実現します.
redisに基づいて分散ロックを実現するのは簡単で、1つのコマンドsetnx(set if no exist)を通過する.keyが存在しない場合にのみsetが1を返すことに成功し、そうでなければ失敗0を返すが、意外な状況を考慮するには厳密な論理が必要である.
//
// Created by dguco on 18-9-9.
//
#ifndef SERVER_REDI_LOCK_H
#define SERVER_REDI_LOCK_H
#include
#include
#include
using namespace std;
//
int GetSecond()
{
struct timeval tmval = {0};
int nRetCode = gettimeofday(&tmval, NULL);
if (nRetCode != 0) {
return 0;
}
return (int) (tmval.tv_sec);
}
#define LOCK_TIME_OUT 1 //1s
CRedisClient g_RedisCli;
class CRedisLock
{
public:
/**
*
* @param lockKey
* @param isBlock
* @return
*/
bool Lock(std::string &lockKey, bool isBlock = false);
template
void DoWithLock(std::string &lockKey, F &&f, Args &&... args);
template
void TryDoWithLock(std::string &lockKey, F &&f, Args &&... args);
private:
int m_iLockTimeOut;
};
template
void CRedisLock::TryDoWithLock(std::string &lockKey, F &&f, Args &&... args)
{
bool isLock = Lock(lockKey, false);
if (isLock) {
using return_type = typename std::result_of::type;
auto task = std::make_shared<:packaged_task> >(
std::bind(std::forward(f), std::forward(args)...)
);
(*task)( );
int now = GetSecond( );
if (now < m_iLockTimeOut) {
g_RedisCli.Del(lockKey);
}
}
}
template
inline void CRedisLock::DoWithLock(std::string &lockKey, F &&f, Args &&... args)
{
bool isLock = Lock(lockKey, true);
if (isLock) {
using return_type = typename std::result_of::type;
auto task = std::make_shared<:packaged_task> >(
std::bind(std::forward(f), std::forward(args)...)
);
(*task)( );
int now = GetSecond( );
if (now < m_iLockTimeOut) {
g_RedisCli.Del(lockKey);
}
}
}
bool CRedisLock::Lock(std::string &lockKey, bool isBlock)
{
int lock = 0;
m_iLockTimeOut = 0;
bool isLock = false;
while (lock != 1) {
int now = GetSecond( );
m_iLockTimeOut = now + LOCK_TIME_OUT + 1;
lock = g_RedisCli.Setnx(lockKey, to_string(m_iLockTimeOut));
//
if (lock == 1) {
isLock = true;
}
// ，
if (!isLock) {
string res = "";
g_RedisCli.Get(lockKey, &res);
//
if (res != "") {
int out1 = atoi(res.c_str( ));
string res1 = "";
g_RedisCli.Getset(lockKey, &res1);
//
if (now > out1 && res == res1) {
isLock = true;
}
}
}
if (isLock or !isBlock) {
break;
}
else {
usleep(1000);
}
}
return isLock;
}
#endif //SERVER_REDI_LOCK_H
string key = "test";
string lockKey = "Lock.test";
string key1 = "test1";
CRedisLock redisLock;
int main()
{
// testDlopen();
// testSoHotLoad();
// listenFileChange();
if (!g_RedisCli.Initialize("127.0.0.1", 6379, 2, 1)) {
std::cout << "connect to redis failed" << std::endl;
return -1;
}
redisLock.DoWithLock(lockKey, [key]
{
string res;
g_RedisCli.Get(key,&res);
int a = atoi(res.c_str());
a++;
g_RedisCli.Set(key, to_string(a));
});
std::cout << "Over" << std::endl;
};注意:これはredisを使用して分散ロックを実現する基本原理にすぎません.この実装は単一のredisにのみ適用され、それ自体にいくつかの欠点があります.
ロックのタイムアウトの問題:
クライアント1はロックを取得しました.クライアント1は共有リソースにアクセスします.クライアント1は、ロックを解除するために、「GET」操作を実行してランダム文字列の値を取得する.クライアント1は、ランダム文字列の値を判断し、予想される値と等しい.クライアント1は、何らかの理由で長い間ブロックされていた.期限が切れたので、ロックが自動的に解放されました.クライアント2は、同じリソースに対応するロックを取得する.クライアント1は、ブロックから復帰し、DEL操作を行い、クライアント2が保持するロックを解除する.
セカンダリコピー
クライアント1はMasterからロックを取得する.Masterがダウンし、ストレージロックのkeyがSlaveに同期できない.SlaveはMasterにアップグレードされた.クライアント2は、同じリソースに対応するロックを新しいMasterから取得する.
上記の問題を解決するために、redlockというアルゴリズムが公式に与えられ、clientは現在の時間(ミリ秒数)を取得してN個のRedisノードに順次取得ロックの操作を実行する.この取得操作は、ランダム文字列my_を含む前の単一Redisノードに基づく取得ロックの処理と同様であるrandom_valueは、有効期限(例えばPX 30000、すなわちロックの有効時間)も含む.あるRedisノードが使用できないときにアルゴリズムが実行されることを保証するために、このロックを取得する操作には、ロックの有効時間(数十ミリ秒レベル)よりもはるかに小さいタイムアウト時間(time out)がある.クライアントは、あるRedisノードへのロックの取得に失敗した後、すぐに次のRedisノードを試行する必要があります.ここでの失敗には、Redisノードが使用できない場合や、Redisノードのロックが他のクライアントによって保持されている場合など、任意のタイプの失敗が含まれるべきです(注:Redlock原文では、Redisノードが使用できない場合のみが記載されていますが、他の失敗も含まれるべきです).ロックを取得するプロセス全体にどれくらいの時間がかかったかを計算します.計算方法は、現在の時間からステップ1のレコードを減算する時間です.クライアントがほとんどのRedisノード(>=N/2+1)からロックを正常に取得し、ロックを取得するのに消費される時間がロックの有効時間を超えていない場合、クライアントは最終的にロックを取得したと判断する.そうでなければ、最終的にロックの取得に失敗したと考えられます.最終的にロックの取得に成功した場合、このロックの有効時間は、最初のロックの有効時間から3ステップ目に計算されたロックの取得に消費された時間を減算することに等しい再計算されるべきである.最終的にロックの取得に失敗した場合(ロックを取得したRedisノードの個数がN/2+1未満であるか、またはロックの取得プロセス全体で消費された時間がロックの最初の有効時間を超えている可能性がある)、クライアントは直ちにすべてのRedisノードにロックの解除操作(すなわち、前述のRedis Luaスクリプト)を開始するべきである.
しかし、このようにして私に与えられた感じは効率が低すぎて、redisノードがますます多くなると、ロックの消費がますます大きくなり、このような実現には依然として欠点があり、Martin Kleppmannの観点を引用して、彼のロックの用途の区別を引用します.彼は鍵の用途を2つに分けた.
1効率性(efficiency)のために、各クライアントを調整して重複作業を避ける.ロックがたまに失効しても、いくつかの操作をもう一度行う可能性があるだけで、他の不良結果は発生しません.例えば同じメールを繰り返し送信しました.2正確性のために(correctness).ロックが無効になることは、発生すると、データの不一致(inconsistency)、データの損失、ファイルの破損、またはその他の深刻な問題を意味する可能性があるため、いかなる場合でも許可されません.最後に、Martinは、効率のために分散ロックを使用し、ロックの偶発的な失効を許容する場合、単一Redisノードを使用するロックスキームで十分であり、簡単で効率的であると結論した.Redlockは過重な実装である.正確性(correctness)のために厳粛な場合に分散ロックを使用する場合は、Redlockは使用しないでください.非同期モデルに構築された十分なアルゴリズムではなく,システムモデルの仮定に多くの危険成分(timing)が含まれている.さらに、fencing tokenを提供するメカニズムはありません.では、どんな技術を使うべきですか.Martin氏は、Zookeeperのようなシナリオや、トランザクションをサポートするデータベースを考慮すべきだと考えています.
次の2つの文章を詳しく見てみましょう.
Redisベースの分散ロックはいったい安全ですか(上)?
Redisベースの分散ロックはいったい安全ですか(下)?