2014-07-03

今更だが、RedisのSlaveのExpireは信用してはいけない

また、障害起因でのブログです。忘れないようにこちらにメモります。

http://trapezoid.hatenablog.com/entry/2013/02/10/035020

にも詳しくかいてあります。

とあるreplication をくんでいるRedisの系統があった。Replication をくんではいるものの、とある事情により Slaveには参照していなかったが、突如 Masterのロードがあがったので Slave に負荷分散する必要が生まれ、あれ？大丈夫だっけ？とある事情ってなんだっけ？ってなったのでそのとある事情についてまとめます。

Slave の expireは信用できない。

結論だけ述べると、 MASTER に以下のようなコマンドうち

SETEX foo 3 1 #key Fooに3秒のexpireで1というvalueをset

10秒後にSlaveにGetコマンドをうつと、本来は Expireしてるので、空がかえってくる事をきたいしそうですが、本来 Expireしてるデータがかえってしまう可能性が多分にあります。

GET foo  #nilを期待するけど、1がかえってくる可能性有り

どうしてこのような事がおきるのでしょうか以下想像と事実の混合ですが。。

前提として Redis の replication は http://redis.io/topics/replication の下記の記述にあるとおり、コマンドベースの Replication をとってる模様です

The master then starts background saving, and starts to buffer all new commands received that will modify the dataset. When the background saving is complete, the master transfers the database file to the slave, which saves it on disk, and then loads it into memory. The master will then send to the slave all buffered commands. This is done as a stream of commands and is in the same format of the Redis protocol itself.

コマンドには、いわゆる冪等性みたいな概念は全くないのでこのような戦略をとる場合は Master でそのコマンドが実行された時の状態と Slave でコマンドが実行されたときの状態を完全に一致させないとデータの不整合がうまれてしまうという問題があります。

先ほどの例で考えましょう

まず、MASTERに以下のようなコマンドがながれたとします

SETEX foo 3 1 # Master から replicationされたコマンド
# 2秒経過
EXPIRE  foo 3 # fooのExpireが延長された
# 2秒経過
INCR foo 1  # Valueが 2 になる

さて、ここで最初のSETEXのコマンドの後にMasterとSlaveの間のReplicationが2秒間遅延した場合にSlaveからはどのようにみえるのだろうか？

SETEX foo 3 1 # Master から replicationされたコマンド
# Master側では2秒経過 してるが、Replicationが2秒遅延してるので 4秒経過してる
EXPIRE  foo 3
# 2秒経過
INCR foo 1

本来、MASTERではSETEXの2秒後にEXPIREがのばされたようにみえるがSLAVEではSETEXの4秒後にEXPIREがのばされたように見えます。

このような状態でSLAVE側で、よしなにExpireしようとするとどのような事がおきるでしょうか？

SETEX foo 3 1 # Master から replicationされたコマンド
# Slave側で3.5秒経過
GET foo  # fooはSETEXから3秒経ってるな。よーしExpireだ
# Master側では2秒経過 したあとにうたれたコマンドが Replicationが2秒遅延してるので 4秒経過してる
EXPIRE  foo 3 # もう fooはexpireしてるよーん
# 2秒経過 
INCR foo 1  # fooはnilだぜ

みたいな感じで不整合が生まれてしまいます。実際には、Masterの時刻を含めてreplicateしてもらい、Slave側で Expires at判定する場合は、自分のサーバーの時刻からみた経過時間ではなく Masterからreplicateされてきてる時間で経過時間をみるみたいな事をすればもう少しうまくいくようになるかもしれませんが、Redisはコマンドいっぱいあるので、様々なコマンドの事をかんがえるとそんなにシンプルではないかもしれません。ちなみに、Redisはこれを非常にシンプルな方法で解決してます。

Slave側ではデータはPurgeしない。Masterでデータの PurgeのReplicationをまつ

order to obtain a correct behavior without sacrificing consistency, when a key expires, a DEL operation is synthesized in both the AOF file and gains all the attached slaves. This way the expiration process is centralized in the master instance, and there is no chance of consistency errors. However while the slaves connected to a master will not expire keys independently (but will wait for the DEL coming from the master), they'll still take the full state of the expires existing in the dataset, so when a slave is elected to a master it will be able to expire the keys independently, fully acting as a master.

これだけです。じゃあ、MasterっていつデータをExpireするの？となると以下のようになります

http://redis.io/commands/expire

