Soma-notes - User contributions [en]

Talk:COMP 3000 Essay 2 2010 Question 6

2010-12-02T13:32:27Z

Abujaki:

Alright so its due tomorrow. I was hoping to get an idea of when everyone will be posting there completed sections thanks. --[[User:Azemanci|Azemanci]] 03:56, 2 December 2010 (UTC)

'''Actual group members'''

- Nicholas Shires nshires@connect.carleton.ca

- Andrew Zemancik andy.zemancik@gmail.com

- [[user:abondio2|Austin Bondio]] -> abondio2@connect.carleton.ca

- David Krutsko :: dkrutsko at connect.carleton.ca

- Andrew Bujaki ==> abujaki [at] connect.carleton.ca

If everyone could just post their names and contact information.--[[User:Azemanci|Azemanci]] 02:57, 15 November 2010 (UTC)

IMPORTANT 
THINGS WE NEED TO DEFINE: 
* Happens-before reasoning
* Lock-set based reasoning
* Hardware Breakpoints 
The prof seemed to be very focused on hardware breakpoints, so it is very important to define it well, and talk about it often, it looks like hardware breakpoints are the one thing thats setting DataCollider apart from other race detectors, so lets focus on it! 
IMPORTANT 

'''Who's Doing What'''

=Research Problem=
I'll do 'Research Problem' and help out with the 'Critique' section, the professor said that part was pretty big [[User:Nshires|Nshires]] 20:45, 21 November 2010 (UTC)

The research problem being addressed by this paper is the detection of erroneous data races inside the kernel without creating much overhead. This problem occurs because read/write access instructions in processes are not always atomic (e.g two read/write commands may happen simultaneously). There are so many ways a data race error may occur that it is very hard to catch them all.

The research team’s program DataCollider needs to detect errors between the hardware and kernel as well as errors in context thread synchronization in the kernel which must synchronize between user-mode processes, interrupts and deferred procedure calls. As shown in the Background Concepts section, this error can create unwanted problems in kernel modules. The research group created DataCollider which puts breakpoints in memory accesses to check if two system calls are calling the same piece of memory. There have been attempts at a solution to this problem in the past that ran in user-mode, but not in kernel mode, and they produced excessive overhead. There are many problems with trying to apply these techniques to a kernel.

One technique that some detectors in the past have used is the “happens before” method. This checks whether one access happened before another or if the other happened first, and if neither of those options were the case, the two accesses were done simultaneously. This method gathers true data race errors but is very hard to implement.

Another method used is the “lock-set” approach. This method checks all of the locks that are held currently by a thread, and if all the accesses do not have at least one common lock, the method sends a warning. This method has many false alarms since many variables nowadays are shared using other ways than locks or have very complex locking systems that lockset cannot understand.

Both these methods produce excessive overhead due to the fact that they have to check every single memory call at runtime. In the next section we will discuss how DataCollider uses a new way to check for data race errors, that produces barely any overhead.
http://www.hpcaconf.org/hpca13/papers/014-zhou.pdf

Moved from main page: (p.s thanks for the info!)[[User:Nshires|Nshires]] 02:32, 2 December 2010 (UTC)

Just a few rough notes:
Research problem / challenges for traditional detectors:

- data-race detectors run in user mode, whereas operating systems run kernel mode (supervisor mode).

- There are a lot of different synchronization methods, and a lot of ways to implement them. So it's nearly impossible to try and code a program that can catch all of them.

- Some kernel modules can "speak privately" with hardware components, so you can't make a program that just logs all the kernel's interactions.

- traditional data race detectors incur massive time overheads because they have to keep an eye on every single memory transaction that occurs at runtime.

--[[User:Abondio2|Austin Bondio]] 01:57, 2 December 2010 (UTC)

=Contribution=
What are the research contribution(s) of this work? Specifically, what are the key research results, and what do they mean? (What was implemented? Why is it any better than what came before?)

Proving that there is a problem in classic solutions to race detectors: 
The main contribution that DataCollider provides is the unique idea of using hardware breakpoints in a data race detector. The question is why is a unique idea necessary. Why does DataCollider have to "reinvent the wheel". There has been a plethora of race condition testers invented in the last two decades, and all of the dynamic data race detectors can be lumped into three categories. They can either be lock-set, happens-before, or a hybrid of the two types of detection. The research team for DataCollider looked at several of these implementations of race condition testers to find ways of improving their own program, and to see that there are major problems in the classic ways of detecting race conditions. 

Some of the programs that were referenced were: 

* Eraser: A Dynamic Data Race Detector for Multithreaded Programs 
* RaceTrack: Efficient Detection of Data Race Conditions via Adaptive Tracking 
* PACER: Proportional Detection of Data Races 
* LiteRace: Effective Sampling for Lightweight Data-Race Detection 
* MultiRace: Efficient on-the-fly data race detection in multithreaded C++ programs 

