[Azure] Multi-Tenancy Application #3, (資料層)實作案例

上篇花了一堆口水，說明各種 data layer 的設計方式，這回不噴口水了，直接來實作...。 開始前先說明一下我的期望，我先假設各位都用過 Entity Framework 或是這類的 solution, 我希望在 data context 這層，就能處理掉所有 隔離 tenancy data 的問題，也就是我可以用一般 application 的開發概念來開發 multi-tenancy 的 application。換另一個說法，我希望 在一個 storage 內，模擬出讓每個 tenancy 都有獨立的 storage 可運用的介面。 Web 的這部份也是一樣的概念，我希望在網址這層，邏輯上就讓每個 tenancy 有獨立的 URL (虛擬目錄)。有這種網址上自行客製的需求，當然是 非 MVC 不可，因此這次會在 MVC 的 Routing 上動手腳，除了 controller 及 action 之外，能夠再切出一層 client 出來，讓 application 也像 是能夠虛擬化一樣，每個用戶可擁有自己的 partition。 最後當然也希望 WEB 這邊的架構，能緊密的跟 DATA 這邊結合。讓開發人員就照一般 的方法就能快速開發出Multi-Tenancy Applicaiotn。寫這種系統，若規模不夠大就沒意思了，因此我初期就把目標鎖定 在 Windows Azure Storage + MVC4, 而應用程式就以常見的 "訂便當系統" 為案例。 訂便當系統，是個很適合開發成 Multi-Tenancy 模式的主題。原因有幾個:

1. 這系統一定是一個團體才會需要用的，如果你只有兩三個人，用講的比較快... 通常是部門、辦公室、或是規模不大，可以一起訂便當的團體會需要使用。這需要基本的每日訂單管理，還有簡單的會員管理功能。
   
2. 既然是 Multi-Tenancy Application, 那麼用 SaaS (Service as a Service) 的方式營運也是很理所當然的。所有客戶通用的內容，就可以由營運單位來負責整理及規劃。
   
3. 除了切割很多獨立的 "分割區" 各自運作之外，Hosting 的一方其實也有很多商機，像是合作的餐聽或是便當店，這些資料就可以共用。甚至是可以主動匯入，讓客戶訂購起來更方便。若這樣能為便當店帶來生意，Hosting 的一方抽點庸金也是很合理的 XD
   
4. 後台 BI 也是很有商機的一環。Service Hosting 的一方，就可以看看各種統計報表，看跟那家餐廳合作的機會較大，另外也可以設計客戶 share 他們自己開發的便當店資訊，給其它客戶使用。若越多客戶採用，可以給些系統租金的回饋等等….

越想越多，再想下去這個 POC 用的 prototype 就寫不完了，需求給各位讀者再去延伸，我這邊作 POC 就把需求收殮一下...。偷學一下 SCRUM 的 story 撰寫技巧，以下是我這次 POC 要實作的 stories:

好，看來一個設計良好的 DataContext, 可以省掉不少工夫。大部份的 coding logic, 都是在客戶的專區內運作的。我把整套系統稱作 "Hub”, 而每個客戶專區內的資料，就通稱為 "HubData”, 如會員資料，或是訂單等等。而其它非 HubData, 就是整個系統通用的資料。因此，我希望 Hub 用的 Data Context 能有這些功能:

1. 取得 HubDataContext 時，就已經能確定目前是在那個 Client 的使用範圍。
2. HubDataContext 能直接提供該 Client 才能用的 Data Collection, 我只要拿來再用 Linq 過濾即可，即使我沒控制好，也不會拿到別的 Client 專區內的 HubData。
3. 全域 (共用) 的資料則不在此限。每個 Client 都能完整存取這些資料內容。

OK，噴了三篇的口水，終於看到第一段程式碼了 Q_Q，HubDataContext 的 interface 看起來要像這樣:

使用它的 Code 要像這樣 (這段我就寫在 unit test 內…):

花了一點時間，總算把實作都寫出來，成功通過單元測試了。套句 Luddy Lee 前輩常說的話，寫雲端的程式測試跟佈署都比以前麻煩，因此做好完整的規劃跟測試就變的更重要了，單元測試是少不了的，請各位切記。過去吃了很多苦頭，更加證明 Luddy Lee 前輩講的話一點都沒錯....

最終的 HubDataContext 實作如下... 其實也沒幾行:

OK，第一步通過了，接下來我們開始來規劃一下 Data Schema …. Azure Table Storage 已經沒有所謂的 "schema” 這回事了，它完全就像 EF5 裡面的 code first 一樣，你的 Data Entity class 定義好，就可以跑了... 這些細節就不在這篇裡多做說明，各位有興趣可以參考其它的資料。既然都是 Code First 開發模式了，我就直接用 class diagram 來描述這些資料 (Entity) 之間的關係:

