Google 發表計算網頁真實性的演算法 (Knowledge-Based Trust)

Slashdot 上看到 Google 發表了計算網頁真實性的演算法,Knowledge-Based Trust (KBT):「Google Wants To Rank Websites Based On Facts Not Links」,原始的論文 PDF 檔案可以在「Knowledge-Based Trust: Estimating the Trustworthiness of Web Sources」這邊取得。

論文本身的原理不難懂 (其實方法相當有趣),主要是給出了三個貢獻。

首先是能夠區分是取出資訊的方法有問題 (extract 的演算法不夠好),或是網站本身就給出錯誤的資訊:

Our main contribution is a more sophisticated probabilistic model, which can distinguish between two main sources of error: incorrect facts on a page, and incorrect extractions made by an extraction system.

第二個則是在效能上的改善:

Our second contribution is a new method to adaptively decide the granularity of sources to work with: if a specific webpage yields too few triples, we may aggregate it with other webpages from the same website. Conversely, if a website has too many triples, we may split it into smaller ones, to avoid computational bottlenecks (Section 4).

第三個則是提出好的分散式演算法,可以螞蟻雄兵計算出來:

The third contribution of this paper is a detailed, large-scale evaluation of the performance of our model.

KBT 並不是要取代 PageRank,而是跟 PageRank 互相配合,可以有效打擊內容農場 (Content farm) 這類網站,畢竟 PageRank 的假設在一般的狀況下是有邏輯的。

在「High PageRank but low KBT (top-left corner)」這段講到了這件事情:

We consider the 15 gossip websites listed in [16]. Among them, 14 have a PageRank among top 15% of the websites, since such websites are often popular. However, for all of them the KBT are in the bottom 50%; in other words, they are considered less trustworthy than half of the websites. Another kind of websites that often get low KBT are forum websites.

再找時間細讀其他類似的演算法...

innodb_file_per_table 對於 CREATE TABLE 與 DROP TABLE 的速度

雖然平常應該不會常常用到 CREATE TABLEDROP TABLE,不過還是很有趣的 benchmark:「Is MySQL’s innodb_file_per_table slowing you down?」。

重點在這段:

  • With innodb_file_per_table=ON
    • Schema and table creation = 1m54.852s
    • Schema drops = 1m21.682s
  • With innodb_file_per_table=OFF
  • Schema and table creation = 0m59.968s
  • Schema drops = 0m54.870s

不過作者測試時沒有用 ENGINE=COMPRESSED (必須在 innodb_file_per_table 打開時才支援,而且這也是選擇打開 innodb_file_per_table 的重要因素),不知道壓縮開起來以後會差多少...

不過就算再怎麼慢,相較於 CREATE TABLEDROP TABLE 的效能,還是比較計較壓縮換來的 I/O 效能。(尤其是資料量超過記憶體大小時)

Windows 10 的 IE 將會有 asm.js 支援

Twitter 上看到的:「Bringing asm.js to the Chakra JavaScript engine in Windows 10」。

這樣只剩下 Safari 還沒支援,其他幾個主流瀏覽器都支援了:(出自維基百科「asm.js」條目)

Mozilla Firefox was the first web browser to implement asm.js-specific optimizations, starting with Firefox 22. The optimizations of Google Chrome's V8 JavaScript engine in Chrome 28 made asm.js benchmarks more than twice as fast as prior versions of Chrome.

MySQL InnoDB 遇到 Deadlock 時的判讀

Percona 的「How to deal with MySQL deadlocks」這篇文章裡面提到了 MySQL InnoDB Deadlock 的判讀與處理。

在支援 transaction 的 engine 裡 deadlock 是不可避免的常態。

在 MySQL 5.5 以及之前的版本,可以透過 Percona 的 pt-deadlock-logger 這隻 script,每固定幾秒鐘就跑一次 SHOW ENGINE INNODB STATUS 記錄下來。在 MySQL 5.6 之後,可以直接使用 innodb_print_all_deadlocks 這個參數,遇到 deadlock 時就寫到 error log 裡。

有了 log 後,接下來就可以判讀 deadlock 的情況,得知是什麼樣的情況造成 deadlock。

文章最後面則是對減少 deadlock 的方法給了一些建議,都是比較一般性。一般還是要靠 bussiness logic 的分析來切割降低 deadlock 的情況。

不過這篇文章需要一些背景知識,像是 InnoDB Lock Modes 與維基百科上的「Multiple granularity locking」,對解讀會有更多幫助。

修正 Mac OS X Yosemite (10.10) 的設定以確保隱私

Hacker New Daily 上看到的:「Fix Mac OS X Yosemite」。原因是 Spotlight 的部份 AppleBing 合作:

If you've upgraded to Mac OS X Yosemite (10.10) and you're using the default settings, each time you start typing in Spotlight (to open an application or search for a file on your computer), your local search terms and location are sent to Apple and third parties (including Microsoft).

有兩個地方要關閉。一個是系統設定,一個是 Safari 設定,細節在原文裡面有,這邊就不抄過來了。

Netflix 不僅使用 AWS,還使用了 GCE...

在「Cloud guru Adrian Cockcroft on Netflix, Amazon, Google, and DigitalOcean」這篇裡面提到 Netflix 現在不僅使用 AWS,還使用了 GCE

The company’s services are now all hosted in the public cloud, but not just in AWS. Netflix is also using Google Compute Engine.

不算是很意外... 畢竟有那個 scale 與實力。

