Remove first 300M lines from 700 GB file on 1TB disk
unix.stackexchange.com
unix.stackexchange.com
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.
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.
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?
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...
I never had a single whiteboard interview in my life, so I can't give you advice on how to get better at them, sorry.
Back in university, I had a "Design and Analysis of Algorithms" course, and one of the first (toy) exercises was to implement a queue using other data structures. This solution with two stacks was what I came up with. That's 12 years ago now, good times :-)
Picking up new technologies doesn't require creativity. Being a good developer (these days) also doesn't require much creativity, especially if you're just implementing spec and not designing systems.
The best way to get better at puzzles is to practice puzzles! The reason I don't want to call these problems whiteboard problems is because it implies that they're only used in that context. These types of puzzles can be done for fun, too! Perhaps you start with simpler puzzles and try some simple solutions. You might solve a few. You'll try some harder puzzles and you'll get frustrated because the solution doesn't come immediately. Sometimes you'll combine two solutions you've used previously to solve something more complex. It's an amazing feeling!
If you want a book of math puzzles, I recommend "Measurement" by Paul Lockhart. He explains and helps you explore math in the way he thinks it should be taught in schools, and I agree with him.
If you want something more programming focused, take a look at "Programming Pearls" by Jon Bentley. It's a very old book, so the constraints he has to work with are quaint by today's standards (do something without using more than a megabyte of RAM. Hah!), but they're good puzzles as far as I remember.
Good luck!
Edit to add: The most useful thing you'll get from spending time with puzzles from a certain field is the intuition about which tools to reach for and which to forget about. You'll still likely have to try for a bunch of tools before you find the ones that work the best (or at all), but you'll get better at choosing ones that are more likely to work sooner, so you'll be able to progress faster on harder puzzles. As Greg LeMond said about cycling: ‘[It] never gets any easier, you just go faster’ :)
Definitely tune that. The file-system is probably working in 4KiB blocks so there would be no benefit in working on smaller ones. In fact as you'll write to each block four times you are probably wasting a lot of time and causing more wear than you need to.
I would suggest something far bigger (in the MiB range at least), especially on traditional drives where reducing head movements is key but random access latency on SSDs is not as close to zero as many people think particularly for small writes. Make sure that whatever you move the data with is loading that full block of your desired size into RAM before starting to write to the destination (i.e. perhaps pipe through something like "buffer -s 4M" if your read/write tool of choice does not support this directly).
In fact an SSD might internally be working with MiB sized blocks, another reason to work in that scale at least and be careful of alignment where you can detect it or the lack of it.
But yes, that solution would definitely work if carefully optimised.
> The correct solution, of course, is to buy a second disk.
Definitely. Must faster, and you still have the original data in-place so you can run checksums to verify the new copy before committing to use it.
Also if working with network attached storage you have an extra set of considerations that will change the optimal block size to work with.
Figure out the output size, and create a sparse file with that size. You'll be able to use it like a regular file, but blocks will only take up space once you write to them.
Now simply copy from the input to the output file, starting at the end. Truncate the input file whenever the disk fills up.
The sparse file suggestion a sibling made is really great. Otherwise, you could reverse the chunks as you write them, and end up with a fully reversed file, or just have to be careful about block boundaries and know that contents are forward, but blocks are backward. I wouldn't want to bulk read a 700g file with line processing, if it's possible to ignore that.
This is great, although the line-vs-block-orientation issues will be tricky to make sure you get right, as others have pointed out. The truncate will almost certainly need to leave a partial last block.
But the basic idea still works: You could read the original file forward to find the index of the 300M'th line, and then just halt the stack reversing bit when you get there. Delete the whole original file and then stack it back.
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.
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.
Of course performance would suffer due to non-aligned access, but just as for regular files one could demand aligned access for optimal speed.
https://man7.org/linux/man-pages/man2/ioctl_ficlonerange.2.h...
>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?
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.
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.
$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.
Ok, $110.
https://www.amazon.com/Seagate-BarraCuda-Internal-Drive-3-5-...
i forgot about not-SSD for a second there.
I can't imagine unless s/he wants to accidentally lose the data any better alternative.
Even if this works perfectly, you never want to delete data you can't easily retrieve again.
Next Monday the client might change their mind
That can be avoided if your filesystem supports reflinks / copy_file_range (BTRFS, XFS, OCFS2). Just create a reflink of the file, drop all the blocks at the beginning of the reflink "copy" up to the one containing the line you want to start with using fallocate --collapse-range, and overwrite the remaining data up to the first line with some suitable fill character. For the JSON-encoded lines in this case spaces should work. Total disk space used: one data block for the padding plus some metadata for the reflink. No changes to the original file. No copying or relocating 700 GB of data. Quick, easy, and and safe. But you have to start with the right filesystem for it to work.
What would you do when the next time this happens it’s 300B lines from a 1PB file?
Something like
readLineOffset = 301
writeLineOffset = 1
While not read eof
line = Read(readLineOffset)
Write(WriteLineOffset, line)
readLineOffset ++
writeLineOffset ++ #!/usr/bin/perl
open(my $fh,">foo") or die($!);
for (1..100) {print $fh "$_\n"};
close($fh);
open($fh,'+<','foo') or die($!);
while(<$fh>) {
my $spot=tell($fh)-length($_);
seek($fh,$spot,SEEK_SET) or die($!);
s/\d/X/g;#replace digits with X's
print $fh "$_" or die($!);
}
close($fh);
That people normally use temporary files, has two reasons: The first is that it is much safer if something goes wrong. You then still have the original and not some half-way processed file. The other reason is that reading and writing in text mode does not really work. But you can of course process text files as binary files and deal with line endings yourself.
And another engineer to say "Are you kidding me? Just buy another freakin' disk!"
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.
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.
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.
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.
memmove(beginning_of_file, beginning_of_file + 300_m_line_offset, file_size - 300_m_line_offset);
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.
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/
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/ don't love the name, but it seems to be somewhat established terminology.
"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.
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.
Oh, but it’s legacy. Better reinvent chunks of the wheel every 5 years.