2013/03/21 系列文章: Multi-Tenancy Application ASP.NET AZURE C# 作品集 技術隨筆

[Azure] Multi-Tenancy Application #2, 資料層的選擇

其實上一篇設計概念還沒寫完，只不過很晚了想睡覺就先貼了，本篇繼續..

之前介紹 MSDN 的那篇文章，作者很精確的分析了資料層面的三種設計方式。不過仔細研究之後，真正能搬上台面的，也只有最後一種 “Shared Schema” 而已。我從系統實際運作的角度，來分別考量這三種方式的可行性，各位就知道我為何這樣說了..。上篇介紹了各種可行的方案，這篇則會說明我認為的最佳方案。

我的看法很簡單，除非你的 Multi-Tenancy 的 “Tenancy” 規模只有幾十個的數量，否則 Separated DB / Separated Schema 都不適用，因為這兩種方式都是依賴把資料放在不同的 DB 或是 TABLE，來達到隔離的目的。並不是說這樣不好，而是這些都是 "過渡" 的作法，讓傳統的 application 不需要大符修改就能化身變為 Multi-Tenancy 的應用系統。而且 database / table 的數量都是有限制的，無法無限制的擴張。同時，以系統設計的角度來看，在系統執行的過程中，動態去建立 DB 或是建立 TABLE 也不是個很好的作法，在我眼裡都會覺的這是禁忌 XD。

當你辛辛苦苦建立了 SaaS 服務，總不可能只服務兩三隻小貓吧? 因此下列的分析會用使用量及 DB 各種功能的理論上限來做簡單的評估。Multi-Tenancy 的用戶數量，就抓個 50000 好了，至於每個用戶的 profile 我也依過去的經驗大致預估看看。依這些假設，就可以來評估各種資料層的處理方式，會有啥問題。

以下是一般的應用，每個用戶需要的資料規模 (假設):

1. 能容納的用戶量限制

以 SalesForce.com 為例，它會為每個 "公司" 開設一個專區，接著看該公司買了多少帳號，就開幾個 User Account。這裡的 "公司" 就是一個用戶，也就是 Multi-Tenancy 裡指的 "Tenancy”。這用戶的數量合理的數量應該是多少? 而系統的理論上限又是多少?

實際運作當然還有軟硬體搭配跟效能問題，這理就先就 "理論上限" 來探討。理論上限值，應該要在任何情況都足夠使用才合理。我特地去挖了 Microsoft SQL Server 的各種物件的數量上限，下表是從官方資料 整理出來的，以目前最新的 SQL 2012 為準，單一一套 SQL SERVER 可以:

看起來，最需要注意的就是 database 數量了。一套 SQL SERVER 最多只能開設3萬個database, 如果你採用 Separated DB 的作法，不論使用量為何，連同試用用戶，或是測試用戶在內，只能給三萬個用戶使用... 雖然不見得每個系統都會有這麼多用戶，不過一定會有不少熱門的應用會超出這樣的限制。

那第二種切割作法 (Separated Schema) 情況如何? SQL server 是以 database objects 的總數來計算的，包含 table, view, function, trigger 等等都算是 database object. 一個資料庫能容納 2G (20億) 個 database objects, 相當於能容納 400K (40萬) 個用戶。這數值比 Separated DB 的 3 萬好上一些... 在台灣，以公司為單位的服務，應該還沒有問題。若是以部門、團隊、或是家庭、社團設計的 application, 這樣的容量上限就需要耽心了。

Share Schema 則完全沒這些問題，只要儲存空間足夠，系統的效能能夠負耽，就沒有這種物理的上限限制了。

2. 效能擴充 (scale out) 的限制

如果考量到大型一點的規模，其實這三種方式都有困難。Separated DB 本身就已經是獨立DB，SQL server 本身執行的負擔就大很多，對於數量很多的用戶，但是每個用戶的人數都不多時，會浪費太多系統資源在執行這堆 DB 上面。不過相對的，這種架構很容易做 Scale Out 的擴充。

另一個要考量的是，雖然稱做 Multi-Tenancy, 但是總有些資料是要讓全部的用互共用吧? 這時這類資料就會變的很難處理，一個不小心就會動用到橫跨上千個 database 的 sql query ..

