-
[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 我也依過去的經驗大致預估看看。依這些假設，就可以來評估各種資料層的處理方式，會有啥問題。
以下是一般的應用，每個用戶需要的資料規模 (假設):
平均數量 資料表 (table) 500 物件 (Sql obj, 如 table, view, trigger, function… etc) 5000 資料筆數 (rows per table) 100000 總容量 (data size) 5GB 1. 能容納的用戶量限制
以 SalesForce.com 為例，它會為每個 "公司" 開設一個專區，接著看該公司買了多少帳號，就開幾個 User Account。這裡的 "公司" 就是一個用戶，也就是 Multi-Tenancy 裡指的 "Tenancy”。這用戶的數量合理的數量應該是多少? 而系統的理論上限又是多少?
實際運作當然還有軟硬體搭配跟效能問題，這理就先就 "理論上限" 來探討。理論上限值，應該要在任何情況都足夠使用才合理。我特地去挖了 Microsoft SQL Server 的各種物件的數量上限，下表是從官方資料 整理出來的，以目前最新的 SQL 2012 為準，單一一套 SQL SERVER 可以:
數值名稱 最大上限 Database size 524272 TB Databases per instance 32767 Instance per computer 50 Tables per database 2147483647
(所有database objects總數上限)User connections 32767 看起來，最需要注意的就是 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 ..
-
[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, 若對隔離及安全性要求越高，就要在越底層就做到隔離的機制。
- Separated DB
最高隔離等級，就是每個客戶一個 database (Separated DB)。用這種模式，再怎麼粗心的工程師，也不會不小心把別的客戶的資料給秀出來。舉個例，系統內的A客戶，就會連到A資料庫，B客戶就用B資料庫。每個客戶的資料庫各自獨立，不會互相打架。
- Separate Schemas (Shared Database)
這種作法比第一種 Separated DB 好一點，它共用同一個 DB，但是替每一個客戶建立一組 Tables。這種作法不需要那麼高的成本 (看過 $$ 就知道，資料庫很貴的….)，多個客戶可以共用資料庫，不過因為 Schema 的層級隔離了，簡單的說不同客戶的 Table Name 是不一樣的，因此粗心的工程師造成客戶資料混在一起的機率也不算高，還有不錯的隔離機制。
這方式實作有點辛苦，不過 SQL 2005 之後開始支援 Schema 這機制，實作上可以簡單的多。
- 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
- Separated DB
-
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);
-
[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 簡短到一眼就看的懂的程度，我的目標定在:
- 查詢對相只針對
List<string>處理，不做泛型及自訂索引欄位。 - 查詢只針對
==做處理。如下列 LINQ 語句的 where 部份:from x in list1 where x == "123456" select x - 條件只限於
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 的作法真不錯用，借兩招來試試… 程式大概執行這幾個步驟:
- 準備 10000000 筆資料，用亂數打亂，建立 list1 (含索引, type:
IndexedList) 及 list2 (不含索引, type:List<string>) - 呼叫
list1.ReIndex(), 替 list1 重建索引 (HashSet), 記錄建立索引花費的時間 - 分別對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/
- 查詢對相只針對
-
[CODE] 可以輸出到 TextBox 的 TextWriter: TextBoxWriter!
吃葡萄不吐葡萄皮... 對，這不是繞口令... 哈哈...。
先祝各位 2011 新年快樂!! 這幾個月忙翻了, 一方面系統要移轉到 windows azure, 另一方面要改善原本系統的排程 (原本是 console app + scheduler task service), 現在要用 windows service 來取代, 突然之間之前覺的工作上用不到的 multi-threading 技巧, 現在都派上用場了...
題外話先扯一下, 在 azure 因為架構上就已經把 web role (presentation layer) / worker role (business logic layer) / azure storage (data layer) 分的很清楚, 相對的每一層之間的 communication 時間就拉長了, 我們碰到的狀況就是 worker role 對 azure storage 有大量的 I/O 的話, 效能就很糟糕... 在這邊用了生產線的模式, 結果效能提升了十幾倍... 果然前輩說的沒錯: 架構對了，什麼事都變簡單了...
另一個案例則是把原本靠 windows task scheduler 執行的排程，改成用自行開發的 windwos service ... 不過開發成 service 實在是不大好除錯, 再加上多執行緒先天也是除錯不易... 因此開發階段都寫成windows form, 提供 START / STOP / PAUSE / CONTINUE 等控制的功能，簡化前段的開發作業。
azure / service 都用到了不少多執行緒的技巧, 改寫成 service 也用了老字號的 Cassini 解決另一部份的問題，這些都是值得介紹一下的部份，不過今天主題不在這，改天另起專欄再說。在改寫成 windows service 的過程中，需要把過去寫成 Console application 的 code 移到 service ，而過去這些程式都直接用 Console.Out 這個 TextWriter 輸出訊息到 DOS command prompt / log file, 移到 windows form 之後, 要輸出到 TextBox 就變的麻煩了點, 本來不想理它, 後來發現不好好處理這個問題還不行...
如果不講究 code 好不好看，其實改一下程式就可以了，把原本的 Console.Out.WriteLine( ) 改成 TextBox.AppendText( ) 就好，但是...
- 原程式得改寫，不能直接用 TextWriter ... 另外, 很多現有的函式庫都接受 TextWriter, 不能靠 TextWriter 輸出的話程式會變很雜
- 只有 create control 的 UI thread 可以呼叫 AppendText( ) ...
- thread-safe 的問題: 輸出的訊息會交錯輸出, 無法閱讀
- 長時間連續執行，TextBox 的訊息會太多, 得要有 recycle 的機制
- 最好可以順便寫 LOG 檔...
老實說，除了 (1) 之外，其它點都是自己寫個專用的 OutputLog method 就可以解決。不過考量到程式未來真正執行時，是在 service 的環境, 在那邊是沒有 TextBox 這種 UI control 的, 最終還是要透過 TextWriter 輸出到 log file, 或是透過 socket 輸出... 何況用 TextWriter 輸出 log 也比較符合抽象化的原則, 不需要去碰到太多輸出方式的細節...
問題跟目的都搞清楚之後，接下來就是實作了。這次實作目標就是要想個辦法，用 TextWriter 的方式輸出 LOG 訊息，而這些訊息要自動呈現在 WebForm 的 TextBox control 上, 就好像在 DOS command prompt 裡執行 console application 一樣。先來想像一下 code 寫起來跟看起來是什麼樣子:
[copy code]1: private TextWriter output;
2: public Form1()
3: {4: InitializeComponent();5: this.output = TextWriter.Synchronized(new TextBoxWriter(this.textBox1));
6: }7: private void Form1_Load(object sender, EventArgs e)
8: {9: for (int i = 0; i < 300; i++)
10: {11: this.output.WriteLine("{0}. Hello!!!", i);
12: }13: }建立好 TextWriter 之後，後面只管用這 writer 輸出訊息，對應的 TextBox 自然就會像 terminal 般，不斷的跑出訊息出來...
基本要求達到了，這就是我要的功能。其實這東西上網 GOOGLE 一下, 類似的例子也有, 不過一來寫起來沒幾行, 二來功能跟我要的有點出入... 想想還是自己寫一個。先來看看這個 writer 是怎麼實作的?
TextWriter 要實作並不難，不過不熟悉的話，也是得花些時間才能搞定。主要是 TextWriter 的 Writer( ) 跟 WriterLine( ) 就共有 35 種不同的多載... HELP 沒有清楚的寫到這堆 method 之間的關係，一時也不知 override 那一個的效果是最好的...。一開始我是從最基本的 void TextWriter.Write(char value) 下手, 結果效能慘不忍睹... 輸出一行字就要一秒鐘, 好像回到了當年DOS時代加上倚天中文後, 按個DIR字是一行一行跑出來的光景... Orz, 後來花了點時間追蹤這卅幾個 method 的先後關係，才改了這個效能 OK 的版本:
[copy code]1: public class TextBoxWriter : TextWriter
2: {3: private TextBox _textbox;
4: public TextBoxWriter(TextBox textbox)
5: {6: this._textbox = textbox;
7: }8: public override void Write(char value)
9: {10: this.Write(new char[] { value }, 0, 1);
11: }12: public override void Write(char[] buffer, int index, int count)
13: {14: if (this._textbox.InvokeRequired)
15: {16: this._textbox.Invoke((Action<string>)this.AppendTextBox, new string(buffer, index, count));
17: }18: else
19: {20: this.AppendTextBox(new string(buffer, index, count));
21: }22: }23: private void AppendTextBox(string text)
24: {25: this._textbox.AppendText(text);
26: }27: public override Encoding Encoding
28: {29: get { return Encoding.UTF8; }
30: }31: }其中補充說明一下, 在 line 14 ~ 21 為何要大費周章的, 把要呼叫 AppendTextBox( ) 的動作, 放到 delegate, 再交由 TextBox 控制項自行 Invoke 呼叫 ? 這是源自 windows form 的一條規範, 要是你寫的程式有多執行緒的應用，一定要知道這鐵律:
UI thread 的限制: 只有 create control 的 thread 可以更動 control 的狀態。
如果不遵守這個規則，執行時就會被警告:
解法就參考 line 14 ~ 21 的部份就好，說明的話 darkthread 這篇講的很清楚, 我就不客氣直接引用了 :D
不過，這樣只是達到基本需求而已，還有其它的問題... (3 ~ 5), 太久沒寫文章了，沒想到一篇寫不完... 請待下回分解 :D