Google Searchbot 將開始有能力解讀 JavaScript...

GoogleOfficial Google Webmaster Central Blog 上正式向全世界公告他們的 Searchbot 將會解讀 JavaScript:「Understanding web pages better」。

也就是說,再這次改版後,就算你的頁面全部用 JavaScript 產生,Google 也有能力解讀出來。這顛覆了以前學到的觀念...

其他家 (DuckDuckGo?) 會支援嗎?不知道會不會跳下去做...

Google 的 site: 限制更少了...

以往在使用 Googlesite: 只知道能放 suffix,譬如 site:edu.tw

而剛剛在「Advanced Uses for Google's Site: Operator」則是看到了 site:blog.* 這種用法,或是 site:blog.*.com 這種用法,不過原作者目前測試發現有漏,我自己測試是沒什麼問題 :p

另外這個技巧在圖片搜尋也可以使用 :p

MySQL 中,MyISAM 與 InnoDB 帶來的差異...

標題所提到的兩個 engine 是在 MySQL 中最常用到的兩個 engine。其中 MyISAM 是在 MySQL 5.1 之前的 default engine,InnoDB 則是 MySQL 5.5 之後的 default engine。

這篇主要是講 MySQL 5.1 + InnoDB Plugin,或是 MySQL 5.5 後的情況。

MyISAM 是 Table-level lock,當有寫入時其他人無法讀取 (有少數例外,像是 bulk insert)。而 InnoDB 設計成 Row-level lock,在寫入時有很大機會還是可以讀取。

另外,InnoDB 支援 ACID transaction,對於學過資料庫理論的人 (像是科班出身) 會覺得比較「親切」,比起 MyISAM 有很多東西可以用。

大多數不換 InnoDB 有幾個原因:

InnoDB 佔用的空間比較大

最常見的原因是認為 InnoDB 相對 MyISAM 所佔用的空間會大不少 (看過三倍大的):但在 InnoDB 自從推出壓縮功能後就接近很多 (看過只大 20% 的,甚至有可能比 MyISAM 小)。而資料量的問題可以參考 Mobile01 的 55GB (2012 年 10 月 uid=1 的蔣大在 Mobile01 上揭露的數字)。

當網站夠大時,記憶體與用 15KRPM SAS 硬碟加上 RAID1+0 的一次性成本其實不高。

InnoDB 不好備份

第二個常見的原因是認為 MyISAM 備份比較容易,直接 copy 就可以備份:這種備份方式其實有很高的風險造成 inconsistent backup (「備份的資料損毀」)。以交易的例子來說,有 auction 與 user 兩個表格,按照字母順序先複製了 auction 表格,再複製 user 表格,中間使用者用點數購買了某個物品 (扣 user 表格裡的點數,在 auction 裡建立一筆資料)。這份備份裡就會備份到「user 內的點數扣掉,但 auction 沒有資料」的情況。

比較好的方式是用 InnoDB 提供的 transaction 建立 consistent backup,備份時長時間讀取不會像 MyISAM 無法寫入。另外一種方式是建立 backup 專用的 slave,要備份時可以整台 slave 停掉備份 (還有像是 filesystem snapshot 之類的方式,這邊跳過)。

書上寫 MyISAM 效能比較好...

是的,不過這個前提是「如果你只有讀取」。

MyISAM 讀取效能比較好並不是指 MyISAM query 一次 <1ms 時 InnoDB query 一次就要 100ms 這種程度。兩個都還是在 <1ms,只是當你用到「效率不好的 query」時,MyISAM 在 Table scan 的效能會比 InnoDB 好。

但當網站變大遇到 MyISAM + table scan 時就完蛋了:一個 query 卡 1 秒就代表網站上寫入時遇到這個 query 時最少要卡一秒,InnoDB 反而能救你。(雖然這不是好的方向。好的方向應該是想辦法解決 Table scan 的問題,可能是改 query,也有可能是增加 index 或修改 index)

也因為以上的特性,當使用 InnoDB 時,可以這樣設計:

只對時間敏感 Query 加上 Index

以前用 MyISAM 時為了避免跑報表會造成其他線上服務的 query 卡住,如果用 InnoDB 因為不會卡,報表的 query 沒有 index 而 table scan 也是可以接受的。

有嚴格資料正確性需求的 Query 使用 Transaction

像是金流相關系統,一筆購買紀錄可能要修改好幾個表格。用 MyISAM 時必須對好幾個表格使用 TABLE LOCK (仍然有 atomic 問題),現在可以用 transaction 解決。

資料庫正規化

有可能會因為 MyISAM 卡 query 的問題而設計出非正規化的 schema。用 InnoDB 可能可以正規化,用適當的設備成本 (像是適當使用 JOIN) 降低人力維護成本。

Perl on Google App Engine

Python 是第一個可以在 Google App Engine (GAE) 上執行的程式語言,而下一個很有可能是 Perl

Brad Fitzpatrick 在他的 Blog 上說,他被 GAE team 允許對外公佈「我可以使用 20% 的時間開發 Perl on GAE」:Perl on App Engine

這是 GAE 支援其他程式語言的消息中,第一個被正式公開的。在 Brad Fitzpatrick 的文章裡面有一些藍圖,關於他大概會怎麼做的想法。我們應該可以期待他認真起來的戰鬥力 :p

PS:Brad Fitzpatrick 是 LiveJournal 的創辦人、memcached 的作者、OpenID 的制定人。