Onion and pizza: new disk partitioning schemes for virtualization systems

發表: SAC '13 Proceedings of the 28th Annual ACM Symposium on Applied Computing


The traditional disk partitioning scheme commonly used in a virtualization system divides a disk into multiple partitions in a coarse-grained manner, which causes a long seek distance when multiple virtual machines run concurrently. To overcome this drawback, we propose two novel schemes, called onion and pizza. The onion scheme makes partitions in an interleaved way, which leads to not only reduce a seek distance but also enhance fairness among virtual machines. The pizza scheme goes one step further that makes partitions in a vertical fashion, not a horizontal fashion, so that requests from different virtual machines can be served in a same cylinder. In additional, new sector mapping is devised for efficiency of the two schemes. Real implementation based experiments have shown that our proposal can enhance I/O bandwidth up to 95% with an average of 25%, compared with the traditional scheme.

原本 vm的disk partition 都要一整塊相連，如果很多vm，disk seek 可能很長 (例，disk head先被vm1拉走，然後vm4又發出 io request，但是vm4的partition離 vm1很遠~遠 )

他的方法就是
從coarse-grained manner的allocation方法，變成fined-grained (大塊 變 小塊啦啦)，再把 這一小小堆平均散開在整個disk中。依照散開的方法又分成 onion 和 pizza兩種 ，一個是水平地散(同磁盤)，一個是垂直地散

SH:
1 大塊變小塊什麼overhead嗎
2 怎麼散才能保証一定縮短 seek啊? 會不會反而更長 ?
3 有使用replication嗎，replication也是一種縮短seek的方法?  相比之下，有去分析優缺嗎?

Error-correcting codes 錯誤更正碼，ECC，BCH

A想傳送"1"給B，但是怕bit-flip，這時候就是 Error-correcting codes (ECC) 登場的機會啦。

首先，先把"1"(稱作message)用 coding 加以保護 (方法有很多種，先用 Repetition Coding 當範例)，經 Repetition Coding 之後 "1" 變成 "111" (稱為codewords) ，這樣當B收到101，就會猜想中間的"0"應該是bit-flip。

如果運氣很差，剛好flip兩個bits (變成100) 怎麼辦? 那就沒救了，將會判斷成收到 0's。
想要這種出錯率降底的話，就把"1" 變成 "1111111111111.....11111111"
越多越爽，但傳輸率(效能)就爛到哭。

總之，是有tradeoff的，Repetition Coding 很鳥，用來當範例方便而以。有機會(or never)再介紹其他比較威風的 ECC，像是BCH或是LDPC。













腦補-------------------------------------

A BCH code with a higher error-correcting capability (and higher overhead) is the [8360, 8192, 12] code, which can correct 5 errors or detect 11 errors.

8360是codewords
8192是message
所以redundancy的部份就是 8360 - 8192 = 168
多了這168 bits，傳輸變成原本的 8192/8360 = 0.979倍

Improving NAND Endurance by Dynamic Program and Erase Scaling

paper sharing:
title: Improving NAND Endurance by Dynamic Program and Erase Scaling
where: HotStorage13

------------------------------------------------------------------------------
1. flash的endurance和program時用的電壓有關~ (電壓越大~命越短)
2. 承上，所以program speed和endurance就是一個tradeoff囉。(電壓越大寫越快)
3 他就弄了一個FTL叫 DPES-FTL (dynamic program and erase scaling (DPES))，希望可以提高endurance而又不要害到write speed太多

how ? 
→ 兩個write req之間的idle time時用小電壓

如何知道會有idle time?
→ by estimation

contributions
1. endurance-programSpeed model
2. DEPS-FTL

ioMemory virtual storage layer

http://www.fusionio.com/overviews/vsl-technical-overview/ 轉


 有了virtual memory subsystem，當main meory不足夠的時候可以把某些 "page” swap出到secondary storage，
通常是HDD; 如今SSD開始進攻，此 subsystem也該做一下最佳化了吧~~

yes, fusion IO did it as followed:

@ 原本的page table 變成 block table 。
另外這個translation的動作也從 device 移到 host上去做。

---------片段----

With the addition of VSL, the Fusion ioMemory architecture now brings the full disruptive potential of solid state memory to the enterprise.

A HYBRID ARCHITECTURE

Fusion's VSL is a flash-based subsystem to accelerate today's enterprise-class operating systems. It virtualizes NAND flash arrays, combining key elements of the two pillars of modern operating systems: the I/O subsystem and the virtual memory subsystem.

VSL combines the advantages of a virtual memory architecture with a transactional file system approach on an array of NAND flash.

I/O SUBSYSTEM EMULATION

The I/O subsystem in today's operating systems includes a common interface for block-based applications, such as file systems, volume managers, and applications, to access persistent data (storage). VSL utilizes this block interface to present ioMemory modules (i.e. ioDrives) to the operating system as easily accessible block-based storage that existing file systems, volume managers, and applications can use just like a conventional disk.