另一個極端的 Share Schema 做法就完全相反，沒有執行多個 DB 的負擔，執行起來效能是最好的。但是因為所有資料都塞在一起，很容易就面臨到單一 table 的資料筆數過大的問題。以這次的例子，一個用戶有10萬筆資料的話，隨便 1000 個用戶就有 1 億筆資料了... insert / delete / update 資料時，更新 index 的成本會變的很高。一般的查詢就會很吃力了，若是碰到沒寫好的 table join 會更想哭... 換句話說，這樣的架構規劃下，資料庫的最佳化非常的重要。因為你面臨到的就是大型資料庫效能調校問題..

再者，資料庫相對於 WEB 來說，是很不容易 Scale Out 的... 比較合適的作法是對資料庫做 Partition. 不過，這也不是件容易的事，已超出我的理解範圍了 XD，我只能說，要是老闆決定這樣做，那 $$ 決對是省不了的...

3. RDBMS 之外的選擇: Azure Table Store

前面講的，其實都是幾年前我在傷腦筋的問題。傳統的資料庫是為了資料的正確性及一致性而打造的儲存技術，過多的限制 (schema, constraint, relation…) 也限制了它無法有效 scale / partition 的特性。要徹底解決這些問題，不砍掉重練的話就只能花大錢及人力，來追上雲端服務的使用量了...。

不論是 Google, 或是 Microsoft Azure, 或是依據 Google 提出 MapReduce 而發展出來的 Hadoop, 都有處理巨量資料的能力。我就挑我最熟的 Azure 來說明。近幾年資料庫相關的技術，開始有了不一樣的變化。開始出現 "NO SQL” 的資料儲存方式。這種儲存方式有著跟 RDBMS 完全不一樣的特性，它比較簡單，主要是以 Key-Value 的型式來存取。因為 NO SQL 的結構比 RDBMS 簡單，因此能夠很容易的做到 scale out, 將單一資料庫，擴充到上千台 server 的規模。而 Azure 提供的 Table Storage, 則是將這種 NO SQL 的資料，跟 RDBMS 表格式的資料，做了一個很好的串接。

想瞭解 Azure 的細節，這輪不到我來說，市面上有幾本書很不錯，像是 MVC 小朱的新書，或是大師 Lee Ruddy 的大作都很值得參考，若不介意看英文書，那選擇就更多了~，我就不在這多說太多了。但是 Azure Table Storage 有兩個很重要的特色，一定要講一下:

1. PartitionKey / RowKey: 

老實說，這對 Multi-Tenancy 來說，是最完美的設計了。這篇文章講的很精闢，你要用 Azure Table Storage 的話一定要好好的研究 PartitionKey / RowKey, 因為我看過太多可笑的用法，實在糟蹋了這樣好的設計...。這篇文章前面講的都是howto, 最後一章是 "Why using Windows Azure Table Storage”, 我截錄一段:

The storage system achieves good scalability by distributing the partitions across many storage nodes.

The system monitors the usage patterns of the partitions, and automatically balances these partitions across all the storage nodes. This allows the system and your application to scale to meet the traffic needs of your table. That is, if there is a lot of traffic to some of your partitions, the system will automatically spread them out to many storage nodes, so that the traffic load will be spread across many servers. However, a partition i.e. all entities with same partition key, will be served by a single node. Even so, the amount of data stored within a partition is not limited by the storage capacity of one storage node.

The entities within the same partition are stored together. This allows efficient querying within a partition. Furthermore, your application can benefit from efficient caching and other performance optimizations that are provided by data locality within a partition. Choosing a partition key is important for an application to be able to scale well. There is a tradeoff here between trying to benefit from entity locality, where you get efficient queries over entities in the same partition, and the scalability of your table, where the more partitions your table has the easier it is for Windows Azure Table to spread the load out over many servers.

翻成白話，意思就是，開發人員只要慎選 partition key, 則 Azure 就會把同一個 partition 的資料放在同一個 node (不限於同一個 table 的 entities)。因此查詢會受惠於各種 cache 及 optimiaztion 機制，得到最佳效能。同時 Azure 也會自動依照 partition key 來分散到多個 node, 達到最佳的 scalability。

2. Scalability Issues, and Query optimization issues

另外，MSDN magazine 也有一篇值得一讀的文章... "Windows Azure Table Storage – Not Your Father’s Database" (中譯: 不是令北的資料庫… Orz), 一樣切重點出來:

PartitionKeys and RowKeys Drive Performance and Scalability

Many developers are used to a system of primary keys, foreign keys and constraints between the two. With Windows Azure Table storage, you have to let go of these concepts or you’ll have difficulty grasping its system of keys.

In Windows Azure Tables, the string PartitionKey and RowKey properties work together as an index for your table, so when defining them, you must consider how your data is queried. Together, the properties also provide for uniqueness, acting as a primary key for the row. Each entity in a table must have a unique PartitionKey/RowKey combination.

