Results 1 to 9 of 9

Thread: FastECC: fastest Reed-Solomon codec for >30 parity blocks

  1. #1
    Programmer Bulat Ziganshin's Avatar
    Join Date
    Mar 2007
    Location
    Uzbekistan
    Posts
    4,572
    Thanks
    779
    Thanked 687 Times in 372 Posts

    FastECC: fastest Reed-Solomon codec for >30 parity blocks

    Last weeks I worked on the FastECC library. Now the version 0.1 (encoding only) is almost finished, I just need to update the docs before release.

    The library implements Reed-Solomon coder, like a lot of programs around. What's unusual is its use of FFT for really fast implementation. And what's especially unusual for me is what I developed novel math method for fast RS decoding. It's very simple, but I was unable to find its description in math papers around. Note that it is not included in current sources, but i already implemented and tested it, so it really works.

    Unforunately, the library doesn't seem very useful today - modern media is very reliable and there are more chances that entire hdd/ssd will fail rather than individual sectors, and for data transmission thousands of ECC blocks are too much.

    One question i have to all readers is how to name the library? FastECC name seems too generic

  2. Thanks (7):

    Christoph Diegelmann (9th May 2017),Cyan (7th May 2017),encode (11th May 2017),hexagone (8th May 2017),Piotr Tarsa (7th May 2017),Shelwien (7th May 2017),SolidComp (8th May 2017)

  3. #2
    Member Skymmer's Avatar
    Join Date
    Mar 2009
    Location
    Russia
    Posts
    688
    Thanks
    41
    Thanked 173 Times in 88 Posts
    No offense, but the title of topic looks like it have been created by Hamid

    As for the name: i can suggest a simple scheme. Bulat Ziganshin ECC or BZECC

  4. Thanks:

    Mike (7th May 2017)

  5. #3
    Member
    Join Date
    Jun 2009
    Location
    Kraków, Poland
    Posts
    1,495
    Thanks
    26
    Thanked 131 Times in 101 Posts
    Unforunately, the library doesn't seem very useful today - modern media is very reliable and there are more chances that entire hdd/ssd will fail rather than individual sectors, and for data transmission thousands of ECC blocks are too much.
    I wouldn't be so sure. Bit rot detection and repairing is still an active topic. Look at:
    https://en.wikipedia.org/wiki/Data_degradation
    https://en.wikipedia.org/wiki/Data_scrubbing

    Average Joe probably wouldn't care much about ECCs - if some file once in a while gets damaged then probably it won't be a disaster.

    Despite that eg SSD have error checking and (presumably) error correction, unrecoverable errors can happen. See here: http://techreport.com/review/27909/t...heyre-all-dead
    Samsung SSD drives survived for a long time after the first unrecoverable error.

    I had some HDD drives and they usually were dying slowly (multiple weeks). Errors were accumulating to the point that OS won't boot, new OS install won't work, etc Only one of my HDDs died abruptly and that was relatively quickly after purchase (within two weeks AFAIR).

    IMO fast ECC would be an interesting proposition for data-centers and all kinds of sensitive data hosting.

  6. #4
    Member
    Join Date
    Nov 2014
    Location
    California
    Posts
    158
    Thanks
    51
    Thanked 44 Times in 33 Posts
    Reed-Solomon can be useful for distributed networks a la Bittorrent because there is no need to locate and fetch all pieces.

  7. #5
    Programmer Bulat Ziganshin's Avatar
    Join Date
    Mar 2007
    Location
    Uzbekistan
    Posts
    4,572
    Thanks
    779
    Thanked 687 Times in 372 Posts
    with yesterday post on hackernews it got 100+ stars and became one of most trending repositories today: https://github.com/trending/c++

  8. #6
    Member
    Join Date
    May 2017
    Location
    north america
    Posts
    2
    Thanks
    0
    Thanked 0 Times in 0 Posts
    Quote Originally Posted by Bulat Ziganshin View Post
    Last weeks I worked on the FastECC library. Now the version 0.1 (encoding only) is almost finished, I just need to update the docs before release.
    Unfortunately, the library doesn't seem very useful today - modern media is very reliable and there are more chances that entire hdd/ssd will fail rather than individual sectors, and for data transmission thousands of ECC blocks are too much.
    Why are thousands of ECC blocks too much? Say we want to transfer a 1GB file, not particularly large, video files or just an ISO image easily get that big these days. Say you split it into 4096 256kb chunks, even 64 parity blocks would give significant protection. This would protect against busts of dropped packets or losing some blocks/tracks from the sending or receiving disks. The storage/bandwidth overhead would be 1.5% or so. Similarly this could be useful for broadcasts (via network or radio) or filesharing/torrents. That way any received only needs to get 98.5% of the file to be able to rebuild any missing pieces.

    Question is how long does it take to add those 64 parity blocks? Sure other codes that support a max of 256 shards for parity+data could work as well, but the complexity of adding multiple levels of ECC or interleaving to prevent bursts of errors from killing the file would be expensive.

  9. #7
    Programmer Bulat Ziganshin's Avatar
    Join Date
    Mar 2007
    Location
    Uzbekistan
    Posts
    4,572
    Thanks
    779
    Thanked 687 Times in 372 Posts
    well, that i meant in the initial post: in the last years people lost interest in programs like Parchive. It's due to

    1) more reliable media - we no more use floppies/optical disks, and i don't remember that ssd/modern hdd ever said that cluster can't be read (but i seen that on usb flashes)
    2) most of our data today are audio/video files and it's not large problem if you lose a few sectors unless you hold a primary copy
    3) high-speed internet. with 100 mbit/s, one can download entire BD in a hour

    FastECC is absolutely useless for RAID storage (such as hadoop). With RAID, when one sector is overwritten, RAID software should read all other data sectors in the same shard in order to recompute parity sectors of the shard, and then overwrite all these parity sectors. So, RAID software developers are looking for solutions that will allow them to read/write less sectors on each operation (such as pyramid codes), rather than opposite

    FastECC is probably useless for any hardware controllers (SSD, Ethernet, LTE, DVB...). These controllers work with analog signals and tend to use soft decoders to extract as much data as possible (soft decoders understand that data received as 7 have more chances to be decoded as 8 rather than to be decoded as 2, and can deal even with something like 7.4 which is more probably 8 rather than 6). Soft decoders are aboslutely out of my Math skills, so if someone will build soft decoder, it will be not FastECC, but other great lib (and most probably not free)

    there are some applications still. PAR3 is one of them - it's still interesting for some people, although not many. Various communication applications and P2P data storage are also frequently mentioned here and in the HackerNews thread.



    I made a quick speed comparison and found that FE is faster than 16-bit RS codec in MultiPar starting from ~32 parity blocks. 8-bit RS codecs such as ISA-L should be even faster than 16-bit ones. And with 20% redundancy 32 parity blocks means 160 data blocks, close to the maximum possible for 8-bit RS. So, it seems that FE territory starts right where 8-bit codecs territory ends - if you need more than 255 data+parity blocks, FE should be faster than any 16-bit RS coders, otherwise 8-bit ISA-L is preferable.

    Moreover, FE is free from patent restrictions that has any fast 16-bit RS codec using PSHUFB (i.e. SSSE3). And slow codecs are several times slower than MultiPar, so they have even less chances.

    There is a great alternative to FE - catid wirehair library, but afair it also may be covered with patents. It's already as fast as FE, but can be made several times faster using SSE. It's limited to 64000 source blocks, but amount of parity blocks can be arbitrary. It's LDPC codec, so not MDS, but chances that it needs even single extra block to recover is as low as 0.1%.

    Unlike Wirehair and MultiPar, FE doesn't work directly with arbitrary binary data - it works in GF(p) or GF(p^2), default is GF(0xFFF00001). This means that input data should be converted into 0..0xFFF00000 range, that further means that parity sectors are slighly longer that input ones (f.e. 4096 byte data sectors and 4100 byte parity sectors). This also limits its applications.

    So, overall, FE should replace any use of 16-bit RS codecs, while LDPC and 8-bit RS codecs will keep their niches.
    Last edited by Bulat Ziganshin; 12th May 2017 at 14:11.

  10. Thanks:

    Shelwien (12th May 2017)

  11. #8
    Member
    Join Date
    May 2017
    Location
    north america
    Posts
    2
    Thanks
    0
    Thanked 0 Times in 0 Posts
    Quote Originally Posted by Bulat Ziganshin View Post
    well, that i meant in the initial post: in the last years people lost interest in programs like Parchive. It's due to
    FastECC is absolutely useless for RAID storage (such as hadoop). With RAID, when one sector is overwritten, RAID software should read all other data sectors in the same shard in order to recompute parity sectors of the shard, and then overwrite all these parity sectors. So, RAID software developers are looking for solutions that will allow them to read/write less sectors on each operation (such as pyramid codes), rather than opposite
    Not I've come across pyramid codes before. Got a reference? I've heard of Merkle trees ( https://en.wikipedia.org/wiki/Merkle_tree ), is that what you mean?

  12. #9
    Programmer Bulat Ziganshin's Avatar
    Join Date
    Mar 2007
    Location
    Uzbekistan
    Posts
    4,572
    Thanks
    779
    Thanked 687 Times in 372 Posts
    nothing common with merkle trees (used to parallelize hashing). look at that: https://www.google.com/search?q=pyra...&oe=utf-8&aq=t

    pyramid codes minimizes overhead of online operations - i.e. when only one sector was changed, you want to minimize number of sectors that should be read/written. but of course, they are less effective (far from MDS) than RS codes

Similar Threads

  1. FARSH: hashing 30 GB/s!
    By Bulat Ziganshin in forum Data Compression
    Replies: 66
    Last Post: 17th October 2016, 09:21
  2. Adler32 on Large Blocks
    By encode in forum Data Compression
    Replies: 1
    Last Post: 2nd January 2015, 21:38
  3. fastest lossless video codec
    By Itemp in forum Data Compression
    Replies: 3
    Last Post: 2nd July 2012, 16:50
  4. 2G+ memory blocks
    By Shelwien in forum Data Compression
    Replies: 0
    Last Post: 6th March 2009, 02:13
  5. QuickLZ 1.30
    By spark in forum Forum Archive
    Replies: 18
    Last Post: 30th June 2007, 15:12

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •