delete

密碼裡面不能有 SELECT/INSERT/UPDATE/DELETE/DROP

這是在 Hacker News 上看到的：「Password may not contain: select, insert, update, delete, drop (uni-lj.si)」，原網站在「Password reset - ID portal」，熱鬧的地方在於原作者 (或是外包商？) 也在 Hacker News 上面回應...

禁止密碼裡面有某些字元還蠻常見的，但這次看到的很有趣 (然後被貼到 Hacker News 上)：

Your password must also not contain the following character combinations: script, select, insert, update, delete, drop, --, ', /*, */.

從網域及英文版的介面可以查到這是盧比安納大學的系統，作者 (或是外包) 在 id=39079030 提到了這是上面的要求：

Oooh! I put that string there! It was a request by management, and I still don't know why. This site doesn't store any passwords, it's basically just a nice interface to external account management.

I heard a rumour that some legacy apps have weird validation on their login fields, so students wouldn't be able to log in with passwords containing certain strings. But I don't actually know of any examples.

就... 很好玩？

比 Bloom filter 與 Cuckoo filter 再更進一步的 Xor filter

Bloom filter 算是教科書上的經典演算法之一，在實際應用上有更好的選擇，像是先前提到的 Cuckoo filter：「Cuckoo Filter：比 Bloom Filter 多了 Delete」。

現在又有人提出新的資料結構，號稱又比 Bloom filter 與 Cuckoo filter 好：「Xor Filters: Faster and Smaller Than Bloom Filters」。

不過並不是完全超越，其中馬上可以看到的差異就是不支援 delete：

Deletions are generally unsafe with these filters even in principle because they track hash values and cannot deal with collisions without access to the object data: if you have two objects mapping to the same hash value, and you have a filter on hash values, it is going to be difficult to delete one without the other.

論文的預印本可以在 arXiv 上下載：「Xor Filters: Faster and Smaller Than Bloom and Cuckoo Filters」。

在 SQL 裡面避免大量刪除資料的方式

看到 Percona 的「An Overview of Sharding in PostgreSQL and How it Relates to MongoDB’s」這篇，雖然是在講 PostgreSQL 上的 sharding (以及 partition)，突然想到好像沒寫過要怎麼避免大量刪除資料的操作...

一個常見的情境是，想要讓某個表格只保留這一個月的資料，所以每個月開頭都會跑一隻 cron job 負責刪掉上個月的資料，像是 DELETE FROM xxx WHERE timestamp < yyy; 這樣的指令。

這個方式無論是在 PostgreSQL 或是 MySQL 都需要很多時間與 I/O 資源，而透過 partition 將不同時間區段切開到不同的表格，再用 TRUNCATE 直接清空表格剛好可以解這樣的問題。

Percona 的文章裡說了一些 PostgreSQL 的歷史與目前的進展。

在 PostgreSQL 9 或更早以前的版本，一個常見的作法是透過 table inheritance 實做 partition，然後用再用 function 實做 INSERT：

CREATE TABLE temperature (
  id BIGSERIAL PRIMARY KEY NOT NULL,
  city_id INT NOT NULL,
  timestamp TIMESTAMP NOT NULL,
  temp DECIMAL(5,2) NOT NULL
);

CREATE TABLE temperature_201901 (CHECK (timestamp >= DATE '2019-01-01' AND timestamp <= DATE '2019-01-31')) INHERITS (temperature);
CREATE TABLE temperature_201902 (CHECK (timestamp >= DATE '2019-02-01' AND timestamp <= DATE '2019-02-28')) INHERITS (temperature);
CREATE TABLE temperature_201903 (CHECK (timestamp >= DATE '2019-03-01' AND timestamp <= DATE '2019-03-31')) INHERITS (temperature);

CREATE OR REPLACE FUNCTION temperature_insert_trigger()
RETURNS TRIGGER AS $$
BEGIN
    IF ( NEW.timestamp >= DATE '2019-01-01' AND NEW.timestamp <= DATE '2019-01-31' ) THEN INSERT INTO temperature_201901 VALUES (NEW.*);
    ELSIF ( NEW.timestamp >= DATE '2019-02-01' AND NEW.timestamp <= DATE '2019-02-28' ) THEN INSERT INTO temperature_201902 VALUES (NEW.*);
    ELSIF ( NEW.timestamp >= DATE '2019-03-01' AND NEW.timestamp <= DATE '2019-03-31' ) THEN INSERT INTO temperature_201903 VALUES (NEW.*);
    ELSE RAISE EXCEPTION 'Date out of range!';
    END IF;
    RETURN NULL;
END;
$$
LANGUAGE plpgsql;

在 PostgreSQL 10 之後，就直接支援一些與 partition 相關的設計，像是這樣：

CREATE TABLE temperature (
  id BIGSERIAL NOT NULL,
  city_id INT NOT NULL,
  timestamp TIMESTAMP NOT NULL,
  temp DECIMAL(5,2) NOT NULL
) PARTITION BY RANGE (timestamp);

CREATE TABLE temperature_201901 PARTITION OF temperature FOR VALUES FROM ('2019-01-01') TO ('2019-02-01');
CREATE TABLE temperature_201902 PARTITION OF temperature FOR VALUES FROM ('2019-02-01') TO ('2019-03-01');
CREATE TABLE temperature_201903 PARTITION OF temperature FOR VALUES FROM ('2019-03-01') TO ('2019-04-01');

雖然還是有些限制，但可以看出比起以前簡單不少。

而有了 partition 後，文章的後續就在討論這跟 MongoDB 的 sharding 有什麼關係，但這就不是我關注的事情了...

EnterpriseDB 打算推出的 zheap，想要解 VACUUM 問題...

前天被問到「DO or UNDO - there is no VACUUM」這篇，回家後仔細看一看再翻了一些資料，看起來是要往 InnoDB 的解法靠...

PostgreSQL 與 InnoDB 都是透過 MVCC 的概念實做 transaction 之間的互動，但兩者實際的作法不太一樣。其中帶來一個明顯的差異就是 PostgreSQL 需要 VACUUM。這點在同一篇作者八年前 (2011) 的文章就有提過兩者的差異以及優缺點：「MySQL vs. PostgreSQL, Part 2: VACUUM vs. Purge」。

當 UPDATE 時，InnoDB 會把新資料寫到表格內，然後把可能會被 rollback 的舊資料放到表格外：

In InnoDB, only the most recent version of an updated row is retained in the table itself. Old versions of updated rows are moved to the rollback segment, while deleted row versions are left in place and marked for future cleanup. Thus, purge must get rid of any deleted rows from the table itself, and clear out any old versions of updated rows from the rollback segment.

而被 DELETE 清除的資料則是由 purge thread 處理：

All the information necessary to find the deleted records that might need to be purged is also written to the rollback segment, so it's quite easy to find the rows that need to be cleaned out; and the old versions of the updated records are all in the rollback segment itself, so those are easy to find, too.

所以可以在 InnoDB 看到 purge thread 相關的設定：「MySQL :: MySQL 5.7 Reference Manual :: 14.6.11 Configuring InnoDB Purge Scheduling」，負責處理這些東西。

而在 PostgreSQL 的作法則是反過來，舊的資料放在原來地方，新資料另外存：

PostgreSQL takes a completely different approach. There is no rollback tablespace, or anything similar. When a row is updated, the old version is left in place; the new version is simply written into the table along with it.

新舊資料的位置其實還好，主要是因為沒有類似的地方可以記錄哪些要清：

Lacking a centralized record of what must be purged, PostgreSQL's VACUUM has historically needed to scan the entire table to look for records that might require cleanup.

這也使得 PostgreSQL 裡需要 autovacuum 之類的程序去掃，或是手動跑 vacuum。而在去年 (2017) 的文章裡也有提到目前還是類似的情況：「MVCC and VACUUM」。

而在今年 (2018) 的文章裡，EnterpriseDB 就提出了 zheap 的想法，在 UPDATE 時寫到 table 裡，把可能被 rollback 的資料放到 undo log 裡。其實就是把 InnoDB 那套方法拿過來用，只是整篇都沒提到而已 XD：

That brings me to the design which EnterpriseDB is proposing. We are working to build a new table storage format for PostgreSQL, which we’re calling zheap. In a zheap, whenever possible, we handle an UPDATE by moving the old row version to an undo log, and putting the new row version in the place previously occupied by the old one. If the transaction aborts, we retrieve the old row version from undo and put it back in the original location; if a concurrent transaction needs to see the old row version, it can find it in undo. Of course, this doesn’t work when the block is full and the row is getting wider, and there are some other problem cases as well, but it covers many useful cases. In the typical case, therefore, even bulk updates do not force a zheap to grow. Instead, the undo grows. When a transaction commits, all row versions that will become dead are in the undo, not the zheap.

不過馬上就會想到問題，如果要改善問題，不是個找地方記錄哪些位置要回收就好了嗎？順便改變方法是為了避免 fragment 嗎？

等著看之後變成什麼樣子吧...

DynamoDB 推出 TTL 功能

DynamoDB 推出了依照時間自動刪除的功能：「New – Manage DynamoDB Items Using Time to Live (TTL)」。

You can enable this feature on a table-by-table basis, specifying an item attribute that contains the expiration time for the item.

這個功能比較特別的是，刪除的 scan 是不收取費用的：

There is no charge for the internal scan operation or for the deletion. You will pay for storage until the item is actually deleted.

Cuckoo Filter：比 Bloom Filter 多了 Delete

在「Cuckoo Filter implementation in Go, better than Bloom Filters」這邊看到這個資料結構，有興趣的人也可以看「Cuckoo Filter：设计与实现」這篇介紹，下面是我抓重點整理。

Bloom Filter 支援的操作：

Add(element)
Query(element)

1970 年提出來的資料結構。優點是空間複雜度是 O(1)，Query(element) 會有可接受的 false positive，缺點是不支援 Delete(element)、以及數量變多時誤判率的增加。

Cuckoo Filter 多了一組操作：

Delete(element)

2014 年提出來的資料結構。空間複雜度一樣是 O(1)，但相同的空間用量下 false positive 變低，然後支援 Delete(element) 了。也因此論文直接寫「Cuckoo Filter: Practically Better Than Bloom」，表示可以直接替代。

用 Go 發展的 groupcache...

groupcache 是 Brad Fitzpatrick 最新的作品 (之前最有名的兩個作品是 memcached 與 OpenID 1)，目標在於取代一部分 memcached 的功能。

以官方的說明是：

groupcache is a caching and cache-filling library, intended as a replacement for memcached in many cases.

另外一篇介紹文是「Playing With Groupcache」。

跟 memcached 差異最大的地方在於「沒有更改與刪除的功能」，一旦寫進去後就不會變動。在放棄 update/delete 的特性後，換來的是：

Cluster 的能力。
處理熱點的能力。

以往在 memcached server 之間是沒有交集的，在 groupcache 則是 cluster 起來。另外以前在 memcached 會因為同時存取同一個 key 而造成 single CPU overloading 的問題，在 groupcache 則透過 auto-mirror 機制解決。

不過還是得想一下要怎麼用，畢竟沒有 update/delete 功能...

把 MySQL MyISAM 換到 Galera Cluster 的 InnoDB 上...

在「Switching from MySQL/MyISAM to Galera Cluster」這邊看到一個 script 可以檢查 MySQL MyISAM 換到 InnoDB，而且預定要換成 Galera Cluster 時的問題。

常見的問題都有檢查到，還蠻有用的：

針對沒有 Primary Key 的表格提出警告，讓管理者規劃補上 Primary Key。
針對 MyISAM 換成 InnoDB 後造成 Primary Key 太長的表格提出警告，讓管理者想辦法修改。

Galera Cluster 無法處理沒有 Primary Key 表格的刪除動作：(可以參考「MariaDB Galera Cluster - Known Limitations」這邊的說明)

DELETE operation is unsupported on tables without primary key. Also rows in tables without primary key may appear in different order on different nodes. Don't use tables without primary key.

不過每個表格都要有 Primary Key 並不難，因為如果有正規化時通常都會達到目標。就算不去用他也還是可以設計一個 INT UNSIGNED PRIMARY KEY AUTO_INCREMENT 放著。(過大的時候再換成 BIGINT UNSIGNED)

在 mutt 裡刪除重複的信件

因為 mailing list 之類的東西我還是習慣在 mutt 裡讀 (操作起來比較快)，而有時候會把 -announce 與 -users 都丟到同一個檔案裡，所以偶而會在一個檔案裡面有同時寄到多個 mailing list 而重複的信件...

之前是看到的時候就手動砍掉，不過用 Google 找了一下，發現早就有方法可以做了：「Tip: Remove Duplicate Emails with Mutt」。

變化一下就是用 D 然後輸入 ~=，當離開這個信件檔時就會刪除這些重複的信件。等下再來研究要怎麼樣在切換信件檔時自動執行這個命令...