這篇就實際一點了，講到很多 Azure Table Storage 的特性，也帶出了設計時必需考慮的要點。因為設計理念不同，連帶的查詢時的限制 & 表現，跟傳統的 RDBMS 完全不同... 有沒有仔細規劃 partition key / row key, 決定了你的 query 效能的好壞。

除了內定的 partition key / row key 之外，其它 "欄位" 完全沒有任何的索引機制。這就是最需要顧慮的地方。實際上，Azure Table Storage 跟本就沒有 Schema 的設計，當然也沒有像 RDBMS 那樣的表格，反而是個典型的 Key-Value Pair 的 storage 而已。至於這些看起來像欄位的東西，完全是用 Code (TableEntity) 跟實際儲存的 Data (應該是 XML，或是類似的結構化 data) 變出來的東西。也因此，Query 完全需要良好的規劃才能有好的表現。

若各位對 Azure Table Storage 的 Query 技巧有興趣，這段 VIDEO 很值得一看。這是 2009 PDC 的一個場次: "Windows Azure Tables and Queues Deep Dive”, 講到很多 Query 的技巧..

再回到前面那篇參考文章，最後作者也列了一些缺點及建議，強烈建議各位在決定採用 Azure Table Storage 前要認真閱讀:

Windows Azure table storage is designed for high scalability, but there are some drawbacks to it though:

• There is no possibility to sort the data through your query. The data is being sorted by default by the partition and row key and that’s the only order you can retrieve the information from the table storage. This can often be a painful issue when using table storage. Sorting is apparently an expensive operation, so for scalability this is not supported.
• Each entity will have a primary key based on the partition key and row key
• The only clustered index is on the PartitionKey and the RowKey. That means if you need to build a query that searches on another property then these, performance will go down. If you need to query for data that doesn’t search on the partition key, performance will go down drastically. With the relational database we are used to make filters on about any column when needed. With table storage this is not a good idea or you might end up with slow data retrieval.
• Joining related data is not possible by default. You need to read from seperate tables and doing the stitching yourself
• There is no possibility to execute a count on your table, except for looping over all your entities, which is a very expensive query
• Paging with table storage can be of more of a challenge then it was with the relational database
• Generating reports from table storage is nearly impossible as it’s non-relational

If you can not manage with these restrictions, then Windows Azure table storage might not be the ideal storage solution. The use of Windows Azure table storage is depending on the needs and priorities of your application. But if you have a look at how large companies like Twitter, Facebook, Bing, Google and so forth work with data, you’ll see they are moving away from the traditional relational data model. It’s trading some features like filtering, sorting and joining for scalability and performance. The larger your data volume is growing, the more the latter will be impacted.

看起來蠻恐佈的，由於架構的不同，Azure Table Storage 無法題供像 RDBMS 那樣多樣化的查詢能力，除了 partition key / row key 之外，甚至連 RDBMS 最基本的 index 都沒有，這也導至這篇的作者連這點也列入缺點 "Generating reports from table storage is nearly impossible as it’s non-relational" ...

不過，實際的狀況其實沒這麼嚴重。Azure Table Storage 極為強大的 scalability 可以彌補查詢上的不足，平行的查詢，及針對巨量資料的設計，都是你在處理巨量資料的武器，而這些是 RDBMS 所無法提供的。

寫到這裡，我簡單下個結論。Azure Table Storage, 是個很棒的 “storage”, 有絕佳的延申及擴充能力。能夠輕易的儲存及處理巨量資料，不論是資料大小或是資料筆數都一樣。不過它畢竟不是 "R"DBMS，而是 NO SQL這一類的 storage, 因此在執行覆雜的 QUERY 上不是 RDBMS 的對手。一些統計方面的功能 (如 SUM, COUNT, AVERAGE …. 等等) 就更不用說了。這部份得靠 ORM、Linq 及你的程式來補足。

而 Azure Table Storage 的規劃就將 partition 的機制放進去了，拿來做 Multi-Tenancy 的資料切割機制真是絕配! 跟本就是為了這樣的應用而設計的... 下一篇我會示範實際的程式碼，用 Azure Table Storage 來實作 Multi-Tenancy Applicaion 的 Data Layer ..

2013/03/17 系列文章: Multi-Tenancy Application AZURE MSDN SQL 技術隨筆

[Azure] Multi-Tenancy Application #1, 設計概念

對，各位你沒看錯，我的部落格在隔了一年半之後又有新文章了 XD

