I though it could be TRIM issue despite the fact that I have more than 20GB free. I tried almost everything. I factory reset it multiple times. No help.
Then did a fresh Install of CM, still issue wasn't resolved. Factory reset it multiple times, but to no avail. Then reverted back to Stock 4.4.4 after flashing Factory image through Fastboot, but sh** happened again. Reset it, did fresh install of PA ROM, but this freaking issue just doesn't go away.
I had more than 20GB free on all occasions. I also used "Lag fix" app from Play Store, but it didn't help either. Is this a TRIM issue? Did you experience this issue at all?