Red Winter is set in Russia in 1920, as former Russian and then Chekist soldier Nikolai Levitsky tries to return to his family. He's seen the reality of what bringing about the "revolution" involves and decided he wants nothing more to do with it. But his family is missing, along with the rest of the residents of their village. Well, except one elderly woman driven mad by the horrors she survived at the hands of a unit of Chekist soldiers, led by one calling himself "Koschei the Deathless". Nikolai, uncertain whether his family is still alive or not, chooses to bet on hope and sets out to find the monster and rescue his family. Along the way he meets two women, Tanya and Lyudmilla, both seeking Koschei for their own reasons, and a man and a young girl he's chosen to protect. There's also the little matter that the State doesn't just let soldiers walk away. . .
The book ends on a relatively happy note. Happier than I'd expect if it had been written by a Russian. The sense of a country where everyone is living in a constant state of fearful, heightened awareness was conveyed well. Everyone hedges around others. Nobody is going to reveal too much about themselves, where they're from, where they're going. Because they can't tell if the person they're talking to is going to turn them in to the Chekists. Or just kill them because they think they're a Chekist. Or kill them because they're starving. Everyone is constantly evaluating everyone else in terms of how much they can be trusted, or how useful they are. "How likely is this person to kill me in my sleep, and are they valuable enough to take the risk?" It's very effective at creating suspense, because it feels as though any character's paranoia could take over at any moment and throw everything into chaos.
Also, I enjoyed the incorporation of the physical landscape in Russia. These massive, endless plains where Nikolai can see so far that he can't necessarily make out what it is he's seeing. Either that or he's traveling through dense, dark woods trying to keep anyone from spotting him from miles away. But then he can't tell what's around him. Both feed into that paranoia, either the sense something could be lurking unseen, or the sense of being exposed, visible to anyone from any direction for miles and miles. Either you can't hide, or you can't run.
'For me, he was a shadow. Galina had called him Koschei the Deathless. She had put a knife in him and it had done him no harm, but the Deathless One was no more real than One-Eyed Likho, and no one is immune to the blade of the knife. She must have made a mistake.
Anyone can die. I had seen that often enough.'