VIRTUAL MEMORY SUBSYSTEM EMULATION

The virtual memory subsystem abstracts logical data addresses from their physical location by creating a directory of data locations. In modern OSs, a 64-bit virtual address space is used to organize and partition data used by the applications and users. Below this virtual address space lays the physical RAM, which has a much smaller address space. Operating systems and applications use this virtual interface to RAM (called the page table) to look up the physical location of data using a directory rather than requiring massive quantities of RAM just to satisfy each application's memory address space.

Similar to page tables in the host virtual memory subsystem, VSL virtualizes Flash via "block tables." VSL translates block requests to physical ioMemory addresses, also analogous to the virtual memory subsystem. It's important to note that these block tables are stored in host memory. This is a key advantage over other solid-state architectures (e.g. SSDs) that store block tables only in embedded RAM, where block tables are accessible only behind legacy storage protocols.

KEY BENEFITS OF VSL

• Direct storage Access. With VSL, the CPU seamlessly interacts with ioMemory as though it were just another memory tier below DRAM. VSL provides direct access from each CPU core to the Flash media across the system bus, independent of other cores, and in parallel. This access results in extremely low latency, near linear performance scaling, and minimal performance degradation with mixed read/write workloads.

Without VSL, SSDs must serialize access through RAID controllers and use embedded processors to perform block mapping. As data is copied and re-copied through multiple layers of memory and embedded processors, the result is unnecessary context switching, queuing bottlenecks, and I/O storms, which all increase latency.

Linux Driver 思考 轉from http://dicky-chiang.blogspot.com/2011/03/linux-driver.html

Linux Driver 思考

剛突然找一篇很不錯的文章,雖然字數很少,但裡面的內容讓我有種被啟發的感覺...

====================

傳統意義上的Linux Driver僅僅是設備驅動，簡言之，和設備有關，如LCD，Camera等等。 但是， 筆者認為，Linux Driver的作用不僅僅侷限於此，從廣義上講， Linux Driver提供了一種User Space訪問 Kernel中特定Function的通用編程模型，即，平民（User Space中的Application， Process， Lib等）通向皇宮（Kernel）的大道。

如果一個模塊提供的Function必須運行於Kernel Space中（可能是設備相關的Function，從而需要訪問特權指令或者特權地址空間； 抑或者Function本身是設備無關的，但是訪問到了其他的一些運行於Kernel的Function； 甚至於吃飽了沒事幹，就喜歡把原本可以在User Space中運行的API實現在Kernel中，就是喜歡，你管的著嗎？！）。 同時，又希望User Space中的Client能訪問使用這些Function， 那麼， 將其Adapt成Driver是再合理不過的解決方案了。 這是為什麼那？？

因為，從理論上來說，Kernel中的API，User Space中的Client是無法直接訪問的，只能利用系統調用陷入到內核態後調用。 Linux的系統調用非常多，均已經固定， 如何支持新的Kernel Function的調用那？ 有兩種方式：

1。 在Kernel中實現一個新的系統調用（添加新的系統調用號），用來支持你實現的新功能。 這真是殺雞用牛刀的幹活，吃力不討好。 你需要全全負責User Space到Kernel Space的切換，系統調用號的傳遞，系統調用上下文的保存， 調用後的系統上下文的恢復，Kernel Space向User Space的切換。

2。 復用一個現有的系統函數/調用，來支持你的新功能。 具有抽象意義的系統調用莫過於read，write，open這些為Driver定製的API了。 所以，我們可以簡單的將我們的Function Wrapper成Driver需要的open，read，write等，然後，再按照Driver的要求，將我們的Module Wrapper成一個Driver的設備文件並註冊到系統中。 這樣，User Space中的Client，可以採用傳統的Driver的模式來間接訪問到我們新加的這些Function，並且，可能這些Function根本和實際的設備沒有任何聯繫。

所以，我們不應該把Linux的Driver狹義的理解為設備驅動， 其實，它是一種通用的User Space訪問Kernel Space Function的編程模式。 只要你有這種需求，你就可以實現為Driver，而不需要關心和實現複雜的系統調用過程。 比如Android中的Binder Driver， 根本不是真正的和物理設備打交道， 而僅僅是一個運行於Kernel的Binder Function，但是適配成了Driver，方便User Space中的Client調用。

embedded linux pirmer 2nd edition 研讀 chapter 10.1 MTD

10.1 MTD overview
1.MTD不是一個blk device
2.blk device有 read/write, 而MTD有read/write/erase
3.CF card, SD card, USB flash 都不是MTD device，它們都有FTL(它們看起來就像是blk device)
4.Translation mechanisms can make MTD look like a character or block device

MTD , flash , 觀念修正

1.所謂的 nand flash controller ...裡面好像沒有 micro-processor ?