How Redis expires keys Redis keys are expired in two ways: a passive way, and an active way. A key is actively expired simply when some client tries to access it, and the key is found to be timed out. Of course this is not enough as there are expired keys that will never be accessed again. This keys should be expired anyway, so periodically Redis test a few keys at random among keys with an expire set. All the keys that are already expired are deleted from the keyspace. Specifically this is what Redis does 10 times per second: Test 100 random keys from the set of keys with an associated expire. Delete all the keys found expired. If more than 25 keys were expired, start again from step 1. This is a trivial probabilistic algorithm, basically the assumption is that our sample is representative of the whole key space, and we continue to expire until the percentage of keys that are likely to be expired is under 25% This means that at any given moment the maximum amount of keys already expired that are using memory is at max equal to max amount of write operations per second divided by 4.

MasterにGetしたタイミングで明示的に確認する以外は、わりとadhocです。expireされたデータが残ってる可能性は十分にあります。以上のような理由により SlaveのGet時にはExpireは信用できないのです。

じゃあどうするかというと、expires_at みたいな値をvalueにつっこんでおいてアプリケーション側でexpire判定ロジックをすればokです。また、以上のような理由があったとしてもMasterのexpireは設定しておいた方がいいです。そうしないとRedisがデータをPurgeしてくれないので、無駄にデータが増える事になります。以上のような理由で、RedisのexpireとSlaveを運用する場合は、データ量をいい感じにへらしてもらうためにExpireをつけるくらいのイメージのほうがよし。

間違ってたり、もっといいアイディアあれば教えてください

2014-05-16

Why I want to stop using range partition with timestamp column

Partition 周りで社内で説明する事が有ったのでせっかくなのでブログをかきます。注.) 僕自身はMySQLにさほど詳しくはないので、完全には鵜呑みにしない事をおすすめしますが

下記のようなテーブルがあったとします

CREATE TABLE messages (
  id int unsigned NOT NULL,
  user_id int unsigned NOT NULL,
  content varchar(255) NOT NULL DEFAULT '',
  created_at int unsigned NOT NULL  
  PRIMARY KEY (id),
  KEY `on_user_id` (user_id)
) Engine=InnoDB DEFAULT CHARSET=utf8;

データ量が多かったりして、3ヶ月以前のデータをPurgeするとか考えだすとdeleteは重いので、めんどいです。

ここで非常に強力なのが Partitioningです。もし3ヶ月以前のデータはPurgeしてよいのであれば、上記テーブルは TimestampでPartitioningするというテーブル設計がよくとられがちです。具体的には

