15 ms·
Remove first 300M lines from 700 GB file on 1TB disk
- rwmj 6y agoThe true answer is buried about half way down the page. The fallocate command / syscall nowadays allows you to remove or insert block-aligned extents at the beginning of a file, assuming you're using a modern filesystem like ext4 or xfs. The only difficulty that remains is working out how many blocks to remove and dealing with the non-aligned part. LWN has a few articles on this topic: https://lwn.net/Articles/589260/ https://lwn.net/Articles/589260/ https://lwn.net/Articles/629965/ https://lwn.net/Articles/629965/
- OskarS 6y agoI don't know man, the top answer is clever, but it's also a pretty straight-forward UNIX way of doing it, and pretty easy to understand. Going around messing with trying to convert to filesystem blocks and obscure syscalls that only work on certain file systems seems way scarier in comparison. And you're almost certainly going to end up with extra characters at the beginning, so you having to do some version of the dd thing anyway. The actual answer, as others have pointed out, is to buy a new drive. If the data has any value, it's worth it.
- coldcode 6y agoI worked at a place where the entire's company business (images) was stored on a single large drive, and the CEO was too cheap to buy a second, so there was no backup. Never underestimate how dumb people can be sometimes.
- Jugurtha 6y agoWas that a special type of drive that cost as much as the company's value? Was there any justification besides the cost of the drive? Even something like 'I live dangerously.'
- pjc50 6y agoInaction, deluding oneself about risks and hubris all have a special value all their own. Very popular these days.
- mlonkibjuyhv 6y agoHey colleague! Of course whatever was used to make those images disappeared some 10 years ago. And the actual mint images are already gone from an earlier disk-crash. THESE images are actually made from systems that have been running at a customer site for years and years.
- Wowfunhappy 6y ago> The actual answer, as others have pointed out, is to buy a new drive. If the data has any value, it's worth it. If you read the comments on the StackExchange question, the scenario that prompted it does make sense: >> I'm migrating our company's database and this is 700GB file with profile data in JSON format, each line one profile. The process that imported the data stopped after running several days after 70% done. Now, to not repeat the full import, I want to cut the first 70% (300 million lines). >> [One option would be] exporting the data from the old DB again, skipping the first 300 Mio entries and cp it again over to the new and import it there. It roughly takes a day. I just thought there must be a way to do it in place: the data are already there - just truncate the first part of it and continue. So it's not as if this is the only copy of the data. It would just be nice if there was a way to cut some of it without recopying everything.
- OskarS 6y agoYeah, fair enough, that's a reasonable scenario.
- Liquid_Fire 6y agoIn that case, surely it would be possible to point the database importer at a pipe, the other end of which is the output of `tail -n +300000000 db_dump.json`. No need to actually modify the file.
- deleted 6y ago[deleted]
- londons_explore 6y agoOr, if it's JSON, just replace the first 300M lines with spaces. You probably don't care if it's 299M rows, so just dd over the start of the file, guessing the number of bytes to write and choosing a low number to be sure. You'll know if you're missing records when you run a count(*) on the database when it's loaded. Use some hex editor (most support files larger than ram) to check you have the necessary opening square brace at the start of the file, and to remove whatever partial record is there. Sure, it isn't elegant, but is a solution most people can come up with without needing to spend 20 minutes hunting through man pages.
- magicalhippo 6y agoI've found it curious that so few (any?) file systems allow for non-aligned starting blocks. Ie keeping an offset into the initial block. That would make prepending files rather trivial, as well as trimming the start of files (hello log files). Of course performance would suffer due to non-aligned access, but just as for regular files one could demand aligned access for optimal speed.
- yencabulator 6y agoExtent-based filesystems have no problem with that, and performance wouldn't be impacted either. The preserved tail of the first extent would have to copied / CoWed, that's it. https://man7.org/linux/man-pages/man2/ioctl_ficlonerange.2.html https://man7.org/linux/man-pages/man2/ioctl_ficlonerange.2.h...
- ComodoHacker 6y agoFrom the linked article: >The immediate user for this operation would appear to be video editing applications, which could use it to quickly and efficiently remove a segment of a video file. Do any of Linux video editor apps actually employ this feature?
- kazinator 6y agoA segment of a video file isn't going to be block-aligned. Deleting a non-block-aligned segment of a file means copying the remaining data over it and then truncating the file at the end using the ancient truncate function. It's not obvious how that can be improved.
- TheOtherHobbes 6y agoWithout getting into the details of video compression, you can't remove arbitrary parts of a video file without causing problems when the file is played. Even if the video is uncompressed you will still need to remove entire frames and then - for most formats - reconstruct a file header at the start of the file. This is a much harder problem than throwing away x% of a file without worrying about the structure of the content. It's fairly easy to solve that problem at the disk block level. But if you're trying to keep the data structures error-free, you're going to have to do a lot more work.
- yencabulator 6y agoAren't all video editors "non-linear editing" these days anyway? All they mutate when you're editing is a small amount of metadata called edit decision list. The output file is only created when you explicitly execute a "render" operation, everything you see before that is just parts of the input files mixed as needed.
- jmt_ 6y agoThe dd approach is interesting. Editing a file like that in place cowboy style with dd would fill me with anxiety however
- tumetab1 6y agoCan anyone explain how dd is able to read and write a file at the same time without using a temporary file? :\
- arbitrage 6y agoit opens up two file handles, reads from the first and writes to the second.
- tumetab1 6y agoThat doesn't fully explain it but I think I got it, each line is overwritten with what it's place on the 300th line after. Something like readLineOffset = 301 writeLineOffset = 1 While not read eof line = Read(readLineOffset) Write(WriteLineOffset, line) readLineOffset ++ writeLineOffset ++
- ComodoHacker 6y agodd reads and writes in blocks of bytes, not lines. You have to figure out where 300th line starts beforehand.
- netmonk 6y agoMore over, how dd deal with EOL ? and counting them ?
- jrochkind1 6y agoI believe it doesn't, and the solution in the OP first counts EOLs to get the byte offset you want, then tells dd what to do just in terms of byte offsets.
- hprotagonist 6y agothe only answer i’d use here is “go buy another 1TB drive and then ...” $100 and a day and a half for shipping is a much better idea than playing russian roulette with work data by adjusting files in-place.
- help56883 6y agoYeah that's right. Even 2 TB drives don't cost $100 though.
- hprotagonist 6y agoSamsung 850 EVO 250GB 2.5-Inch SATA III Internal SSD (MZ-75E250B/AM) https://www.amazon.com/dp/B00OAJ412U/ref=cm_sw_r_cp_api_fab_JaGAFbHSEVABQ https://www.amazon.com/dp/B00OAJ412U/ref=cm_sw_r_cp_api_fab_... Ok, $110.
- hervature 6y agoParent is agreeing with you. 2TB drives do not cost $100. https://www.amazon.com/Seagate-BarraCuda-Internal-Drive-3-5-Inch/dp/B07H2RR55Q/ref=sr_1_3?crid=1XOSDB8OH2C9M&dchild=1&keywords=2tb+hard+drive&qid=1600783165&s=electronics&sprefix=2tb%2Celectronics%2C205&sr=1-3 https://www.amazon.com/Seagate-BarraCuda-Internal-Drive-3-5-...
- hprotagonist 6y agoah damn platters are cheap! i forgot about not-SSD for a second there.
- silon42 6y agoI'd use the answer 2 (but attempt to just compress the output first, depending on type of data, leaving original file alone)
- abhayhegde 6y ago
- lucb1e 6y agoThis comes up from time to time and depending on luck you'll get people saying it's stupid and just buy another hard drive, or someone goes nerdy and figures out it can be done with conv=notrunc. The top answer uses that as well, just like I did when answering a previous instance of this question on stackexchange (that question was about compressing a file without having to store the compressed version in parallel -- same question different application https://unix.stackexchange.com/a/383019/30731 https://unix.stackexchange.com/a/383019/30731).
- deleted 6y ago[deleted]
- adwn 6y agoMy first idea was to solve this "queue" (FIFO) problem with a "two stacks" solution: Without special system calls, files can only be appended and truncated at the end, not the beginning, so they behave like a stack. Two stacks can be used to simulate a queue. Implementation sketch: 1) Successively read the last 1 kiB from the source file, append it to a temporary file, and truncate 1 kiB from the source file. 2) Truncate the last 300M lines from the temporary file. 3) Successively read the last 1 kiB from the temporary file, append it to the destination file, and truncate 1 kiB from the temporary file. This way, you never need more than 1 kiB of additional disk space (tune this number as desired). I think this is an elegant solution. The correct solution, of course, is to buy a second disk.
- bjornedstrom 6y agoYou win the internet today, that's a fantastic solution. I think the only gotcha is to handle the last block read in step 1 in case it's not evenly 1 kiB. Otherwise the first read in step 3 will overlap the blocks.
- dasil003 6y agoYou should dub this “slinky copy”
- anthropodie 6y agoYou must be pretty good at whiteboard interviews. I can pick up new technologies quickly and I am a good developer (at least my manager says so) but I can never come up with elegant solutions like this to what I call a whiteboard problem. This is the exact reason why I fail at those whiteboard interviews. Any suggestions for me?
- piva00 6y agoThe only suggestion I have is practice, it's a skill like many others where practice makes you aware of patterns and these patterns have common or known approaches. Of course just blindly applying patterns won't cut it, the practice part is that the common ones become ingrained and you can focus your mental effort into the specifics of a new problem. Rehearsing your knowledge of data structures and algorithms while studying algorithmic quizzes can get you pretty far, it's time-consuming though so it needs to be something you get fun out of it, I don't get much fun out of it so I have done the bare minimum that is needed for this industry...
- emerged 6y agoWhats wrong with this: 1) scan to find 300m line offset N 2) shift file from N to 0 using reads+writes 3) truncate last N bytes You can print out the current offsets in case of a crash you need to resume from. You read exactly the size of the file once and write it exactly once, and it's safe.
- kreetx 6y agoBeaten to the punch :)
- ComodoHacker 6y agoIt's #1 answer. Nothing wrong except it isn't safe. Depending on type of crash you might not have a chance to see your printed offset.
- emerged 6y agoYou can miss a printed offset and it still works. The file data exists in two places while writing the offset.
- tzs 6y agoThe old fashioned way to deal with making sure you see your printed offsets is to actually print your offsets. You'd go to the machine room and run the command on the system console, which would typically be a hardcopy terminal like a DECwriter. The trendy modern way, of course, would be to use the cloud. Upload the offsets to the cloud as they are produced, pausing until you get confirmation after each upload. A more clever and/or foolhardy way is to put the crash recovery markers in the file itself. Place evenly spaced markers throughout the file, saving the data that they overwrite in a separate file. Then do your in-place file shifting. Finally, replace the markers with the saved data.
- anon946 6y agoIf you print the offset after a write has safely completed, then it should still work. The internal copy is idempotent, up to the number of bytes in the first 300M lines. In other words, assuming reasonable line lengths, you can safely re-do a copy operation. So if you crash, you may not have printed out the last offset, but you have recorded a recent offset. You can then just restart from that recent offset.
- kreetx 6y agoDisregarding the copy time, why not just find the 300M-th newline and move everything else down, then truncate?
- kingofpandora 6y agoWhat does "move everything else down" mean?
- jgalar 6y agoI would guess memory map the whole file, then do the equivalent of: memmove(beginning_of_file, beginning_of_file + 300_m_line_offset, file_size - 300_m_line_offset);
- kreetx 6y agoAs someone not too familiar with precise system calls/file system internals, I just meant that if the "keep" part of the file starts at byte 1234, then start moving all of them at an above that location to locations at and above 0 (i.e to the beginning). And when the last byte is now at byte `last - 1234` then truncate the file. One could write a tiny program to do that and I'd feel relatively safe running that. (All that `dd` stuff would probably work too, and faster, but you'd need to spend time learning it first then. But that tool probably has discrepancies between OS'es, has history, etc. Can be simpler to just write the program.) EDIT: and you can iterate in blocks of the size of the disregarded prefix.
- vaccinator 6y agoWhy do you need to move everything down? Can't you just tell the filesystem that the file moved and changed size?
- barbegal 6y agoThe user wants to avoid having to rewrite the file to disk "This is one option. Exporting the data from the old DB again, skipping the first 300 Mio entries and cp it again over to the new and import it there. It roughly takes a day. I just thought there must be a way to do it in place: the data are already there - just truncate the first part of it and continue. But I'm not in a desperate position. I have backups and no (extreme) time pressure. So in this sense it's an exercise." Solutions such as: compressing, splitting into smaller files, using dd would require re-writing most or all of the file so are not what the user is looking for Using fallocate to change where the file starts from would appear to be the correct solution but it would leave some unwanted data at the start of the file. The best solution would be to use fallocate and then overwrite the unwanted lines in the first block with newline characters.
- drran 6y agoIn gdb, conditionally break on fopen() call, then use fseek to skip first 300M lines, then continue import.
- jerf 6y agoWhile it is fun to discuss the literal question given, this is very likely one of those "XY problems" [1]. You don't need a file with the first 300M lines cut off. You need a view of the file with the first 300M lines cut off. To the consumer of such a file, there is no difference between that and a file with the first 300M lines cut off. One way to produce that is by producing a literal file on disk with that, but it's not the best or even IMHO a good way. The easiest way is to use "tail -n +300000001" as someone mentioned, but then, piping the result to where it needs to go. In a bad scenario, the target program requires a file, in which case you can set up a FIFO: https://www.howtoforge.com/linux-mkfifo-command/ https://www.howtoforge.com/linux-mkfifo-command/ In the worst case, the consuming program insists on random access to the file, in which case, finally, you have the problem that you need a real (OS-level) file. But as this is a database reload situation (expand the comments in the question to see this), this is unlikely to be the case. (In a truly desperate situation, you could grab your favorite scripting language that has FUSE support and set up a special-purpose one-file FUSE filesystem that serves that one file with the front cut off and translates all seeks correctly. It's probably easier than you think, but certainly I'd have to be backed into a corner pretty hard to do this.) The upshot is, files aren't files, or to put it another way, the file!interface isn't the same as files!disk. File!interface is an interface that allows you to read, write, seek, etc. and files!disk are a particular implementation of a bag of bytes on disk, and despite using the same name, it's important to keep them straight. The user doesn't need a file!disk that does what need, they need a file!interface that will serve the contents they need. It is much easier to get the file!interface than the file!disk in this situation. Or to put it another another way, it's all just numbers. Files have no ontological existence, really. It's all just a question of what numbers will be returned by a "read". If you return the right numbers, you have the "right" file, regardless of how those right numbers appeared. I realize this may sound simple and obvious when I say it, but it is a major mental block that almost all junior programmers and a fair number of mid-level programmers have. It especially causes problems when you're a network programmer doing network things; you really need to understand that in the end, it's all just numbers, and as long as you consume the correct numbers, and produce the correct numbers, the right things will happen. (The simplest case of this was when I produced a network server on port 80 that, if you poked it with the correct magic sequence, did the thing it was supposed to do, but if you did anything else, returned a hard-coded byte string that "happened" to be an HTTP response that said what you did wrong and how to fix it, completely ignoring the rest of the "request", including ignoring if it was even HTTP at all. You don't need an HTTP library to produce an HTTP response, you just need to produce the right numbers on the TCP stream. Nginx does something similar to detect when you're trying to use HTTP on an HTTPS port, so it returns a nice message instead of a bare binary SSL negotiation.) [1]: http://xyproblem.info/ http://xyproblem.info/ don't love the name, but it seems to be somewhat established terminology.
- utf_8x 6y agoAssuming the data is at all important, "go buy another drive" is really the only valid solution here...
- ed25519FUUU 6y agoA well balanced team will have two types of engineers. One says "Here's the DD incantation that if uttered precisely right will produce the desired result." And another engineer to say "Are you kidding me? Just buy another freakin' disk!"
- jariel 6y agoYes, and that team should have 1 guy saying DD it, and the rest saying 'buy a disk' even if most of them already thought to DD it. It's like trying to fix an engine that's running. My god man, why would anyone try to do that, other than to put it on YouTube.
- zadokshi 6y agoYou just cat/pipe it to an Amazon s3 bucket (check out s3 command line tools), trimming the lines you don’t want, and piping through bzip2 as well if needed. Storage cost for an hour or so to hold in s3 it is quicker and cheaper than trying to muck around installing a second hard drive.
- saagarjha 6y agoYou’ll need a good connection, though!
- OldHand2018 6y agoHow many lines are in the 700GB file? What percentage of the file does the first 300M lines take up? At work, we have lots of 20-30GB text files that gzip down to 14-15% of the original size. If this 700GB file was similarly populated, a gzip of the whole thing would be 100GB or so. Doing a tail piped to the gzip command would work.
- exabrial 6y agoIf the data is irreplaceable, the correct answer is: Get another disk.
- hamburglar 6y agoCaveat: yes, the real answer is buying more disk because it's safest, but I have a couple of outrageous suggestions that I haven't seen floated: 1) custom FUSE filesystem that just skips the first N bytes of a file with a given name. Calculate N ahead of time by reading the file (you could calculate it on-demand but this will introduce a massive perf delay in some early file op that could cause a timeout for whatever software is reading the file) 2) (warning: this sounds insane but I've actually seen embedded devices that do this type of gymnastics in the name of not buying more storage space) if it's acceptable to temporarily have the file not be a text file, you could write custom code for sliding the data forward in the file by N bytes, starting with the N + (2*blocksize)th byte. The first two blocks are left until the end because you encode the progress of this operation into a state block, which includes a SHA of the state for validation purposes and which is written atomically, alternating between block 0 and 1 of the file. Your actual move of data must be designed in such a way that each data write is nondestructive if its state write is lost (i.e. it can only write to scratch space). Resume an interrupted move by figuring out which state validates and has the higher serial number. This is not something I'd attempt as a one-off. I'd want to be damn sure this code was well-tested.
- pnutjam 6y agovim <filename> 300000000dd :wq
- freetanga 6y agoOn mainframe, a one step JCL with a smart DFSORT and proper disk allocation would do this without blinking... Oh, but it’s legacy. Better reinvent chunks of the wheel every 5 years.
- sgt 6y agoJust for fun of course, but how about changing the low level data in the inode structure and having it point to a data block that is 300M lines past the start? Can this be done with debugfs, I wonder?
- nitwit005 6y agoI find myself imagining that one of the lines turns out to be more than half the file size, and picking a solution that fails to account for that possibility.