Tag Archives: structure

Quotient filter

Posted on August 9, 2017 by Gea-Suan Lin

之前有提過「Cuckoo Filter：比 Bloom Filter 多了 Delete」，最近在「A general purpose counting filter: making every bit count」這邊看到 Quotient filter，也是類似 Bloom filter 的資料結構，但想要解決更多問題。 一般的 Bloom filter (BF) 會有這些問題： The inability to delete items Poor scaling out of RAM The inability to resize dynamically The … Continue reading →

Posted in CDN, Computer, Murmuring, Network, Programming | Tagged , , , , , , , , , , , , , | Leave a comment

GitHub 的組織管理可以堆階層了...

Posted on June 14, 2017 by Gea-Suan Lin

GitHub 的組織管理可以堆階層了：「Nested teams add depth to your team structure」。 If you're a member of Engineering and someone creates a child team called Security, team members of Engineering aren't automatically direct team members of Security. Security and all other teams nested … Continue reading →

Posted in Computer, Murmuring, Network, Security, Service, WWW | Tagged , , , , , | Leave a comment

Reddit 在處理 Page View 的方式

Posted on May 28, 2017 by Gea-Suan Lin

Reddit 說明了他們如何處理 pageview：「View Counting at Reddit」。 以 Reddit 的規模有提到兩個重點，第一個在善用 Redis 的 HyperLogLog 這個資料結構，當量大的時候其實可以允許有微小的誤差： The amount of memory varies per implementation, but in the case of this implementation, we could count over 1 million IDs using just 12 kilobytes of space, … Continue reading →

Posted in Cassandra, Computer, Database, Murmuring, Network, Programming, Service, Software | Tagged , , , , , , , , , , , , , , , , , , , | Leave a comment

在面試時的資料結構與演算法的問題

Posted on April 28, 2017 by Gea-Suan Lin

在「500 Data structures and algorithms interview questions and their solutions」這邊看到在 Quora 上整理出來的題目 (以及解答)。 每個題目下面也都有地方可以留言，等久一點應該會更豐富？ 另外一個不錯的地方在於題目的分類，舉例來說，如果想要練習 Backtracking，可以去翻對應的題目出來練。

Posted in Computer, Murmuring, Programming | Tagged , , , , , , | Leave a comment

Cuckoo Filter：比 Bloom Filter 多了 Delete

Posted on August 8, 2016 by Gea-Suan Lin

在「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」，表示可以直接替代。

Posted in Computer, Murmuring, Programming | Tagged , , , , , , , | 1 Comment

看到 zmx 貼了之前的連結，更確信 Uber 的問題不是技術問題了...

Posted on August 3, 2016 by Gea-Suan Lin

在 Twitter 上看到 zmx 提了一個連結，講 Uber 年初時貼的「How We Built Uber Engineering’s Highest Query per Second Service Using Go」這篇文章的問題： TLDR; Uber：傳統方式太複雜了根據我們資料特性自創一套高效能的空間索引服務。前 Bing 員工：買了 Bing 怎麼不問專家啊？Quadtree 降兩個數量級啊，不然你們自創的做了這個小修改也是降兩個數量級啊！https://t.co/nHw1DgmYtU — Bill Zhong (@zmx) August 2, 2016 對照最近的事情還蠻有趣的，尤其是這篇文章後面提到的，酸～爆～了～XDDD： It is clear to me that the … Continue reading →

Posted in Computer, Murmuring, Network, Programming, Search Engine, Software | Tagged , , , , , , , , , , | Leave a comment

MySQL 的 Index 設計技巧

Posted on April 28, 2015 by Gea-Suan Lin

Percona 的「Indexing 101: Optimizing MySQL queries on a single table」這篇講了最基本的 index 設計技巧，雖然文章裡沒提到，但最好是需要 B-tree 與 B+ tree 的背景知識。 MySQL 的 query 大致分成幾個階段。先決定要使用哪些 index (或是完全不用)，然後透過 index 抓出符合條件資料 (或是 table scan)，最後再細部過濾。 以文章裡提到的「Multiple inequalities」範例裡這樣的 SQL query 來討論： SELECT * FROM t WHERE c > … Continue reading →

Posted in Computer, Database, Murmuring, MySQL, Software | Tagged , , , , , , , , | Leave a comment

資料結構、RDBMS、ORM

Posted on June 23, 2014 by Gea-Suan Lin

欠了很久的雜記。既然是雜記，只是把一些事情記錄下來，許多句子的主題會跳來跳去，請多見諒。 先解釋標題的三個詞彙。這邊要講的是三種存取資料的方式： 資料結構：直接操作最底層的資料結構。 RDBMS (Relational Database Management System，關聯式資料庫)：透過 RDBMS 存取資料的方式，在 open source 領域比較常遇到 MySQL 與 PostgreSQL。由於與下面的 ORM 比較，這一條指的是透過 SQL query 去存取資料。 ORM (Object-Relational Mapping)：透過程式語言的 object 以及 object 之間的關聯性存取資料。 彈性最高、效能也最好的是直接的資料存取，但寫起來也最複雜；而 ORM 大致上就是反過來。 現代的 RDBMS 大多都有實做 ACID，在自己操作資料結構時考慮這塊會比較辛苦。兩個層級之間有一些 library 試著解決這個問題 (像是 BerkeleyDB 或是 … Continue reading →

Posted in Computer, Database, Murmuring, MySQL, PostgreSQL, Programming, Software | Tagged , , , , , , , , , , , , , , | Leave a comment

ESR 解釋 C 的 Compiler 對 Structure Packing 的處理...

Posted on January 3, 2014 by Gea-Suan Lin

ESR (Eric S. Raymond) 寫了一篇 C Compiler 對 struct 實際如何佔用記憶體空間的說明：「The Lost Art of C Structure Packing」，全文在「The Lost Art of C Structure Packing」。 以前都學過也都還記得，但沒用就不容易想起來... 以文章裡的例子用這個 struct 說明： struct { char *p; char c; int x; }; (下面就不列出 struct 的部份了) 實際上在記憶體裡面會因為 alignment … Continue reading →

Posted in Computer, Hardware, Murmuring, Programming, Software | Tagged , , , , , | 2 Comments

Linux kernel 內的資料結構與演算法...

Posted on November 28, 2013 by Gea-Suan Lin

在 Theoretical Computer Science Stack Exchange 上，有人問到有沒有哪些軟硬體的 source code 是可以跟學生說明某些經典演算法的重要性：「Core algorithms deployed」。 下面就有人列了 Linux kernel 內的演算法，以及對應的程式碼。相當長的一份列表... 除了 Linux kernel 外，也還有其他大型 open source 專案用到的資料結構與演算法... 不過看到 Bubble sort 是怎樣呢... XD

Posted in Computer, Linux, Murmuring, OS, Programming, Software | Tagged , , , , , , | Leave a comment