好久沒寫了，這年頭什麼東西都流行加個 "微" ... BLOG 有微博，Messenger 有微信... MV有微電影... 連我們在做的數位學習也出現 "微型課件" ... 什麼都微型化的後果，就是越來越懶的 POST 這種 "大型" 的文章在 BLOG 上了.. 常常想到一些東西，還沒成熟到一個完整概念，就貼到 FB 上，越來越速食的結果就越來越沒顧到 BLOG... Orz…

不過，世界果然是在往M型的方向發展，雲端到現在已經是個成熟的技術 & 概念了，WEB APP的開發也越來越大型化，用了 Azure 當 PaaS (Platform as a Service) 後，要開發大型的 Web Application 門檻也不像過去那麼高。這次要寫的，就是 SaaS (Software as a Service) 被廣為流傳的設計概念: 多租戶 (Multi-Tenancy) 的設計方式。

其實說明 SaaS 或是 Multi-Tenancy 的文章一大堆，完全輪不到我這種文筆程度的人來寫 XD，一樣，我只針對特別的地方下筆。Multi-Tenancy 顧名思義，就是讓一個 Application 能做適當的切割，"分租" 給多個客戶使用。跟過去一個 Application 就服務一個客戶不一樣，Multi-Tenancy 先天就是設計來服務多個客戶用的，也因為當年 SalesForce 的成功而聲名大噪。

回到系統的角度來思考，要設計一個漂亮的 Multi-Tenancy (Web) Application, 還真的是個不小的挑戰... 沒錯，我就吃過這種苦頭 XD，大概六年前因為工作上的關係，就已經有這樣的設計架構了，不過當年一切都要自己來，因此什麼釘子都碰過了。用現在的技術，有太多簡潔的作法，不過確看不到有太多的人在討論 (至少中文的沒有)，就動起這念頭，想來寫幾篇.. 內容就定位在用當紅技術: Microsoft Azure + ASP.NET MVC4 當作底層開始吧~~

先來探討一下幾種常見的 Multi-Tenancy 的設計方式。MSDN 有篇文章寫的很精闢，快七年前的文章了，當年靠著這篇給我不少靈感... 我就先來導讀一下，標一下幾個架構設計的重點 (底下圖片皆引用 MSDN 該篇文章):

三種架構: Separated DB / Separate Schema / Shared Schema 比較:

要把多個客戶塞進同一套系統內，最直接的問題就是資料隔離的 issue 了。暫時不管 application, 只管 data, 若對隔離及安全性要求越高，就要在越底層就做到隔離的機制。

1. Separated DB
   
   
   最高隔離等級，就是每個客戶一個 database (Separated DB)。用這種模式，再怎麼粗心的工程師，也不會不小心把別的客戶的資料給秀出來。舉個例，系統內的A客戶，就會連到A資料庫，B客戶就用B資料庫。每個客戶的資料庫各自獨立，不會互相打架。
   
   
2. Separate Schemas (Shared Database)
   
   
   這種作法比第一種 Separated DB 好一點，它共用同一個 DB，但是替每一個客戶建立一組 Tables。這種作法不需要那麼高的成本 (看過 $$ 就知道，資料庫很貴的….)，多個客戶可以共用資料庫，不過因為 Schema 的層級隔離了，簡單的說不同客戶的 Table Name 是不一樣的，因此粗心的工程師造成客戶資料混在一起的機率也不算高，還有不錯的隔離機制。
   
   這方式實作有點辛苦，不過 SQL 2005 之後開始支援 Schema 這機制，實作上可以簡單的多。
   
   
3. Shared Schema (Shared Database & Shared Schema)
   
   
   
   這作法最極端了，所有資料都放在同一個資料庫，同一組資料表... 靠的是一個客戶ID的欄位來區別。這種方式成本最低，設計也最簡易直覺，不過... 整個系統只要有一道 SQL query 寫錯 (漏掉 where TenantID = ‘MyAccount’)，一切就完了，A客戶的資料就會出現在B客戶的報表裡...

當然，這篇是 MSDN 的文章，自然也提到了 Microsoft 的技術 (SQL server) 如何因應這三種不同的需求。這張表格是整篇文章的精華了，很清楚的講到三種模式，對各種問題的最佳處理方式。表格貼不過來 @@，我直接用截圖來說明:

簡單舉個例子，Extensibility Patterns 這欄說明的是如何擴充你的資料? 這裡指的擴充不是指效能，是只你要如何增加新的資料型態?

Separate DB  or Shared DB 最簡單，就照一般的方法，開新的欄位就好。對於 Shared Schema 的系統來說就沒這麼容易了，只能預先開幾個備用欄位 (如每個 table 都開: column1, column2, column3 …. etc)，不然就只能弄出像 NO SQL 那種 Name-Values 的方式來處理。不過，有經驗的開發者都知道，這樣搞下去，QUERY 實在很難寫...