2.what is the relation between  NFC, MTD ?

3.----轉---
假設你有flash(在embedded system幾乎都有)首先, 先K一下flash的spec. 看看read/write/erase的command sequence(每一家的flash都不一樣). 再來看看你的flash是要用8-bit or 16-bit的bus-width, 其command sequence也不一樣. 接下來, 看看linux的MTD chip driver有沒有支援, 若有支援確無法work, 八成是bus-width的設定問題. 另外也要看看你的flash是support CFI or JEDEC or non-CFI interface. 不同的類型也使用不同的chip driver. 
最後, 規劃自己的mapping driver(也就是flash上的partition table, 因為flash不像硬碟會存partition table) 這要自己來, 否則linux怎麼知道你要如何規劃flash? linux是依賴註冊mapping driver來得知partition table information的. 

大約就是如此, 前陣子改了AMD的flash chip driver來支援. 所以才有一點小小的心得. 跟大家分享
-------------


4.http://translate.google.com.tw/translate?hl=zh-TW&sl=zh-CN&u=http://www.cnblogs.com/jinmu190/&ei=uDC_TePMGIW8vgOEg-y6BQ&sa=X&oi=translate&ct=result&resnum=4&ved=0CDwQ7gEwAw&prev=/search%3Fq%3Dftl%2Bblock%2Bdevice%26hl%3Dzh-TW%26rlz%3D1C1CHNY_zh-TWTW376TW376%26prmd%3Divns
必看網址


5， MTD 裡面有 simple FTL (mdtblock)，應該是block mapped的FTL。

6. CF card , SD card , USB flash這些東西…雖然也常被叫作 "flash" ，但它們不是 MTD，因為他們有FTL，可直接視作block device，才不會和MTD搞混

續上篇 How Storage I/O Control Works

1.VMware的 sioc 是如格偵測 IO congestion ?
→ latency 超過threshold 時 (default : 30ms)


2. 『This is to ensure that low-priority workloads do not monopolize
or reduce I/O bandwidth for high-priority workloads』中的high low priority怎分???


3.soic怎麼應對low-priotiry workloads ?
→ 減少 他的 io queue slot 

續上篇_ The Challenge of Shared Resources

Controlling the dynamic allocation of resources in distributed systems has been a long-standing challenge. Virtualized environments introduce further challenges because of the inherent sharing of physical resources by many virtual machines.
『動態resource分配』在分散式系統中原本就是個挑戰，然而，此挑戰在VM的環境更明顯（天生需要共用physical resource）
VMware has provided ways to manage shared physical resources, such as CPU and memory, and to prioritize their use among all the virtual machines in the environment. CPU and memory controls have worked well since memory and CPU resources are shared only at a local-host level, for virtual machines residing within a single ESX® server.
The task of regulating shared resources that span multiple ESX hosts, such as shared datastores, presents new challenges, because
these resources are accessed in a distributed manner by multiple ESX hosts. Previous disk shares did not address this challenge, as the shares and limits were enforced only at a single ESX host level, and were only enforced in response to host-side HBA bottlenecks,
which occur rarely. This approach had the problem of potentially allowing lower-priority virtual machines greater access to storage resources based on their placement across different ESX hosts, as well as neglecting to provide benefits in the case that the datastore
is congested but the host-side queue is not. An ideal I/O resource-management solution should provide the allocation of I/O resources independent of the placement of virtual machines and with consideration of the priorities of all virtual machines accessing the shared datastore. It should also be able to detect and control all instances of congestion happening at the shared resource

應該考慮到VMs的"priority" 來決定IO resource 的分配。

翻譯 『Storage I/O Control Technical Overview and Considerations for Deployment』 第一段

Storage I/O Control (SIOC) 讓VM可以達到performance isolation，它讓VM中著名的noisy neighbor的問題大大降低。更棒的是…他可以暫時提高"critical"的VM的IO resource allocation。



SIOC improves upon the previous host-level I/O scheduler by detecting and responding to congestion occurring at the array
經過host-level IO scheduler的最佳化後，SIOC緊接著派上用場(它會偵測並回應storage的congestion的情形)



With SIOC, vSphere administrators can mitigate the performance loss of critical workloads due to high congestion and storage latency during peak load periods





Benefits of leveraging SIOC:
• Provides performance protection by enforcing proportional fairness of access to shared storage
• Detects and manages bottlenecks at the array 
• Maximizes your storage investments by enabling higher levels of virtual-machine consolidation across your shared datastores
The purpose of this paper is to explain the basic mechanics of how SIOC, a new feature in vSphere 4.1, works and to discuss 
considerations for deploying it in your VMware virtualized environments

SIOC的好處:
1.達成"比例上的公平"→ 越多io的VM給越多io resource (?)
2.偵測，管理 array上的bottlenecks
3.善用virtual storage