CREATE TABLE messages (
  id int unsigned NOT NULL,
  user_id int unsigned NOT NULL,
  content varchar(255) NOT NULL DEFAULT '',
  created_at int unsigned NOT NULL  
  PRIMARY KEY (id, created_at),
  KEY `on_user_id` (user_id)
) Engine=InnoDB DEFAULT CHARSET=utf8
/*!50100 PARTITION BY RANGE (created_at)
(PARTITION p201403170000 VALUES LESS THAN (1394996400) ENGINE = InnoDB,
 PARTITION p201403170400 VALUES LESS THAN (1395010800) ENGINE = InnoDB,
 ## 以下略

created_at が PK になっているのは、Partition の対象のカラムは MySQL 的に PK ないしは UNIQUE KEY に含まれてないといけないからです。

このようにする事で

一定期間以前のデータを削除したいときは Drop partitionすれば良い。Drop partitionはDrop tableのようなものなので、高速である
Partition 単位のindexは小さくなるので、データを最新順にとってくるような特定の Partition にアクセスが集中する処理は非常に高速である

といいことがたくさんあります。特に Purge がらくちんなのは大変便利で Partitionがないと生きていけないみたいな感覚によくなります。Purgeには色々負荷を押さえるための魔術が必要なケースが多く、最初に使い始めたときはこんなに楽なのか。今まで僕のPurgeの努力はなんだったのかと感動しました。

ただし、上記の設計には一つ大きな弱点があります

以下のような Query を投げる事を想定しましょう

SELECT * FROM messages
WHERE created_at < NOW()  # Partition pruningのため
ORDER BY id DESC 
LIMIT 10

これ、本来は最新のPartition から順に探索していけばいいのですが、 id と created_at の順序は同一であるという事をMySQL さんは知らないのでどうしても全ての Partition を見に行かなくてはいけず、非常に効率がわるいのです。そして、おそらくですが MySQL は全てのPartition をなめたあとに id による Merge Sort をしようとするような実装になっていると思います(勝手な想像)。

この問題に関しては、以下のようなIndexを追加する事で Indexは多少無駄になるものの、Partition pruning を聞かせる事が可能です。

ALTER TABLE messages add KEY `on_created_at` (created_at)

SELECT * FROM messages
WHERE created_at < NOW()  # Partition pruningのため
ORDER BY created_at DESC, id DESC 
LIMIT 10

ただ、これだけのためであればこのIndex 無駄ですよね。コードも複雑になりますし非常にいけてないです。また、これでは解決できない問題もあります。以下のような Query です

SELECT * FROM messages
WHERE id IN (1, 10, 100)

これも Partition pruning がきかないので、MySQLさんは全ての Partition に検索をかけにいきます。partitionが30個あったら30個のテーブルに SELECT なげるようなものです。これは一応一定の改善策があります

SELECT * FROM messages
WHERE id IN (1, 10, 100)
AND created_at >= @CRETEAED_AT_OF_ID_1 AND created_at >= @CREATED_AT_OF_ID_100
LIMIT 10

もし、各id の created_at がわかってる場合は、それらの中で最小のcreated_atと最大のcreated_at で範囲をしぼることができます。ただ、すごく古いデータとすごく新しいデータに同時にアクセスしようとすると結局効率は改善されません。

そもそもです。そもそもは id が PKなわけです。PK による ORDER BY とかにそんなにがんばりたくありません。 pk が id なのに PRIMARY KEY に created_at をいれるとかもなんか黒魔術的な感じがしていやです。黒魔術を使うとだいたいどっかでしわ寄せがくるものですし、現実的に発生してしまっています。

全てを解決する方法が有ります。id でRange Partition すればいいのです。みんな、そんな事はわかってるのですが、3ヶ月以前のデータを簡単に捨てたいんだとか思うとPartition 管理が多少めんどうになるので、二の足を踏みがちなのかなと勝手に想像しています。

でもid でrange partitionしつつ、一定時間よりも古いデータをPurgeするみたいな処理はそんなに難しくはないですね。

例として

Partitionがかわるタイミングで Batch処理でシーケンスを発行して各partitionの最も最新のcreated_at のmappingを作っておく、DROP 際はそのmappingを参照する
各Partition の最新のデータを取得して、そのpartitionの最新のcreated_atを判定し、一定期間よりも古いデータだった場合はPartition dropする

このような管理にしておけば上記のようなperformance周りの問題は全てなくなり、かつコードも簡単になり、みんなハッピーです。

もちろん自動でPartition を追加するロジックとかも必要で、こういった事は timestamp based partition よりもめんどうなのですが管理ツールは一回だけつくればいいですし、idでrange partition するべきと思います

2013-10-11

Insert ignore into、Select For Update とシュレディンガーの猫

Repeatable Read とシュレディンガーの猫

Repeatable Read のポリシーはシュレディンガーの猫と似ていると思う。つまり、状態が観測されたらそのTransactionで、それは決定事項になるという事である。

シュレディンガーの猫 http://ja.wikipedia.org/wiki/%E3%82%B7%E3%83%A5%E3%83%AC%E3%83%BC%E3%83%87%E3%82%A3%E3%83%B3%E3%82%AC%E3%83%BC%E3%81%AE%E7%8C%AB

シュレディンガーの猫的には以下である。

箱の中身を観測するまでは猫が生きているかいきていないかは決定してなく、どちらの状態もとりうる
箱の中身を観測した時点において、猫がいきている状態なのか死んでいる状態なのか確定する

これを Repeatable Read におきかえると以下のようになる

Transactionないで特定のレコード(猫)の状態を観測するまではそのレコード(猫)はどんな値もとりうる
Transactionないでなんらかの方法でレコード(猫)の状態を観測したタイミングでレコード(猫)の値が決定される(もちろん更新系の処理をしないとならないけど)。排他/共有LockがとられるのでほかのTransactionからは変更不可能になる)

http://dev.mysql.com/doc/refman/5.1/en/innodb-lock-modes.html

Insert Ignore Into , Select for Updateの違い。

この状態が観測されたらというのがわりとみそで、INSERT IGNORE INTOでレコードが存在したとき、UPDATE (SELECT FOR UPDATE)でレコードが存在しなく時もそれぞれ以下のような状態が確定するので共有Lock相当のLockがとられるという事をわすれがちです。

存在するレコードに対するINSERT IGNORE INTO : レコードが存在する事が確定、ほかのTransactionからDELETEされないようにロックとる
存在しないレコードに対するUPDATE。レコードが存在しない事が確定、ほかのTransactionからINSERTされないようにロックとる

例えば、以下のようなテーブルがあったとします。

CREATE TABLE `friend_counts` (
  `user_id` int(10) unsigned NOT NULL,
  `count` int(10) unsigned NOT NULL,
  PRIMARY KEY (`user_id`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8

このテーブルに対して、レコードがある場合は、countの値をIncrement、なかったら初期データーをつっこむということをしたいとします。

下記がSelect for updateで行うパターンです。

sub increment_friend_count {
  my $user_id = shift;
  my $dbh = _get_dbh;

  my ($affected_row) = $dbh->selectrow_array('UPDATE friend_counts SET count = count + 1 WHERE user_id = ?', undef, $user_id);

  unless ($affected_row) {
    $dbh->do('INSERT INTO friend_counts (user_id, friend_num) values(?, 1)', undef, $user_id);
  }
  $dbh->commit;
}

下記がInsert ignore intoで行うパターンです

sub increment_friend_count {
  my $user_id = shift;
  my $dbh = _get_dbh;

  my $affected_row =  $dbh->do('INSERT IGNORE INTO friend_counts (user_id, count) values(?, 1)', undef, $user_id);
  unless ($affected_row) {
    $dbh->do('UPDATE friend_count set count = count+1 WHERE user_id = ?', undef, $user_id);
  }
  $dhh->commit;
}

これ、ちなみにどちらも問題があります。まず、前者に関しては、UPDATEがからぶった場合、そのレコードに対する共有Lockをとります。ちなみにMYSQLはIndex TreeでLockするので、存在しないレコードに対するlockはGap Lockで実現されます。なので、レコードが存在しない状態でこのコードが同時に二つのセッションから実行されると、UPDATEの部分で同時にGap Lock (共有Lock) が取得され、その後のInsertでDeadlockします。

INSERT IGNORE INTOも同様に INSERT IGNORE INTOが失敗した時点(affected_rowsが0)の時点でそのレコードが存在している事が確定します。ほかのTransactionからのDELETEを許したりすると、TRANSACTIONないでそのレコードが存在する事を担保できないので、INSERTが失敗したレコードに対して共有LOCKが取得されます。この場合、レコードが有る状態で同時に二つのSessionから実行されると Deadlockします。

これ、どちらも同じように感じますが、以下の問題設定では大きく異なります。

大きいサービスでRequestがすごい頻度でくる
新しく機能をリリースしたタイミングでテーブルにレコードがあまりうまっていない。

なぜなら、前者のSELECT FOR UPDATEを先に行うバージョンはGAP LOCKなので、Index Treeでその両端にあるレコードまでLockします。極端な話、テーブルが空っぽの状態ではテーブルLockと等しい状態になります。

一方、後者のINSERT IGNORE INTOから先に行うパターンはRowに対する共有Lockでしかないので、影響範囲が限定されます。

空っぽのテーブルに対して、同時に別のユーザーidでこのパターンを実行する以下のサンプルがわかりやすいです。

セッションA

mysql> start transaction;
Query OK, 0 rows affected (0.00 sec)

mysql> UPDATE friend_counts set count = count + 1 where user_id = 1000;
Query OK, 0 rows affected (0.00 sec)
Rows matched: 0  Changed: 0  Warnings: 0

セッションB

mysql> start transaction;
Query OK, 0 rows affected (0.00 sec)

mysql> UPDATE friend_counts SET count = count + 1 where user_id = 2000;
Query OK, 0 rows affected (0.00 sec)
Rows matched: 0  Changed: 0  Warnings: 0

mysql> INSERT INTO friend_counts (user_id, count) VALUES(2000,1);
ERROR 1205 (HY000): Lock wait timeout exceeded; try restarting transaction

一方 Insert ignore intoだとこれはもちろん、成功します。

セッションA

mysql> start transaction;
Query OK, 0 rows affected (0.00 sec)

mysql> INSERT IGNORE INTO user_friend_counts (user_id, count) VALUES(1000,1);
Query OK, 0 rows affected (0.00 sec)

セッションB

mysql> start transaction;
Query OK, 0 rows affected (0.00 sec)

mysql> INSERT IGNORE INTO friend_counts (user_id, count) VALUES(2000,1);
Query OK, 0 rows affected (0.00 sec)

mysql> UPDATE friend_counts SET count = count + 1 where user_id = 2000;
Query OK, 1 row affected (0.01 sec)
Rows matched: 1  Changed: 1  Warnings: 0

なので、サービスリリース直後はINSERT IGNORE INTOの方がよいかなーと思った次第。

maedamaのブログ

アプリケーションエンジニアです。最近は主に設計を担当しています。

今更だが、RedisのSlaveのExpireは信用してはいけない

Slave の expireは信用できない。

Slave側ではデータはPurgeしない。Masterでデータの PurgeのReplicationをまつ

Why I want to stop using range partition with timestamp column

Insert ignore into、Select For Update とシュレディンガーの猫

Repeatable Read とシュレディンガーの猫

Insert Ignore Into , Select for Updateの違い。

Slave の expireは信用できない。

Slave側ではデータはPurgeしない。Masterで データの PurgeのReplicationをまつ

Repeatable Read と シュレディンガーの猫

Insert Ignore Into , Select for Updateの違い。

Slave側ではデータはPurgeしない。Masterでデータの PurgeのReplicationをまつ

Repeatable Read とシュレディンガーの猫