Eraser: A Dynamic Data Race Detector for Multithreaded Programs[http://delivery.acm.org/10.1145/270000/265927/p391-savage.pdf?key1=265927&key2=7323721921&coll=DL&dl=ACM&CFID=116768888&CFTOKEN=55577437]
 
lock-set based reasoning 

Eraser, a data race detector programmed in 1997, was one of the earlier data race detectors on the market. It may have been a useful and revolutionary program of its time, however, it uses very low level techniques compared to most data race detectors today. One of the reason why it is unsuccessful is because it only checks whether memory accesses use proper locking techniques. If a memory access is found that does not use a lock, then Eraser will report a data race. In many cases, the misuse of proper locking techniques is a conscious decision by the programmer, so Eraser will report many false positives. This also does not take into account all of the benign problems such as date of access variables. DataCollider used this source as an example of a lock-set based program, and why they are a poor choice for a race condition debugger. 

PACER: Proportional Detection of Data Races[http://www.cs.ucla.edu/~dlmarino/pubs/pldi09.pdf] 
happens-before reasoning 
Pacer, a happens-before reasoning data race detector, uses the FastTrack algorithm to detect data races. FastTrack uses vector-clocks to keep track of two threads, and find whether or not they are conflicting in any way. Pacer samples some percentage of each memory access, (from 1 to 3 percent) and runs the FastTrack happens-before algorithm on each thread that accesses that part of memory. DataCollider used this source as an example of the implementation of sampling. Similar to Pacer, DataCollider samples some memory accesses, but instead of using vector-clocks to catch the second thread, they use hardware break points. Hardware break points are considerably faster, and cause DataCollider to run much faster than Pacer. 

LiteRace: Effective Sampling for Lightweight Data-Race Detection[http://www.cs.ucla.edu/~dlmarino/pubs/pldi09.pdf] 
happens-before reasoning 
LiteRace, similar to Pacer, samples a percentage of memory accesses from a program. Where it differs is the parts of memory that LiteRace samples the most. The "hot spot" regions of memory are ones that are accessed most by the program. Since they are accessed the most, chances are that they have already been successfully debugged, or if there are data races there, they are benign. LiteRace detects these areas in memory as hot spots, and samples them at a much lower rate. This improves LiteRace's chances of capturing a valid data race at a much lower sampling rate. Where DataCollider bests LiteRace is based on LiteRace's installing mechanism. LiteRace needs to be recompiled into the software it is trying to debug, whereas DataColleder's breakpoints do not require any code changes to the program. This is a major success for DataCollider because often third party testers do not have the source code for a program. 

RaceTrack: Efficient Detection of Data Race Conditions via Adaptive Trackings[http://delivery.acm.org/10.1145/1100000/1095832/p221-yu.pdf?key1=1095832&key2=8433721921&coll=DL&dl=ACM&CFID=116768888&CFTOKEN=55577437] 
combination of lock-set and happens-before reasoning 

RaceTrack uses a unique technique in order to detect data races. The program being debugged is run on top of RaceTrack as a virtual machine using the .NET framework, and it will examine all of the memory accesses that the program requests. As soon as suspicious behavior is exhibited, a warning is sent off to be later evaluated when the program terminates. RaceTrack uses this technique because several process intensive inspections of the state of the machine must be checked, and doing this on the fly is expensive. There are many problems with RaceTrack. It is very successful at detecting a vast percentage of data races, however, it has a high overhead and requires extreme amounts of memory. RaceTrack must save the state of the entire machine every time a warning is produced, and it also has to save each threads memory accesses to check which memory access "happened before". Since most warnings thrown are found to be benign, saving the state of the machine wastes computational power and memory. Long running programs also prove to be a problem, where the computer being debugged will run out of memory to store all of the warning states before the program terminates. It then will have to either increase overhead significantly to store the warnings on disk, or it will have to delete some warnings to make room for new ones. 

MultiRace: Efficient on-the-fly data race detection in multithreaded C++ programs[http://docs.google.com/viewer?a=v&q=cache:C8gWk-H3GmEJ:citeseerx.ist.psu.edu/viewdoc/download%3Fdoi%3D10.1.1.73.9551%26rep%3Drep1%26type%3Dpdf+MultiRace:+Efficient+on-the-fly+data+race+detection+in+multithreaded+C%2B%2B+programs&hl=en&gl=ca&pid=bl&srcid=ADGEESj1jYlzXMOwgbh7SVntUsHxVeI1TvmkU8Oslkm-L9gq-NIyglj5eD48rtkcziUQUynmjOmZojsyzw_tBRiLN6T0n6iiDZyUiFjBUfLijQbzNsRpDQCsMpn-xTiIqK2PUj4DXwoM&sig=AHIEtbRBHpMvb5fel3XOi5oASAogumY-rg] 
combination of lock-set and happens-before reasoning 

MultiRace is another hybrid style race condition debugger that uses two unique algorithms. The first algorithm, Djit is the happens-before iteration, which INSERT STUFF HERE. The second is an improved iteration of the lock-set algorithm. MultiRace is the most similar program to DataCollider in terms of their goals. Both strive to decrease overhead to near standard running times of the program itself, and to increase the program transparency for maximum user compatibility. MultiRace itself is several orders of magnitude more complicated than DataCollider, but since MultiRace hides its complexity from the user with transparency, it is still simple to use. It is arguable that MultiRace is superior for detecting races for C++ programs, however, MultiRace is not compatible with any other programming language. Since DataCollider uses hardware breakpoints, the coding language of the program is irrelevant. Also, since DataCollider avoids using both lock-set and happens before algorithms, it is versatile enough to even debug kernels. 

DataCollider is a very unique program. Most other dynamic race condition testers can be lumped into the three groups lock-set, happens-before, or hybrid. DataCollider, however, recognizes the errors of these styles of detection, and manages to avoid them completely. Even though there are issues with false positives and benign races, DataCollider provides very simple, versatile, and lightweight functionality in debugging a program. Future programs may take this unique style of race detection and add their own functionality to improve upon it. It could be that DataCollider could inspire a ground breaking solution to race conditions and how to detect them.

=Background Concepts=
Hey guys, sorry I'm late to the party. I'll get started with Background Concepts. - [[user:abondio2|Austin Bondio]] 15:33, 23 November 2010 (UTC)

=Critique=

I'll work on the critique which will probably need more then one person and I'll also fill out the paper information section.--[[User:Azemanci|Azemanci]] 18:42, 23 November 2010 (UTC)

DataCollider:
DataCollider seems like a very innovative piece of software. It’s new use of breakpoints inside kernel-space instead of lock-set or happens-before methods in user-mode let it check data race errors in the very kernel itself without producing as much overhead as its old contenders (it even finds data races for overheads less than five percent). One thing to note about DataCollider is that ninety percent of its output to the user is false alarms. This means that after running DataCollider, the user has to sift through all of the gathered data to find the ten percent of data that actually contains real data race errors. The team of creator’s were able to create a to sort through all of the material it collects to only spit out the valuable information, but the creators still found some false alarms in the output . They have noted though that some users like to see the benign reports so that they can make design changes to their programs to make them more portable and scalable and therefore decided not to implement this. Even though DataCollider returns 90% false alarms the projects team have still been able to locate 25 errors in the Windows operating system. Of those 25 errors 12 have already been fixed. This shows that DataCollider is an effective tool in locating data race errors within the kernel effectively enough that they can be corrected.

feel free to add/edit anything [[User:Nshires|Nshires]] 02:54, 2 December 2010 (UTC)

Right on thanks for that I was just about to start writing a section on data collider I'm not really sure what else we can critique.--[[User:Azemanci|Azemanci]] 03:11, 2 December 2010 (UTC)

I added a few things to the what you wrote and I also moved it to the main page. --[[User:Azemanci|Azemanci]] 03:22, 2 December 2010 (UTC)

Talk:COMP 3000 Essay 1 2010 Question 10

2010-10-15T04:14:01Z

Abujaki: Hybrid Drives

Hey all,

I think we should write down our emails here so we can further discuss stuff without having to login here.
('''***Note that discussions over email can't be counted towards your participation grade!***'''--[[User:Soma|Anil]])

Geoff Smith (gsmith0413@gmail.com) - gsmith6

Andrew Bujáki (abujaki [at] Connect or Live.ca)
***I'm usually on MSN(Live) for collaboration at nights, Just make sure to put in a little message about who you are when you're adding me. :)

I used Google Scholar and came to this page http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=812717&tag=1#
Which briefly touches on the issues of Flash memory. Specifically, inability to update in place, and limited write/erase cycles.

Inability to update in place could refer to the way the flash disk is programmed, instead of bit-by-bit, it is programmed block-by-block. A block would have to be erased and completely reprogrammed in order to flip one bit after it's been set.
http://en.wikipedia.org/wiki/Flash_memory#Block_erasure

Limited write/erase: Flash memory typically has a short lifespan if it's being used a lot. Writing and erasing the memory (Changing, updating, etc) Will wear it out. Flash memory has a finite amount of writes, (varying on manufacturer, models, etc), and once they've been used up, you'll get bad sectors, corrupt data, and generally be SOL.
http://en.wikipedia.org/wiki/Flash_memory#Memory_wear

Filesystems would have to be changed to play nicely with these constraints, where it must use blocks efficiently and nicely, and minimize writing/erasing as much as possible.

I found a paper that talks about the performance, capabilities and limitations of NAND flash storage.

Abstract: "This presentation provides an in-depth examination of the
fundamental theoretical performance, capabilities, and
limitations of NAND Flash-based Solid State Storage (SSS). The
tutorial will explore the raw performance capabilities of NAND
Flash, and limitations to performance imposed by mitigation of
reliability issues, interfaces, protocols, and technology types.
Best practices for system integration of SSS will be discussed.
Performance achievements will be reviewed for various
products and applications. "

Link: http://www.flashmemorysummit.com/English/Collaterals/Proceedings/2009/20090812_T1B_Smith.pdf

There's no Starting place like Wikipedia, even if you shouldn't source it.

http://en.wikipedia.org/wiki/Flash_Memory

http://en.wikipedia.org/wiki/LogFS

http://en.wikipedia.org/wiki/Hard_disk

http://en.wikipedia.org/wiki/Wear_leveling

http://en.wikipedia.org/wiki/Hot_spot_%28computer_science%29

http://en.wikipedia.org/wiki/Solid-state_drive

Hey Guys,

We really don't have much time to get this done. Lets meet tomorrow after class and get our bearings to do this properly.

Fedor

A few of us have Networking immediately after class. I know personally I won't be able to make anything set on Tuesday.
Additionally, he spoke briefly about hotspots on the disk for our question last week, where places on the disk would be written to far more often than others.
As well, for bibliographical citing, http://bibme.org is a wonderful resource for the popular formats (I.e. MLA). If it should come down to that.
~Andrew

===links===

Start Posting some stuff to source from:

http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=1199079&tag=1
--"Introduction to flash memory"

http://portal.acm.org/citation.cfm?id=1244248
--"Wear Leveling" (it's about a proposed way of doing it, but explains a whole bunch of other things to do that)

http://portal.acm.org/citation.cfm?id=1731355
--"Online maintenance of very large random samples on flash storage" (ie dealing with the constraints of Flash Storage in a system that might actually be written to 100000 times)

http://vlsi.kaist.ac.kr/paper_list/2006_TC_CFFS.pdf
--"An Efficient NAND Flash File System for Flash Memory Storage" discuses shortcomings of using hard disk based file systems and current flash based file systems

http://maltiel-consulting.com/NAND_vs_NOR_Flash_Memory_Technology_Overview_Read_Write_Erase_speed_for_SLC_MLC_semiconductor_consulting_expert.pdf
--"NAND vs NOR Flash Memory" (note: i didn't get this off of Google scholar but it seems to be written by someone from Toshiba. is that ok?)

Hi everybody,

So here are the latest news. Geoff, Andrew and myself had a meeting after class today and came up with a plan for writing this thing.

We decided to have 3 parts:

1. What flash storage is, why its good but also why it must have the problems that it does (the assumption is that it must have them, why would it otherwise?)
[don't know much about this just now... basics include that there is NOR (reads slightly faster)and NAND (holds more, writes faster, erases much faster, lasts about ten times longer) flash with NAND being especially popular for storage (what's NOR good for?). Here, we'd ideally want to talk about why flash was invented (supposed as an alternative to slow ROM), why it was suitable for that, and how it works on a technical level. Then, we'd want to mention why this technical functionality was innovative and useful but also why it came with two serious set-backs: having a limited-number of re-write cycles and needing to erase a block at a time.]

Either way, Flash storage affords far faster fetch times than the traditional platter-based HDD, and stability of information in a sense. Where the data is not actually stored, but reprogrammed, in a sense, the data is more secure and is less likely to be erased easily. On that note, in order to flip a single bit, that entire block will need to be erased, then reprogrammed. In an 'old' HDD, let's say, When the HDD fails at the end of its life cycle, your data is gone. (unless you're willing to shell out $200/hr to have it recovered, yes I've seen companies in Ottawa that do this.) In a flash HDD, when it reaches the end of its life, it merely becomes read-only. Bugger for Databases, but useful for technical notes and archives, let's say.
With today's modern gaming computers, Flash memory can be good on quick load times, however with limited read-writes, it could afford better use to things that are not updated as frequently. I.e... Well I don't have a better example than a webserver hosting a company's CSS and scripts.
~Source: Years in the 'biz

Flash memory started out as a replacement for EPROMs. At the time EPROMs needed a UV photoemission to be erased while flash memory could be erased electronically. The first flash memory product came out in 1988 but it did not take off until the late 1990’s because it could not be reliable produced. NOR and NAND memory is named after the arrangement of the cells in the memory array. NOR based flash memory benefits from having very fast burst read times but slower write times. Due to the structure of NOR memory programs stored in NOR based memory can be executed without being loaded into RAM first. NAND flash memory has a very large storage capacity and can read and write large files relatively fast. NAND is more suited for storage while NOR memory is better suited for direct program execution such as in CMOS chips.
source: http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=1199079&tag=1 , http://maltiel-consulting.com/NAND_vs_NOR_Flash_Memory_Technology_Overview_Read_Write_Erase_speed_for_SLC_MLC_semiconductor_consulting_expert.pdf

2. How a traditional disk-based file-system works and why the limitations of flash storage make the two a poor match
[the obvious answer seems to be that traditional file-systems could just write to whatever memory was available but if they did this with a flash file-systems, certain chunks of memory would become unusable before others and the memory would be more difficult to work with. Also, disk-based file systems need to deal with seeking times which means that they want to organize their data in such a way as to reduce those (by putting related things together?) - with Flash, this isn't really a problem and thus one constraint the less to be concerned with.]

3. How a log based file-system works and why this method of operation is so well suited to working with flash memory especially in light of the latter's inherent limitations
[...]

At this time, the plan is that Geoff will work on #3 today, Andrew will work on #1 tomorrow and I will work on #2 tomorrow. The three of us will make an effort to consult some somewhat more painfully technical literature in order to gain insight into our respective queries. Whatever insight we find will be posted here.

Then, we will meet again on Thursday after class to decide how to actually write the essay.

PS, if there is anybody in the group besides the three of us - let us know so you can find a way to contribute to this... as at least two of us are competent essayists, painfully technical research would on one or more of the above topics would be a great way to contribute... especially if you could post it here prior to one of us going over the same thing.

Fedor

-- I'm not that great (but absolutely horrid) at essays and I'm alright at research, but if nothing else I have Thursday off and nothing (else) that needs doing by Friday so I can probably spend a bunch of time working on it just before it's due. -- ''Nick L''

-- Hay sorry I was unable to attend the meeting after class today. I am not too good at writing essays as well but I am pretty good at summarizing and researching. I am not too sure at what you would like me to do. Right now I'll assume you need me to research/summarizing articles for the 3 topics above. If you need me to do anything else post it here. I'll be checking the discussion regularly until this due. once again sorry for missing the meeting-- Paul Cox.

-- Hey i'm also supposed to be in on this. Sorry i couldn't contribute sooner because i was playing catchup in my other classes. Let me know what i can do and i'll be on it asap. - kirill (k.kashigin@gmail.com)
update: i'm gonna be helping Fedor with #2

PS, this article http://docs.google.com/viewer?a=v&q=cache:E7-H_pv_18wJ:citeseerx.ist.psu.edu/viewdoc/download%3Fdoi%3D10.1.1.92.2279%26rep%3Drep1%26type%3Dpdf+flash+memory+and+disk-based+file+systems&hl=en&gl=ca&pid=bl&srcid=ADGEESgspy-jqIdLOpaLYlPPoM56kjLPwXcL3_eMbTTBRkI7PG0jQKl9vIieTAYHubPu0EdQ0V4ccaf_p0S_SnqKMirSIM0Qoq5E0NpLd0M7LAGaE51wkD0F55cRSkX8dnTqx_9Yx2E7&sig=AHIEtbS-yfGI9Y48DJ0WyEEhmsXInelRGw looks really useful for part 3.

---same article as above but shorter link: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.160.5142

PPS, and this article looks really great for understanding how log based file systems work: http://delivery.acm.org/10.1145/150000/146943/p26-rosenblum.pdf?key1=146943&key2=3656986821&coll=GUIDE&dl=GUIDE&CFID=108397378&CFTOKEN=72657973

Hey Luc (TA) here, Anandtech ran a series of articles on solid state drives that you guys might find useful. It mostly looked at hardware aspects but it gives some interesting insights on how to modify file systems to better support flash memory.

http://www.anandtech.com/cpuchipsets/intel/showdoc.aspx?i=3403

http://www.anandtech.com/storage/showdoc.aspx?i=3531&p=1

http://anandtech.com/storage/showdoc.aspx?i=3631

--[[User:3maisons|3maisons]] 19:44, 12 October 2010 (UTC)

Hey Paul&Kirill,

If one of you guys could help me out with #2, that would be really great. I was going to work on that tomorrow, but I also have another large assignment to deal with and not having to do this research would greatly ease my life. Moreover, I do intend to work on writing&polishing the essay on Thursday as I have a lot of experience with that and it far more than research. Let me know if either one of you can help me with this.

The other person could probably read over what Luc posted for us and see if it fits into our framework. Just be sure to state who is going to do what.

Nick,

Honestly, we really hope to have the research done by Thursday. If that is the only day that you are free and you're not a writer, I'm honestly not sure what you could do. Perhaps someone else can think of something.

- Fedor

I'm gonna have something for #2 up tonight. -kirill

So I found this article on Reddit, posted from Linux Weekly News on pretty much exactly what we are looking at. It's entitled "Solid-state storage devices and the block layer"

http://lwn.net/SubscriberLink/408428/68fa8465da45967a/ --[[User:Gsmith6|Gsmith6]] 20:36, 13 October 2010 (UTC)

I wasn't exactly sure how much information i was supposed to present but here's what i got for #2:

Most conventional file systems are designed to me implemented on hard disk drives. This fact does not mean they cannot be implemented on a solid state drive (file storage that uses flash memory instead of magnetic discs). It would however, in many ways, defeat the purpose of using flash memory. The most consuming process for an HDD is seeking data by relocating the read-head and spinning the magnetic disk. A traditional file system optimizes the way it stores data by placing related blocks close-by on the disk to minimize mechanical movement within the HDD. One of the great advantages of flash memory, which accounts for its fast read speed, is that there is no need to seek data physically so there is no need to waste resources laying out the data in close proximity.
A traditional HDD file system will also attempt to defragment itself, moving blocks of data around for closer proximity on the magnetic disk. This process, although beneficial for HDD's, is harmful and inefficient for flash based storage. A flash optimal file system needs to reduce the amount of erase operations, since flash memory only has a limited amount of erase cycles as well as having very slow erase speeds.
When an HDD rewrites data to a physical location there is no need for it to erase the previously occupying data first, so a traditional disk based file system doesn't worry about erasing data from unused memory blocks. In contrast flash memory needs to first erase the data block before it can modify any of it contents. Since the erase procedure is extremely slow, its not practical to overwrite old data every time. It is also decremental to the life span of flash memory.
To maximize the potential of flash based memory the file system would have to write new data to empty memory blocks. This method would also call for some sort of garbage collection to erase unused blocks when the system is idle, which does not get implemented in conventional file systems since it is not needed.

--kirill

So Fedor and I were talking in the labs, and we came to the conclusion that we have been focusing on just the translation from a regular file system to a flash drive. We were under the impression that this was in fact the "Flash Optimized System", but pulling up some more articles, I'm finding that this is not necessarily the case.

This paper here http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.128.6156&rep=rep1&type=pdf.
shows an example from Axis Communications where they developed a file system specifically designed to be used on flash drives.

Now I haven't completely read it, so it might just be an optimized translational system, but its at least a start.

At our meeting today, we've decided that it would be best if people could post a rough summary of their notes in the appropriate sections, and I will rewrite them into an essay, which Fedor will go through later tonight to edit and add some more information.

Paul: I missed your comment that you weren't that great at writing, and good at research. If you want some articles behind the pay-walls, I've saved a bunch of them and emailed them to myself. Just email me (at the address at the top of the page) and I'll be more than happy to send some your way.

PS. some more references

Design tradeoffs for SSD performance http://portal.acm.org/citation.cfm?id=1404014.1404019
A log buffer-based flash translation layer using fully-associative sector translation http://delivery.acm.org/10.1145/1280000/1275990/a18-lee.pdf?key1=1275990&key2=0709607821&coll=GUIDE&dl=GUIDE&CFID=105787273&CFTOKEN=74601780

--[[User:Gsmith6|Gsmith6]] 15:03, 14 October 2010 (UTC)

I don't have any notes on this computer. >: I will be adding more to my section later on tonight. Sorry. ~Andrew

Hello dudes,

Just a quick note, try to include citations in your paragraphs - each time that you make a claim which came from evidence, put a little number [X, pp. page-number (if applicable)] into your text. Then, put the same [X] at the bottom of the page with the bibliographical information about the source. The prof hasn't yet gotten back to me about his preferred citation format, so just stick with this one for now:

Authors. ''Title''. Web-page. Date of article. Web (the word). Date you accessed it.

Here's an example:

[1] Kawaguchi, Nishioka, Tamoda. ''A Flash Memory Based File System''.
http://docs.google.com/viewer?a=v&q=cache:E7-H_pv_18wJ:citeseerx.ist.psu.edu/viewdoc/download%3Fdoi%3D10.1.1.92.2279%26rep%3Drep1%26type%3Dpdf+flash+memory+and+disk-based+file+systems&hl=en&gl=ca&pid=bl&srcid=ADGEESgspy-jqIdLOpaLYlPPoM56kjLPwXcL3_eMbTTBRkI7PG0jQKl9vIieTAYHubPu0EdQ0V4ccaf_p0S_SnqKMirSIM0Qoq5E0NpLd0M7LAGaE51wkD0F55cRSkX8dnTqx_9Yx2E7&sig=AHIEtbS-yfGI9Y48DJ0WyEEhmsXInelRGw . 1995. Web. Oct. 14, 2010.

Fedor

PS, its a good idea to check this fairly frequently between now and tomorrow morning - you never know when something will come up.

Phew... for a while there I was starting to think that I had nothing about the actual "Log-Based System", but it turns out that the "Transitional Layer" is the same thing. It looks like some articles are calling it the Log system, while others are calling it the transitional layer. Pretty sure I'm going to have an experts knowledge about flash drives after reading all these articles :P
--[[User:Gsmith6|Gsmith6]] 18:13, 14 October 2010 (UTC)

Hay Geoff this is what i got so far after reading a couple of the pdfs. the double tabed points are just my annotation on how they relate to the question.

Ware leveling: p1126-chang.pdf

* Uneven wearing of flash memory due to storing data close together
* Garbage collection prefers that no blocks have pages that have data that is constantly becoming invalid
* data that remains the same for longs periods of time should be moved from block that have not be written to much and moved to blocks that haven been erased frequently.

Log file structure: 926-rosenblum.pdf

* LFS based on assumption that frequently read files will be stored in cash and that the hard disk traffic will be dominated by writes
* Writes all new info to disk in a sequential structure called a log
* Data is stored permanently in these logs no other data is stored on the hard drive
* Converts many small random synchronous writes to a large asynchronous sequential write
** Good for flash because it cuts down on writing (prolongs drive life)
** It also good because it writes to a bigger section then a page. This means it can fill a block at a time so it doesn’t fill up other blocks with random writes that would later need to be cleaned. Cuts down on cleaning.
* Inode is stored in the log on the disk while an inode map is maintained in memory which points to the inode in the hard disk. as
** This is good for flash drives because reading does not hurt the drives life and it is fast.
** This means the map will not have to be updated on the disk as frequently cutting down on the writes.
* Log systems weakness is that it is susceptible to becoming fragmented due to the larger writes.
** Since flash drives do not require fragmentation this is fine. Also since flash drives have very fast random access the system does not become bogged down when the logs are fragmented
* Log system implements a cleaning system that scans a segment in and sees if there is live data in it. If there is a certain percentage of invalid data which goes according to the cleaning policy it will be cleaned. All the live data will be copied out and the segment will be erased.
** This is a garbage collector but its built into the file system.
* Segments contain a number of blocks. Segments can contain logs or parts of logs.

I'm still sifting though the other pdfs you sent me. Would you like me to post more info or should i format this into a paragraph or 2?

--Paul

I'm sorting through my notes and putting them into a digital format. Difficult because It's hard to remember what I copied directly out of the notes for my own reference, so I'm trying to de-plagarize. I'll upload what I have to the section by 20:30, but expect more updates. ~Andrew

Hey Paul,

Thanks for helping out with the research
I'm thinking that we probably have enough information (at least for the log-based system), so maybe if you could "try" and putting them into paragraphs. I'm kind of in the middle of typing up the essay, and I'm uploading new information every 10-20 minutes or so. Even if you could get something into paragraph form, I can go through and edit, rearrange, and add stuff as I get there. --[[User:Gsmith6|Gsmith6]] 23:51, 14 October 2010 (UTC)

I'm just going to dump my entire wiki so far into my profile page, because everything's being updated so quickly.
[[User:Abujaki]] ~Andrew

I'm sitting at my computer working on much less immediately important homework if someone wants me to do something. I'm not a great writer but if there's something that needs doing I can do it. -- Nick [[User:Nlessard|Nlessard]] 00:55, 15 October 2010 (UTC)

Hey guys,

Keep up the good work!

Geoff, it would be good if you uploaded the stuff you were typing as you got each section finished. I rewrote part 2 and the intro some hours ago and I guess I could go out and write a conclusion while stuff is still being updated.

The other thing is that the current version of part 1 doesn't really seem to serve the argument - I mean, it doesn't actually tell us why flash has the constraints that it does on a technical level... and that's not surprising because that information seems to be hard to find. Still, I'm going to see if I can find out anything about that, though, so far, I haven't had much luck.

Apart from this, I'll try to get up early tomorrow to look over what's there: make sure the argument works, etc.

Good luck with the writing,

Fedor

I think it has to do with how some transistors are made. Give me a second to research that... ~Andrew

From source 20, page 269 sec 4.6.4
Stress Induced Oxide leakage
...These devices are either erased ... orboth programmed and erased by a high field (Fowler-Nordheim) injection of electrons into a very thin dielectric film to charge and discharge the floating gate. Unfortunately, [passing] this current through the oxide degrades the quality of the oxide and eventually leads to breakdown. The wearout of tunnel oxide films during high-field stress has been correlated with the buildup of both positive or negative trapped charges."... there are still some things missing from this explanation... Give me a couple more seconds... and my brain won't process this for some reason. =_= What can you guys make of this? ~Andrew

And I said NOR Flash memory had fast fetch times. I found what I was looking for, just not too sure how to explain it in text. Silicon Oxide is used for electron injection methods, including the Fowler-Nordheim Tunneling method, where it seems to say that an electric current is passed across the oxide and it thins enough for a current to be passed through a barrier into the oxide conduction... band?

Kay. New resource [19], the massively complicated theories and science would put anyone to sleep, but the basic point is The Silicon oxide layer will degrade in quality to the point where charge trapping begins to occur, the more it's used, and the more electrons that tunnel through it over time. It's like a kneaded eraser scenario. The more you use it, the poorer quality it gets until it gets all flakey and cannot do its job anymore. The same happens with the SiO2 layer in the floating gate transistors ~Andrew

hmmm... alright, I think I understand that, could you maybe try your best and add it into the essay? If not I can try and whip something up to put in there. thanks --[[User:Gsmith6|Gsmith6]] 02:39, 15 October 2010 (UTC)

Wow, I'm sorry I made you go into that... that does explain the limited erase-cycles, though. Was it the use of these materials that made flash innovative? How does that explain the block-sized erasures?

Going to go write a conclusion now.

Fedor

While looking for what you requested, I found an entire section on the oxide breakdown... oops. :P
So really nothing changes, As electrons tunnel through the oxide layer, it deteriorates. When the damage becomes too great, the oxide abruptly loses its insulative properties. (damn firefox, that's a word) Looking for the erasures now ~Andrew

Hey guys,

I'm off to sleep, but I'll be up at 5am to see what else I can do.

Fedor

Aw, I just missed you.
It turns out that erasing entire blocks is necessary based on how the chip is built. For both NOR and NAND, pairs of word lines share an erase line, which is located near the floating gate. It uses FN tunneling to erase two lines of words at a time, making the sector the smallest size you can erase simply because that's how it's physically wired.
i.e []-mem byte |-erase line

#[]|[][]|[]
#[]|[][]|[]
#[]|[][]|[]
#[]|[][]|[] ... If that makes any sense... The erase line is separate from the byte select or word select lines

Numbers for formatting sake.

I'm prolly gonna take Fedor's advice and head to bed, but I'll likely pop back on before I go to sleep in case anyone needs me to look up anything else. :P

--[[User:Lmundt|Lmundt]] 03:23, 15 October 2010 (UTC) Interesting article compaing speeds
https://noc.sara.nl/nrg/publications/RoN2010-D1.1.pdf

Wow, I can't believe I completely forgot. Hybrid Drives... I can't remember for the life of me whether they exist yet or not, but there will eventually exist a hard drive that's both flash and traditional platter. It allocates files that are not rewritten often, like an OS (well except windows and all its lovely updates) to the flash memory on install, and the remainder of the files (Documents, programs etc) to the traditional platter. Because you can't reformat an OS 100,000 times (no matter HOW badly you screw it up with viruses and the like), the flash memory will retain usability, and all the hotspots are on the platters, so you don't need to worry about minimizing disk usage.
I'm out for the night. Cheers all! ~Andrew

Talk:COMP 3000 Essay 1 2010 Question 10

2010-10-15T03:22:40Z

Abujaki:

Talk:COMP 3000 Essay 1 2010 Question 10

2010-10-15T03:21:55Z

Abujaki:

Hey all,

I think we should write down our emails here so we can further discuss stuff without having to login here.
('''***Note that discussions over email can't be counted towards your participation grade!***'''--[[User:Soma|Anil]])

Geoff Smith (gsmith0413@gmail.com) - gsmith6

Andrew Bujáki (abujaki [at] Connect or Live.ca)
***I'm usually on MSN(Live) for collaboration at nights, Just make sure to put in a little message about who you are when you're adding me. :)

I used Google Scholar and came to this page http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=812717&tag=1#
Which briefly touches on the issues of Flash memory. Specifically, inability to update in place, and limited write/erase cycles.

Inability to update in place could refer to the way the flash disk is programmed, instead of bit-by-bit, it is programmed block-by-block. A block would have to be erased and completely reprogrammed in order to flip one bit after it's been set.
http://en.wikipedia.org/wiki/Flash_memory#Block_erasure

Limited write/erase: Flash memory typically has a short lifespan if it's being used a lot. Writing and erasing the memory (Changing, updating, etc) Will wear it out. Flash memory has a finite amount of writes, (varying on manufacturer, models, etc), and once they've been used up, you'll get bad sectors, corrupt data, and generally be SOL.
http://en.wikipedia.org/wiki/Flash_memory#Memory_wear

Filesystems would have to be changed to play nicely with these constraints, where it must use blocks efficiently and nicely, and minimize writing/erasing as much as possible.

I found a paper that talks about the performance, capabilities and limitations of NAND flash storage.

Abstract: "This presentation provides an in-depth examination of the
fundamental theoretical performance, capabilities, and
limitations of NAND Flash-based Solid State Storage (SSS). The
tutorial will explore the raw performance capabilities of NAND
Flash, and limitations to performance imposed by mitigation of
reliability issues, interfaces, protocols, and technology types.
Best practices for system integration of SSS will be discussed.
Performance achievements will be reviewed for various
products and applications. "

Link: http://www.flashmemorysummit.com/English/Collaterals/Proceedings/2009/20090812_T1B_Smith.pdf

There's no Starting place like Wikipedia, even if you shouldn't source it.

http://en.wikipedia.org/wiki/Flash_Memory

http://en.wikipedia.org/wiki/LogFS

http://en.wikipedia.org/wiki/Hard_disk

http://en.wikipedia.org/wiki/Wear_leveling

http://en.wikipedia.org/wiki/Hot_spot_%28computer_science%29

http://en.wikipedia.org/wiki/Solid-state_drive

Hey Guys,

We really don't have much time to get this done. Lets meet tomorrow after class and get our bearings to do this properly.

Fedor

A few of us have Networking immediately after class. I know personally I won't be able to make anything set on Tuesday.
Additionally, he spoke briefly about hotspots on the disk for our question last week, where places on the disk would be written to far more often than others.
As well, for bibliographical citing, http://bibme.org is a wonderful resource for the popular formats (I.e. MLA). If it should come down to that.
~Andrew

===links===

Start Posting some stuff to source from:

http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=1199079&tag=1
--"Introduction to flash memory"

http://portal.acm.org/citation.cfm?id=1244248
--"Wear Leveling" (it's about a proposed way of doing it, but explains a whole bunch of other things to do that)

http://portal.acm.org/citation.cfm?id=1731355
--"Online maintenance of very large random samples on flash storage" (ie dealing with the constraints of Flash Storage in a system that might actually be written to 100000 times)

http://vlsi.kaist.ac.kr/paper_list/2006_TC_CFFS.pdf
--"An Efficient NAND Flash File System for Flash Memory Storage" discuses shortcomings of using hard disk based file systems and current flash based file systems

http://maltiel-consulting.com/NAND_vs_NOR_Flash_Memory_Technology_Overview_Read_Write_Erase_speed_for_SLC_MLC_semiconductor_consulting_expert.pdf
--"NAND vs NOR Flash Memory" (note: i didn't get this off of Google scholar but it seems to be written by someone from Toshiba. is that ok?)

Hi everybody,

So here are the latest news. Geoff, Andrew and myself had a meeting after class today and came up with a plan for writing this thing.

We decided to have 3 parts:

1. What flash storage is, why its good but also why it must have the problems that it does (the assumption is that it must have them, why would it otherwise?)
[don't know much about this just now... basics include that there is NOR (reads slightly faster)and NAND (holds more, writes faster, erases much faster, lasts about ten times longer) flash with NAND being especially popular for storage (what's NOR good for?). Here, we'd ideally want to talk about why flash was invented (supposed as an alternative to slow ROM), why it was suitable for that, and how it works on a technical level. Then, we'd want to mention why this technical functionality was innovative and useful but also why it came with two serious set-backs: having a limited-number of re-write cycles and needing to erase a block at a time.]

Either way, Flash storage affords far faster fetch times than the traditional platter-based HDD, and stability of information in a sense. Where the data is not actually stored, but reprogrammed, in a sense, the data is more secure and is less likely to be erased easily. On that note, in order to flip a single bit, that entire block will need to be erased, then reprogrammed. In an 'old' HDD, let's say, When the HDD fails at the end of its life cycle, your data is gone. (unless you're willing to shell out $200/hr to have it recovered, yes I've seen companies in Ottawa that do this.) In a flash HDD, when it reaches the end of its life, it merely becomes read-only. Bugger for Databases, but useful for technical notes and archives, let's say.
With today's modern gaming computers, Flash memory can be good on quick load times, however with limited read-writes, it could afford better use to things that are not updated as frequently. I.e... Well I don't have a better example than a webserver hosting a company's CSS and scripts.
~Source: Years in the 'biz

Flash memory started out as a replacement for EPROMs. At the time EPROMs needed a UV photoemission to be erased while flash memory could be erased electronically. The first flash memory product came out in 1988 but it did not take off until the late 1990’s because it could not be reliable produced. NOR and NAND memory is named after the arrangement of the cells in the memory array. NOR based flash memory benefits from having very fast burst read times but slower write times. Due to the structure of NOR memory programs stored in NOR based memory can be executed without being loaded into RAM first. NAND flash memory has a very large storage capacity and can read and write large files relatively fast. NAND is more suited for storage while NOR memory is better suited for direct program execution such as in CMOS chips.
source: http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=1199079&tag=1 , http://maltiel-consulting.com/NAND_vs_NOR_Flash_Memory_Technology_Overview_Read_Write_Erase_speed_for_SLC_MLC_semiconductor_consulting_expert.pdf

2. How a traditional disk-based file-system works and why the limitations of flash storage make the two a poor match
[the obvious answer seems to be that traditional file-systems could just write to whatever memory was available but if they did this with a flash file-systems, certain chunks of memory would become unusable before others and the memory would be more difficult to work with. Also, disk-based file systems need to deal with seeking times which means that they want to organize their data in such a way as to reduce those (by putting related things together?) - with Flash, this isn't really a problem and thus one constraint the less to be concerned with.]

3. How a log based file-system works and why this method of operation is so well suited to working with flash memory especially in light of the latter's inherent limitations
[...]

At this time, the plan is that Geoff will work on #3 today, Andrew will work on #1 tomorrow and I will work on #2 tomorrow. The three of us will make an effort to consult some somewhat more painfully technical literature in order to gain insight into our respective queries. Whatever insight we find will be posted here.

Then, we will meet again on Thursday after class to decide how to actually write the essay.

PS, if there is anybody in the group besides the three of us - let us know so you can find a way to contribute to this... as at least two of us are competent essayists, painfully technical research would on one or more of the above topics would be a great way to contribute... especially if you could post it here prior to one of us going over the same thing.

Fedor

-- I'm not that great (but absolutely horrid) at essays and I'm alright at research, but if nothing else I have Thursday off and nothing (else) that needs doing by Friday so I can probably spend a bunch of time working on it just before it's due. -- ''Nick L''

-- Hay sorry I was unable to attend the meeting after class today. I am not too good at writing essays as well but I am pretty good at summarizing and researching. I am not too sure at what you would like me to do. Right now I'll assume you need me to research/summarizing articles for the 3 topics above. If you need me to do anything else post it here. I'll be checking the discussion regularly until this due. once again sorry for missing the meeting-- Paul Cox.

-- Hey i'm also supposed to be in on this. Sorry i couldn't contribute sooner because i was playing catchup in my other classes. Let me know what i can do and i'll be on it asap. - kirill (k.kashigin@gmail.com)
update: i'm gonna be helping Fedor with #2

PS, this article http://docs.google.com/viewer?a=v&q=cache:E7-H_pv_18wJ:citeseerx.ist.psu.edu/viewdoc/download%3Fdoi%3D10.1.1.92.2279%26rep%3Drep1%26type%3Dpdf+flash+memory+and+disk-based+file+systems&hl=en&gl=ca&pid=bl&srcid=ADGEESgspy-jqIdLOpaLYlPPoM56kjLPwXcL3_eMbTTBRkI7PG0jQKl9vIieTAYHubPu0EdQ0V4ccaf_p0S_SnqKMirSIM0Qoq5E0NpLd0M7LAGaE51wkD0F55cRSkX8dnTqx_9Yx2E7&sig=AHIEtbS-yfGI9Y48DJ0WyEEhmsXInelRGw looks really useful for part 3.

---same article as above but shorter link: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.160.5142

PPS, and this article looks really great for understanding how log based file systems work: http://delivery.acm.org/10.1145/150000/146943/p26-rosenblum.pdf?key1=146943&key2=3656986821&coll=GUIDE&dl=GUIDE&CFID=108397378&CFTOKEN=72657973

Hey Luc (TA) here, Anandtech ran a series of articles on solid state drives that you guys might find useful. It mostly looked at hardware aspects but it gives some interesting insights on how to modify file systems to better support flash memory.

http://www.anandtech.com/cpuchipsets/intel/showdoc.aspx?i=3403

http://www.anandtech.com/storage/showdoc.aspx?i=3531&p=1

http://anandtech.com/storage/showdoc.aspx?i=3631

--[[User:3maisons|3maisons]] 19:44, 12 October 2010 (UTC)

Hey Paul&Kirill,

If one of you guys could help me out with #2, that would be really great. I was going to work on that tomorrow, but I also have another large assignment to deal with and not having to do this research would greatly ease my life. Moreover, I do intend to work on writing&polishing the essay on Thursday as I have a lot of experience with that and it far more than research. Let me know if either one of you can help me with this.

The other person could probably read over what Luc posted for us and see if it fits into our framework. Just be sure to state who is going to do what.

Nick,

Honestly, we really hope to have the research done by Thursday. If that is the only day that you are free and you're not a writer, I'm honestly not sure what you could do. Perhaps someone else can think of something.

- Fedor

I'm gonna have something for #2 up tonight. -kirill

So I found this article on Reddit, posted from Linux Weekly News on pretty much exactly what we are looking at. It's entitled "Solid-state storage devices and the block layer"

http://lwn.net/SubscriberLink/408428/68fa8465da45967a/ --[[User:Gsmith6|Gsmith6]] 20:36, 13 October 2010 (UTC)

I wasn't exactly sure how much information i was supposed to present but here's what i got for #2:

Most conventional file systems are designed to me implemented on hard disk drives. This fact does not mean they cannot be implemented on a solid state drive (file storage that uses flash memory instead of magnetic discs). It would however, in many ways, defeat the purpose of using flash memory. The most consuming process for an HDD is seeking data by relocating the read-head and spinning the magnetic disk. A traditional file system optimizes the way it stores data by placing related blocks close-by on the disk to minimize mechanical movement within the HDD. One of the great advantages of flash memory, which accounts for its fast read speed, is that there is no need to seek data physically so there is no need to waste resources laying out the data in close proximity.
A traditional HDD file system will also attempt to defragment itself, moving blocks of data around for closer proximity on the magnetic disk. This process, although beneficial for HDD's, is harmful and inefficient for flash based storage. A flash optimal file system needs to reduce the amount of erase operations, since flash memory only has a limited amount of erase cycles as well as having very slow erase speeds.
When an HDD rewrites data to a physical location there is no need for it to erase the previously occupying data first, so a traditional disk based file system doesn't worry about erasing data from unused memory blocks. In contrast flash memory needs to first erase the data block before it can modify any of it contents. Since the erase procedure is extremely slow, its not practical to overwrite old data every time. It is also decremental to the life span of flash memory.
To maximize the potential of flash based memory the file system would have to write new data to empty memory blocks. This method would also call for some sort of garbage collection to erase unused blocks when the system is idle, which does not get implemented in conventional file systems since it is not needed.

--kirill

So Fedor and I were talking in the labs, and we came to the conclusion that we have been focusing on just the translation from a regular file system to a flash drive. We were under the impression that this was in fact the "Flash Optimized System", but pulling up some more articles, I'm finding that this is not necessarily the case.

This paper here http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.128.6156&rep=rep1&type=pdf.
shows an example from Axis Communications where they developed a file system specifically designed to be used on flash drives.

Now I haven't completely read it, so it might just be an optimized translational system, but its at least a start.

At our meeting today, we've decided that it would be best if people could post a rough summary of their notes in the appropriate sections, and I will rewrite them into an essay, which Fedor will go through later tonight to edit and add some more information.

Paul: I missed your comment that you weren't that great at writing, and good at research. If you want some articles behind the pay-walls, I've saved a bunch of them and emailed them to myself. Just email me (at the address at the top of the page) and I'll be more than happy to send some your way.

PS. some more references

Design tradeoffs for SSD performance http://portal.acm.org/citation.cfm?id=1404014.1404019
A log buffer-based flash translation layer using fully-associative sector translation http://delivery.acm.org/10.1145/1280000/1275990/a18-lee.pdf?key1=1275990&key2=0709607821&coll=GUIDE&dl=GUIDE&CFID=105787273&CFTOKEN=74601780

--[[User:Gsmith6|Gsmith6]] 15:03, 14 October 2010 (UTC)

I don't have any notes on this computer. >: I will be adding more to my section later on tonight. Sorry. ~Andrew

Hello dudes,

Just a quick note, try to include citations in your paragraphs - each time that you make a claim which came from evidence, put a little number [X, pp. page-number (if applicable)] into your text. Then, put the same [X] at the bottom of the page with the bibliographical information about the source. The prof hasn't yet gotten back to me about his preferred citation format, so just stick with this one for now:

Authors. ''Title''. Web-page. Date of article. Web (the word). Date you accessed it.

Here's an example:

[1] Kawaguchi, Nishioka, Tamoda. ''A Flash Memory Based File System''.
http://docs.google.com/viewer?a=v&q=cache:E7-H_pv_18wJ:citeseerx.ist.psu.edu/viewdoc/download%3Fdoi%3D10.1.1.92.2279%26rep%3Drep1%26type%3Dpdf+flash+memory+and+disk-based+file+systems&hl=en&gl=ca&pid=bl&srcid=ADGEESgspy-jqIdLOpaLYlPPoM56kjLPwXcL3_eMbTTBRkI7PG0jQKl9vIieTAYHubPu0EdQ0V4ccaf_p0S_SnqKMirSIM0Qoq5E0NpLd0M7LAGaE51wkD0F55cRSkX8dnTqx_9Yx2E7&sig=AHIEtbS-yfGI9Y48DJ0WyEEhmsXInelRGw . 1995. Web. Oct. 14, 2010.

Fedor

PS, its a good idea to check this fairly frequently between now and tomorrow morning - you never know when something will come up.

Phew... for a while there I was starting to think that I had nothing about the actual "Log-Based System", but it turns out that the "Transitional Layer" is the same thing. It looks like some articles are calling it the Log system, while others are calling it the transitional layer. Pretty sure I'm going to have an experts knowledge about flash drives after reading all these articles :P
--[[User:Gsmith6|Gsmith6]] 18:13, 14 October 2010 (UTC)

Hay Geoff this is what i got so far after reading a couple of the pdfs. the double tabed points are just my annotation on how they relate to the question.

Ware leveling: p1126-chang.pdf

* Uneven wearing of flash memory due to storing data close together
* Garbage collection prefers that no blocks have pages that have data that is constantly becoming invalid
* data that remains the same for longs periods of time should be moved from block that have not be written to much and moved to blocks that haven been erased frequently.

Log file structure: 926-rosenblum.pdf

* LFS based on assumption that frequently read files will be stored in cash and that the hard disk traffic will be dominated by writes
* Writes all new info to disk in a sequential structure called a log
* Data is stored permanently in these logs no other data is stored on the hard drive
* Converts many small random synchronous writes to a large asynchronous sequential write
** Good for flash because it cuts down on writing (prolongs drive life)
** It also good because it writes to a bigger section then a page. This means it can fill a block at a time so it doesn’t fill up other blocks with random writes that would later need to be cleaned. Cuts down on cleaning.
* Inode is stored in the log on the disk while an inode map is maintained in memory which points to the inode in the hard disk. as
** This is good for flash drives because reading does not hurt the drives life and it is fast.
** This means the map will not have to be updated on the disk as frequently cutting down on the writes.
* Log systems weakness is that it is susceptible to becoming fragmented due to the larger writes.
** Since flash drives do not require fragmentation this is fine. Also since flash drives have very fast random access the system does not become bogged down when the logs are fragmented
* Log system implements a cleaning system that scans a segment in and sees if there is live data in it. If there is a certain percentage of invalid data which goes according to the cleaning policy it will be cleaned. All the live data will be copied out and the segment will be erased.
** This is a garbage collector but its built into the file system.
* Segments contain a number of blocks. Segments can contain logs or parts of logs.

I'm still sifting though the other pdfs you sent me. Would you like me to post more info or should i format this into a paragraph or 2?

--Paul

I'm sorting through my notes and putting them into a digital format. Difficult because It's hard to remember what I copied directly out of the notes for my own reference, so I'm trying to de-plagarize. I'll upload what I have to the section by 20:30, but expect more updates. ~Andrew

Hey Paul,

Thanks for helping out with the research
I'm thinking that we probably have enough information (at least for the log-based system), so maybe if you could "try" and putting them into paragraphs. I'm kind of in the middle of typing up the essay, and I'm uploading new information every 10-20 minutes or so. Even if you could get something into paragraph form, I can go through and edit, rearrange, and add stuff as I get there. --[[User:Gsmith6|Gsmith6]] 23:51, 14 October 2010 (UTC)

I'm just going to dump my entire wiki so far into my profile page, because everything's being updated so quickly.
[[User:Abujaki]] ~Andrew

I'm sitting at my computer working on much less immediately important homework if someone wants me to do something. I'm not a great writer but if there's something that needs doing I can do it. -- Nick [[User:Nlessard|Nlessard]] 00:55, 15 October 2010 (UTC)

Hey guys,

Keep up the good work!

Geoff, it would be good if you uploaded the stuff you were typing as you got each section finished. I rewrote part 2 and the intro some hours ago and I guess I could go out and write a conclusion while stuff is still being updated.

The other thing is that the current version of part 1 doesn't really seem to serve the argument - I mean, it doesn't actually tell us why flash has the constraints that it does on a technical level... and that's not surprising because that information seems to be hard to find. Still, I'm going to see if I can find out anything about that, though, so far, I haven't had much luck.

Apart from this, I'll try to get up early tomorrow to look over what's there: make sure the argument works, etc.

Good luck with the writing,

Fedor

I think it has to do with how some transistors are made. Give me a second to research that... ~Andrew

From source 20, page 269 sec 4.6.4
Stress Induced Oxide leakage
...These devices are either erased ... orboth programmed and erased by a high field (Fowler-Nordheim) injection of electrons into a very thin dielectric film to charge and discharge the floating gate. Unfortunately, [passing] this current through the oxide degrades the quality of the oxide and eventually leads to breakdown. The wearout of tunnel oxide films during high-field stress has been correlated with the buildup of both positive or negative trapped charges."... there are still some things missing from this explanation... Give me a couple more seconds... and my brain won't process this for some reason. =_= What can you guys make of this? ~Andrew

And I said NOR Flash memory had fast fetch times. I found what I was looking for, just not too sure how to explain it in text. Silicon Oxide is used for electron injection methods, including the Fowler-Nordheim Tunneling method, where it seems to say that an electric current is passed across the oxide and it thins enough for a current to be passed through a barrier into the oxide conduction... band?

Kay. New resource [19], the massively complicated theories and science would put anyone to sleep, but the basic point is The Silicon oxide layer will degrade in quality to the point where charge trapping begins to occur, the more it's used, and the more electrons that tunnel through it over time. It's like a kneaded eraser scenario. The more you use it, the poorer quality it gets until it gets all flakey and cannot do its job anymore. The same happens with the SiO2 layer in the floating gate transistors ~Andrew

hmmm... alright, I think I understand that, could you maybe try your best and add it into the essay? If not I can try and whip something up to put in there. thanks --[[User:Gsmith6|Gsmith6]] 02:39, 15 October 2010 (UTC)

Wow, I'm sorry I made you go into that... that does explain the limited erase-cycles, though. Was it the use of these materials that made flash innovative? How does that explain the block-sized erasures?

Going to go write a conclusion now.

Fedor

While looking for what you requested, I found an entire section on the oxide breakdown... oops. :P
So really nothing changes, As electrons tunnel through the oxide layer, it deteriorates. When the damage becomes too great, the oxide abruptly loses its insulative properties. (damn firefox, that's a word) Looking for the erasures now ~Andrew

Hey guys,

I'm off to sleep, but I'll be up at 5am to see what else I can do.

Fedor

Aw, I just missed you.
It turns out that erasing entire blocks is necessary based on how the chip is built. For both NOR and NAND, pairs of word lines share an erase line, which is located near the floating gate. It uses FN tunneling to erase two lines of words at a time, making the sector the smallest size you can erase simply because that's how it's physically wired.
i.e []-mem byte |-erase line

.[]|[][]|[]
.[]|[][]|[]
.[]|[][]|[]
.[]|[][]|[] ... If that makes any sense... The erase line is separate from the byte select or word select lines

I'm prolly gonna take Fedor's advice and head to bed, but I'll likely pop back on before I go to sleep in case anyone needs me to look up anything else. :P

Talk:COMP 3000 Essay 1 2010 Question 10

2010-10-15T03:21:28Z

Abujaki:

Hey all,

I think we should write down our emails here so we can further discuss stuff without having to login here.
('''***Note that discussions over email can't be counted towards your participation grade!***'''--[[User:Soma|Anil]])

Geoff Smith (gsmith0413@gmail.com) - gsmith6

Andrew Bujáki (abujaki [at] Connect or Live.ca)
***I'm usually on MSN(Live) for collaboration at nights, Just make sure to put in a little message about who you are when you're adding me. :)

I used Google Scholar and came to this page http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=812717&tag=1#
Which briefly touches on the issues of Flash memory. Specifically, inability to update in place, and limited write/erase cycles.

Inability to update in place could refer to the way the flash disk is programmed, instead of bit-by-bit, it is programmed block-by-block. A block would have to be erased and completely reprogrammed in order to flip one bit after it's been set.
http://en.wikipedia.org/wiki/Flash_memory#Block_erasure

Limited write/erase: Flash memory typically has a short lifespan if it's being used a lot. Writing and erasing the memory (Changing, updating, etc) Will wear it out. Flash memory has a finite amount of writes, (varying on manufacturer, models, etc), and once they've been used up, you'll get bad sectors, corrupt data, and generally be SOL.
http://en.wikipedia.org/wiki/Flash_memory#Memory_wear

Filesystems would have to be changed to play nicely with these constraints, where it must use blocks efficiently and nicely, and minimize writing/erasing as much as possible.

I found a paper that talks about the performance, capabilities and limitations of NAND flash storage.

Abstract: "This presentation provides an in-depth examination of the
fundamental theoretical performance, capabilities, and
limitations of NAND Flash-based Solid State Storage (SSS). The
tutorial will explore the raw performance capabilities of NAND
Flash, and limitations to performance imposed by mitigation of
reliability issues, interfaces, protocols, and technology types.
Best practices for system integration of SSS will be discussed.
Performance achievements will be reviewed for various
products and applications. "

Link: http://www.flashmemorysummit.com/English/Collaterals/Proceedings/2009/20090812_T1B_Smith.pdf

There's no Starting place like Wikipedia, even if you shouldn't source it.

http://en.wikipedia.org/wiki/Flash_Memory

http://en.wikipedia.org/wiki/LogFS

http://en.wikipedia.org/wiki/Hard_disk

http://en.wikipedia.org/wiki/Wear_leveling

http://en.wikipedia.org/wiki/Hot_spot_%28computer_science%29

http://en.wikipedia.org/wiki/Solid-state_drive

Hey Guys,

We really don't have much time to get this done. Lets meet tomorrow after class and get our bearings to do this properly.

Fedor

A few of us have Networking immediately after class. I know personally I won't be able to make anything set on Tuesday.
Additionally, he spoke briefly about hotspots on the disk for our question last week, where places on the disk would be written to far more often than others.
As well, for bibliographical citing, http://bibme.org is a wonderful resource for the popular formats (I.e. MLA). If it should come down to that.
~Andrew

===links===

Start Posting some stuff to source from:

http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=1199079&tag=1
--"Introduction to flash memory"

http://portal.acm.org/citation.cfm?id=1244248
--"Wear Leveling" (it's about a proposed way of doing it, but explains a whole bunch of other things to do that)

http://portal.acm.org/citation.cfm?id=1731355
--"Online maintenance of very large random samples on flash storage" (ie dealing with the constraints of Flash Storage in a system that might actually be written to 100000 times)

http://vlsi.kaist.ac.kr/paper_list/2006_TC_CFFS.pdf
--"An Efficient NAND Flash File System for Flash Memory Storage" discuses shortcomings of using hard disk based file systems and current flash based file systems

http://maltiel-consulting.com/NAND_vs_NOR_Flash_Memory_Technology_Overview_Read_Write_Erase_speed_for_SLC_MLC_semiconductor_consulting_expert.pdf
--"NAND vs NOR Flash Memory" (note: i didn't get this off of Google scholar but it seems to be written by someone from Toshiba. is that ok?)

Hi everybody,

So here are the latest news. Geoff, Andrew and myself had a meeting after class today and came up with a plan for writing this thing.

We decided to have 3 parts:

1. What flash storage is, why its good but also why it must have the problems that it does (the assumption is that it must have them, why would it otherwise?)
[don't know much about this just now... basics include that there is NOR (reads slightly faster)and NAND (holds more, writes faster, erases much faster, lasts about ten times longer) flash with NAND being especially popular for storage (what's NOR good for?). Here, we'd ideally want to talk about why flash was invented (supposed as an alternative to slow ROM), why it was suitable for that, and how it works on a technical level. Then, we'd want to mention why this technical functionality was innovative and useful but also why it came with two serious set-backs: having a limited-number of re-write cycles and needing to erase a block at a time.]

Either way, Flash storage affords far faster fetch times than the traditional platter-based HDD, and stability of information in a sense. Where the data is not actually stored, but reprogrammed, in a sense, the data is more secure and is less likely to be erased easily. On that note, in order to flip a single bit, that entire block will need to be erased, then reprogrammed. In an 'old' HDD, let's say, When the HDD fails at the end of its life cycle, your data is gone. (unless you're willing to shell out $200/hr to have it recovered, yes I've seen companies in Ottawa that do this.) In a flash HDD, when it reaches the end of its life, it merely becomes read-only. Bugger for Databases, but useful for technical notes and archives, let's say.
With today's modern gaming computers, Flash memory can be good on quick load times, however with limited read-writes, it could afford better use to things that are not updated as frequently. I.e... Well I don't have a better example than a webserver hosting a company's CSS and scripts.
~Source: Years in the 'biz

Flash memory started out as a replacement for EPROMs. At the time EPROMs needed a UV photoemission to be erased while flash memory could be erased electronically. The first flash memory product came out in 1988 but it did not take off until the late 1990’s because it could not be reliable produced. NOR and NAND memory is named after the arrangement of the cells in the memory array. NOR based flash memory benefits from having very fast burst read times but slower write times. Due to the structure of NOR memory programs stored in NOR based memory can be executed without being loaded into RAM first. NAND flash memory has a very large storage capacity and can read and write large files relatively fast. NAND is more suited for storage while NOR memory is better suited for direct program execution such as in CMOS chips.
source: http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=1199079&tag=1 , http://maltiel-consulting.com/NAND_vs_NOR_Flash_Memory_Technology_Overview_Read_Write_Erase_speed_for_SLC_MLC_semiconductor_consulting_expert.pdf

2. How a traditional disk-based file-system works and why the limitations of flash storage make the two a poor match
[the obvious answer seems to be that traditional file-systems could just write to whatever memory was available but if they did this with a flash file-systems, certain chunks of memory would become unusable before others and the memory would be more difficult to work with. Also, disk-based file systems need to deal with seeking times which means that they want to organize their data in such a way as to reduce those (by putting related things together?) - with Flash, this isn't really a problem and thus one constraint the less to be concerned with.]

3. How a log based file-system works and why this method of operation is so well suited to working with flash memory especially in light of the latter's inherent limitations
[...]

At this time, the plan is that Geoff will work on #3 today, Andrew will work on #1 tomorrow and I will work on #2 tomorrow. The three of us will make an effort to consult some somewhat more painfully technical literature in order to gain insight into our respective queries. Whatever insight we find will be posted here.

Then, we will meet again on Thursday after class to decide how to actually write the essay.

PS, if there is anybody in the group besides the three of us - let us know so you can find a way to contribute to this... as at least two of us are competent essayists, painfully technical research would on one or more of the above topics would be a great way to contribute... especially if you could post it here prior to one of us going over the same thing.

Fedor

-- I'm not that great (but absolutely horrid) at essays and I'm alright at research, but if nothing else I have Thursday off and nothing (else) that needs doing by Friday so I can probably spend a bunch of time working on it just before it's due. -- ''Nick L''

-- Hay sorry I was unable to attend the meeting after class today. I am not too good at writing essays as well but I am pretty good at summarizing and researching. I am not too sure at what you would like me to do. Right now I'll assume you need me to research/summarizing articles for the 3 topics above. If you need me to do anything else post it here. I'll be checking the discussion regularly until this due. once again sorry for missing the meeting-- Paul Cox.

-- Hey i'm also supposed to be in on this. Sorry i couldn't contribute sooner because i was playing catchup in my other classes. Let me know what i can do and i'll be on it asap. - kirill (k.kashigin@gmail.com)
update: i'm gonna be helping Fedor with #2

PS, this article http://docs.google.com/viewer?a=v&q=cache:E7-H_pv_18wJ:citeseerx.ist.psu.edu/viewdoc/download%3Fdoi%3D10.1.1.92.2279%26rep%3Drep1%26type%3Dpdf+flash+memory+and+disk-based+file+systems&hl=en&gl=ca&pid=bl&srcid=ADGEESgspy-jqIdLOpaLYlPPoM56kjLPwXcL3_eMbTTBRkI7PG0jQKl9vIieTAYHubPu0EdQ0V4ccaf_p0S_SnqKMirSIM0Qoq5E0NpLd0M7LAGaE51wkD0F55cRSkX8dnTqx_9Yx2E7&sig=AHIEtbS-yfGI9Y48DJ0WyEEhmsXInelRGw looks really useful for part 3.

---same article as above but shorter link: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.160.5142

PPS, and this article looks really great for understanding how log based file systems work: http://delivery.acm.org/10.1145/150000/146943/p26-rosenblum.pdf?key1=146943&key2=3656986821&coll=GUIDE&dl=GUIDE&CFID=108397378&CFTOKEN=72657973

Hey Luc (TA) here, Anandtech ran a series of articles on solid state drives that you guys might find useful. It mostly looked at hardware aspects but it gives some interesting insights on how to modify file systems to better support flash memory.

http://www.anandtech.com/cpuchipsets/intel/showdoc.aspx?i=3403

http://www.anandtech.com/storage/showdoc.aspx?i=3531&p=1

http://anandtech.com/storage/showdoc.aspx?i=3631

--[[User:3maisons|3maisons]] 19:44, 12 October 2010 (UTC)

Hey Paul&Kirill,

If one of you guys could help me out with #2, that would be really great. I was going to work on that tomorrow, but I also have another large assignment to deal with and not having to do this research would greatly ease my life. Moreover, I do intend to work on writing&polishing the essay on Thursday as I have a lot of experience with that and it far more than research. Let me know if either one of you can help me with this.

The other person could probably read over what Luc posted for us and see if it fits into our framework. Just be sure to state who is going to do what.

Nick,

Honestly, we really hope to have the research done by Thursday. If that is the only day that you are free and you're not a writer, I'm honestly not sure what you could do. Perhaps someone else can think of something.

- Fedor

I'm gonna have something for #2 up tonight. -kirill

So I found this article on Reddit, posted from Linux Weekly News on pretty much exactly what we are looking at. It's entitled "Solid-state storage devices and the block layer"

http://lwn.net/SubscriberLink/408428/68fa8465da45967a/ --[[User:Gsmith6|Gsmith6]] 20:36, 13 October 2010 (UTC)

I wasn't exactly sure how much information i was supposed to present but here's what i got for #2:

Most conventional file systems are designed to me implemented on hard disk drives. This fact does not mean they cannot be implemented on a solid state drive (file storage that uses flash memory instead of magnetic discs). It would however, in many ways, defeat the purpose of using flash memory. The most consuming process for an HDD is seeking data by relocating the read-head and spinning the magnetic disk. A traditional file system optimizes the way it stores data by placing related blocks close-by on the disk to minimize mechanical movement within the HDD. One of the great advantages of flash memory, which accounts for its fast read speed, is that there is no need to seek data physically so there is no need to waste resources laying out the data in close proximity.
A traditional HDD file system will also attempt to defragment itself, moving blocks of data around for closer proximity on the magnetic disk. This process, although beneficial for HDD's, is harmful and inefficient for flash based storage. A flash optimal file system needs to reduce the amount of erase operations, since flash memory only has a limited amount of erase cycles as well as having very slow erase speeds.
When an HDD rewrites data to a physical location there is no need for it to erase the previously occupying data first, so a traditional disk based file system doesn't worry about erasing data from unused memory blocks. In contrast flash memory needs to first erase the data block before it can modify any of it contents. Since the erase procedure is extremely slow, its not practical to overwrite old data every time. It is also decremental to the life span of flash memory.
To maximize the potential of flash based memory the file system would have to write new data to empty memory blocks. This method would also call for some sort of garbage collection to erase unused blocks when the system is idle, which does not get implemented in conventional file systems since it is not needed.

--kirill

So Fedor and I were talking in the labs, and we came to the conclusion that we have been focusing on just the translation from a regular file system to a flash drive. We were under the impression that this was in fact the "Flash Optimized System", but pulling up some more articles, I'm finding that this is not necessarily the case.

This paper here http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.128.6156&rep=rep1&type=pdf.
shows an example from Axis Communications where they developed a file system specifically designed to be used on flash drives.

Now I haven't completely read it, so it might just be an optimized translational system, but its at least a start.

At our meeting today, we've decided that it would be best if people could post a rough summary of their notes in the appropriate sections, and I will rewrite them into an essay, which Fedor will go through later tonight to edit and add some more information.

Paul: I missed your comment that you weren't that great at writing, and good at research. If you want some articles behind the pay-walls, I've saved a bunch of them and emailed them to myself. Just email me (at the address at the top of the page) and I'll be more than happy to send some your way.

PS. some more references

Design tradeoffs for SSD performance http://portal.acm.org/citation.cfm?id=1404014.1404019
A log buffer-based flash translation layer using fully-associative sector translation http://delivery.acm.org/10.1145/1280000/1275990/a18-lee.pdf?key1=1275990&key2=0709607821&coll=GUIDE&dl=GUIDE&CFID=105787273&CFTOKEN=74601780

--[[User:Gsmith6|Gsmith6]] 15:03, 14 October 2010 (UTC)

I don't have any notes on this computer. >: I will be adding more to my section later on tonight. Sorry. ~Andrew

Hello dudes,

Just a quick note, try to include citations in your paragraphs - each time that you make a claim which came from evidence, put a little number [X, pp. page-number (if applicable)] into your text. Then, put the same [X] at the bottom of the page with the bibliographical information about the source. The prof hasn't yet gotten back to me about his preferred citation format, so just stick with this one for now:

Authors. ''Title''. Web-page. Date of article. Web (the word). Date you accessed it.

Here's an example:

[1] Kawaguchi, Nishioka, Tamoda. ''A Flash Memory Based File System''.
http://docs.google.com/viewer?a=v&q=cache:E7-H_pv_18wJ:citeseerx.ist.psu.edu/viewdoc/download%3Fdoi%3D10.1.1.92.2279%26rep%3Drep1%26type%3Dpdf+flash+memory+and+disk-based+file+systems&hl=en&gl=ca&pid=bl&srcid=ADGEESgspy-jqIdLOpaLYlPPoM56kjLPwXcL3_eMbTTBRkI7PG0jQKl9vIieTAYHubPu0EdQ0V4ccaf_p0S_SnqKMirSIM0Qoq5E0NpLd0M7LAGaE51wkD0F55cRSkX8dnTqx_9Yx2E7&sig=AHIEtbS-yfGI9Y48DJ0WyEEhmsXInelRGw . 1995. Web. Oct. 14, 2010.

Fedor

PS, its a good idea to check this fairly frequently between now and tomorrow morning - you never know when something will come up.

Phew... for a while there I was starting to think that I had nothing about the actual "Log-Based System", but it turns out that the "Transitional Layer" is the same thing. It looks like some articles are calling it the Log system, while others are calling it the transitional layer. Pretty sure I'm going to have an experts knowledge about flash drives after reading all these articles :P
--[[User:Gsmith6|Gsmith6]] 18:13, 14 October 2010 (UTC)

Hay Geoff this is what i got so far after reading a couple of the pdfs. the double tabed points are just my annotation on how they relate to the question.

Ware leveling: p1126-chang.pdf

* Uneven wearing of flash memory due to storing data close together
* Garbage collection prefers that no blocks have pages that have data that is constantly becoming invalid
* data that remains the same for longs periods of time should be moved from block that have not be written to much and moved to blocks that haven been erased frequently.

Log file structure: 926-rosenblum.pdf

* LFS based on assumption that frequently read files will be stored in cash and that the hard disk traffic will be dominated by writes
* Writes all new info to disk in a sequential structure called a log
* Data is stored permanently in these logs no other data is stored on the hard drive
* Converts many small random synchronous writes to a large asynchronous sequential write
** Good for flash because it cuts down on writing (prolongs drive life)
** It also good because it writes to a bigger section then a page. This means it can fill a block at a time so it doesn’t fill up other blocks with random writes that would later need to be cleaned. Cuts down on cleaning.
* Inode is stored in the log on the disk while an inode map is maintained in memory which points to the inode in the hard disk. as
** This is good for flash drives because reading does not hurt the drives life and it is fast.
** This means the map will not have to be updated on the disk as frequently cutting down on the writes.
* Log systems weakness is that it is susceptible to becoming fragmented due to the larger writes.
** Since flash drives do not require fragmentation this is fine. Also since flash drives have very fast random access the system does not become bogged down when the logs are fragmented
* Log system implements a cleaning system that scans a segment in and sees if there is live data in it. If there is a certain percentage of invalid data which goes according to the cleaning policy it will be cleaned. All the live data will be copied out and the segment will be erased.
** This is a garbage collector but its built into the file system.
* Segments contain a number of blocks. Segments can contain logs or parts of logs.

I'm still sifting though the other pdfs you sent me. Would you like me to post more info or should i format this into a paragraph or 2?

--Paul

I'm sorting through my notes and putting them into a digital format. Difficult because It's hard to remember what I copied directly out of the notes for my own reference, so I'm trying to de-plagarize. I'll upload what I have to the section by 20:30, but expect more updates. ~Andrew

Hey Paul,

Thanks for helping out with the research
I'm thinking that we probably have enough information (at least for the log-based system), so maybe if you could "try" and putting them into paragraphs. I'm kind of in the middle of typing up the essay, and I'm uploading new information every 10-20 minutes or so. Even if you could get something into paragraph form, I can go through and edit, rearrange, and add stuff as I get there. --[[User:Gsmith6|Gsmith6]] 23:51, 14 October 2010 (UTC)

I'm just going to dump my entire wiki so far into my profile page, because everything's being updated so quickly.
[[User:Abujaki]] ~Andrew

I'm sitting at my computer working on much less immediately important homework if someone wants me to do something. I'm not a great writer but if there's something that needs doing I can do it. -- Nick [[User:Nlessard|Nlessard]] 00:55, 15 October 2010 (UTC)

Hey guys,

Keep up the good work!

Geoff, it would be good if you uploaded the stuff you were typing as you got each section finished. I rewrote part 2 and the intro some hours ago and I guess I could go out and write a conclusion while stuff is still being updated.

The other thing is that the current version of part 1 doesn't really seem to serve the argument - I mean, it doesn't actually tell us why flash has the constraints that it does on a technical level... and that's not surprising because that information seems to be hard to find. Still, I'm going to see if I can find out anything about that, though, so far, I haven't had much luck.

Apart from this, I'll try to get up early tomorrow to look over what's there: make sure the argument works, etc.

Good luck with the writing,

Fedor

I think it has to do with how some transistors are made. Give me a second to research that... ~Andrew

From source 20, page 269 sec 4.6.4
Stress Induced Oxide leakage
...These devices are either erased ... orboth programmed and erased by a high field (Fowler-Nordheim) injection of electrons into a very thin dielectric film to charge and discharge the floating gate. Unfortunately, [passing] this current through the oxide degrades the quality of the oxide and eventually leads to breakdown. The wearout of tunnel oxide films during high-field stress has been correlated with the buildup of both positive or negative trapped charges."... there are still some things missing from this explanation... Give me a couple more seconds... and my brain won't process this for some reason. =_= What can you guys make of this? ~Andrew

And I said NOR Flash memory had fast fetch times. I found what I was looking for, just not too sure how to explain it in text. Silicon Oxide is used for electron injection methods, including the Fowler-Nordheim Tunneling method, where it seems to say that an electric current is passed across the oxide and it thins enough for a current to be passed through a barrier into the oxide conduction... band?

Kay. New resource [19], the massively complicated theories and science would put anyone to sleep, but the basic point is The Silicon oxide layer will degrade in quality to the point where charge trapping begins to occur, the more it's used, and the more electrons that tunnel through it over time. It's like a kneaded eraser scenario. The more you use it, the poorer quality it gets until it gets all flakey and cannot do its job anymore. The same happens with the SiO2 layer in the floating gate transistors ~Andrew

hmmm... alright, I think I understand that, could you maybe try your best and add it into the essay? If not I can try and whip something up to put in there. thanks --[[User:Gsmith6|Gsmith6]] 02:39, 15 October 2010 (UTC)

Wow, I'm sorry I made you go into that... that does explain the limited erase-cycles, though. Was it the use of these materials that made flash innovative? How does that explain the block-sized erasures?

Going to go write a conclusion now.

Fedor

While looking for what you requested, I found an entire section on the oxide breakdown... oops. :P
So really nothing changes, As electrons tunnel through the oxide layer, it deteriorates. When the damage becomes too great, the oxide abruptly loses its insulative properties. (damn firefox, that's a word) Looking for the erasures now ~Andrew

Hey guys,

I'm off to sleep, but I'll be up at 5am to see what else I can do.

Fedor

Aw, I just missed you.
It turns out that erasing entire blocks is necessary based on how the chip is built. For both NOR and NAND, pairs of word lines share an erase line, which is located near the floating gate. It uses FN tunneling to erase two lines of words at a time, making the sector the smallest size you can erase simply because that's how it's physically wired.
i.e []-mem byte |-erase line

[]|[][]|[]
[]|[][]|[]
[]|[][]|[]
[]|[][]|[] ... If that makes any sense... The erase line is separate from the byte select or word select lines

I'm prolly gonna take Fedor's advice and head to bed, but I'll likely pop back on before I go to sleep in case anyone needs me to look up anything else. :P

Talk:COMP 3000 Essay 1 2010 Question 10

2010-10-15T03:06:02Z

Abujaki:

Talk:COMP 3000 Essay 1 2010 Question 10

2010-10-15T02:20:12Z

Abujaki:

Talk:COMP 3000 Essay 1 2010 Question 10

2010-10-15T02:19:14Z

Abujaki:

Hey all,

I think we should write down our emails here so we can further discuss stuff without having to login here.
('''***Note that discussions over email can't be counted towards your participation grade!***'''--[[User:Soma|Anil]])

Geoff Smith (gsmith0413@gmail.com) - gsmith6

Andrew Bujáki (abujaki [at] Connect or Live.ca)
***I'm usually on MSN(Live) for collaboration at nights, Just make sure to put in a little message about who you are when you're adding me. :)

I used Google Scholar and came to this page http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=812717&tag=1#
Which briefly touches on the issues of Flash memory. Specifically, inability to update in place, and limited write/erase cycles.

Inability to update in place could refer to the way the flash disk is programmed, instead of bit-by-bit, it is programmed block-by-block. A block would have to be erased and completely reprogrammed in order to flip one bit after it's been set.
http://en.wikipedia.org/wiki/Flash_memory#Block_erasure

Limited write/erase: Flash memory typically has a short lifespan if it's being used a lot. Writing and erasing the memory (Changing, updating, etc) Will wear it out. Flash memory has a finite amount of writes, (varying on manufacturer, models, etc), and once they've been used up, you'll get bad sectors, corrupt data, and generally be SOL.
http://en.wikipedia.org/wiki/Flash_memory#Memory_wear

Filesystems would have to be changed to play nicely with these constraints, where it must use blocks efficiently and nicely, and minimize writing/erasing as much as possible.

I found a paper that talks about the performance, capabilities and limitations of NAND flash storage.

Abstract: "This presentation provides an in-depth examination of the
fundamental theoretical performance, capabilities, and
limitations of NAND Flash-based Solid State Storage (SSS). The
tutorial will explore the raw performance capabilities of NAND
Flash, and limitations to performance imposed by mitigation of
reliability issues, interfaces, protocols, and technology types.
Best practices for system integration of SSS will be discussed.
Performance achievements will be reviewed for various
products and applications. "

Link: http://www.flashmemorysummit.com/English/Collaterals/Proceedings/2009/20090812_T1B_Smith.pdf

There's no Starting place like Wikipedia, even if you shouldn't source it.

http://en.wikipedia.org/wiki/Flash_Memory

http://en.wikipedia.org/wiki/LogFS

http://en.wikipedia.org/wiki/Hard_disk

http://en.wikipedia.org/wiki/Wear_leveling

http://en.wikipedia.org/wiki/Hot_spot_%28computer_science%29

http://en.wikipedia.org/wiki/Solid-state_drive

Hey Guys,

We really don't have much time to get this done. Lets meet tomorrow after class and get our bearings to do this properly.

Fedor

A few of us have Networking immediately after class. I know personally I won't be able to make anything set on Tuesday.
Additionally, he spoke briefly about hotspots on the disk for our question last week, where places on the disk would be written to far more often than others.
As well, for bibliographical citing, http://bibme.org is a wonderful resource for the popular formats (I.e. MLA). If it should come down to that.
~Andrew

===links===

Start Posting some stuff to source from:

http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=1199079&tag=1
--"Introduction to flash memory"

http://portal.acm.org/citation.cfm?id=1244248
--"Wear Leveling" (it's about a proposed way of doing it, but explains a whole bunch of other things to do that)

http://portal.acm.org/citation.cfm?id=1731355
--"Online maintenance of very large random samples on flash storage" (ie dealing with the constraints of Flash Storage in a system that might actually be written to 100000 times)

http://vlsi.kaist.ac.kr/paper_list/2006_TC_CFFS.pdf
--"An Efficient NAND Flash File System for Flash Memory Storage" discuses shortcomings of using hard disk based file systems and current flash based file systems

http://maltiel-consulting.com/NAND_vs_NOR_Flash_Memory_Technology_Overview_Read_Write_Erase_speed_for_SLC_MLC_semiconductor_consulting_expert.pdf
--"NAND vs NOR Flash Memory" (note: i didn't get this off of Google scholar but it seems to be written by someone from Toshiba. is that ok?)

Hi everybody,

So here are the latest news. Geoff, Andrew and myself had a meeting after class today and came up with a plan for writing this thing.

We decided to have 3 parts:

1. What flash storage is, why its good but also why it must have the problems that it does (the assumption is that it must have them, why would it otherwise?)
[don't know much about this just now... basics include that there is NOR (reads slightly faster)and NAND (holds more, writes faster, erases much faster, lasts about ten times longer) flash with NAND being especially popular for storage (what's NOR good for?). Here, we'd ideally want to talk about why flash was invented (supposed as an alternative to slow ROM), why it was suitable for that, and how it works on a technical level. Then, we'd want to mention why this technical functionality was innovative and useful but also why it came with two serious set-backs: having a limited-number of re-write cycles and needing to erase a block at a time.]

Either way, Flash storage affords far faster fetch times than the traditional platter-based HDD, and stability of information in a sense. Where the data is not actually stored, but reprogrammed, in a sense, the data is more secure and is less likely to be erased easily. On that note, in order to flip a single bit, that entire block will need to be erased, then reprogrammed. In an 'old' HDD, let's say, When the HDD fails at the end of its life cycle, your data is gone. (unless you're willing to shell out $200/hr to have it recovered, yes I've seen companies in Ottawa that do this.) In a flash HDD, when it reaches the end of its life, it merely becomes read-only. Bugger for Databases, but useful for technical notes and archives, let's say.
With today's modern gaming computers, Flash memory can be good on quick load times, however with limited read-writes, it could afford better use to things that are not updated as frequently. I.e... Well I don't have a better example than a webserver hosting a company's CSS and scripts.
~Source: Years in the 'biz

Flash memory started out as a replacement for EPROMs. At the time EPROMs needed a UV photoemission to be erased while flash memory could be erased electronically. The first flash memory product came out in 1988 but it did not take off until the late 1990’s because it could not be reliable produced. NOR and NAND memory is named after the arrangement of the cells in the memory array. NOR based flash memory benefits from having very fast burst read times but slower write times. Due to the structure of NOR memory programs stored in NOR based memory can be executed without being loaded into RAM first. NAND flash memory has a very large storage capacity and can read and write large files relatively fast. NAND is more suited for storage while NOR memory is better suited for direct program execution such as in CMOS chips.
source: http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=1199079&tag=1 , http://maltiel-consulting.com/NAND_vs_NOR_Flash_Memory_Technology_Overview_Read_Write_Erase_speed_for_SLC_MLC_semiconductor_consulting_expert.pdf

2. How a traditional disk-based file-system works and why the limitations of flash storage make the two a poor match
[the obvious answer seems to be that traditional file-systems could just write to whatever memory was available but if they did this with a flash file-systems, certain chunks of memory would become unusable before others and the memory would be more difficult to work with. Also, disk-based file systems need to deal with seeking times which means that they want to organize their data in such a way as to reduce those (by putting related things together?) - with Flash, this isn't really a problem and thus one constraint the less to be concerned with.]

3. How a log based file-system works and why this method of operation is so well suited to working with flash memory especially in light of the latter's inherent limitations
[...]

At this time, the plan is that Geoff will work on #3 today, Andrew will work on #1 tomorrow and I will work on #2 tomorrow. The three of us will make an effort to consult some somewhat more painfully technical literature in order to gain insight into our respective queries. Whatever insight we find will be posted here.

Then, we will meet again on Thursday after class to decide how to actually write the essay.

PS, if there is anybody in the group besides the three of us - let us know so you can find a way to contribute to this... as at least two of us are competent essayists, painfully technical research would on one or more of the above topics would be a great way to contribute... especially if you could post it here prior to one of us going over the same thing.

Fedor

-- I'm not that great (but absolutely horrid) at essays and I'm alright at research, but if nothing else I have Thursday off and nothing (else) that needs doing by Friday so I can probably spend a bunch of time working on it just before it's due. -- ''Nick L''

-- Hay sorry I was unable to attend the meeting after class today. I am not too good at writing essays as well but I am pretty good at summarizing and researching. I am not too sure at what you would like me to do. Right now I'll assume you need me to research/summarizing articles for the 3 topics above. If you need me to do anything else post it here. I'll be checking the discussion regularly until this due. once again sorry for missing the meeting-- Paul Cox.

-- Hey i'm also supposed to be in on this. Sorry i couldn't contribute sooner because i was playing catchup in my other classes. Let me know what i can do and i'll be on it asap. - kirill (k.kashigin@gmail.com)
update: i'm gonna be helping Fedor with #2

PS, this article http://docs.google.com/viewer?a=v&q=cache:E7-H_pv_18wJ:citeseerx.ist.psu.edu/viewdoc/download%3Fdoi%3D10.1.1.92.2279%26rep%3Drep1%26type%3Dpdf+flash+memory+and+disk-based+file+systems&hl=en&gl=ca&pid=bl&srcid=ADGEESgspy-jqIdLOpaLYlPPoM56kjLPwXcL3_eMbTTBRkI7PG0jQKl9vIieTAYHubPu0EdQ0V4ccaf_p0S_SnqKMirSIM0Qoq5E0NpLd0M7LAGaE51wkD0F55cRSkX8dnTqx_9Yx2E7&sig=AHIEtbS-yfGI9Y48DJ0WyEEhmsXInelRGw looks really useful for part 3.

---same article as above but shorter link: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.160.5142

PPS, and this article looks really great for understanding how log based file systems work: http://delivery.acm.org/10.1145/150000/146943/p26-rosenblum.pdf?key1=146943&key2=3656986821&coll=GUIDE&dl=GUIDE&CFID=108397378&CFTOKEN=72657973

Hey Luc (TA) here, Anandtech ran a series of articles on solid state drives that you guys might find useful. It mostly looked at hardware aspects but it gives some interesting insights on how to modify file systems to better support flash memory.

http://www.anandtech.com/cpuchipsets/intel/showdoc.aspx?i=3403

http://www.anandtech.com/storage/showdoc.aspx?i=3531&p=1

http://anandtech.com/storage/showdoc.aspx?i=3631

--[[User:3maisons|3maisons]] 19:44, 12 October 2010 (UTC)

Hey Paul&Kirill,

If one of you guys could help me out with #2, that would be really great. I was going to work on that tomorrow, but I also have another large assignment to deal with and not having to do this research would greatly ease my life. Moreover, I do intend to work on writing&polishing the essay on Thursday as I have a lot of experience with that and it far more than research. Let me know if either one of you can help me with this.

The other person could probably read over what Luc posted for us and see if it fits into our framework. Just be sure to state who is going to do what.

Nick,

Honestly, we really hope to have the research done by Thursday. If that is the only day that you are free and you're not a writer, I'm honestly not sure what you could do. Perhaps someone else can think of something.

- Fedor

I'm gonna have something for #2 up tonight. -kirill

So I found this article on Reddit, posted from Linux Weekly News on pretty much exactly what we are looking at. It's entitled "Solid-state storage devices and the block layer"

http://lwn.net/SubscriberLink/408428/68fa8465da45967a/ --[[User:Gsmith6|Gsmith6]] 20:36, 13 October 2010 (UTC)

I wasn't exactly sure how much information i was supposed to present but here's what i got for #2:

Most conventional file systems are designed to me implemented on hard disk drives. This fact does not mean they cannot be implemented on a solid state drive (file storage that uses flash memory instead of magnetic discs). It would however, in many ways, defeat the purpose of using flash memory. The most consuming process for an HDD is seeking data by relocating the read-head and spinning the magnetic disk. A traditional file system optimizes the way it stores data by placing related blocks close-by on the disk to minimize mechanical movement within the HDD. One of the great advantages of flash memory, which accounts for its fast read speed, is that there is no need to seek data physically so there is no need to waste resources laying out the data in close proximity.
A traditional HDD file system will also attempt to defragment itself, moving blocks of data around for closer proximity on the magnetic disk. This process, although beneficial for HDD's, is harmful and inefficient for flash based storage. A flash optimal file system needs to reduce the amount of erase operations, since flash memory only has a limited amount of erase cycles as well as having very slow erase speeds.
When an HDD rewrites data to a physical location there is no need for it to erase the previously occupying data first, so a traditional disk based file system doesn't worry about erasing data from unused memory blocks. In contrast flash memory needs to first erase the data block before it can modify any of it contents. Since the erase procedure is extremely slow, its not practical to overwrite old data every time. It is also decremental to the life span of flash memory.
To maximize the potential of flash based memory the file system would have to write new data to empty memory blocks. This method would also call for some sort of garbage collection to erase unused blocks when the system is idle, which does not get implemented in conventional file systems since it is not needed.

--kirill

So Fedor and I were talking in the labs, and we came to the conclusion that we have been focusing on just the translation from a regular file system to a flash drive. We were under the impression that this was in fact the "Flash Optimized System", but pulling up some more articles, I'm finding that this is not necessarily the case.

This paper here http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.128.6156&rep=rep1&type=pdf.
shows an example from Axis Communications where they developed a file system specifically designed to be used on flash drives.

Now I haven't completely read it, so it might just be an optimized translational system, but its at least a start.

At our meeting today, we've decided that it would be best if people could post a rough summary of their notes in the appropriate sections, and I will rewrite them into an essay, which Fedor will go through later tonight to edit and add some more information.

Paul: I missed your comment that you weren't that great at writing, and good at research. If you want some articles behind the pay-walls, I've saved a bunch of them and emailed them to myself. Just email me (at the address at the top of the page) and I'll be more than happy to send some your way.

PS. some more references

Design tradeoffs for SSD performance http://portal.acm.org/citation.cfm?id=1404014.1404019
A log buffer-based flash translation layer using fully-associative sector translation http://delivery.acm.org/10.1145/1280000/1275990/a18-lee.pdf?key1=1275990&key2=0709607821&coll=GUIDE&dl=GUIDE&CFID=105787273&CFTOKEN=74601780

--[[User:Gsmith6|Gsmith6]] 15:03, 14 October 2010 (UTC)

I don't have any notes on this computer. >: I will be adding more to my section later on tonight. Sorry. ~Andrew

Hello dudes,

Just a quick note, try to include citations in your paragraphs - each time that you make a claim which came from evidence, put a little number [X, pp. page-number (if applicable)] into your text. Then, put the same [X] at the bottom of the page with the bibliographical information about the source. The prof hasn't yet gotten back to me about his preferred citation format, so just stick with this one for now:

Authors. ''Title''. Web-page. Date of article. Web (the word). Date you accessed it.

Here's an example:

[1] Kawaguchi, Nishioka, Tamoda. ''A Flash Memory Based File System''.
http://docs.google.com/viewer?a=v&q=cache:E7-H_pv_18wJ:citeseerx.ist.psu.edu/viewdoc/download%3Fdoi%3D10.1.1.92.2279%26rep%3Drep1%26type%3Dpdf+flash+memory+and+disk-based+file+systems&hl=en&gl=ca&pid=bl&srcid=ADGEESgspy-jqIdLOpaLYlPPoM56kjLPwXcL3_eMbTTBRkI7PG0jQKl9vIieTAYHubPu0EdQ0V4ccaf_p0S_SnqKMirSIM0Qoq5E0NpLd0M7LAGaE51wkD0F55cRSkX8dnTqx_9Yx2E7&sig=AHIEtbS-yfGI9Y48DJ0WyEEhmsXInelRGw . 1995. Web. Oct. 14, 2010.

Fedor

PS, its a good idea to check this fairly frequently between now and tomorrow morning - you never know when something will come up.

Phew... for a while there I was starting to think that I had nothing about the actual "Log-Based System", but it turns out that the "Transitional Layer" is the same thing. It looks like some articles are calling it the Log system, while others are calling it the transitional layer. Pretty sure I'm going to have an experts knowledge about flash drives after reading all these articles :P
--[[User:Gsmith6|Gsmith6]] 18:13, 14 October 2010 (UTC)

Hay Geoff this is what i got so far after reading a couple of the pdfs. the double tabed points are just my annotation on how they relate to the question.

Ware leveling: p1126-chang.pdf

* Uneven wearing of flash memory due to storing data close together
* Garbage collection prefers that no blocks have pages that have data that is constantly becoming invalid
* data that remains the same for longs periods of time should be moved from block that have not be written to much and moved to blocks that haven been erased frequently.

Log file structure: 926-rosenblum.pdf

* LFS based on assumption that frequently read files will be stored in cash and that the hard disk traffic will be dominated by writes
* Writes all new info to disk in a sequential structure called a log
* Data is stored permanently in these logs no other data is stored on the hard drive
* Converts many small random synchronous writes to a large asynchronous sequential write
** Good for flash because it cuts down on writing (prolongs drive life)
** It also good because it writes to a bigger section then a page. This means it can fill a block at a time so it doesn’t fill up other blocks with random writes that would later need to be cleaned. Cuts down on cleaning.
* Inode is stored in the log on the disk while an inode map is maintained in memory which points to the inode in the hard disk. as
** This is good for flash drives because reading does not hurt the drives life and it is fast.
** This means the map will not have to be updated on the disk as frequently cutting down on the writes.
* Log systems weakness is that it is susceptible to becoming fragmented due to the larger writes.
** Since flash drives do not require fragmentation this is fine. Also since flash drives have very fast random access the system does not become bogged down when the logs are fragmented
* Log system implements a cleaning system that scans a segment in and sees if there is live data in it. If there is a certain percentage of invalid data which goes according to the cleaning policy it will be cleaned. All the live data will be copied out and the segment will be erased.
** This is a garbage collector but its built into the file system.
* Segments contain a number of blocks. Segments can contain logs or parts of logs.

I'm still sifting though the other pdfs you sent me. Would you like me to post more info or should i format this into a paragraph or 2?

--Paul

I'm sorting through my notes and putting them into a digital format. Difficult because It's hard to remember what I copied directly out of the notes for my own reference, so I'm trying to de-plagarize. I'll upload what I have to the section by 20:30, but expect more updates. ~Andrew

Hey Paul,

Thanks for helping out with the research
I'm thinking that we probably have enough information (at least for the log-based system), so maybe if you could "try" and putting them into paragraphs. I'm kind of in the middle of typing up the essay, and I'm uploading new information every 10-20 minutes or so. Even if you could get something into paragraph form, I can go through and edit, rearrange, and add stuff as I get there. --[[User:Gsmith6|Gsmith6]] 23:51, 14 October 2010 (UTC)

I'm just going to dump my entire wiki so far into my profile page, because everything's being updated so quickly.
[[User:Abujaki]] ~Andrew

I'm sitting at my computer working on much less immediately important homework if someone wants me to do something. I'm not a great writer but if there's something that needs doing I can do it. -- Nick [[User:Nlessard|Nlessard]] 00:55, 15 October 2010 (UTC)

Hey guys,

Keep up the good work!

Geoff, it would be good if you uploaded the stuff you were typing as you got each section finished. I rewrote part 2 and the intro some hours ago and I guess I could go out and write a conclusion while stuff is still being updated.

The other thing is that the current version of part 1 doesn't really seem to serve the argument - I mean, it doesn't actually tell us why flash has the constraints that it does on a technical level... and that's not surprising because that information seems to be hard to find. Still, I'm going to see if I can find out anything about that, though, so far, I haven't had much luck.

Apart from this, I'll try to get up early tomorrow to look over what's there: make sure the argument works, etc.

Good luck with the writing,

Fedor

I think it has to do with how some transistors are made. Give me a second to research that... ~Andrew

From source 20, page 269 sec 4.6.4
Stress Induced Oxide leakage
...These devices are either erased ... orboth programmed and erased by a high field (Fowler-Nordheim) injection of electrons into a very thin dielectric film to charge and discharge the floating gate. Unfortunately, [passing] this current through the oxide degrades the quality of the oxide and eventually leads to breakdown. The wearout of tunnel oxide films during high-field stress has been correlated with the buildup of both positive or negative trapped charges."... there are still some things missing from this explanation... Give me a couple more seconds... and my brain won't process this for some reason. =_= What can you guys make of this? ~Andrew

And I said NOR Flash memory had fast fetch times. I found what I was looking for, just not too sure how to explain it in text. Silicon Oxide is used for electron injection methods, including the Fowler-Nordheim Tunneling method, where it seems to say that an electric current is passed across the oxide and it thins enough for a current to be passed through a barrier into the oxide conduction... band?

Kay. New resource [18], the massively complicated theories and science would put anyone to sleep, but the basic point is The Silicon oxide layer will degrade in quality to the point where charge trapping begins to occur, the more it's used, and the more electrons that tunnel through it over time. It's like a kneaded eraser scenario. The more you use it, the poorer quality it gets until it gets all flakey and cannot do its job anymore. The same happens with the SiO2 layer in the floating gate transistors ~Andrew

Talk:COMP 3000 Essay 1 2010 Question 10

2010-10-15T02:18:41Z

Abujaki:

Hey all,

I think we should write down our emails here so we can further discuss stuff without having to login here.
('''***Note that discussions over email can't be counted towards your participation grade!***'''--[[User:Soma|Anil]])

Geoff Smith (gsmith0413@gmail.com) - gsmith6

Andrew Bujáki (abujaki [at] Connect or Live.ca)
***I'm usually on MSN(Live) for collaboration at nights, Just make sure to put in a little message about who you are when you're adding me. :)

I used Google Scholar and came to this page http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=812717&tag=1#
Which briefly touches on the issues of Flash memory. Specifically, inability to update in place, and limited write/erase cycles.

Inability to update in place could refer to the way the flash disk is programmed, instead of bit-by-bit, it is programmed block-by-block. A block would have to be erased and completely reprogrammed in order to flip one bit after it's been set.
http://en.wikipedia.org/wiki/Flash_memory#Block_erasure

Limited write/erase: Flash memory typically has a short lifespan if it's being used a lot. Writing and erasing the memory (Changing, updating, etc) Will wear it out. Flash memory has a finite amount of writes, (varying on manufacturer, models, etc), and once they've been used up, you'll get bad sectors, corrupt data, and generally be SOL.
http://en.wikipedia.org/wiki/Flash_memory#Memory_wear

Filesystems would have to be changed to play nicely with these constraints, where it must use blocks efficiently and nicely, and minimize writing/erasing as much as possible.

I found a paper that talks about the performance, capabilities and limitations of NAND flash storage.

Abstract: "This presentation provides an in-depth examination of the
fundamental theoretical performance, capabilities, and
limitations of NAND Flash-based Solid State Storage (SSS). The
tutorial will explore the raw performance capabilities of NAND
Flash, and limitations to performance imposed by mitigation of
reliability issues, interfaces, protocols, and technology types.
Best practices for system integration of SSS will be discussed.
Performance achievements will be reviewed for various
products and applications. "

Link: http://www.flashmemorysummit.com/English/Collaterals/Proceedings/2009/20090812_T1B_Smith.pdf

There's no Starting place like Wikipedia, even if you shouldn't source it.

http://en.wikipedia.org/wiki/Flash_Memory

http://en.wikipedia.org/wiki/LogFS

http://en.wikipedia.org/wiki/Hard_disk

http://en.wikipedia.org/wiki/Wear_leveling

http://en.wikipedia.org/wiki/Hot_spot_%28computer_science%29

http://en.wikipedia.org/wiki/Solid-state_drive

Hey Guys,

We really don't have much time to get this done. Lets meet tomorrow after class and get our bearings to do this properly.

Fedor

A few of us have Networking immediately after class. I know personally I won't be able to make anything set on Tuesday.
Additionally, he spoke briefly about hotspots on the disk for our question last week, where places on the disk would be written to far more often than others.
As well, for bibliographical citing, http://bibme.org is a wonderful resource for the popular formats (I.e. MLA). If it should come down to that.
~Andrew

===links===

Start Posting some stuff to source from:

http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=1199079&tag=1
--"Introduction to flash memory"

http://portal.acm.org/citation.cfm?id=1244248
--"Wear Leveling" (it's about a proposed way of doing it, but explains a whole bunch of other things to do that)

http://portal.acm.org/citation.cfm?id=1731355
--"Online maintenance of very large random samples on flash storage" (ie dealing with the constraints of Flash Storage in a system that might actually be written to 100000 times)

http://vlsi.kaist.ac.kr/paper_list/2006_TC_CFFS.pdf
--"An Efficient NAND Flash File System for Flash Memory Storage" discuses shortcomings of using hard disk based file systems and current flash based file systems

http://maltiel-consulting.com/NAND_vs_NOR_Flash_Memory_Technology_Overview_Read_Write_Erase_speed_for_SLC_MLC_semiconductor_consulting_expert.pdf
--"NAND vs NOR Flash Memory" (note: i didn't get this off of Google scholar but it seems to be written by someone from Toshiba. is that ok?)

Hi everybody,

So here are the latest news. Geoff, Andrew and myself had a meeting after class today and came up with a plan for writing this thing.

We decided to have 3 parts:

1. What flash storage is, why its good but also why it must have the problems that it does (the assumption is that it must have them, why would it otherwise?)
[don't know much about this just now... basics include that there is NOR (reads slightly faster)and NAND (holds more, writes faster, erases much faster, lasts about ten times longer) flash with NAND being especially popular for storage (what's NOR good for?). Here, we'd ideally want to talk about why flash was invented (supposed as an alternative to slow ROM), why it was suitable for that, and how it works on a technical level. Then, we'd want to mention why this technical functionality was innovative and useful but also why it came with two serious set-backs: having a limited-number of re-write cycles and needing to erase a block at a time.]

Either way, Flash storage affords far faster fetch times than the traditional platter-based HDD, and stability of information in a sense. Where the data is not actually stored, but reprogrammed, in a sense, the data is more secure and is less likely to be erased easily. On that note, in order to flip a single bit, that entire block will need to be erased, then reprogrammed. In an 'old' HDD, let's say, When the HDD fails at the end of its life cycle, your data is gone. (unless you're willing to shell out $200/hr to have it recovered, yes I've seen companies in Ottawa that do this.) In a flash HDD, when it reaches the end of its life, it merely becomes read-only. Bugger for Databases, but useful for technical notes and archives, let's say.
With today's modern gaming computers, Flash memory can be good on quick load times, however with limited read-writes, it could afford better use to things that are not updated as frequently. I.e... Well I don't have a better example than a webserver hosting a company's CSS and scripts.
~Source: Years in the 'biz

Flash memory started out as a replacement for EPROMs. At the time EPROMs needed a UV photoemission to be erased while flash memory could be erased electronically. The first flash memory product came out in 1988 but it did not take off until the late 1990’s because it could not be reliable produced. NOR and NAND memory is named after the arrangement of the cells in the memory array. NOR based flash memory benefits from having very fast burst read times but slower write times. Due to the structure of NOR memory programs stored in NOR based memory can be executed without being loaded into RAM first. NAND flash memory has a very large storage capacity and can read and write large files relatively fast. NAND is more suited for storage while NOR memory is better suited for direct program execution such as in CMOS chips.
source: http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=1199079&tag=1 , http://maltiel-consulting.com/NAND_vs_NOR_Flash_Memory_Technology_Overview_Read_Write_Erase_speed_for_SLC_MLC_semiconductor_consulting_expert.pdf

2. How a traditional disk-based file-system works and why the limitations of flash storage make the two a poor match
[the obvious answer seems to be that traditional file-systems could just write to whatever memory was available but if they did this with a flash file-systems, certain chunks of memory would become unusable before others and the memory would be more difficult to work with. Also, disk-based file systems need to deal with seeking times which means that they want to organize their data in such a way as to reduce those (by putting related things together?) - with Flash, this isn't really a problem and thus one constraint the less to be concerned with.]

3. How a log based file-system works and why this method of operation is so well suited to working with flash memory especially in light of the latter's inherent limitations
[...]

At this time, the plan is that Geoff will work on #3 today, Andrew will work on #1 tomorrow and I will work on #2 tomorrow. The three of us will make an effort to consult some somewhat more painfully technical literature in order to gain insight into our respective queries. Whatever insight we find will be posted here.

Then, we will meet again on Thursday after class to decide how to actually write the essay.

PS, if there is anybody in the group besides the three of us - let us know so you can find a way to contribute to this... as at least two of us are competent essayists, painfully technical research would on one or more of the above topics would be a great way to contribute... especially if you could post it here prior to one of us going over the same thing.

Fedor

-- I'm not that great (but absolutely horrid) at essays and I'm alright at research, but if nothing else I have Thursday off and nothing (else) that needs doing by Friday so I can probably spend a bunch of time working on it just before it's due. -- ''Nick L''

-- Hay sorry I was unable to attend the meeting after class today. I am not too good at writing essays as well but I am pretty good at summarizing and researching. I am not too sure at what you would like me to do. Right now I'll assume you need me to research/summarizing articles for the 3 topics above. If you need me to do anything else post it here. I'll be checking the discussion regularly until this due. once again sorry for missing the meeting-- Paul Cox.

-- Hey i'm also supposed to be in on this. Sorry i couldn't contribute sooner because i was playing catchup in my other classes. Let me know what i can do and i'll be on it asap. - kirill (k.kashigin@gmail.com)
update: i'm gonna be helping Fedor with #2

PS, this article http://docs.google.com/viewer?a=v&q=cache:E7-H_pv_18wJ:citeseerx.ist.psu.edu/viewdoc/download%3Fdoi%3D10.1.1.92.2279%26rep%3Drep1%26type%3Dpdf+flash+memory+and+disk-based+file+systems&hl=en&gl=ca&pid=bl&srcid=ADGEESgspy-jqIdLOpaLYlPPoM56kjLPwXcL3_eMbTTBRkI7PG0jQKl9vIieTAYHubPu0EdQ0V4ccaf_p0S_SnqKMirSIM0Qoq5E0NpLd0M7LAGaE51wkD0F55cRSkX8dnTqx_9Yx2E7&sig=AHIEtbS-yfGI9Y48DJ0WyEEhmsXInelRGw looks really useful for part 3.

---same article as above but shorter link: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.160.5142

PPS, and this article looks really great for understanding how log based file systems work: http://delivery.acm.org/10.1145/150000/146943/p26-rosenblum.pdf?key1=146943&key2=3656986821&coll=GUIDE&dl=GUIDE&CFID=108397378&CFTOKEN=72657973

Hey Luc (TA) here, Anandtech ran a series of articles on solid state drives that you guys might find useful. It mostly looked at hardware aspects but it gives some interesting insights on how to modify file systems to better support flash memory.

http://www.anandtech.com/cpuchipsets/intel/showdoc.aspx?i=3403

http://www.anandtech.com/storage/showdoc.aspx?i=3531&p=1

http://anandtech.com/storage/showdoc.aspx?i=3631

--[[User:3maisons|3maisons]] 19:44, 12 October 2010 (UTC)

Hey Paul&Kirill,

If one of you guys could help me out with #2, that would be really great. I was going to work on that tomorrow, but I also have another large assignment to deal with and not having to do this research would greatly ease my life. Moreover, I do intend to work on writing&polishing the essay on Thursday as I have a lot of experience with that and it far more than research. Let me know if either one of you can help me with this.

The other person could probably read over what Luc posted for us and see if it fits into our framework. Just be sure to state who is going to do what.

Nick,

Honestly, we really hope to have the research done by Thursday. If that is the only day that you are free and you're not a writer, I'm honestly not sure what you could do. Perhaps someone else can think of something.

- Fedor

I'm gonna have something for #2 up tonight. -kirill

So I found this article on Reddit, posted from Linux Weekly News on pretty much exactly what we are looking at. It's entitled "Solid-state storage devices and the block layer"

http://lwn.net/SubscriberLink/408428/68fa8465da45967a/ --[[User:Gsmith6|Gsmith6]] 20:36, 13 October 2010 (UTC)

I wasn't exactly sure how much information i was supposed to present but here's what i got for #2:

Most conventional file systems are designed to me implemented on hard disk drives. This fact does not mean they cannot be implemented on a solid state drive (file storage that uses flash memory instead of magnetic discs). It would however, in many ways, defeat the purpose of using flash memory. The most consuming process for an HDD is seeking data by relocating the read-head and spinning the magnetic disk. A traditional file system optimizes the way it stores data by placing related blocks close-by on the disk to minimize mechanical movement within the HDD. One of the great advantages of flash memory, which accounts for its fast read speed, is that there is no need to seek data physically so there is no need to waste resources laying out the data in close proximity.
A traditional HDD file system will also attempt to defragment itself, moving blocks of data around for closer proximity on the magnetic disk. This process, although beneficial for HDD's, is harmful and inefficient for flash based storage. A flash optimal file system needs to reduce the amount of erase operations, since flash memory only has a limited amount of erase cycles as well as having very slow erase speeds.
When an HDD rewrites data to a physical location there is no need for it to erase the previously occupying data first, so a traditional disk based file system doesn't worry about erasing data from unused memory blocks. In contrast flash memory needs to first erase the data block before it can modify any of it contents. Since the erase procedure is extremely slow, its not practical to overwrite old data every time. It is also decremental to the life span of flash memory.
To maximize the potential of flash based memory the file system would have to write new data to empty memory blocks. This method would also call for some sort of garbage collection to erase unused blocks when the system is idle, which does not get implemented in conventional file systems since it is not needed.

--kirill

So Fedor and I were talking in the labs, and we came to the conclusion that we have been focusing on just the translation from a regular file system to a flash drive. We were under the impression that this was in fact the "Flash Optimized System", but pulling up some more articles, I'm finding that this is not necessarily the case.

This paper here http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.128.6156&rep=rep1&type=pdf.
shows an example from Axis Communications where they developed a file system specifically designed to be used on flash drives.

Now I haven't completely read it, so it might just be an optimized translational system, but its at least a start.

At our meeting today, we've decided that it would be best if people could post a rough summary of their notes in the appropriate sections, and I will rewrite them into an essay, which Fedor will go through later tonight to edit and add some more information.

Paul: I missed your comment that you weren't that great at writing, and good at research. If you want some articles behind the pay-walls, I've saved a bunch of them and emailed them to myself. Just email me (at the address at the top of the page) and I'll be more than happy to send some your way.

PS. some more references

Design tradeoffs for SSD performance http://portal.acm.org/citation.cfm?id=1404014.1404019
A log buffer-based flash translation layer using fully-associative sector translation http://delivery.acm.org/10.1145/1280000/1275990/a18-lee.pdf?key1=1275990&key2=0709607821&coll=GUIDE&dl=GUIDE&CFID=105787273&CFTOKEN=74601780

--[[User:Gsmith6|Gsmith6]] 15:03, 14 October 2010 (UTC)

I don't have any notes on this computer. >: I will be adding more to my section later on tonight. Sorry. ~Andrew

Hello dudes,

Just a quick note, try to include citations in your paragraphs - each time that you make a claim which came from evidence, put a little number [X, pp. page-number (if applicable)] into your text. Then, put the same [X] at the bottom of the page with the bibliographical information about the source. The prof hasn't yet gotten back to me about his preferred citation format, so just stick with this one for now:

Authors. ''Title''. Web-page. Date of article. Web (the word). Date you accessed it.

Here's an example:

[1] Kawaguchi, Nishioka, Tamoda. ''A Flash Memory Based File System''.
http://docs.google.com/viewer?a=v&q=cache:E7-H_pv_18wJ:citeseerx.ist.psu.edu/viewdoc/download%3Fdoi%3D10.1.1.92.2279%26rep%3Drep1%26type%3Dpdf+flash+memory+and+disk-based+file+systems&hl=en&gl=ca&pid=bl&srcid=ADGEESgspy-jqIdLOpaLYlPPoM56kjLPwXcL3_eMbTTBRkI7PG0jQKl9vIieTAYHubPu0EdQ0V4ccaf_p0S_SnqKMirSIM0Qoq5E0NpLd0M7LAGaE51wkD0F55cRSkX8dnTqx_9Yx2E7&sig=AHIEtbS-yfGI9Y48DJ0WyEEhmsXInelRGw . 1995. Web. Oct. 14, 2010.

Fedor

PS, its a good idea to check this fairly frequently between now and tomorrow morning - you never know when something will come up.

Phew... for a while there I was starting to think that I had nothing about the actual "Log-Based System", but it turns out that the "Transitional Layer" is the same thing. It looks like some articles are calling it the Log system, while others are calling it the transitional layer. Pretty sure I'm going to have an experts knowledge about flash drives after reading all these articles :P
--[[User:Gsmith6|Gsmith6]] 18:13, 14 October 2010 (UTC)

Hay Geoff this is what i got so far after reading a couple of the pdfs. the double tabed points are just my annotation on how they relate to the question.

Ware leveling: p1126-chang.pdf

* Uneven wearing of flash memory due to storing data close together
* Garbage collection prefers that no blocks have pages that have data that is constantly becoming invalid
* data that remains the same for longs periods of time should be moved from block that have not be written to much and moved to blocks that haven been erased frequently.

Log file structure: 926-rosenblum.pdf

* LFS based on assumption that frequently read files will be stored in cash and that the hard disk traffic will be dominated by writes
* Writes all new info to disk in a sequential structure called a log
* Data is stored permanently in these logs no other data is stored on the hard drive
* Converts many small random synchronous writes to a large asynchronous sequential write
** Good for flash because it cuts down on writing (prolongs drive life)
** It also good because it writes to a bigger section then a page. This means it can fill a block at a time so it doesn’t fill up other blocks with random writes that would later need to be cleaned. Cuts down on cleaning.
* Inode is stored in the log on the disk while an inode map is maintained in memory which points to the inode in the hard disk. as
** This is good for flash drives because reading does not hurt the drives life and it is fast.
** This means the map will not have to be updated on the disk as frequently cutting down on the writes.
* Log systems weakness is that it is susceptible to becoming fragmented due to the larger writes.
** Since flash drives do not require fragmentation this is fine. Also since flash drives have very fast random access the system does not become bogged down when the logs are fragmented
* Log system implements a cleaning system that scans a segment in and sees if there is live data in it. If there is a certain percentage of invalid data which goes according to the cleaning policy it will be cleaned. All the live data will be copied out and the segment will be erased.
** This is a garbage collector but its built into the file system.
* Segments contain a number of blocks. Segments can contain logs or parts of logs.

I'm still sifting though the other pdfs you sent me. Would you like me to post more info or should i format this into a paragraph or 2?

--Paul

I'm sorting through my notes and putting them into a digital format. Difficult because It's hard to remember what I copied directly out of the notes for my own reference, so I'm trying to de-plagarize. I'll upload what I have to the section by 20:30, but expect more updates. ~Andrew

Hey Paul,

Thanks for helping out with the research
I'm thinking that we probably have enough information (at least for the log-based system), so maybe if you could "try" and putting them into paragraphs. I'm kind of in the middle of typing up the essay, and I'm uploading new information every 10-20 minutes or so. Even if you could get something into paragraph form, I can go through and edit, rearrange, and add stuff as I get there. --[[User:Gsmith6|Gsmith6]] 23:51, 14 October 2010 (UTC)

I'm just going to dump my entire wiki so far into my profile page, because everything's being updated so quickly.
[[User:Abujaki]] ~Andrew

I'm sitting at my computer working on much less immediately important homework if someone wants me to do something. I'm not a great writer but if there's something that needs doing I can do it. -- Nick [[User:Nlessard|Nlessard]] 00:55, 15 October 2010 (UTC)

Hey guys,

Keep up the good work!

Geoff, it would be good if you uploaded the stuff you were typing as you got each section finished. I rewrote part 2 and the intro some hours ago and I guess I could go out and write a conclusion while stuff is still being updated.

The other thing is that the current version of part 1 doesn't really seem to serve the argument - I mean, it doesn't actually tell us why flash has the constraints that it does on a technical level... and that's not surprising because that information seems to be hard to find. Still, I'm going to see if I can find out anything about that, though, so far, I haven't had much luck.

Apart from this, I'll try to get up early tomorrow to look over what's there: make sure the argument works, etc.

Good luck with the writing,

Fedor

I think it has to do with how some transistors are made. Give me a second to research that... ~Andrew

From source 20, page 269 sec 4.6.4
Stress Induced Oxide leakage
...These devices are either erased ... orboth programmed and erased by a high field (Fowler-Nordheim) injection of electrons into a very thin dielectric film to charge and discharge the floating gate. Unfortunately, [passing] this current through the oxide degrades the quality of the oxide and eventually leads to breakdown. The wearout of tunnel oxide films during high-field stress has been correlated with the buildup of both positive or negative trapped charges."... there are still some things missing from this explanation... Give me a couple more seconds... and my brain won't process this for some reason. =_= What can you guys make of this? ~Andrew

And I said NOR Flash memory had fast fetch times. I found what I was looking for, just not too sure how to explain it in text. Silicon Oxide is used for electron injection methods, including the Fowler-Nordheim Tunneling method, where it seems to say that an electric current is passed across the oxide and it thins enough for a current to be passed through a barrier into the oxide conduction... band?

Kay. New resource [18], the massively complicated theories and science would put anyone to sleep, but the basic point is The Silicon oxide layer will degrade in quality to the point where charge trapping begins to occur, the more it's used, and the more electrons that tunnel through it over time. It's like a kneaded eraser scenario. The more you use it, the poorer quality it gets until it gets all flakey and cannot do its job anymore. The same happens with the SiO2 layer in the floating gate transistors

Talk:COMP 3000 Essay 1 2010 Question 10

2010-10-15T02:12:17Z

Abujaki:

Talk:COMP 3000 Essay 1 2010 Question 10

2010-10-15T02:00:04Z

Abujaki:

Talk:COMP 3000 Essay 1 2010 Question 10

2010-10-15T01:53:12Z

Abujaki:

User:Abujaki

2010-10-15T00:23:37Z

Abujaki:

Essay:

===== How does it work? =====
The data is stored as a certain voltage either above a preset x level, or below a preset y level, both determined by the manufacturer. A high voltage is typically read as a 1, and a low voltage is typically a 0. The voltage in question is preserved in a 'Floating gate' transistor, where an additional gate is sammiched between two insulators. This ensures there is no voltage leak (Provides the nonvolatility and prevents damage to the stored data during the read step.)

===== NOR and NAND =====
The two main types of flash memory are NOR and NAND. Both of them consist of a grid of memory Floating Gate transistors.

====== NOR ======
The chips are arranged in a logical grid pattern in parallel, using Word lines and bit lines to access the transistors to read/write to.
Word = Y lines
Byte = X lines.
• Reads faster
• Should be careful not to over-erase the transistors (Depletion mode)
• Fast random read/write
• Additionally, NOR Guarantees 100% good bits, so error-checking and correction doesn't need to be programmed into the system.

====== NAND ======
* 8 or 16 transistors in series, between two select gates.
* The string gate ensures selectivity???
* The Ground gate keeps current from passing through the cell while the memory is programming
* Depletion mode is okay, but the
* Physically smaller cell size (85% smaller than NOR) [20]
* Because the bytes are in serial, a word can be written to memory all at once instead of bit-by-bit like in NOR
* Primarily preferred for data storage and removable media
* Offers redundant memory and error-correcting to remove bad bits.
* Comparatively slower read times because the bytes are linked in serial.
* More complex than NOR
* Slightly more costly than NOR

===== Strengths =====
* Cheap
* High-density storage (Lots of data per square inch)
* Long data retention
* Fast read/write times
* Erasable
* Flash memory is nonvolatile. This means even after the power is removed from the device, the memory device will retain the information programmed into it. Typical manufacturer specifications require nonvolatile memory to retain data for at least 10 years before the first erroneous readout of data.

===== Weaknesses =====
* Limited read/erases. (See endurance)
* Not Byte-alterable. In order to flip a byte, you would need to erase and reprogram an entire memory block

===== Why use flash? =====
* Flash memory, because of its data retention capabilities coupled with quick read/write cycles is a staple in today's portable device technology.
* NOR Flash memory quickly replaced EPROMs ( Erasable Programmable Read-Only Memory) in development. While both are nonvolatile and erasable, Flash also offers cost-effectiveness, both to manufacture and replace, was high-density, and offered fast reads.
*Unlike its predecessor, Flash memory is erasable electronically. (EPROMS needed to be erased with UV light, so if you left it out in the sun, you lost all your data) This allows the device to be erased and reprogrammed fairly quickly

===== Data Retention =====
Data retention refers to the period of time between storing the data, and the first erroneous readout of the data. Typical memory specifications require flash memory to be able to retain data for 10 years.

===== Endurance =====
Endurance refers to the number of write/erase cycles the memory can endure before the technology is worn out, due to stress from reads and erases. Over time, the retention capability of the memory will degrade, and A general industry requirement is 100,000 erase/write cycles before failure.

***NOTE: I'm still trying to clean this up so it looks pretty.

User:Abujaki

2010-10-15T00:18:42Z

Abujaki:

Essay:

===== How does it work? =====
The data is stored as a certain voltage either above a preset x level, or below a preset y level, both determined by the manufacturer. A high voltage is typically read as a 1, and a low voltage is typically a 0. The voltage in question is preserved in a 'Floating gate' transistor, where an additional gate is sammiched between two insulators. This ensures there is no voltage leak (Provides the nonvolitility and prevents damage to the stored data during the read step.)

===== NOR and NAND =====
The two main types of flash memory are NOR and NAND. Both of them consist of a grid of memory Floating Gate transistors.

====== NOR ======
The chips are arranged in a logical grid pattern in paralell, using Word lines and bit lines to access the transistors to read/write to.
Word = Y lines
Byte = X lines.
• Reads faster
• Should be careful not to over-erase the transistors (Depletion mode)
• Fast random read/write
• Additionally, NOR Guarantees 100% good bits, so error-checking and correction doesn't need to be programmed into the system.

====== NAND ======
* 8 or 16 transistors in series, between two select gates.
* The string gate ensures selectivity
* The Ground gate keeps current from passing through the cell while the memory is programming
* Depletion mode is okay, but the
* Physically smaller cell size (85% smaller than NOR) [20]
* Because the bytes are in serial, a word can be written to memory all at once instead of bit-by-bit like in NOR
* Primarily preferred for data storage and removable media
* Offers redundant memory and error-correcting to remove bad bits.
* Comparitively slower read times because the bytes are linked in serial.
* More complex than NOR
* Slightly more costly than NOR

===== Strengths =====
* Cheap
* High-density storage (Lots of data per square inch)
* Long data retention
* Fast read/write times
* Erasable
* Flash memory is nonvolatile. This means even after the power is removed from the device, the memory device will retain the information programmed into it. Typical manufacturer specifications require nonvolatile memory to retain data for at least 10 years before the first errenous readout of data.

===== Weaknesses =====
* Limited read/erases. (See endurance)
* Not Byte-alterable. In order to flip a byte, you would need to erase and reprogram an entire memory block

===== Why use flash? =====
* Flash memory, because of its data retention capabilities coupled with quick read/write cycles is a staple in today's portable device technology.
* NOR Flash memory quickly replaced EPROMs ( Erasable Programmable Read-Only Memory) in development. While both are nonvolatile and erasable, Flash also offers cost-effectiveness, both to manufacture and replace, was high-density, and offered fast reads.
*Unlike its predecessor, Flash memory is erasable electronically. (EPROMS needed to be erased with UV light, so if you left it out in the sun, you lost all your data) This allows the device to be erased and reprogrammed fairly quickly

===== Data Retention =====
Data retention refers to the period of time between storing the data, and the first errenous readout of the data. Typical memory specifications require flash memory to be able to retain data for 10 years.

===== Endurance =====
Endurance refers to the number of write/erase cycles the memory can endure before the technology is worn out, due to stress from reads and erases. Over time, the retention capability of the memory will degrade, and A general industry requirement is 100,000 erase/write cycles before failure.

***NOTE: I'm still trying to clean this up so it looks pretty.

User:Abujaki

2010-10-15T00:14:16Z

Abujaki:

Essay:

===== How does it work? =====
The data is stored as a certain voltage either above a preset x level, or below a preset y level, both determined by the manufacturer. A high voltage is typically read as a 1, and a low voltage is typically a 0. The voltage in question is preserved in a 'Floating gate' transistor, where an additional gate is sammiched between two insulators. This ensures there is no voltage leak (Provides the nonvolitility and prevents damage to the stored data during the read step.)

===== NOR and NAND =====
The two main types of flash memory are NOR and NAND. Both of them consist of a grid of memory Floating Gate transistors.

====== NOR ======
The chips are arranged in a logical grid pattern in paralell, using Word lines and bit lines to access the transistors to read/write to.
Word = Y lines
Byte = X lines.
• Reads faster
• Should be careful not to over-erase the transistors (Depletion mode)
• Fast random read/write
• Additionally, NOR Guarantees 100% good bits, so error-checking and correction doesn't need to be programmed into the system.

====== NAND ======
* 8 or 16 transistors in series, between two select gates.
* The string gate ensures selectivity
* The Ground gate keeps current from passing through the cell while the memory is programming
* Depletion mode is okay, but the
* Physically smaller cell size (85% smaller than NOR) [20]
* Because the bytes are in serial, a word can be written to memory all at once instead of bit-by-bit like in NOR
* Primarily preferred for data storage and removable media
* Offers redundant memory and error-correcting to remove bad bits.
* Comparitively slower read times because the bytes are linked in serial.
* More complex than NOR
* Slightly more costly than NOR

===== Strengths =====
* Cheap
* High-density storage (Lots of data per square inch)
* Long data retention
* Fast read/write times
* Erasable
* Flash memory is nonvolatile. This means even after the power is removed from the device, the memory device will retain the information programmed into it. Typical manufacturer specifications require nonvolatile memory to retain data for at least 10 years before the first errenous readout of data.

===== Weaknesses =====
* Limited read/erases. (See endurance)
* Not Byte-alterable. In order to flip a byte, you would need to erase and reprogram an entire memory block

===== Why use flash? =====
* Flash memory, because of its data retention capabilities coupled with quick read/write cycles is a staple in today's portable device technology.
* NOR Flash memory quickly replaced EPROMs ( Erasable Programmable Read-Only Memory) in development. While both are nonvolatile and erasable, Flash also offers cost-effectiveness, both to manufacture and replace, was high-density, and offered fast reads.

===== Data Retention =====
Data retention refers to the period of time between storing the data, and the first errenous readout of the data. Typical memory specifications require flash memory to be able to retain data for 10 years.

===== Endurance =====
Endurance refers to the number of write/erase cycles the memory can endure before the technology is worn out, due to stress from reads and erases. Over time, the retention capability of the memory will degrade, and A general industry requirement is 100,000 erase/write cycles before failure.

***NOTE: I'm still trying to clean this up so it looks pretty.

Talk:COMP 3000 Essay 1 2010 Question 10

2010-10-15T00:12:25Z

Abujaki:

User:Abujaki

2010-10-15T00:11:53Z

Abujaki:

Essay:

===== How does it work? =====
The data is stored as a certain voltage either above a preset x level, or below a preset y level, both determined by the manufacturer. A high voltage is typically read as a 1, and a low voltage is typically a 0. The voltage in question is preserved in a 'Floating gate' transistor, where an additional gate is sammiched between two insulators. This ensures there is no voltage leak (Provides the nonvolitility and prevents damage to the stored data during the read step.)

===== NOR and NAND =====
The two main types of flash memory are NOR and NAND. Both of them consist of a grid of memory Floating Gate transistors.

=== NOR ===
The chips are arranged in a logical grid pattern in paralell, using Word lines and bit lines to access the transistors to read/write to.
Word = Y lines
Byte = X lines.
• Reads faster
• Should be careful not to over-erase the transistors (Depletion mode)
• Fast random read/write
• Additionally, NOR Guarantees 100% good bits, so error-checking and correction doesn't need to be programmed into the system.

=== NAND ===
* 8 or 16 transistors in series, between two select gates.
* The string gate ensures selectivity
* The Ground gate keeps current from passing through the cell while the memory is programming
* Depletion mode is okay, but the
* Physically smaller cell size (85% smaller than NOR) [20]
* Because the bytes are in serial, a word can be written to memory all at once instead of bit-by-bit like in NOR
* Primarily preferred for data storage and removable media
* Offers redundant memory and error-correcting to remove bad bits.
* Comparitively slower read times because the bytes are linked in serial.
* More complex than NOR
* Slightly more costly than NOR

===== Strengths =====
* Cheap
* High-density storage (Lots of data per square inch)
* Long data retention
* Fast read/write times
* Erasable
* Flash memory is nonvolatile. This means even after the power is removed from the device, the memory device will retain the information programmed into it. Typical manufacturer specifications require nonvolatile memory to retain data for at least 10 years before the first errenous readout of data.

===== Weaknesses =====
* Limited read/erases. (See endurance)
* Not Byte-alterable. In order to flip a byte, you would need to erase and reprogram an entire memory block

===== Why use flash? =====
* Flash memory, because of its data retention capabilities coupled with quick read/write cycles is a staple in today's portable device technology.
* NOR Flash memory quickly replaced EPROMs ( Erasable Programmable Read-Only Memory) in development. While both are nonvolatile and erasable, Flash also offers cost-effectiveness, both to manufacture and replace, was high-density, and offered fast reads.

===== Data Retention =====
Data retention refers to the period of time between storing the data, and the first errenous readout of the data. Typical memory specifications require flash memory to be able to retain data for 10 years.

===== Endurance =====
Endurance refers to the number of write/erase cycles the memory can endure before the technology is worn out, due to stress from reads and erases. Over time, the retention capability of the memory will degrade, and A general industry requirement is 100,000 erase/write cycles before failure.

***NOTE: I'm still trying to clean this up so it looks pretty.

User:Abujaki

2010-10-15T00:10:05Z

Abujaki:

Essay:

===== How does it work? =====
The data is stored as a certain voltage either above a preset x level, or below a preset y level, both determined by the manufacturer. A high voltage is typically read as a 1, and a low voltage is typically a 0. The voltage in question is preserved in a 'Floating gate' transistor, where an additional gate is sammiched between two insulators. This ensures there is no voltage leak (Provides the nonvolitility and prevents damage to the stored data during the read step.)

===== NOR and NAND =====
The two main types of flash memory are NOR and NAND. Both of them consist of a grid of memory Floating Gate transistors.

=== NOR ===
The chips are arranged in a logical grid pattern in paralell, using Word lines and bit lines to access the transistors to read/write to.
Word = Y lines
Byte = X lines.
• Reads faster
• Should be careful not to over-erase the transistors (Depletion mode)
• Fast random read/write
• Additionally, NOR Guarantees 100% good bits, so error-checking and correction doesn't need to be programmed into the system.

=== NAND ===
* 8 or 16 transistors in series, between two select gates.
* The string gate ensures selectivity
* The Ground gate keeps current from passing through the cell while the memory is programming
* Depletion mode is okay, but the
* Physically smaller cell size (85% smaller than NOR) [20]
* Because the bytes are in serial, a word can be written to memory all at once instead of bit-by-bit like in NOR
* Primarily preferred for data storage and removable media
* Offers redundant memory and error-correcting to remove bad bits.
* Comparitively slower read times because the bytes are linked in serial.
* More complex than NOR
* Slightly more costly than NOR

===== Strengths =====
* Cheap
* High-density storage (Lots of data per square inch)
* Long data retention
* Fast read/write times
* Erasable
* Flash memory is nonvolatile. This means even after the power is removed from the device, the memory device will retain the information programmed into it. Typical manufacturer specifications require nonvolatile memory to retain data for at least 10 years before the first errenous readout of data.

===== Weaknesses =====
* Limited read/erases. (See endurance)
* Not Byte-alterable. In order to flip a byte, you would need to erase and reprogram an entire memory block

===== Why use flash? =====
* Flash memory, because of its data retention capabilities coupled with quick read/write cycles is a staple in today's portable device technology.
* NOR Flash memory quickly replaced EPROMs ( Erasable Programmable Read-Only Memory) in development. While both are nonvolatile and erasable, Flash also offers cost-effectiveness, both to manufacture and replace, was high-density, and offered fast reads.

===== Data Retention =====
Data retention refers to the period of time between storing the data, and the first errenous readout of the data. Typical memory specifications require flash memory to be able to retain data for 10 years.

===== Endurance =====
Endurance refers to the number of write/erase cycles the memory can endure before the technology is worn out, due to stress from reads and erases. Over time, the retention capability of the memory will degrade, and A general industry requirement is 100,000 erase/write cycles before failure.

Talk:COMP 3000 Essay 1 2010 Question 10

2010-10-15T00:07:26Z

Abujaki:

Hey all,

I think we should write down our emails here so we can further discuss stuff without having to login here.
('''***Note that discussions over email can't be counted towards your participation grade!***'''--[[User:Soma|Anil]])

Geoff Smith (gsmith0413@gmail.com) - gsmith6

Andrew Bujáki (abujaki [at] Connect or Live.ca)
***I'm usually on MSN(Live) for collaboration at nights, Just make sure to put in a little message about who you are when you're adding me. :)

I used Google Scholar and came to this page http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=812717&tag=1#
Which briefly touches on the issues of Flash memory. Specifically, inability to update in place, and limited write/erase cycles.

Inability to update in place could refer to the way the flash disk is programmed, instead of bit-by-bit, it is programmed block-by-block. A block would have to be erased and completely reprogrammed in order to flip one bit after it's been set.
http://en.wikipedia.org/wiki/Flash_memory#Block_erasure

Limited write/erase: Flash memory typically has a short lifespan if it's being used a lot. Writing and erasing the memory (Changing, updating, etc) Will wear it out. Flash memory has a finite amount of writes, (varying on manufacturer, models, etc), and once they've been used up, you'll get bad sectors, corrupt data, and generally be SOL.
http://en.wikipedia.org/wiki/Flash_memory#Memory_wear

Filesystems would have to be changed to play nicely with these constraints, where it must use blocks efficiently and nicely, and minimize writing/erasing as much as possible.

I found a paper that talks about the performance, capabilities and limitations of NAND flash storage.

Abstract: "This presentation provides an in-depth examination of the
fundamental theoretical performance, capabilities, and
limitations of NAND Flash-based Solid State Storage (SSS). The
tutorial will explore the raw performance capabilities of NAND
Flash, and limitations to performance imposed by mitigation of
reliability issues, interfaces, protocols, and technology types.
Best practices for system integration of SSS will be discussed.
Performance achievements will be reviewed for various
products and applications. "

Link: http://www.flashmemorysummit.com/English/Collaterals/Proceedings/2009/20090812_T1B_Smith.pdf

There's no Starting place like Wikipedia, even if you shouldn't source it.

http://en.wikipedia.org/wiki/Flash_Memory

http://en.wikipedia.org/wiki/LogFS

http://en.wikipedia.org/wiki/Hard_disk

http://en.wikipedia.org/wiki/Wear_leveling

http://en.wikipedia.org/wiki/Hot_spot_%28computer_science%29

http://en.wikipedia.org/wiki/Solid-state_drive

Hey Guys,

We really don't have much time to get this done. Lets meet tomorrow after class and get our bearings to do this properly.

Fedor

A few of us have Networking immediately after class. I know personally I won't be able to make anything set on Tuesday.
Additionally, he spoke briefly about hotspots on the disk for our question last week, where places on the disk would be written to far more often than others.
As well, for bibliographical citing, http://bibme.org is a wonderful resource for the popular formats (I.e. MLA). If it should come down to that.
~Andrew

===links===

Start Posting some stuff to source from:

http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=1199079&tag=1
--"Introduction to flash memory"

http://portal.acm.org/citation.cfm?id=1244248
--"Wear Leveling" (it's about a proposed way of doing it, but explains a whole bunch of other things to do that)

http://portal.acm.org/citation.cfm?id=1731355
--"Online maintenance of very large random samples on flash storage" (ie dealing with the constraints of Flash Storage in a system that might actually be written to 100000 times)

http://vlsi.kaist.ac.kr/paper_list/2006_TC_CFFS.pdf
--"An Efficient NAND Flash File System for Flash Memory Storage" discuses shortcomings of using hard disk based file systems and current flash based file systems

http://maltiel-consulting.com/NAND_vs_NOR_Flash_Memory_Technology_Overview_Read_Write_Erase_speed_for_SLC_MLC_semiconductor_consulting_expert.pdf
--"NAND vs NOR Flash Memory" (note: i didn't get this off of Google scholar but it seems to be written by someone from Toshiba. is that ok?)

Hi everybody,

So here are the latest news. Geoff, Andrew and myself had a meeting after class today and came up with a plan for writing this thing.

We decided to have 3 parts:

1. What flash storage is, why its good but also why it must have the problems that it does (the assumption is that it must have them, why would it otherwise?)
[don't know much about this just now... basics include that there is NOR (reads slightly faster)and NAND (holds more, writes faster, erases much faster, lasts about ten times longer) flash with NAND being especially popular for storage (what's NOR good for?). Here, we'd ideally want to talk about why flash was invented (supposed as an alternative to slow ROM), why it was suitable for that, and how it works on a technical level. Then, we'd want to mention why this technical functionality was innovative and useful but also why it came with two serious set-backs: having a limited-number of re-write cycles and needing to erase a block at a time.]

Either way, Flash storage affords far faster fetch times than the traditional platter-based HDD, and stability of information in a sense. Where the data is not actually stored, but reprogrammed, in a sense, the data is more secure and is less likely to be erased easily. On that note, in order to flip a single bit, that entire block will need to be erased, then reprogrammed. In an 'old' HDD, let's say, When the HDD fails at the end of its life cycle, your data is gone. (unless you're willing to shell out $200/hr to have it recovered, yes I've seen companies in Ottawa that do this.) In a flash HDD, when it reaches the end of its life, it merely becomes read-only. Bugger for Databases, but useful for technical notes and archives, let's say.
With today's modern gaming computers, Flash memory can be good on quick load times, however with limited read-writes, it could afford better use to things that are not updated as frequently. I.e... Well I don't have a better example than a webserver hosting a company's CSS and scripts.
~Source: Years in the 'biz

Flash memory started out as a replacement for EPROMs. At the time EPROMs needed a UV photoemission to be erased while flash memory could be erased electronically. The first flash memory product came out in 1988 but it did not take off until the late 1990’s because it could not be reliable produced. NOR and NAND memory is named after the arrangement of the cells in the memory array. NOR based flash memory benefits from having very fast burst read times but slower write times. Due to the structure of NOR memory programs stored in NOR based memory can be executed without being loaded into RAM first. NAND flash memory has a very large storage capacity and can read and write large files relatively fast. NAND is more suited for storage while NOR memory is better suited for direct program execution such as in CMOS chips.
source: http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=1199079&tag=1 , http://maltiel-consulting.com/NAND_vs_NOR_Flash_Memory_Technology_Overview_Read_Write_Erase_speed_for_SLC_MLC_semiconductor_consulting_expert.pdf

2. How a traditional disk-based file-system works and why the limitations of flash storage make the two a poor match
[the obvious answer seems to be that traditional file-systems could just write to whatever memory was available but if they did this with a flash file-systems, certain chunks of memory would become unusable before others and the memory would be more difficult to work with. Also, disk-based file systems need to deal with seeking times which means that they want to organize their data in such a way as to reduce those (by putting related things together?) - with Flash, this isn't really a problem and thus one constraint the less to be concerned with.]

3. How a log based file-system works and why this method of operation is so well suited to working with flash memory especially in light of the latter's inherent limitations
[...]

At this time, the plan is that Geoff will work on #3 today, Andrew will work on #1 tomorrow and I will work on #2 tomorrow. The three of us will make an effort to consult some somewhat more painfully technical literature in order to gain insight into our respective queries. Whatever insight we find will be posted here.

Then, we will meet again on Thursday after class to decide how to actually write the essay.

PS, if there is anybody in the group besides the three of us - let us know so you can find a way to contribute to this... as at least two of us are competent essayists, painfully technical research would on one or more of the above topics would be a great way to contribute... especially if you could post it here prior to one of us going over the same thing.

Fedor

-- I'm not that great (but absolutely horrid) at essays and I'm alright at research, but if nothing else I have Thursday off and nothing (else) that needs doing by Friday so I can probably spend a bunch of time working on it just before it's due. -- ''Nick L''

-- Hay sorry I was unable to attend the meeting after class today. I am not too good at writing essays as well but I am pretty good at summarizing and researching. I am not too sure at what you would like me to do. Right now I'll assume you need me to research/summarizing articles for the 3 topics above. If you need me to do anything else post it here. I'll be checking the discussion regularly until this due. once again sorry for missing the meeting-- Paul Cox.

-- Hey i'm also supposed to be in on this. Sorry i couldn't contribute sooner because i was playing catchup in my other classes. Let me know what i can do and i'll be on it asap. - kirill (k.kashigin@gmail.com)
update: i'm gonna be helping Fedor with #2

PS, this article http://docs.google.com/viewer?a=v&q=cache:E7-H_pv_18wJ:citeseerx.ist.psu.edu/viewdoc/download%3Fdoi%3D10.1.1.92.2279%26rep%3Drep1%26type%3Dpdf+flash+memory+and+disk-based+file+systems&hl=en&gl=ca&pid=bl&srcid=ADGEESgspy-jqIdLOpaLYlPPoM56kjLPwXcL3_eMbTTBRkI7PG0jQKl9vIieTAYHubPu0EdQ0V4ccaf_p0S_SnqKMirSIM0Qoq5E0NpLd0M7LAGaE51wkD0F55cRSkX8dnTqx_9Yx2E7&sig=AHIEtbS-yfGI9Y48DJ0WyEEhmsXInelRGw looks really useful for part 3.

---same article as above but shorter link: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.160.5142

PPS, and this article looks really great for understanding how log based file systems work: http://delivery.acm.org/10.1145/150000/146943/p26-rosenblum.pdf?key1=146943&key2=3656986821&coll=GUIDE&dl=GUIDE&CFID=108397378&CFTOKEN=72657973

Hey Luc (TA) here, Anandtech ran a series of articles on solid state drives that you guys might find useful. It mostly looked at hardware aspects but it gives some interesting insights on how to modify file systems to better support flash memory.

http://www.anandtech.com/cpuchipsets/intel/showdoc.aspx?i=3403

http://www.anandtech.com/storage/showdoc.aspx?i=3531&p=1

http://anandtech.com/storage/showdoc.aspx?i=3631

--[[User:3maisons|3maisons]] 19:44, 12 October 2010 (UTC)

Hey Paul&Kirill,

If one of you guys could help me out with #2, that would be really great. I was going to work on that tomorrow, but I also have another large assignment to deal with and not having to do this research would greatly ease my life. Moreover, I do intend to work on writing&polishing the essay on Thursday as I have a lot of experience with that and it far more than research. Let me know if either one of you can help me with this.

The other person could probably read over what Luc posted for us and see if it fits into our framework. Just be sure to state who is going to do what.

Nick,

Honestly, we really hope to have the research done by Thursday. If that is the only day that you are free and you're not a writer, I'm honestly not sure what you could do. Perhaps someone else can think of something.

- Fedor

I'm gonna have something for #2 up tonight. -kirill

So I found this article on Reddit, posted from Linux Weekly News on pretty much exactly what we are looking at. It's entitled "Solid-state storage devices and the block layer"

http://lwn.net/SubscriberLink/408428/68fa8465da45967a/ --[[User:Gsmith6|Gsmith6]] 20:36, 13 October 2010 (UTC)

I wasn't exactly sure how much information i was supposed to present but here's what i got for #2:

Most conventional file systems are designed to me implemented on hard disk drives. This fact does not mean they cannot be implemented on a solid state drive (file storage that uses flash memory instead of magnetic discs). It would however, in many ways, defeat the purpose of using flash memory. The most consuming process for an HDD is seeking data by relocating the read-head and spinning the magnetic disk. A traditional file system optimizes the way it stores data by placing related blocks close-by on the disk to minimize mechanical movement within the HDD. One of the great advantages of flash memory, which accounts for its fast read speed, is that there is no need to seek data physically so there is no need to waste resources laying out the data in close proximity.
A traditional HDD file system will also attempt to defragment itself, moving blocks of data around for closer proximity on the magnetic disk. This process, although beneficial for HDD's, is harmful and inefficient for flash based storage. A flash optimal file system needs to reduce the amount of erase operations, since flash memory only has a limited amount of erase cycles as well as having very slow erase speeds.
When an HDD rewrites data to a physical location there is no need for it to erase the previously occupying data first, so a traditional disk based file system doesn't worry about erasing data from unused memory blocks. In contrast flash memory needs to first erase the data block before it can modify any of it contents. Since the erase procedure is extremely slow, its not practical to overwrite old data every time. It is also decremental to the life span of flash memory.
To maximize the potential of flash based memory the file system would have to write new data to empty memory blocks. This method would also call for some sort of garbage collection to erase unused blocks when the system is idle, which does not get implemented in conventional file systems since it is not needed.

--kirill

So Fedor and I were talking in the labs, and we came to the conclusion that we have been focusing on just the translation from a regular file system to a flash drive. We were under the impression that this was in fact the "Flash Optimized System", but pulling up some more articles, I'm finding that this is not necessarily the case.

This paper here http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.128.6156&rep=rep1&type=pdf.
shows an example from Axis Communications where they developed a file system specifically designed to be used on flash drives.

Now I haven't completely read it, so it might just be an optimized translational system, but its at least a start.

At our meeting today, we've decided that it would be best if people could post a rough summary of their notes in the appropriate sections, and I will rewrite them into an essay, which Fedor will go through later tonight to edit and add some more information.

Paul: I missed your comment that you weren't that great at writing, and good at research. If you want some articles behind the pay-walls, I've saved a bunch of them and emailed them to myself. Just email me (at the address at the top of the page) and I'll be more than happy to send some your way.

PS. some more references

Design tradeoffs for SSD performance http://portal.acm.org/citation.cfm?id=1404014.1404019
A log buffer-based flash translation layer using fully-associative sector translation http://delivery.acm.org/10.1145/1280000/1275990/a18-lee.pdf?key1=1275990&key2=0709607821&coll=GUIDE&dl=GUIDE&CFID=105787273&CFTOKEN=74601780

--[[User:Gsmith6|Gsmith6]] 15:03, 14 October 2010 (UTC)

I don't have any notes on this computer. >: I will be adding more to my section later on tonight. Sorry. ~Andrew

Hello dudes,

Just a quick note, try to include citations in your paragraphs - each time that you make a claim which came from evidence, put a little number [X, pp. page-number (if applicable)] into your text. Then, put the same [X] at the bottom of the page with the bibliographical information about the source. The prof hasn't yet gotten back to me about his preferred citation format, so just stick with this one for now:

Authors. ''Title''. Web-page. Date of article. Web (the word). Date you accessed it.

Here's an example:

[1] Kawaguchi, Nishioka, Tamoda. ''A Flash Memory Based File System''.
http://docs.google.com/viewer?a=v&q=cache:E7-H_pv_18wJ:citeseerx.ist.psu.edu/viewdoc/download%3Fdoi%3D10.1.1.92.2279%26rep%3Drep1%26type%3Dpdf+flash+memory+and+disk-based+file+systems&hl=en&gl=ca&pid=bl&srcid=ADGEESgspy-jqIdLOpaLYlPPoM56kjLPwXcL3_eMbTTBRkI7PG0jQKl9vIieTAYHubPu0EdQ0V4ccaf_p0S_SnqKMirSIM0Qoq5E0NpLd0M7LAGaE51wkD0F55cRSkX8dnTqx_9Yx2E7&sig=AHIEtbS-yfGI9Y48DJ0WyEEhmsXInelRGw . 1995. Web. Oct. 14, 2010.

Fedor

PS, its a good idea to check this fairly frequently between now and tomorrow morning - you never know when something will come up.

Phew... for a while there I was starting to think that I had nothing about the actual "Log-Based System", but it turns out that the "Transitional Layer" is the same thing. It looks like some articles are calling it the Log system, while others are calling it the transitional layer. Pretty sure I'm going to have an experts knowledge about flash drives after reading all these articles :P
--[[User:Gsmith6|Gsmith6]] 18:13, 14 October 2010 (UTC)

Hay Geoff this is what i got so far after reading a couple of the pdfs. the double tabed points are just my annotation on how they relate to the question.

Ware leveling: p1126-chang.pdf

* Uneven wearing of flash memory due to storing data close together
* Garbage collection prefers that no blocks have pages that have data that is constantly becoming invalid
* data that remains the same for longs periods of time should be moved from block that have not be written to much and moved to blocks that haven been erased frequently.

Log file structure: 926-rosenblum.pdf

* LFS based on assumption that frequently read files will be stored in cash and that the hard disk traffic will be dominated by writes
* Writes all new info to disk in a sequential structure called a log
* Data is stored permanently in these logs no other data is stored on the hard drive
* Converts many small random synchronous writes to a large asynchronous sequential write
** Good for flash because it cuts down on writing (prolongs drive life)
** It also good because it writes to a bigger section then a page. This means it can fill a block at a time so it doesn’t fill up other blocks with random writes that would later need to be cleaned. Cuts down on cleaning.
* Inode is stored in the log on the disk while an inode map is maintained in memory which points to the inode in the hard disk. as
** This is good for flash drives because reading does not hurt the drives life and it is fast.
** This means the map will not have to be updated on the disk as frequently cutting down on the writes.
* Log systems weakness is that it is susceptible to becoming fragmented due to the larger writes.
** Since flash drives do not require fragmentation this is fine. Also since flash drives have very fast random access the system does not become bogged down when the logs are fragmented
* Log system implements a cleaning system that scans a segment in and sees if there is live data in it. If there is a certain percentage of invalid data which goes according to the cleaning policy it will be cleaned. All the live data will be copied out and the segment will be erased.
** This is a garbage collector but its built into the file system.
* Segments contain a number of blocks. Segments can contain logs or parts of logs.

I'm still sifting though the other pdfs you sent me. Would you like me to post more info or should i format this into a paragraph or 2?

--Paul

I'm sorting through my notes and putting them into a digital format. Difficult because It's hard to remember what I copied directly out of the notes for my own reference, so I'm trying to de-plagarize. I'll upload what I have to the section by 20:30, but expect more updates. ~Andrew

Hey Paul,

Thanks for helping out with the research
I'm thinking that we probably have enough information (at least for the log-based system), so maybe if you could "try" and putting them into paragraphs. I'm kind of in the middle of typing up the essay, and I'm uploading new information every 10-20 minutes or so. Even if you could get something into paragraph form, I can go through and edit, rearrange, and add stuff as I get there. --[[User:Gsmith6|Gsmith6]] 23:51, 14 October 2010 (UTC)

I'm just going to dump my entire wiki so far into an attached file, because everything's being updated so quickly.
[[User:Abujaki]] ~Andrew

User:Abujaki

2010-10-15T00:06:22Z

Abujaki: Created page with "Essay: ===== How does it work? ===== The data is stored as a certain voltage either above a preset x level, or below a preset y level, both determined by the manufacturer. A hi…"

Essay:

===== How does it work? =====
The data is stored as a certain voltage either above a preset x level, or below a preset y level, both determined by the manufacturer. A high voltage is typically read as a 1, and a low voltage is typically a 0. The voltage in question is preserved in a 'Floating gate' transistor, where an additional gate is sammiched between two insulators. This ensures there is no voltage leak (Provides the and prevents damage to the stored data during the read step.

===== NOR and NAND =====
The two main types of flash memory are NOR and NAND. Both of them consist of a grid of memory Floating Gate transistors.

=== NOR ===
The chips are arranged in a logical grid pattern in paralell, using Word lines and bit lines to access the transistors to read/write to.
Word = Y lines
Byte = X lines.
• Reads faster
• Should be careful not to over-erase the transistors (Depletion mode)
• Fast random read/write
• Additionally, NOR Guarantees 100% good bits, so error-checking and correction doesn't need to be programmed into the system.

=== NAND ===
* 8 or 16 transistors in series, between two select gates.
* The string gate ensures selectivity
* The Ground gate keeps current from passing through the cell while the memory is programming
* Depletion mode is okay, but the
* Physically smaller cell size (85% smaller than NOR) [20]
* Because the bytes are in serial, a word can be written to memory all at once instead of bit-by-bit like in NOR
* Primarily preferred for data storage and removable media
* Offers redundant memory and error-correcting to remove bad bits.
* Comparitively slower read times because the bytes are linked in serial.
* More complex than NOR
* Slightly more costly than NOR

===== Strengths =====
* Cheap
* High-density storage (Lots of data per square inch)
* Long data retention
* Fast read/write times
* Erasable
* Flash memory is nonvolatile. This means even after the power is removed from the device, the memory device will retain the information programmed into it. Typical manufacturer specifications require nonvolatile memory to retain data for at least 10 years before the first errenous readout of data.

===== Weaknesses =====
* Limited read/erases. (See endurance)
* Not Byte-alterable. In order to flip a byte, you would need to erase and reprogram an entire memory block

===== Why use flash? =====
* Flash memory, because of its data retention capabilities coupled with quick read/write cycles is a staple in today's portable device technology.
* NOR Flash memory quickly replaced EPROMs ( Erasable Programmable Read-Only Memory) in development. While both are nonvolatile and erasable, Flash also offers cost-effectiveness, both to manufacture and replace, was high-density, and offered fast reads.

===== Data Retention =====
Data retention refers to the period of time between storing the data, and the first errenous readout of the data. Typical memory specifications require flash memory to be able to retain data for 10 years.

===== Endurance =====
Endurance refers to the number of write/erase cycles the memory can endure before the technology is worn out, due to stress from reads and erases. Over time, the retention capability of the memory will degrade, and A general industry requirement is 100,000 erase/write cycles before failure.

Talk:COMP 3000 Essay 1 2010 Question 10

2010-10-15T00:03:56Z

Abujaki:

Talk:COMP 3000 Essay 1 2010 Question 10

2010-10-14T23:39:17Z

Abujaki:

COMP 3000 Essay 1 2010 Question 10

2010-10-14T23:36:09Z

Abujaki: /* References */

=Question=

How do the constraints of flash storage affect the design of flash-optimized file systems? Explain by contrasting with hard disk-based file systems.

=Answer=
First introduced in the late 80s, Flash-memory is a light, energy-independent, compact, shock-resistent and efficiently readable type of storage. Because of the particular limitations of this kind of memory, flash file systems require a fundamentally different system architecture than disk-based file-systems: these systems need to be designed in light of flash-memory’s limited number of erase-cycles and its need to conduct erasures one entire block at a time. These constraints are a direct result of the same design that gives flash its advantages with regard to [ TO WHAT?] as both are due to [TO WHAT?] . Thus, a typical disk-based file-system is not suitable for working with flash memory as it erases far too frequently and indiscriminently while being simultaneously optimized for other constraints that do not affect flash memory. This means that a different solution is necessary and that solution is the log-based file-system which is far better suited to working with flash memory because it optimizes erasures by [WHAT?].

==Flash Memory==
Flash memory is non-volatile(meaning digital storage that does not require power to retain its memory) storage space that has become more popular recently due to its fast fetch times. There are two basic forms of the flash storage system, NOR and NAND. Each type has its advantages and disadvantages. NOR has the fastest read times, but is much slower at writing. NAND on the other hand has much more capacity, faster write times, is less expensive, and has a much longer life expectancy.[2]

More and more people use flash memory, ranging from a few hundred megabyte USB key, to a few terrabyte internal solid-state drive(SSD). Two main reasons for this movement are because of flash's extremely fast read times, and its falling price. A typical flash drive has read speeds of up to 16 times faster than a hard disk drive (HDD).<ref>http://www.micron.com/products/solid_state_storage/client_ssd.html</ref>

===Constraints===
''Flash memory has two major constraints
# Limited number of writes/erasures
# Bytes cannot be individually flipped
''

==Traditionally Optimized File Systems==

With the previous section in mind, it should come as no surprise that a conventional hard disk drive (HDD) file-system is not optimized to work with flash memory. The reason for this is that conventional hard-disks have different constraints from those of flash memory - their primary problem is to reduce seeking time, while the primary problem when working with flash memory is to erase in a minimal and balanced way.

The most consuming process for an HDD is seeking data by relocating the read-head and spinning the magnetic disk. A traditional file system optimizes the way it stores data by placing related blocks close-by on the disk in order to minimize mechanical movement within the HDD. One of the great advantages of flash memory, which accounts for its fast read speed, is that there is no need to seek data physically so there is no need to waste resources laying out the data in close proximity. This is also why defragmentaion, a procedure used by HDDs to put files into more convenient configurations and thus minimize seeking times, loses its purpose in a flash memory context. Indeed, the unnecessary erasures that it entails are both inefficient and harmful for a flash memory unit.

This comes direclty out of flash memory's aforementioned constraints: the slow block-sized erasures and the limited number of erase-cycles. Because of these, a flash optimal file system needs to minimize its erase operations and also to spread out its erasures in such a way as to avoid the formation of hot-spots: sections of memory which have undergone a disproportionately high number of erasures and are thus in danger of burning out. To minimize these, a system using flash memory would have to write new data to empty memory blocks. This method would also call for some sort of garbage collection to conduct necessary erasure operations while the system is idle. It makes better sense to do these at this time because of the slow nature of erasures in the flash memory context. Of course, there is no such feature in a traditional HDD file-system.

==Flash Optimized File Systems==
''Flash Optimized files systems do to optimize HDD read/write/etc''

=Questions=

=References=

I'm going to start making up some proper citations for the websites we have. the order they're going in probably won't line up with the actual essay so I put the number for the link I'm actually citing next to each link, renumber as appropriate:

'''also, add in the right page number'''

[1] [http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=812717&tag=1#]

[2] [http://www.flashmemorysummit.com/English/Collaterals/Proceedings/2009/20090812_T1B_Smith.pdf]

[3][http://portal.acm.org/citation.cfm?id=1244248]

[4] [http://portal.acm.org/citation.cfm?id=1731355]

[5] [http://vlsi.kaist.ac.kr/paper_list/2006_TC_CFFS.pdf]

[6] [http://maltiel-consulting.com/NAND_vs_NOR_Flash_Memory_Technology_Overview_Read_Write_Erase_speed_for_SLC_MLC_semiconductor_consulting_expert.pdf]

[7] [http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=1199079&tag=1]

[8] [http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.160.5142]

[9] [http://delivery.acm.org/10.1145/150000/146943/p26-rosenblum.pdf?key1=146943&key2=3656986821&coll=GUIDE&dl=GUIDE&CFID=108397378&CFTOKEN=72657973]

[10] [http://www.anandtech.com/show/2614]

[11] [http://www.anandtech.com/storage/showdoc.aspx?i=3531&p=1]

[12] [http://anandtech.com/storage/showdoc.aspx?i=3631]

[13] [http://lwn.net/SubscriberLink/408428/68fa8465da45967a/]

[14] [http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.128.6156&rep=rep1&type=pdf]

[15] [http://portal.acm.org/citation.cfm?id=1404014.1404019]

[16] [http://portal.acm.org/citation.cfm?id=1275990]

[17] [http://www.micron.com/products/solid_state_storage/client_ssd.html]

==actual references start here==

[1] Kim, Han-joon; Lee, Sang-goo. ''A New Flash Memory Management for Flash Storage System''. ''IEEExplore''. Dept. of Comput. Sci., Seoul Nat. Univ., 06 Aug 2002. <http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=812717&tag=1#>

[2] Smith, Lance. ''NAND Flash Solid State Storage Performance and Capability''. ''Flash Memory Summit''. SNIA Education Committee, 18 Aug 2009. <http://www.flashmemorysummit.com/English/Collaterals/Proceedings/2009/20090812_T1B_Smith.pdf>

[3] Chang, LiPin. ''On Efficient Wear Leveling for Large-Scale Flash-Memory Storage Systems''. ''Association for Computing Machinery (ACM)''. Dept. of Comput. Sci.,Nat. ChiaoTung Univ., 15 Mar 2007. <http://portal.acm.org/citation.cfm?id=1244248>

[4] Nath, Suman; Gibbons, Phillip. ''Online maintenance of very large random samples on flash storage''. ''Association for Computing Machinery (ACM)''. The VLDB Journal, 27 Jul 2007. <http://portal.acm.org/citation.cfm?id=1731355>

[5] Lim, Seung-Ho; Park; Kyu-Ho. ''An Efficient NAND Flash File System for Flash Memory Storage''. ''CORE Laboratory''. IEEE Transactions On Computers, Jul 2006. <http://vlsi.kaist.ac.kr/paper_list/2006_TC_CFFS.pdf>

[6] ''NAND vs. NOR Flash Memory Technology Overview''. ''RMG and Associates''. Toshiba America, accessed 14 Oct 2010. <http://maltiel-consulting.com/NAND_vs_NOR_Flash_Memory_Technology_Overview_Read_Write_Erase_speed_for_SLC_MLC_semiconductor_consulting_expert.pdf>

[7] Bez, Roberto; Camerlenghi, Emilio; Modelli, Alberto; Visconti, Angelo. ''Introduction to Flash Memory''. ''IEEExplore''. STMicroelectronics, 21 May 2003. <http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=1199079&tag=1>

[8] Kawaguchi, Atsuo; Nishioka, Shingo; Motoda Hiroshi. ''A Flash-Memory Based File System''. ''CiteSeerX'' Advanced Research laboratory, Hitachi, Ltd., 1995. <http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.160.5142>

[9] Rosenblum, Mendel; Ouserhout, John. ''The Design and Implementation of a Log-structured File System''. ''Association for Computing Machinery (ACM)''. University of California at Berkeley, Feb 1992. <http://portal.acm.org/citation.cfm?id=146943&coll=GUIDE&dl=GUIDE&CFID=108397378&CFTOKEN=72657973&ret=1#Fulltext>

[10] Shimpi, Anand. ''Intel X25-M SSD: Intel Delivers One of the World's Fastest Drives''. ''AnAndTech''. AnAndTech, 8 Sep 2008. <http://www.anandtech.com/show/2614>

[11] Shimpi, Anand. ''The SSD Relapse: Understanding and Choosing the Best SSD''. ''AnAndTech''. AnAndTech, 30 Aug 2009. <http://www.anandtech.com/show/2829>

[12] Shimpi, Anand. ''The SSD Anthology: Understanding SSDs and New Drives from OCZ''. ''AnAndTech''. AnAndTech, 18 Mar 2009. <http://www.anandtech.com/show/2738>

[13] Corbet, Jonathan. ''Solid-State Storage Devices and the Block Layer''. ''Linux Weekly News''. Linux Weekly News, 4 Oct 2010. <http://lwn.net/Articles/408428/>

[14] Woodhouse, David. ''JFFS : The Journalling Flash File System''. ''CiteSeerX''. Red Hat, Inc, accessed 14 Oct 2010. <http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.128.6156&rep=rep1&type=pdf>

[15] Agrawal, Nitin; Prabhakaran, Vijayan; Wobber, Ted; Davis, John; Manasse, Mark. Panigrahy, Rina. ''Design Tradeoffs for SSD Performance''. ''Association for Computing Machinery (ACM)'', USENIX 2008 Annual Technical Conference, 2008. <http://portal.acm.org/citation.cfm?id=1404014.1404019>

[16] Lee, Sang-Won, et al. ''A Log Buffer-Based Flash Translation Layer Using Fully-Associative Sector Translation''. ''Association for Computing Machinery (ACM)''. ACM Transactions on Embedded Computing Systems (TECS), Jul 2007. <http://portal.acm.org/citation.cfm?id=1275990>

[17] Micron Technology Inc, ''Reach New Heights in Computing Performance''. <http://www.micron.com/products/solid_state_storage/client_ssd.html> (may need reworking)

[18] Flash Memories. 1 ed. New York: Springer, 1999. Print.

[19] Nonvolatile Memory Technologies with Emphasis on Flash: A Comprehensive Guide to Understanding and Using Flash Memory Devices (IEEE Press Series on Microelectronic Systems). New York: Wiley-Ieee Press, 2008. Print.

[20] Nonvolatile Semiconductor Memory Technology: A Comprehensive Guide to Understanding and Using NVSM Devices (IEEE Press Series on Microelectronic Systems). New York: Wiley-Ieee Press, 1997. Print.

=External links=

Relivant Wikipedia articles: [http://en.wikipedia.org/wiki/Flash_Memory Flash Memory], [http://en.wikipedia.org/wiki/LogFS, LogFS], [http://en.wikipedia.org/wiki/Hard_disk Hard Disk Drives], [http://en.wikipedia.org/wiki/Wear_leveling Wear Leveling], [http://en.wikipedia.org/wiki/Hot_spot_%28computer_science%29 Hot Spots], [http://en.wikipedia.org/wiki/Solid-state_drive Sold State Drive].

=old=

Hey guys,

This is what I've got so far... mostly based on wikipedia:

Flash memory has two limitations: it can only be erased in blocks and and it wears out after a certain number of erase cycles. Furthermore, a particular kind of Flash memory (NAND) is not able to provide random access.
As a result of these Flash based file-systems cannot be handled in the same way as disk-based file systems. Here are a few of the key differences:

- Because memory must be erased in blocks, its erasure tends to take up time. Consequently, it is necessary to time the erasures in a way so as not to interfere with the efficiency of the system’s other operations. This is is not a real concern with disk-based file-systems.
- A disk file-system needs to minimize the seeking time, but Flash file-system does not concern itself with this as it doesn’t have a disk.
- A flash system tries to distribute memory in such a way so as not to make a particular block of memory subject to a disproportionally large number of erasures. The purpose of this is to keep the block from wearing out prematurely. The result of it is that memory needs to be distributed differently than in a disk based file-system.
Log-sturctured file systems are thus best suited to dealing with flash memory (they apparently do all of the above things).

For the essay form, I'm thinking of doing a section about traditional hard-disk systems, another about flash-memory and a third about flash systems. At this point, I am imagining the thesis as something like, "Flash systems require a fundamentally different system architecture than disk-based systems due to their need to adapt to the constraints inherent in flash memory: specifically, due to that memory's limited life-span and block-based erasures." The argument would then talk about how these two differences directly lead to a new FS approach.

That's how I see it at the moment. Honestly, I don't like doing research about this kind of stuff, so my data isn't very deep. That said, if you guys could find more info and summarize it, I'm pretty sure that I could synthesize it all into a coherent essay.

Fedor

COMP 3000 Essay 1 2010 Question 10

2010-10-14T23:35:31Z

Abujaki: /* actual references start here */

=Question=

How do the constraints of flash storage affect the design of flash-optimized file systems? Explain by contrasting with hard disk-based file systems.

=Answer=
First introduced in the late 80s, Flash-memory is a light, energy-independent, compact, shock-resistent and efficiently readable type of storage. Because of the particular limitations of this kind of memory, flash file systems require a fundamentally different system architecture than disk-based file-systems: these systems need to be designed in light of flash-memory’s limited number of erase-cycles and its need to conduct erasures one entire block at a time. These constraints are a direct result of the same design that gives flash its advantages with regard to [ TO WHAT?] as both are due to [TO WHAT?] . Thus, a typical disk-based file-system is not suitable for working with flash memory as it erases far too frequently and indiscriminently while being simultaneously optimized for other constraints that do not affect flash memory. This means that a different solution is necessary and that solution is the log-based file-system which is far better suited to working with flash memory because it optimizes erasures by [WHAT?].

==Flash Memory==
Flash memory is non-volatile(meaning digital storage that does not require power to retain its memory) storage space that has become more popular recently due to its fast fetch times. There are two basic forms of the flash storage system, NOR and NAND. Each type has its advantages and disadvantages. NOR has the fastest read times, but is much slower at writing. NAND on the other hand has much more capacity, faster write times, is less expensive, and has a much longer life expectancy.[2]

More and more people use flash memory, ranging from a few hundred megabyte USB key, to a few terrabyte internal solid-state drive(SSD). Two main reasons for this movement are because of flash's extremely fast read times, and its falling price. A typical flash drive has read speeds of up to 16 times faster than a hard disk drive (HDD).<ref>http://www.micron.com/products/solid_state_storage/client_ssd.html</ref>

===Constraints===
''Flash memory has two major constraints
# Limited number of writes/erasures
# Bytes cannot be individually flipped
''

==Traditionally Optimized File Systems==

With the previous section in mind, it should come as no surprise that a conventional hard disk drive (HDD) file-system is not optimized to work with flash memory. The reason for this is that conventional hard-disks have different constraints from those of flash memory - their primary problem is to reduce seeking time, while the primary problem when working with flash memory is to erase in a minimal and balanced way.

The most consuming process for an HDD is seeking data by relocating the read-head and spinning the magnetic disk. A traditional file system optimizes the way it stores data by placing related blocks close-by on the disk in order to minimize mechanical movement within the HDD. One of the great advantages of flash memory, which accounts for its fast read speed, is that there is no need to seek data physically so there is no need to waste resources laying out the data in close proximity. This is also why defragmentaion, a procedure used by HDDs to put files into more convenient configurations and thus minimize seeking times, loses its purpose in a flash memory context. Indeed, the unnecessary erasures that it entails are both inefficient and harmful for a flash memory unit.

This comes direclty out of flash memory's aforementioned constraints: the slow block-sized erasures and the limited number of erase-cycles. Because of these, a flash optimal file system needs to minimize its erase operations and also to spread out its erasures in such a way as to avoid the formation of hot-spots: sections of memory which have undergone a disproportionately high number of erasures and are thus in danger of burning out. To minimize these, a system using flash memory would have to write new data to empty memory blocks. This method would also call for some sort of garbage collection to conduct necessary erasure operations while the system is idle. It makes better sense to do these at this time because of the slow nature of erasures in the flash memory context. Of course, there is no such feature in a traditional HDD file-system.

==Flash Optimized File Systems==
''Flash Optimized files systems do to optimize HDD read/write/etc''

=Questions=

=References=

I'm going to start making up some proper citations for the websites we have. the order they're going in probably won't line up with the actual essay so I put the number for the link I'm actually citing next to each link, renumber as appropriate:

'''also, add in the right page number'''

[1] [http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=812717&tag=1#]

[2] [http://www.flashmemorysummit.com/English/Collaterals/Proceedings/2009/20090812_T1B_Smith.pdf]

[3][http://portal.acm.org/citation.cfm?id=1244248]

[4] [http://portal.acm.org/citation.cfm?id=1731355]

[5] [http://vlsi.kaist.ac.kr/paper_list/2006_TC_CFFS.pdf]

[6] [http://maltiel-consulting.com/NAND_vs_NOR_Flash_Memory_Technology_Overview_Read_Write_Erase_speed_for_SLC_MLC_semiconductor_consulting_expert.pdf]

[7] [http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=1199079&tag=1]

[8] [http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.160.5142]

[9] [http://delivery.acm.org/10.1145/150000/146943/p26-rosenblum.pdf?key1=146943&key2=3656986821&coll=GUIDE&dl=GUIDE&CFID=108397378&CFTOKEN=72657973]

[10] [http://www.anandtech.com/show/2614]

[11] [http://www.anandtech.com/storage/showdoc.aspx?i=3531&p=1]

[12] [http://anandtech.com/storage/showdoc.aspx?i=3631]

[13] [http://lwn.net/SubscriberLink/408428/68fa8465da45967a/]

[14] [http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.128.6156&rep=rep1&type=pdf]

[15] [http://portal.acm.org/citation.cfm?id=1404014.1404019]

[16] [http://portal.acm.org/citation.cfm?id=1275990]

[http://www.micron.com/products/solid_state_storage/client_ssd.html]

==actual references start here==

[1] Kim, Han-joon; Lee, Sang-goo. ''A New Flash Memory Management for Flash Storage System''. ''IEEExplore''. Dept. of Comput. Sci., Seoul Nat. Univ., 06 Aug 2002. <http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=812717&tag=1#>

[2] Smith, Lance. ''NAND Flash Solid State Storage Performance and Capability''. ''Flash Memory Summit''. SNIA Education Committee, 18 Aug 2009. <http://www.flashmemorysummit.com/English/Collaterals/Proceedings/2009/20090812_T1B_Smith.pdf>

[3] Chang, LiPin. ''On Efficient Wear Leveling for Large-Scale Flash-Memory Storage Systems''. ''Association for Computing Machinery (ACM)''. Dept. of Comput. Sci.,Nat. ChiaoTung Univ., 15 Mar 2007. <http://portal.acm.org/citation.cfm?id=1244248>

[4] Nath, Suman; Gibbons, Phillip. ''Online maintenance of very large random samples on flash storage''. ''Association for Computing Machinery (ACM)''. The VLDB Journal, 27 Jul 2007. <http://portal.acm.org/citation.cfm?id=1731355>

[5] Lim, Seung-Ho; Park; Kyu-Ho. ''An Efficient NAND Flash File System for Flash Memory Storage''. ''CORE Laboratory''. IEEE Transactions On Computers, Jul 2006. <http://vlsi.kaist.ac.kr/paper_list/2006_TC_CFFS.pdf>

[6] ''NAND vs. NOR Flash Memory Technology Overview''. ''RMG and Associates''. Toshiba America, accessed 14 Oct 2010. <http://maltiel-consulting.com/NAND_vs_NOR_Flash_Memory_Technology_Overview_Read_Write_Erase_speed_for_SLC_MLC_semiconductor_consulting_expert.pdf>

[7] Bez, Roberto; Camerlenghi, Emilio; Modelli, Alberto; Visconti, Angelo. ''Introduction to Flash Memory''. ''IEEExplore''. STMicroelectronics, 21 May 2003. <http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=1199079&tag=1>

[8] Kawaguchi, Atsuo; Nishioka, Shingo; Motoda Hiroshi. ''A Flash-Memory Based File System''. ''CiteSeerX'' Advanced Research laboratory, Hitachi, Ltd., 1995. <http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.160.5142>

[9] Rosenblum, Mendel; Ouserhout, John. ''The Design and Implementation of a Log-structured File System''. ''Association for Computing Machinery (ACM)''. University of California at Berkeley, Feb 1992. <http://portal.acm.org/citation.cfm?id=146943&coll=GUIDE&dl=GUIDE&CFID=108397378&CFTOKEN=72657973&ret=1#Fulltext>

[10] Shimpi, Anand. ''Intel X25-M SSD: Intel Delivers One of the World's Fastest Drives''. ''AnAndTech''. AnAndTech, 8 Sep 2008. <http://www.anandtech.com/show/2614>

[11] Shimpi, Anand. ''The SSD Relapse: Understanding and Choosing the Best SSD''. ''AnAndTech''. AnAndTech, 30 Aug 2009. <http://www.anandtech.com/show/2829>

[12] Shimpi, Anand. ''The SSD Anthology: Understanding SSDs and New Drives from OCZ''. ''AnAndTech''. AnAndTech, 18 Mar 2009. <http://www.anandtech.com/show/2738>

[13] Corbet, Jonathan. ''Solid-State Storage Devices and the Block Layer''. ''Linux Weekly News''. Linux Weekly News, 4 Oct 2010. <http://lwn.net/Articles/408428/>

[14] Woodhouse, David. ''JFFS : The Journalling Flash File System''. ''CiteSeerX''. Red Hat, Inc, accessed 14 Oct 2010. <http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.128.6156&rep=rep1&type=pdf>

[15] Agrawal, Nitin; Prabhakaran, Vijayan; Wobber, Ted; Davis, John; Manasse, Mark. Panigrahy, Rina. ''Design Tradeoffs for SSD Performance''. ''Association for Computing Machinery (ACM)'', USENIX 2008 Annual Technical Conference, 2008. <http://portal.acm.org/citation.cfm?id=1404014.1404019>

[16] Lee, Sang-Won, et al. ''A Log Buffer-Based Flash Translation Layer Using Fully-Associative Sector Translation''. ''Association for Computing Machinery (ACM)''. ACM Transactions on Embedded Computing Systems (TECS), Jul 2007. <http://portal.acm.org/citation.cfm?id=1275990>

[17] Micron Technology Inc, ''Reach New Heights in Computing Performance''. <http://www.micron.com/products/solid_state_storage/client_ssd.html> (may need reworking)

[18] Flash Memories. 1 ed. New York: Springer, 1999. Print.

[19] Nonvolatile Memory Technologies with Emphasis on Flash: A Comprehensive Guide to Understanding and Using Flash Memory Devices (IEEE Press Series on Microelectronic Systems). New York: Wiley-Ieee Press, 2008. Print.

[20] Nonvolatile Semiconductor Memory Technology: A Comprehensive Guide to Understanding and Using NVSM Devices (IEEE Press Series on Microelectronic Systems). New York: Wiley-Ieee Press, 1997. Print.

=External links=

Relivant Wikipedia articles: [http://en.wikipedia.org/wiki/Flash_Memory Flash Memory], [http://en.wikipedia.org/wiki/LogFS, LogFS], [http://en.wikipedia.org/wiki/Hard_disk Hard Disk Drives], [http://en.wikipedia.org/wiki/Wear_leveling Wear Leveling], [http://en.wikipedia.org/wiki/Hot_spot_%28computer_science%29 Hot Spots], [http://en.wikipedia.org/wiki/Solid-state_drive Sold State Drive].

=old=

Hey guys,

This is what I've got so far... mostly based on wikipedia:

Flash memory has two limitations: it can only be erased in blocks and and it wears out after a certain number of erase cycles. Furthermore, a particular kind of Flash memory (NAND) is not able to provide random access.
As a result of these Flash based file-systems cannot be handled in the same way as disk-based file systems. Here are a few of the key differences:

- Because memory must be erased in blocks, its erasure tends to take up time. Consequently, it is necessary to time the erasures in a way so as not to interfere with the efficiency of the system’s other operations. This is is not a real concern with disk-based file-systems.
- A disk file-system needs to minimize the seeking time, but Flash file-system does not concern itself with this as it doesn’t have a disk.
- A flash system tries to distribute memory in such a way so as not to make a particular block of memory subject to a disproportionally large number of erasures. The purpose of this is to keep the block from wearing out prematurely. The result of it is that memory needs to be distributed differently than in a disk based file-system.
Log-sturctured file systems are thus best suited to dealing with flash memory (they apparently do all of the above things).

For the essay form, I'm thinking of doing a section about traditional hard-disk systems, another about flash-memory and a third about flash systems. At this point, I am imagining the thesis as something like, "Flash systems require a fundamentally different system architecture than disk-based systems due to their need to adapt to the constraints inherent in flash memory: specifically, due to that memory's limited life-span and block-based erasures." The argument would then talk about how these two differences directly lead to a new FS approach.

That's how I see it at the moment. Honestly, I don't like doing research about this kind of stuff, so my data isn't very deep. That said, if you guys could find more info and summarize it, I'm pretty sure that I could synthesize it all into a coherent essay.

Fedor

Talk:COMP 3000 Essay 1 2010 Question 10

2010-10-14T16:51:58Z

Abujaki:

COMP 3000 Essay 1 2010 Question 10

2010-10-14T16:51:07Z

Abujaki: /* Flash Memory */

Talk:COMP 3000 Essay 1 2010 Question 10

2010-10-13T03:23:53Z

Abujaki: Added notes to part 1

Talk:COMP 3000 Essay 1 2010 Question 10

2010-10-12T15:17:42Z

Abujaki: Added my email for contact

Talk:COMP 3000 Essay 1 2010 Question 10

2010-10-12T12:55:46Z

Abujaki:

Talk:COMP 3000 Essay 1 2010 Question 10

2010-10-12T12:23:00Z

Abujaki:

Talk:COMP 3000 Essay 1 2010 Question 10

2010-10-05T13:19:14Z

Abujaki:

I used Google Scholar and came to this page http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=812717&tag=1#
Which briefly touches on the issues of Flash memory. Specifically, inability to update in place, and limited write/erase cycles.

Inability to update in place could refer to the way the flash disk is programmed, instead of bit-by-bit, it is programmed block-by-block. A block would have to be erased and completely reprogrammed in order to flip one bit after it's been set.
http://en.wikipedia.org/wiki/Flash_memory#Block_erasure

Limited write/erase: Flash memory typically has a short lifespan if it's being used a lot. Writing and erasing the memory (Changing, updating, etc) Will wear it out. Flash memory has a finite amount of writes, (varying on manufacturer, models, etc), and once they've been used up, you'll get bad sectors, corrupt data, and generally be SOL.
http://en.wikipedia.org/wiki/Flash_memory#Memory_wear

Filesystems would have to be changed to play nicely with these constraints, where it must use blocks efficiently and nicely, and minimize writing/erasing as much as possible.

Talk:COMP 3000 Essay 1 2010 Question 10

2010-10-05T13:13:34Z

Abujaki: Limitations of flash researched