其實這篇文章講的很務實，從設計架構、開發、到系統上線的維護及調校都講的很清楚，若各位有在企業內部 (INTRANET) 的環境建立 Multi-Tenancy Application 的需求，只能用 Windows Server + SQL Server 的話，這篇文章很值得參考。不過，這篇文章的時空被景是 2006 年，當年沒有 Azure 這種東西... MVC 也沒今天那麼成熟... 現在要做同樣的事，你有更厲害的武器可以用...

現在該怎麼做? 當然是等下一篇 XD

2013/03/12 系列文章: Multi-Tenancy Application AZURE MSDN SQL 技術隨筆

LINQ to Object #2, Indexes for Objects

上一篇自己寫了很不成熟的範例，示範怎麼同時使用 LINQ to Object 的方式查詢物件，同時又能用到索引的機制。不過示範歸示範，總是要有上的了檯面的作法… 這就是本篇的目的: i4o (indexes for objects) 這套函式庫的應用!

開始囉唆前，先來看看怎麼用吧! 接續上一篇的範例，我做了點調整，一方面把查詢的對像，從原本的 string 換成 Foo，另一方面也加上了第三種對照組: 使用 i4o 來建立索引。程式碼及執行結果如下:

對三種不同的 collection 進行 Linq 查詢

Stopwatch timer = new Stopwatch();

// 建立資料集合 list1: 使用 List<Foo>, 沒有索引
List<Foo> list1 = new List<Foo>();
list1.AddRange(RndFooSeq(8072, 1000000));

// 建立資料集合 list2: 使用 IndexedList, 自訂型別，針對 Foo.Text 及 Foo.Number 建立索引，Query 只支援 == 運算元
IndexedList list2 = new IndexedList();
list2.AddRange(list1);

// 建立資料集合 list3: 使用 i4o library
IndexableCollection<Foo> list3 = list1.ToIndexableCollection<Foo>();

// 對 list1 進行 query
Console.WriteLine("\n\n\nQuery Test (non-indexed):");
timer.Restart();
(from x in list1 where x.Text == "888365" select x.Text).ToList<string>();
Console.WriteLine("Query time: {0:0.00} msec", timer.Elapsed.TotalMilliseconds);

// 對 list2 建立索引，進行 query
Console.WriteLine("\n\n\nQuery Test (indexed, dic):");
timer.Restart();
list2.ReIndex();
Console.WriteLine("Build Index time: {0:0.00} msec", timer.Elapsed.TotalMilliseconds);
timer.Restart();
(from x in list2 where x.Text == "888365" select x.Text).ToList<string>();
Console.WriteLine("Query time: {0:0.00} msec", timer.Elapsed.TotalMilliseconds);

// 對 list3 建立索引，進行 query
Console.WriteLine("\n\n\nQuery Test (indexed, i4o):");
timer.Restart();
list3.CreateIndexFor(i => i.Text).CreateIndexFor(i=>i.Number);
Console.WriteLine("Build Index time: {0:0.00} msec", timer.Elapsed.TotalMilliseconds);
timer.Restart();
(from x in list3 where x.Text == "888365" select x.Text).ToList<string>();
Console.WriteLine("Query time: {0:0.00} msec", timer.Elapsed.TotalMilliseconds);

2011/10/30 .NET C# Tips 物件導向

[CODE] LINQ to Object - 替物件加上索引!

好久沒寫文章了，看了一下上一篇的日期… 嚇，再撐幾天就 10 個月了 =_=,  週末看了 darkthread 的這篇文章: 當心LINQ搜尋的效能陷阱，想說 LINQ to SQL, LINQ to Entity Framework, LINQ to … 都支援索引, 沒道理 LINQ to Object 不行啊, 一定只是沒人補上實作而已.. 動了這個念頭之後, 接下來的時間就都在研究這些…

回到主題，年紀夠大的網友，大概都還聽過 Embedded SQL 吧? 當年用 C/C++ 要存取資料庫，實在不是件簡單的事… 光是那堆 initial database connection 的動作就搞死人了，因此有些開發工具廠商，就搞出了 Embedded SQL 這種內嵌在程式語言內的 SQL .. 貼一段 CODE，看起來大概像這樣:

Embedded SQL sample code:

/* code to find student name given id */
/* ... */
for (;;) {
    printf("Give student id number : ");
    scanf("%d", "id);
    EXEC SQL WHENEVER NOT FOUND GOTO notfound;
    EXEC SQL SELECT studentname INTO :st_name
             FROM   student
             WHERE  studentid = :id;
    printf("Name of student is %s.\n", st_name);
    continue;
notfound:
    printf("No record exists for id %d!\n", id);
}
/* ... */

有沒有跟現在的 LINQ 很像? CODE 就不多解釋了，這類的工具，大都是遵循這樣的模式: 透過編譯器 (或是 code generator / preprocessor)，將 query language 的部份代換成一般的 data access code，最後編譯成一般的執行檔，執行起來就有你預期的效果…

看到 darkthread 探討 LINQ to Object 效能問題之後，第一個反應就是:

“該怎麼替 LINQ to Object 加上索引??”

LINQ 這堆指令，最終是會被翻譯成 extension method, 而這些 extension method 是可以自訂的，就先寫了一個小程式試看看..

    public class IndexedList : List<string>
    {
    }

    public static class IndexedListLinqExtensions
    {
        public static IEnumerable<string> Where(this IndexedList context, Expression<Func<string, bool>> expr)
        {
            Console.WriteLine("My code!!!");
            foreach (string value in context.Where(expr)) yield return value;
        }
    }

    class Program
    {
        static void Main(string[] args)
        {
            IndexedList list1 = new IndexedList();
            // init list1 ...

            foreach (string value in (from x in list1 where x == "888365" select x)) {
                Console.WriteLine("find: {0}", value);
            }
        }
    }

程式很簡單，只是做個 POC，證明這段 CODE 會動而已。從 List<string> 衍生出一個新類別: IndexedList, 然後針對它定義了專屬的 Extension method: Where(...), 然後試著對 IndexedList 這集合物件，用 LINQ 查詢… 果然 LINQ 在執行 where x == “888365” 這語句時，會轉到我們自訂的 extension method !

接下來的工作就不是那麼簡單了，我自認很愛挖這些 framework 的設計，又自認 C# 語法掌握能力也不差，結果我也是花了一些時間才摸清楚它的來龍去脈… 事情沒這麼簡單，所以我做了極度的簡化…

首先，我只想做個 POC (Proof of concept), 證明可行就好, 完全沒打算把它做成可用的 library .. 因為在研究的過程中，早已找到有人在做這件事了 (i4o, index for objects)。為了讓 code 簡短到一眼就看的懂的程度，我的目標定在:

1. 查詢對相只針對 List<string> 處理，不做泛型及自訂索引欄位。
2. 查詢只針對 == 做處理。如下列 LINQ 語句的 where 部份: from x in list1 where x == "123456" select x
3. 條件只限於 x == "123456", 只提供 == 運算元，只提供常數的比對，常數只能放在右邊…

接下來就是索引的部份了，因為 where 只處理 == 這種運算，也不用排序了，採用 HashSet 就很夠用了，速度又快又好用，時間複雜度只有 O(1) .. 看起來很理想，於是剛才的 Sample Code 就可以改成這樣:

IndexedList : 加上索引的 List<string> 實作

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Linq.Expressions;

namespace IndexedLinqTest
{
    public class IndexedList : List<string>
    {
        public readonly HashSet<string> _index = new HashSet<string>();

        public void ReIndex()
        {
            foreach (string value in this)
            {
                this._index.Add(value);
            }
        }
    }

    public static class IndexedListLinqExtensions
    {
        public static IEnumerable<string> Where(this IndexedList context, Expression<Func<string, bool>> expr)
        {
            if (expr.CanReduce == false "" expr.Body.NodeType == ExpressionType.Equal)
            {
                BinaryExpression binExp = (BinaryExpression)expr.Body;
                string expectedValue = (binExp.Right as ConstantExpression).Value as string;
                if (context._index.Contains(expectedValue)) yield return expectedValue;
            }
            else
            {
                //return context.Where(expr);
                foreach (string value in context.Where(expr)) yield return value;
            }
        }
    }
}

程式碼稍等再說明，先來看看怎麼用! darkthread 的作法真不錯用，借兩招來試試… 程式大概執行這幾個步驟:

1. 準備 10000000 筆資料，用亂數打亂，建立 list1 (含索引, type: IndexedList) 及 list2 (不含索引, type: List<string>)
2. 呼叫 list1.ReIndex(), 替 list1 重建索引 (HashSet), 記錄建立索引花費的時間
3. 分別對list1, list2進行LINQ查詢，查出四筆指定的資料，計算查詢花費的時間

直接來看看程式碼吧:

測試 Indexed LINQ 的程式碼

class Program
{
    static void Main(string[] args)
    {
        Stopwatch timer = new Stopwatch();

        IndexedList list1 = new IndexedList();
        list1.AddRange(RndSeq(8072, 10000000));

        List<string> list2 = new List<string>();
        list2.AddRange(list1);

        timer.Restart();
        list1.ReIndex();
        Console.WriteLine("Build Index time: {0:0.00} msec", timer.Elapsed.TotalMilliseconds);


        Console.WriteLine("\n\n\nQuery Test (indexed):");
        timer.Restart();

        foreach (string value in (from x in list1 where x == "888365" select x)) 
            Console.WriteLine("find: {0}", value);

        foreach (string value in (from x in list1 where x == "663867" select x)) 
            Console.WriteLine("find: {0}", value);

        foreach (string value in (from x in list1 where x == "555600" select x)) 
            Console.WriteLine("find: {0}", value);

        foreach (string value in (from x in list1 where x == "888824" select x)) 
            Console.WriteLine("find: {0}", value);

        Console.WriteLine("Query time: {0:0.00} msec", timer.Elapsed.TotalMilliseconds);

        
        
        Console.WriteLine("\n\n\nQuery Test (non-indexed):");
        timer.Restart();

        foreach (string value in (from x in list2 where x == "888365" select x)) 
            Console.WriteLine("find: {0}", value);

        foreach (string value in (from x in list2 where x == "663867" select x)) 
            Console.WriteLine("find: {0}", value);

        foreach (string value in (from x in list2 where x == "555600" select x)) 
            Console.WriteLine("find: {0}", value);

        foreach (string value in (from x in list2 where x == "888824" select x)) 
            Console.WriteLine("find: {0}", value);

        Console.WriteLine("Query time: {0:0.00} msec", timer.Elapsed.TotalMilliseconds);
    }

    private static IEnumerable<string> SeqGenerator(int count)
    {
        for (int i = 0; i < count; i++) yield return i.ToString();
    }

    private static IEnumerable<string> RndSeq(int seed, int count)
    {
        Random rnd = new Random(seed);
        foreach (string value in (from x in SeqGenerator(count) orderby rnd.Next() select x)) yield return value;
    }
}

而程式執行的結果:

貼一下參考配備 (這是炫耀文…)，給大家體會一下速度…

CPU: INTEL i7 2600K, INTEL Z68 主機板 RAM: 8GB OS: Windows 7 (x64)

看起來藉著 HashSet 當索引，來加速 LINQ 查詢的目的已經達到了。不加索引需要 2147.83 ms, 而加上索引只需要 2.19ms … 兩者時間複雜度分別是 O(1) v.s. O(n), 要是資料的筆數再往上加，兩者的差距會更大…

回過頭來看看程式碼吧! 關鍵在 LINQ 的 Extension 上面:

支援索引的 LINQ extension: where( )

public static IEnumerable<string> Where(this IndexedList context, Expression<Func<string, bool>> expr)
{
    if (expr.CanReduce == false "" expr.Body.NodeType == ExpressionType.Equal)
    {
        BinaryExpression binExp = (BinaryExpression)expr.Body;
        string expectedValue = (binExp.Right as ConstantExpression).Value as string;
        if (context._index.Contains(expectedValue)) yield return expectedValue;
    }
    else
    {
        //return context.Where(expr);
        foreach (string value in context.Where(expr)) yield return value;
    }
}

line 1 的宣告，限制了只有對 IndexedList 型別的物件，下達 WHERE 語句的情況下，才會交由你的 extension method 執行。而 Microsoft 會把整個 where 語句，建構成 Expression 這型別的物件。

前面我下的一堆條件，像是只能用 == 運算元，只針對字串常數比對等等，就都寫在 line 3 的判段式了。基本上只要不符合這些條件，就會跳到 line 12, 索引等於完全無用武之地了。

要是符合使用索引的條件，則程式會進到 line 5 ~ line 7.  程式會透過 HashSet 去檢查要找的 data 是否存在於 List 內? 前面提過了，用 HashSet.Contains(...) 來檢查 (O(1))，效能遠比 List<string>.Contains(...) 的效能 (O(n) ) 好的多。

實驗的結果到此為止，很明顯了，索引的確發揮出效果了，不過老實說，這段 code 真的沒什麼實用的價值… 哈哈，與其這樣繞一大圈，用 LINQ 很帥氣的查資料，還不如直接用程式找 HashSet 就好… 這只是證明 it works, 不繼續完成它，主要的原因是已經有人做了，而且做的比我好 XD! 需要的人可以參考看看 i4o 這套 library. 想體會這東西怎麼用，可以先看看作者的 BLOG，這篇是使用範例:

http://staxmanade.blogspot.com/2008/12/i4o-indexspecification-for.html

要下載的話，它的 project hosted 在 codeplex: http://i4o.codeplex.com/

2011/10/25 C# 技術隨筆 物件導向